Friday 21 November 2008

C++: An STL-like circular buffer (Part 4)

Now it's time to think about the gory internal details of our circular_buffer.

Obviously, we need a data store for the buffer. A good old-fashioned array will do nicely, thank you. We'll need to remember the capacity of the array so we don't overrun it. And we must maintain a record of the front and the back of the data stored in the array. We could store these as indexes into the array, or as a pointer to the data. Let's go with the latter. There will be no need to separately store the number of items held in the buffer as it can be derived easily from the front/back pointers.

We want to play the C++ game nicely and make sure that we never leak resources, so we'll store the buffer in a boost::scoped_array (see here). So, here's a first stab at the data members for our class:
private:
const size_type m_capacity;
boost::scoped_array<value_type> m_buffer;
value_type *m_front;
value_type *m_back; // points to next unused item
Stylistic note #1: I really don't usually like m_ prefixes for member variables. However, since we will shortly need to create a public method called capacity(), we can't use that as a variable name. I don't want to instead use a bizarre variable name for "capacity", so I'll adopt this naming scheme.

Here's the plan:
  • We insert new data at m_back.
  • We read data from m_front.
  • When m_front == m_back (as it will after construction), the buffer is empty.
  • If the item after m_front is m_back, then the buffer is full.
Having established this, we can get on with some serious implementation:

The constructor

The constructor sets everything up as you'd expect. Note that we make it explicit so you can't write the nonsensical line: circular_buffer cb = 20;
// In declaration
explicit circular_buffer(size_t capacity);


template <typename T>
circular_buffer<T>::circular_buffer(size_t capacity)
: m_capacity(capacity),
m_buffer(new value_type[capacity]),
m_front(buffer.get()),
m_back(buffer.get())
{
}
Stylistic note #2: I'm writing the definitions of all methods out-of-line underneath the class declaration. This makes the class declaration far easier to read, at the expense of more typing are the definition.

If you're paying attention then you'll already realise that there may be some problems with this design. We'll get to this in Part 6.

Some easy questions

Now we can implement some of the simpler methods required by section 23.1 of the C++ standard. size() returns the number of items held in the buffer. empty() tells you if the container is empty (rather than emptying all the items out of it, which is a common newbie misunderstanding!) capacity() tells you how many items the container can hold. max_size() returns the size() of the largest possible container.
// In declaration
size_type size() const;
size_type max_size() const;
bool empty() const;
size_type capacity() const;

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::capacity() const
{
return m_capacity;
}

template <typename T>
bool circular_buffer<T>::empty() const
{
return m_front == m_back;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::size() const
{
return (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::max_size() const
{
// Yes, this is a rather nasty trick. We could pull the maximum value for
// size_type from std::numeric_limits instead of using -1.
// But we'll do something even nicer shortly.
const size_type count = size_type(-1) / sizeof(value_type);
return std::max(count, size_type(1));
}
The only reasonably complex function is size() and it's clear what's going on in there, isn't it?

Note the use of typename in the function implementations above. That is required to help the compiler deduce that
circular_buffer<T>::size_type is the name of a type; the poor thing can't work this out for itself.

Notable by their absense

The circular_buffer is notionally a sequence container (as defined by section 23.1.1 of the standard), by its very nature it does not support insertion or removal of items in the middle of the sequence. So we will not provide a version of insert() or erase(). We'll also chose not to support reserve(); unlike a growing container (e.g. std::vector), the circular buffer size must be supplied on construction. There is little point in providing an interface to change this capacity. (If you want to do this, I will leave it as an exercise for the reader).

Prohibit the prohibitable

Our choice of data storage means that it is not safe to copy or assign to a circular_buffer. Until we deign to fix this, we'll make sure that a user of the code can't shoot themselves in the foot:
// In declaration
private: // Not to be implemented
typedef circular_buffer class_type;
circular_buffer(const class_type &);
class_type &operator=(const class_type &);
This is a standard c++ technique: we declare the copy constructor and assignment operator in the private section and don't implement them.

Testing

Before we bring part 4 to rest, we'd best check that those methods work. I usually use Aeryn, a great unit test framework for C++. But rather than indoctrinate you into the cult Aeryn right now, we'll write some simple tests using nothing more that the standard C assert macro.
int main()
{
circular_buffer<int> cb(5);

assert(cb.size() == 0);
assert(cb.capacity() == 5);
assert(cb.empty());
assert(cb.max_size() > 0);
}
Right now, there's not much more we can do to the buffer. But that's all set to change...

5 comments:

Anonymous said...

Pete, I've been waiting for some actual code in this series, but now it's arrived I'm disappointed.

1. your blog layout makes the code hard to read
2. I don't think your unit tests would pass

I like the pictures though.

Pete Goodliffe said...

Thomas,

I agree that the blog layout isn't ideal for this.

This series a bit of an experiment as far as I'm concerned - I'm seeing if I can effectively draft an article through the medium of the blog.

Right now my observations are:

1. It's painful to write a serious amount of text in the blogger interface.

2. Putting code examples into blogger is hateful. HTML-conversion of templated C++ code is not my idea of a good time!

3. It's hard to read back your code when it's full of &lt;s in the editor.

I think I prefer my traditional method of writing right now!

My plan is to start off with some crude implementations, and through this series refine the circular_buffer until it's in a good shape, and the reader will have followed clearly each changes.

Anonymous said...

Thanks for your reply, Pete. Please don't let me put you off your experiment -- I'm enjoying the serialisation.

I don't use blogger, but surely there's some editor/api which allows you to write longer articles which include code blocks?

One of the bugs in the code I spotted seems to be fixed now, but size() still looks wrong.

the_exile said...

...and possibly empty is actually not_empty?

But at least you know we're reading!

I'm enjoying your writing as ever!

Pete Goodliffe said...

Heh! Yeah, you were right about empty(). Thanks.

Don't worry - these methods are all going to change at the beginning of part 5 :-)