Wednesday, 26 November 2008

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

The circular_buffer is looking in pretty good shape now. We've squashed bugs and introduced an allocator. And, to be fair, we could stop here and have a perfectly usable class.

However, let's add some more methods to the container to learn a bit more about writing STL-like containers. The story can't end here after all, there's been no dramatic climax.

operator[] and at

These two methods aren't strictly required of a circular buffer. Section 23.1.1 of the standard claims these operations are only provided when they take constant time. We can achieve constant time indexing with our class, so let's write them.
    // In declaration
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference at(size_type n);
const_reference at(size_type n) const;
at() is an index operator that performs bounds checking, throwing a std::out_of_range error if the index is invalid. operator[] itself need perform no bounds checking. Given our wrap() method, the implementations are simple:
template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::operator[]
(size_type n)
{
return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::operator[]
(size_type n) const
{
return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::at(size_type n)
{
if (n >= size()) throw std::out_of_range("Parameter out of range");
return (*this)[n];
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::at
(size_type n) const
{
if (n >= size()) throw std::out_of_range("Parameter out of range");
return (*this)[n];
}
We implement at() in terms of operator[]. To use std::out_of_range, you'll need to include <stdexcept>

We should write some more tests for test these new methods. In showing you this, I'll reproduce the entire class so far.
#include <algorithm>
#include <stdexcept>

template <typename T, typename A = std::allocator<T> >
class circular_buffer
{
public:
typedef T value_type;
typedef A allocator_type;
typedef typename allocator_type::size_type size_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;

explicit circular_buffer(size_type capacity,
const allocator_type &a = allocator_type());
~circular_buffer();
allocator_type get_allocator() const;

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();
void clear();

reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference at(size_type n);
const_reference at(size_type n) const;

private:
size_type m_capacity;
allocator_type m_allocator;
pointer m_buffer;
pointer m_front;
pointer 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) const
{
assert(ptr < m_buffer + m_capacity*2);
if (ptr >= m_buffer+m_capacity)
return ptr-m_capacity;
else
return ptr;
}
};

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)
{
assert(capacity > 0);
}

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

template <typename T, typename A>
inline
typename circular_buffer<T,A>::allocator_type
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>::capacity() const
{
return m_capacity;
}

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

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

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::max_size() const
{
return m_allocator.max_size();
}

template <typename T, typename A>
inline
bool circular_buffer<T,A>::push_back(const value_type &value)
{
if (m_front && m_front == m_back)
m_allocator.destroy(m_back);

m_allocator.construct(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 A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::front()
{
assert(m_front);
return *m_front;
}

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

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

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::operator[]
(size_type n)
{
return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::operator[]
(size_type n) const
{
return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::at(size_type n)
{
if (n >= size()) throw std::out_of_range("Parameter out of range");
return (*this)[n];
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::at
(size_type n) const
{
if (n >= size()) throw std::out_of_range("Parameter out of range");
return (*this)[n];
}

namespace tests
{
void pushing_and_popping()
{
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);

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

void indexing()
{
circular_buffer<int> cb(5);

// A helper - like asssert, but checks for an exception
#define assert_throws(a,b) \
{\
try { a; throw "Failed to throw"; } \
catch (const b&) { /*OK*/ } \
catch (...) { throw "Threw wrong thing"; } \
}

// We loop round this test several times so our data wraps around the
// internal m_buffer array a few times.
for (size_t n = 0; n < 10; ++n)
{
assert(cb.empty());

const circular_buffer<int> &const_cb(cb);

assert_throws(cb.at(0), std::out_of_range);
assert_throws(cb.at(1), std::out_of_range);
assert_throws(const_cb.at(0), std::out_of_range);
assert_throws(const_cb.at(0), std::out_of_range);
// we could check that operator[] explodes, but there's little point!

assert(cb.push_back(0));
assert(cb.push_back(1));
assert(cb.push_back(2));
assert(cb.at(0) == 0); assert(const_cb.at(0) == 0);
assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
assert(cb[0] == 0); assert(const_cb[0] == 0);
assert(cb[1] == 1); assert(const_cb[1] == 1);
assert(cb[2] == 2); assert(const_cb[2] == 2);

assert(cb.front() == 0);
cb[0] = 3;
assert(cb.front() == 3);
assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
assert(cb[0] == 3); assert(const_cb[0] == 3);
assert(cb[1] == 1); assert(const_cb[1] == 1);
assert(cb[2] == 2); assert(const_cb[2] == 2);

cb[1] = 4;
assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
assert(cb.at(1) == 4); assert(const_cb.at(1) == 4);
assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
assert(cb[0] == 3); assert(const_cb[0] == 3);
assert(cb[1] == 4); assert(const_cb[1] == 4);
assert(cb[2] == 2); assert(const_cb[2] == 2);

cb.pop_front();
assert(cb[0] == 4); assert(const_cb[0] == 4);
assert(cb[1] == 2); assert(const_cb[1] == 2);

cb.pop_front();
assert(cb[0] == 2); assert(const_cb[0] == 2);

cb.pop_front();
}

}
}

int main()
{
tests::pushing_and_popping();
tests::indexing();
return 0;
}


6 comments:

Ben said...

Trying to follow along in VC9, but I get a compile error on the implementation line of const_reference operator[] - the compiler can't convert "*wrap()" (a reference) to a const_reference. Adding a const_pointer version of wrap() solved this: paste

Pete Goodliffe said...

Hiya.

Thanks for the comment! Glad you're following along :-)

I'll admit that although I have run the "final thing" through VS and gcc, I've only run the interim versions that are coming out in this miniseries through gcc.

So, at your prompting, I've just run the code at the end of Part 9 through VS 2008, and it compiles fine.

Ish.

I had to add #include <cassert>, but that was it.

Sorry, I'm no VS expert... VC9 is Visual Studio 2008, isn't it? What settings did you enable to get it to complain like that?

I understand the reason for the problem you report, though. Thanks.

Ben said...

Interesting; I included <assert.h>, I wonder if there's a difference.

Yes, VC9 is Studio 2008. I'm using a standard full install (with SP1), with default project settings, generated from the Win32 Console App wizard. I'd send you the project, but it's at work, and this being the weekend it is...

Pete Goodliffe said...

There's little practical difference between <cassert> and <assert.h>. The "c" family of header files define the same functions and constants as their non-"c" counterparts, put the names in the std:: namespace. Since assert is a macro (and doesn't honour namespacing), it doesn't make any practical difference.

I created my VS2008 project in exactly the same way as you. Mine doesn't fail. So, can I check - did your original (failing) version of wrap have a const qualification? The code fails to compile as you describe in that case.

Ben said...

That must be it. PEBKAC.

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