In this part, we'll get
back to some basics. In a brief intermission from iterators, we'll add the complement to
front(),
back(), which returns a reference to the last item in the buffer. We provide a
const and a non-
const version:
// In declaration
reference back();
const_reference back() const;
template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::back()
{
assert(m_front);
return *wrap(m_back-1);
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::back() const
{
assert(m_front);
return *wrap(m_back-1);
}
To make this work, we need to make
wrap cope with pointers that stray below
m_buffer:
value_type *wrap(value_type *ptr) const
{
assert(ptr < m_buffer + m_capacity*2);
assert(ptr > m_buffer - m_capacity);
if (ptr >= m_buffer+m_capacity)
return ptr-m_capacity;
else if (ptr < m_buffer)
return ptr+m_capacity;
else
return ptr;
}
As ever, I'll add some tests that exercise the code, and reproduce the entire thing below for your cut-n-paste pleasure...
#include <algorithm>
#include <cassert>
#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;
class iterator;
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;
reference back();
const_reference back() const;
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference at(size_type n);
const_reference at(size_type n) const;
iterator begin();
iterator end();
bool push_back(const value_type &);
void pop_front();
void clear();
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);
assert(ptr > m_buffer - m_capacity);
if (ptr >= m_buffer+m_capacity)
return ptr-m_capacity;
else if (ptr < m_buffer)
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
typename circular_buffer<T,A>::reference circular_buffer<T,A>::back()
{
assert(m_front);
return *wrap(m_back-1);
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::back() const
{
assert(m_front);
return *wrap(m_back-1);
}
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];
}
template <typename T, typename A>
class circular_buffer<T,A>::iterator
: public std::iterator<std::random_access_iterator_tag,
value_type,
size_type,
pointer,
reference>
{
public:
typedef circular_buffer<T> parent_type;
typedef typename parent_type::iterator self_type;
iterator(parent_type &parent, size_type index)
: parent(parent), index(index) {}
self_type &operator++()
{
++index;
return *this;
}
self_type operator++(int) // postincrement
{
self_type old(*this);
operator++();
return old;
}
self_type &operator--()
{
--index;
return *this;
}
self_type operator--(int) // postdecrement
{
self_type old(*this);
operator--();
return old;
}
reference operator*() { return parent[index]; }
pointer operator->() { return &(parent[index]); }
bool operator==(const self_type &other) const
{ return &parent == &other.parent && index == other.index; }
bool operator!=(const self_type &other) const
{ return !(other == *this); }
private:
parent_type &parent;
size_type index;
};
template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::begin()
{
return iterator(*this, 0);
}
template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::end()
{
return iterator(*this, size());
}
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.back() == 1);
assert(cb.push_back(2));
assert(cb.size() == 2);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 1);
assert(cb.back() == 2);
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.back() == 5);
assert(!cb.push_back(6));
assert(cb.size() == 5);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 2);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 4);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 3);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 3);
assert(cb.front() == 4);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 2);
assert(cb.front() == 5);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 1);
assert(cb.front() == 6);
assert(cb.back() == 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.back() == 7);
assert(cb.push_back(8));
assert(cb.push_back(9));
assert(cb.size() == 3);
assert(!cb.empty());
assert(cb.front() == 7);
assert(cb.back() == 9);
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;
}
In this part, we'll get back to some basics. In a brief intermission from iterators, we'll add the complement to front(), back(), which returns a reference to the last item in the buffer. We provide a const and a non-const version:
Various different shades of green on a green background... interesting colour scheme you have :)
ReplyDeleteOooh, that implementation of wrap() is a bit worrying. I'm pretty sure that C++ doesn't guarantee that that sort of arithmetic will work with pointers outside the actual allocated object. For the ptr<m_buffer case to fail you probably have to be on some sort of segmented or Win16 architecture; but the ptr>=m_buffer+m_capacity one can fail even on a sane 32-bit architecture if m_buffer ends up near the very top of memory. (C++ guarantees this to work for m_buffer+m_capacity, but not for anything beyond there.)
ReplyDeleteTo implement wrap() without invoking undefined behaviour, you probably need to implement it as something like
value_type *wrap(value_type *ptr, difference_type offset)
{
size_type pos = ptr - m_buffer;
assert(pos < m_capacity);
if (offset >= 0)
{
assert(offset<m_capacity);
pos += offset;
}
else
{
// Care with promotion to unsigned!
assert(-offset<m_capacity);
pos += (m_capacity+offset);
}
if (pos > m_capacity)
pos -= m_capacity;
return m_buffer + pos;
}
and call it with wrap(m_back, -1) or whatever, but of course that's rather more expensive, as calculating pos requires a division. You could avoid the division by working in char*s, but at the expense of much uglier code...
Hi Peter. Yes, you have a very valid point.
ReplyDeleteI think a nicer solution here would be something like:
pointer increment(pointer ptr, size_type by) const
{
assert(ptr >= m_buffer);
assert(ptr < m_buffer+m_capacity);
const size_type index = ptr-m_buffer;
assert(index < m_capacity);
if (index+by >= m_capacity)
return ptr+by-m_capacity;
else
return ptr+by;
}
pointer decrement(pointer ptr, size_type by) const
{
assert(ptr >= m_buffer);
assert(ptr < m_buffer+m_capacity);
const size_type index = ptr-m_buffer;
assert(index < m_capacity);
if (index >= by)
return ptr-by;
else
return ptr+(m_capacity-by);
}
It still has the pointer arithmetic issue you mention, but it reads a little better, and avoids some unnecessary if statements.
Can you please explain why I get an error when trying to use an iterator?
ReplyDeleteI am trying to retrieve the entries from the circular buffer from the oldest entry to the youngest.
In your test file, I tried to add the following (using Visual Studio 2010) just to test iterators:
circular_buffer<int>::iterator iter;
int n(0);
for (iter = cb.begin(); iter != cb.end(); iter++) {
n++;
}
On the definition of 'iter', I get the following error:
error C2512: 'circular_buffer::iterator' : no appropriate default constructor available
In the "for" statement, "iter = cb.begin()", I get the error:
error C2582: 'operator =' function is unavailable in 'circular_buffer::iterator'
Many thanks