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