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

So far we have created a fairly inert husk of a circular_buffer class. The few methods we've written allow you to easily discover that it doesn't have anything in it. And that's about it. We need to get data in and we need to get data out.

Refining the data representation

But first, let's consider the internal data representation. We originally decided that the buffer is empty when m_front == m_back, and full when 'm_front+1' (modulo m_buffer size) == m_back.

If you're observant you'll notice that this means the m_buffer array will never get completely filled. The circular_buffer will be considered full when there is one space left in m_buffer. Certainly, for a buffer of ints this might be acceptable, but a circular_buffer of a large custom data type might be consuming a lot of memory unnecessarily.

So what can be done about this? A simple mechanism that will work well is to set the m_front pointer to 0 when the buffer is empty. This simple change means the following methods change:

template <typename T>
circular_buffer<T>::circular_buffer(size_t capacity)
: m_capacity(capacity),
buffer(new value_type[capacity]),
m_front(0), //< initialisation change here
m_back(buffer.get())
{
}

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

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

Getting data in

Following STL traditions, we'll provide a push_back method to push an item onto the back of the circular_buffer. At this point, we must decide what to do when the buffer is full. The options are:

• throw an exception
• return an error code
• silently ignore the data and leave the circular_buffer unchanged
• accept the data and consume the oldest peice of data at the back of the buffer

We'll choose the latter option. It would be perfectly possible provide several options in the future, either by a template traits parameter, a parameter to the push_back method, or a set of overloaded functions. This is left as an excercise for the reader.

Traditionally, a push_back method returns void, but we'll return a boolean value: true normally, or false if the new data has pushed old stale data from the back of the buffer. The signature is in the class declaration is therefore:

bool push_back(const value_type &);

It's basic template-code good practice to pass the parameter as a const reference. We'll not go into the reasons here, but make sure you know why.

Here's our first go at the implementation of push_back...

template <typename T>
bool circular_buffer<T>::push_back(const value_type &value)
{
 *m_back = value;

 value_type *const next = wrap(m_back+1);
 if (!m_front)
 {
     // first entry in the buffer
     m_front = m_back;
     m_back = next;
     return true;
 }
 else if (m_front == m_back)
 {
     // buffer is full already, throw something away
     m_front = m_back = next;
     return false;
 }
 else
 {
       m_back = next;
       return true;
 }
}

You'll notice that I have incanted a new method, wrap. This is a little internal helper that takes a pointer and wraps it around into m_buffer if it falls of m_buffer's bounds. We're going to be doing this quite a lot.

private:
value_type *wrap(value_type *ptr)
{
 assert(ptr < buffer.get() + m_capacity*2);
 if (ptr >= buffer.get()+m_capacity)
      return ptr-m_capacity;
 else
      return ptr;
}

Now let's check that it all works correctly:

int main()
{
circular_buffer<int> cb(5);

assert(cb.push_back(1));
assert(cb.size() == 1);
assert(cb.capacity() == 5);
assert(!cb.empty());

assert(cb.push_back(2));
assert(cb.size() == 2);
assert(cb.capacity() == 5);
assert(!cb.empty());

assert(cb.push_back(3));
assert(cb.push_back(4));
assert(cb.push_back(5));
assert(cb.size() == 5);
assert(cb.capacity() == 5);
assert(!cb.empty());

assert(!cb.push_back(6));
assert(cb.size() == 5);
assert(cb.capacity() == 5);
assert(!cb.empty());
}

Getting data out

We got it in there, now we need a way to get it out again. To read the contents we implement front(), which returns the item at the head of the buffer. We need two overloads, a const and non-const version:

// In declaration
reference       front();
const_reference front() const;

We can return a reference (or const_reference) to the data inside m_buffer to avoid unnecessary data copying.

What should the behaviour be when the circular_buffer is empty? Following the model set by existing STL containers, the result is undefined. The user Should Not do this, and if you do the class might just explode in a shower of bright purple sparks.

Of course, we'll be a bit more polite than that.

template <typename T>
typename circular_buffer<T>::reference circular_buffer<T>::front()
{
 assert(m_front);
 return *m_front;
}

template <typename T>
typename circular_buffer<T>::const_reference circular_buffer<T>::front() const
{
 assert(m_front);
 return *m_front;
}

