blob: e68b78508cc6b64ab6c0b95d8d5aa5649a445a8a [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
55 __split_buffer();
56 explicit __split_buffer(__alloc_rr& __a);
57 explicit __split_buffer(const __alloc_rr& __a);
58 __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a);
59 ~__split_buffer();
60
Howard Hinnant73d21a42010-09-04 23:28:19 +000061#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant0a612b02011-06-02 20:00:14 +000062 __split_buffer(__split_buffer&& __c)
63 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000064 __split_buffer(__split_buffer&& __c, const __alloc_rr& __a);
Howard Hinnant0a612b02011-06-02 20:00:14 +000065 __split_buffer& operator=(__split_buffer&& __c)
66 _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
67 is_nothrow_move_assignable<allocator_type>::value) ||
68 !__alloc_traits::propagate_on_container_move_assignment::value);
Howard Hinnant73d21a42010-09-04 23:28:19 +000069#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000070
Howard Hinnant0a612b02011-06-02 20:00:14 +000071 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __begin_;}
72 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __begin_;}
73 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __end_;}
74 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __end_;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000075
Howard Hinnant0a612b02011-06-02 20:00:14 +000076 _LIBCPP_INLINE_VISIBILITY
77 void clear() _NOEXCEPT
78 {__destruct_at_end(__begin_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000079 _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(__end_ - __begin_);}
80 _LIBCPP_INLINE_VISIBILITY bool empty() const {return __end_ == __begin_;}
81 _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __first_);}
82 _LIBCPP_INLINE_VISIBILITY size_type __front_spare() const {return static_cast<size_type>(__begin_ - __first_);}
83 _LIBCPP_INLINE_VISIBILITY size_type __back_spare() const {return static_cast<size_type>(__end_cap() - __end_);}
84
85 _LIBCPP_INLINE_VISIBILITY reference front() {return *__begin_;}
86 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *__begin_;}
87 _LIBCPP_INLINE_VISIBILITY reference back() {return *(__end_ - 1);}
88 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(__end_ - 1);}
89
90 void reserve(size_type __n);
Howard Hinnant0a612b02011-06-02 20:00:14 +000091 void shrink_to_fit() _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000092 void push_front(const_reference __x);
93 void push_back(const_reference __x);
Michael J. Spencer626916f2010-12-10 19:47:54 +000094#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000095 void push_front(value_type&& __x);
96 void push_back(value_type&& __x);
Michael J. Spencer626916f2010-12-10 19:47:54 +000097#if !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000098 template <class... _Args>
99 void emplace_back(_Args&&... __args);
Michael J. Spencer626916f2010-12-10 19:47:54 +0000100#endif // !defined(_LIBCPP_HAS_NO_VARIADICS)
101#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000102
103 _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);}
104 _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);}
105
106 void __construct_at_end(size_type __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000107 void __construct_at_end(size_type __n, const_reference __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000108 template <class _InputIter>
109 typename enable_if
110 <
111 __is_input_iterator<_InputIter>::value &&
112 !__is_forward_iterator<_InputIter>::value,
113 void
114 >::type
115 __construct_at_end(_InputIter __first, _InputIter __last);
116 template <class _ForwardIterator>
117 typename enable_if
118 <
119 __is_forward_iterator<_ForwardIterator>::value,
120 void
121 >::type
122 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
123
124 _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin)
Howard Hinnant1468b662010-11-19 22:17:28 +0000125 {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000126 void __destruct_at_begin(pointer __new_begin, false_type);
127 void __destruct_at_begin(pointer __new_begin, true_type);
128
Howard Hinnant0a612b02011-06-02 20:00:14 +0000129 _LIBCPP_INLINE_VISIBILITY
130 void __destruct_at_end(pointer __new_last) _NOEXCEPT
Howard Hinnant1468b662010-11-19 22:17:28 +0000131 {__destruct_at_end(__new_last, is_trivially_destructible<value_type>());}
Howard Hinnant0a612b02011-06-02 20:00:14 +0000132 void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;
133 void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000134
Howard Hinnant0a612b02011-06-02 20:00:14 +0000135 void swap(__split_buffer& __x)
136 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
137 __is_nothrow_swappable<__alloc_rr>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000138
139 bool __invariants() const;
140
141private:
Howard Hinnant333f50d2010-09-21 20:16:37 +0000142 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000143 void __move_assign_alloc(const __split_buffer& __c, true_type)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000144 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000145 {
146 __alloc() = _STD::move(__c.__alloc());
147 }
148
Howard Hinnant333f50d2010-09-21 20:16:37 +0000149 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant0a612b02011-06-02 20:00:14 +0000150 void __move_assign_alloc(const __split_buffer& __c, false_type) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000151 {}
152
Howard Hinnant333f50d2010-09-21 20:16:37 +0000153 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000154 static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000155 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
156 __is_nothrow_swappable<__alloc_rr>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000157 {__swap_alloc(__x, __y, integral_constant<bool,
158 __alloc_traits::propagate_on_container_swap::value>());}
159
Howard Hinnant333f50d2010-09-21 20:16:37 +0000160 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000161 static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y, true_type)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000162 _NOEXCEPT_(__is_nothrow_swappable<__alloc_rr>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000163 {
164 using _STD::swap;
165 swap(__x, __y);
166 }
Howard Hinnant333f50d2010-09-21 20:16:37 +0000167
168 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant0a612b02011-06-02 20:00:14 +0000169 static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y, false_type) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000170 {}
171};
172
173template <class _Tp, class _Allocator>
174bool
175__split_buffer<_Tp, _Allocator>::__invariants() const
176{
177 if (__first_ == nullptr)
178 {
179 if (__begin_ != nullptr)
180 return false;
181 if (__end_ != nullptr)
182 return false;
183 if (__end_cap() != nullptr)
184 return false;
185 }
186 else
187 {
188 if (__begin_ < __first_)
189 return false;
190 if (__end_ < __begin_)
191 return false;
192 if (__end_cap() < __end_)
193 return false;
194 }
195 return true;
196}
197
198// Default constructs __n objects starting at __end_
199// throws if construction throws
200// Precondition: __n > 0
201// Precondition: size() + __n <= capacity()
202// Postcondition: size() == size() + __n
203template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000204void
205__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n)
206{
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000207 __alloc_rr& __a = this->__alloc();
208 do
209 {
210 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), value_type());
211 ++this->__end_;
212 --__n;
213 } while (__n > 0);
214}
215
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000216// Copy constructs __n objects starting at __end_ from __x
217// throws if construction throws
218// Precondition: __n > 0
219// Precondition: size() + __n <= capacity()
220// Postcondition: size() == old size() + __n
221// Postcondition: [i] == __x for all i in [size() - __n, __n)
222template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000223void
224__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
225{
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000226 __alloc_rr& __a = this->__alloc();
227 do
228 {
229 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), __x);
230 ++this->__end_;
231 --__n;
232 } while (__n > 0);
233}
234
235template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000236template <class _InputIter>
237typename enable_if
238<
239 __is_input_iterator<_InputIter>::value &&
240 !__is_forward_iterator<_InputIter>::value,
241 void
242>::type
243__split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last)
244{
245 __alloc_rr& __a = this->__alloc();
246 for (; __first != __last; ++__first)
247 {
248 if (__end_ == __end_cap())
249 {
250 size_type __old_cap = __end_cap() - __first_;
251 size_type __new_cap = _STD::max<size_type>(2 * __old_cap, 8);
252 __split_buffer __buf(__new_cap, 0, __a);
253 for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_)
254 __alloc_traits::construct(__buf.__alloc(),
255 _STD::__to_raw_pointer(__buf.__end_), _STD::move(*__p));
256 swap(__buf);
257 }
258 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), *__first);
259 ++this->__end_;
260 }
261}
262
263template <class _Tp, class _Allocator>
264template <class _ForwardIterator>
265typename enable_if
266<
267 __is_forward_iterator<_ForwardIterator>::value,
268 void
269>::type
270__split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
271{
272 __alloc_rr& __a = this->__alloc();
273 for (; __first != __last; ++__first)
274 {
275 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), *__first);
276 ++this->__end_;
277 }
278}
279
280template <class _Tp, class _Allocator>
281_LIBCPP_INLINE_VISIBILITY inline
282void
283__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type)
284{
285 while (__begin_ < __new_begin)
286 __alloc_traits::destroy(__alloc(), __begin_++);
287}
288
289template <class _Tp, class _Allocator>
290_LIBCPP_INLINE_VISIBILITY inline
291void
292__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type)
293{
294 __begin_ = __new_begin;
295}
296
297template <class _Tp, class _Allocator>
298_LIBCPP_INLINE_VISIBILITY inline
299void
Howard Hinnant0a612b02011-06-02 20:00:14 +0000300__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000301{
302 while (__new_last < __end_)
303 __alloc_traits::destroy(__alloc(), --__end_);
304}
305
306template <class _Tp, class _Allocator>
307_LIBCPP_INLINE_VISIBILITY inline
308void
Howard Hinnant0a612b02011-06-02 20:00:14 +0000309__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000310{
311 __end_ = __new_last;
312}
313
314template <class _Tp, class _Allocator>
315__split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)
316 : __end_cap_(0, __a)
317{
318 __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr;
319 __begin_ = __end_ = __first_ + __start;
320 __end_cap() = __first_ + __cap;
321}
322
323template <class _Tp, class _Allocator>
324_LIBCPP_INLINE_VISIBILITY inline
325__split_buffer<_Tp, _Allocator>::__split_buffer()
326 : __first_(0), __begin_(0), __end_(0), __end_cap_(0)
327{
328}
329
330template <class _Tp, class _Allocator>
331_LIBCPP_INLINE_VISIBILITY inline
332__split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a)
333 : __first_(0), __begin_(0), __end_(0), __end_cap_(0, __a)
334{
335}
336
337template <class _Tp, class _Allocator>
338_LIBCPP_INLINE_VISIBILITY inline
339__split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a)
340 : __first_(0), __begin_(0), __end_(0), __end_cap_(0, __a)
341{
342}
343
344template <class _Tp, class _Allocator>
345__split_buffer<_Tp, _Allocator>::~__split_buffer()
346{
347 clear();
348 if (__first_)
349 __alloc_traits::deallocate(__alloc(), __first_, capacity());
350}
351
Howard Hinnant73d21a42010-09-04 23:28:19 +0000352#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000353
354template <class _Tp, class _Allocator>
355__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000356 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000357 : __first_(_STD::move(__c.__first_)),
358 __begin_(_STD::move(__c.__begin_)),
359 __end_(_STD::move(__c.__end_)),
360 __end_cap_(_STD::move(__c.__end_cap_))
361{
362 __c.__first_ = nullptr;
363 __c.__begin_ = nullptr;
364 __c.__end_ = nullptr;
365 __c.__end_cap() = nullptr;
366}
367
368template <class _Tp, class _Allocator>
369__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a)
370 : __end_cap_(__a)
371{
372 if (__a == __c.__alloc())
373 {
374 __first_ = __c.__first_;
375 __begin_ = __c.__begin_;
376 __end_ = __c.__end_;
377 __end_cap() = __c.__end_cap();
378 __c.__first_ = nullptr;
379 __c.__begin_ = nullptr;
380 __c.__end_ = nullptr;
381 __c.__end_cap() = nullptr;
382 }
383 else
384 {
385 size_type __cap = __c.size();
386 __first_ = __alloc_traits::allocate(__alloc(), __cap);
387 __begin_ = __end_ = __first_;
388 __end_cap() = __first_ + __cap;
389 typedef move_iterator<iterator> _I;
390 __construct_at_end(_I(__c.begin()), _I(__c.end()));
391 }
392}
393
394template <class _Tp, class _Allocator>
395__split_buffer<_Tp, _Allocator>&
396__split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000397 _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
398 is_nothrow_move_assignable<allocator_type>::value) ||
399 !__alloc_traits::propagate_on_container_move_assignment::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000400{
401 clear();
402 shrink_to_fit();
403 __first_ = __c.__first_;
404 __begin_ = __c.__begin_;
405 __end_ = __c.__end_;
406 __end_cap() = __c.__end_cap();
407 __move_assign_alloc(__c,
408 integral_constant<bool,
409 __alloc_traits::propagate_on_container_move_assignment::value>());
410 __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
411 return *this;
412}
413
Howard Hinnant73d21a42010-09-04 23:28:19 +0000414#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000415
416template <class _Tp, class _Allocator>
417void
418__split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x)
Howard Hinnant0a612b02011-06-02 20:00:14 +0000419 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
420 __is_nothrow_swappable<__alloc_rr>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000421{
422 _STD::swap(__first_, __x.__first_);
423 _STD::swap(__begin_, __x.__begin_);
424 _STD::swap(__end_, __x.__end_);
425 _STD::swap(__end_cap(), __x.__end_cap());
426 __swap_alloc(__alloc(), __x.__alloc());
427}
428
429template <class _Tp, class _Allocator>
430void
431__split_buffer<_Tp, _Allocator>::reserve(size_type __n)
432{
433 if (__n < capacity())
434 {
435 __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc());
436 __t.__construct_at_end(move_iterator<pointer>(__begin_),
437 move_iterator<pointer>(__end_));
438 _STD::swap(__first_, __t.__first_);
439 _STD::swap(__begin_, __t.__begin_);
440 _STD::swap(__end_, __t.__end_);
441 _STD::swap(__end_cap(), __t.__end_cap());
442 }
443}
444
445template <class _Tp, class _Allocator>
446void
Howard Hinnant0a612b02011-06-02 20:00:14 +0000447__split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000448{
449 if (capacity() > size())
450 {
451#ifndef _LIBCPP_NO_EXCEPTIONS
452 try
453 {
Howard Hinnant324bb032010-08-22 00:02:43 +0000454#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000455 __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc());
456 __t.__construct_at_end(move_iterator<pointer>(__begin_),
457 move_iterator<pointer>(__end_));
458 __t.__end_ = __t.__begin_ + (__end_ - __begin_);
459 _STD::swap(__first_, __t.__first_);
460 _STD::swap(__begin_, __t.__begin_);
461 _STD::swap(__end_, __t.__end_);
462 _STD::swap(__end_cap(), __t.__end_cap());
463#ifndef _LIBCPP_NO_EXCEPTIONS
464 }
465 catch (...)
466 {
467 }
Howard Hinnant324bb032010-08-22 00:02:43 +0000468#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000469 }
470}
471
472template <class _Tp, class _Allocator>
473void
474__split_buffer<_Tp, _Allocator>::push_front(const_reference __x)
475{
476 if (__begin_ == __first_)
477 {
478 if (__end_ < __end_cap())
479 {
480 difference_type __d = __end_cap() - __end_;
481 __d = (__d + 1) / 2;
482 __begin_ = _STD::move_backward(__begin_, __end_, __end_ + __d);
483 __end_ += __d;
484 }
485 else
486 {
487 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
Howard Hinnantf8ce4592010-07-07 19:14:52 +0000488 __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000489 __t.__construct_at_end(move_iterator<pointer>(__begin_),
490 move_iterator<pointer>(__end_));
491 _STD::swap(__first_, __t.__first_);
492 _STD::swap(__begin_, __t.__begin_);
493 _STD::swap(__end_, __t.__end_);
494 _STD::swap(__end_cap(), __t.__end_cap());
495 }
496 }
497 __alloc_traits::construct(__alloc(), _STD::__to_raw_pointer(__begin_-1), __x);
498 --__begin_;
499}
500
Howard Hinnant73d21a42010-09-04 23:28:19 +0000501#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000502
503template <class _Tp, class _Allocator>
504void
505__split_buffer<_Tp, _Allocator>::push_front(value_type&& __x)
506{
507 if (__begin_ == __first_)
508 {
509 if (__end_ < __end_cap())
510 {
511 difference_type __d = __end_cap() - __end_;
512 __d = (__d + 1) / 2;
513 __begin_ = _STD::move_backward(__begin_, __end_, __end_ + __d);
514 __end_ += __d;
515 }
516 else
517 {
518 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
Howard Hinnantf8ce4592010-07-07 19:14:52 +0000519 __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000520 __t.__construct_at_end(move_iterator<pointer>(__begin_),
521 move_iterator<pointer>(__end_));
522 _STD::swap(__first_, __t.__first_);
523 _STD::swap(__begin_, __t.__begin_);
524 _STD::swap(__end_, __t.__end_);
525 _STD::swap(__end_cap(), __t.__end_cap());
526 }
527 }
528 __alloc_traits::construct(__alloc(), _STD::__to_raw_pointer(__begin_-1),
529 _STD::move(__x));
530 --__begin_;
531}
532
Howard Hinnant73d21a42010-09-04 23:28:19 +0000533#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000534
535template <class _Tp, class _Allocator>
536_LIBCPP_INLINE_VISIBILITY inline
537void
538__split_buffer<_Tp, _Allocator>::push_back(const_reference __x)
539{
540 if (__end_ == __end_cap())
541 {
542 if (__begin_ > __first_)
543 {
544 difference_type __d = __begin_ - __first_;
545 __d = (__d + 1) / 2;
546 __end_ = _STD::move(__begin_, __end_, __begin_ - __d);
547 __begin_ -= __d;
548 }
549 else
550 {
551 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
552 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
553 __t.__construct_at_end(move_iterator<pointer>(__begin_),
554 move_iterator<pointer>(__end_));
555 _STD::swap(__first_, __t.__first_);
556 _STD::swap(__begin_, __t.__begin_);
557 _STD::swap(__end_, __t.__end_);
558 _STD::swap(__end_cap(), __t.__end_cap());
559 }
560 }
561 __alloc_traits::construct(__alloc(), _STD::__to_raw_pointer(__end_), __x);
562 ++__end_;
563}
564
Howard Hinnant73d21a42010-09-04 23:28:19 +0000565#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000566
567template <class _Tp, class _Allocator>
568void
569__split_buffer<_Tp, _Allocator>::push_back(value_type&& __x)
570{
571 if (__end_ == __end_cap())
572 {
573 if (__begin_ > __first_)
574 {
575 difference_type __d = __begin_ - __first_;
576 __d = (__d + 1) / 2;
577 __end_ = _STD::move(__begin_, __end_, __begin_ - __d);
578 __begin_ -= __d;
579 }
580 else
581 {
582 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
583 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
584 __t.__construct_at_end(move_iterator<pointer>(__begin_),
585 move_iterator<pointer>(__end_));
586 _STD::swap(__first_, __t.__first_);
587 _STD::swap(__begin_, __t.__begin_);
588 _STD::swap(__end_, __t.__end_);
589 _STD::swap(__end_cap(), __t.__end_cap());
590 }
591 }
592 __alloc_traits::construct(__alloc(), _STD::__to_raw_pointer(__end_),
593 _STD::move(__x));
594 ++__end_;
595}
596
Howard Hinnant73d21a42010-09-04 23:28:19 +0000597#ifndef _LIBCPP_HAS_NO_VARIADICS
598
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000599template <class _Tp, class _Allocator>
600template <class... _Args>
601void
602__split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args)
603{
604 if (__end_ == __end_cap())
605 {
606 if (__begin_ > __first_)
607 {
608 difference_type __d = __begin_ - __first_;
609 __d = (__d + 1) / 2;
610 __end_ = _STD::move(__begin_, __end_, __begin_ - __d);
611 __begin_ -= __d;
612 }
613 else
614 {
615 size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1);
616 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
617 __t.__construct_at_end(move_iterator<pointer>(__begin_),
618 move_iterator<pointer>(__end_));
619 _STD::swap(__first_, __t.__first_);
620 _STD::swap(__begin_, __t.__begin_);
621 _STD::swap(__end_, __t.__end_);
622 _STD::swap(__end_cap(), __t.__end_cap());
623 }
624 }
625 __alloc_traits::construct(__alloc(), _STD::__to_raw_pointer(__end_),
626 _STD::forward<_Args>(__args)...);
627 ++__end_;
628}
629
Howard Hinnant73d21a42010-09-04 23:28:19 +0000630#endif // _LIBCPP_HAS_NO_VARIADICS
631
632#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000633
Howard Hinnant0a612b02011-06-02 20:00:14 +0000634template <class _Tp, class _Allocator>
635_LIBCPP_INLINE_VISIBILITY inline
636void
637swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y)
638 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
639{
640 __x.swap(__y);
641}
642
643
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000644_LIBCPP_END_NAMESPACE_STD
645
646#endif // _LIBCPP_SPLIT_BUFFER