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