libcxx/include/__split_buffer

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