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