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