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