545 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03___SPLIT_BUFFER11#define _LIBCPP___CXX03___SPLIT_BUFFER12 13#include <__cxx03/__algorithm/max.h>14#include <__cxx03/__algorithm/move.h>15#include <__cxx03/__algorithm/move_backward.h>16#include <__cxx03/__config>17#include <__cxx03/__iterator/distance.h>18#include <__cxx03/__iterator/iterator_traits.h>19#include <__cxx03/__iterator/move_iterator.h>20#include <__cxx03/__memory/allocate_at_least.h>21#include <__cxx03/__memory/allocator.h>22#include <__cxx03/__memory/allocator_traits.h>23#include <__cxx03/__memory/compressed_pair.h>24#include <__cxx03/__memory/pointer_traits.h>25#include <__cxx03/__memory/swap_allocator.h>26#include <__cxx03/__type_traits/add_lvalue_reference.h>27#include <__cxx03/__type_traits/conditional.h>28#include <__cxx03/__type_traits/enable_if.h>29#include <__cxx03/__type_traits/integral_constant.h>30#include <__cxx03/__type_traits/is_nothrow_assignable.h>31#include <__cxx03/__type_traits/is_nothrow_constructible.h>32#include <__cxx03/__type_traits/is_swappable.h>33#include <__cxx03/__type_traits/is_trivially_destructible.h>34#include <__cxx03/__type_traits/is_trivially_relocatable.h>35#include <__cxx03/__type_traits/remove_reference.h>36#include <__cxx03/__utility/forward.h>37#include <__cxx03/__utility/move.h>38#include <__cxx03/cstddef>39 40#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)41# pragma GCC system_header42#endif43 44_LIBCPP_PUSH_MACROS45#include <__cxx03/__undef_macros>46 47_LIBCPP_BEGIN_NAMESPACE_STD48 49// __split_buffer allocates a contiguous chunk of memory and stores objects in the range [__begin_, __end_).50// It has uninitialized memory in the ranges [__first_, __begin_) and [__end_, __end_cap_.first()). That allows51// it to grow both in the front and back without having to move the data.52 53template <class _Tp, class _Allocator = allocator<_Tp> >54struct __split_buffer {55public:56 using value_type = _Tp;57 using allocator_type = _Allocator;58 using __alloc_rr = __libcpp_remove_reference_t<allocator_type>;59 using __alloc_traits = allocator_traits<__alloc_rr>;60 using reference = value_type&;61 using const_reference = const value_type&;62 using size_type = typename __alloc_traits::size_type;63 using difference_type = typename __alloc_traits::difference_type;64 using pointer = typename __alloc_traits::pointer;65 using const_pointer = typename __alloc_traits::const_pointer;66 using iterator = pointer;67 using const_iterator = const_pointer;68 69 // A __split_buffer contains the following members which may be trivially relocatable:70 // - pointer: may be trivially relocatable, so it's checked71 // - allocator_type: may be trivially relocatable, so it's checked72 // __split_buffer doesn't have any self-references, so it's trivially relocatable if its members are.73 using __trivially_relocatable = __conditional_t<74 __libcpp_is_trivially_relocatable<pointer>::value && __libcpp_is_trivially_relocatable<allocator_type>::value,75 __split_buffer,76 void>;77 78 pointer __first_;79 pointer __begin_;80 pointer __end_;81 __compressed_pair<pointer, allocator_type> __end_cap_;82 83 using __alloc_ref = __add_lvalue_reference_t<allocator_type>;84 using __alloc_const_ref = __add_lvalue_reference_t<allocator_type>;85 86 __split_buffer(const __split_buffer&) = delete;87 __split_buffer& operator=(const __split_buffer&) = delete;88 89 _LIBCPP_HIDE_FROM_ABI __split_buffer()90 : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __default_init_tag()) {}91 92 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(__alloc_rr& __a)93 : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) {}94 95 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(const __alloc_rr& __a)96 : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) {}97 98 _LIBCPP_HIDE_FROM_ABI __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a);99 100 _LIBCPP_HIDE_FROM_ABI __split_buffer(__split_buffer&& __c);101 102 _LIBCPP_HIDE_FROM_ABI __split_buffer(__split_buffer&& __c, const __alloc_rr& __a);103 104 _LIBCPP_HIDE_FROM_ABI __split_buffer& operator=(__split_buffer&& __c);105 106 _LIBCPP_HIDE_FROM_ABI ~__split_buffer();107 108 _LIBCPP_HIDE_FROM_ABI __alloc_rr& __alloc() _NOEXCEPT { return __end_cap_.second(); }109 _LIBCPP_HIDE_FROM_ABI const __alloc_rr& __alloc() const _NOEXCEPT { return __end_cap_.second(); }110 111 _LIBCPP_HIDE_FROM_ABI pointer& __end_cap() _NOEXCEPT { return __end_cap_.first(); }112 _LIBCPP_HIDE_FROM_ABI const pointer& __end_cap() const _NOEXCEPT { return __end_cap_.first(); }113 114 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __begin_; }115 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __begin_; }116 117 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __end_; }118 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __end_; }119 120 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __destruct_at_end(__begin_); }121 122 _LIBCPP_HIDE_FROM_ABI size_type size() const { return static_cast<size_type>(__end_ - __begin_); }123 124 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __end_ == __begin_; }125 126 _LIBCPP_HIDE_FROM_ABI size_type capacity() const { return static_cast<size_type>(__end_cap() - __first_); }127 128 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const { return static_cast<size_type>(__begin_ - __first_); }129 130 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const { return static_cast<size_type>(__end_cap() - __end_); }131 132 _LIBCPP_HIDE_FROM_ABI reference front() { return *__begin_; }133 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return *__begin_; }134 _LIBCPP_HIDE_FROM_ABI reference back() { return *(__end_ - 1); }135 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return *(__end_ - 1); }136 137 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n);138 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;139 _LIBCPP_HIDE_FROM_ABI void push_front(const_reference __x);140 _LIBCPP_HIDE_FROM_ABI void push_back(const_reference __x);141 _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x);142 _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x);143 144 template <class... _Args>145 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args);146 147 _LIBCPP_HIDE_FROM_ABI void pop_front() { __destruct_at_begin(__begin_ + 1); }148 _LIBCPP_HIDE_FROM_ABI void pop_back() { __destruct_at_end(__end_ - 1); }149 150 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n);151 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x);152 153 template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> = 0>154 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(_InputIter __first, _InputIter __last);155 156 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>157 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);158 159 template <class _Iterator, class _Sentinel>160 _LIBCPP_HIDE_FROM_ABI void __construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last);161 162 template <class _Iterator>163 _LIBCPP_HIDE_FROM_ABI void __construct_at_end_with_size(_Iterator __first, size_type __n);164 165 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin) {166 __destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());167 }168 169 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin, false_type);170 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin, true_type);171 172 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT {173 __destruct_at_end(__new_last, false_type());174 }175 176 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;177 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;178 179 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer& __x);180 181 _LIBCPP_HIDE_FROM_ABI bool __invariants() const;182 183private:184 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer& __c, true_type) {185 __alloc() = std::move(__c.__alloc());186 }187 188 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT {}189 190 struct _ConstructTransaction {191 _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(pointer* __p, size_type __n) _NOEXCEPT192 : __pos_(*__p),193 __end_(*__p + __n),194 __dest_(__p) {}195 196 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { *__dest_ = __pos_; }197 198 pointer __pos_;199 const pointer __end_;200 201 private:202 pointer* __dest_;203 };204};205 206template <class _Tp, class _Allocator>207bool __split_buffer<_Tp, _Allocator>::__invariants() const {208 if (__first_ == nullptr) {209 if (__begin_ != nullptr)210 return false;211 if (__end_ != nullptr)212 return false;213 if (__end_cap() != nullptr)214 return false;215 } else {216 if (__begin_ < __first_)217 return false;218 if (__end_ < __begin_)219 return false;220 if (__end_cap() < __end_)221 return false;222 }223 return true;224}225 226// Default constructs __n objects starting at __end_227// throws if construction throws228// Precondition: __n > 0229// Precondition: size() + __n <= capacity()230// Postcondition: size() == size() + __n231template <class _Tp, class _Allocator>232void __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) {233 _ConstructTransaction __tx(&this->__end_, __n);234 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {235 __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_));236 }237}238 239// Copy constructs __n objects starting at __end_ from __x240// throws if construction throws241// Precondition: __n > 0242// Precondition: size() + __n <= capacity()243// Postcondition: size() == old size() + __n244// Postcondition: [i] == __x for all i in [size() - __n, __n)245template <class _Tp, class _Allocator>246void __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) {247 _ConstructTransaction __tx(&this->__end_, __n);248 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {249 __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_), __x);250 }251}252 253template <class _Tp, class _Allocator>254template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> >255void __split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last) {256 __construct_at_end_with_sentinel(__first, __last);257}258 259template <class _Tp, class _Allocator>260template <class _Iterator, class _Sentinel>261void __split_buffer<_Tp, _Allocator>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) {262 __alloc_rr& __a = this->__alloc();263 for (; __first != __last; ++__first) {264 if (__end_ == __end_cap()) {265 size_type __old_cap = __end_cap() - __first_;266 size_type __new_cap = std::max<size_type>(2 * __old_cap, 8);267 __split_buffer __buf(__new_cap, 0, __a);268 for (pointer __p = __begin_; __p != __end_; ++__p, (void)++__buf.__end_)269 __alloc_traits::construct(__buf.__alloc(), std::__to_address(__buf.__end_), std::move(*__p));270 swap(__buf);271 }272 __alloc_traits::construct(__a, std::__to_address(this->__end_), *__first);273 ++this->__end_;274 }275}276template <class _Tp, class _Allocator>277template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >278void __split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) {279 __construct_at_end_with_size(__first, std::distance(__first, __last));280}281 282template <class _Tp, class _Allocator>283template <class _ForwardIterator>284void __split_buffer<_Tp, _Allocator>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) {285 _ConstructTransaction __tx(&this->__end_, __n);286 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__first) {287 __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_), *__first);288 }289}290 291template <class _Tp, class _Allocator>292inline void __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) {293 while (__begin_ != __new_begin)294 __alloc_traits::destroy(__alloc(), std::__to_address(__begin_++));295}296 297template <class _Tp, class _Allocator>298inline void __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) {299 __begin_ = __new_begin;300}301 302template <class _Tp, class _Allocator>303inline _LIBCPP_HIDE_FROM_ABI void304__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT {305 while (__new_last != __end_)306 __alloc_traits::destroy(__alloc(), std::__to_address(--__end_));307}308 309template <class _Tp, class _Allocator>310inline _LIBCPP_HIDE_FROM_ABI void311__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT {312 __end_ = __new_last;313}314 315template <class _Tp, class _Allocator>316__split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)317 : __end_cap_(nullptr, __a) {318 if (__cap == 0) {319 __first_ = nullptr;320 } else {321 auto __allocation = std::__allocate_at_least(__alloc(), __cap);322 __first_ = __allocation.ptr;323 __cap = __allocation.count;324 }325 __begin_ = __end_ = __first_ + __start;326 __end_cap() = __first_ + __cap;327}328 329template <class _Tp, class _Allocator>330__split_buffer<_Tp, _Allocator>::~__split_buffer() {331 clear();332 if (__first_)333 __alloc_traits::deallocate(__alloc(), __first_, capacity());334}335 336template <class _Tp, class _Allocator>337__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c)338 : __first_(std::move(__c.__first_)),339 __begin_(std::move(__c.__begin_)),340 __end_(std::move(__c.__end_)),341 __end_cap_(std::move(__c.__end_cap_)) {342 __c.__first_ = nullptr;343 __c.__begin_ = nullptr;344 __c.__end_ = nullptr;345 __c.__end_cap() = nullptr;346}347 348template <class _Tp, class _Allocator>349__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a)350 : __end_cap_(nullptr, __a) {351 if (__a == __c.__alloc()) {352 __first_ = __c.__first_;353 __begin_ = __c.__begin_;354 __end_ = __c.__end_;355 __end_cap() = __c.__end_cap();356 __c.__first_ = nullptr;357 __c.__begin_ = nullptr;358 __c.__end_ = nullptr;359 __c.__end_cap() = nullptr;360 } else {361 auto __allocation = std::__allocate_at_least(__alloc(), __c.size());362 __first_ = __allocation.ptr;363 __begin_ = __end_ = __first_;364 __end_cap() = __first_ + __allocation.count;365 typedef move_iterator<iterator> _Ip;366 __construct_at_end(_Ip(__c.begin()), _Ip(__c.end()));367 }368}369 370template <class _Tp, class _Allocator>371__split_buffer<_Tp, _Allocator>& __split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c) {372 clear();373 shrink_to_fit();374 __first_ = __c.__first_;375 __begin_ = __c.__begin_;376 __end_ = __c.__end_;377 __end_cap() = __c.__end_cap();378 __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());379 __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;380 return *this;381}382 383template <class _Tp, class _Allocator>384void __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x) {385 std::swap(__first_, __x.__first_);386 std::swap(__begin_, __x.__begin_);387 std::swap(__end_, __x.__end_);388 std::swap(__end_cap(), __x.__end_cap());389 std::__swap_allocator(__alloc(), __x.__alloc());390}391 392template <class _Tp, class _Allocator>393void __split_buffer<_Tp, _Allocator>::reserve(size_type __n) {394 if (__n < capacity()) {395 __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc());396 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));397 std::swap(__first_, __t.__first_);398 std::swap(__begin_, __t.__begin_);399 std::swap(__end_, __t.__end_);400 std::swap(__end_cap(), __t.__end_cap());401 }402}403 404template <class _Tp, class _Allocator>405void __split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT {406 if (capacity() > size()) {407#ifndef _LIBCPP_HAS_NO_EXCEPTIONS408 try {409#endif // _LIBCPP_HAS_NO_EXCEPTIONS410 __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc());411 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));412 __t.__end_ = __t.__begin_ + (__end_ - __begin_);413 std::swap(__first_, __t.__first_);414 std::swap(__begin_, __t.__begin_);415 std::swap(__end_, __t.__end_);416 std::swap(__end_cap(), __t.__end_cap());417#ifndef _LIBCPP_HAS_NO_EXCEPTIONS418 } catch (...) {419 }420#endif // _LIBCPP_HAS_NO_EXCEPTIONS421 }422}423 424template <class _Tp, class _Allocator>425void __split_buffer<_Tp, _Allocator>::push_front(const_reference __x) {426 if (__begin_ == __first_) {427 if (__end_ < __end_cap()) {428 difference_type __d = __end_cap() - __end_;429 __d = (__d + 1) / 2;430 __begin_ = std::move_backward(__begin_, __end_, __end_ + __d);431 __end_ += __d;432 } else {433 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);434 __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());435 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));436 std::swap(__first_, __t.__first_);437 std::swap(__begin_, __t.__begin_);438 std::swap(__end_, __t.__end_);439 std::swap(__end_cap(), __t.__end_cap());440 }441 }442 __alloc_traits::construct(__alloc(), std::__to_address(__begin_ - 1), __x);443 --__begin_;444}445 446template <class _Tp, class _Allocator>447void __split_buffer<_Tp, _Allocator>::push_front(value_type&& __x) {448 if (__begin_ == __first_) {449 if (__end_ < __end_cap()) {450 difference_type __d = __end_cap() - __end_;451 __d = (__d + 1) / 2;452 __begin_ = std::move_backward(__begin_, __end_, __end_ + __d);453 __end_ += __d;454 } else {455 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);456 __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());457 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));458 std::swap(__first_, __t.__first_);459 std::swap(__begin_, __t.__begin_);460 std::swap(__end_, __t.__end_);461 std::swap(__end_cap(), __t.__end_cap());462 }463 }464 __alloc_traits::construct(__alloc(), std::__to_address(__begin_ - 1), std::move(__x));465 --__begin_;466}467 468template <class _Tp, class _Allocator>469inline _LIBCPP_HIDE_FROM_ABI void __split_buffer<_Tp, _Allocator>::push_back(const_reference __x) {470 if (__end_ == __end_cap()) {471 if (__begin_ > __first_) {472 difference_type __d = __begin_ - __first_;473 __d = (__d + 1) / 2;474 __end_ = std::move(__begin_, __end_, __begin_ - __d);475 __begin_ -= __d;476 } else {477 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);478 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());479 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));480 std::swap(__first_, __t.__first_);481 std::swap(__begin_, __t.__begin_);482 std::swap(__end_, __t.__end_);483 std::swap(__end_cap(), __t.__end_cap());484 }485 }486 __alloc_traits::construct(__alloc(), std::__to_address(__end_), __x);487 ++__end_;488}489 490template <class _Tp, class _Allocator>491void __split_buffer<_Tp, _Allocator>::push_back(value_type&& __x) {492 if (__end_ == __end_cap()) {493 if (__begin_ > __first_) {494 difference_type __d = __begin_ - __first_;495 __d = (__d + 1) / 2;496 __end_ = std::move(__begin_, __end_, __begin_ - __d);497 __begin_ -= __d;498 } else {499 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);500 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());501 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));502 std::swap(__first_, __t.__first_);503 std::swap(__begin_, __t.__begin_);504 std::swap(__end_, __t.__end_);505 std::swap(__end_cap(), __t.__end_cap());506 }507 }508 __alloc_traits::construct(__alloc(), std::__to_address(__end_), std::move(__x));509 ++__end_;510}511 512template <class _Tp, class _Allocator>513template <class... _Args>514void __split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args) {515 if (__end_ == __end_cap()) {516 if (__begin_ > __first_) {517 difference_type __d = __begin_ - __first_;518 __d = (__d + 1) / 2;519 __end_ = std::move(__begin_, __end_, __begin_ - __d);520 __begin_ -= __d;521 } else {522 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);523 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());524 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));525 std::swap(__first_, __t.__first_);526 std::swap(__begin_, __t.__begin_);527 std::swap(__end_, __t.__end_);528 std::swap(__end_cap(), __t.__end_cap());529 }530 }531 __alloc_traits::construct(__alloc(), std::__to_address(__end_), std::forward<_Args>(__args)...);532 ++__end_;533}534 535template <class _Tp, class _Allocator>536inline _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y) {537 __x.swap(__y);538}539 540_LIBCPP_END_NAMESPACE_STD541 542_LIBCPP_POP_MACROS543 544#endif // _LIBCPP___CXX03___SPLIT_BUFFER545