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