__split_buffer revision 227825
1227825Stheraven// -*- C++ -*- 2227825Stheraven#ifndef _LIBCPP_SPLIT_BUFFER 3227825Stheraven#define _LIBCPP_SPLIT_BUFFER 4227825Stheraven 5227825Stheraven#include <__config> 6227825Stheraven#include <type_traits> 7227825Stheraven#include <algorithm> 8227825Stheraven 9227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 10227825Stheraven#pragma GCC system_header 11227825Stheraven#endif 12227825Stheraven 13227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 14227825Stheraven 15227825Stheraventemplate <bool> 16227825Stheravenclass __split_buffer_common 17227825Stheraven{ 18227825Stheravenprotected: 19227825Stheraven void __throw_length_error() const; 20227825Stheraven void __throw_out_of_range() const; 21227825Stheraven}; 22227825Stheraven 23227825Stheraventemplate <class _Tp, class _Allocator = allocator<_Tp> > 24227825Stheravenstruct __split_buffer 25227825Stheraven : private __split_buffer_common<true> 26227825Stheraven{ 27227825Stheravenprivate: 28227825Stheraven __split_buffer(const __split_buffer&); 29227825Stheraven __split_buffer& operator=(const __split_buffer&); 30227825Stheravenpublic: 31227825Stheraven typedef _Tp value_type; 32227825Stheraven typedef _Allocator allocator_type; 33227825Stheraven typedef typename remove_reference<allocator_type>::type __alloc_rr; 34227825Stheraven typedef allocator_traits<__alloc_rr> __alloc_traits; 35227825Stheraven typedef value_type& reference; 36227825Stheraven typedef const value_type& const_reference; 37227825Stheraven typedef typename __alloc_traits::size_type size_type; 38227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 39227825Stheraven typedef typename __alloc_traits::pointer pointer; 40227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 41227825Stheraven typedef pointer iterator; 42227825Stheraven typedef const_pointer const_iterator; 43227825Stheraven 44227825Stheraven pointer __first_; 45227825Stheraven pointer __begin_; 46227825Stheraven pointer __end_; 47227825Stheraven __compressed_pair<pointer, allocator_type> __end_cap_; 48227825Stheraven 49227825Stheraven typedef typename add_lvalue_reference<allocator_type>::type __alloc_ref; 50227825Stheraven typedef typename add_lvalue_reference<allocator_type>::type __alloc_const_ref; 51227825Stheraven 52227825Stheraven _LIBCPP_INLINE_VISIBILITY __alloc_rr& __alloc() _NOEXCEPT {return __end_cap_.second();} 53227825Stheraven _LIBCPP_INLINE_VISIBILITY const __alloc_rr& __alloc() const _NOEXCEPT {return __end_cap_.second();} 54227825Stheraven _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() _NOEXCEPT {return __end_cap_.first();} 55227825Stheraven _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const _NOEXCEPT {return __end_cap_.first();} 56227825Stheraven 57227825Stheraven __split_buffer() 58227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 59227825Stheraven explicit __split_buffer(__alloc_rr& __a); 60227825Stheraven explicit __split_buffer(const __alloc_rr& __a); 61227825Stheraven __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a); 62227825Stheraven ~__split_buffer(); 63227825Stheraven 64227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 65227825Stheraven __split_buffer(__split_buffer&& __c) 66227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 67227825Stheraven __split_buffer(__split_buffer&& __c, const __alloc_rr& __a); 68227825Stheraven __split_buffer& operator=(__split_buffer&& __c) 69227825Stheraven _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && 70227825Stheraven is_nothrow_move_assignable<allocator_type>::value) || 71227825Stheraven !__alloc_traits::propagate_on_container_move_assignment::value); 72227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 73227825Stheraven 74227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __begin_;} 75227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __begin_;} 76227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __end_;} 77227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __end_;} 78227825Stheraven 79227825Stheraven _LIBCPP_INLINE_VISIBILITY 80227825Stheraven void clear() _NOEXCEPT 81227825Stheraven {__destruct_at_end(__begin_);} 82227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(__end_ - __begin_);} 83227825Stheraven _LIBCPP_INLINE_VISIBILITY bool empty() const {return __end_ == __begin_;} 84227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __first_);} 85227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type __front_spare() const {return static_cast<size_type>(__begin_ - __first_);} 86227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type __back_spare() const {return static_cast<size_type>(__end_cap() - __end_);} 87227825Stheraven 88227825Stheraven _LIBCPP_INLINE_VISIBILITY reference front() {return *__begin_;} 89227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *__begin_;} 90227825Stheraven _LIBCPP_INLINE_VISIBILITY reference back() {return *(__end_ - 1);} 91227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(__end_ - 1);} 92227825Stheraven 93227825Stheraven void reserve(size_type __n); 94227825Stheraven void shrink_to_fit() _NOEXCEPT; 95227825Stheraven void push_front(const_reference __x); 96227825Stheraven void push_back(const_reference __x); 97227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 98227825Stheraven void push_front(value_type&& __x); 99227825Stheraven void push_back(value_type&& __x); 100227825Stheraven#if !defined(_LIBCPP_HAS_NO_VARIADICS) 101227825Stheraven template <class... _Args> 102227825Stheraven void emplace_back(_Args&&... __args); 103227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_VARIADICS) 104227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 105227825Stheraven 106227825Stheraven _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);} 107227825Stheraven _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);} 108227825Stheraven 109227825Stheraven void __construct_at_end(size_type __n); 110227825Stheraven void __construct_at_end(size_type __n, const_reference __x); 111227825Stheraven template <class _InputIter> 112227825Stheraven typename enable_if 113227825Stheraven < 114227825Stheraven __is_input_iterator<_InputIter>::value && 115227825Stheraven !__is_forward_iterator<_InputIter>::value, 116227825Stheraven void 117227825Stheraven >::type 118227825Stheraven __construct_at_end(_InputIter __first, _InputIter __last); 119227825Stheraven template <class _ForwardIterator> 120227825Stheraven typename enable_if 121227825Stheraven < 122227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 123227825Stheraven void 124227825Stheraven >::type 125227825Stheraven __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 126227825Stheraven 127227825Stheraven _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin) 128227825Stheraven {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());} 129227825Stheraven void __destruct_at_begin(pointer __new_begin, false_type); 130227825Stheraven void __destruct_at_begin(pointer __new_begin, true_type); 131227825Stheraven 132227825Stheraven _LIBCPP_INLINE_VISIBILITY 133227825Stheraven void __destruct_at_end(pointer __new_last) _NOEXCEPT 134227825Stheraven {__destruct_at_end(__new_last, is_trivially_destructible<value_type>());} 135227825Stheraven void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT; 136227825Stheraven void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT; 137227825Stheraven 138227825Stheraven void swap(__split_buffer& __x) 139227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 140227825Stheraven __is_nothrow_swappable<__alloc_rr>::value); 141227825Stheraven 142227825Stheraven bool __invariants() const; 143227825Stheraven 144227825Stheravenprivate: 145227825Stheraven _LIBCPP_INLINE_VISIBILITY 146227825Stheraven void __move_assign_alloc(__split_buffer& __c, true_type) 147227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 148227825Stheraven { 149227825Stheraven __alloc() = _VSTD::move(__c.__alloc()); 150227825Stheraven } 151227825Stheraven 152227825Stheraven _LIBCPP_INLINE_VISIBILITY 153227825Stheraven void __move_assign_alloc(__split_buffer& __c, false_type) _NOEXCEPT 154227825Stheraven {} 155227825Stheraven 156227825Stheraven _LIBCPP_INLINE_VISIBILITY 157227825Stheraven static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y) 158227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 159227825Stheraven __is_nothrow_swappable<__alloc_rr>::value) 160227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 161227825Stheraven __alloc_traits::propagate_on_container_swap::value>());} 162227825Stheraven 163227825Stheraven _LIBCPP_INLINE_VISIBILITY 164227825Stheraven static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y, true_type) 165227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<__alloc_rr>::value) 166227825Stheraven { 167227825Stheraven using _VSTD::swap; 168227825Stheraven swap(__x, __y); 169227825Stheraven } 170227825Stheraven 171227825Stheraven _LIBCPP_INLINE_VISIBILITY 172227825Stheraven static void __swap_alloc(__alloc_rr& __x, __alloc_rr& __y, false_type) _NOEXCEPT 173227825Stheraven {} 174227825Stheraven}; 175227825Stheraven 176227825Stheraventemplate <class _Tp, class _Allocator> 177227825Stheravenbool 178227825Stheraven__split_buffer<_Tp, _Allocator>::__invariants() const 179227825Stheraven{ 180227825Stheraven if (__first_ == nullptr) 181227825Stheraven { 182227825Stheraven if (__begin_ != nullptr) 183227825Stheraven return false; 184227825Stheraven if (__end_ != nullptr) 185227825Stheraven return false; 186227825Stheraven if (__end_cap() != nullptr) 187227825Stheraven return false; 188227825Stheraven } 189227825Stheraven else 190227825Stheraven { 191227825Stheraven if (__begin_ < __first_) 192227825Stheraven return false; 193227825Stheraven if (__end_ < __begin_) 194227825Stheraven return false; 195227825Stheraven if (__end_cap() < __end_) 196227825Stheraven return false; 197227825Stheraven } 198227825Stheraven return true; 199227825Stheraven} 200227825Stheraven 201227825Stheraven// Default constructs __n objects starting at __end_ 202227825Stheraven// throws if construction throws 203227825Stheraven// Precondition: __n > 0 204227825Stheraven// Precondition: size() + __n <= capacity() 205227825Stheraven// Postcondition: size() == size() + __n 206227825Stheraventemplate <class _Tp, class _Allocator> 207227825Stheravenvoid 208227825Stheraven__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) 209227825Stheraven{ 210227825Stheraven __alloc_rr& __a = this->__alloc(); 211227825Stheraven do 212227825Stheraven { 213227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); 214227825Stheraven ++this->__end_; 215227825Stheraven --__n; 216227825Stheraven } while (__n > 0); 217227825Stheraven} 218227825Stheraven 219227825Stheraven// Copy constructs __n objects starting at __end_ from __x 220227825Stheraven// throws if construction throws 221227825Stheraven// Precondition: __n > 0 222227825Stheraven// Precondition: size() + __n <= capacity() 223227825Stheraven// Postcondition: size() == old size() + __n 224227825Stheraven// Postcondition: [i] == __x for all i in [size() - __n, __n) 225227825Stheraventemplate <class _Tp, class _Allocator> 226227825Stheravenvoid 227227825Stheraven__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) 228227825Stheraven{ 229227825Stheraven __alloc_rr& __a = this->__alloc(); 230227825Stheraven do 231227825Stheraven { 232227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); 233227825Stheraven ++this->__end_; 234227825Stheraven --__n; 235227825Stheraven } while (__n > 0); 236227825Stheraven} 237227825Stheraven 238227825Stheraventemplate <class _Tp, class _Allocator> 239227825Stheraventemplate <class _InputIter> 240227825Stheraventypename enable_if 241227825Stheraven< 242227825Stheraven __is_input_iterator<_InputIter>::value && 243227825Stheraven !__is_forward_iterator<_InputIter>::value, 244227825Stheraven void 245227825Stheraven>::type 246227825Stheraven__split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last) 247227825Stheraven{ 248227825Stheraven __alloc_rr& __a = this->__alloc(); 249227825Stheraven for (; __first != __last; ++__first) 250227825Stheraven { 251227825Stheraven if (__end_ == __end_cap()) 252227825Stheraven { 253227825Stheraven size_type __old_cap = __end_cap() - __first_; 254227825Stheraven size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8); 255227825Stheraven __split_buffer __buf(__new_cap, 0, __a); 256227825Stheraven for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_) 257227825Stheraven __alloc_traits::construct(__buf.__alloc(), 258227825Stheraven _VSTD::__to_raw_pointer(__buf.__end_), _VSTD::move(*__p)); 259227825Stheraven swap(__buf); 260227825Stheraven } 261227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 262227825Stheraven ++this->__end_; 263227825Stheraven } 264227825Stheraven} 265227825Stheraven 266227825Stheraventemplate <class _Tp, class _Allocator> 267227825Stheraventemplate <class _ForwardIterator> 268227825Stheraventypename enable_if 269227825Stheraven< 270227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 271227825Stheraven void 272227825Stheraven>::type 273227825Stheraven__split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 274227825Stheraven{ 275227825Stheraven __alloc_rr& __a = this->__alloc(); 276227825Stheraven for (; __first != __last; ++__first) 277227825Stheraven { 278227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 279227825Stheraven ++this->__end_; 280227825Stheraven } 281227825Stheraven} 282227825Stheraven 283227825Stheraventemplate <class _Tp, class _Allocator> 284227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 285227825Stheravenvoid 286227825Stheraven__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) 287227825Stheraven{ 288227825Stheraven while (__begin_ < __new_begin) 289227825Stheraven __alloc_traits::destroy(__alloc(), __begin_++); 290227825Stheraven} 291227825Stheraven 292227825Stheraventemplate <class _Tp, class _Allocator> 293227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 294227825Stheravenvoid 295227825Stheraven__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) 296227825Stheraven{ 297227825Stheraven __begin_ = __new_begin; 298227825Stheraven} 299227825Stheraven 300227825Stheraventemplate <class _Tp, class _Allocator> 301227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 302227825Stheravenvoid 303227825Stheraven__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT 304227825Stheraven{ 305227825Stheraven while (__new_last < __end_) 306227825Stheraven __alloc_traits::destroy(__alloc(), --__end_); 307227825Stheraven} 308227825Stheraven 309227825Stheraventemplate <class _Tp, class _Allocator> 310227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 311227825Stheravenvoid 312227825Stheraven__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT 313227825Stheraven{ 314227825Stheraven __end_ = __new_last; 315227825Stheraven} 316227825Stheraven 317227825Stheraventemplate <class _Tp, class _Allocator> 318227825Stheraven__split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a) 319227825Stheraven : __end_cap_(0, __a) 320227825Stheraven{ 321227825Stheraven __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr; 322227825Stheraven __begin_ = __end_ = __first_ + __start; 323227825Stheraven __end_cap() = __first_ + __cap; 324227825Stheraven} 325227825Stheraven 326227825Stheraventemplate <class _Tp, class _Allocator> 327227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 328227825Stheraven__split_buffer<_Tp, _Allocator>::__split_buffer() 329227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 330227825Stheraven : __first_(0), __begin_(0), __end_(0), __end_cap_(0) 331227825Stheraven{ 332227825Stheraven} 333227825Stheraven 334227825Stheraventemplate <class _Tp, class _Allocator> 335227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 336227825Stheraven__split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a) 337227825Stheraven : __first_(0), __begin_(0), __end_(0), __end_cap_(0, __a) 338227825Stheraven{ 339227825Stheraven} 340227825Stheraven 341227825Stheraventemplate <class _Tp, class _Allocator> 342227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 343227825Stheraven__split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a) 344227825Stheraven : __first_(0), __begin_(0), __end_(0), __end_cap_(0, __a) 345227825Stheraven{ 346227825Stheraven} 347227825Stheraven 348227825Stheraventemplate <class _Tp, class _Allocator> 349227825Stheraven__split_buffer<_Tp, _Allocator>::~__split_buffer() 350227825Stheraven{ 351227825Stheraven clear(); 352227825Stheraven if (__first_) 353227825Stheraven __alloc_traits::deallocate(__alloc(), __first_, capacity()); 354227825Stheraven} 355227825Stheraven 356227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 357227825Stheraven 358227825Stheraventemplate <class _Tp, class _Allocator> 359227825Stheraven__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c) 360227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 361227825Stheraven : __first_(_VSTD::move(__c.__first_)), 362227825Stheraven __begin_(_VSTD::move(__c.__begin_)), 363227825Stheraven __end_(_VSTD::move(__c.__end_)), 364227825Stheraven __end_cap_(_VSTD::move(__c.__end_cap_)) 365227825Stheraven{ 366227825Stheraven __c.__first_ = nullptr; 367227825Stheraven __c.__begin_ = nullptr; 368227825Stheraven __c.__end_ = nullptr; 369227825Stheraven __c.__end_cap() = nullptr; 370227825Stheraven} 371227825Stheraven 372227825Stheraventemplate <class _Tp, class _Allocator> 373227825Stheraven__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a) 374227825Stheraven : __end_cap_(__a) 375227825Stheraven{ 376227825Stheraven if (__a == __c.__alloc()) 377227825Stheraven { 378227825Stheraven __first_ = __c.__first_; 379227825Stheraven __begin_ = __c.__begin_; 380227825Stheraven __end_ = __c.__end_; 381227825Stheraven __end_cap() = __c.__end_cap(); 382227825Stheraven __c.__first_ = nullptr; 383227825Stheraven __c.__begin_ = nullptr; 384227825Stheraven __c.__end_ = nullptr; 385227825Stheraven __c.__end_cap() = nullptr; 386227825Stheraven } 387227825Stheraven else 388227825Stheraven { 389227825Stheraven size_type __cap = __c.size(); 390227825Stheraven __first_ = __alloc_traits::allocate(__alloc(), __cap); 391227825Stheraven __begin_ = __end_ = __first_; 392227825Stheraven __end_cap() = __first_ + __cap; 393227825Stheraven typedef move_iterator<iterator> _I; 394227825Stheraven __construct_at_end(_I(__c.begin()), _I(__c.end())); 395227825Stheraven } 396227825Stheraven} 397227825Stheraven 398227825Stheraventemplate <class _Tp, class _Allocator> 399227825Stheraven__split_buffer<_Tp, _Allocator>& 400227825Stheraven__split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c) 401227825Stheraven _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && 402227825Stheraven is_nothrow_move_assignable<allocator_type>::value) || 403227825Stheraven !__alloc_traits::propagate_on_container_move_assignment::value) 404227825Stheraven{ 405227825Stheraven clear(); 406227825Stheraven shrink_to_fit(); 407227825Stheraven __first_ = __c.__first_; 408227825Stheraven __begin_ = __c.__begin_; 409227825Stheraven __end_ = __c.__end_; 410227825Stheraven __end_cap() = __c.__end_cap(); 411227825Stheraven __move_assign_alloc(__c, 412227825Stheraven integral_constant<bool, 413227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value>()); 414227825Stheraven __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 415227825Stheraven return *this; 416227825Stheraven} 417227825Stheraven 418227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 419227825Stheraven 420227825Stheraventemplate <class _Tp, class _Allocator> 421227825Stheravenvoid 422227825Stheraven__split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x) 423227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 424227825Stheraven __is_nothrow_swappable<__alloc_rr>::value) 425227825Stheraven{ 426227825Stheraven _VSTD::swap(__first_, __x.__first_); 427227825Stheraven _VSTD::swap(__begin_, __x.__begin_); 428227825Stheraven _VSTD::swap(__end_, __x.__end_); 429227825Stheraven _VSTD::swap(__end_cap(), __x.__end_cap()); 430227825Stheraven __swap_alloc(__alloc(), __x.__alloc()); 431227825Stheraven} 432227825Stheraven 433227825Stheraventemplate <class _Tp, class _Allocator> 434227825Stheravenvoid 435227825Stheraven__split_buffer<_Tp, _Allocator>::reserve(size_type __n) 436227825Stheraven{ 437227825Stheraven if (__n < capacity()) 438227825Stheraven { 439227825Stheraven __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc()); 440227825Stheraven __t.__construct_at_end(move_iterator<pointer>(__begin_), 441227825Stheraven move_iterator<pointer>(__end_)); 442227825Stheraven _VSTD::swap(__first_, __t.__first_); 443227825Stheraven _VSTD::swap(__begin_, __t.__begin_); 444227825Stheraven _VSTD::swap(__end_, __t.__end_); 445227825Stheraven _VSTD::swap(__end_cap(), __t.__end_cap()); 446227825Stheraven } 447227825Stheraven} 448227825Stheraven 449227825Stheraventemplate <class _Tp, class _Allocator> 450227825Stheravenvoid 451227825Stheraven__split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 452227825Stheraven{ 453227825Stheraven if (capacity() > size()) 454227825Stheraven { 455227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 456227825Stheraven try 457227825Stheraven { 458227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 459227825Stheraven __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc()); 460227825Stheraven __t.__construct_at_end(move_iterator<pointer>(__begin_), 461227825Stheraven move_iterator<pointer>(__end_)); 462227825Stheraven __t.__end_ = __t.__begin_ + (__end_ - __begin_); 463227825Stheraven _VSTD::swap(__first_, __t.__first_); 464227825Stheraven _VSTD::swap(__begin_, __t.__begin_); 465227825Stheraven _VSTD::swap(__end_, __t.__end_); 466227825Stheraven _VSTD::swap(__end_cap(), __t.__end_cap()); 467227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 468227825Stheraven } 469227825Stheraven catch (...) 470227825Stheraven { 471227825Stheraven } 472227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 473227825Stheraven } 474227825Stheraven} 475227825Stheraven 476227825Stheraventemplate <class _Tp, class _Allocator> 477227825Stheravenvoid 478227825Stheraven__split_buffer<_Tp, _Allocator>::push_front(const_reference __x) 479227825Stheraven{ 480227825Stheraven if (__begin_ == __first_) 481227825Stheraven { 482227825Stheraven if (__end_ < __end_cap()) 483227825Stheraven { 484227825Stheraven difference_type __d = __end_cap() - __end_; 485227825Stheraven __d = (__d + 1) / 2; 486227825Stheraven __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); 487227825Stheraven __end_ += __d; 488227825Stheraven } 489227825Stheraven else 490227825Stheraven { 491227825Stheraven size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1); 492227825Stheraven __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); 493227825Stheraven __t.__construct_at_end(move_iterator<pointer>(__begin_), 494227825Stheraven move_iterator<pointer>(__end_)); 495227825Stheraven _VSTD::swap(__first_, __t.__first_); 496227825Stheraven _VSTD::swap(__begin_, __t.__begin_); 497227825Stheraven _VSTD::swap(__end_, __t.__end_); 498227825Stheraven _VSTD::swap(__end_cap(), __t.__end_cap()); 499227825Stheraven } 500227825Stheraven } 501227825Stheraven __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x); 502227825Stheraven --__begin_; 503227825Stheraven} 504227825Stheraven 505227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 506227825Stheraven 507227825Stheraventemplate <class _Tp, class _Allocator> 508227825Stheravenvoid 509227825Stheraven__split_buffer<_Tp, _Allocator>::push_front(value_type&& __x) 510227825Stheraven{ 511227825Stheraven if (__begin_ == __first_) 512227825Stheraven { 513227825Stheraven if (__end_ < __end_cap()) 514227825Stheraven { 515227825Stheraven difference_type __d = __end_cap() - __end_; 516227825Stheraven __d = (__d + 1) / 2; 517227825Stheraven __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d); 518227825Stheraven __end_ += __d; 519227825Stheraven } 520227825Stheraven else 521227825Stheraven { 522227825Stheraven size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1); 523227825Stheraven __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc()); 524227825Stheraven __t.__construct_at_end(move_iterator<pointer>(__begin_), 525227825Stheraven move_iterator<pointer>(__end_)); 526227825Stheraven _VSTD::swap(__first_, __t.__first_); 527227825Stheraven _VSTD::swap(__begin_, __t.__begin_); 528227825Stheraven _VSTD::swap(__end_, __t.__end_); 529227825Stheraven _VSTD::swap(__end_cap(), __t.__end_cap()); 530227825Stheraven } 531227825Stheraven } 532227825Stheraven __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), 533227825Stheraven _VSTD::move(__x)); 534227825Stheraven --__begin_; 535227825Stheraven} 536227825Stheraven 537227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 538227825Stheraven 539227825Stheraventemplate <class _Tp, class _Allocator> 540227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 541227825Stheravenvoid 542227825Stheraven__split_buffer<_Tp, _Allocator>::push_back(const_reference __x) 543227825Stheraven{ 544227825Stheraven if (__end_ == __end_cap()) 545227825Stheraven { 546227825Stheraven if (__begin_ > __first_) 547227825Stheraven { 548227825Stheraven difference_type __d = __begin_ - __first_; 549227825Stheraven __d = (__d + 1) / 2; 550227825Stheraven __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 551227825Stheraven __begin_ -= __d; 552227825Stheraven } 553227825Stheraven else 554227825Stheraven { 555227825Stheraven size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1); 556227825Stheraven __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 557227825Stheraven __t.__construct_at_end(move_iterator<pointer>(__begin_), 558227825Stheraven move_iterator<pointer>(__end_)); 559227825Stheraven _VSTD::swap(__first_, __t.__first_); 560227825Stheraven _VSTD::swap(__begin_, __t.__begin_); 561227825Stheraven _VSTD::swap(__end_, __t.__end_); 562227825Stheraven _VSTD::swap(__end_cap(), __t.__end_cap()); 563227825Stheraven } 564227825Stheraven } 565227825Stheraven __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), __x); 566227825Stheraven ++__end_; 567227825Stheraven} 568227825Stheraven 569227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 570227825Stheraven 571227825Stheraventemplate <class _Tp, class _Allocator> 572227825Stheravenvoid 573227825Stheraven__split_buffer<_Tp, _Allocator>::push_back(value_type&& __x) 574227825Stheraven{ 575227825Stheraven if (__end_ == __end_cap()) 576227825Stheraven { 577227825Stheraven if (__begin_ > __first_) 578227825Stheraven { 579227825Stheraven difference_type __d = __begin_ - __first_; 580227825Stheraven __d = (__d + 1) / 2; 581227825Stheraven __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 582227825Stheraven __begin_ -= __d; 583227825Stheraven } 584227825Stheraven else 585227825Stheraven { 586227825Stheraven size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1); 587227825Stheraven __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 588227825Stheraven __t.__construct_at_end(move_iterator<pointer>(__begin_), 589227825Stheraven move_iterator<pointer>(__end_)); 590227825Stheraven _VSTD::swap(__first_, __t.__first_); 591227825Stheraven _VSTD::swap(__begin_, __t.__begin_); 592227825Stheraven _VSTD::swap(__end_, __t.__end_); 593227825Stheraven _VSTD::swap(__end_cap(), __t.__end_cap()); 594227825Stheraven } 595227825Stheraven } 596227825Stheraven __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), 597227825Stheraven _VSTD::move(__x)); 598227825Stheraven ++__end_; 599227825Stheraven} 600227825Stheraven 601227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 602227825Stheraven 603227825Stheraventemplate <class _Tp, class _Allocator> 604227825Stheraventemplate <class... _Args> 605227825Stheravenvoid 606227825Stheraven__split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args) 607227825Stheraven{ 608227825Stheraven if (__end_ == __end_cap()) 609227825Stheraven { 610227825Stheraven if (__begin_ > __first_) 611227825Stheraven { 612227825Stheraven difference_type __d = __begin_ - __first_; 613227825Stheraven __d = (__d + 1) / 2; 614227825Stheraven __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d); 615227825Stheraven __begin_ -= __d; 616227825Stheraven } 617227825Stheraven else 618227825Stheraven { 619227825Stheraven size_type __c = max<size_type>(2 * (__end_cap() - __first_), 1); 620227825Stheraven __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc()); 621227825Stheraven __t.__construct_at_end(move_iterator<pointer>(__begin_), 622227825Stheraven move_iterator<pointer>(__end_)); 623227825Stheraven _VSTD::swap(__first_, __t.__first_); 624227825Stheraven _VSTD::swap(__begin_, __t.__begin_); 625227825Stheraven _VSTD::swap(__end_, __t.__end_); 626227825Stheraven _VSTD::swap(__end_cap(), __t.__end_cap()); 627227825Stheraven } 628227825Stheraven } 629227825Stheraven __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), 630227825Stheraven _VSTD::forward<_Args>(__args)...); 631227825Stheraven ++__end_; 632227825Stheraven} 633227825Stheraven 634227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 635227825Stheraven 636227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 637227825Stheraven 638227825Stheraventemplate <class _Tp, class _Allocator> 639227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 640227825Stheravenvoid 641227825Stheravenswap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y) 642227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 643227825Stheraven{ 644227825Stheraven __x.swap(__y); 645227825Stheraven} 646227825Stheraven 647227825Stheraven 648227825Stheraven_LIBCPP_END_NAMESPACE_STD 649227825Stheraven 650227825Stheraven#endif // _LIBCPP_SPLIT_BUFFER 651