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

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