__split_buffer revision 287679
16418Ssherman// -*- C++ -*- 211354Sdfuchs#ifndef _LIBCPP_SPLIT_BUFFER 36418Ssherman#define _LIBCPP_SPLIT_BUFFER 46418Ssherman 56418Ssherman#include <__config> 66418Ssherman#include <type_traits> 76418Ssherman#include <algorithm> 86418Ssherman 96418Ssherman#include <__undef_min_max> 106418Ssherman 116418Ssherman#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 126418Ssherman#pragma GCC system_header 136418Ssherman#endif 146418Ssherman 156418Ssherman_LIBCPP_BEGIN_NAMESPACE_STD 166418Ssherman 176418Sshermantemplate <bool> 186418Sshermanclass __split_buffer_common 196418Ssherman{ 206418Sshermanprotected: 216418Ssherman void __throw_length_error() const; 226418Ssherman void __throw_out_of_range() const; 236418Ssherman}; 246418Ssherman 256418Sshermantemplate <class _Tp, class _Allocator = allocator<_Tp> > 266418Sshermanstruct __split_buffer 276418Ssherman : private __split_buffer_common<true> 286418Ssherman{ 296418Sshermanprivate: 306418Ssherman __split_buffer(const __split_buffer&); 316418Ssherman __split_buffer& operator=(const __split_buffer&); 326418Sshermanpublic: 336418Ssherman typedef _Tp value_type; 346418Ssherman typedef _Allocator allocator_type; 356418Ssherman typedef typename remove_reference<allocator_type>::type __alloc_rr; 366418Ssherman typedef allocator_traits<__alloc_rr> __alloc_traits; 376418Ssherman typedef value_type& reference; 386418Ssherman typedef const value_type& const_reference; 396418Ssherman typedef typename __alloc_traits::size_type size_type; 406418Ssherman typedef typename __alloc_traits::difference_type difference_type; 416418Ssherman typedef typename __alloc_traits::pointer pointer; 426418Ssherman typedef typename __alloc_traits::const_pointer const_pointer; 436418Ssherman typedef pointer iterator; 446418Ssherman typedef const_pointer const_iterator; 456418Ssherman 466418Ssherman pointer __first_; 476418Ssherman pointer __begin_; 486418Ssherman pointer __end_; 496418Ssherman __compressed_pair<pointer, allocator_type> __end_cap_; 506418Ssherman 516418Ssherman typedef typename add_lvalue_reference<allocator_type>::type __alloc_ref; 526418Ssherman typedef typename add_lvalue_reference<allocator_type>::type __alloc_const_ref; 536418Ssherman 546418Ssherman _LIBCPP_INLINE_VISIBILITY __alloc_rr& __alloc() _NOEXCEPT {return __end_cap_.second();} 556418Ssherman _LIBCPP_INLINE_VISIBILITY const __alloc_rr& __alloc() const _NOEXCEPT {return __end_cap_.second();} 566418Ssherman _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() _NOEXCEPT {return __end_cap_.first();} 576418Ssherman _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const _NOEXCEPT {return __end_cap_.first();} 586418Ssherman 596418Ssherman __split_buffer() 606418Ssherman _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 616418Ssherman explicit __split_buffer(__alloc_rr& __a); 626418Ssherman explicit __split_buffer(const __alloc_rr& __a); 636418Ssherman __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a); 646418Ssherman ~__split_buffer(); 656418Ssherman 666418Ssherman#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 676418Ssherman __split_buffer(__split_buffer&& __c) 686418Ssherman _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 696418Ssherman __split_buffer(__split_buffer&& __c, const __alloc_rr& __a); 706418Ssherman __split_buffer& operator=(__split_buffer&& __c) 716418Ssherman _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && 726418Ssherman is_nothrow_move_assignable<allocator_type>::value) || 736418Ssherman !__alloc_traits::propagate_on_container_move_assignment::value); 746418Ssherman#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 756418Ssherman 766418Ssherman _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __begin_;} 776418Ssherman _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __begin_;} 786418Ssherman _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __end_;} 796418Ssherman _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __end_;} 806418Ssherman 816418Ssherman _LIBCPP_INLINE_VISIBILITY 826418Ssherman void clear() _NOEXCEPT 836418Ssherman {__destruct_at_end(__begin_);} 846418Ssherman _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(__end_ - __begin_);} 856418Ssherman _LIBCPP_INLINE_VISIBILITY bool empty() const {return __end_ == __begin_;} 866418Ssherman _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __first_);} 876418Ssherman _LIBCPP_INLINE_VISIBILITY size_type __front_spare() const {return static_cast<size_type>(__begin_ - __first_);} 886897Ssherman _LIBCPP_INLINE_VISIBILITY size_type __back_spare() const {return static_cast<size_type>(__end_cap() - __end_);} 896418Ssherman 906418Ssherman _LIBCPP_INLINE_VISIBILITY reference front() {return *__begin_;} 916418Ssherman _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *__begin_;} 926418Ssherman _LIBCPP_INLINE_VISIBILITY reference back() {return *(__end_ - 1);} 936418Ssherman _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(__end_ - 1);} 946418Ssherman 956418Ssherman void reserve(size_type __n); 966418Ssherman void shrink_to_fit() _NOEXCEPT; 976418Ssherman void push_front(const_reference __x); 986418Ssherman _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); 996418Ssherman#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 1006418Ssherman void push_front(value_type&& __x); 1016418Ssherman void push_back(value_type&& __x); 1026418Ssherman#if !defined(_LIBCPP_HAS_NO_VARIADICS) 1036418Ssherman template <class... _Args> 1046897Ssherman void emplace_back(_Args&&... __args); 1056897Ssherman#endif // !defined(_LIBCPP_HAS_NO_VARIADICS) 1066897Ssherman#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 1076897Ssherman 1086897Ssherman _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);} 1096897Ssherman _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);} 1106897Ssherman 1116897Ssherman void __construct_at_end(size_type __n); 1126897Ssherman void __construct_at_end(size_type __n, const_reference __x); 1136897Ssherman template <class _InputIter> 1146897Ssherman typename enable_if 1156897Ssherman < 1166897Ssherman __is_input_iterator<_InputIter>::value && 1176897Ssherman !__is_forward_iterator<_InputIter>::value, 1186897Ssherman void 1196897Ssherman >::type 1206897Ssherman __construct_at_end(_InputIter __first, _InputIter __last); 1216897Ssherman template <class _ForwardIterator> 1226897Ssherman typename enable_if 1236897Ssherman < 1246897Ssherman __is_forward_iterator<_ForwardIterator>::value, 1256897Ssherman void 1266897Ssherman >::type 1276897Ssherman __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 1286897Ssherman 1298390Srriggs _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin) 1306897Ssherman {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());} 1317716Ssherman void __destruct_at_begin(pointer __new_begin, false_type); 1326418Ssherman void __destruct_at_begin(pointer __new_begin, true_type); 1336418Ssherman 1346418Ssherman _LIBCPP_INLINE_VISIBILITY 1356418Ssherman void __destruct_at_end(pointer __new_last) _NOEXCEPT 1366418Ssherman {__destruct_at_end(__new_last, false_type());} 1376418Ssherman _LIBCPP_INLINE_VISIBILITY 1386418Ssherman void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT; 1396418Ssherman _LIBCPP_INLINE_VISIBILITY 1406418Ssherman void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT; 1416418Ssherman 1426418Ssherman void swap(__split_buffer& __x) 1436418Ssherman _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 1446418Ssherman __is_nothrow_swappable<__alloc_rr>::value); 1456418Ssherman 1466418Ssherman bool __invariants() const; 1476418Ssherman 1486418Sshermanprivate: 1496418Ssherman _LIBCPP_INLINE_VISIBILITY 1506418Ssherman void __move_assign_alloc(__split_buffer& __c, true_type) 1516418Ssherman _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1526418Ssherman { 1536418Ssherman __alloc() = _VSTD::move(__c.__alloc()); 1546418Ssherman } 1556418Ssherman 1566418Ssherman _LIBCPP_INLINE_VISIBILITY 1576418Ssherman void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT 1586418Ssherman {} 1596418Ssherman 1606418Ssherman _LIBCPP_INLINE_VISIBILITY 1616418Ssherman static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y) 1626418Ssherman _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 1636897Ssherman __is_nothrow_swappable<__alloc_rr>::value) 1646418Ssherman {__swap_alloc(__x, __y, integral_constant<bool, 1656418Ssherman __alloc_traits::propagate_on_container_swap::value>());} 1666418Ssherman 1676418Ssherman _LIBCPP_INLINE_VISIBILITY 1686418Ssherman static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y, true_type) 1696418Ssherman _NOEXCEPT_(__is_nothrow_swappable<__alloc_rr>::value) 1706418Ssherman { 1716418Ssherman using _VSTD::swap; 1726418Ssherman swap(__x, __y); 1736418Ssherman } 1746418Ssherman 1756418Ssherman _LIBCPP_INLINE_VISIBILITY 1766418Ssherman static void __swap_alloc(__alloc_rr&, __alloc_rr&, false_type) _NOEXCEPT 1776418Ssherman {} 1786418Ssherman}; 1796418Ssherman 1806418Sshermantemplate <class _Tp, class _Allocator> 1816418Sshermanbool 1826418Ssherman__split_buffer<_Tp, _Allocator>::__invariants() const 1836418Ssherman{ 1846418Ssherman if (__first_ == nullptr) 1856418Ssherman { 1866418Ssherman if (__begin_ != nullptr) 1876418Ssherman return false; 1886418Ssherman if (__end_ != nullptr) 1896418Ssherman return false; 1906418Ssherman if (__end_cap() != nullptr) 1916418Ssherman return false; 1926418Ssherman } 1936418Ssherman else 1946418Ssherman { 1956418Ssherman if (__begin_ < __first_) 1966418Ssherman return false; 1976418Ssherman if (__end_ < __begin_) 1986418Ssherman return false; 1996418Ssherman if (__end_cap() < __end_) 2006418Ssherman return false; 2016418Ssherman } 2026418Ssherman return true; 2036418Ssherman} 2046418Ssherman 2056418Ssherman// Default constructs __n objects starting at __end_ 2066897Ssherman// throws if construction throws 2076418Ssherman// Precondition: __n > 0 2086418Ssherman// Precondition: size() + __n <= capacity() 2096418Ssherman// Postcondition: size() == size() + __n 2106418Sshermantemplate <class _Tp, class _Allocator> 2116418Sshermanvoid 2126418Ssherman__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) 2136418Ssherman{ 2146418Ssherman __alloc_rr& __a = this->__alloc(); 2156418Ssherman do 2166418Ssherman { 2176418Ssherman __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); 2186418Ssherman ++this->__end_; 2196418Ssherman --__n; 2206418Ssherman } while (__n > 0); 2216418Ssherman} 2226418Ssherman 2236418Ssherman// Copy constructs __n objects starting at __end_ from __x 2246418Ssherman// throws if construction throws 2256418Ssherman// Precondition: __n > 0 2266418Ssherman// Precondition: size() + __n <= capacity() 2276418Ssherman// Postcondition: size() == old size() + __n 2286418Ssherman// Postcondition: [i] == __x for all i in [size() - __n, __n) 2296897Sshermantemplate <class _Tp, class _Allocator> 2306418Sshermanvoid 2316418Ssherman__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) 2326418Ssherman{ 2336548Ssherman __alloc_rr& __a = this->__alloc(); 2346418Ssherman do 2356418Ssherman { 2366418Ssherman __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); 2376418Ssherman ++this->__end_; 2386548Ssherman --__n; 2396418Ssherman } while (__n > 0); 2406418Ssherman} 2416418Ssherman 2426418Sshermantemplate <class _Tp, class _Allocator> 2436418Sshermantemplate <class _InputIter> 2446418Sshermantypename enable_if 2456418Ssherman< 2466897Ssherman __is_input_iterator<_InputIter>::value && 2476418Ssherman !__is_forward_iterator<_InputIter>::value, 2486418Ssherman void 2496418Ssherman>::type 2506418Ssherman__split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last) 2516897Ssherman{ 2526418Ssherman __alloc_rr& __a = this->__alloc(); 2536418Ssherman for (; __first != __last; ++__first) 2546418Ssherman { 2556418Ssherman if (__end_ == __end_cap()) 2566418Ssherman { 2576418Ssherman size_type __old_cap = __end_cap() - __first_; 2586418Ssherman size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8); 2596418Ssherman __split_buffer __buf(__new_cap, 0, __a); 2606418Ssherman for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_) 2616418Ssherman __alloc_traits::construct(__buf.__alloc(), 2626418Ssherman _VSTD::__to_raw_pointer(__buf.__end_), _VSTD::move(*__p)); 26311354Sdfuchs swap(__buf); 26411354Sdfuchs } 2656418Ssherman __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 2666418Ssherman ++this->__end_; 2676418Ssherman } 2686418Ssherman} 2696418Ssherman 2706897Sshermantemplate <class _Tp, class _Allocator> 2716418Sshermantemplate <class _ForwardIterator> 2726897Sshermantypename enable_if 2736418Ssherman< 2746418Ssherman __is_forward_iterator<_ForwardIterator>::value, 2756897Ssherman void 2766418Ssherman>::type 2776418Ssherman__split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 2786418Ssherman{ 2796418Ssherman __alloc_rr& __a = this->__alloc(); 2806418Ssherman for (; __first != __last; ++__first) 2816418Ssherman { 2826418Ssherman __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 2836418Ssherman ++this->__end_; 2846418Ssherman } 2856418Ssherman} 2866418Ssherman 2876418Sshermantemplate <class _Tp, class _Allocator> 2886418Sshermaninline _LIBCPP_INLINE_VISIBILITY 2896418Sshermanvoid 2906418Ssherman__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) 2916418Ssherman{ 2926418Ssherman while (__begin_ != __new_begin) 2936897Ssherman __alloc_traits::destroy(__alloc(), __to_raw_pointer(__begin_++)); 2946418Ssherman} 2956418Ssherman 2966418Sshermantemplate <class _Tp, class _Allocator> 2976418Sshermaninline _LIBCPP_INLINE_VISIBILITY 2986418Sshermanvoid 2996418Ssherman__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) 3006418Ssherman{ 3016418Ssherman __begin_ = __new_begin; 3026418Ssherman} 3036418Ssherman 3046418Sshermantemplate <class _Tp, class _Allocator> 3056897Sshermaninline _LIBCPP_INLINE_VISIBILITY 3066418Sshermanvoid 3076418Ssherman__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT 3086418Ssherman{ 3096418Ssherman while (__new_last != __end_) 3106418Ssherman __alloc_traits::destroy(__alloc(), __to_raw_pointer(--__end_)); 3116418Ssherman} 3126418Ssherman 3136418Sshermantemplate <class _Tp, class _Allocator> 3146418Sshermaninline _LIBCPP_INLINE_VISIBILITY 3156418Sshermanvoid 3166548Ssherman__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT 3176418Ssherman{ 3186418Ssherman __end_ = __new_last; 3196418Ssherman} 3206418Ssherman 3216418Sshermantemplate <class _Tp, class _Allocator> 3226897Ssherman__split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a) 3236418Ssherman : __end_cap_(nullptr, __a) 3246418Ssherman{ 3256418Ssherman __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr; 3266418Ssherman __begin_ = __end_ = __first_ + __start; 3276418Ssherman __end_cap() = __first_ + __cap; 3286418Ssherman} 3296418Ssherman 3306418Sshermantemplate <class _Tp, class _Allocator> 3316418Sshermaninline _LIBCPP_INLINE_VISIBILITY 3326418Ssherman__split_buffer<_Tp, _Allocator>::__split_buffer() 3336418Ssherman _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 3346418Ssherman : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr) 3356418Ssherman{ 3366418Ssherman} 3376418Ssherman 3386418Sshermantemplate <class _Tp, class _Allocator> 3396418Sshermaninline _LIBCPP_INLINE_VISIBILITY 3406418Ssherman__split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a) 3416418Ssherman : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) 3426418Ssherman{ 3436418Ssherman} 3446418Ssherman 3456418Sshermantemplate <class _Tp, class _Allocator> 3466418Sshermaninline _LIBCPP_INLINE_VISIBILITY 3476418Ssherman__split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a) 3486418Ssherman : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) 3496418Ssherman{ 3506418Ssherman} 3516418Ssherman 3526418Sshermantemplate <class _Tp, class _Allocator> 3536418Ssherman__split_buffer<_Tp, _Allocator>::~__split_buffer() 3546548Ssherman{ 3556548Ssherman clear(); 3566897Ssherman if (__first_) 3576548Ssherman __alloc_traits::deallocate(__alloc(), __first_, capacity()); 3586548Ssherman} 3596548Ssherman 3606548Ssherman#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 3616548Ssherman 3626897Sshermantemplate <class _Tp, class _Allocator> 3636548Ssherman__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c) 3646548Ssherman _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 3656548Ssherman : __first_(_VSTD::move(__c.__first_)), 3666548Ssherman __begin_(_VSTD::move(__c.__begin_)), 3676548Ssherman __end_(_VSTD::move(__c.__end_)), 3686897Ssherman __end_cap_(_VSTD::move(__c.__end_cap_)) 3696548Ssherman{ 3706548Ssherman __c.__first_ = nullptr; 3716548Ssherman __c.__begin_ = nullptr; 3726548Ssherman __c.__end_ = nullptr; 3736548Ssherman __c.__end_cap() = nullptr; 3746897Ssherman} 3756548Ssherman 3766548Sshermantemplate <class _Tp, class _Allocator> 3776548Ssherman__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a) 3786548Ssherman : __end_cap_(__a) 3796897Ssherman{ 3806548Ssherman if (__a == __c.__alloc()) 3816548Ssherman { 3826548Ssherman __first_ = __c.__first_; 3836548Ssherman __begin_ = __c.__begin_; 3846897Ssherman __end_ = __c.__end_; 3856548Ssherman __end_cap() = __c.__end_cap(); 3866548Ssherman __c.__first_ = nullptr; 3876548Ssherman __c.__begin_ = nullptr; 3886548Ssherman __c.__end_ = nullptr; 3896548Ssherman __c.__end_cap() = nullptr; 3906418Ssherman } 3916418Ssherman else 3926897Ssherman { 3936418Ssherman size_type __cap = __c.size(); 3946418Ssherman __first_ = __alloc_traits::allocate(__alloc(), __cap); 3956418Ssherman __begin_ = __end_ = __first_; 3966418Ssherman __end_cap() = __first_ + __cap; 3976418Ssherman typedef move_iterator<iterator> _Ip; 3986418Ssherman __construct_at_end(_Ip(__c.begin()), _Ip(__c.end())); 3996897Ssherman } 4006548Ssherman} 4016548Ssherman 4026548Sshermantemplate <class _Tp, class _Allocator> 4036548Ssherman__split_buffer<_Tp, _Allocator>& 4046548Ssherman__split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c) 4056897Ssherman _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && 4066548Ssherman is_nothrow_move_assignable<allocator_type>::value) || 4076548Ssherman !__alloc_traits::propagate_on_container_move_assignment::value) 4086548Ssherman{ 4096548Ssherman clear(); 4106548Ssherman shrink_to_fit(); 4116897Ssherman __first_ = __c.__first_; 4126418Ssherman __begin_ = __c.__begin_; 4136418Ssherman __end_ = __c.__end_; 4146418Ssherman __end_cap() = __c.__end_cap(); 4156418Ssherman __move_assign_alloc(__c, 4166897Ssherman integral_constant<bool, 4176418Ssherman __alloc_traits::propagate_on_container_move_assignment::value>()); 4186418Ssherman __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 4196418Ssherman return *this; 4206418Ssherman} 4216418Ssherman 4226418Ssherman#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 4236548Ssherman 4246548Sshermantemplate <class _Tp, class _Allocator> 4256897Sshermanvoid 4266548Ssherman__split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x) 4276548Ssherman _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 4286548Ssherman __is_nothrow_swappable<__alloc_rr>::value) 4296548Ssherman{ 4306548Ssherman _VSTD::swap(__first_, __x.__first_); 4316548Ssherman _VSTD::swap(__begin_, __x.__begin_); 4326418Ssherman _VSTD::swap(__end_, __x.__end_); 4336418Ssherman _VSTD::swap(__end_cap(), __x.__end_cap()); 4346897Ssherman __swap_alloc(__alloc(), __x.__alloc()); 4356418Ssherman} 4366418Ssherman 4376418Sshermantemplate <class _Tp, class _Allocator> 4386418Sshermanvoid 4396418Ssherman__split_buffer<_Tp, _Allocator>::reserve(size_type __n) 4406418Ssherman{ 4416897Ssherman if (__n < capacity()) 4426418Ssherman { 4436418Ssherman __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc()); 4446418Ssherman __t.__construct_at_end(move_iterator<pointer>(__begin_), 4456418Ssherman move_iterator<pointer>(__end_)); 4466418Ssherman _VSTD::swap(__first_, __t.__first_); 4476418Ssherman _VSTD::swap(__begin_, __t.__begin_); 4486897Ssherman _VSTD::swap(__end_, __t.__end_); 4496418Ssherman _VSTD::swap(__end_cap(), __t.__end_cap()); 4506418Ssherman } 4516418Ssherman} 4526418Ssherman 4536418Sshermantemplate <class _Tp, class _Allocator> 4546418Sshermanvoid 4556897Ssherman__split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 4566418Ssherman{ 4576418Ssherman if (capacity() > size()) 4586418Ssherman { 4596418Ssherman#ifndef _LIBCPP_NO_EXCEPTIONS 4606418Ssherman try 4616418Ssherman { 4626897Ssherman#endif // _LIBCPP_NO_EXCEPTIONS 4636418Ssherman __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc()); 4646418Ssherman __t.__construct_at_end(move_iterator<pointer>(__begin_), 4656418Ssherman move_iterator<pointer>(__end_)); 4666418Ssherman __t.__end_ = __t.__begin_ + (__end_ - __begin_); 4676418Ssherman _VSTD::swap(__first_, __t.__first_); 4686418Ssherman _VSTD::swap(__begin_, __t.__begin_); 4696897Ssherman _VSTD::swap(__end_, __t.__end_); 4706418Ssherman _VSTD::swap(__end_cap(), __t.__end_cap()); 4716418Ssherman#ifndef _LIBCPP_NO_EXCEPTIONS 4726418Ssherman } 4736418Ssherman catch (...) 4746418Ssherman { 4756418Ssherman } 4766897Ssherman#endif // _LIBCPP_NO_EXCEPTIONS 4776418Ssherman } 4786418Ssherman} 4796418Ssherman 4806418Sshermantemplate <class _Tp, class _Allocator> 4816418Sshermanvoid 4826418Ssherman__split_buffer<_Tp, _Allocator>::push_front(const_reference __x) 4836418Ssherman{ 4846418Ssherman if (__begin_ == __first_) 4856418Ssherman { 4866418Ssherman if (__end_ < __end_cap()) 4876418Ssherman { 4886418Ssherman difference_type __d = __end_cap() - __end_; 4896418Ssherman __d = (__d + 1) / 2; 4906897Ssherman __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); 4916418Ssherman __end_ += __d; 4926418Ssherman } 4936418Ssherman else 4946418Ssherman { 4956418Ssherman size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 4966418Ssherman __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); 4976418Ssherman __t.__construct_at_end(move_iterator<pointer>(__begin_), 4986418Ssherman move_iterator<pointer>(__end_)); 4996418Ssherman _VSTD::swap(__first_, __t.__first_); 5006418Ssherman _VSTD::swap(__begin_, __t.__begin_); 5016418Ssherman _VSTD::swap(__end_, __t.__end_); 5026897Ssherman _VSTD::swap(__end_cap(), __t.__end_cap()); 5036418Ssherman } 5046418Ssherman } 5056418Ssherman __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x); 5066418Ssherman --__begin_; 5076418Ssherman} 5086418Ssherman 5096418Ssherman#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 5106418Ssherman 5116418Sshermantemplate <class _Tp, class _Allocator> 5126418Sshermanvoid 5136418Ssherman__split_buffer<_Tp, _Allocator>::push_front(value_type&& __x) 5146418Ssherman{ 5156418Ssherman if (__begin_ == __first_) 5166418Ssherman { 5176418Ssherman if (__end_ < __end_cap()) 5186418Ssherman { 5196897Ssherman difference_type __d = __end_cap() - __end_; 5206418Ssherman __d = (__d + 1) / 2; 5216418Ssherman __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); 5226418Ssherman __end_ += __d; 5236418Ssherman } 5246418Ssherman else 5256418Ssherman { 5266418Ssherman size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 5276418Ssherman __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); 5286418Ssherman __t.__construct_at_end(move_iterator<pointer>(__begin_), 5296418Ssherman move_iterator<pointer>(__end_)); 5306418Ssherman _VSTD::swap(__first_, __t.__first_); 5316418Ssherman _VSTD::swap(__begin_, __t.__begin_); 5326418Ssherman _VSTD::swap(__end_, __t.__end_); 5336418Ssherman _VSTD::swap(__end_cap(), __t.__end_cap()); 5346418Ssherman } 5356418Ssherman } 5366897Ssherman __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), 5376418Ssherman _VSTD::move(__x)); 5386418Ssherman --__begin_; 5396418Ssherman} 5406418Ssherman 5416418Ssherman#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 5426418Ssherman 5436418Sshermantemplate <class _Tp, class _Allocator> 5446418Sshermaninline _LIBCPP_INLINE_VISIBILITY 5456418Sshermanvoid 5466418Ssherman__split_buffer<_Tp, _Allocator>::push_back(const_reference __x) 5476418Ssherman{ 5486418Ssherman if (__end_ == __end_cap()) 5496418Ssherman { 5506418Ssherman if (__begin_ > __first_) 5516418Ssherman { 5526418Ssherman difference_type __d = __begin_ - __first_; 5536897Ssherman __d = (__d + 1) / 2; 5546418Ssherman __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 5556418Ssherman __begin_ -= __d; 5566418Ssherman } 5576418Ssherman else 5586418Ssherman { 5596418Ssherman size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 5606418Ssherman __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 5616418Ssherman __t.__construct_at_end(move_iterator<pointer>(__begin_), 5626418Ssherman move_iterator<pointer>(__end_)); 5636418Ssherman _VSTD::swap(__first_, __t.__first_); 5646418Ssherman _VSTD::swap(__begin_, __t.__begin_); 5656418Ssherman _VSTD::swap(__end_, __t.__end_); 5666418Ssherman _VSTD::swap(__end_cap(), __t.__end_cap()); 5676418Ssherman } 5686418Ssherman } 5696418Ssherman __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), __x); 5706418Ssherman ++__end_; 5716897Ssherman} 5726418Ssherman 5736418Ssherman#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 5746418Ssherman 5756418Sshermantemplate <class _Tp, class _Allocator> 5766418Sshermanvoid 5776897Ssherman__split_buffer<_Tp, _Allocator>::push_back(value_type&& __x) 5786418Ssherman{ 5796418Ssherman if (__end_ == __end_cap()) 5806418Ssherman { 5816418Ssherman if (__begin_ > __first_) 5826418Ssherman { 5836897Ssherman difference_type __d = __begin_ - __first_; 5846418Ssherman __d = (__d + 1) / 2; 5856418Ssherman __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 5866418Ssherman __begin_ -= __d; 5876418Ssherman } 5886418Ssherman else 5896418Ssherman { 5906418Ssherman size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 5916418Ssherman __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 5926897Ssherman __t.__construct_at_end(move_iterator<pointer>(__begin_), 5936418Ssherman move_iterator<pointer>(__end_)); 5946418Ssherman _VSTD::swap(__first_, __t.__first_); 5956418Ssherman _VSTD::swap(__begin_, __t.__begin_); 5966418Ssherman _VSTD::swap(__end_, __t.__end_); 5976418Ssherman _VSTD::swap(__end_cap(), __t.__end_cap()); 5986418Ssherman } 5996418Ssherman } 6006418Ssherman __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), 6016897Ssherman _VSTD::move(__x)); 6026418Ssherman ++__end_; 6036418Ssherman} 6046418Ssherman 6056418Ssherman#ifndef _LIBCPP_HAS_NO_VARIADICS 6066897Ssherman 6076418Sshermantemplate <class _Tp, class _Allocator> 6086418Sshermantemplate <class... _Args> 6096418Sshermanvoid 6106418Ssherman__split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args) 6116418Ssherman{ 6126418Ssherman if (__end_ == __end_cap()) 6136418Ssherman { 6146897Ssherman if (__begin_ > __first_) 6156418Ssherman { 6166418Ssherman difference_type __d = __begin_ - __first_; 6176418Ssherman __d = (__d + 1) / 2; 6186418Ssherman __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 6196418Ssherman __begin_ -= __d; 6206418Ssherman } 6216897Ssherman else 6226418Ssherman { 6236418Ssherman size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1); 6246418Ssherman __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 6256418Ssherman __t.__construct_at_end(move_iterator<pointer>(__begin_), 6266418Ssherman move_iterator<pointer>(__end_)); 6276418Ssherman _VSTD::swap(__first_, __t.__first_); 6286418Ssherman _VSTD::swap(__begin_, __t.__begin_); 6296418Ssherman _VSTD::swap(__end_, __t.__end_); 6306418Ssherman _VSTD::swap(__end_cap(), __t.__end_cap()); 6316897Ssherman } 6326418Ssherman } 6336418Ssherman __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), 6346418Ssherman _VSTD::forward<_Args>(__args)...); 6356418Ssherman ++__end_; 6366418Ssherman} 6376418Ssherman 6386418Ssherman#endif // _LIBCPP_HAS_NO_VARIADICS 6396418Ssherman 6406418Ssherman#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 6416897Ssherman 6426418Sshermantemplate <class _Tp, class _Allocator> 6436418Sshermaninline _LIBCPP_INLINE_VISIBILITY 6446418Sshermanvoid 6456418Sshermanswap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y) 6466418Ssherman _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 6476418Ssherman{ 6486418Ssherman __x.swap(__y); 6496418Ssherman} 6506418Ssherman 6516897Ssherman 6526418Ssherman_LIBCPP_END_NAMESPACE_STD 6536418Ssherman 6546418Ssherman#endif // _LIBCPP_SPLIT_BUFFER 6556418Ssherman