Once we've read the item at the front, we need to remove it so we can get at the next item. The candidate for that is called called pop_front. Again, the user should not call pop_front if there is no data in the circular_buffer so we are quite at liberty to produce exciting purple sparks, or boring assertion failures.

template <typename T>
void circular_buffer<T>::pop_front()
{
 assert(m_front);

 value_type *const next = wrap(m_front+1);
 if (next == m_back)
     m_front = 0;
 else
     m_front = next;
}

If you're paying attention, you should by now be feeling very uncomfortable. There's an elephant lurking in the corner of this room. Clue: it's related to object lifetimes. We'll address this in the next installment.

Until then, we need to compose some reasonable tests for front() and pop_front(). To do this, I'll provide the entire code so far so you can see how it looks.

#include <boost/scoped_array.hpp>
#include <algorithm>

template <typename T>
class circular_buffer
{
public:
  typedef T                 value_type;
  typedef size_t            size_type;
  typedef value_type       &reference;
  typedef const value_type &const_reference;

  circular_buffer(size_t capacity);

  size_type    size()     const;
  size_type    max_size() const;
  bool empty() const;

  size_type capacity() const;

  reference       front();
  const_reference front() const;

  bool push_back(const value_type &);
  void pop_front();

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

  typedef circular_buffer<T> class_type;
  circular_buffer(const class_type &);
  class_type &operator=(const class_type &);

  value_type *wrap(value_type *ptr)
  {
  assert(ptr < m_buffer.get() + m_capacity*2);
  if (ptr >= m_buffer.get()+m_capacity)
        return ptr-m_capacity;
  else
        return ptr;
  }
};

template <typename T>
circular_buffer<T>::circular_buffer(size_t capacity)
: m_capacity(capacity),
m_buffer(new value_type[capacity]),
m_front(0),
m_back(m_buffer.get())
{
}

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;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::size() const
{
  return !m_front ? 0
      : (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
{
  const size_type count = size_type(-1) / sizeof(value_type);
  return std::max(count, size_type(1));
}

template <typename T>
bool circular_buffer<T>::push_back(const value_type &value)
{
  *m_back = value;

  value_type *const next = wrap(m_back+1);
  if (!m_front)
  {
      // first entry in the buffer
      m_front = m_back;
      m_back = next;
      return true;
  }
  else if (m_front == m_back)
  {
      // buffer is full already, throw something away
      m_front = m_back = next;
      return false;
  }
  else
  {
      m_back = next;
      return true;
  }
}

template <typename T>
typename circular_buffer<T>::reference circular_buffer<T>::front()
{
  assert(m_front);
  return *m_front;
}

template <typename T>
typename circular_buffer<T>::const_reference circular_buffer<T>::front() const
{
  assert(m_front);
  return *m_front;
}

template <typename T>
void circular_buffer<T>::pop_front()
{
  assert(m_front);

  value_type *const next = wrap(m_front+1);
  if (next == m_back)
      m_front = 0;
  else
      m_front = next;
}

int main()
{
  circular_buffer<int> cb(5);

  assert(cb.size() == 0);
  assert(cb.capacity() == 5);
  assert(cb.empty());
  assert(cb.max_size() > 0);

  assert(cb.push_back(1));
  assert(cb.size() == 1);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 1);

  assert(cb.push_back(2));
  assert(cb.size() == 2);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 1);

  assert(cb.push_back(3));
  assert(cb.push_back(4));
  assert(cb.push_back(5));
  assert(cb.size() == 5);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 1);

  assert(!cb.push_back(6));
  assert(cb.size() == 5);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 2);

  cb.pop_front();
  assert(cb.size() == 4);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 3);

  cb.pop_front();
  assert(cb.size() == 3);
  assert(cb.front() == 4);

  cb.pop_front();
  assert(cb.size() == 2);
  assert(cb.front() == 5);

  cb.pop_front();
  assert(cb.size() == 1);
  assert(cb.front() == 6);

  cb.pop_front();
  assert(cb.size() == 0);
  assert(cb.capacity() == 5);
  assert(cb.empty());

  // empty again

  assert(cb.push_back(7));
  assert(cb.size() == 1);
  assert(cb.capacity() == 5);
  assert(!cb.empty());
  assert(cb.front() == 7);

  assert(cb.push_back(8));
  assert(cb.push_back(9));
  assert(cb.size() == 3);
  assert(!cb.empty());
  assert(cb.front() == 7);

  return 0;
}