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

source code of boost/boost/circular_buffer/details.hpp