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