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 | |
34 | namespace boost { |
35 | |
36 | namespace cb_details { |
37 | |
38 | template <class Traits> struct nonconst_traits; |
39 | |
40 | template<class ForwardIterator, class Diff, class T, class Alloc> |
41 | void uninitialized_fill_n_with_alloc( |
42 | ForwardIterator first, Diff n, const T& item, Alloc& alloc); |
43 | |
44 | template<class InputIterator, class ForwardIterator, class Alloc> |
45 | ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator dest, Alloc& a); |
46 | |
47 | template<class InputIterator, class ForwardIterator, class Alloc> |
48 | ForwardIterator 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 | */ |
54 | template <class Traits> |
55 | struct 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 | */ |
71 | template <class Traits> |
72 | struct 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 | */ |
88 | template <class Iterator> |
89 | struct iterator_wrapper { |
90 | mutable Iterator m_it; |
91 | explicit iterator_wrapper(Iterator it) : m_it(it) {} |
92 | Iterator operator () () const { return m_it++; } |
93 | private: |
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 | */ |
101 | template <class Pointer, class Value> |
102 | struct item_wrapper { |
103 | Value m_item; |
104 | explicit item_wrapper(Value item) : m_item(item) {} |
105 | Pointer operator () () const { return &m_item; } |
106 | private: |
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 | */ |
114 | template <class Value, class Alloc> |
115 | struct 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 | } |
125 | private: |
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 | */ |
133 | template <class Iterator, class Alloc> |
134 | struct 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 | |
148 | template <class Iterator, class Alloc> |
149 | inline 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 | */ |
157 | template <class Size> |
158 | class 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 | |
166 | public: |
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 | */ |
197 | template <class Buff, class Traits> |
198 | struct 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. |
424 | template <class Buff, class Traits> |
425 | inline iterator<Buff, Traits> |
426 | operator + (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 | */ |
434 | template<class InputIterator, class ForwardIterator, class Alloc> |
435 | inline 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 | |
449 | template<class InputIterator, class ForwardIterator, class Alloc> |
450 | ForwardIterator 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 | |
457 | template<class InputIterator, class ForwardIterator, class Alloc> |
458 | ForwardIterator 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 | */ |
467 | template<class InputIterator, class ForwardIterator, class Alloc> |
468 | ForwardIterator 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 | */ |
477 | template<class ForwardIterator, class Diff, class T, class Alloc> |
478 | inline 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 | |