ceph/src/boost/libs/circular_buffer/include/boost/circular_buffer/details.hpp

   1 // Helper classes and functions for the circular buffer.
   2
   3 // Copyright (c) 2003-2008 Jan Gaspar
   4 // Copyright (c) 2014 Glen Fernandes   // C++11 allocator model support.
   5
   6 // Use, modification, and distribution is subject to the Boost Software
   7 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9
  10 #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP)
  11 #define BOOST_CIRCULAR_BUFFER_DETAILS_HPP
  12
  13 #if defined(_MSC_VER)
  14     #pragma once
  15 #endif
  16
  17 #include <boost/throw_exception.hpp>
  18 #include <boost/container/allocator_traits.hpp>
  19 #include <boost/move/move.hpp>
  20 #include <boost/type_traits/is_nothrow_move_constructible.hpp>
  21 #include <boost/utility/addressof.hpp>
  22 #include <boost/detail/no_exceptions_support.hpp>
  23 #include <iterator>
  24
  25 // Silence MS /W4 warnings like C4913:
  26 // "user defined binary operator ',' exists but no overload could convert all operands, default built-in binary operator ',' used"
  27 // This might happen when previously including some boost headers that overload the coma operator.
  28 #if defined(_MSC_VER)
  29 #  pragma warning(push)
  30 #  pragma warning(disable:4913)
  31 #endif
  32
  33 namespace boost {
  34
  35 namespace cb_details {
  36
  37 template <class Traits> struct nonconst_traits;
  38
  39 template<class ForwardIterator, class Diff, class T, class Alloc>
  40 void uninitialized_fill_n_with_alloc(
  41     ForwardIterator first, Diff n, const T& item, Alloc& alloc);
  42
  43 template<class InputIterator, class ForwardIterator, class Alloc>
  44 ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a);
  45
  46 template<class InputIterator, class ForwardIterator, class Alloc>
  47 ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a);
  48
  49 /*!
  50     \struct const_traits
  51     \brief Defines the data types for a const iterator.
  52 */
  53 template <class Traits>
  54 struct const_traits {
  55     // Basic types
  56     typedef typename Traits::value_type value_type;
  57     typedef typename Traits::const_pointer pointer;
  58     typedef typename Traits::const_reference reference;
  59     typedef typename Traits::size_type size_type;
  60     typedef typename Traits::difference_type difference_type;
  61
  62     // Non-const traits
  63     typedef nonconst_traits<Traits> nonconst_self;
  64 };
  65
  66 /*!
  67     \struct nonconst_traits
  68     \brief Defines the data types for a non-const iterator.
  69 */
  70 template <class Traits>
  71 struct nonconst_traits {
  72     // Basic types
  73     typedef typename Traits::value_type value_type;
  74     typedef typename Traits::pointer pointer;
  75     typedef typename Traits::reference reference;
  76     typedef typename Traits::size_type size_type;
  77     typedef typename Traits::difference_type difference_type;
  78
  79     // Non-const traits
  80     typedef nonconst_traits<Traits> nonconst_self;
  81 };
  82
  83 /*!
  84     \struct iterator_wrapper
  85     \brief Helper iterator dereference wrapper.
  86 */
  87 template <class Iterator>
  88 struct iterator_wrapper {
  89     mutable Iterator m_it;
  90     explicit iterator_wrapper(Iterator it) : m_it(it) {}
  91     Iterator operator () () const { return m_it++; }
  92 private:
  93     iterator_wrapper<Iterator>& operator = (const iterator_wrapper<Iterator>&); // do not generate
  94 };
  95
  96 /*!
  97     \struct item_wrapper
  98     \brief Helper item dereference wrapper.
  99 */
 100 template <class Pointer, class Value>
 101 struct item_wrapper {
 102     Value m_item;
 103     explicit item_wrapper(Value item) : m_item(item) {}
 104     Pointer operator () () const { return &m_item; }
 105 private:
 106     item_wrapper<Pointer, Value>& operator = (const item_wrapper<Pointer, Value>&); // do not generate
 107 };
 108
 109 /*!
 110     \struct assign_n
 111     \brief Helper functor for assigning n items.
 112 */
 113 template <class Value, class Alloc>
 114 struct assign_n {
 115     typedef typename boost::container::allocator_traits<Alloc>::size_type size_type;
 116     size_type m_n;
 117     Value m_item;
 118     Alloc& m_alloc;
 119     assign_n(size_type n, Value item, Alloc& alloc) : m_n(n), m_item(item), m_alloc(alloc) {}
 120     template <class Pointer>
 121     void operator () (Pointer p) const {
 122         uninitialized_fill_n_with_alloc(p, m_n, m_item, m_alloc);
 123     }
 124 private:
 125     assign_n<Value, Alloc>& operator = (const assign_n<Value, Alloc>&); // do not generate
 126 };
 127
 128 /*!
 129     \struct assign_range
 130     \brief Helper functor for assigning range of items.
 131 */
 132 template <class Iterator, class Alloc>
 133 struct assign_range {
 134     Iterator m_first;
 135     Iterator m_last;
 136     Alloc&   m_alloc;
 137
 138     assign_range(const Iterator& first, const Iterator& last, Alloc& alloc)
 139         : m_first(first), m_last(last), m_alloc(alloc) {}
 140
 141     template <class Pointer>
 142     void operator () (Pointer p) const {
 143         boost::cb_details::uninitialized_copy(m_first, m_last, p, m_alloc);
 144     }
 145 };
 146
 147 template <class Iterator, class Alloc>
 148 inline assign_range<Iterator, Alloc> make_assign_range(const Iterator& first, const Iterator& last, Alloc& a) {
 149     return assign_range<Iterator, Alloc>(first, last, a);
 150 }
 151
 152 /*!
 153     \class capacity_control
 154     \brief Capacity controller of the space optimized circular buffer.
 155 */
 156 template <class Size>
 157 class capacity_control {
 158
 159     //! The capacity of the space-optimized circular buffer.
 160     Size m_capacity;
 161
 162     //! The lowest guaranteed or minimum capacity of the adapted space-optimized circular buffer.
 163     Size m_min_capacity;
 164
 165 public:
 166
 167     //! Constructor.
 168     capacity_control(Size buffer_capacity, Size min_buffer_capacity = 0)
 169     : m_capacity(buffer_capacity), m_min_capacity(min_buffer_capacity)
 170     { // Check for capacity lower than min_capacity.
 171         BOOST_CB_ASSERT(buffer_capacity >= min_buffer_capacity);
 172     }
 173
 174     // Default copy constructor.
 175
 176     // Default assign operator.
 177
 178     //! Get the capacity of the space optimized circular buffer.
 179     Size capacity() const { return m_capacity; }
 180
 181     //! Get the minimal capacity of the space optimized circular buffer.
 182     Size min_capacity() const { return m_min_capacity; }
 183
 184     //! Size operator - returns the capacity of the space optimized circular buffer.
 185     operator Size() const { return m_capacity; }
 186 };
 187
 188 /*!
 189     \struct iterator
 190     \brief Random access iterator for the circular buffer.
 191     \param Buff The type of the underlying circular buffer.
 192     \param Traits Basic iterator types.
 193     \note This iterator is not circular. It was designed
 194           for iterating from begin() to end() of the circular buffer.
 195 */
 196 template <class Buff, class Traits>
 197 struct iterator :
 198     public std::iterator<
 199     std::random_access_iterator_tag,
 200     typename Traits::value_type,
 201     typename Traits::difference_type,
 202     typename Traits::pointer,
 203     typename Traits::reference>
 204 #if BOOST_CB_ENABLE_DEBUG
 205     , public debug_iterator_base
 206 #endif // #if BOOST_CB_ENABLE_DEBUG
 207 {
 208 // Helper types
 209
 210     //! Base iterator.
 211     typedef std::iterator<
 212         std::random_access_iterator_tag,
 213         typename Traits::value_type,
 214         typename Traits::difference_type,
 215         typename Traits::pointer,
 216         typename Traits::reference> base_iterator;
 217
 218     //! Non-const iterator.
 219     typedef iterator<Buff, typename Traits::nonconst_self> nonconst_self;
 220
 221 // Basic types
 222
 223     //! The type of the elements stored in the circular buffer.
 224     typedef typename base_iterator::value_type value_type;
 225
 226     //! Pointer to the element.
 227     typedef typename base_iterator::pointer pointer;
 228
 229     //! Reference to the element.
 230     typedef typename base_iterator::reference reference;
 231
 232     //! Size type.
 233     typedef typename Traits::size_type size_type;
 234
 235     //! Difference type.
 236     typedef typename base_iterator::difference_type difference_type;
 237
 238 // Member variables
 239
 240     //! The circular buffer where the iterator points to.
 241     const Buff* m_buff;
 242
 243     //! An internal iterator.
 244     pointer m_it;
 245
 246 // Construction & assignment
 247
 248     // Default copy constructor.
 249
 250     //! Default constructor.
 251     iterator() : m_buff(0), m_it(0) {}
 252
 253 #if BOOST_CB_ENABLE_DEBUG
 254
 255     //! Copy constructor (used for converting from a non-const to a const iterator).
 256     iterator(const nonconst_self& it) : debug_iterator_base(it), m_buff(it.m_buff), m_it(it.m_it) {}
 257
 258     //! Internal constructor.
 259     /*!
 260         \note This constructor is not intended to be used directly by the user.
 261     */
 262     iterator(const Buff* cb, const pointer p) : debug_iterator_base(cb), m_buff(cb), m_it(p) {}
 263
 264 #else
 265
 266     iterator(const nonconst_self& it) : m_buff(it.m_buff), m_it(it.m_it) {}
 267
 268     iterator(const Buff* cb, const pointer p) : m_buff(cb), m_it(p) {}
 269
 270 #endif // #if BOOST_CB_ENABLE_DEBUG
 271
 272     //! Assign operator.
 273     iterator& operator = (const iterator& it) {
 274         if (this == &it)
 275             return *this;
 276 #if BOOST_CB_ENABLE_DEBUG
 277         debug_iterator_base::operator =(it);
 278 #endif // #if BOOST_CB_ENABLE_DEBUG
 279         m_buff = it.m_buff;
 280         m_it = it.m_it;
 281         return *this;
 282     }
 283
 284 // Random access iterator methods
 285
 286     //! Dereferencing operator.
 287     reference operator * () const {
 288         BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
 289         BOOST_CB_ASSERT(m_it != 0);        // check for iterator pointing to end()
 290         return *m_it;
 291     }
 292
 293     //! Dereferencing operator.
 294     pointer operator -> () const { return &(operator*()); }
 295
 296     //! Difference operator.
 297     template <class Traits0>
 298     difference_type operator - (const iterator<Buff, Traits0>& it) const {
 299         BOOST_CB_ASSERT(is_valid(m_buff));    // check for uninitialized or invalidated iterator
 300         BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
 301         return linearize_pointer(*this) - linearize_pointer(it);
 302     }
 303
 304     //! Increment operator (prefix).
 305     iterator& operator ++ () {
 306         BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
 307         BOOST_CB_ASSERT(m_it != 0);        // check for iterator pointing to end()
 308         m_buff->increment(m_it);
 309         if (m_it == m_buff->m_last)
 310             m_it = 0;
 311         return *this;
 312     }
 313
 314     //! Increment operator (postfix).
 315     iterator operator ++ (int) {
 316         iterator<Buff, Traits> tmp = *this;
 317         ++*this;
 318         return tmp;
 319     }
 320
 321     //! Decrement operator (prefix).
 322     iterator& operator -- () {
 323         BOOST_CB_ASSERT(is_valid(m_buff));        // check for uninitialized or invalidated iterator
 324         BOOST_CB_ASSERT(m_it != m_buff->m_first); // check for iterator pointing to begin()
 325         if (m_it == 0)
 326             m_it = m_buff->m_last;
 327         m_buff->decrement(m_it);
 328         return *this;
 329     }
 330
 331     //! Decrement operator (postfix).
 332     iterator operator -- (int) {
 333         iterator<Buff, Traits> tmp = *this;
 334         --*this;
 335         return tmp;
 336     }
 337
 338     //! Iterator addition.
 339     iterator& operator += (difference_type n) {
 340         BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
 341         if (n > 0) {
 342             BOOST_CB_ASSERT(m_buff->end() - *this >= n); // check for too large n
 343             m_it = m_buff->add(m_it, n);
 344             if (m_it == m_buff->m_last)
 345                 m_it = 0;
 346         } else if (n < 0) {
 347             *this -= -n;
 348         }
 349         return *this;
 350     }
 351
 352     //! Iterator addition.
 353     iterator operator + (difference_type n) const { return iterator<Buff, Traits>(*this) += n; }
 354
 355     //! Iterator subtraction.
 356     iterator& operator -= (difference_type n) {
 357         BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
 358         if (n > 0) {
 359             BOOST_CB_ASSERT(*this - m_buff->begin() >= n); // check for too large n
 360             m_it = m_buff->sub(m_it == 0 ? m_buff->m_last : m_it, n);
 361         } else if (n < 0) {
 362             *this += -n;
 363         }
 364         return *this;
 365     }
 366
 367     //! Iterator subtraction.
 368     iterator operator - (difference_type n) const { return iterator<Buff, Traits>(*this) -= n; }
 369
 370     //! Element access operator.
 371     reference operator [] (difference_type n) const { return *(*this + n); }
 372
 373 // Equality & comparison
 374
 375     //! Equality.
 376     template <class Traits0>
 377     bool operator == (const iterator<Buff, Traits0>& it) const {
 378         BOOST_CB_ASSERT(is_valid(m_buff));    // check for uninitialized or invalidated iterator
 379         BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
 380         return m_it == it.m_it;
 381     }
 382
 383     //! Inequality.
 384     template <class Traits0>
 385     bool operator != (const iterator<Buff, Traits0>& it) const {
 386         BOOST_CB_ASSERT(is_valid(m_buff));    // check for uninitialized or invalidated iterator
 387         BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
 388         return m_it != it.m_it;
 389     }
 390
 391     //! Less.
 392     template <class Traits0>
 393     bool operator < (const iterator<Buff, Traits0>& it) const {
 394         BOOST_CB_ASSERT(is_valid(m_buff));    // check for uninitialized or invalidated iterator
 395         BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
 396         return linearize_pointer(*this) < linearize_pointer(it);
 397     }
 398
 399     //! Greater.
 400     template <class Traits0>
 401     bool operator > (const iterator<Buff, Traits0>& it) const { return it < *this; }
 402
 403     //! Less or equal.
 404     template <class Traits0>
 405     bool operator <= (const iterator<Buff, Traits0>& it) const { return !(it < *this); }
 406
 407     //! Greater or equal.
 408     template <class Traits0>
 409     bool operator >= (const iterator<Buff, Traits0>& it) const { return !(*this < it); }
 410
 411 // Helpers
 412
 413     //! Get a pointer which would point to the same element as the iterator in case the circular buffer is linearized.
 414     template <class Traits0>
 415     typename Traits0::pointer linearize_pointer(const iterator<Buff, Traits0>& it) const {
 416         return it.m_it == 0 ? m_buff->m_buff + m_buff->size() :
 417             (it.m_it < m_buff->m_first ? it.m_it + (m_buff->m_end - m_buff->m_first)
 418                 : m_buff->m_buff + (it.m_it - m_buff->m_first));
 419     }
 420 };
 421
 422 //! Iterator addition.
 423 template <class Buff, class Traits>
 424 inline iterator<Buff, Traits>
 425 operator + (typename Traits::difference_type n, const iterator<Buff, Traits>& it) {
 426     return it + n;
 427 }
 428
 429 /*!
 430     \fn ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest)
 431     \brief Equivalent of <code>std::uninitialized_copy</code> but with explicit specification of value type.
 432 */
 433 template<class InputIterator, class ForwardIterator, class Alloc>
 434 inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a) {
 435     ForwardIterator next = dest;
 436     BOOST_TRY {
 437         for (; first != last; ++first, ++dest)
 438             boost::container::allocator_traits<Alloc>::construct(a, boost::addressof(*dest), *first);
 439     } BOOST_CATCH(...) {
 440         for (; next != dest; ++next)
 441             boost::container::allocator_traits<Alloc>::destroy(a, boost::addressof(*next));
 442         BOOST_RETHROW
 443     }
 444     BOOST_CATCH_END
 445     return dest;
 446 }
 447
 448 template<class InputIterator, class ForwardIterator, class Alloc>
 449 ForwardIterator uninitialized_move_if_noexcept_impl(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a,
 450     true_type) {
 451     for (; first != last; ++first, ++dest)
 452         boost::container::allocator_traits<Alloc>::construct(a, boost::addressof(*dest), boost::move(*first));
 453     return dest;
 454 }
 455
 456 template<class InputIterator, class ForwardIterator, class Alloc>
 457 ForwardIterator uninitialized_move_if_noexcept_impl(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a,
 458     false_type) {
 459     return uninitialized_copy(first, last, dest, a);
 460 }
 461
 462 /*!
 463     \fn ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest)
 464     \brief Equivalent of <code>std::uninitialized_copy</code> but with explicit specification of value type and moves elements if they have noexcept move constructors.
 465 */
 466 template<class InputIterator, class ForwardIterator, class Alloc>
 467 ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a) {
 468     typedef typename boost::is_nothrow_move_constructible<typename boost::container::allocator_traits<Alloc>::value_type>::type tag_t;
 469     return uninitialized_move_if_noexcept_impl(first, last, dest, a, tag_t());
 470 }
 471
 472 /*!
 473     \fn void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc)
 474     \brief Equivalent of <code>std::uninitialized_fill_n</code> with allocator.
 475 */
 476 template<class ForwardIterator, class Diff, class T, class Alloc>
 477 inline void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc) {
 478     ForwardIterator next = first;
 479     BOOST_TRY {
 480         for (; n > 0; ++first, --n)
 481             boost::container::allocator_traits<Alloc>::construct(alloc, boost::addressof(*first), item);
 482     } BOOST_CATCH(...) {
 483         for (; next != first; ++next)
 484             boost::container::allocator_traits<Alloc>::destroy(alloc, boost::addressof(*next));
 485         BOOST_RETHROW
 486     }
 487     BOOST_CATCH_END
 488 }
 489
 490 } // namespace cb_details
 491
 492 } // namespace boost
 493
 494 #if defined(_MSC_VER)
 495 #  pragma warning(pop)
 496 #endif
 497
 498 #endif // #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP)