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