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