493 lines
13 KiB
C++
Executable File
493 lines
13 KiB
C++
Executable File
/******************************************************************************
|
|
* $Id: $
|
|
* $Name: $
|
|
*
|
|
* Author: Pete Goodliffe
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
* Copyright 2002 Pete Goodliffe All rights reserved.
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
* Purpose: STL-style circular buffer
|
|
*
|
|
* ----------------------------------------------------------------------------
|
|
* History: See source control system log.
|
|
*
|
|
*****************************************************************************/
|
|
|
|
#ifndef CIRCULAR_BUFFER_H
|
|
#define CIRCULAR_BUFFER_H
|
|
|
|
#include <exception>
|
|
#include <iterator>
|
|
#include <memory>
|
|
|
|
/******************************************************************************
|
|
* Iterators
|
|
*****************************************************************************/
|
|
|
|
/**
|
|
* Iterator type for the circular_buffer class.
|
|
*
|
|
* This one template class provides all variants of forward/reverse
|
|
* const/non const iterators through plentiful template magic.
|
|
*
|
|
* You don't need to instantiate it directly, use the good public functions
|
|
* availble in circular_buffer.
|
|
*/
|
|
template <typename T, //circular_buffer type
|
|
//(incl const)
|
|
typename T_nonconst, //with any consts
|
|
typename elem_type = typename T::value_type> //+ const for const iter
|
|
class circular_buffer_iterator
|
|
{
|
|
public:
|
|
|
|
typedef circular_buffer_iterator<T, T_nonconst, elem_type> self_type;
|
|
|
|
typedef T cbuf_type;
|
|
typedef std::random_access_iterator_tag iterator_category;
|
|
typedef typename cbuf_type::value_type value_type;
|
|
typedef typename cbuf_type::size_type size_type;
|
|
typedef typename cbuf_type::pointer pointer;
|
|
typedef typename cbuf_type::const_pointer const_pointer;
|
|
typedef typename cbuf_type::reference reference;
|
|
typedef typename cbuf_type::const_reference const_reference;
|
|
typedef typename cbuf_type::difference_type difference_type;
|
|
|
|
circular_buffer_iterator(cbuf_type *b, size_type p)
|
|
: buf_(b), pos_(p) {}
|
|
|
|
// Converting a non-const iterator to a const iterator
|
|
circular_buffer_iterator
|
|
(const circular_buffer_iterator<T_nonconst, T_nonconst,
|
|
typename T_nonconst::value_type>
|
|
&other)
|
|
: buf_(other.buf_), pos_(other.pos_) {}
|
|
friend class circular_buffer_iterator<const T, T, const elem_type>;
|
|
|
|
// Use compiler generated copy ctor, copy assignment operator and dtor
|
|
|
|
elem_type &operator*() { return (*buf_)[pos_]; }
|
|
elem_type *operator->() { return &(operator*()); }
|
|
|
|
self_type &operator++()
|
|
{
|
|
pos_ += 1;
|
|
return *this;
|
|
}
|
|
self_type operator++(int)
|
|
{
|
|
self_type tmp(*this);
|
|
++(*this);
|
|
return tmp;
|
|
}
|
|
|
|
self_type &operator--()
|
|
{
|
|
pos_ -= 1;
|
|
return *this;
|
|
}
|
|
self_type operator--(int)
|
|
{
|
|
self_type tmp(*this);
|
|
--(*this);
|
|
return tmp;
|
|
}
|
|
|
|
self_type operator+(difference_type n) const
|
|
{
|
|
self_type tmp(*this);
|
|
tmp.pos_ += n;
|
|
return tmp;
|
|
}
|
|
self_type &operator+=(difference_type n)
|
|
{
|
|
pos_ += n;
|
|
return *this;
|
|
}
|
|
|
|
self_type operator-(difference_type n) const
|
|
{
|
|
self_type tmp(*this);
|
|
tmp.pos_ -= n;
|
|
return tmp;
|
|
}
|
|
self_type &operator-=(difference_type n)
|
|
{
|
|
pos_ -= n;
|
|
return *this;
|
|
}
|
|
|
|
difference_type operator-(const self_type &c) const
|
|
{
|
|
return pos_ - c.pos_;
|
|
}
|
|
|
|
bool operator==(const self_type &other) const
|
|
{
|
|
return pos_ == other.pos_ && buf_ == other.buf_;
|
|
}
|
|
bool operator!=(const self_type &other) const
|
|
{
|
|
return pos_ != other.pos_ && buf_ == other.buf_;
|
|
}
|
|
bool operator>(const self_type &other) const
|
|
{
|
|
return pos_ > other.pos_;
|
|
}
|
|
bool operator>=(const self_type &other) const
|
|
{
|
|
return pos_ >= other.pos_;
|
|
}
|
|
bool operator<(const self_type &other) const
|
|
{
|
|
return pos_ < other.pos_;
|
|
}
|
|
bool operator<=(const self_type &other) const
|
|
{
|
|
return pos_ <= other.pos_;
|
|
}
|
|
|
|
private:
|
|
|
|
cbuf_type *buf_;
|
|
size_type pos_;
|
|
};
|
|
|
|
template <typename circular_buffer_iterator_t>
|
|
circular_buffer_iterator_t operator+
|
|
(const typename circular_buffer_iterator_t::difference_type &a,
|
|
const circular_buffer_iterator_t &b)
|
|
{
|
|
return circular_buffer_iterator_t(a) + b;
|
|
}
|
|
|
|
template <typename circular_buffer_iterator_t>
|
|
circular_buffer_iterator_t operator-
|
|
(const typename circular_buffer_iterator_t::difference_type &a,
|
|
const circular_buffer_iterator_t &b)
|
|
{
|
|
return circular_buffer_iterator_t(a) - b;
|
|
}
|
|
|
|
|
|
/******************************************************************************
|
|
* circular_buffer
|
|
*****************************************************************************/
|
|
|
|
/**
|
|
* This class provides a circular buffer in the STL style.
|
|
*
|
|
* You can add data to the end using the @ref push_back function, read data
|
|
* using @ref front() and remove data using @ref pop_front().
|
|
*
|
|
* The class also provides random access through the @ref operator[]()
|
|
* function and its random access iterator. Subscripting the array with
|
|
* an invalid (out of range) index number leads to undefined results, both
|
|
* for reading and writing.
|
|
*
|
|
* This class template accepts three template parameters:
|
|
* <li> T The type of object contained
|
|
* <li> always_accept_data_when_full Determines the behaviour of
|
|
* @ref push_back when the buffer is full.
|
|
* Set to true new data is always added, the
|
|
* old "end" data is thrown away.
|
|
* Set to false, the new data is not added.
|
|
* No error is returned neither is an
|
|
* exception raised.
|
|
* <li> Alloc Allocator type to use (in line with other
|
|
* STL containers).
|
|
*
|
|
* @short STL style circule buffer
|
|
* @author Pete Goodliffe
|
|
* @version 1.00
|
|
*/
|
|
template <typename T,
|
|
bool always_accept_data_when_full = true,
|
|
typename Alloc = std::allocator<T> >
|
|
class circular_buffer
|
|
{
|
|
public:
|
|
|
|
enum
|
|
{
|
|
version_major = 1,
|
|
version_minor = 0
|
|
};
|
|
|
|
// Typedefs
|
|
typedef circular_buffer<T, always_accept_data_when_full, Alloc>
|
|
self_type;
|
|
|
|
typedef Alloc allocator_type;
|
|
|
|
typedef typename Alloc::value_type value_type;
|
|
typedef typename Alloc::pointer pointer;
|
|
typedef typename Alloc::const_pointer const_pointer;
|
|
typedef typename Alloc::reference reference;
|
|
typedef typename Alloc::const_reference const_reference;
|
|
|
|
typedef typename Alloc::size_type size_type;
|
|
typedef typename Alloc::difference_type difference_type;
|
|
|
|
typedef circular_buffer_iterator
|
|
<self_type, self_type>
|
|
iterator;
|
|
typedef circular_buffer_iterator
|
|
<const self_type, self_type, const value_type>
|
|
const_iterator;
|
|
typedef std::reverse_iterator<iterator> reverse_iterator;
|
|
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
|
|
|
|
// Lifetime
|
|
enum { default_capacity = 100 };
|
|
explicit circular_buffer(size_type capacity = default_capacity)
|
|
: array_(alloc_.allocate(capacity)), array_size_(capacity),
|
|
head_(1), tail_(0), contents_size_(0)
|
|
{
|
|
}
|
|
circular_buffer(const circular_buffer &other)
|
|
: array_(alloc_.allocate(other.array_size_)),
|
|
array_size_(other.array_size_),
|
|
head_(other.head_), tail_(other.tail_),
|
|
contents_size_(other.contents_size_)
|
|
{
|
|
try
|
|
{
|
|
assign_into(other.begin(), other.end());
|
|
}
|
|
catch (...)
|
|
{
|
|
destroy_all_elements();
|
|
alloc_.deallocate(array_, array_size_);
|
|
throw;
|
|
}
|
|
}
|
|
template <class InputIterator>
|
|
circular_buffer(InputIterator from, InputIterator to)
|
|
: array_(alloc_.allocate(1)), array_size_(1),
|
|
head_(1), tail_(0), contents_size_(0)
|
|
{
|
|
circular_buffer tmp;
|
|
tmp.assign_into_reserving(from, to);
|
|
swap(tmp);
|
|
}
|
|
~circular_buffer()
|
|
{
|
|
destroy_all_elements();
|
|
alloc_.deallocate(array_, array_size_);
|
|
}
|
|
circular_buffer &operator=(const self_type &other)
|
|
{
|
|
circular_buffer tmp(other);
|
|
swap(tmp);
|
|
return *this;
|
|
}
|
|
void swap(circular_buffer &other)
|
|
{
|
|
std::swap(array_, other.array_);
|
|
std::swap(array_size_, other.array_size_);
|
|
std::swap(head_, other.head_);
|
|
std::swap(tail_, other.tail_);
|
|
std::swap(contents_size_, other.contents_size_);
|
|
}
|
|
allocator_type get_allocator() const { return alloc_; }
|
|
|
|
// Iterators
|
|
iterator begin() { return iterator(this, 0); }
|
|
iterator end() { return iterator(this, size()); }
|
|
|
|
const_iterator begin() const { return const_iterator(this, 0); }
|
|
const_iterator end() const { return const_iterator(this, size()); }
|
|
|
|
reverse_iterator rbegin() { return reverse_iterator(end()); }
|
|
reverse_iterator rend() { return reverse_iterator(begin()); }
|
|
|
|
const_reverse_iterator rbegin() const
|
|
{
|
|
return const_reverse_iterator(end());
|
|
}
|
|
const_reverse_iterator rend() const
|
|
{
|
|
return const_reverse_iterator(begin());
|
|
}
|
|
|
|
// Size
|
|
size_type size() const { return contents_size_; }
|
|
size_type capacity() const { return array_size_; }
|
|
bool empty() const { return !contents_size_; }
|
|
size_type max_size() const
|
|
{
|
|
return alloc_.max_size();
|
|
}
|
|
void reserve(size_type new_size)
|
|
{
|
|
if (capacity() < new_size)
|
|
{
|
|
circular_buffer tmp(new_size);
|
|
tmp.assign_into(begin(), end());
|
|
swap(tmp);
|
|
}
|
|
}
|
|
|
|
// Accessing
|
|
reference front() { return array_[head_]; }
|
|
reference back() { return array_[tail_]; }
|
|
const_reference front() const { return array_[head_]; }
|
|
const_reference back() const { return array_[tail_]; }
|
|
|
|
void push_back(const value_type &item)
|
|
{
|
|
size_type next = next_tail();
|
|
if (contents_size_ == array_size_)
|
|
{
|
|
if (always_accept_data_when_full)
|
|
{
|
|
array_[next] = item;
|
|
increment_head();
|
|
}
|
|
}
|
|
else
|
|
{
|
|
alloc_.construct(array_ + next, item);
|
|
}
|
|
increment_tail();
|
|
}
|
|
void pop_front()
|
|
{
|
|
size_type destroy_pos = head_;
|
|
increment_head();
|
|
alloc_.destroy(array_ + destroy_pos);
|
|
}
|
|
void clear()
|
|
{
|
|
for (size_type n = 0; n < contents_size_; ++n)
|
|
{
|
|
alloc_.destroy(array_ + index_to_subscript(n));
|
|
}
|
|
head_ = 1;
|
|
tail_ = contents_size_ = 0;
|
|
}
|
|
|
|
reference operator[](size_type n) { return at_unchecked(n); }
|
|
const_reference operator[](size_type n) const { return at_unchecked(n); }
|
|
|
|
reference at(size_type n) { return at_checked(n); }
|
|
const_reference at(size_type n) const { return at_checked(n); }
|
|
|
|
private:
|
|
|
|
reference at_unchecked(size_type index) const
|
|
{
|
|
return array_[index_to_subscript(index)];
|
|
}
|
|
|
|
reference at_checked(size_type index) const
|
|
{
|
|
if (size >= contents_size_)
|
|
{
|
|
throw std::out_of_range();
|
|
}
|
|
return at_unchecked(index);
|
|
}
|
|
|
|
// Rounds an unbounded to an index into array_
|
|
size_type normalise(size_type n) const { return n % array_size_; }
|
|
|
|
// Converts external index to an array subscript
|
|
size_type index_to_subscript(size_type index) const
|
|
{
|
|
return normalise(index + head_);
|
|
}
|
|
|
|
void increment_tail()
|
|
{
|
|
++contents_size_;
|
|
tail_ = next_tail();
|
|
}
|
|
|
|
size_type next_tail()
|
|
{
|
|
return (tail_ + 1 == array_size_) ? 0 : tail_ + 1;
|
|
}
|
|
|
|
void increment_head()
|
|
{
|
|
// precondition: !empty()
|
|
++head_;
|
|
--contents_size_;
|
|
if (head_ == array_size_) head_ = 0;
|
|
}
|
|
|
|
template <typename f_iter>
|
|
void assign_into(f_iter from, f_iter to)
|
|
{
|
|
if (contents_size_) clear();
|
|
while (from != to)
|
|
{
|
|
push_back(*from);
|
|
++from;
|
|
}
|
|
}
|
|
|
|
template <typename f_iter>
|
|
void assign_into_reserving(f_iter from, f_iter to)
|
|
{
|
|
if (contents_size_) clear();
|
|
while (from != to)
|
|
{
|
|
if (contents_size_ == array_size_)
|
|
{
|
|
reserve(static_cast<size_type>(array_size_ * 1.5));
|
|
}
|
|
push_back(*from);
|
|
++from;
|
|
}
|
|
}
|
|
|
|
void destroy_all_elements()
|
|
{
|
|
for (size_type n = 0; n < contents_size_; ++n)
|
|
{
|
|
alloc_.destroy(array_ + index_to_subscript(n));
|
|
}
|
|
}
|
|
|
|
allocator_type alloc_;
|
|
value_type *array_;
|
|
size_type array_size_;
|
|
size_type head_;
|
|
size_type tail_;
|
|
size_type contents_size_;
|
|
};
|
|
|
|
template <typename T,
|
|
bool consume_policy,
|
|
typename Alloc>
|
|
bool operator==(const circular_buffer<T, consume_policy, Alloc> &a,
|
|
const circular_buffer<T, consume_policy, Alloc> &b)
|
|
{
|
|
return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
|
|
}
|
|
|
|
template <typename T,
|
|
bool consume_policy,
|
|
typename Alloc>
|
|
bool operator!=(const circular_buffer<T, consume_policy, Alloc> &a,
|
|
const circular_buffer<T, consume_policy, Alloc> &b)
|
|
{
|
|
return a.size() != b.size() || !std::equal(a.begin(), a.end(), b.begin());
|
|
}
|
|
|
|
template <typename T,
|
|
bool consume_policy,
|
|
typename Alloc>
|
|
bool operator<(const circular_buffer<T, consume_policy, Alloc> &a,
|
|
const circular_buffer<T, consume_policy, Alloc> &b)
|
|
{
|
|
return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
|
|
}
|
|
|
|
#endif
|