path: root/libcxx/include/__split_buffer

// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___SPLIT_BUFFER
#define _LIBCPP___SPLIT_BUFFER

#include <__algorithm/max.h>
#include <__algorithm/move.h>
#include <__algorithm/move_backward.h>
#include <__assert>
#include <__config>
#include <__iterator/distance.h>
#include <__iterator/iterator_traits.h>
#include <__iterator/move_iterator.h>
#include <__memory/addressof.h>
#include <__memory/allocate_at_least.h>
#include <__memory/allocator.h>
#include <__memory/allocator_traits.h>
#include <__memory/compressed_pair.h>
#include <__memory/pointer_traits.h>
#include <__memory/swap_allocator.h>
#include <__type_traits/conditional.h>
#include <__type_traits/enable_if.h>
#include <__type_traits/integral_constant.h>
#include <__type_traits/is_nothrow_assignable.h>
#include <__type_traits/is_nothrow_constructible.h>
#include <__type_traits/is_replaceable.h>
#include <__type_traits/is_swappable.h>
#include <__type_traits/is_trivially_destructible.h>
#include <__type_traits/is_trivially_relocatable.h>
#include <__type_traits/remove_reference.h>
#include <__utility/forward.h>
#include <__utility/move.h>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_PUSH_MACROS
#include <__undef_macros>

_LIBCPP_BEGIN_NAMESPACE_STD

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
class __split_buffer;

template <class _SplitBuffer, class _Tp, class _Allocator>
class __split_buffer_pointer_layout {
protected:
  using value_type                      = _Tp;
  using allocator_type                  = _Allocator;
  using __alloc_rr _LIBCPP_NODEBUG      = __libcpp_remove_reference_t<allocator_type>;
  using __alloc_traits _LIBCPP_NODEBUG  = allocator_traits<__alloc_rr>;
  using reference                       = value_type&;
  using const_reference                 = const value_type&;
  using size_type                       = typename __alloc_traits::size_type;
  using difference_type                 = typename __alloc_traits::difference_type;
  using pointer                         = typename __alloc_traits::pointer;
  using const_pointer                   = typename __alloc_traits::const_pointer;
  using iterator                        = pointer;
  using const_iterator                  = const_pointer;
  using __sentinel_type _LIBCPP_NODEBUG = pointer;

public:
  // Can't be defaulted due to _LIBCPP_COMPRESSED_PAIR not being an aggregate in C++03 and C++11.
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer_pointer_layout() : __back_cap_(nullptr) {}

