Monday 24 November 2008

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

Time to air the dirty laundry, and — since every good metaphor must run to the bitter end — to ask a pantomime washer woman to save the day. Or something like that.

In part 6 we identified some serious object management issues with the existing circular_buffer design. Now we understand them, we'll learn how to fix them, and how to use a C++ allocator. This whole sordid tale will show us exactly how useful allocators are.

What is an allocator?

All STL containers take an allocator as a template parameter. The allocator is an abstraction used to allocate and free memory for items held in the container. The allocator interface is described in section 20.1.5 of the C++ standard.

An allocator is itself templated over the type of object it can allocate space for. Every STL container defaults the allocator template parameter to std::allocator, the standard C++ allocator which employs new and delete. You'll rarely specify an allocator by hand in day-to-day C++ code. The std::allocator class is described in section 20.4.1 of the standard.

The allocator interface is pretty straightforward. An allocator provides a number of typedefs, identical to those required of a container:
  • value_type
  • pointer
  • const_pointer
  • reference
  • const_reference
  • size_type
  • difference_type
It provides a number of methods, including:
size_type max_size(); // Same as a container

// Allocate memory. The second parameter is an optional "hint"
// to the allocator, the address of the object allocated prior to
// this allocation.
pointer allocate(size_type,
typename std::allocator<void>::const_pointer = 0);

// Relinquish allocated memory
void deallocate(pointer p, size_type);

// Construct an object at this (allocated) memory location
void construct(pointer p, const T &t);

// Destruct the object that was constructed in this memory location
void destroy(pointer p);
allocate and deallocate, as their names suggest, service requests for memory allocation or deallocation. More interestingly, construct and destroy are used to vivify an object in already-allocated memory (the memory must have originally come from this allocator). The default implementations employ placement new and invoke the object's destructor in place, as below:
void construct(pointer p, const T &t) { new(p) T(t); }
void destroy(pointer p) { p->~T(); }
That's the kind of C++ you'll very, very rarely write, but that is worth understanding all the same.

Adding the allocator to circular_buffer

So let's thread an allocator through our circular_buffer. The first step, naturally, is to add a new template parameter to the class. We'll default this to std::allocator, which will suit 99% of all users.
template <typename T, typename A = std::allocator<T> >
class circular_buffer
{
// ...
Since the allocator provides a host of useful typedefs related to the object it allocates, we can refine our class' definitions accordingly:
 typedef T                                        value_type;
typedef A allocator_type;
typedef circular_buffer<T,A> self_type;
typedef typename allocator_type::difference_type difference_type;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
We also extend the constructor to take an explicit allocator object (and supply a sensible default), and add get_allocator to retrieve it.
explicit circular_buffer(size_type capacity,
const allocator_type &a = allocator_type());
allocator_type get_allocator() const;
We'll need to hold a copy of the allocator alongside the other private data members. But more importantly, we must use the it to allocate the memory for m_buffer and to delete it again afterwards. The boost::scoped_array (which seemed like such a good idea at the time) goes, and we must therefore add a corresponding custom destructor, too.
public:
~circular_buffer();

private:
size_type m_capacity;
allocator_type m_allocator;
pointer m_buffer;
pointer m_front;
pointer m_back;
The updated method implementations look like this:
template <typename T, typename A>
inline
circular_buffer<T,A>::circular_buffer
(size_type capacity, const allocator_type &allocator)
: m_capacity(capacity),
m_allocator(allocator),
m_buffer(m_allocator.allocate(capacity)),
m_front(0),
m_back(m_buffer)
{
}

template <typename T, typename A>
inline
circular_buffer<T,A>::~circular_buffer()
{
clear(); // Delete all objects before deallocating the buffer
m_allocator.deallocate(m_buffer, m_capacity);
}

template <typename T, typename A>
typename circular_buffer<T,A>::allocator_type
inline
circular_buffer<T,A>::get_allocator() const
{
return m_allocator;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::max_size() const
{
// This is clearly more elegant than the previous implementation!
return m_allocator.max_size();
}

// This version of push_back must constuct and detroy objects in m_buffer
// using m_allocators methods, rather than traditional construction, copying,
// assignment.
template <typename T, typename A>
inline
bool circular_buffer<T,A>::push_back(const value_type &value)
{
// If the buffer is full, and data will fall off the back of the
// buffer - so we must destroy the stale object first.
// This is an implementation choice, we could instead use operator= on
// the value_type to replace the item. However, that would require
// value_type to provide a copy assignment operator.
if (m_front && m_front == m_back)
m_allocator.destroy(m_back);

m_allocator.construct(m_back, value);

// The rest of push_back is as it was before
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 A>
inline
void circular_buffer<T,A>::pop_front()
{
assert(m_front);

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

template <typename T, typename A>
inline
void circular_buffer<T,A>::clear()
{
if (m_front)
{
do
{
m_allocator.destroy(m_front);
m_front = wrap(m_front+1);
}
while (m_front != m_back);
}
m_front = 0;
}
That's everything that needs substantial change. Every other existing method definition gains an additional template parameter (but ignores it). Oh, and wrap() needs the ".get()"s striped from the m_buffer address lookups.

That's it.

We've fixed some nasty, subtle bugs and taken one step closer to STL perfection.

Next time: We begin to iterate. And then we iterate. And then we iterate. And then we...

No comments: