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