Chris@16: // Helper classes and functions for the circular buffer. Chris@16: Chris@16: // Copyright (c) 2003-2008 Jan Gaspar Chris@101: // Copyright (c) 2014 Glen Fernandes // C++11 allocator model support. Chris@16: Chris@16: // Use, modification, and distribution is subject to the Boost Software Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at Chris@16: // http://www.boost.org/LICENSE_1_0.txt) Chris@16: Chris@16: #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP) Chris@16: #define BOOST_CIRCULAR_BUFFER_DETAILS_HPP Chris@16: Chris@101: #if defined(_MSC_VER) Chris@16: #pragma once Chris@16: #endif Chris@16: Chris@16: #include Chris@16: #include Chris@101: #include Chris@16: #include Chris@16: #include Chris@101: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: // Silence MS /W4 warnings like C4913: Chris@16: // "user defined binary operator ',' exists but no overload could convert all operands, default built-in binary operator ',' used" Chris@16: // This might happen when previously including some boost headers that overload the coma operator. Chris@16: #if defined(_MSC_VER) Chris@16: # pragma warning(push) Chris@16: # pragma warning(disable:4913) Chris@16: #endif Chris@16: Chris@16: namespace boost { Chris@16: Chris@16: namespace cb_details { Chris@16: Chris@16: template struct nonconst_traits; Chris@16: Chris@16: template Chris@16: void uninitialized_fill_n_with_alloc( Chris@16: ForwardIterator first, Diff n, const T& item, Alloc& alloc); Chris@16: Chris@101: template Chris@101: ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a); Chris@16: Chris@101: template Chris@101: ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a); Chris@16: Chris@16: /*! Chris@16: \struct const_traits Chris@16: \brief Defines the data types for a const iterator. Chris@16: */ Chris@16: template Chris@16: struct const_traits { Chris@16: // Basic types Chris@16: typedef typename Traits::value_type value_type; Chris@16: typedef typename Traits::const_pointer pointer; Chris@16: typedef typename Traits::const_reference reference; Chris@16: typedef typename Traits::size_type size_type; Chris@16: typedef typename Traits::difference_type difference_type; Chris@16: Chris@16: // Non-const traits Chris@16: typedef nonconst_traits nonconst_self; Chris@16: }; Chris@16: Chris@16: /*! Chris@16: \struct nonconst_traits Chris@16: \brief Defines the data types for a non-const iterator. Chris@16: */ Chris@16: template Chris@16: struct nonconst_traits { Chris@16: // Basic types Chris@16: typedef typename Traits::value_type value_type; Chris@16: typedef typename Traits::pointer pointer; Chris@16: typedef typename Traits::reference reference; Chris@16: typedef typename Traits::size_type size_type; Chris@16: typedef typename Traits::difference_type difference_type; Chris@16: Chris@16: // Non-const traits Chris@16: typedef nonconst_traits nonconst_self; Chris@16: }; Chris@16: Chris@16: /*! Chris@16: \struct iterator_wrapper Chris@16: \brief Helper iterator dereference wrapper. Chris@16: */ Chris@16: template Chris@16: struct iterator_wrapper { Chris@16: mutable Iterator m_it; Chris@16: explicit iterator_wrapper(Iterator it) : m_it(it) {} Chris@16: Iterator operator () () const { return m_it++; } Chris@16: private: Chris@16: iterator_wrapper& operator = (const iterator_wrapper&); // do not generate Chris@16: }; Chris@16: Chris@16: /*! Chris@16: \struct item_wrapper Chris@16: \brief Helper item dereference wrapper. Chris@16: */ Chris@16: template Chris@16: struct item_wrapper { Chris@16: Value m_item; Chris@16: explicit item_wrapper(Value item) : m_item(item) {} Chris@16: Pointer operator () () const { return &m_item; } Chris@16: private: Chris@16: item_wrapper& operator = (const item_wrapper&); // do not generate Chris@16: }; Chris@16: Chris@16: /*! Chris@16: \struct assign_n Chris@16: \brief Helper functor for assigning n items. Chris@16: */ Chris@16: template Chris@16: struct assign_n { Chris@101: typedef typename boost::container::allocator_traits::size_type size_type; Chris@16: size_type m_n; Chris@16: Value m_item; Chris@16: Alloc& m_alloc; Chris@16: assign_n(size_type n, Value item, Alloc& alloc) : m_n(n), m_item(item), m_alloc(alloc) {} Chris@16: template Chris@16: void operator () (Pointer p) const { Chris@16: uninitialized_fill_n_with_alloc(p, m_n, m_item, m_alloc); Chris@16: } Chris@16: private: Chris@16: assign_n& operator = (const assign_n&); // do not generate Chris@16: }; Chris@16: Chris@16: /*! Chris@16: \struct assign_range Chris@16: \brief Helper functor for assigning range of items. Chris@16: */ Chris@101: template Chris@16: struct assign_range { Chris@16: Iterator m_first; Chris@16: Iterator m_last; Chris@101: Alloc& m_alloc; Chris@16: Chris@101: assign_range(const Iterator& first, const Iterator& last, Alloc& alloc) Chris@101: : m_first(first), m_last(last), m_alloc(alloc) {} Chris@16: Chris@16: template Chris@16: void operator () (Pointer p) const { Chris@101: boost::cb_details::uninitialized_copy(m_first, m_last, p, m_alloc); Chris@16: } Chris@16: }; Chris@16: Chris@101: template Chris@101: inline assign_range make_assign_range(const Iterator& first, const Iterator& last, Alloc& a) { Chris@101: return assign_range(first, last, a); Chris@16: } Chris@16: Chris@16: /*! Chris@16: \class capacity_control Chris@16: \brief Capacity controller of the space optimized circular buffer. Chris@16: */ Chris@16: template Chris@16: class capacity_control { Chris@16: Chris@16: //! The capacity of the space-optimized circular buffer. Chris@16: Size m_capacity; Chris@16: Chris@16: //! The lowest guaranteed or minimum capacity of the adapted space-optimized circular buffer. Chris@16: Size m_min_capacity; Chris@16: Chris@16: public: Chris@16: Chris@16: //! Constructor. Chris@16: capacity_control(Size buffer_capacity, Size min_buffer_capacity = 0) Chris@16: : m_capacity(buffer_capacity), m_min_capacity(min_buffer_capacity) Chris@16: { // Check for capacity lower than min_capacity. Chris@16: BOOST_CB_ASSERT(buffer_capacity >= min_buffer_capacity); Chris@16: } Chris@16: Chris@16: // Default copy constructor. Chris@16: Chris@16: // Default assign operator. Chris@16: Chris@16: //! Get the capacity of the space optimized circular buffer. Chris@16: Size capacity() const { return m_capacity; } Chris@16: Chris@16: //! Get the minimal capacity of the space optimized circular buffer. Chris@16: Size min_capacity() const { return m_min_capacity; } Chris@16: Chris@16: //! Size operator - returns the capacity of the space optimized circular buffer. Chris@16: operator Size() const { return m_capacity; } Chris@16: }; Chris@16: Chris@16: /*! Chris@16: \struct iterator Chris@16: \brief Random access iterator for the circular buffer. Chris@16: \param Buff The type of the underlying circular buffer. Chris@16: \param Traits Basic iterator types. Chris@16: \note This iterator is not circular. It was designed Chris@16: for iterating from begin() to end() of the circular buffer. Chris@16: */ Chris@16: template Chris@16: struct iterator : Chris@16: public boost::iterator< Chris@16: std::random_access_iterator_tag, Chris@16: typename Traits::value_type, Chris@16: typename Traits::difference_type, Chris@16: typename Traits::pointer, Chris@16: typename Traits::reference> Chris@16: #if BOOST_CB_ENABLE_DEBUG Chris@16: , public debug_iterator_base Chris@16: #endif // #if BOOST_CB_ENABLE_DEBUG Chris@16: { Chris@16: // Helper types Chris@16: Chris@16: //! Base iterator. Chris@16: typedef boost::iterator< Chris@16: std::random_access_iterator_tag, Chris@16: typename Traits::value_type, Chris@16: typename Traits::difference_type, Chris@16: typename Traits::pointer, Chris@16: typename Traits::reference> base_iterator; Chris@16: Chris@16: //! Non-const iterator. Chris@16: typedef iterator nonconst_self; Chris@16: Chris@16: // Basic types Chris@16: Chris@16: //! The type of the elements stored in the circular buffer. Chris@16: typedef typename base_iterator::value_type value_type; Chris@16: Chris@16: //! Pointer to the element. Chris@16: typedef typename base_iterator::pointer pointer; Chris@16: Chris@16: //! Reference to the element. Chris@16: typedef typename base_iterator::reference reference; Chris@16: Chris@16: //! Size type. Chris@16: typedef typename Traits::size_type size_type; Chris@16: Chris@16: //! Difference type. Chris@16: typedef typename base_iterator::difference_type difference_type; Chris@16: Chris@16: // Member variables Chris@16: Chris@16: //! The circular buffer where the iterator points to. Chris@16: const Buff* m_buff; Chris@16: Chris@16: //! An internal iterator. Chris@16: pointer m_it; Chris@16: Chris@16: // Construction & assignment Chris@16: Chris@16: // Default copy constructor. Chris@16: Chris@16: //! Default constructor. Chris@16: iterator() : m_buff(0), m_it(0) {} Chris@16: Chris@16: #if BOOST_CB_ENABLE_DEBUG Chris@16: Chris@16: //! Copy constructor (used for converting from a non-const to a const iterator). Chris@16: iterator(const nonconst_self& it) : debug_iterator_base(it), m_buff(it.m_buff), m_it(it.m_it) {} Chris@16: Chris@16: //! Internal constructor. Chris@16: /*! Chris@16: \note This constructor is not intended to be used directly by the user. Chris@16: */ Chris@16: iterator(const Buff* cb, const pointer p) : debug_iterator_base(cb), m_buff(cb), m_it(p) {} Chris@16: Chris@16: #else Chris@16: Chris@16: iterator(const nonconst_self& it) : m_buff(it.m_buff), m_it(it.m_it) {} Chris@16: Chris@16: iterator(const Buff* cb, const pointer p) : m_buff(cb), m_it(p) {} Chris@16: Chris@16: #endif // #if BOOST_CB_ENABLE_DEBUG Chris@16: Chris@16: //! Assign operator. Chris@16: iterator& operator = (const iterator& it) { Chris@16: if (this == &it) Chris@16: return *this; Chris@16: #if BOOST_CB_ENABLE_DEBUG Chris@16: debug_iterator_base::operator =(it); Chris@16: #endif // #if BOOST_CB_ENABLE_DEBUG Chris@16: m_buff = it.m_buff; Chris@16: m_it = it.m_it; Chris@16: return *this; Chris@16: } Chris@16: Chris@16: // Random access iterator methods Chris@16: Chris@16: //! Dereferencing operator. Chris@16: reference operator * () const { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: BOOST_CB_ASSERT(m_it != 0); // check for iterator pointing to end() Chris@16: return *m_it; Chris@16: } Chris@16: Chris@16: //! Dereferencing operator. Chris@16: pointer operator -> () const { return &(operator*()); } Chris@16: Chris@16: //! Difference operator. Chris@16: template Chris@16: difference_type operator - (const iterator& it) const { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: return linearize_pointer(*this) - linearize_pointer(it); Chris@16: } Chris@16: Chris@16: //! Increment operator (prefix). Chris@16: iterator& operator ++ () { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: BOOST_CB_ASSERT(m_it != 0); // check for iterator pointing to end() Chris@16: m_buff->increment(m_it); Chris@16: if (m_it == m_buff->m_last) Chris@16: m_it = 0; Chris@16: return *this; Chris@16: } Chris@16: Chris@16: //! Increment operator (postfix). Chris@16: iterator operator ++ (int) { Chris@16: iterator tmp = *this; Chris@16: ++*this; Chris@16: return tmp; Chris@16: } Chris@16: Chris@16: //! Decrement operator (prefix). Chris@16: iterator& operator -- () { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: BOOST_CB_ASSERT(m_it != m_buff->m_first); // check for iterator pointing to begin() Chris@16: if (m_it == 0) Chris@16: m_it = m_buff->m_last; Chris@16: m_buff->decrement(m_it); Chris@16: return *this; Chris@16: } Chris@16: Chris@16: //! Decrement operator (postfix). Chris@16: iterator operator -- (int) { Chris@16: iterator tmp = *this; Chris@16: --*this; Chris@16: return tmp; Chris@16: } Chris@16: Chris@16: //! Iterator addition. Chris@16: iterator& operator += (difference_type n) { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: if (n > 0) { Chris@16: BOOST_CB_ASSERT(m_buff->end() - *this >= n); // check for too large n Chris@16: m_it = m_buff->add(m_it, n); Chris@16: if (m_it == m_buff->m_last) Chris@16: m_it = 0; Chris@16: } else if (n < 0) { Chris@16: *this -= -n; Chris@16: } Chris@16: return *this; Chris@16: } Chris@16: Chris@16: //! Iterator addition. Chris@16: iterator operator + (difference_type n) const { return iterator(*this) += n; } Chris@16: Chris@16: //! Iterator subtraction. Chris@16: iterator& operator -= (difference_type n) { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: if (n > 0) { Chris@16: BOOST_CB_ASSERT(*this - m_buff->begin() >= n); // check for too large n Chris@16: m_it = m_buff->sub(m_it == 0 ? m_buff->m_last : m_it, n); Chris@16: } else if (n < 0) { Chris@16: *this += -n; Chris@16: } Chris@16: return *this; Chris@16: } Chris@16: Chris@16: //! Iterator subtraction. Chris@16: iterator operator - (difference_type n) const { return iterator(*this) -= n; } Chris@16: Chris@16: //! Element access operator. Chris@16: reference operator [] (difference_type n) const { return *(*this + n); } Chris@16: Chris@16: // Equality & comparison Chris@16: Chris@16: //! Equality. Chris@16: template Chris@16: bool operator == (const iterator& it) const { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: return m_it == it.m_it; Chris@16: } Chris@16: Chris@16: //! Inequality. Chris@16: template Chris@16: bool operator != (const iterator& it) const { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: return m_it != it.m_it; Chris@16: } Chris@16: Chris@16: //! Less. Chris@16: template Chris@16: bool operator < (const iterator& it) const { Chris@16: BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator Chris@16: return linearize_pointer(*this) < linearize_pointer(it); Chris@16: } Chris@16: Chris@16: //! Greater. Chris@16: template Chris@16: bool operator > (const iterator& it) const { return it < *this; } Chris@16: Chris@16: //! Less or equal. Chris@16: template Chris@16: bool operator <= (const iterator& it) const { return !(it < *this); } Chris@16: Chris@16: //! Greater or equal. Chris@16: template Chris@16: bool operator >= (const iterator& it) const { return !(*this < it); } Chris@16: Chris@16: // Helpers Chris@16: Chris@16: //! Get a pointer which would point to the same element as the iterator in case the circular buffer is linearized. Chris@16: template Chris@16: typename Traits0::pointer linearize_pointer(const iterator& it) const { Chris@16: return it.m_it == 0 ? m_buff->m_buff + m_buff->size() : Chris@16: (it.m_it < m_buff->m_first ? it.m_it + (m_buff->m_end - m_buff->m_first) Chris@16: : m_buff->m_buff + (it.m_it - m_buff->m_first)); Chris@16: } Chris@16: }; Chris@16: Chris@16: //! Iterator addition. Chris@16: template Chris@16: inline iterator Chris@16: operator + (typename Traits::difference_type n, const iterator& it) { Chris@16: return it + n; Chris@16: } Chris@16: Chris@16: /*! Chris@16: \fn ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest) Chris@16: \brief Equivalent of std::uninitialized_copy but with explicit specification of value type. Chris@16: */ Chris@101: template Chris@101: inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a) { Chris@16: ForwardIterator next = dest; Chris@16: BOOST_TRY { Chris@16: for (; first != last; ++first, ++dest) Chris@101: boost::container::allocator_traits::construct(a, boost::addressof(*dest), *first); Chris@16: } BOOST_CATCH(...) { Chris@16: for (; next != dest; ++next) Chris@101: boost::container::allocator_traits::destroy(a, boost::addressof(*next)); Chris@16: BOOST_RETHROW Chris@16: } Chris@16: BOOST_CATCH_END Chris@16: return dest; Chris@16: } Chris@16: Chris@101: template Chris@101: ForwardIterator uninitialized_move_if_noexcept_impl(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a, Chris@16: true_type) { Chris@16: for (; first != last; ++first, ++dest) Chris@101: boost::container::allocator_traits::construct(a, boost::addressof(*dest), boost::move(*first)); Chris@16: return dest; Chris@16: } Chris@16: Chris@101: template Chris@101: ForwardIterator uninitialized_move_if_noexcept_impl(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a, Chris@16: false_type) { Chris@101: return uninitialized_copy(first, last, dest, a); Chris@16: } Chris@16: Chris@16: /*! Chris@16: \fn ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest) Chris@16: \brief Equivalent of std::uninitialized_copy but with explicit specification of value type and moves elements if they have noexcept move constructors. Chris@16: */ Chris@101: template Chris@101: ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a) { Chris@101: typedef typename boost::is_nothrow_move_constructible::value_type>::type tag_t; Chris@101: return uninitialized_move_if_noexcept_impl(first, last, dest, a, tag_t()); Chris@16: } Chris@16: Chris@16: /*! Chris@16: \fn void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc) Chris@16: \brief Equivalent of std::uninitialized_fill_n with allocator. Chris@16: */ Chris@16: template Chris@16: inline void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc) { Chris@16: ForwardIterator next = first; Chris@16: BOOST_TRY { Chris@16: for (; n > 0; ++first, --n) Chris@101: boost::container::allocator_traits::construct(alloc, boost::addressof(*first), item); Chris@16: } BOOST_CATCH(...) { Chris@16: for (; next != first; ++next) Chris@101: boost::container::allocator_traits::destroy(alloc, boost::addressof(*next)); Chris@16: BOOST_RETHROW Chris@16: } Chris@16: BOOST_CATCH_END Chris@16: } Chris@16: Chris@16: } // namespace cb_details Chris@16: Chris@16: } // namespace boost Chris@16: Chris@16: #if defined(_MSC_VER) Chris@16: # pragma warning(pop) Chris@16: #endif Chris@16: Chris@16: #endif // #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP)