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