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...

1 comment:

lijialefw said...

Why was there no follow on bankruptcy then? The bailout of AIG FP went to (wow power leveling) hedge funds that bound credit swaps on Lehman failing or others betting on rating (wow power leveling) declines. AIG has drained over 100 billion from the government. Which had to go to (wow power leveling) those who bet on failures and downgrades. Many of whom (power leveling)were hedge funds. I-banks that had offsetting swaps needed the money from the AIG bailout or they would have been caught. Its an (wow powerleveling) insiders game and it takes just a little bit too much time for most people to think (wow gold) through where the AIG 100 billion bailout money went to, hedge funds and players, many of whom hire from the top ranks of DOJ, Fed, Treasury, CAOBO