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