1 | // -*- C++ -*- |
2 | #ifndef _LIBCPP_SPLIT_BUFFER |
3 | #define _LIBCPP_SPLIT_BUFFER |
4 | |
5 | #include <__config> |
6 | #include <type_traits> |
7 | #include <algorithm> |
8 | |
9 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
10 | #pragma GCC system_header |
11 | #endif |
12 | |
13 | _LIBCPP_PUSH_MACROS |
14 | #include <__undef_macros> |
15 | |
16 | |
17 | _LIBCPP_BEGIN_NAMESPACE_STD |
18 | |
19 | template <bool> |
20 | class __split_buffer_common |
21 | { |
22 | protected: |
23 | void __throw_length_error() const; |
24 | void __throw_out_of_range() const; |
25 | }; |
26 | |
27 | template <class _Tp, class _Allocator = allocator<_Tp> > |
28 | struct __split_buffer |
29 | : private __split_buffer_common<true> |
30 | { |
31 | private: |
32 | __split_buffer(const __split_buffer&); |
33 | __split_buffer& operator=(const __split_buffer&); |
34 | public: |
35 | typedef _Tp value_type; |
36 | typedef _Allocator allocator_type; |
37 | typedef typename remove_reference<allocator_type>::type __alloc_rr; |
38 | typedef allocator_traits<__alloc_rr> __alloc_traits; |
39 | typedef value_type& reference; |
40 | typedef const value_type& const_reference; |
41 | typedef typename __alloc_traits::size_type size_type; |
42 | typedef typename __alloc_traits::difference_type difference_type; |
43 | typedef typename __alloc_traits::pointer pointer; |
44 | typedef typename __alloc_traits::const_pointer const_pointer; |
45 | typedef pointer iterator; |
46 | typedef const_pointer const_iterator; |
47 | |
48 | pointer __first_; |
49 | pointer __begin_; |
50 | pointer __end_; |
51 | __compressed_pair<pointer, allocator_type> __end_cap_; |
52 | |
53 | typedef typename add_lvalue_reference<allocator_type>::type __alloc_ref; |
54 | typedef typename add_lvalue_reference<allocator_type>::type __alloc_const_ref; |
55 | |
56 | _LIBCPP_INLINE_VISIBILITY __alloc_rr& __alloc() _NOEXCEPT {return __end_cap_.second();} |
57 | _LIBCPP_INLINE_VISIBILITY const __alloc_rr& __alloc() const _NOEXCEPT {return __end_cap_.second();} |
58 | _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() _NOEXCEPT {return __end_cap_.first();} |
59 | _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const _NOEXCEPT {return __end_cap_.first();} |
60 | |
61 | _LIBCPP_INLINE_VISIBILITY |
62 | __split_buffer() |
63 | _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); |
64 | _LIBCPP_INLINE_VISIBILITY |
65 | explicit __split_buffer(__alloc_rr& __a); |
66 | _LIBCPP_INLINE_VISIBILITY |
67 | explicit __split_buffer(const __alloc_rr& __a); |
68 | __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a); |
69 | ~__split_buffer(); |
70 | |
71 | #ifndef _LIBCPP_CXX03_LANG |
72 | __split_buffer(__split_buffer&& __c) |
73 | _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); |
74 | __split_buffer(__split_buffer&& __c, const __alloc_rr& __a); |
75 | __split_buffer& operator=(__split_buffer&& __c) |
76 | _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && |
77 | is_nothrow_move_assignable<allocator_type>::value) || |
78 | !__alloc_traits::propagate_on_container_move_assignment::value); |
79 | #endif // _LIBCPP_CXX03_LANG |
80 | |
81 | _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __begin_;} |
82 | _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __begin_;} |
83 | _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __end_;} |
84 | _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __end_;} |
85 | |
86 | _LIBCPP_INLINE_VISIBILITY |
87 | void clear() _NOEXCEPT |
88 | {__destruct_at_end(__begin_);} |
89 | _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(__end_ - __begin_);} |
90 | _LIBCPP_INLINE_VISIBILITY bool empty() const {return __end_ == __begin_;} |
91 | _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __first_);} |
92 | _LIBCPP_INLINE_VISIBILITY size_type __front_spare() const {return static_cast<size_type>(__begin_ - __first_);} |
93 | _LIBCPP_INLINE_VISIBILITY size_type __back_spare() const {return static_cast<size_type>(__end_cap() - __end_);} |
94 | |
95 | _LIBCPP_INLINE_VISIBILITY reference front() {return *__begin_;} |
96 | _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *__begin_;} |
97 | _LIBCPP_INLINE_VISIBILITY reference back() {return *(__end_ - 1);} |
98 | _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(__end_ - 1);} |
99 | |
100 | void reserve(size_type __n); |
101 | void shrink_to_fit() _NOEXCEPT; |
102 | void push_front(const_reference __x); |
103 | _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); |
104 | #ifndef _LIBCPP_CXX03_LANG |
105 | void push_front(value_type&& __x); |
106 | void push_back(value_type&& __x); |
107 | template <class... _Args> |
108 | void emplace_back(_Args&&... __args); |
109 | #endif // !defined(_LIBCPP_CXX03_LANG) |
110 | |
111 | _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);} |
112 | _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);} |
113 | |
114 | void __construct_at_end(size_type __n); |
115 | void __construct_at_end(size_type __n, const_reference __x); |
116 | template <class _InputIter> |
117 | typename enable_if |
118 | < |
119 | __is_cpp17_input_iterator<_InputIter>::value && |
120 | !__is_cpp17_forward_iterator<_InputIter>::value, |
121 | void |
122 | >::type |
123 | __construct_at_end(_InputIter __first, _InputIter __last); |
124 | template <class _ForwardIterator> |
125 | typename enable_if |
126 | < |
127 | __is_cpp17_forward_iterator<_ForwardIterator>::value, |
128 | void |
129 | >::type |
130 | __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); |
131 | |
132 | _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin) |
133 | {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());} |
134 | _LIBCPP_INLINE_VISIBILITY |
135 | void __destruct_at_begin(pointer __new_begin, false_type); |
136 | _LIBCPP_INLINE_VISIBILITY |
137 | void __destruct_at_begin(pointer __new_begin, true_type); |
138 | |
139 | _LIBCPP_INLINE_VISIBILITY |
140 | void __destruct_at_end(pointer __new_last) _NOEXCEPT |
141 | {__destruct_at_end(__new_last, false_type());} |
142 | _LIBCPP_INLINE_VISIBILITY |
143 | void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT; |
144 | _LIBCPP_INLINE_VISIBILITY |
145 | void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT; |
146 | |
147 | void swap(__split_buffer& __x) |
148 | _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| |
149 | __is_nothrow_swappable<__alloc_rr>::value); |
150 | |
151 | bool __invariants() const; |
152 | |
153 | private: |
154 | _LIBCPP_INLINE_VISIBILITY |
155 | void __move_assign_alloc(__split_buffer& __c, true_type) |
156 | _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) |
157 | { |
158 | __alloc() = _VSTD::move(__c.__alloc()); |
159 | } |
160 | |
161 | _LIBCPP_INLINE_VISIBILITY |
162 | void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT |
163 | {} |
164 | |
165 | struct _ConstructTransaction { |
166 | explicit _ConstructTransaction(pointer* __p, size_type __n) _NOEXCEPT |
167 | : __pos_(*__p), __end_(*__p + __n), __dest_(__p) { |
168 | } |
169 | ~_ConstructTransaction() { |
170 | *__dest_ = __pos_; |
171 | } |
172 | pointer __pos_; |
173 | const pointer __end_; |
174 | private: |
175 | pointer *__dest_; |
176 | }; |
177 | }; |
178 | |
179 | template <class _Tp, class _Allocator> |
180 | bool |
181 | __split_buffer<_Tp, _Allocator>::__invariants() const |
182 | { |
183 | if (__first_ == nullptr) |
184 | { |
185 | if (__begin_ != nullptr) |
186 | return false; |
187 | if (__end_ != nullptr) |
188 | return false; |
189 | if (__end_cap() != nullptr) |
190 | return false; |
191 | } |
192 | else |
193 | { |
194 | if (__begin_ < __first_) |
195 | return false; |
196 | if (__end_ < __begin_) |
197 | return false; |
198 | if (__end_cap() < __end_) |
199 | return false; |
200 | } |
201 | return true; |
202 | } |
203 | |
204 | // Default constructs __n objects starting at __end_ |
205 | // throws if construction throws |
206 | // Precondition: __n > 0 |
207 | // Precondition: size() + __n <= capacity() |
208 | // Postcondition: size() == size() + __n |
209 | template <class _Tp, class _Allocator> |
210 | void |
211 | __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) |
212 | { |
213 | _ConstructTransaction __tx(&this->__end_, __n); |
214 | for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { |
215 | __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_)); |
216 | } |
217 | } |
218 | |
219 | // Copy constructs __n objects starting at __end_ from __x |
220 | // throws if construction throws |
221 | // Precondition: __n > 0 |
222 | // Precondition: size() + __n <= capacity() |
223 | // Postcondition: size() == old size() + __n |
224 | // Postcondition: [i] == __x for all i in [size() - __n, __n) |
225 | template <class _Tp, class _Allocator> |
226 | void |
227 | __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) |
228 | { |
229 | _ConstructTransaction __tx(&this->__end_, __n); |
230 | for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { |
231 | __alloc_traits::construct(this->__alloc(), |
232 | _VSTD::__to_address(__tx.__pos_), __x); |
233 | } |
234 | } |
235 | |
236 | template <class _Tp, class _Allocator> |
237 | template <class _InputIter> |
238 | typename enable_if |
239 | < |
240 | __is_cpp17_input_iterator<_InputIter>::value && |
241 | !__is_cpp17_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_; |
252 | size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8); |
253 | __split_buffer __buf(__new_cap, 0, __a); |
254 | for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_) |
255 | __alloc_traits::construct(__buf.__alloc(), |
256 | _VSTD::__to_address(__buf.__end_), _VSTD::move(*__p)); |
257 | swap(__buf); |
258 | } |
259 | __alloc_traits::construct(__a, _VSTD::__to_address(this->__end_), *__first); |
260 | ++this->__end_; |
261 | } |
262 | } |
263 | |
264 | template <class _Tp, class _Allocator> |
265 | template <class _ForwardIterator> |
266 | typename enable_if |
267 | < |
268 | __is_cpp17_forward_iterator<_ForwardIterator>::value, |
269 | void |
270 | >::type |
271 | __split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) |
272 | { |
273 | _ConstructTransaction __tx(&this->__end_, std::distance(__first, __last)); |
274 | for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, ++__first) { |
275 | __alloc_traits::construct(this->__alloc(), |
276 | _VSTD::__to_address(__tx.__pos_), *__first); |
277 | } |
278 | } |
279 | |
280 | template <class _Tp, class _Allocator> |
281 | inline |
282 | void |
283 | __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) |
284 | { |
285 | while (__begin_ != __new_begin) |
286 | __alloc_traits::destroy(__alloc(), __to_address(__begin_++)); |
287 | } |
288 | |
289 | template <class _Tp, class _Allocator> |
290 | inline |
291 | void |
292 | __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) |
293 | { |
294 | __begin_ = __new_begin; |
295 | } |
296 | |
297 | template <class _Tp, class _Allocator> |
298 | inline _LIBCPP_INLINE_VISIBILITY |
299 | void |
300 | __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT |
301 | { |
302 | while (__new_last != __end_) |
303 | __alloc_traits::destroy(__alloc(), __to_address(--__end_)); |
304 | } |
305 | |
306 | template <class _Tp, class _Allocator> |
307 | inline _LIBCPP_INLINE_VISIBILITY |
308 | void |
309 | __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT |
310 | { |
311 | __end_ = __new_last; |
312 | } |
313 | |
314 | template <class _Tp, class _Allocator> |
315 | __split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a) |
316 | : __end_cap_(nullptr, __a) |
317 | { |
318 | __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr; |
319 | __begin_ = __end_ = __first_ + __start; |
320 | __end_cap() = __first_ + __cap; |
321 | } |
322 | |
323 | template <class _Tp, class _Allocator> |
324 | inline |
325 | __split_buffer<_Tp, _Allocator>::__split_buffer() |
326 | _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) |
327 | : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __default_init_tag()) |
328 | { |
329 | } |
330 | |
331 | template <class _Tp, class _Allocator> |
332 | inline |
333 | __split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a) |
334 | : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) |
335 | { |
336 | } |
337 | |
338 | template <class _Tp, class _Allocator> |
339 | inline |
340 | __split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a) |
341 | : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) |
342 | { |
343 | } |
344 | |
345 | template <class _Tp, class _Allocator> |
346 | __split_buffer<_Tp, _Allocator>::~__split_buffer() |
347 | { |
348 | clear(); |
349 | if (__first_) |
350 | __alloc_traits::deallocate(__alloc(), __first_, capacity()); |
351 | } |
352 | |
353 | #ifndef _LIBCPP_CXX03_LANG |
354 | |
355 | template <class _Tp, class _Allocator> |
356 | __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c) |
357 | _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) |
358 | : __first_(_VSTD::move(__c.__first_)), |
359 | __begin_(_VSTD::move(__c.__begin_)), |
360 | __end_(_VSTD::move(__c.__end_)), |
361 | __end_cap_(_VSTD::move(__c.__end_cap_)) |
362 | { |
363 | __c.__first_ = nullptr; |
364 | __c.__begin_ = nullptr; |
365 | __c.__end_ = nullptr; |
366 | __c.__end_cap() = nullptr; |
367 | } |
368 | |
369 | template <class _Tp, class _Allocator> |
370 | __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a) |
371 | : __end_cap_(nullptr, __a) |
372 | { |
373 | if (__a == __c.__alloc()) |
374 | { |
375 | __first_ = __c.__first_; |
376 | __begin_ = __c.__begin_; |
377 | __end_ = __c.__end_; |
378 | __end_cap() = __c.__end_cap(); |
379 | __c.__first_ = nullptr; |
380 | __c.__begin_ = nullptr; |
381 | __c.__end_ = nullptr; |
382 | __c.__end_cap() = nullptr; |
383 | } |
384 | else |
385 | { |
386 | size_type __cap = __c.size(); |
387 | __first_ = __alloc_traits::allocate(__alloc(), __cap); |
388 | __begin_ = __end_ = __first_; |
389 | __end_cap() = __first_ + __cap; |
390 | typedef move_iterator<iterator> _Ip; |
391 | __construct_at_end(_Ip(__c.begin()), _Ip(__c.end())); |
392 | } |
393 | } |
394 | |
395 | template <class _Tp, class _Allocator> |
396 | __split_buffer<_Tp, _Allocator>& |
397 | __split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c) |
398 | _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && |
399 | is_nothrow_move_assignable<allocator_type>::value) || |
400 | !__alloc_traits::propagate_on_container_move_assignment::value) |
401 | { |
402 | clear(); |
403 | shrink_to_fit(); |
404 | __first_ = __c.__first_; |
405 | __begin_ = __c.__begin_; |
406 | __end_ = __c.__end_; |
407 | __end_cap() = __c.__end_cap(); |
408 | __move_assign_alloc(__c, |
409 | integral_constant<bool, |
410 | __alloc_traits::propagate_on_container_move_assignment::value>()); |
411 | __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; |
412 | return *this; |
413 | } |
414 | |
415 | #endif // _LIBCPP_CXX03_LANG |
416 | |
417 | template <class _Tp, class _Allocator> |
418 | void |
419 | __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x) |
420 | _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| |
421 | __is_nothrow_swappable<__alloc_rr>::value) |
422 | { |
423 | _VSTD::swap(__first_, __x.__first_); |
424 | _VSTD::swap(__begin_, __x.__begin_); |
425 | _VSTD::swap(__end_, __x.__end_); |
426 | _VSTD::swap(__end_cap(), __x.__end_cap()); |
427 | __swap_allocator(__alloc(), __x.__alloc()); |
428 | } |
429 | |
430 | template <class _Tp, class _Allocator> |
431 | void |
432 | __split_buffer<_Tp, _Allocator>::reserve(size_type __n) |
433 | { |
434 | if (__n < capacity()) |
435 | { |
436 | __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc()); |
437 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
438 | move_iterator<pointer>(__end_)); |
439 | _VSTD::swap(__first_, __t.__first_); |
440 | _VSTD::swap(__begin_, __t.__begin_); |
441 | _VSTD::swap(__end_, __t.__end_); |
442 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
443 | } |
444 | } |
445 | |
446 | template <class _Tp, class _Allocator> |
447 | void |
448 | __split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT |
449 | { |
450 | if (capacity() > size()) |
451 | { |
452 | #ifndef _LIBCPP_NO_EXCEPTIONS |
453 | try |
454 | { |
455 | #endif // _LIBCPP_NO_EXCEPTIONS |
456 | __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc()); |
457 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
458 | move_iterator<pointer>(__end_)); |
459 | __t.__end_ = __t.__begin_ + (__end_ - __begin_); |
460 | _VSTD::swap(__first_, __t.__first_); |
461 | _VSTD::swap(__begin_, __t.__begin_); |
462 | _VSTD::swap(__end_, __t.__end_); |
463 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
464 | #ifndef _LIBCPP_NO_EXCEPTIONS |
465 | } |
466 | catch (...) |
467 | { |
468 | } |
469 | #endif // _LIBCPP_NO_EXCEPTIONS |
470 | } |
471 | } |
472 | |
473 | template <class _Tp, class _Allocator> |
474 | void |
475 | __split_buffer<_Tp, _Allocator>::push_front(const_reference __x) |
476 | { |
477 | if (__begin_ == __first_) |
478 | { |
479 | if (__end_ < __end_cap()) |
480 | { |
481 | difference_type __d = __end_cap() - __end_; |
482 | __d = (__d + 1) / 2; |
483 | __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); |
484 | __end_ += __d; |
485 | } |
486 | else |
487 | { |
488 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
489 | __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); |
490 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
491 | move_iterator<pointer>(__end_)); |
492 | _VSTD::swap(__first_, __t.__first_); |
493 | _VSTD::swap(__begin_, __t.__begin_); |
494 | _VSTD::swap(__end_, __t.__end_); |
495 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
496 | } |
497 | } |
498 | __alloc_traits::construct(__alloc(), _VSTD::__to_address(__begin_-1), __x); |
499 | --__begin_; |
500 | } |
501 | |
502 | #ifndef _LIBCPP_CXX03_LANG |
503 | |
504 | template <class _Tp, class _Allocator> |
505 | void |
506 | __split_buffer<_Tp, _Allocator>::push_front(value_type&& __x) |
507 | { |
508 | if (__begin_ == __first_) |
509 | { |
510 | if (__end_ < __end_cap()) |
511 | { |
512 | difference_type __d = __end_cap() - __end_; |
513 | __d = (__d + 1) / 2; |
514 | __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); |
515 | __end_ += __d; |
516 | } |
517 | else |
518 | { |
519 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
520 | __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); |
521 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
522 | move_iterator<pointer>(__end_)); |
523 | _VSTD::swap(__first_, __t.__first_); |
524 | _VSTD::swap(__begin_, __t.__begin_); |
525 | _VSTD::swap(__end_, __t.__end_); |
526 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
527 | } |
528 | } |
529 | __alloc_traits::construct(__alloc(), _VSTD::__to_address(__begin_-1), |
530 | _VSTD::move(__x)); |
531 | --__begin_; |
532 | } |
533 | |
534 | #endif // _LIBCPP_CXX03_LANG |
535 | |
536 | template <class _Tp, class _Allocator> |
537 | inline _LIBCPP_INLINE_VISIBILITY |
538 | void |
539 | __split_buffer<_Tp, _Allocator>::push_back(const_reference __x) |
540 | { |
541 | if (__end_ == __end_cap()) |
542 | { |
543 | if (__begin_ > __first_) |
544 | { |
545 | difference_type __d = __begin_ - __first_; |
546 | __d = (__d + 1) / 2; |
547 | __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); |
548 | __begin_ -= __d; |
549 | } |
550 | else |
551 | { |
552 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
553 | __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); |
554 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
555 | move_iterator<pointer>(__end_)); |
556 | _VSTD::swap(__first_, __t.__first_); |
557 | _VSTD::swap(__begin_, __t.__begin_); |
558 | _VSTD::swap(__end_, __t.__end_); |
559 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
560 | } |
561 | } |
562 | __alloc_traits::construct(__alloc(), _VSTD::__to_address(__end_), __x); |
563 | ++__end_; |
564 | } |
565 | |
566 | #ifndef _LIBCPP_CXX03_LANG |
567 | |
568 | template <class _Tp, class _Allocator> |
569 | void |
570 | __split_buffer<_Tp, _Allocator>::push_back(value_type&& __x) |
571 | { |
572 | if (__end_ == __end_cap()) |
573 | { |
574 | if (__begin_ > __first_) |
575 | { |
576 | difference_type __d = __begin_ - __first_; |
577 | __d = (__d + 1) / 2; |
578 | __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); |
579 | __begin_ -= __d; |
580 | } |
581 | else |
582 | { |
583 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
584 | __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); |
585 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
586 | move_iterator<pointer>(__end_)); |
587 | _VSTD::swap(__first_, __t.__first_); |
588 | _VSTD::swap(__begin_, __t.__begin_); |
589 | _VSTD::swap(__end_, __t.__end_); |
590 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
591 | } |
592 | } |
593 | __alloc_traits::construct(__alloc(), _VSTD::__to_address(__end_), |
594 | _VSTD::move(__x)); |
595 | ++__end_; |
596 | } |
597 | |
598 | template <class _Tp, class _Allocator> |
599 | template <class... _Args> |
600 | void |
601 | __split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args) |
602 | { |
603 | if (__end_ == __end_cap()) |
604 | { |
605 | if (__begin_ > __first_) |
606 | { |
607 | difference_type __d = __begin_ - __first_; |
608 | __d = (__d + 1) / 2; |
609 | __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); |
610 | __begin_ -= __d; |
611 | } |
612 | else |
613 | { |
614 | size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); |
615 | __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); |
616 | __t.__construct_at_end(move_iterator<pointer>(__begin_), |
617 | move_iterator<pointer>(__end_)); |
618 | _VSTD::swap(__first_, __t.__first_); |
619 | _VSTD::swap(__begin_, __t.__begin_); |
620 | _VSTD::swap(__end_, __t.__end_); |
621 | _VSTD::swap(__end_cap(), __t.__end_cap()); |
622 | } |
623 | } |
624 | __alloc_traits::construct(__alloc(), _VSTD::__to_address(__end_), |
625 | _VSTD::forward<_Args>(__args)...); |
626 | ++__end_; |
627 | } |
628 | |
629 | #endif // _LIBCPP_CXX03_LANG |
630 | |
631 | template <class _Tp, class _Allocator> |
632 | inline _LIBCPP_INLINE_VISIBILITY |
633 | void |
634 | swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y) |
635 | _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
636 | { |
637 | __x.swap(__y); |
638 | } |
639 | |
640 | _LIBCPP_END_NAMESPACE_STD |
641 | |
642 | _LIBCPP_POP_MACROS |
643 | |
644 | #endif // _LIBCPP_SPLIT_BUFFER |
645 | |