blob: d5b8f0a3ee2c2c2e2e934dbac7aa3fc0b0db6f3f [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2#ifndef _LIBCPP_SPLIT_BUFFER
3#define _LIBCPP_SPLIT_BUFFER
4
5#include <__config>
6#include <type_traits>
7#include <algorithm>
8
9#pragma GCC system_header
10
11_LIBCPP_BEGIN_NAMESPACE_STD
12
13template <bool>
14class __split_buffer_common
15{
16protected:
17 void __throw_length_error() const;
18 void __throw_out_of_range() const;
19};
20
Howard Hinnantf8ce4592010-07-07 19:14:52 +000021template <class _Tp, class _Allocator = allocator<_Tp> >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000022struct __split_buffer
23 : private __split_buffer_common<true>
24{
25private:
26 __split_buffer(const __split_buffer&);
27 __split_buffer& operator=(const __split_buffer&);
28public:
Howard Hinnant324bb032010-08-22 00:02:43 +000029 typedef _Tp value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000030 typedef _Allocator allocator_type;
31 typedef typename remove_reference<allocator_type>::type __alloc_rr;
32 typedef allocator_traits<__alloc_rr> __alloc_traits;
33 typedef value_type& reference;
34 typedef const value_type& const_reference;
35 typedef typename __alloc_traits::size_type size_type;
36 typedef typename __alloc_traits::difference_type difference_type;
37 typedef typename __alloc_traits::pointer pointer;
38 typedef typename __alloc_traits::const_pointer const_pointer;
39 typedef pointer iterator;
40 typedef const_pointer const_iterator;
41
42 pointer __first_;
43 pointer __begin_;
44 pointer __end_;
45 __compressed_pair<pointer, allocator_type> __end_cap_;
46
47 typedef typename add_lvalue_reference<allocator_type>::type __alloc_ref;
48 typedef typename add_lvalue_reference<allocator_type>::type __alloc_const_ref;
49
Howard Hinnant0a612b02011-06-02 20:00:14 +000050 _LIBCPP_INLINE_VISIBILITY __alloc_rr& __alloc() _NOEXCEPT {return __end_cap_.second();}
51 _LIBCPP_INLINE_VISIBILITY const __alloc_rr& __alloc() const _NOEXCEPT {return __end_cap_.second();}
52 _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() _NOEXCEPT {return __end_cap_.first();}
53 _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const _NOEXCEPT {return __end_cap_.first();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000054
Howard Hinnant009b2c42011-06-03 15:16:49 +000055 __split_buffer()
56 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000057 explicit __split_buffer(__alloc_rr& __a);
58 explicit __split_buffer(const __alloc_rr& __a);
59 __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a);
60 ~__split_buffer();
61
Howard Hinnant73d21a42010-09-04 23:28:19 +000062#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant0a612b02011-06-02 20:00:14 +000063 __split_buffer(__split_buffer&& __c)
64 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000065 __split_buffer(__split_buffer&& __c, const __alloc_rr& __a);
Howard Hinnant0a612b02011-06-02 20:00:14 +000066 __split_buffer& operator=(__split_buffer&& __c)
67 _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
68 is_nothrow_move_assignable<allocator_type>::value) ||
69 !__alloc_traits::propagate_on_container_move_assignment::value);
Howard Hinnant73d21a42010-09-04 23:28:19 +000070#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000071
Howard Hinnant0a612b02011-06-02 20:00:14 +000072 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __begin_;}
73 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __begin_;}
74 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __end_;}
75 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __end_;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000076
Howard Hinnant0a612b02011-06-02 20:00:14 +000077 _LIBCPP_INLINE_VISIBILITY
78 void clear() _NOEXCEPT
79 {__destruct_at_end(__begin_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000080 _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(__end_ - __begin_);}
81 _LIBCPP_INLINE_VISIBILITY bool empty() const {return __end_ == __begin_;}
82 _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __first_);}
83 _LIBCPP_INLINE_VISIBILITY size_type __front_spare() const {return static_cast<size_type>(__begin_ - __first_);}
84 _LIBCPP_INLINE_VISIBILITY size_type __back_spare() const {return static_cast<size_type>(__end_cap() - __end_);}
85
86 _LIBCPP_INLINE_VISIBILITY reference front() {return *__begin_;}
87 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *__begin_;}
88 _LIBCPP_INLINE_VISIBILITY reference back() {return *(__end_ - 1);}
89 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(__end_ - 1);}
90
91 void reserve(size_type __n);
Howard Hinnant0a612b02011-06-02 20:00:14 +000092 void shrink_to_fit() _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000093 void push_front(const_reference __x);
94 void push_back(const_reference __x);
Michael J. Spencer626916f2010-12-10 19:47:54 +000095#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000096 void push_front(value_type&& __x);
97 void push_back(value_type&& __x);
Michael J. Spencer626916f2010-12-10 19:47:54 +000098#if !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000099 template <class... _Args>
100 void emplace_back(_Args&&... __args);
Michael J. Spencer626916f2010-12-10 19:47:54 +0000101#endif // !defined(_LIBCPP_HAS_NO_VARIADICS)
102#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000103
104 _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);}
105 _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);}
106
107 void __construct_at_end(size_type __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000108 void __construct_at_end(size_type __n, const_reference __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000109 template <class _InputIter>
110 typename enable_if
111 <
112 __is_input_iterator<_InputIter>::value &&
113 !__is_forward_iterator<_InputIter>::value,
114 void
115 >::type
116 __construct_at_end(_InputIter __first, _InputIter __last);
117 template <class _ForwardIterator>
118 typename enable_if
119 <
120 __is_forward_iterator<_ForwardIterator>::value,
121 void
122 >::type
123 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
124
125 _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin)
Howard Hinnant1468b662010-11-19 22:17:28 +0000126 {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000127 void __destruct_at_begin(pointer __new_begin, false_type);
128 void __destruct_at_begin(pointer __new_begin, true_type);
129
Howard Hinnant0a612b02011-06-02 20:00:14 +0000130 _LIBCPP_INLINE_VISIBILITY
131 void __destruct_at_end(pointer __new_last) _NOEXCEPT
Howard Hinnant1468b662010-11-19 22:17:28 +0000132 {__destruct_at_end(__new_last, is_trivially_destructible<value_type>());}
Howard Hinnant0a612b02011-06-02 20:00:14 +0000133 void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;
134 void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000135
Howard Hinnant0a612b02011-06-02 20:00:14 +0000136 void swap(__split_buffer& __x)
137 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
138 __is_nothrow_swappable<__alloc_rr>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000139
140 bool __invariants() const;
141
142private:
Howard Hinnant333f50d2010-09-21 20:16:37 +0000143 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant9cbee432011-09-02 20:42:31 +0000144 void __move_assign_alloc(__split_buffer& __c, true_type)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000145 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000146 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000147 __alloc() = _VSTD::move(__c.__alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000148 }
149
Howard Hinnant333f50d2010-09-21 20:16:37 +0000150 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant9cbee432011-09-02 20:42:31 +0000151 void __move_assign_alloc(__split_buffer& __c, false_type) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000152 {}
153
Howard Hinnant333f50d2010-09-21 20:16:37 +0000154 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000155 static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000156 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
157 __is_nothrow_swappable<__alloc_rr>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000158 {__swap_alloc(__x, __y, integral_constant<bool,
159 __alloc_traits::propagate_on_container_swap::value>());}
160
Howard Hinnant333f50d2010-09-21 20:16:37 +0000161 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000162 static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y, true_type)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000163 _NOEXCEPT_(__is_nothrow_swappable<__alloc_rr>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000164 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000165 using _VSTD::swap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000166 swap(__x, __y);
167 }
Howard Hinnant333f50d2010-09-21 20:16:37 +0000168
169 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant0a612b02011-06-02 20:00:14 +0000170 static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y, false_type) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000171 {}
172};
173
174template <class _Tp, class _Allocator>
175bool
176__split_buffer<_Tp, _Allocator>::__invariants() const
177{
178 if (__first_ == nullptr)
179 {
180 if (__begin_ != nullptr)
181 return false;
182 if (__end_ != nullptr)
183 return false;
184 if (__end_cap() != nullptr)
185 return false;
186 }
187 else
188 {
189 if (__begin_ < __first_)
190 return false;
191 if (__end_ < __begin_)
192 return false;
193 if (__end_cap() < __end_)
194 return false;
195 }
196 return true;
197}
198
199// Default constructs __n objects starting at __end_
200// throws if construction throws
201// Precondition: __n > 0
202// Precondition: size() + __n <= capacity()
203// Postcondition: size() == size() + __n
204template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000205void
206__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n)
207{
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000208 __alloc_rr& __a = this->__alloc();
209 do
210 {
Howard Hinnant5f255942011-08-28 15:21:29 +0000211 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000212 ++this->__end_;
213 --__n;
214 } while (__n > 0);
215}
216
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000217// Copy constructs __n objects starting at __end_ from __x
218// throws if construction throws
219// Precondition: __n > 0
220// Precondition: size() + __n <= capacity()
221// Postcondition: size() == old size() + __n
222// Postcondition: [i] == __x for all i in [size() - __n, __n)
223template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000224void
225__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
226{
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000227 __alloc_rr& __a = this->__alloc();
228 do
229 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000230 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000231 ++this->__end_;
232 --__n;
233 } while (__n > 0);
234}
235
236template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000237template <class _InputIter>
238typename enable_if
239<
240 __is_input_iterator<_InputIter>::value &&
241 !__is_forward_iterator<_InputIter>::value,
242 void
243>::type
244__split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last)
245{
246 __alloc_rr& __a = this->__alloc();
247 for (; __first != __last; ++__first)
248 {
249 if (__end_ == __end_cap())
250 {
251 size_type __old_cap = __end_cap() - __first_;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000252 size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000253 __split_buffer __buf(__new_cap, 0, __a);
254 for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_)
255 __alloc_traits::construct(__buf.__alloc(),
Howard Hinnant0949eed2011-06-30 21:18:19 +0000256 _VSTD::__to_raw_pointer(__buf.__end_), _VSTD::move(*__p));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000257 swap(__buf);
258 }
Howard Hinnant0949eed2011-06-30 21:18:19 +0000259 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000260 ++this->__end_;
261 }
262}
263
264template <class _Tp, class _Allocator>
265template <class _ForwardIterator>
266typename enable_if
267<
268 __is_forward_iterator<_ForwardIterator>::value,
269 void
270>::type
271__split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
272{
273 __alloc_rr& __a = this->__alloc();
274 for (; __first != __last; ++__first)
275 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000276 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000277 ++this->__end_;
278 }
279}
280
281template <class _Tp, class _Allocator>
282_LIBCPP_INLINE_VISIBILITY inline
283void
284__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type)
285{
286 while (__begin_ < __new_begin)
287 __alloc_traits::destroy(__alloc(), __begin_++);
288}
289
290template <class _Tp, class _Allocator>
291_LIBCPP_INLINE_VISIBILITY inline
292void
293__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type)
294{
295 __begin_ = __new_begin;
296}
297
298template <class _Tp, class _Allocator>
299_LIBCPP_INLINE_VISIBILITY inline
300void
Howard Hinnant0a612b02011-06-02 20:00:14 +0000301__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000302{
303 while (__new_last < __end_)
304 __alloc_traits::destroy(__alloc(), --__end_);
305}
306
307template <class _Tp, class _Allocator>
308_LIBCPP_INLINE_VISIBILITY inline
309void
Howard Hinnant0a612b02011-06-02 20:00:14 +0000310__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000311{
312 __end_ = __new_last;
313}
314
315template <class _Tp, class _Allocator>
316__split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)
317 : __end_cap_(0, __a)
318{
319 __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr;
320 __begin_ = __end_ = __first_ + __start;
321 __end_cap() = __first_ + __cap;
322}
323
324template <class _Tp, class _Allocator>
325_LIBCPP_INLINE_VISIBILITY inline
326__split_buffer<_Tp, _Allocator>::__split_buffer()
Howard Hinnant009b2c42011-06-03 15:16:49 +0000327 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000328 : __first_(0), __begin_(0), __end_(0), __end_cap_(0)
329{
330}
331
332template <class _Tp, class _Allocator>
333_LIBCPP_INLINE_VISIBILITY inline
334__split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a)
335 : __first_(0), __begin_(0), __end_(0), __end_cap_(0, __a)
336{
337}
338
339template <class _Tp, class _Allocator>
340_LIBCPP_INLINE_VISIBILITY inline
341__split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a)
342 : __first_(0), __begin_(0), __end_(0), __end_cap_(0, __a)
343{
344}
345
346template <class _Tp, class _Allocator>
347__split_buffer<_Tp, _Allocator>::~__split_buffer()
348{
349 clear();
350 if (__first_)
351 __alloc_traits::deallocate(__alloc(), __first_, capacity());
352}
353
Howard Hinnant73d21a42010-09-04 23:28:19 +0000354#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000355
356template <class _Tp, class _Allocator>
357__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000358 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000359 : __first_(_VSTD::move(__c.__first_)),
360 __begin_(_VSTD::move(__c.__begin_)),
361 __end_(_VSTD::move(__c.__end_)),
362 __end_cap_(_VSTD::move(__c.__end_cap_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000363{
364 __c.__first_ = nullptr;
365 __c.__begin_ = nullptr;
366 __c.__end_ = nullptr;
367 __c.__end_cap() = nullptr;
368}
369
370template <class _Tp, class _Allocator>
371__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a)
372 : __end_cap_(__a)
373{
374 if (__a == __c.__alloc())
375 {
376 __first_ = __c.__first_;
377 __begin_ = __c.__begin_;
378 __end_ = __c.__end_;
379 __end_cap() = __c.__end_cap();
380 __c.__first_ = nullptr;
381 __c.__begin_ = nullptr;
382 __c.__end_ = nullptr;
383 __c.__end_cap() = nullptr;
384 }
385 else
386 {
387 size_type __cap = __c.size();
388 __first_ = __alloc_traits::allocate(__alloc(), __cap);
389 __begin_ = __end_ = __first_;
390 __end_cap() = __first_ + __cap;
391 typedef move_iterator<iterator> _I;
392 __construct_at_end(_I(__c.begin()), _I(__c.end()));
393 }
394}
395
396template <class _Tp, class _Allocator>
397__split_buffer<_Tp, _Allocator>&
398__split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000399 _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
400 is_nothrow_move_assignable<allocator_type>::value) ||
401 !__alloc_traits::propagate_on_container_move_assignment::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000402{
403 clear();
404 shrink_to_fit();
405 __first_ = __c.__first_;
406 __begin_ = __c.__begin_;
407 __end_ = __c.__end_;
408 __end_cap() = __c.__end_cap();
409 __move_assign_alloc(__c,
410 integral_constant<bool,
411 __alloc_traits::propagate_on_container_move_assignment::value>());
412 __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
413 return *this;
414}
415
Howard Hinnant73d21a42010-09-04 23:28:19 +0000416#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000417
418template <class _Tp, class _Allocator>
419void
420__split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000421 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
422 __is_nothrow_swappable<__alloc_rr>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000423{
Howard Hinnant0949eed2011-06-30 21:18:19 +0000424 _VSTD::swap(__first_, __x.__first_);
425 _VSTD::swap(__begin_, __x.__begin_);
426 _VSTD::swap(__end_, __x.__end_);
427 _VSTD::swap(__end_cap(), __x.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000428 __swap_alloc(__alloc(), __x.__alloc());
429}
430
431template <class _Tp, class _Allocator>
432void
433__split_buffer<_Tp, _Allocator>::reserve(size_type __n)
434{
435 if (__n < capacity())
436 {
437 __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc());
438 __t.__construct_at_end(move_iterator<pointer>(__begin_),
439 move_iterator<pointer>(__end_));
Howard Hinnant0949eed2011-06-30 21:18:19 +0000440 _VSTD::swap(__first_, __t.__first_);
441 _VSTD::swap(__begin_, __t.__begin_);
442 _VSTD::swap(__end_, __t.__end_);
443 _VSTD::swap(__end_cap(), __t.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000444 }
445}
446
447template <class _Tp, class _Allocator>
448void
Howard Hinnant0a612b02011-06-02 20:00:14 +0000449__split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000450{
451 if (capacity() > size())
452 {
453#ifndef _LIBCPP_NO_EXCEPTIONS
454 try
455 {
Howard Hinnant324bb032010-08-22 00:02:43 +0000456#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000457 __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc());
458 __t.__construct_at_end(move_iterator<pointer>(__begin_),
459 move_iterator<pointer>(__end_));
460 __t.__end_ = __t.__begin_ + (__end_ - __begin_);
Howard Hinnant0949eed2011-06-30 21:18:19 +0000461 _VSTD::swap(__first_, __t.__first_);
462 _VSTD::swap(__begin_, __t.__begin_);
463 _VSTD::swap(__end_, __t.__end_);
464 _VSTD::swap(__end_cap(), __t.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000465#ifndef _LIBCPP_NO_EXCEPTIONS
466 }
467 catch (...)
468 {
469 }
Howard Hinnant324bb032010-08-22 00:02:43 +0000470#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000471 }
472}
473
474template <class _Tp, class _Allocator>
475void
476__split_buffer<_Tp, _Allocator>::push_front(const_reference __x)
477{
478 if (__begin_ == __first_)
479 {
480 if (__end_ < __end_cap())
481 {
482 difference_type __d = __end_cap() - __end_;
483 __d = (__d + 1) / 2;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000484 __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000485 __end_ += __d;
486 }
487 else
488 {
489 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
Howard Hinnantf8ce4592010-07-07 19:14:52 +0000490 __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000491 __t.__construct_at_end(move_iterator<pointer>(__begin_),
492 move_iterator<pointer>(__end_));
Howard Hinnant0949eed2011-06-30 21:18:19 +0000493 _VSTD::swap(__first_, __t.__first_);
494 _VSTD::swap(__begin_, __t.__begin_);
495 _VSTD::swap(__end_, __t.__end_);
496 _VSTD::swap(__end_cap(), __t.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000497 }
498 }
Howard Hinnant0949eed2011-06-30 21:18:19 +0000499 __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000500 --__begin_;
501}
502
Howard Hinnant73d21a42010-09-04 23:28:19 +0000503#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000504
505template <class _Tp, class _Allocator>
506void
507__split_buffer<_Tp, _Allocator>::push_front(value_type&& __x)
508{
509 if (__begin_ == __first_)
510 {
511 if (__end_ < __end_cap())
512 {
513 difference_type __d = __end_cap() - __end_;
514 __d = (__d + 1) / 2;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000515 __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000516 __end_ += __d;
517 }
518 else
519 {
520 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
Howard Hinnantf8ce4592010-07-07 19:14:52 +0000521 __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000522 __t.__construct_at_end(move_iterator<pointer>(__begin_),
523 move_iterator<pointer>(__end_));
Howard Hinnant0949eed2011-06-30 21:18:19 +0000524 _VSTD::swap(__first_, __t.__first_);
525 _VSTD::swap(__begin_, __t.__begin_);
526 _VSTD::swap(__end_, __t.__end_);
527 _VSTD::swap(__end_cap(), __t.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000528 }
529 }
Howard Hinnant0949eed2011-06-30 21:18:19 +0000530 __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1),
531 _VSTD::move(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000532 --__begin_;
533}
534
Howard Hinnant73d21a42010-09-04 23:28:19 +0000535#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000536
537template <class _Tp, class _Allocator>
538_LIBCPP_INLINE_VISIBILITY inline
539void
540__split_buffer<_Tp, _Allocator>::push_back(const_reference __x)
541{
542 if (__end_ == __end_cap())
543 {
544 if (__begin_ > __first_)
545 {
546 difference_type __d = __begin_ - __first_;
547 __d = (__d + 1) / 2;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000548 __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000549 __begin_ -= __d;
550 }
551 else
552 {
553 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
554 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
555 __t.__construct_at_end(move_iterator<pointer>(__begin_),
556 move_iterator<pointer>(__end_));
Howard Hinnant0949eed2011-06-30 21:18:19 +0000557 _VSTD::swap(__first_, __t.__first_);
558 _VSTD::swap(__begin_, __t.__begin_);
559 _VSTD::swap(__end_, __t.__end_);
560 _VSTD::swap(__end_cap(), __t.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000561 }
562 }
Howard Hinnant0949eed2011-06-30 21:18:19 +0000563 __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000564 ++__end_;
565}
566
Howard Hinnant73d21a42010-09-04 23:28:19 +0000567#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000568
569template <class _Tp, class _Allocator>
570void
571__split_buffer<_Tp, _Allocator>::push_back(value_type&& __x)
572{
573 if (__end_ == __end_cap())
574 {
575 if (__begin_ > __first_)
576 {
577 difference_type __d = __begin_ - __first_;
578 __d = (__d + 1) / 2;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000579 __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000580 __begin_ -= __d;
581 }
582 else
583 {
584 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
585 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
586 __t.__construct_at_end(move_iterator<pointer>(__begin_),
587 move_iterator<pointer>(__end_));
Howard Hinnant0949eed2011-06-30 21:18:19 +0000588 _VSTD::swap(__first_, __t.__first_);
589 _VSTD::swap(__begin_, __t.__begin_);
590 _VSTD::swap(__end_, __t.__end_);
591 _VSTD::swap(__end_cap(), __t.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000592 }
593 }
Howard Hinnant0949eed2011-06-30 21:18:19 +0000594 __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_),
595 _VSTD::move(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000596 ++__end_;
597}
598
Howard Hinnant73d21a42010-09-04 23:28:19 +0000599#ifndef _LIBCPP_HAS_NO_VARIADICS
600
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000601template <class _Tp, class _Allocator>
602template <class... _Args>
603void
604__split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args)
605{
606 if (__end_ == __end_cap())
607 {
608 if (__begin_ > __first_)
609 {
610 difference_type __d = __begin_ - __first_;
611 __d = (__d + 1) / 2;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000612 __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000613 __begin_ -= __d;
614 }
615 else
616 {
617 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
618 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
619 __t.__construct_at_end(move_iterator<pointer>(__begin_),
620 move_iterator<pointer>(__end_));
Howard Hinnant0949eed2011-06-30 21:18:19 +0000621 _VSTD::swap(__first_, __t.__first_);
622 _VSTD::swap(__begin_, __t.__begin_);
623 _VSTD::swap(__end_, __t.__end_);
624 _VSTD::swap(__end_cap(), __t.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000625 }
626 }
Howard Hinnant0949eed2011-06-30 21:18:19 +0000627 __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_),
628 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000629 ++__end_;
630}
631
Howard Hinnant73d21a42010-09-04 23:28:19 +0000632#endif // _LIBCPP_HAS_NO_VARIADICS
633
634#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000635
Howard Hinnant0a612b02011-06-02 20:00:14 +0000636template <class _Tp, class _Allocator>
637_LIBCPP_INLINE_VISIBILITY inline
638void
639swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y)
640 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
641{
642 __x.swap(__y);
643}
644
645
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000646_LIBCPP_END_NAMESPACE_STD
647
648#endif // _LIBCPP_SPLIT_BUFFER