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#if !defined(BOOST_NO_CXX11_DEFAULTED_FUNCTIONS)
263 iterator& operator=(const iterator&) = default;
264#else
265 iterator& operator=(const iterator& it) {
266 if (this == &it)
267 return *this;
268#if BOOST_CB_ENABLE_DEBUG
269 debug_iterator_base::operator =(it);
270#endif // #if BOOST_CB_ENABLE_DEBUG
271 m_buff = it.m_buff;
272 m_it = it.m_it;
273 return *this;
274 }
275#endif
276
277// Random access iterator methods
278
279 //! Dereferencing operator.
280 reference operator * () const {
281 BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
282 BOOST_CB_ASSERT(m_it != 0); // check for iterator pointing to end()
283 return *m_it;
284 }
285
286 //! Dereferencing operator.
287 pointer operator -> () const { return &(operator*()); }
288
289 //! Difference operator.
290 template <class Traits0>
291 difference_type operator - (const iterator<Buff, Traits0>& it) const {
292 BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
293 BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
294 return linearize_pointer(*this) - linearize_pointer(it);
295 }
296
297 //! Increment operator (prefix).
298 iterator& operator ++ () {
299 BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
300 BOOST_CB_ASSERT(m_it != 0); // check for iterator pointing to end()
301 m_buff->increment(m_it);
302 if (m_it == m_buff->m_last)
303 m_it = 0;
304 return *this;
305 }
306
307 //! Increment operator (postfix).
308 iterator operator ++ (int) {
309 iterator<Buff, Traits> tmp = *this;
310 ++*this;
311 return tmp;
312 }
313
314 //! Decrement operator (prefix).
315 iterator& operator -- () {
316 BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
317 BOOST_CB_ASSERT(m_it != m_buff->m_first); // check for iterator pointing to begin()
318 if (m_it == 0)
319 m_it = m_buff->m_last;
320 m_buff->decrement(m_it);
321 return *this;
322 }
323
324 //! Decrement operator (postfix).
325 iterator operator -- (int) {
326 iterator<Buff, Traits> tmp = *this;
327 --*this;
328 return tmp;
329 }
330
331 //! Iterator addition.
332 iterator& operator += (difference_type n) {
333 BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
334 if (n > 0) {
335 BOOST_CB_ASSERT(m_buff->end() - *this >= n); // check for too large n
336 m_it = m_buff->add(m_it, n);
337 if (m_it == m_buff->m_last)
338 m_it = 0;
339 } else if (n < 0) {
340 *this -= -n;
341 }
342 return *this;
343 }
344
345 //! Iterator addition.
346 iterator operator + (difference_type n) const { return iterator<Buff, Traits>(*this) += n; }
347
348 //! Iterator subtraction.
349 iterator& operator -= (difference_type n) {
350 BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
351 if (n > 0) {
352 BOOST_CB_ASSERT(*this - m_buff->begin() >= n); // check for too large n
353 m_it = m_buff->sub(m_it == 0 ? m_buff->m_last : m_it, n);
354 } else if (n < 0) {
355 *this += -n;
356 }
357 return *this;
358 }
359
360 //! Iterator subtraction.
361 iterator operator - (difference_type n) const { return iterator<Buff, Traits>(*this) -= n; }
362
363 //! Element access operator.
364 reference operator [] (difference_type n) const { return *(*this + n); }
365
366// Equality & comparison
367
368 //! Equality.
369 template <class Traits0>
370 bool operator == (const iterator<Buff, Traits0>& it) const {
371 BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
372 BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
373 return m_it == it.m_it;
374 }
375
376 //! Inequality.
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 //! Less.
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 linearize_pointer(*this) < linearize_pointer(it);
390 }
391
392 //! Greater.
393 template <class Traits0>
394 bool operator > (const iterator<Buff, Traits0>& it) const { return it < *this; }
395
396 //! Less or equal.
397 template <class Traits0>
398 bool operator <= (const iterator<Buff, Traits0>& it) const { return !(it < *this); }
399
400 //! Greater or equal.
401 template <class Traits0>
402 bool operator >= (const iterator<Buff, Traits0>& it) const { return !(*this < it); }
403
404// Helpers
405
406 //! Get a pointer which would point to the same element as the iterator in case the circular buffer is linearized.
407 template <class Traits0>
408 typename Traits0::pointer linearize_pointer(const iterator<Buff, Traits0>& it) const {
409 return it.m_it == 0 ? m_buff->m_buff + m_buff->size() :
410 (it.m_it < m_buff->m_first ? it.m_it + (m_buff->m_end - m_buff->m_first)
411 : m_buff->m_buff + (it.m_it - m_buff->m_first));
412 }
413};
414
415//! Iterator addition.
416template <class Buff, class Traits>
417inline iterator<Buff, Traits>
418operator + (typename Traits::difference_type n, const iterator<Buff, Traits>& it) {
419 return it + n;
420}
421
422/*!
423 \fn ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest)
424 \brief Equivalent of <code>std::uninitialized_copy</code> but with explicit specification of value type.
425*/
426template<class InputIterator, class ForwardIterator, class Alloc>
427inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a) {
428 ForwardIterator next = dest;
429 BOOST_TRY {
430 for (; first != last; ++first, ++dest)
431 boost::allocator_construct(a, boost::to_address(dest), *first);
432 } BOOST_CATCH(...) {
433 for (; next != dest; ++next)
434 boost::allocator_destroy(a, boost::to_address(next));
435 BOOST_RETHROW
436 }
437 BOOST_CATCH_END
438 return dest;
439}
440
441template<class InputIterator, class ForwardIterator, class Alloc>
442ForwardIterator uninitialized_move_if_noexcept_impl(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a,
443 true_type) {
444 for (; first != last; ++first, ++dest)
445 boost::allocator_construct(a, boost::to_address(dest), boost::move(*first));
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 false_type) {
452 return uninitialized_copy(first, last, dest, a);
453}
454
455/*!
456 \fn ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest)
457 \brief Equivalent of <code>std::uninitialized_copy</code> but with explicit specification of value type and moves elements if they have noexcept move constructors.
458*/
459template<class InputIterator, class ForwardIterator, class Alloc>
460ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a) {
461 typedef typename boost::is_nothrow_move_constructible<typename Alloc::value_type>::type tag_t;
462 return uninitialized_move_if_noexcept_impl(first, last, dest, a, tag_t());
463}
464
465/*!
466 \fn void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc)
467 \brief Equivalent of <code>std::uninitialized_fill_n</code> with allocator.
468*/
469template<class ForwardIterator, class Diff, class T, class Alloc>
470inline void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc) {
471 ForwardIterator next = first;
472 BOOST_TRY {
473 for (; n > 0; ++first, --n)
474 boost::allocator_construct(alloc, boost::to_address(first), item);
475 } BOOST_CATCH(...) {
476 for (; next != first; ++next)
477 boost::allocator_destroy(alloc, boost::to_address(next));
478 BOOST_RETHROW
479 }
480 BOOST_CATCH_END
481}
482
483} // namespace cb_details
484
485} // namespace boost
486
487#if defined(_MSC_VER)
488# pragma warning(pop)
489#endif
490
491#endif // #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP)
492

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