__split_buffer revision 288943
152419Sjulian// -*- C++ -*- 252419Sjulian#ifndef _LIBCPP_SPLIT_BUFFER 3139823Simp#define _LIBCPP_SPLIT_BUFFER 4139823Simp 5139823Simp#include <__config> 652419Sjulian#include <type_traits> 752419Sjulian#include <algorithm> 870700Sjulian 952419Sjulian#include <__undef_min_max> 1052419Sjulian 1152419Sjulian#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 1252419Sjulian#pragma GCC system_header 1352419Sjulian#endif 1452419Sjulian 1552419Sjulian_LIBCPP_BEGIN_NAMESPACE_STD 1652419Sjulian 1752419Sjuliantemplate <bool> 1852419Sjulianclass __split_buffer_common 1970700Sjulian{ 2052419Sjulianprotected: 2152419Sjulian void __throw_length_error() const; 2252419Sjulian void __throw_out_of_range() const; 2352419Sjulian}; 2452419Sjulian 2552419Sjuliantemplate <class _Tp, class _Allocator = allocator<_Tp> > 2652419Sjulianstruct __split_buffer 2752419Sjulian : private __split_buffer_common<true> 2852419Sjulian{ 2952419Sjulianprivate: 3052419Sjulian __split_buffer(const __split_buffer&); 3152419Sjulian __split_buffer& operator=(const __split_buffer&); 3252419Sjulianpublic: 3352419Sjulian typedef _Tp value_type; 3452419Sjulian typedef _Allocator allocator_type; 3552419Sjulian typedef typename remove_reference<allocator_type>::type __alloc_rr; 3652419Sjulian typedef allocator_traits<__alloc_rr> __alloc_traits; 3752419Sjulian typedef value_type& reference; 3867506Sjulian typedef const value_type& const_reference; 3967506Sjulian typedef typename __alloc_traits::size_type size_type; 4052419Sjulian typedef typename __alloc_traits::difference_type difference_type; 4152419Sjulian typedef typename __alloc_traits::pointer pointer; 4252419Sjulian typedef typename __alloc_traits::const_pointer const_pointer; 4352419Sjulian typedef pointer iterator; 4452419Sjulian typedef const_pointer const_iterator; 4552419Sjulian 4652419Sjulian pointer __first_; 4752419Sjulian pointer __begin_; 4852419Sjulian pointer __end_; 4952419Sjulian __compressed_pair<pointer, allocator_type> __end_cap_; 50139236Sglebius 51139235Sglebius typedef typename add_lvalue_reference<allocator_type>::type __alloc_ref; 5252419Sjulian typedef typename add_lvalue_reference<allocator_type>::type __alloc_const_ref; 53131933Smarcel 5452419Sjulian _LIBCPP_INLINE_VISIBILITY __alloc_rr& __alloc() _NOEXCEPT {return __end_cap_.second();} 55114216Skan _LIBCPP_INLINE_VISIBILITY const __alloc_rr& __alloc() const _NOEXCEPT {return __end_cap_.second();} 5652419Sjulian _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() _NOEXCEPT {return __end_cap_.first();} 57139235Sglebius _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const _NOEXCEPT {return __end_cap_.first();} 5852419Sjulian 5972946Sjulian __split_buffer() 60139235Sglebius _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 6152419Sjulian explicit __split_buffer(__alloc_rr& __a); 6252419Sjulian explicit __split_buffer(const __alloc_rr& __a); 6352419Sjulian __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a); 6452419Sjulian ~__split_buffer(); 6552419Sjulian 6653913Sarchie#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 6752419Sjulian __split_buffer(__split_buffer&& __c) 6872053Sjulian _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 6959756Speter __split_buffer(__split_buffer&& __c, const __alloc_rr& __a); 7070784Sjulian __split_buffer& operator=(__split_buffer&& __c) 7170700Sjulian _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && 7270700Sjulian is_nothrow_move_assignable<allocator_type>::value) || 7352419Sjulian !__alloc_traits::propagate_on_container_move_assignment::value); 7470784Sjulian#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 75146212Sglebius 7670784Sjulian _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __begin_;} 7770784Sjulian _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __begin_;} 7870784Sjulian _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __end_;} 7970784Sjulian _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __end_;} 8070784Sjulian 8170784Sjulian _LIBCPP_INLINE_VISIBILITY 8270784Sjulian void clear() _NOEXCEPT 8370784Sjulian {__destruct_at_end(__begin_);} 8470784Sjulian _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(__end_ - __begin_);} 8570784Sjulian _LIBCPP_INLINE_VISIBILITY bool empty() const {return __end_ == __begin_;} 8670784Sjulian _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __first_);} 8770935Sjulian _LIBCPP_INLINE_VISIBILITY size_type __front_spare() const {return static_cast<size_type>(__begin_ - __first_);} 8870935Sjulian _LIBCPP_INLINE_VISIBILITY size_type __back_spare() const {return static_cast<size_type>(__end_cap() - __end_);} 8970935Sjulian 9070935Sjulian _LIBCPP_INLINE_VISIBILITY reference front() {return *__begin_;} 9170935Sjulian _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *__begin_;} 9270935Sjulian _LIBCPP_INLINE_VISIBILITY reference back() {return *(__end_ - 1);} 9370935Sjulian _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(__end_ - 1);} 9470935Sjulian 9570935Sjulian void reserve(size_type __n); 9670935Sjulian void shrink_to_fit() _NOEXCEPT; 9770935Sjulian void push_front(const_reference __x); 9870935Sjulian _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); 9970935Sjulian#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 10070935Sjulian void push_front(value_type&& __x); 10170935Sjulian void push_back(value_type&& __x); 10270935Sjulian#if !defined(_LIBCPP_HAS_NO_VARIADICS) 10370935Sjulian template <class... _Args> 10470935Sjulian void emplace_back(_Args&&... __args); 10570935Sjulian#endif // !defined(_LIBCPP_HAS_NO_VARIADICS) 10670935Sjulian#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 10770784Sjulian 10870935Sjulian _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);} 10970935Sjulian _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);} 11070935Sjulian 111132464Sjulian void __construct_at_end(size_type __n); 11270935Sjulian void __construct_at_end(size_type __n, const_reference __x); 11370935Sjulian template <class _InputIter> 11470935Sjulian typename enable_if 11570935Sjulian < 11670935Sjulian __is_input_iterator<_InputIter>::value && 11770935Sjulian !__is_forward_iterator<_InputIter>::value, 11870935Sjulian void 11970935Sjulian >::type 12070935Sjulian __construct_at_end(_InputIter __first, _InputIter __last); 12170935Sjulian template <class _ForwardIterator> 12270935Sjulian typename enable_if 12370935Sjulian < 12470935Sjulian __is_forward_iterator<_ForwardIterator>::value, 12570935Sjulian void 12670935Sjulian >::type 12770935Sjulian __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 12870935Sjulian 12970935Sjulian _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin) 13070935Sjulian {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());} 13170935Sjulian void __destruct_at_begin(pointer __new_begin, false_type); 13270935Sjulian void __destruct_at_begin(pointer __new_begin, true_type); 13370935Sjulian 13470935Sjulian _LIBCPP_INLINE_VISIBILITY 13570935Sjulian void __destruct_at_end(pointer __new_last) _NOEXCEPT 13670935Sjulian {__destruct_at_end(__new_last, false_type());} 13770935Sjulian _LIBCPP_INLINE_VISIBILITY 13870935Sjulian void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT; 139148261Sglebius _LIBCPP_INLINE_VISIBILITY 14070935Sjulian void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT; 14170935Sjulian 14270935Sjulian void swap(__split_buffer& __x) 14371885Sjulian _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 14471885Sjulian __is_nothrow_swappable<__alloc_rr>::value); 14570935Sjulian 14670935Sjulian bool __invariants() const; 14770935Sjulian 14870935Sjulianprivate: 14970935Sjulian _LIBCPP_INLINE_VISIBILITY 15070935Sjulian void __move_assign_alloc(__split_buffer& __c, true_type) 15170935Sjulian _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 15270935Sjulian { 15370935Sjulian __alloc() = _VSTD::move(__c.__alloc()); 15470935Sjulian } 15570935Sjulian 15670700Sjulian _LIBCPP_INLINE_VISIBILITY 15770700Sjulian void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT 15871902Sjulian {} 15970700Sjulian}; 16052419Sjulian 16170700Sjuliantemplate <class _Tp, class _Allocator> 16270700Sjulianbool 16352419Sjulian__split_buffer<_Tp, _Allocator>::__invariants() const 16470700Sjulian{ 16571354Sjulian if (__first_ == nullptr) 16671354Sjulian { 16771354Sjulian if (__begin_ != nullptr) 16870700Sjulian return false; 16971354Sjulian if (__end_ != nullptr) 17071354Sjulian return false; 17171354Sjulian if (__end_cap() != nullptr) 17271354Sjulian return false; 173131008Srwatson } 17471354Sjulian else 17571354Sjulian { 17671354Sjulian if (__begin_ < __first_) 17771354Sjulian return false; 17871354Sjulian if (__end_ < __begin_) 17971354Sjulian return false; 18071354Sjulian if (__end_cap() < __end_) 18171354Sjulian return false; 18252722Sjulian } 18370700Sjulian return true; 18452419Sjulian} 18552419Sjulian 18670700Sjulian// Default constructs __n objects starting at __end_ 18752722Sjulian// throws if construction throws 18852419Sjulian// Precondition: __n > 0 18970700Sjulian// Precondition: size() + __n <= capacity() 19052419Sjulian// Postcondition: size() == size() + __n 19174078Sjuliantemplate <class _Tp, class _Allocator> 19270700Sjulianvoid 19370700Sjulian__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) 19470700Sjulian{ 19571047Sjulian __alloc_rr& __a = this->__alloc(); 19671047Sjulian do 19771849Sjulian { 19871849Sjulian __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); 19971047Sjulian ++this->__end_; 20071047Sjulian --__n; 20152419Sjulian } while (__n > 0); 20270784Sjulian} 20370700Sjulian 20470700Sjulian// Copy constructs __n objects starting at __end_ from __x 20570700Sjulian// throws if construction throws 20670700Sjulian// Precondition: __n > 0 20770700Sjulian// Precondition: size() + __n <= capacity() 20870700Sjulian// Postcondition: size() == old size() + __n 20971849Sjulian// Postcondition: [i] == __x for all i in [size() - __n, __n) 21070784Sjuliantemplate <class _Tp, class _Allocator> 21170700Sjulianvoid 21270700Sjulian__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) 21352419Sjulian{ 21452419Sjulian __alloc_rr& __a = this->__alloc(); 21570700Sjulian do 21670700Sjulian { 21770700Sjulian __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); 21870700Sjulian ++this->__end_; 21952419Sjulian --__n; 22070700Sjulian } while (__n > 0); 22170784Sjulian} 22270784Sjulian 22370784Sjuliantemplate <class _Tp, class _Allocator> 22470784Sjuliantemplate <class _InputIter> 22570784Sjuliantypename enable_if 22670784Sjulian< 22770784Sjulian __is_input_iterator<_InputIter>::value && 22870784Sjulian !__is_forward_iterator<_InputIter>::value, 22970784Sjulian void 23070784Sjulian>::type 23170784Sjulian__split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last) 23270784Sjulian{ 23370784Sjulian __alloc_rr& __a = this->__alloc(); 23470784Sjulian for (; __first != __last; ++__first) 23570784Sjulian { 23670784Sjulian if (__end_ == __end_cap()) 23770784Sjulian { 23870784Sjulian size_type __old_cap = __end_cap() - __first_; 23970784Sjulian size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8); 24070784Sjulian __split_buffer __buf(__new_cap, 0, __a); 24172200Sbmilekic for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_) 24270784Sjulian __alloc_traits::construct(__buf.__alloc(), 24370784Sjulian _VSTD::__to_raw_pointer(__buf.__end_), _VSTD::move(*__p)); 24470784Sjulian swap(__buf); 24570784Sjulian } 24670784Sjulian __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 24770784Sjulian ++this->__end_; 24872200Sbmilekic } 24970784Sjulian} 25070784Sjulian 25172200Sbmilekictemplate <class _Tp, class _Allocator> 25270784Sjuliantemplate <class _ForwardIterator> 25370784Sjuliantypename enable_if 25470784Sjulian< 25572200Sbmilekic __is_forward_iterator<_ForwardIterator>::value, 25670784Sjulian void 25772200Sbmilekic>::type 25870784Sjulian__split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 25970784Sjulian{ 26070784Sjulian __alloc_rr& __a = this->__alloc(); 26170784Sjulian for (; __first != __last; ++__first) 26270784Sjulian { 26370784Sjulian __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 26470784Sjulian ++this->__end_; 26570784Sjulian } 26670784Sjulian} 26770784Sjulian 26872200Sbmilekictemplate <class _Tp, class _Allocator> 26970784Sjulianinline _LIBCPP_INLINE_VISIBILITY 27070784Sjulianvoid 27170784Sjulian__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) 27270784Sjulian{ 27370784Sjulian while (__begin_ != __new_begin) 27470784Sjulian __alloc_traits::destroy(__alloc(), __to_raw_pointer(__begin_++)); 27572200Sbmilekic} 27670784Sjulian 27770784Sjuliantemplate <class _Tp, class _Allocator> 27872200Sbmilekicinline _LIBCPP_INLINE_VISIBILITY 27970784Sjulianvoid 28070784Sjulian__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) 28170784Sjulian{ 28272200Sbmilekic __begin_ = __new_begin; 28370784Sjulian} 28472200Sbmilekic 28570784Sjuliantemplate <class _Tp, class _Allocator> 28670784Sjulianinline _LIBCPP_INLINE_VISIBILITY 28770784Sjulianvoid 28870784Sjulian__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT 28970784Sjulian{ 29070784Sjulian while (__new_last != __end_) 29170784Sjulian __alloc_traits::destroy(__alloc(), __to_raw_pointer(--__end_)); 29270784Sjulian} 29370784Sjulian 29470784Sjuliantemplate <class _Tp, class _Allocator> 29570784Sjulianinline _LIBCPP_INLINE_VISIBILITY 29672200Sbmilekicvoid 29770784Sjulian__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT 29870784Sjulian{ 29972200Sbmilekic __end_ = __new_last; 30070784Sjulian} 30170784Sjulian 30270784Sjuliantemplate <class _Tp, class _Allocator> 30370784Sjulian__split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a) 30472200Sbmilekic : __end_cap_(nullptr, __a) 30570784Sjulian{ 30670784Sjulian __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr; 30772200Sbmilekic __begin_ = __end_ = __first_ + __start; 30870784Sjulian __end_cap() = __first_ + __cap; 30970784Sjulian} 31070784Sjulian 31170784Sjuliantemplate <class _Tp, class _Allocator> 31270784Sjulianinline _LIBCPP_INLINE_VISIBILITY 31370784Sjulian__split_buffer<_Tp, _Allocator>::__split_buffer() 31470784Sjulian _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 31570700Sjulian : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr) 31670700Sjulian{ 31770784Sjulian} 31870784Sjulian 31970784Sjuliantemplate <class _Tp, class _Allocator> 320131933Smarcelinline _LIBCPP_INLINE_VISIBILITY 32152419Sjulian__split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a) 32271047Sjulian : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) 32352419Sjulian{ 32452419Sjulian} 32552722Sjulian 32652722Sjuliantemplate <class _Tp, class _Allocator> 32753403Sarchieinline _LIBCPP_INLINE_VISIBILITY 32853403Sarchie__split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a) 32953403Sarchie : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) 33053403Sarchie{ 33153403Sarchie} 332113255Sdes 33353403Sarchietemplate <class _Tp, class _Allocator> 33453403Sarchie__split_buffer<_Tp, _Allocator>::~__split_buffer() 33553403Sarchie{ 33653403Sarchie clear(); 33787599Sobrien if (__first_) 33853403Sarchie __alloc_traits::deallocate(__alloc(), __first_, capacity()); 33953403Sarchie} 34053403Sarchie 34153403Sarchie#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 34253403Sarchie 34352722Sjuliantemplate <class _Tp, class _Allocator> 34453403Sarchie__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c) 34552419Sjulian _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 34653913Sarchie : __first_(_VSTD::move(__c.__first_)), 34753913Sarchie __begin_(_VSTD::move(__c.__begin_)), 34853913Sarchie __end_(_VSTD::move(__c.__end_)), 34953913Sarchie __end_cap_(_VSTD::move(__c.__end_cap_)) 35053913Sarchie{ 35197685Sarchie __c.__first_ = nullptr; 35297685Sarchie __c.__begin_ = nullptr; 35353913Sarchie __c.__end_ = nullptr; 35453913Sarchie __c.__end_cap() = nullptr; 35597685Sarchie} 35653913Sarchie 35753913Sarchietemplate <class _Tp, class _Allocator> 35853913Sarchie__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a) 35953913Sarchie : __end_cap_(__a) 36053913Sarchie{ 36153913Sarchie if (__a == __c.__alloc()) 36253913Sarchie { 36353913Sarchie __first_ = __c.__first_; 36453913Sarchie __begin_ = __c.__begin_; 36553913Sarchie __end_ = __c.__end_; 36653913Sarchie __end_cap() = __c.__end_cap(); 36772645Sasmodai __c.__first_ = nullptr; 36853913Sarchie __c.__begin_ = nullptr; 36953913Sarchie __c.__end_ = nullptr; 37053913Sarchie __c.__end_cap() = nullptr; 37153913Sarchie } 37253913Sarchie else 37353913Sarchie { 37453913Sarchie size_type __cap = __c.size(); 37553913Sarchie __first_ = __alloc_traits::allocate(__alloc(), __cap); 37653913Sarchie __begin_ = __end_ = __first_; 37753913Sarchie __end_cap() = __first_ + __cap; 37853913Sarchie typedef move_iterator<iterator> _Ip; 37953913Sarchie __construct_at_end(_Ip(__c.begin()), _Ip(__c.end())); 38053913Sarchie } 38153913Sarchie} 38253913Sarchie 38353913Sarchietemplate <class _Tp, class _Allocator> 38453913Sarchie__split_buffer<_Tp, _Allocator>& 38553913Sarchie__split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c) 38653913Sarchie _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && 38753913Sarchie is_nothrow_move_assignable<allocator_type>::value) || 38853913Sarchie !__alloc_traits::propagate_on_container_move_assignment::value) 38953913Sarchie{ 39053913Sarchie clear(); 39153913Sarchie shrink_to_fit(); 39253913Sarchie __first_ = __c.__first_; 39353913Sarchie __begin_ = __c.__begin_; 39453913Sarchie __end_ = __c.__end_; 39553913Sarchie __end_cap() = __c.__end_cap(); 39653913Sarchie __move_assign_alloc(__c, 39753913Sarchie integral_constant<bool, 39853913Sarchie __alloc_traits::propagate_on_container_move_assignment::value>()); 39953913Sarchie __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 40053913Sarchie return *this; 40153913Sarchie} 40253913Sarchie 40353913Sarchie#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 40453913Sarchie 40553913Sarchietemplate <class _Tp, class _Allocator> 40653913Sarchievoid 40753913Sarchie__split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x) 40853913Sarchie _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 40953913Sarchie __is_nothrow_swappable<__alloc_rr>::value) 41053913Sarchie{ 41153913Sarchie _VSTD::swap(__first_, __x.__first_); 41253913Sarchie _VSTD::swap(__begin_, __x.__begin_); 41353913Sarchie _VSTD::swap(__end_, __x.__end_); 41453913Sarchie _VSTD::swap(__end_cap(), __x.__end_cap()); 41553913Sarchie __swap_allocator(__alloc(), __x.__alloc()); 41653913Sarchie} 41753913Sarchie 41853913Sarchietemplate <class _Tp, class _Allocator> 41953913Sarchievoid 42053913Sarchie__split_buffer<_Tp, _Allocator>::reserve(size_type __n) 42153913Sarchie{ 42253913Sarchie if (__n < capacity()) 42353913Sarchie { 42453913Sarchie __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc()); 42553913Sarchie __t.__construct_at_end(move_iterator<pointer>(__begin_), 42653913Sarchie move_iterator<pointer>(__end_)); 42753913Sarchie _VSTD::swap(__first_, __t.__first_); 42853913Sarchie _VSTD::swap(__begin_, __t.__begin_); 42953913Sarchie _VSTD::swap(__end_, __t.__end_); 43053913Sarchie _VSTD::swap(__end_cap(), __t.__end_cap()); 43153913Sarchie } 43253913Sarchie} 43353913Sarchie 43453913Sarchietemplate <class _Tp, class _Allocator> 43553913Sarchievoid 43653913Sarchie__split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 43753913Sarchie{ 43853913Sarchie if (capacity() > size()) 43953913Sarchie { 44053913Sarchie#ifndef _LIBCPP_NO_EXCEPTIONS 44153913Sarchie try 44253913Sarchie { 44353913Sarchie#endif // _LIBCPP_NO_EXCEPTIONS 44453913Sarchie __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc()); 44553913Sarchie __t.__construct_at_end(move_iterator<pointer>(__begin_), 44653913Sarchie move_iterator<pointer>(__end_)); 44753913Sarchie __t.__end_ = __t.__begin_ + (__end_ - __begin_); 44853913Sarchie _VSTD::swap(__first_, __t.__first_); 44953913Sarchie _VSTD::swap(__begin_, __t.__begin_); 45053913Sarchie _VSTD::swap(__end_, __t.__end_); 45153913Sarchie _VSTD::swap(__end_cap(), __t.__end_cap()); 45253913Sarchie#ifndef _LIBCPP_NO_EXCEPTIONS 45353913Sarchie } 45453913Sarchie catch (...) 45553913Sarchie { 45653913Sarchie } 45753913Sarchie#endif // _LIBCPP_NO_EXCEPTIONS 45853913Sarchie } 45953913Sarchie} 46053913Sarchie 46153913Sarchietemplate <class _Tp, class _Allocator> 46253913Sarchievoid 46353913Sarchie__split_buffer<_Tp, _Allocator>::push_front(const_reference __x) 46453913Sarchie{ 46553913Sarchie if (__begin_ == __first_) 46653913Sarchie { 46753913Sarchie if (__end_ < __end_cap()) 46853913Sarchie { 46953913Sarchie difference_type __d = __end_cap() - __end_; 47053913Sarchie __d = (__d + 1) / 2; 47153913Sarchie __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); 47253913Sarchie __end_ += __d; 47353913Sarchie } 47453913Sarchie else 47553913Sarchie { 47653913Sarchie size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 47753913Sarchie __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); 47853913Sarchie __t.__construct_at_end(move_iterator<pointer>(__begin_), 47953913Sarchie move_iterator<pointer>(__end_)); 48053913Sarchie _VSTD::swap(__first_, __t.__first_); 48153913Sarchie _VSTD::swap(__begin_, __t.__begin_); 48253913Sarchie _VSTD::swap(__end_, __t.__end_); 48353913Sarchie _VSTD::swap(__end_cap(), __t.__end_cap()); 48453913Sarchie } 48553913Sarchie } 48653913Sarchie __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x); 48753913Sarchie --__begin_; 48853913Sarchie} 48953913Sarchie 49053913Sarchie#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 49153913Sarchie 49253913Sarchietemplate <class _Tp, class _Allocator> 49353913Sarchievoid 49453913Sarchie__split_buffer<_Tp, _Allocator>::push_front(value_type&& __x) 49553913Sarchie{ 49662471Sphk if (__begin_ == __first_) 49762471Sphk { 49862471Sphk if (__end_ < __end_cap()) 49962471Sphk { 50062471Sphk difference_type __d = __end_cap() - __end_; 50162471Sphk __d = (__d + 1) / 2; 50262471Sphk __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); 50353913Sarchie __end_ += __d; 50453913Sarchie } 50553913Sarchie else 50653913Sarchie { 50753913Sarchie size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 50853913Sarchie __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); 50953913Sarchie __t.__construct_at_end(move_iterator<pointer>(__begin_), 51053913Sarchie move_iterator<pointer>(__end_)); 51153913Sarchie _VSTD::swap(__first_, __t.__first_); 51253913Sarchie _VSTD::swap(__begin_, __t.__begin_); 51353913Sarchie _VSTD::swap(__end_, __t.__end_); 51453913Sarchie _VSTD::swap(__end_cap(), __t.__end_cap()); 51553913Sarchie } 51653913Sarchie } 51753913Sarchie __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), 51853913Sarchie _VSTD::move(__x)); 51953913Sarchie --__begin_; 52053913Sarchie} 52153913Sarchie 52253913Sarchie#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 52353913Sarchie 52453913Sarchietemplate <class _Tp, class _Allocator> 52553913Sarchieinline _LIBCPP_INLINE_VISIBILITY 52652419Sjulianvoid 52752419Sjulian__split_buffer<_Tp, _Allocator>::push_back(const_reference __x) 52852419Sjulian{ 52952419Sjulian if (__end_ == __end_cap()) 53052419Sjulian { 53152419Sjulian if (__begin_ > __first_) 53252419Sjulian { 53352419Sjulian difference_type __d = __begin_ - __first_; 53452419Sjulian __d = (__d + 1) / 2; 53552419Sjulian __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 53670700Sjulian __begin_ -= __d; 53752419Sjulian } 53852419Sjulian else 53952419Sjulian { 54071047Sjulian size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 54152419Sjulian __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 54252419Sjulian __t.__construct_at_end(move_iterator<pointer>(__begin_), 54352419Sjulian move_iterator<pointer>(__end_)); 544132705Sglebius _VSTD::swap(__first_, __t.__first_); 545132705Sglebius _VSTD::swap(__begin_, __t.__begin_); 546132705Sglebius _VSTD::swap(__end_, __t.__end_); 547132705Sglebius _VSTD::swap(__end_cap(), __t.__end_cap()); 548132705Sglebius } 54952419Sjulian } 55070700Sjulian __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), __x); 55170700Sjulian ++__end_; 55270700Sjulian} 55370700Sjulian 55470700Sjulian#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 55570700Sjulian 55670700Sjuliantemplate <class _Tp, class _Allocator> 55770784Sjulianvoid 55870700Sjulian__split_buffer<_Tp, _Allocator>::push_back(value_type&& __x) 55970700Sjulian{ 56070700Sjulian if (__end_ == __end_cap()) 56170700Sjulian { 56270700Sjulian if (__begin_ > __first_) 56370700Sjulian { 56470935Sjulian difference_type __d = __begin_ - __first_; 56570700Sjulian __d = (__d + 1) / 2; 56670700Sjulian __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 56770700Sjulian __begin_ -= __d; 56871047Sjulian } 56970700Sjulian else 57070700Sjulian { 57170700Sjulian size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 57252419Sjulian __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 57352419Sjulian __t.__construct_at_end(move_iterator<pointer>(__begin_), 57452419Sjulian move_iterator<pointer>(__end_)); 57570700Sjulian _VSTD::swap(__first_, __t.__first_); 57670700Sjulian _VSTD::swap(__begin_, __t.__begin_); 57752419Sjulian _VSTD::swap(__end_, __t.__end_); 57852419Sjulian _VSTD::swap(__end_cap(), __t.__end_cap()); 57952419Sjulian } 58052419Sjulian } 58152419Sjulian __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), 58252419Sjulian _VSTD::move(__x)); 58352419Sjulian ++__end_; 58452419Sjulian} 58552419Sjulian 58671047Sjulian#ifndef _LIBCPP_HAS_NO_VARIADICS 58752419Sjulian 58852419Sjuliantemplate <class _Tp, class _Allocator> 58952419Sjuliantemplate <class... _Args> 59052419Sjulianvoid 59170784Sjulian__split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args) 59252419Sjulian{ 59371047Sjulian if (__end_ == __end_cap()) 59452419Sjulian { 59552419Sjulian if (__begin_ > __first_) 59670784Sjulian { 59770784Sjulian difference_type __d = __begin_ - __first_; 59852419Sjulian __d = (__d + 1) / 2; 59952419Sjulian __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 60093818Sjhb __begin_ -= __d; 60170784Sjulian } 60270784Sjulian else 60370784Sjulian { 60470784Sjulian size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 60552419Sjulian __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 60652419Sjulian __t.__construct_at_end(move_iterator<pointer>(__begin_), 60770784Sjulian move_iterator<pointer>(__end_)); 60852419Sjulian _VSTD::swap(__first_, __t.__first_); 60970700Sjulian _VSTD::swap(__begin_, __t.__begin_); 61072200Sbmilekic _VSTD::swap(__end_, __t.__end_); 61170784Sjulian _VSTD::swap(__end_cap(), __t.__end_cap()); 61272200Sbmilekic } 61370700Sjulian } 61470700Sjulian __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), 61552722Sjulian _VSTD::forward<_Args>(__args)...); 61672200Sbmilekic ++__end_; 61770784Sjulian} 61870700Sjulian 61970784Sjulian#endif // _LIBCPP_HAS_NO_VARIADICS 62071354Sjulian 62170784Sjulian#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 62271354Sjulian 62371354Sjuliantemplate <class _Tp, class _Allocator> 62470784Sjulianinline _LIBCPP_INLINE_VISIBILITY 62570700Sjulianvoid 62670784Sjulianswap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y) 62771354Sjulian _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 62870784Sjulian{ 62972200Sbmilekic __x.swap(__y); 63052722Sjulian} 63152419Sjulian 63252419Sjulian 63352419Sjulian_LIBCPP_END_NAMESPACE_STD 63452419Sjulian 63552419Sjulian#endif // _LIBCPP_SPLIT_BUFFER 63652419Sjulian