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