  _LIBCPP_CONSTEXPR_SINCE_CXX20
  _LIBCPP_HIDE_FROM_ABI explicit __split_buffer_pointer_layout(const allocator_type& __alloc)
      : __back_cap_(nullptr), __alloc_(__alloc) {}

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer __front_cap() _NOEXCEPT { return __front_cap_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer __front_cap() const _NOEXCEPT {
    return __front_cap_;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer begin() _NOEXCEPT { return __begin_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer begin() const _NOEXCEPT { return __begin_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() _NOEXCEPT { return __end_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() const _NOEXCEPT { return __end_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT {
    return static_cast<size_type>(__end_ - __begin_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __begin_ == __end_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT {
    return static_cast<size_type>(__back_cap_ - __front_cap_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type& __get_allocator() _NOEXCEPT { return __alloc_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type const& __get_allocator() const _NOEXCEPT {
    return __alloc_;
  }

  // Returns the sentinel object directly. Should be used in conjunction with automatic type deduction,
  // not explicit types.
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_sentinel() const _NOEXCEPT {
    return __end_;
  }
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_capacity() const _NOEXCEPT {
    return __back_cap_;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_data(pointer __new_first) _NOEXCEPT {
    __front_cap_ = __new_first;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __set_valid_range(pointer __new_begin, pointer __new_end) _NOEXCEPT {
    __begin_ = __new_begin;
    __end_   = __new_end;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __set_valid_range(pointer __new_begin, size_type __new_size) _NOEXCEPT {
    __begin_ = __new_begin;
    __end_   = __begin_ + __new_size;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(pointer __new_end) _NOEXCEPT {
    _LIBCPP_ASSERT_INTERNAL(__front_cap_ <= __new_end, "__new_end cannot precede __front_cap_");
    __end_ = __new_end;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(size_type __new_size) _NOEXCEPT {
    __end_ = __begin_ + __new_size;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(size_type __new_capacity) _NOEXCEPT {
    __back_cap_ = __front_cap_ + __new_capacity;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(pointer __new_capacity) _NOEXCEPT {
    __back_cap_ = __new_capacity;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const _NOEXCEPT {
    return static_cast<size_type>(__begin_ - __front_cap_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const _NOEXCEPT {
    return static_cast<size_type>(__back_cap_ - __end_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT { return *(__end_ - 1); }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT { return *(__end_ - 1); }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator(
      __split_buffer_pointer_layout<__split_buffer<value_type, __alloc_rr&, __split_buffer_pointer_layout>,
                                    value_type,
                                    __alloc_rr&>& __other) _NOEXCEPT {
    std::swap(__front_cap_, __other.__front_cap_);
    std::swap(__begin_, __other.__begin_);
    std::swap(__back_cap_, __other.__back_cap_);
    std::swap(__end_, __other.__end_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer_pointer_layout& __other) _NOEXCEPT {
    std::swap(__front_cap_, __other.__front_cap_);
    std::swap(__begin_, __other.__begin_);
    std::swap(__back_cap_, __other.__back_cap_);
    std::swap(__end_, __other.__end_);
    std::__swap_allocator(__alloc_, __other.__alloc_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __reset() _NOEXCEPT {
    __front_cap_ = nullptr;
    __begin_     = nullptr;
    __end_       = nullptr;
    __back_cap_  = nullptr;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __copy_without_alloc(__split_buffer_pointer_layout const& __other)
      _NOEXCEPT_(is_nothrow_copy_assignable<pointer>::value) {
    __front_cap_ = __other.__front_cap_;
    __begin_     = __other.__begin_;
    __end_       = __other.__end_;
    __back_cap_  = __other.__back_cap_;
  }

private:
  pointer __front_cap_ = nullptr;
  pointer __begin_     = nullptr;
  pointer __end_       = nullptr;
  _LIBCPP_COMPRESSED_PAIR(pointer, __back_cap_, allocator_type, __alloc_);

  template <class, class, class>
  friend class __split_buffer_pointer_layout;
};

template <class _SplitBuffer, class _Tp, class _Allocator>
class __split_buffer_size_layout {
protected:
  using value_type                      = _Tp;
  using allocator_type                  = _Allocator;
  using __alloc_rr _LIBCPP_NODEBUG      = __libcpp_remove_reference_t<allocator_type>;
  using __alloc_traits _LIBCPP_NODEBUG  = allocator_traits<__alloc_rr>;
  using reference                       = value_type&;
  using const_reference                 = const value_type&;
  using size_type                       = typename __alloc_traits::size_type;
  using difference_type                 = typename __alloc_traits::difference_type;
  using pointer                         = typename __alloc_traits::pointer;
  using const_pointer                   = typename __alloc_traits::const_pointer;
  using iterator                        = pointer;
  using const_iterator                  = const_pointer;
  using __sentinel_type _LIBCPP_NODEBUG = size_type;

public:
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer_size_layout() = default;

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer_size_layout(const allocator_type& __alloc)
      : __alloc_(__alloc) {}

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer __front_cap() _NOEXCEPT { return __front_cap_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer __front_cap() const _NOEXCEPT {
    return __front_cap_;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer begin() _NOEXCEPT { return __begin_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer begin() const _NOEXCEPT { return __begin_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() _NOEXCEPT { return __begin_ + __size_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() const _NOEXCEPT { return __begin_ + __size_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __size_ == 0; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT { return __cap_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type& __get_allocator() _NOEXCEPT { return __alloc_; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type const& __get_allocator() const _NOEXCEPT {
    return __alloc_;
  }

  // Returns the sentinel object directly. Should be used in conjunction with automatic type deduction,
  // not explicit types.
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_sentinel() const _NOEXCEPT {
    return __size_;
  }
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_capacity() const _NOEXCEPT {
    return __cap_;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_data(pointer __new_first) _NOEXCEPT {
    __front_cap_ = __new_first;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __set_valid_range(pointer __new_begin, pointer __new_end) _NOEXCEPT {
    // Size-based __split_buffers track their size directly: we need to explicitly update the size
    // when the front is adjusted.
    __size_ -= __new_begin - __begin_;
    __begin_ = __new_begin;
    __set_sentinel(__new_end);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __set_valid_range(pointer __new_begin, size_type __new_size) _NOEXCEPT {
    // Size-based __split_buffers track their size directly: we need to explicitly update the size
    // when the front is adjusted.
    __size_ -= __new_begin - __begin_;
    __begin_ = __new_begin;
    __set_sentinel(__new_size);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(pointer __new_end) _NOEXCEPT {
    _LIBCPP_ASSERT_INTERNAL(__front_cap_ <= __new_end, "__new_end cannot precede __front_cap_");
    __size_ += __new_end - end();
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(size_type __new_size) _NOEXCEPT {
    __size_ = __new_size;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(size_type __new_capacity) _NOEXCEPT {
    __cap_ = __new_capacity;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(pointer __new_capacity) _NOEXCEPT {
    __cap_ = __new_capacity - __begin_;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const _NOEXCEPT {
    return static_cast<size_type>(__begin_ - __front_cap_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const _NOEXCEPT {
    // `__cap_ - __end_` tells us the total number of spares when in size-mode. We need to remove
    // the __front_spare from the count.
    return __cap_ - __size_ - __front_spare();
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT { return __begin_[__size_ - 1]; }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT {
    return __begin_[__size_ - 1];
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator(
      __split_buffer_pointer_layout<__split_buffer<value_type, __alloc_rr&, __split_buffer_pointer_layout>,
                                    value_type,
                                    __alloc_rr&>& __other) _NOEXCEPT {
    std::swap(__front_cap_, __other.__front_cap_);
    std::swap(__begin_, __other.__begin_);
    std::swap(__cap_, __other.__cap_);
    std::swap(__size_, __other.__size_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer_size_layout& __other) _NOEXCEPT {
    std::swap(__front_cap_, __other.__front_cap_);
    std::swap(__begin_, __other.__begin_);
    std::swap(__cap_, __other.__cap_);
    std::swap(__size_, __other.__size_);
    std::__swap_allocator(__alloc_, __other.__alloc_);
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __reset() _NOEXCEPT {
    __front_cap_ = nullptr;
    __begin_     = nullptr;
    __size_      = 0;
    __cap_       = 0;
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __copy_without_alloc(__split_buffer_size_layout const& __other)
      _NOEXCEPT_(is_nothrow_copy_assignable<pointer>::value) {
    __front_cap_ = __other.__front_cap_;
    __begin_     = __other.__begin_;
    __cap_       = __other.__cap_;
    __size_      = __other.__size_;
  }

private:
  pointer __front_cap_ = nullptr;
  pointer __begin_     = nullptr;
  size_type __size_    = 0;
  size_type __cap_     = 0;
  _LIBCPP_NO_UNIQUE_ADDRESS allocator_type __alloc_;

  template <class, class, class>
  friend class __split_buffer_size_layout;
};

// `__split_buffer` is a contiguous array data structure. It may hold spare capacity at both ends of
// the sequence. This allows for a `__split_buffer` to grow from both the front and the back without
// relocating its contents until it runs out of room. This characteristic sets it apart from
// `std::vector`, which only holds spare capacity at its end. As such, `__split_buffer` is useful
// for implementing both `std::vector` and `std::deque`.
//
// The sequence is stored as a contiguous chunk of memory delimited by the following "pointers" (`o` denotes
// uninitialized memory and `x` denotes a valid object):
//
//     |oooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoooooooooooooooooooooooo|
//      ^                  ^                                    ^                       ^
//  __front_cap_        __begin_                              __end_               __back_cap_
//
// The range [__front_cap_, __begin_) contains uninitialized memory. It is referred to as the "front spare capacity".
// The range [__begin_, __end_) contains valid objects. It is referred to as the "valid range".
// The range [__end_, __back_cap_) contains uninitialized memory. It is referred to as the "back spare capacity".
//
// The layout of `__split_buffer` is determined by the `_Layout` template template parameter. This
// `_Layout` allows the above pointers to be stored as different representations, such as integer
// offsets. A layout class template must provide the following interface:
//
//    template<class _Tp, class _Allocator, class _Layout>
//    class __layout {
//    protected:
//      using value_type                     = _Tp;
//      using allocator_type                 = _Allocator;
//      using __alloc_rr                     = __libcpp_remove_reference_t<allocator_type>;
//      using __alloc_traits                 = allocator_traits<__alloc_rr>;
//      using reference                      = value_type&;
//      using const_reference                = const value_type&;
//      using size_type                      = typename __alloc_traits::size_type;
//      using difference_type                = typename __alloc_traits::difference_type;
//      using pointer                        = typename __alloc_traits::pointer;
//      using const_pointer                  = typename __alloc_traits::const_pointer;
//      using iterator                       = pointer;
//      using const_iterator                 = const_pointer;
//      using __sentinel_type                = /* type that represents the layout's sentinel */;
//
//    public:
//      __layout() = default;
//      explicit __layout(const allocator_type&);
//
//      pointer __front_cap();
//      const_pointer __front_cap() const;
//
//      pointer begin();
//      const_pointer begin() const;
//
//      pointer end();
//      pointer end() const;
//
//      size_type size() const;
//      bool empty() const;
//      size_type capacity() const;
//
//      allocator_type& __get_allocator();
//      allocator_type const& __get_allocator() const;
//
//      __sentinel_type __raw_sentinel() const;
//      __sentinel_type __raw_capacity() const;
//
//      void __set_data(pointer);
//      void __set_valid_range(pointer __begin, pointer __end);
//      void __set_valid_range(pointer __begin, size_type __size);
//      void __set_sentinel(pointer __end);
//      void __set_sentinel(size_type __size);
//
//      void __set_capacity(size_type __capacity);
//      void __set_capacity(pointer __capacity);
//
//      size_type __front_spare() const;
//      size_type __back_spare() const;
//
//      reference back();
//      const_reference back() const;
//
//      template<class _OtherLayout>
//      void __swap_without_allocator(_OtherLayout&);
//      void swap(__layout&);
//
//      void __reset();
//      void __copy_without_alloc(__layout const&);
//    };
//
template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
class __split_buffer : _Layout<__split_buffer<_Tp, _Allocator, _Layout>, _Tp, _Allocator> {
  using __base_type _LIBCPP_NODEBUG = _Layout<__split_buffer<_Tp, _Allocator, _Layout>, _Tp, _Allocator>;

public:
  using __base_type::__back_spare;
  using __base_type::__copy_without_alloc;
  using __base_type::__front_cap;
  using __base_type::__front_spare;
  using __base_type::__get_allocator;
  using __base_type::__raw_capacity;
  using __base_type::__raw_sentinel;
  using __base_type::__reset;
  using __base_type::__set_capacity;
  using __base_type::__set_data;
  using __base_type::__set_sentinel;
  using __base_type::__set_valid_range;

  using typename __base_type::__alloc_rr;
  using typename __base_type::__alloc_traits;
  using typename __base_type::allocator_type;
  using typename __base_type::const_iterator;
  using typename __base_type::const_pointer;
  using typename __base_type::const_reference;
  using typename __base_type::difference_type;
  using typename __base_type::iterator;
  using typename __base_type::pointer;
  using typename __base_type::reference;
  using typename __base_type::size_type;
  using typename __base_type::value_type;

  // A __split_buffer contains the following members which may be trivially relocatable:
  // - pointer: may be trivially relocatable, so it's checked
  // - allocator_type: may be trivially relocatable, so it's checked
  // __split_buffer doesn't have any self-references, so it's trivially relocatable if its members are.
  using __trivially_relocatable _LIBCPP_NODEBUG = __conditional_t<
      __libcpp_is_trivially_relocatable<pointer>::value && __libcpp_is_trivially_relocatable<allocator_type>::value,
      __split_buffer,
      void>;
  using __replaceable _LIBCPP_NODEBUG =
      __conditional_t<__is_replaceable_v<pointer> && __container_allocator_is_replaceable<__alloc_traits>::value,
                      __split_buffer,
                      void>;

  __split_buffer(const __split_buffer&)            = delete;
  __split_buffer& operator=(const __split_buffer&) = delete;

  _LIBCPP_HIDE_FROM_ABI __split_buffer() = default;

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(__alloc_rr& __a) : __base_type(__a) {}

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(const __alloc_rr& __a)
      : __base_type(__a) {}

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
  __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a);

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer(__split_buffer&& __c)
      _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer(__split_buffer&& __c, const __alloc_rr& __a);

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer& operator=(__split_buffer&& __c)
      _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
                  is_nothrow_move_assignable<allocator_type>::value) ||
                 !__alloc_traits::propagate_on_container_move_assignment::value);

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~__split_buffer();

  using __base_type::back;
  using __base_type::begin;
  using __base_type::capacity;
  using __base_type::empty;
  using __base_type::end;
  using __base_type::size;

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __destruct_at_end(begin()); }
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() { return *begin(); }
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return *begin(); }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;

  template <class... _Args>
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);
  template <class... _Args>
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args);

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_front() { __destruct_at_begin(begin() + 1); }
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back() { __destruct_at_end(end() - 1); }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n);
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x);

  template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);

  template <class _Iterator, class _Sentinel>
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last);

  template <class _Iterator>
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __construct_at_end_with_size(_Iterator __first, size_type __n);

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin) {
    __destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin, false_type);
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin, true_type);

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT {
    __destruct_at_end(__new_last, false_type());
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer& __x)
      _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>);

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const {
    if (__front_cap() == nullptr) {
      if (begin() != nullptr)
        return false;

      if (!empty())
        return false;

      if (capacity() != 0)
        return false;

      return true;
    } else {
      if (begin() < __front_cap())
        return false;

      if (capacity() < size())
        return false;

      if (end() < begin())
        return false;

      return true;
    }
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
  __swap_without_allocator(__split_buffer<value_type, __alloc_rr&, _Layout>& __other) _NOEXCEPT {
    __base_type::__swap_without_allocator(__other);
  }

private:
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer& __c, true_type)
      _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
    __get_allocator() = std::move(__c.__get_allocator());
  }

  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT {}

  struct _ConstructTransaction {
    _LIBCPP_CONSTEXPR_SINCE_CXX20
    _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(__split_buffer* __parent, pointer __p, size_type __n) _NOEXCEPT
        : __pos_(__p),
          __end_(__p + __n),
          __parent_(__parent) {}

    _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { __parent_->__set_sentinel(__pos_); }

    pointer __pos_;
    const pointer __end_;

  private:
    __split_buffer* __parent_;
  };

  template <class _T2, class _A2, template <class, class, class> class _L2>
  friend class __split_buffer;
};

//  Default constructs __n objects starting at `end()`
//  throws if construction throws
//  Precondition:  __n > 0
//  Precondition:  size() + __n <= capacity()
//  Postcondition:  size() == size() + __n
template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(size_type __n) {
  _ConstructTransaction __tx(this, end(), __n);
  for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
    __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_));
  }
}

//  Copy constructs __n objects starting at `end()` from __x
//  throws if construction throws
//  Precondition:  __n > 0
//  Precondition:  size() + __n <= capacity()
//  Postcondition:  size() == old size() + __n
//  Postcondition:  [i] == __x for all i in [size() - __n, __n)
template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(size_type __n, const_reference __x) {
  _ConstructTransaction __tx(this, end(), __n);
  for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
    __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_), __x);
  }
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
template <class _Iterator, class _Sentinel>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) {
  __alloc_rr& __a = __get_allocator();
  for (; __first != __last; ++__first) {
    if (__back_spare() == 0) {
      size_type __old_cap = capacity();
      size_type __new_cap = std::max<size_type>(2 * __old_cap, 8);
      __split_buffer __buf(__new_cap, 0, __a);
      pointer __buf_end = __buf.end();
      pointer __end     = end();
      for (pointer __p = begin(); __p != __end; ++__p) {
        __alloc_traits::construct(__buf.__get_allocator(), std::__to_address(__buf_end), std::move(*__p));
        __buf.__set_sentinel(++__buf_end);
      }
      swap(__buf);
    }

    __alloc_traits::construct(__a, std::__to_address(end()), *__first);
    __set_sentinel(size() + 1);
  }
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) {
  __construct_at_end_with_size(__first, std::distance(__first, __last));
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
template <class _ForwardIterator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) {
  _ConstructTransaction __tx(this, end(), __n);
  for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__first) {
    __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_), *__first);
  }
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_begin(pointer __new_begin, false_type) {
  pointer __begin = begin();
  // Updating begin at every iteration is unnecessary because destruction can't throw.
  while (__begin != __new_begin)
    __alloc_traits::destroy(__get_allocator(), std::__to_address(__begin++));
  __set_valid_range(__begin, end());
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_begin(pointer __new_begin, true_type) {
  __set_valid_range(__new_begin, end());
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT {
  pointer __end = end();
  // Updating begin at every iteration is unnecessary because destruction can't throw.
  while (__new_last != __end)
    __alloc_traits::destroy(__get_allocator(), std::__to_address(--__end));
  __set_sentinel(__end);
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20
__split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)
    : __base_type(__a) {
  _LIBCPP_ASSERT_INTERNAL(__cap >= __start, "can't have a start point outside the capacity");
  if (__cap > 0) {
    auto __allocation = std::__allocate_at_least(__get_allocator(), __cap);
    __set_data(__allocation.ptr);
    __cap = __allocation.count;
  }

  pointer __begin = __front_cap() + __start;
  __set_valid_range(__begin, __begin);
  __set_capacity(__cap);
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>::~__split_buffer() {
  clear();
  if (__front_cap())
    __alloc_traits::deallocate(__get_allocator(), __front_cap(), capacity());
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(__split_buffer&& __c)
    _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
    : __base_type(std::move(__c)) {
  __c.__reset();
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20
__split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a)
    : __base_type(__a) {
  if (__a == __c.__get_allocator()) {
    __set_data(__c.__front_cap());
    __set_valid_range(__c.begin(), __c.end());
    __set_capacity(__c.capacity());
    __c.__reset();
  } else {
    auto __allocation = std::__allocate_at_least(__get_allocator(), __c.size());
    __set_data(__allocation.ptr);
    __set_valid_range(__front_cap(), __front_cap());
    __set_capacity(__allocation.count);
    typedef move_iterator<iterator> _Ip;
    __construct_at_end(_Ip(__c.begin()), _Ip(__c.end()));
  }
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>&
__split_buffer<_Tp, _Allocator, _Layout>::operator=(__split_buffer&& __c)
    _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
                is_nothrow_move_assignable<allocator_type>::value) ||
               !__alloc_traits::propagate_on_container_move_assignment::value) {
  clear();
  shrink_to_fit();
  __copy_without_alloc(__c);
  __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
  __c.__reset();
  return *this;
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::swap(__split_buffer& __x)
    _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>) {
  __base_type::swap(__x);
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::shrink_to_fit() _NOEXCEPT {
  if (capacity() > size()) {
#if _LIBCPP_HAS_EXCEPTIONS
    try {
#endif // _LIBCPP_HAS_EXCEPTIONS
      __split_buffer<value_type, __alloc_rr&, _Layout> __t(size(), 0, __get_allocator());
      if (__t.capacity() < capacity()) {
        __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(end()));
        __t.__set_sentinel(size());
        __swap_without_allocator(__t);
      }
#if _LIBCPP_HAS_EXCEPTIONS
    } catch (...) {
    }
#endif // _LIBCPP_HAS_EXCEPTIONS
  }
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
template <class... _Args>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::emplace_front(_Args&&... __args) {
  if (__front_spare() == 0) {
    pointer __end = end();
    if (__back_spare() > 0) {
      // The elements are pressed up against the front of the buffer: we need to move them back a
      // little bit to make `emplace_front` have amortised O(1) complexity.
      difference_type __d = __back_spare();
      __d                 = (__d + 1) / 2;
      auto __new_end      = __end + __d;
      __set_valid_range(std::move_backward(begin(), __end, __new_end), __new_end);
    } else {
      size_type __c = std::max<size_type>(2 * capacity(), 1);
      __split_buffer<value_type, __alloc_rr&, _Layout> __t(__c, (__c + 3) / 4, __get_allocator());
      __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(__end));
      __base_type::__swap_without_allocator(__t);
    }
  }

  __alloc_traits::construct(__get_allocator(), std::__to_address(begin() - 1), std::forward<_Args>(__args)...);
  __set_valid_range(begin() - 1, size() + 1);
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
template <class... _Args>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::emplace_back(_Args&&... __args) {
  pointer __end = end();
  if (__back_spare() == 0) {
    if (__front_spare() > 0) {
      difference_type __d = __front_spare();
      __d                 = (__d + 1) / 2;
      __end               = std::move(begin(), __end, begin() - __d);
      __set_valid_range(begin() - __d, __end);
    } else {
      size_type __c = std::max<size_type>(2 * capacity(), 1);
      __split_buffer<value_type, __alloc_rr&, _Layout> __t(__c, __c / 4, __get_allocator());
      __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(__end));
      __base_type::__swap_without_allocator(__t);
    }
  }

  __alloc_traits::construct(__get_allocator(), std::__to_address(__end), std::forward<_Args>(__args)...);
  __set_sentinel(++__end);
}

template <class _Tp, class _Allocator, template <class, class, class> class _Layout>
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
swap(__split_buffer<_Tp, _Allocator, _Layout>& __x, __split_buffer<_Tp, _Allocator, _Layout>& __y)
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
  __x.swap(__y);
}

_LIBCPP_END_NAMESPACE_STD

_LIBCPP_POP_MACROS

#endif // _LIBCPP___SPLIT_BUFFER