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