// Helper classes and functions for the circular buffer. | |
// Copyright (c) 2003-2008 Jan Gaspar | |
// Use, modification, and distribution is subject to the Boost Software | |
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
#if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP) | |
#define BOOST_CIRCULAR_BUFFER_DETAILS_HPP | |
#if defined(_MSC_VER) && _MSC_VER >= 1200 | |
#pragma once | |
#endif | |
#include <boost/iterator.hpp> | |
#include <boost/throw_exception.hpp> | |
#include <boost/detail/no_exceptions_support.hpp> | |
#include <iterator> | |
namespace boost { | |
namespace cb_details { | |
template <class Traits> struct nonconst_traits; | |
template<class ForwardIterator, class Diff, class T, class Alloc> | |
void uninitialized_fill_n_with_alloc( | |
ForwardIterator first, Diff n, const T& item, Alloc& alloc); | |
template<class InputIterator, class ForwardIterator, class Alloc> | |
ForwardIterator uninitialized_copy_with_alloc( | |
InputIterator first, InputIterator last, ForwardIterator dest, Alloc& alloc); | |
/*! | |
\struct const_traits | |
\brief Defines the data types for a const iterator. | |
*/ | |
template <class Traits> | |
struct const_traits { | |
// Basic types | |
typedef typename Traits::value_type value_type; | |
typedef typename Traits::const_pointer pointer; | |
typedef typename Traits::const_reference reference; | |
typedef typename Traits::size_type size_type; | |
typedef typename Traits::difference_type difference_type; | |
// Non-const traits | |
typedef nonconst_traits<Traits> nonconst_self; | |
}; | |
/*! | |
\struct nonconst_traits | |
\brief Defines the data types for a non-const iterator. | |
*/ | |
template <class Traits> | |
struct nonconst_traits { | |
// Basic types | |
typedef typename Traits::value_type value_type; | |
typedef typename Traits::pointer pointer; | |
typedef typename Traits::reference reference; | |
typedef typename Traits::size_type size_type; | |
typedef typename Traits::difference_type difference_type; | |
// Non-const traits | |
typedef nonconst_traits<Traits> nonconst_self; | |
}; | |
/*! | |
\struct iterator_wrapper | |
\brief Helper iterator dereference wrapper. | |
*/ | |
template <class Iterator> | |
struct iterator_wrapper { | |
mutable Iterator m_it; | |
explicit iterator_wrapper(Iterator it) : m_it(it) {} | |
Iterator operator () () const { return m_it++; } | |
private: | |
iterator_wrapper<Iterator>& operator = (const iterator_wrapper<Iterator>&); // do not generate | |
}; | |
/*! | |
\struct item_wrapper | |
\brief Helper item dereference wrapper. | |
*/ | |
template <class Pointer, class Value> | |
struct item_wrapper { | |
Value m_item; | |
explicit item_wrapper(Value item) : m_item(item) {} | |
Pointer operator () () const { return &m_item; } | |
private: | |
item_wrapper<Pointer, Value>& operator = (const item_wrapper<Pointer, Value>&); // do not generate | |
}; | |
/*! | |
\struct assign_n | |
\brief Helper functor for assigning n items. | |
*/ | |
template <class Value, class Alloc> | |
struct assign_n { | |
typedef typename Alloc::size_type size_type; | |
size_type m_n; | |
Value m_item; | |
Alloc& m_alloc; | |
assign_n(size_type n, Value item, Alloc& alloc) : m_n(n), m_item(item), m_alloc(alloc) {} | |
template <class Pointer> | |
void operator () (Pointer p) const { | |
uninitialized_fill_n_with_alloc(p, m_n, m_item, m_alloc); | |
} | |
private: | |
assign_n<Value, Alloc>& operator = (const assign_n<Value, Alloc>&); // do not generate | |
}; | |
/*! | |
\struct assign_range | |
\brief Helper functor for assigning range of items. | |
*/ | |
template <class Iterator, class Alloc> | |
struct assign_range { | |
const Iterator& m_first; | |
const Iterator& m_last; | |
Alloc& m_alloc; | |
assign_range(const Iterator& first, const Iterator& last, Alloc& alloc) | |
: m_first(first), m_last(last), m_alloc(alloc) {} | |
template <class Pointer> | |
void operator () (Pointer p) const { | |
uninitialized_copy_with_alloc(m_first, m_last, p, m_alloc); | |
} | |
private: | |
assign_range<Iterator, Alloc>& operator = (const assign_range<Iterator, Alloc>&); // do not generate | |
}; | |
/*! | |
\class capacity_control | |
\brief Capacity controller of the space optimized circular buffer. | |
*/ | |
template <class Size> | |
class capacity_control { | |
//! The capacity of the space optimized circular buffer. | |
Size m_capacity; | |
//! The lowest guaranteed capacity of the adapted circular buffer. | |
Size m_min_capacity; | |
public: | |
//! Constructor. | |
capacity_control(Size buffer_capacity, Size min_buffer_capacity = 0) | |
: m_capacity(buffer_capacity), m_min_capacity(min_buffer_capacity) { | |
BOOST_CB_ASSERT(buffer_capacity >= min_buffer_capacity); // check for capacity lower than min_capacity | |
} | |
// Default copy constructor. | |
// Default assign operator. | |
//! Get the capacity of the space optimized circular buffer. | |
Size capacity() const { return m_capacity; } | |
//! Get the minimal capacity of the space optimized circular buffer. | |
Size min_capacity() const { return m_min_capacity; } | |
//! Size operator - returns the capacity of the space optimized circular buffer. | |
operator Size() const { return m_capacity; } | |
}; | |
/*! | |
\struct iterator | |
\brief Random access iterator for the circular buffer. | |
\param Buff The type of the underlying circular buffer. | |
\param Traits Basic iterator types. | |
\note This iterator is not circular. It was designed | |
for iterating from begin() to end() of the circular buffer. | |
*/ | |
template <class Buff, class Traits> | |
struct iterator : | |
public boost::iterator< | |
std::random_access_iterator_tag, | |
typename Traits::value_type, | |
typename Traits::difference_type, | |
typename Traits::pointer, | |
typename Traits::reference> | |
#if BOOST_CB_ENABLE_DEBUG | |
, public debug_iterator_base | |
#endif // #if BOOST_CB_ENABLE_DEBUG | |
{ | |
// Helper types | |
//! Base iterator. | |
typedef boost::iterator< | |
std::random_access_iterator_tag, | |
typename Traits::value_type, | |
typename Traits::difference_type, | |
typename Traits::pointer, | |
typename Traits::reference> base_iterator; | |
//! Non-const iterator. | |
typedef iterator<Buff, typename Traits::nonconst_self> nonconst_self; | |
// Basic types | |
//! The type of the elements stored in the circular buffer. | |
typedef typename base_iterator::value_type value_type; | |
//! Pointer to the element. | |
typedef typename base_iterator::pointer pointer; | |
//! Reference to the element. | |
typedef typename base_iterator::reference reference; | |
//! Size type. | |
typedef typename Traits::size_type size_type; | |
//! Difference type. | |
typedef typename base_iterator::difference_type difference_type; | |
// Member variables | |
//! The circular buffer where the iterator points to. | |
const Buff* m_buff; | |
//! An internal iterator. | |
pointer m_it; | |
// Construction & assignment | |
// Default copy constructor. | |
//! Default constructor. | |
iterator() : m_buff(0), m_it(0) {} | |
#if BOOST_CB_ENABLE_DEBUG | |
//! Copy constructor (used for converting from a non-const to a const iterator). | |
iterator(const nonconst_self& it) : debug_iterator_base(it), m_buff(it.m_buff), m_it(it.m_it) {} | |
//! Internal constructor. | |
/*! | |
\note This constructor is not intended to be used directly by the user. | |
*/ | |
iterator(const Buff* cb, const pointer p) : debug_iterator_base(cb), m_buff(cb), m_it(p) {} | |
#else | |
iterator(const nonconst_self& it) : m_buff(it.m_buff), m_it(it.m_it) {} | |
iterator(const Buff* cb, const pointer p) : m_buff(cb), m_it(p) {} | |
#endif // #if BOOST_CB_ENABLE_DEBUG | |
//! Assign operator. | |
iterator& operator = (const iterator& it) { | |
if (this == &it) | |
return *this; | |
#if BOOST_CB_ENABLE_DEBUG | |
debug_iterator_base::operator =(it); | |
#endif // #if BOOST_CB_ENABLE_DEBUG | |
m_buff = it.m_buff; | |
m_it = it.m_it; | |
return *this; | |
} | |
// Random access iterator methods | |
//! Dereferencing operator. | |
reference operator * () const { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
BOOST_CB_ASSERT(m_it != 0); // check for iterator pointing to end() | |
return *m_it; | |
} | |
//! Dereferencing operator. | |
pointer operator -> () const { return &(operator*()); } | |
//! Difference operator. | |
template <class Traits0> | |
difference_type operator - (const iterator<Buff, Traits0>& it) const { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
return linearize_pointer(*this) - linearize_pointer(it); | |
} | |
//! Increment operator (prefix). | |
iterator& operator ++ () { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
BOOST_CB_ASSERT(m_it != 0); // check for iterator pointing to end() | |
m_buff->increment(m_it); | |
if (m_it == m_buff->m_last) | |
m_it = 0; | |
return *this; | |
} | |
//! Increment operator (postfix). | |
iterator operator ++ (int) { | |
iterator<Buff, Traits> tmp = *this; | |
++*this; | |
return tmp; | |
} | |
//! Decrement operator (prefix). | |
iterator& operator -- () { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
BOOST_CB_ASSERT(m_it != m_buff->m_first); // check for iterator pointing to begin() | |
if (m_it == 0) | |
m_it = m_buff->m_last; | |
m_buff->decrement(m_it); | |
return *this; | |
} | |
//! Decrement operator (postfix). | |
iterator operator -- (int) { | |
iterator<Buff, Traits> tmp = *this; | |
--*this; | |
return tmp; | |
} | |
//! Iterator addition. | |
iterator& operator += (difference_type n) { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
if (n > 0) { | |
BOOST_CB_ASSERT(m_buff->end() - *this >= n); // check for too large n | |
m_it = m_buff->add(m_it, n); | |
if (m_it == m_buff->m_last) | |
m_it = 0; | |
} else if (n < 0) { | |
*this -= -n; | |
} | |
return *this; | |
} | |
//! Iterator addition. | |
iterator operator + (difference_type n) const { return iterator<Buff, Traits>(*this) += n; } | |
//! Iterator subtraction. | |
iterator& operator -= (difference_type n) { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
if (n > 0) { | |
BOOST_CB_ASSERT(*this - m_buff->begin() >= n); // check for too large n | |
m_it = m_buff->sub(m_it == 0 ? m_buff->m_last : m_it, n); | |
} else if (n < 0) { | |
*this += -n; | |
} | |
return *this; | |
} | |
//! Iterator subtraction. | |
iterator operator - (difference_type n) const { return iterator<Buff, Traits>(*this) -= n; } | |
//! Element access operator. | |
reference operator [] (difference_type n) const { return *(*this + n); } | |
// Equality & comparison | |
//! Equality. | |
template <class Traits0> | |
bool operator == (const iterator<Buff, Traits0>& it) const { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
return m_it == it.m_it; | |
} | |
//! Inequality. | |
template <class Traits0> | |
bool operator != (const iterator<Buff, Traits0>& it) const { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
return m_it != it.m_it; | |
} | |
//! Less. | |
template <class Traits0> | |
bool operator < (const iterator<Buff, Traits0>& it) const { | |
BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator | |
return linearize_pointer(*this) < linearize_pointer(it); | |
} | |
//! Greater. | |
template <class Traits0> | |
bool operator > (const iterator<Buff, Traits0>& it) const { return it < *this; } | |
//! Less or equal. | |
template <class Traits0> | |
bool operator <= (const iterator<Buff, Traits0>& it) const { return !(it < *this); } | |
//! Greater or equal. | |
template <class Traits0> | |
bool operator >= (const iterator<Buff, Traits0>& it) const { return !(*this < it); } | |
// Helpers | |
//! Get a pointer which would point to the same element as the iterator in case the circular buffer is linearized. | |
template <class Traits0> | |
typename Traits0::pointer linearize_pointer(const iterator<Buff, Traits0>& it) const { | |
return it.m_it == 0 ? m_buff->m_buff + m_buff->size() : | |
(it.m_it < m_buff->m_first ? it.m_it + (m_buff->m_end - m_buff->m_first) | |
: m_buff->m_buff + (it.m_it - m_buff->m_first)); | |
} | |
}; | |
//! Iterator addition. | |
template <class Buff, class Traits> | |
inline iterator<Buff, Traits> | |
operator + (typename Traits::difference_type n, const iterator<Buff, Traits>& it) { | |
return it + n; | |
} | |
#if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR) | |
//! Iterator category. | |
template <class Buff, class Traits> | |
inline std::random_access_iterator_tag iterator_category(const iterator<Buff, Traits>&) { | |
return std::random_access_iterator_tag(); | |
} | |
//! The type of the elements stored in the circular buffer. | |
template <class Buff, class Traits> | |
inline typename Traits::value_type* value_type(const iterator<Buff, Traits>&) { return 0; } | |
//! Distance type. | |
template <class Buff, class Traits> | |
inline typename Traits::difference_type* distance_type(const iterator<Buff, Traits>&) { return 0; } | |
#endif // #if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR) | |
/*! | |
\fn ForwardIterator uninitialized_copy_with_alloc(InputIterator first, InputIterator last, ForwardIterator dest, | |
Alloc& alloc) | |
\brief Equivalent of <code>std::uninitialized_copy</code> with allocator. | |
*/ | |
template<class InputIterator, class ForwardIterator, class Alloc> | |
inline ForwardIterator uninitialized_copy_with_alloc(InputIterator first, InputIterator last, ForwardIterator dest, | |
Alloc& alloc) { | |
ForwardIterator next = dest; | |
BOOST_TRY { | |
for (; first != last; ++first, ++dest) | |
alloc.construct(dest, *first); | |
} BOOST_CATCH(...) { | |
for (; next != dest; ++next) | |
alloc.destroy(next); | |
BOOST_RETHROW | |
} | |
BOOST_CATCH_END | |
return dest; | |
} | |
/*! | |
\fn void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc) | |
\brief Equivalent of <code>std::uninitialized_fill_n</code> with allocator. | |
*/ | |
template<class ForwardIterator, class Diff, class T, class Alloc> | |
inline void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc) { | |
ForwardIterator next = first; | |
BOOST_TRY { | |
for (; n > 0; ++first, --n) | |
alloc.construct(first, item); | |
} BOOST_CATCH(...) { | |
for (; next != first; ++next) | |
alloc.destroy(next); | |
BOOST_RETHROW | |
} | |
BOOST_CATCH_END | |
} | |
} // namespace cb_details | |
} // namespace boost | |
#endif // #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP) |