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