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