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
36template <class _Tp, class _Allocator = allocator<_Tp> >
37struct __split_buffer
38{
39private:
40 __split_buffer(const __split_buffer&);
41 __split_buffer& operator=(const __split_buffer&);
42public:
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
148private:
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
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>
205void
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)
220template <class _Tp, class _Allocator>
221void
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
231template <class _Tp, class _Allocator>
232template <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
254template <class _Tp, class _Allocator>
255template <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
266template <class _Tp, class _Allocator>
267inline
268void
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
275template <class _Tp, class _Allocator>
276inline
277void
278__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type)
279{
280 __begin_ = __new_begin;
281}
282
283template <class _Tp, class _Allocator>
284inline _LIBCPP_INLINE_VISIBILITY
285void
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
292template <class _Tp, class _Allocator>
293inline _LIBCPP_INLINE_VISIBILITY
294void
295__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT
296{
297 __end_ = __new_last;
298}
299
300template <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
315template <class _Tp, class _Allocator>
316inline
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
323template <class _Tp, class _Allocator>
324inline
325__split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a)
326 : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a)
327{
328}
329
330template <class _Tp, class _Allocator>
331inline
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
337template <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
345template <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
359template <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
385template <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
405template <class _Tp, class _Allocator>
406void
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
418template <class _Tp, class _Allocator>
419void
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
434template <class _Tp, class _Allocator>
435void
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
461template <class _Tp, class _Allocator>
462void
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
490template <class _Tp, class _Allocator>
491void
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
520template <class _Tp, class _Allocator>
521inline _LIBCPP_INLINE_VISIBILITY
522void
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
550template <class _Tp, class _Allocator>
551void
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
580template <class _Tp, class _Allocator>
581template <class... _Args>
582void
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
611template <class _Tp, class _Allocator>
612inline _LIBCPP_INLINE_VISIBILITY
613void
614swap(__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

source code of flutter_engine/third_party/libcxx/include/__split_buffer