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