monotone

monotone Mtn Source Tree

Root/src/boost/circular_buffer_base.hpp

1// Implementation of the base circular buffer.
2
3// Copyright (c) 2003
4// Jan Gaspar, Whitestein Technologies
5
6// Permission to use or copy this software for any purpose is hereby granted
7// without fee, provided the above notices are retained on all copies.
8// Permission to modify the code and to distribute modified code is granted,
9// provided the above notices are retained, and a notice that the code was
10// modified is included with the above copyright notice.
11
12// This material is provided "as is", with absolutely no warranty expressed
13// or implied. Any use is at your own risk.
14
15#if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)
16#define BOOST_CIRCULAR_BUFFER_BASE_HPP
17
18#include <boost/concept_check.hpp>
19#include <boost/iterator.hpp>
20#include <boost/iterator_adaptors.hpp>
21#include <boost/call_traits.hpp>
22#include <boost/type_traits.hpp>
23#include <boost/throw_exception.hpp>
24#include <boost/assert.hpp>
25#include <boost/version.hpp>
26
27#if BOOST_VERSION >= 103100
28#include <boost/iterator/reverse_iterator.hpp>
29#endif
30
31#include <memory>
32#include <algorithm>
33#if !defined(BOOST_NO_EXCEPTIONS)
34 #include <stdexcept>
35#endif
36
37namespace boost {
38
39// Exception handling macros.
40#if !defined(BOOST_NO_EXCEPTIONS)
41 #define BOOST_CB_TRY try {
42 #define BOOST_CB_UNWIND(action) } catch(...) { action; throw; }
43#else
44 #define BOOST_CB_TRY
45 #define BOOST_CB_UNWIND(action)
46#endif
47
48namespace cb_details {
49
50/*
51 \struct cb_int_iterator_tag
52 \brief Identifying tag for integer types (not for iterators).
53*/
54struct cb_int_iterator_tag {};
55
56/*
57 \struct cb_iterator_category
58 \brief Defines iterator category.
59*/
60template <bool>
61struct cb_iterator_category {
62 //! Represents iterators.
63 typedef std::input_iterator_tag iterator_category;
64};
65
66template <>
67struct cb_iterator_category<true> {
68 //! Represents integral types (not iterators).
69 typedef cb_int_iterator_tag iterator_category;
70};
71
72/*
73 \struct cb_iterator_category_traits
74 \brief Defines the iterator category tag for the given iterator.
75*/
76template <class Iterator>
77struct cb_iterator_category_traits {
78 //! Iterator category tag type.
79 /*!
80 Depending on the template parameter the <tt>tag</tt> distinguishes
81 between iterators and non-iterators. If the template parameter
82 is an iterator the <tt>tag</tt> is typedef for <tt>std::input_iterator_tag</tt>.
83 If the parameter is not an iterator the <tt>tag</tt> is typedef for
84 <tt>cb_int_iterator_tag</tt>.
85 */
86 typedef typename cb_details::cb_iterator_category<
87 is_integral<Iterator>::value>::iterator_category tag;
88};
89
90template <class Traits> struct cb_nonconst_traits;
91
92/*
93 \struct cb_const_traits
94 \brief Defines the data types for a const iterator.
95 \param Traits Defines the basic types.
96*/
97template <class Traits>
98struct cb_const_traits {
99// Basic types
100 typedef typename Traits::value_type value_type;
101 typedef typename Traits::const_pointer pointer;
102 typedef typename Traits::const_reference reference;
103 typedef typename Traits::size_type size_type;
104 typedef typename Traits::difference_type difference_type;
105
106// Non-const traits
107 typedef cb_nonconst_traits<Traits> nonconst_traits;
108};
109
110/*
111 \struct cb_nonconst_traits
112 \brief Defines the data types for a non-const iterator.
113 \param Traits Defines the basic types.
114*/
115template <class Traits>
116struct cb_nonconst_traits {
117// Basic types
118 typedef typename Traits::value_type value_type;
119 typedef typename Traits::pointer pointer;
120 typedef typename Traits::reference reference;
121 typedef typename Traits::size_type size_type;
122 typedef typename Traits::difference_type difference_type;
123
124// Non-const traits
125 typedef cb_nonconst_traits<Traits> nonconst_traits;
126};
127
128/*
129 \struct cb_internal_pointer
130 \brief Helper pointer used in the cb_iterator.
131*/
132template <class Traits0>
133struct cb_helper_pointer {
134 bool m_end;
135 typename Traits0::pointer m_it;
136};
137
138/*
139 \class cb_iterator
140 \brief Random access iterator for the circular buffer.
141 \param Buff The type of the underlying circular buffer.
142 \param Traits Defines basic iterator types.
143 \note This iterator is not circular. It was designed
144 for iterating from begin() to end() of the circular buffer.
145*/
146template <class Buff, class Traits>
147class cb_iterator :
148 public boost::iterator<
149 std::random_access_iterator_tag,
150 typename Traits::value_type,
151 typename Traits::difference_type,
152 typename Traits::pointer,
153 typename Traits::reference>
154{
155private:
156// Helper types
157
158 //! Base iterator.
159 typedef boost::iterator<
160 std::random_access_iterator_tag,
161 typename Traits::value_type,
162 typename Traits::difference_type,
163 typename Traits::pointer,
164 typename Traits::reference> base_type;
165
166 //! Non-const iterator.
167 typedef cb_iterator<Buff, typename Traits::nonconst_traits> nonconst_self;
168
169public:
170// Basic types
171
172 //! The type of the elements stored in the circular buffer.
173 typedef typename base_type::value_type value_type;
174
175 //! Pointer to the element.
176 typedef typename base_type::pointer pointer;
177
178 //! Reference to the element.
179 typedef typename base_type::reference reference;
180
181 //! Size type.
182 typedef typename Traits::size_type size_type;
183
184 //! Difference type.
185 typedef typename base_type::difference_type difference_type;
186
187public:
188// Member variables
189
190 //! The circular buffer where the iterator points to.
191 const Buff* m_buff;
192
193 //! An internal iterator.
194 pointer m_it;
195
196public:
197// Construction & assignment
198
199 // Default copy constructor.
200
201 //! Default constructor.
202 cb_iterator() : m_buff(0), m_it(0) {}
203
204 //! Copy constructor (used for converting from a non-const to a const iterator).
205 cb_iterator(const nonconst_self& it)
206 : m_buff(it.m_buff), m_it(it.m_it) {}
207
208 //! Internal constructor.
209 /*!
210 \note This constructor is not intended to be used directly by the user.
211 */
212 cb_iterator(const Buff* cb, const pointer it)
213 : m_buff(cb), m_it(it) {}
214
215 // Default assign operator.
216
217public:
218// Random access iterator methods
219
220 //! Dereferencing operator.
221 reference operator * () const {
222 BOOST_ASSERT(m_buff != 0); // uninitialized iterator
223 BOOST_ASSERT(m_it != 0); // iterator pointing to the end
224 return *m_it;
225 }
226
227 //! Dereferencing operator.
228 pointer operator -> () const { return &(operator*()); }
229
230 //! Difference operator.
231 difference_type operator - (const cb_iterator& it) const {
232 BOOST_ASSERT(m_buff != 0); // uninitialized iterator
233 BOOST_ASSERT(it.m_buff != 0); // uninitialized iterator
234 BOOST_ASSERT(m_buff == it.m_buff); // iterators of different containers or invalidated iterator
235 cb_helper_pointer<Traits> lhs = create_helper_pointer(*this);
236 cb_helper_pointer<Traits> rhs = create_helper_pointer(it);
237 if (less(rhs, lhs) && lhs.m_it <= rhs.m_it)
238 return lhs.m_it + m_buff->capacity() - rhs.m_it;
239 if (less(lhs, rhs) && lhs.m_it >= rhs.m_it)
240 return lhs.m_it - m_buff->capacity() - rhs.m_it;
241 return lhs.m_it - rhs.m_it;
242 }
243
244 //! Increment operator (prefix).
245 cb_iterator& operator ++ () {
246 BOOST_ASSERT(m_buff != 0); // uninitialized iterator
247 BOOST_ASSERT(m_it != 0); // iterator pointing to the end
248 m_buff->increment(m_it);
249 if (m_it == m_buff->m_last)
250 m_it = 0;
251 return *this;
252 }
253
254 //! Increment operator (postfix).
255 cb_iterator operator ++ (int) {
256 cb_iterator tmp = *this;
257 ++*this;
258 return tmp;
259 }
260
261 //! Decrement operator (prefix).
262 cb_iterator& operator -- () {
263 BOOST_ASSERT(m_buff != 0); // uninitialized iterator
264 if (m_it == 0)
265 m_it = m_buff->m_last;
266 m_buff->decrement(m_it);
267 return *this;
268 }
269
270 //! Decrement operator (postfix).
271 cb_iterator operator -- (int) {
272 cb_iterator tmp = *this;
273 --*this;
274 return tmp;
275 }
276
277 //! Iterator addition.
278 cb_iterator& operator += (difference_type n) {
279 if (n > 0) {
280 BOOST_ASSERT(m_buff != 0); // uninitialized iterator
281 BOOST_ASSERT(m_it != 0); // iterator pointing to the end
282 m_it = m_buff->add(m_it, n);
283 if (m_it == m_buff->m_last)
284 m_it = 0;
285 } else if (n < 0) {
286 *this -= -n;
287 }
288 return *this;
289 }
290
291 //! Iterator addition.
292 cb_iterator operator + (difference_type n) const { return cb_iterator(*this) += n; }
293
294 //! Iterator subtraction.
295 cb_iterator& operator -= (difference_type n) {
296 if (n > 0) {
297 BOOST_ASSERT(m_buff != 0);
298 m_it = m_buff->sub(m_it == 0 ? m_buff->m_last : m_it, n);
299 } else if (n < 0) {
300 *this += -n;
301 }
302 return *this;
303 }
304
305 //! Iterator subtraction.
306 cb_iterator operator - (difference_type n) const { return cb_iterator(*this) -= n; }
307
308 //! Element access operator.
309 reference operator [] (difference_type n) const { return *(*this + n); }
310
311public:
312// Equality & comparison
313
314 //! Equality.
315 template <class Traits0>
316 bool operator == (const cb_iterator<Buff, Traits0>& it) const {
317 BOOST_ASSERT(m_buff != 0); // uninitialized iterator
318 BOOST_ASSERT(it.m_buff != 0); // uninitialized iterator
319 BOOST_ASSERT(m_buff == it.m_buff); // iterators of different containers or invalidated iterator
320 return m_it == it.m_it;
321 }
322
323 //! Inequality.
324 template <class Traits0>
325 bool operator != (const cb_iterator<Buff, Traits0>& it) const {
326 BOOST_ASSERT(m_buff != 0); // uninitialized iterator
327 BOOST_ASSERT(it.m_buff != 0); // uninitialized iterator
328 BOOST_ASSERT(m_buff == it.m_buff); // iterators of different containers or invalidated iterator
329 return m_it != it.m_it;
330 }
331
332 //! Less.
333 template <class Traits0>
334 bool operator < (const cb_iterator<Buff, Traits0>& it) const {
335 BOOST_ASSERT(m_buff != 0); // uninitialized iterator
336 BOOST_ASSERT(it.m_buff != 0); // uninitialized iterator
337 BOOST_ASSERT(m_buff == it.m_buff); // iterators of different containers or invalidated iterator
338 return less(create_helper_pointer(*this), create_helper_pointer(it));
339 }
340
341 //! Greater.
342 template <class Traits0>
343 bool operator > (const cb_iterator<Buff, Traits0>& it) const { return it < *this; }
344
345 //! Less or equal.
346 template <class Traits0>
347 bool operator <= (const cb_iterator<Buff, Traits0>& it) const { return !(it < *this); }
348
349 //! Greater or equal.
350 template <class Traits0>
351 bool operator >= (const cb_iterator<Buff, Traits0>& it) const { return !(*this < it); }
352
353private:
354// Helpers
355
356 //! Create helper pointer.
357 template <class Traits0>
358 cb_helper_pointer<Traits0> create_helper_pointer(const cb_iterator<Buff, Traits0>& it) const {
359 cb_helper_pointer<Traits0> helper;
360 helper.m_end = (it.m_it == 0);
361 helper.m_it = helper.m_end ? m_buff->m_last : it.m_it;
362 return helper;
363 }
364
365 //! Compare two pointers.
366 /*!
367 \return 1 if p1 is greater than p2.
368 \return 0 if p1 is equal to p2.
369 \return -1 if p1 is lower than p2.
370 */
371 template <class Pointer0, class Pointer1>
372 static difference_type compare(Pointer0 p1, Pointer1 p2) {
373 return p1 < p2 ? -1 : (p1 > p2 ? 1 : 0);
374 }
375
376 //! Less.
377 template <class InternalIterator0, class InternalIterator1>
378 bool less(const InternalIterator0& lhs, const InternalIterator1& rhs) const {
379 switch (compare(lhs.m_it, m_buff->m_first)) {
380 case -1:
381 switch (compare(rhs.m_it, m_buff->m_first)) {
382 case -1: return lhs.m_it < rhs.m_it;
383 case 0: return rhs.m_end;
384 case 1: return false;
385 }
386 case 0:
387 switch (compare(rhs.m_it, m_buff->m_first)) {
388 case -1: return !lhs.m_end;
389 case 0: return !lhs.m_end && rhs.m_end;
390 case 1: return !lhs.m_end;
391 }
392 case 1:
393 switch (compare(rhs.m_it, m_buff->m_first)) {
394 case -1: return true;
395 case 0: return rhs.m_end;
396 case 1: return lhs.m_it < rhs.m_it;
397 }
398 }
399 return false;
400 }
401};
402
403//! Iterator addition.
404template <class Buff, class Traits>
405inline cb_iterator<Buff, Traits>
406operator + (typename Traits::difference_type n, const cb_iterator<Buff, Traits>& it) {
407 return it + n;
408}
409
410#if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR)
411
412//! Iterator category.
413template <class Buff, class Traits>
414inline std::random_access_iterator_tag
415iterator_category(const cb_iterator<Buff, Traits>&) {
416 return std::random_access_iterator_tag();
417}
418
419//! The type of the elements stored in the circular buffer.
420template <class Buff, class Traits>
421inline typename Traits::value_type*
422value_type(const cb_iterator<Buff, Traits>&) { return 0; }
423
424//! Distance type.
425template <class Buff, class Traits>
426inline typename Traits::difference_type*
427distance_type(const cb_iterator<Buff, Traits>&) { return 0; }
428
429#endif // #if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR)
430
431}; // namespace cb_details
432
433/*!
434 \class circular_buffer
435 \brief Circular buffer - a STL compliant container.
436 \param T The type of the elements stored in the circular buffer.
437 \param Alloc The allocator type used for all internal memory management.
438 \author <a href="mailto:jano_gaspar@yahoo.com">Jan Gaspar</a>
439 \version 3.3
440 \date 2003
441
442 For more information how to use the circular buffer see the
443 <a href="../circular_buffer.html">documentation</a>.
444*/
445template <class T, class Alloc>
446class circular_buffer {
447
448// Requirements
449 BOOST_CLASS_REQUIRE(T, boost, AssignableConcept);
450
451public:
452// Basic types
453
454 //! The type of the elements stored in the circular buffer.
455 typedef typename Alloc::value_type value_type;
456
457 //! Pointer to the element.
458 typedef typename Alloc::pointer pointer;
459
460 //! Const pointer to the element.
461 typedef typename Alloc::const_pointer const_pointer;
462
463 //! Reference to the element.
464 typedef typename Alloc::reference reference;
465
466 //! Const reference to the element.
467 typedef typename Alloc::const_reference const_reference;
468
469 //! Size type.
470 typedef typename Alloc::size_type size_type;
471
472 //! Difference type.
473 typedef typename Alloc::difference_type difference_type;
474
475 //! The type of the allocator used in the circular buffer.
476 typedef Alloc allocator_type;
477
478 //! Return the allocator.
479 /*!
480 \return Allocator
481 */
482 allocator_type get_allocator() const { return m_alloc; }
483
484// Helper types
485
486 // Define a type that represents the "best" way to pass the value_type to a method.
487 typedef typename call_traits<value_type>::param_type param_value_type;
488
489// Iterators
490
491 //! Const (random access) iterator used to iterate through a circular buffer.
492 typedef cb_details::cb_iterator< circular_buffer<T, Alloc>, cb_details::cb_const_traits<Alloc> > const_iterator;
493
494 //! Iterator (random access) used to iterate through a circular buffer.
495 typedef cb_details::cb_iterator< circular_buffer<T, Alloc>, cb_details::cb_nonconst_traits<Alloc> > iterator;
496
497#if BOOST_VERSION >= 103100
498 //! Const iterator used to iterate backwards through a circular buffer.
499 typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
500
501 //! Iterator used to iterate backwards through a circular buffer.
502 typedef boost::reverse_iterator<iterator> reverse_iterator;
503#else
504 //! Const iterator used to iterate backwards through a circular buffer.
505 typedef typename reverse_iterator_generator<const_iterator>::type const_reverse_iterator;
506
507 //! Iterator used to iterate backwards through a circular buffer.
508 typedef typename reverse_iterator_generator<iterator>::type reverse_iterator;
509#endif
510
511private:
512// Member variables
513
514 //! The internal buffer used for storing elements in the circular buffer.
515 pointer m_buff;
516
517 //! The internal buffer's end (end of the storage space).
518 pointer m_end;
519
520 //! The virtual beginning of the circular buffer (the leftmost element).
521 pointer m_first;
522
523 //! The virtual end of the circular buffer (the rightmost element).
524 pointer m_last;
525
526 //! The number of items currently stored in the circular buffer.
527 size_type m_size;
528
529 //! The allocator.
530 allocator_type m_alloc;
531
532// Friends
533#if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
534 friend iterator;
535 friend const_iterator;
536#else
537 friend struct cb_details::cb_iterator< circular_buffer<T, Alloc>, cb_details::cb_const_traits<Alloc> >;
538 friend struct cb_details::cb_iterator< circular_buffer<T, Alloc>, cb_details::cb_nonconst_traits<Alloc> >;
539#endif
540
541public:
542// Element access
543
544 //! Return an iterator pointing to the beginning of the circular buffer.
545 iterator begin() { return iterator(this, empty() ? 0 : m_first); }
546
547 //! Return an iterator pointing to the end of the circular buffer.
548 iterator end() { return iterator(this, 0); }
549
550 //! Return a const iterator pointing to the beginning of the circular buffer.
551 const_iterator begin() const { return const_iterator(this, empty() ? 0 : m_first); }
552
553 //! Return a const iterator pointing to the end of the circular buffer.
554 const_iterator end() const { return const_iterator(this, 0); }
555
556 //! Return a reverse iterator pointing to the beginning of the reversed circular buffer.
557 reverse_iterator rbegin() { return reverse_iterator(end()); }
558
559 //! Return a reverse iterator pointing to the end of the reversed circular buffer.
560 reverse_iterator rend() { return reverse_iterator(begin()); }
561
562 //! Return a const reverse iterator pointing to the beginning of the reversed circular buffer.
563 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
564
565 //! Return a const reverse iterator pointing to the end of the reversed circular buffer.
566 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
567
568 //! Return the element at the <tt>index</tt> position.
569 reference operator [] (size_type index) { return *add(m_first, index); }
570
571 //! Return the element at the <tt>index</tt> position.
572 const_reference operator [] (size_type index) const { return *add(m_first, index); }
573
574 //! Return the element at the <tt>index</tt> position.
575 /*!
576 \throws std::out_of_range thrown when the <tt>index</tt> is invalid.
577 */
578 reference at(size_type index) {
579 check_position(index);
580 return (*this)[index];
581 }
582
583 //! Return the element at the <tt>index</tt> position.
584 /*!
585 \throws std::out_of_range thrown when the <tt>index</tt> is invalid.
586 */
587 const_reference at(size_type index) const {
588 check_position(index);
589 return (*this)[index];
590 }
591
592 //! Return the first (leftmost) element.
593 reference front() { return *m_first; }
594
595 //! Return the last (rightmost) element.
596 reference back() { return *((m_last == m_buff ? m_end : m_last) - 1); }
597
598 //! Return the first (leftmost) element.
599 const_reference front() const { return *m_first; }
600
601 //! Return the last (rightmost) element.
602 const_reference back() const { return *((m_last == m_buff ? m_end : m_last) - 1); }
603
604 //! Return pointer to data stored in the circular buffer as a continuous array of values.
605 /*!
606 This method can be usefull e.g. when passing the stored data into the legacy C API.
607 \post <tt>\&(*this)[0] \< \&(*this)[1] \< ... \< \&(*this).back()</tt>
608 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
609 */
610 pointer data() {
611 if (m_first < m_last || m_first == m_buff)
612 return m_first;
613 size_type constructed = 0;
614 pointer src = m_first;
615 pointer dest = m_buff;
616 BOOST_CB_TRY
617 for (pointer first = m_first; dest < src; src = first) {
618 for (size_type ii = 0; src < m_end; ++src, ++dest, ++ii) {
619 if (dest == first) {
620 first += ii;
621 break;
622 }
623 if (is_uninitialized(dest)) {
624 m_alloc.construct(dest, *src);
625 ++constructed;
626 } else {
627 std::swap(*dest, *src);
628 }
629 }
630 }
631 BOOST_CB_UNWIND(
632 for (dest = m_last; constructed > 0; ++dest, --constructed)
633 m_alloc.destroy(dest);
634 )
635 for (dest = m_buff + size(); dest < m_end; ++dest)
636 m_alloc.destroy(dest);
637 m_first = m_buff;
638 m_last = add(m_buff, size());
639 return m_buff;
640 }
641
642// Size and capacity
643
644 //! Return the number of elements currently stored in the circular buffer.
645 size_type size() const { return m_size; }
646
647 //! Return the largest possible size (or capacity) of the circular buffer.
648 size_type max_size() const { return m_alloc.max_size(); }
649
650 //! Is the circular buffer empty?
651 /*!
652 \return true if there are no elements stored in the circular buffer.
653 \return false otherwise.
654 */
655 bool empty() const { return size() == 0; }
656
657 //! Is the circular buffer full?
658 /*!
659 \return true if the number of elements stored in the circular buffer
660 equals the capacity of the circular buffer.
661 \return false otherwise.
662 */
663 bool full() const { return size() == capacity(); }
664
665 //! Return the capacity of the circular buffer.
666 size_type capacity() const { return m_end - m_buff; }
667
668 //! Change the capacity of the circular buffer.
669 /*!
670 \post <tt>(*this).capacity() == new_capacity</tt><br>
671 If the current number of elements stored in the circular
672 buffer is greater than the desired new capacity then the
673 first (leftmost) <tt>((*this).size() - new_capacity)</tt> elements
674 will be removed.
675 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
676 \throws Whatever T::T(const T&) throws.
677 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
678 */
679 void set_capacity(size_type new_capacity) {
680 if (new_capacity == capacity())
681 return;
682 pointer buff = allocate(new_capacity);
683 size_type new_size = new_capacity < size() ? new_capacity : size();
684 BOOST_CB_TRY
685 std::uninitialized_copy(end() - new_size, end(), buff);
686 BOOST_CB_UNWIND(deallocate(buff, new_capacity))
687 destroy();
688 m_size = new_size;
689 m_buff = m_first = buff;
690 m_end = m_buff + new_capacity;
691 m_last = add(m_buff, size());
692 }
693
694 //! Change the size of the circular buffer.
695 /*!
696 \post <tt>(*this).size() == new_size</tt><br>
697 If the new size is greater than the current size, the rest
698 of the circular buffer is filled with copies of <tt>item</tt>.
699 In case the resulting size exceeds the current capacity
700 the capacity is set to <tt>new_size</tt>.
701 If the new size is lower than the current size, the first
702 (leftmost) <tt>((*this).size() - new_size)</tt> elements will be removed.
703 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
704 \throws Whatever T::T(const T&) throws.
705 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
706 */
707 void resize(size_type new_size, param_value_type item = T()) {
708 if (new_size > size()) {
709 if (new_size > capacity())
710 set_capacity(new_size);
711 insert(end(), new_size - size(), item);
712 } else {
713 erase(begin(), end() - new_size);
714 }
715 }
716
717// Construction/Destruction
718
719 //! Create an empty circular buffer with a given capacity.
720 /*!
721 \post <tt>(*this).capacity() == capacity \&\& (*this).size == 0</tt>
722 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
723 */
724 explicit circular_buffer(
725 size_type capacity,
726 const allocator_type& a = allocator_type())
727 : m_size(0), m_alloc(a) {
728 m_first = m_last = m_buff = allocate(capacity);
729 m_end = m_buff + capacity;
730 }
731
732 //! Create a full circular buffer with a given capacity and filled with copies of <tt>item</tt>.
733 /*!
734 \post <tt>(*this).size() == capacity \&\& (*this)[0] == (*this)[1] == ... == (*this).back() == item</tt>
735 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
736 \throws Whatever T::T(const T&) throws.
737 */
738 circular_buffer(
739 size_type capacity,
740 param_value_type item,
741 const allocator_type& a = allocator_type())
742 : m_size(capacity), m_alloc(a) {
743 m_first = m_last = m_buff = allocate(capacity);
744 m_end = m_buff + capacity;
745 BOOST_CB_TRY
746 std::uninitialized_fill_n(m_buff, size(), item);
747 BOOST_CB_UNWIND(deallocate(m_buff, capacity))
748 }
749
750 //! Copy constructor.
751 /*!
752 \post <tt>*this == cb</tt>
753 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
754 \throws Whatever T::T(const T&) throws.
755 */
756 circular_buffer(const circular_buffer<T, Alloc>& cb)
757 : m_size(cb.size()), m_alloc(cb.get_allocator()) {
758 m_first = m_last = m_buff = allocate(cb.capacity());
759 BOOST_CB_TRY
760 m_end = std::uninitialized_copy(cb.begin(), cb.end(), m_buff);
761 BOOST_CB_UNWIND(deallocate(m_buff, cb.capacity()))
762 }
763
764 //! Create a circular buffer with a copy of a range.
765 /*!
766 \post <tt>(*this).capacity() == capacity</tt><br>
767 If the number of items to copy from the range
768 <tt>[first, last)</tt> is greater than the specified
769 <tt>capacity</tt> then only elements from the range
770 <tt>[last - capacity, last)</tt> will be copied.
771 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
772 \throws Whatever T::T(const T&) throws.
773 */
774 template <class InputIterator>
775 circular_buffer(
776 size_type capacity,
777 InputIterator first,
778 InputIterator last,
779 const allocator_type& a = allocator_type())
780 : m_alloc(a) {
781 m_first = m_buff = allocate(capacity);
782 m_end = m_buff + capacity;
783 size_type diff = std::distance(first, last);
784 if (diff > capacity) {
785 std::advance(first, diff - capacity);
786 m_size = capacity;
787 m_last = m_buff;
788 } else {
789 m_size = diff;
790 if (diff == capacity)
791 m_last = m_buff;
792 else
793 m_last = m_buff + size();
794 }
795 BOOST_CB_TRY
796 std::uninitialized_copy(first, last, m_buff);
797 BOOST_CB_UNWIND(deallocate(m_buff, capacity))
798 }
799
800 //! Destructor.
801 ~circular_buffer() { destroy(); }
802
803private:
804// Helper functors
805
806 // Functor for assigning n items.
807 struct assign_n {
808 size_type m_n;
809 param_value_type m_item;
810 assign_n(size_type n, param_value_type item) : m_n(n), m_item(item) {}
811 void operator () (pointer p) const {
812 std::uninitialized_fill_n(p, m_n, m_item);
813 }
814 private:
815 assign_n& operator = (const assign_n&); // do not generate
816 };
817
818 // Functor for assigning range of items.
819 template <class InputIterator>
820 struct assign_range {
821 InputIterator m_first;
822 InputIterator m_last;
823 assign_range(InputIterator first, InputIterator last) : m_first(first), m_last(last) {}
824 void operator() (pointer p) const {
825 std::uninitialized_copy(m_first, m_last, p);
826 }
827 };
828
829public:
830// Assign methods
831
832 //! Assignment operator.
833 /*!
834 \post <tt>*this == cb</tt>
835 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
836 \throws Whatever T::T(const T&) throws.
837 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
838 */
839 circular_buffer<T, Alloc>& operator = (const circular_buffer<T, Alloc>& cb) {
840 if (this == &cb)
841 return *this;
842 pointer buff = allocate(cb.capacity());
843 BOOST_CB_TRY
844 pointer last = std::uninitialized_copy(cb.begin(), cb.end(), buff);
845 destroy();
846 m_size = cb.size();
847 m_first = m_buff = buff;
848 m_end = m_buff + cb.capacity();
849 m_last = full() ? m_buff : last;
850 BOOST_CB_UNWIND(deallocate(buff, cb.capacity()))
851 return *this;
852 }
853
854 //! Assign <tt>n</tt> items into the circular buffer.
855 /*!
856 \post <tt>(*this).size() == n \&\&
857 (*this)[0] == (*this)[1] == ... == (*this).back() == item</tt><br>
858 If the number of items to be assigned exceeds
859 the capacity of the circular buffer the capacity
860 is increased to <tt>n</tt> otherwise it stays unchanged.
861 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
862 \throws Whatever T::T(const T&) throws.
863 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
864 */
865 void assign(size_type n, param_value_type item) { do_assign(n, assign_n(n, item)); }
866
867 //! Assign a copy of range.
868 /*!
869 \post <tt>(*this).size() == std::distance(first, last)</tt><br>
870 If the number of items to be assigned exceeds
871 the capacity of the circular buffer the capacity
872 is set to that number otherwise is stays unchanged.
873 \throws "An allocation error" if memory is exhausted (<tt>std::bad_alloc</tt> if standard allocator is used).
874 \throws Whatever T::T(const T&) throws.
875 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
876 */
877 template <class InputIterator>
878 void assign(InputIterator first, InputIterator last) {
879 assign(first, last, cb_details::cb_iterator_category_traits<InputIterator>::tag());
880 }
881
882 //! Swap the contents of two circular buffers.
883 /*!
884 \post <tt>this</tt> contains elements of <tt>cb</tt> and vice versa.
885 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
886 */
887 void swap(circular_buffer& cb) {
888 std::swap(m_alloc, cb.m_alloc); // in general this is not necessary,
889 // because allocators should not have state
890 std::swap(m_buff, cb.m_buff);
891 std::swap(m_end, cb.m_end);
892 std::swap(m_first, cb.m_first);
893 std::swap(m_last, cb.m_last);
894 std::swap(m_size, cb.m_size);
895 }
896
897// push and pop
898
899 //! Insert a new element at the end.
900 /*!
901 \post <tt>(*this).back() == item</tt><br>
902 If the circular buffer is full, the first (leftmost) element will be removed.
903 \throws Whatever T::T(const T&) throws.
904 \throws Whatever T::operator = (const T&) throws.
905 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
906 */
907 void push_back(param_value_type item) {
908 if (full()) {
909 if (empty())
910 return;
911 *m_last = item;
912 increment(m_first);
913 m_last = m_first;
914 } else {
915 m_alloc.construct(m_last, item);
916 increment(m_last);
917 ++m_size;
918 }
919 }
920
921 //! Insert a new element with the default value at the end.
922 /*!
923 \post <tt>(*this).back() == value_type()</tt><br>
924 If the circular buffer is full, the first (leftmost) element will be removed.
925 \throws Whatever T::T(const T&) throws.
926 \throws Whatever T::operator = (const T&) throws.
927 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
928 */
929 void push_back() { push_back(value_type()); }
930
931 //! Insert a new element at the start.
932 /*!
933 \post <tt>(*this).front() == item</tt><br>
934 If the circular buffer is full, the last (rightmost) element will be removed.
935 \throws Whatever T::T(const T&) throws.
936 \throws Whatever T::operator = (const T&) throws.
937 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
938 */
939 void push_front(param_value_type item) {
940 BOOST_CB_TRY
941 if (full()) {
942 if (empty())
943 return;
944 decrement(m_first);
945 *m_first = item;
946 m_last = m_first;
947 } else {
948 decrement(m_first);
949 m_alloc.construct(m_first, item);
950 ++m_size;
951 }
952 BOOST_CB_UNWIND(increment(m_first))
953 }
954
955 //! Insert a new element with the default value at the start.
956 /*!
957 \post <tt>(*this).front() == value_type()</tt><br>
958 If the circular buffer is full, the last (rightmost) element will be removed.
959 \throws Whatever T::T(const T&) throws.
960 \throws Whatever T::operator = (const T&) throws.
961 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
962 */
963 void push_front() { push_front(value_type()); }
964
965 //! Remove the last (rightmost) element.
966 /*!
967 \pre <tt>iterator it = (*this).end()</tt>
968 \post <tt>(*this).end() != it</tt>
969 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
970 */
971 void pop_back() {
972 decrement(m_last);
973 m_alloc.destroy(m_last);
974 --m_size;
975 }
976
977 //! Remove the first (leftmost) element.
978 /*!
979 \pre <tt>iterator it = (*this).begin()</tt>
980 \post <tt>(*this).begin() != it</tt>
981 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
982 */
983 void pop_front() {
984 m_alloc.destroy(m_first);
985 increment(m_first);
986 --m_size;
987 }
988
989private:
990// Helper wrappers
991
992 // Iterator dereference wrapper.
993 template <class InputIterator>
994 struct item_wrapper {
995 mutable InputIterator m_it;
996 item_wrapper(InputIterator it) : m_it(it) {}
997 operator const_reference () const { return *m_it++; }
998 };
999
1000public:
1001// Insert
1002
1003 //! Insert the <tt>item</tt> before the given position.
1004 /*!
1005 \post The <tt>item</tt> will be inserted at the position <tt>pos</tt>.<br>
1006 If the circular buffer is full, the first (leftmost) element will be removed.
1007 \return iterator to the inserted element.
1008 \throws Whatever T::T(const T&) throws.
1009 \throws Whatever T::operator = (const T&) throws.
1010 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1011 */
1012 iterator insert(iterator pos, param_value_type item) {
1013 if (full() && pos == begin())
1014 return begin();
1015 if (pos.m_it == 0) {
1016 if (full())
1017 *m_last = item;
1018 else
1019 m_alloc.construct(m_last, item);
1020 pos.m_it = m_last;
1021 } else {
1022 pointer src = m_last;
1023 pointer dest = m_last;
1024 BOOST_CB_TRY
1025 while (src != pos.m_it) {
1026 decrement(src);
1027 create_copy(dest, *src);
1028 decrement(dest);
1029 }
1030 *pos = item;
1031 BOOST_CB_UNWIND(
1032 for (pointer it = m_last; it != dest; decrement(it))
1033 destroy_copy(it);
1034 )
1035 }
1036 increment(m_last);
1037 if (full())
1038 increment(m_first);
1039 else
1040 ++m_size;
1041 return iterator(this, pos.m_it);
1042 }
1043
1044 //! Insert a new element with the default value before the given position.
1045 /*!
1046 \post <tt>value_type()</tt> will be inserted at the position <tt>pos</tt>.<br>
1047 If the circular buffer is full, the first (leftmost) element will be removed.
1048 \return iterator to the inserted element.
1049 \throws Whatever T::T(const T&) throws.
1050 \throws Whatever T::operator = (const T&) throws.
1051 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1052 */
1053 iterator insert(iterator pos) { return insert(pos, value_type()); }
1054
1055 //! Insert <tt>n</tt> copies of the item before the given position.
1056 /*!
1057 \post This operation preserves the capacity of the circular buffer.
1058 If the insertion would result in exceeding the capacity
1059 of the circular buffer then the necessary number of elements
1060 from the beginning (left) of the circular buffer will be removed
1061 or not all <tt>n</tt> elements will be inserted or both.<tt><br>
1062 Example:<br>
1063 original circular buffer |1|2|3|4| | | - capacity: 6, size: 4<br>
1064 position ---------------------^<br>
1065 insert(position, (size_t)5, 6);<br>
1066 (If the operation won't preserve capacity, the buffer
1067 would look like this |1|2|6|6|6|6|6|3|4|)<br>
1068 RESULTING circular buffer |6|6|6|6|3|4| - capacity: 6, size: 6</tt>
1069 \throws Whatever T::T(const T&) throws.
1070 \throws Whatever T::operator = (const T&) throws.
1071 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1072 */
1073 void insert(iterator pos, size_type n, param_value_type item) {
1074 if (n == 0)
1075 return;
1076 size_type copy = capacity() - (end() - pos);
1077 if (copy == 0)
1078 return;
1079 if (n > copy)
1080 n = copy;
1081 insert_n_item(pos, n, item);
1082 }
1083
1084 //! Insert the range <tt>[first, last)</tt> before the given position.
1085 /*!
1086 \post This operation preserves the capacity of the circular buffer.
1087 If the insertion would result in exceeding the capacity
1088 of the circular buffer then the necessary number of elements
1089 from the beginning (left) of the circular buffer will be removed
1090 or not the whole range will be inserted or both.
1091 In case the whole range cannot be inserted it will be inserted just
1092 some elements from the end (right) of the range (see the example).<tt><br>
1093 Example:<br>
1094 array to insert: int array[] = { 5, 6, 7, 8, 9 };<br>
1095 original circular buffer |1|2|3|4| | | - capacity: 6, size: 4<br>
1096 position ---------------------^<br>
1097 insert(position, array, array + 5);<br>
1098 (If the operation won't preserve capacity, the buffer
1099 would look like this |1|2|5|6|7|8|9|3|4|)<br>
1100 RESULTING circular buffer |6|7|8|9|3|4| - capacity: 6, size: 6</tt>
1101 \throws Whatever T::T(const T&) throws.
1102 \throws Whatever T::operator = (const T&) throws.
1103 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1104 */
1105 template <class InputIterator>
1106 void insert(iterator pos, InputIterator first, InputIterator last) {
1107 insert(pos, first, last, cb_details::cb_iterator_category_traits<InputIterator>::tag());
1108 }
1109
1110 //! Insert an <tt>item</tt> before the given position.
1111 /*!
1112 \post The <tt>item</tt> will be inserted at the position <tt>pos</tt>.<br>
1113 If the circular buffer is full, the last element (rightmost) will be removed.
1114 \return iterator to the inserted element.
1115 \throws Whatever T::T(const T&) throws.
1116 \throws Whatever T::operator = (const T&) throws.
1117 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1118 */
1119 iterator rinsert(iterator pos, param_value_type item) {
1120 if (full() && pos == end())
1121 return end();
1122 if (pos == begin()) {
1123 BOOST_CB_TRY
1124 decrement(m_first);
1125 if (full())
1126 *m_first = item;
1127 else
1128 m_alloc.construct(m_first, item);
1129 BOOST_CB_UNWIND(increment(m_first))
1130 } else {
1131 pointer src = m_first;
1132 pointer dest = m_first;
1133 pointer it = get_valid_pointer(pos.m_it);
1134 decrement(dest);
1135 BOOST_CB_TRY
1136 while (src != it) {
1137 create_copy(dest, *src);
1138 increment(src);
1139 increment(dest);
1140 }
1141 decrement(m_first);
1142 *--pos = item;
1143 BOOST_CB_UNWIND(
1144 it = m_first;
1145 for (increment(m_first); it != dest; increment(it))
1146 destroy_copy(it);
1147 )
1148 }
1149 if (full())
1150 decrement(m_last);
1151 else
1152 ++m_size;
1153 return iterator(this, pos.m_it);
1154 }
1155
1156 //! Insert a new element with the default value before the given position.
1157 /*!
1158 \post <tt>value_type()</tt> will be inserted at the position <tt>pos</tt>.<br>
1159 If the circular buffer is full, the last (rightmost) element will be removed.
1160 \return iterator to the inserted element.
1161 \throws Whatever T::T(const T&) throws.
1162 \throws Whatever T::operator = (const T&) throws.
1163 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1164 */
1165 iterator rinsert(iterator pos) { return rinsert(pos, value_type()); }
1166
1167 //! Insert <tt>n</tt> copies of the item before the given position.
1168 /*!
1169 \post This operation preserves the capacity of the circular buffer.
1170 If the insertion would result in exceeding the capacity
1171 of the circular buffer then the necessary number of elements
1172 from the end (right) of the circular buffer will be removed
1173 or not all <tt>n</tt> elements will be inserted or both.<tt><br>
1174 Example:<br>
1175 original circular buffer |1|2|3|4| | | - capacity: 6, size: 4<br>
1176 position ---------------------^<br>
1177 insert(position, (size_t)5, 6);<br>
1178 (If the operation won't preserve capacity, the buffer
1179 would look like this |1|2|6|6|6|6|6|3|4|)<br>
1180 RESULTING circular buffer |1|2|6|6|6|6| - capacity: 6, size: 6</tt>
1181 \throws Whatever T::T(const T&) throws.
1182 \throws Whatever T::operator = (const T&) throws.
1183 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1184 */
1185 void rinsert(iterator pos, size_type n, param_value_type item) { rinsert_n_item(pos, n, item); }
1186
1187 //! Insert the range <tt>[first, last)</tt> before the given position.
1188 /*!
1189 \post This operation preserves the capacity of the circular buffer.
1190 If the insertion would result in exceeding the capacity
1191 of the circular buffer then the necessary number of elements
1192 from the end (right) of the circular buffer will be removed
1193 or not the whole range will be inserted or both.
1194 In case the whole range cannot be inserted it will be inserted just
1195 some elements from the beginning (left) of the range (see the example).<tt><br>
1196 Example:<br>
1197 array to insert: int array[] = { 5, 6, 7, 8, 9 };<br>
1198 original circular buffer |1|2|3|4| | | - capacity: 6, size: 4<br>
1199 position ---------------------^<br>
1200 insert(position, array, array + 5);<br>
1201 (If the operation won't preserve capacity, the buffer
1202 would look like this |1|2|5|6|7|8|9|3|4|)<br>
1203 RESULTING circular buffer |1|2|5|6|7|8| - capacity: 6, size: 6</tt>
1204 \throws Whatever T::T(const T&) throws.
1205 \throws Whatever T::operator = (const T&) throws.
1206 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1207 */
1208 template <class InputIterator>
1209 void rinsert(iterator pos, InputIterator first, InputIterator last) {
1210 rinsert(pos, first, last, cb_details::cb_iterator_category_traits<InputIterator>::tag());
1211 }
1212
1213// Erase
1214
1215 //! Erase the element at the given position.
1216 /*!
1217 \pre <tt>size_type old_size = (*this).size()</tt>
1218 \post <tt>(*this).size() == old_size - 1</tt><br>
1219 Removes an element at the position <tt>pos</tt>.
1220 \return iterator to the first element remaining beyond the removed
1221 element or <tt>(*this).end()</tt> if no such element exists.
1222 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1223 */
1224 iterator erase(iterator pos) {
1225 std::copy(pos + 1, end(), pos);
1226 decrement(m_last);
1227 m_alloc.destroy(m_last);
1228 --m_size;
1229 return iterator(this, pos.m_it == m_last ? 0 : pos.m_it);
1230 }
1231
1232 //! Erase the range <tt>[first, last)</tt>.
1233 /*!
1234 \pre <tt>size_type old_size = (*this).size()</tt>
1235 \post <tt>(*this).size() == old_size - std::distance(first, last)</tt><br>
1236 Removes the elements from the range <tt>[first, last)</tt>.
1237 \return iterator to the first element remaining beyond the removed
1238 element or <tt>(*this).end()</tt> if no such element exists.
1239 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1240 */
1241 iterator erase(iterator first, iterator last) {
1242 if (first != last)
1243 std::copy(last, end(), first);
1244 difference_type diff = last - first;
1245 m_size -= diff;
1246 for (; diff > 0; --diff) {
1247 decrement(m_last);
1248 m_alloc.destroy(m_last);
1249 }
1250 return iterator(this, first.m_it == m_last ? 0 : first.m_it);
1251 }
1252
1253 //! Erase all the stored elements.
1254 /*!
1255 \post (*this).size() == 0
1256 \note For iterator invalidation see the <a href="../circular_buffer.html#invalidation">documentation</a>.
1257 */
1258 void clear() {
1259 destroy_content();
1260 m_first = m_last = m_buff;
1261 m_size = 0;
1262 }
1263
1264private:
1265// Helper methods
1266
1267 //! Check if the <tt>index</tt> is valid.
1268 void check_position(size_type index) const {
1269 if (index >= size())
1270 throw_exception(std::out_of_range("circular_buffer"));
1271 }
1272
1273 //! Increment the pointer.
1274 template <class Pointer0>
1275 void increment(Pointer0& p) const {
1276 if (++p == m_end)
1277 p = m_buff;
1278 }
1279
1280 //! Decrement the pointer.
1281 template <class Pointer0>
1282 void decrement(Pointer0& p) const {
1283 if (p == m_buff)
1284 p = m_end;
1285 --p;
1286 }
1287
1288 //! Add <tt>n</tt> to the pointer.
1289 template <class Pointer0>
1290 Pointer0 add(Pointer0 p, difference_type n) const {
1291 return p + (n < (m_end - p) ? n : n - capacity());
1292 }
1293
1294 //! Subtract <tt>n</tt> from the pointer.
1295 template <class Pointer0>
1296 Pointer0 sub(Pointer0 p, difference_type n) const {
1297 return p - (n > (p - m_buff) ? n - capacity() : n);
1298 }
1299
1300 //! Return valid pointer.
1301 pointer get_valid_pointer(pointer p) const { return p == 0 ? m_last : p; }
1302
1303 //! Does the pointer point to the uninitialized memory?
1304 bool is_uninitialized(pointer p) const { return p >= m_last && (m_first < m_last || p < m_first); }
1305
1306 //! Create a copy of the <tt>item</tt> at the given position.
1307 /*!
1308 The copy is created either at uninitialized memory
1309 or replaces the old item.
1310 */
1311 void create_copy(pointer pos, param_value_type item) {
1312 if (is_uninitialized(pos))
1313 m_alloc.construct(pos, item);
1314 else
1315 *pos = item;
1316 }
1317
1318 //! Try to recover when the create_copy fails.
1319 void destroy_copy(pointer pos) {
1320 if (is_uninitialized(pos))
1321 m_alloc.destroy(pos);
1322 // the assignment cannot be rolled back
1323 }
1324
1325 //! Allocate memory.
1326 pointer allocate(size_type n) {
1327 if (n > max_size())
1328 throw_exception(std::length_error("circular_buffer"));
1329 return (n == 0) ? 0 : m_alloc.allocate(n, 0);
1330 }
1331
1332 //! Deallocate memory.
1333 void deallocate(pointer p, size_type n) {
1334 if (p != 0)
1335 m_alloc.deallocate(p, n);
1336 }
1337
1338 //! Destroy the content of the circular buffer.
1339 void destroy_content() {
1340 iterator last = end();
1341 for (iterator it = begin(); it != last; ++it)
1342 m_alloc.destroy(it.m_it);
1343 }
1344
1345 //! Destroy content and frees allocated memory.
1346 void destroy() {
1347 destroy_content();
1348 deallocate(m_buff, capacity());
1349 }
1350
1351 //! Helper assign method.
1352 template <class InputIterator>
1353 void assign(InputIterator n, InputIterator item, cb_details::cb_int_iterator_tag) {
1354 assign((size_type)n, item);
1355 }
1356
1357 //! Helper assign method.
1358 template <class InputIterator>
1359 void assign(InputIterator first, InputIterator last, std::input_iterator_tag) {
1360 do_assign(std::distance(first, last), assign_range<InputIterator>(first, last));
1361 }
1362
1363 //! Helper assign method.
1364 template <class Functor>
1365 void do_assign(size_type n, const Functor& fnc) {
1366 if (n > capacity()) {
1367 pointer buff = allocate(n);
1368 BOOST_CB_TRY
1369 fnc(buff);
1370 BOOST_CB_UNWIND(deallocate(buff, n))
1371 destroy();
1372 m_buff = buff;
1373 m_end = m_buff + n;
1374 } else {
1375 destroy_content();
1376 BOOST_CB_TRY
1377 fnc(m_buff);
1378 BOOST_CB_UNWIND(m_size = 0;)
1379 }
1380 m_size = n;
1381 m_first = m_buff;
1382 m_last = add(m_buff, size());
1383 }
1384
1385 //! Helper insert method.
1386 template <class InputIterator>
1387 void insert(iterator pos, InputIterator n, InputIterator item, cb_details::cb_int_iterator_tag) {
1388 insert(pos, (size_type)n, item);
1389 }
1390
1391 //! Helper insert method.
1392 template <class InputIterator>
1393 void insert(iterator pos, InputIterator first, InputIterator last, std::input_iterator_tag) {
1394 difference_type n = std::distance(first, last);
1395 if (n == 0)
1396 return;
1397 difference_type copy = capacity() - (end() - pos);
1398 if (copy == 0)
1399 return;
1400 if (n > copy) {
1401 std::advance(first, n - copy);
1402 n = copy;
1403 }
1404 insert_n_item(pos, n, item_wrapper<InputIterator>(first));
1405 }
1406
1407 //! Helper insert method.
1408 template <class Item>
1409 void insert_n_item(iterator pos, size_type n, const Item& item) {
1410 size_type construct = capacity() - size();
1411 if (construct > n)
1412 construct = n;
1413 if (pos.m_it == 0) {
1414 size_type ii = 0;
1415 pointer p = m_last;
1416 BOOST_CB_TRY
1417 for (; ii < construct; ++ii, increment(p))
1418 m_alloc.construct(p, item);
1419 for (;ii < n; ++ii, increment(p))
1420 *p = item;
1421 BOOST_CB_UNWIND(
1422 size_type unwind = ii < construct ? ii : construct;
1423 for (ii = 0, p = m_last; ii < unwind; ++ii, increment(p))
1424 m_alloc.destroy(p);
1425 )
1426 } else {
1427 pointer src = m_last;
1428 pointer dest = add(m_last, n - 1);
1429 pointer p = pos.m_it;
1430 size_type ii = 0;
1431 BOOST_CB_TRY
1432 while (src != p) {
1433 decrement(src);
1434 create_copy(dest, *src);
1435 decrement(dest);
1436 }
1437 for (; ii < n; ++ii, increment(p))
1438 create_copy(p, item);
1439 BOOST_CB_UNWIND(
1440 for (p = add(m_last, n - 1); p != dest; decrement(p))
1441 destroy_copy(p);
1442 for (n = 0, p = pos.m_it; n < ii; ++n, increment(p))
1443 destroy_copy(p);
1444 )
1445 }
1446 m_last = add(m_last, n);
1447 m_first = add(m_first, n - construct);
1448 m_size += construct;
1449 }
1450
1451 //! Helper rinsert method.
1452 template <class InputIterator>
1453 void rinsert(iterator pos, InputIterator n, InputIterator item, cb_details::cb_int_iterator_tag) {
1454 rinsert(pos, (size_type)n, item);
1455 }
1456
1457 //! Helper rinsert method.
1458 template <class InputIterator>
1459 void rinsert(iterator pos, InputIterator first, InputIterator last, std::input_iterator_tag) {
1460 rinsert_n_item(pos, std::distance(first, last), item_wrapper<InputIterator>(first));
1461 }
1462
1463 //! Helper rinsert method.
1464 template <class Item>
1465 void rinsert_n_item(iterator pos, size_type n, const Item& item) {
1466 if (n == 0)
1467 return;
1468 size_type copy = capacity() - (pos - begin());
1469 if (copy == 0)
1470 return;
1471 if (n > copy)
1472 n = copy;
1473 size_type construct = capacity() - size();
1474 if (construct > n)
1475 construct = n;
1476 if (pos == begin()) {
1477 pointer p = sub(get_valid_pointer(pos.m_it), n);
1478 size_type ii = n;
1479 BOOST_CB_TRY
1480 for (;ii > construct; --ii, increment(p))
1481 *p = item;
1482 for (; ii > 0; --ii, increment(p))
1483 m_alloc.construct(p, item);
1484 BOOST_CB_UNWIND(
1485 size_type unwind = ii < construct ? construct - ii : 0;
1486 p = sub(get_valid_pointer(pos.m_it), construct);
1487 for (ii = 0; ii < unwind; ++ii, increment(p))
1488 m_alloc.destroy(p);
1489 )
1490 } else {
1491 pointer src = m_first;
1492 pointer dest = sub(m_first, n);
1493 pointer p = get_valid_pointer(pos.m_it);
1494 size_type ii = 0;
1495 BOOST_CB_TRY
1496 while (src != p) {
1497 create_copy(dest, *src);
1498 increment(src);
1499 increment(dest);
1500 }
1501 p = sub(p, n);
1502 for (; ii < n; ++ii, increment(p))
1503 create_copy(p, item);
1504 BOOST_CB_UNWIND(
1505 for (p = sub(m_first, n); p != dest; increment(p))
1506 destroy_copy(p);
1507 p = sub(get_valid_pointer(pos.m_it), n);
1508 for (n = 0; n < ii; ++n, increment(p))
1509 destroy_copy(p);
1510 )
1511 }
1512 m_first = sub(m_first, n);
1513 m_last = sub(m_last, n - construct);
1514 m_size += construct;
1515 }
1516};
1517
1518// Non-member functions
1519
1520//! Test two circular buffers for equality.
1521template <class T, class Alloc>
1522inline bool operator == (const circular_buffer<T, Alloc>& lhs,
1523 const circular_buffer<T, Alloc>& rhs) {
1524 return lhs.size() == rhs.size() &&
1525 std::equal(lhs.begin(), lhs.end(), rhs.begin());
1526}
1527
1528//! Lexicographical comparison.
1529template <class T, class Alloc>
1530inline bool operator < (const circular_buffer<T, Alloc>& lhs,
1531 const circular_buffer<T, Alloc>& rhs) {
1532 return std::lexicographical_compare(
1533 lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
1534}
1535
1536#if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
1537
1538//! Test two circular buffers for non-equality.
1539template <class T, class Alloc>
1540inline bool operator != (const circular_buffer<T, Alloc>& lhs,
1541 const circular_buffer<T, Alloc>& rhs) {
1542 return !(lhs == rhs);
1543}
1544
1545//! Lexicographical comparison.
1546template <class T, class Alloc>
1547inline bool operator > (const circular_buffer<T, Alloc>& lhs,
1548 const circular_buffer<T, Alloc>& rhs) {
1549 return rhs < lhs;
1550}
1551
1552//! Lexicographical comparison.
1553template <class T, class Alloc>
1554inline bool operator <= (const circular_buffer<T, Alloc>& lhs,
1555 const circular_buffer<T, Alloc>& rhs) {
1556 return !(rhs < lhs);
1557}
1558
1559//! Lexicographical comparison.
1560template <class T, class Alloc>
1561inline bool operator >= (const circular_buffer<T, Alloc>& lhs,
1562 const circular_buffer<T, Alloc>& rhs) {
1563 return !(lhs < rhs);
1564}
1565
1566//! Swap the contents of two circular buffers.
1567template <class T, class Alloc>
1568inline void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs) {
1569 lhs.swap(rhs);
1570}
1571
1572#endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
1573
1574#undef BOOST_CB_UNWIND
1575#undef BOOST_CB_TRY
1576
1577} // namespace boost
1578
1579#endif // #if !defined(BOOST_CIRCULAR_BUFFER_BASE_HPP)

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status