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 | |
35 | namespace boost { |
36 | |
37 | namespace cb_details { |
38 | |
39 | template <class Alloc> struct nonconst_traits; |
40 | |
41 | template<class ForwardIterator, class Diff, class T, class Alloc> |
42 | void uninitialized_fill_n_with_alloc( |
43 | ForwardIterator first, Diff n, const T& item, Alloc& alloc); |
44 | |
45 | template<class InputIterator, class ForwardIterator, class Alloc> |
46 | ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a); |
47 | |
48 | template<class InputIterator, class ForwardIterator, class Alloc> |
49 | ForwardIterator 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 | */ |
55 | template <class Alloc> |
56 | struct 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 | */ |
72 | template <class Alloc> |
73 | struct 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 | */ |
89 | template <class Iterator> |
90 | struct iterator_wrapper { |
91 | mutable Iterator m_it; |
92 | explicit iterator_wrapper(Iterator it) : m_it(it) {} |
93 | Iterator operator () () const { return m_it++; } |
94 | private: |
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 | */ |
102 | template <class Pointer, class Value> |
103 | struct item_wrapper { |
104 | Value m_item; |
105 | explicit item_wrapper(Value item) : m_item(item) {} |
106 | Pointer operator () () const { return &m_item; } |
107 | private: |
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 | */ |
115 | template <class Value, class Alloc> |
116 | struct 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 | } |
126 | private: |
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 | */ |
134 | template <class Iterator, class Alloc> |
135 | struct 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 | |
149 | template <class Iterator, class Alloc> |
150 | inline 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 | */ |
158 | template <class Size> |
159 | class 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 | |
167 | public: |
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 | */ |
198 | template <class Buff, class Traits> |
199 | struct 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. |
412 | template <class Buff, class Traits> |
413 | inline iterator<Buff, Traits> |
414 | operator + (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 | */ |
422 | template<class InputIterator, class ForwardIterator, class Alloc> |
423 | inline 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 | |
437 | template<class InputIterator, class ForwardIterator, class Alloc> |
438 | ForwardIterator 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 | |
445 | template<class InputIterator, class ForwardIterator, class Alloc> |
446 | ForwardIterator 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 | */ |
455 | template<class InputIterator, class ForwardIterator, class Alloc> |
456 | ForwardIterator 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 | */ |
465 | template<class ForwardIterator, class Diff, class T, class Alloc> |
466 | inline 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 | |