Warning, /include/c++/v1/__cxx03/__split_buffer is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03___SPLIT_BUFFER
0011 #define _LIBCPP___CXX03___SPLIT_BUFFER
0012
0013 #include <__cxx03/__algorithm/max.h>
0014 #include <__cxx03/__algorithm/move.h>
0015 #include <__cxx03/__algorithm/move_backward.h>
0016 #include <__cxx03/__config>
0017 #include <__cxx03/__iterator/distance.h>
0018 #include <__cxx03/__iterator/iterator_traits.h>
0019 #include <__cxx03/__iterator/move_iterator.h>
0020 #include <__cxx03/__memory/allocate_at_least.h>
0021 #include <__cxx03/__memory/allocator.h>
0022 #include <__cxx03/__memory/allocator_traits.h>
0023 #include <__cxx03/__memory/compressed_pair.h>
0024 #include <__cxx03/__memory/pointer_traits.h>
0025 #include <__cxx03/__memory/swap_allocator.h>
0026 #include <__cxx03/__type_traits/add_lvalue_reference.h>
0027 #include <__cxx03/__type_traits/conditional.h>
0028 #include <__cxx03/__type_traits/enable_if.h>
0029 #include <__cxx03/__type_traits/integral_constant.h>
0030 #include <__cxx03/__type_traits/is_nothrow_assignable.h>
0031 #include <__cxx03/__type_traits/is_nothrow_constructible.h>
0032 #include <__cxx03/__type_traits/is_swappable.h>
0033 #include <__cxx03/__type_traits/is_trivially_destructible.h>
0034 #include <__cxx03/__type_traits/is_trivially_relocatable.h>
0035 #include <__cxx03/__type_traits/remove_reference.h>
0036 #include <__cxx03/__utility/forward.h>
0037 #include <__cxx03/__utility/move.h>
0038 #include <__cxx03/cstddef>
0039
0040 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0041 # pragma GCC system_header
0042 #endif
0043
0044 _LIBCPP_PUSH_MACROS
0045 #include <__cxx03/__undef_macros>
0046
0047 _LIBCPP_BEGIN_NAMESPACE_STD
0048
0049 // __split_buffer allocates a contiguous chunk of memory and stores objects in the range [__begin_, __end_).
0050 // It has uninitialized memory in the ranges [__first_, __begin_) and [__end_, __end_cap_.first()). That allows
0051 // it to grow both in the front and back without having to move the data.
0052
0053 template <class _Tp, class _Allocator = allocator<_Tp> >
0054 struct __split_buffer {
0055 public:
0056 using value_type = _Tp;
0057 using allocator_type = _Allocator;
0058 using __alloc_rr = __libcpp_remove_reference_t<allocator_type>;
0059 using __alloc_traits = allocator_traits<__alloc_rr>;
0060 using reference = value_type&;
0061 using const_reference = const value_type&;
0062 using size_type = typename __alloc_traits::size_type;
0063 using difference_type = typename __alloc_traits::difference_type;
0064 using pointer = typename __alloc_traits::pointer;
0065 using const_pointer = typename __alloc_traits::const_pointer;
0066 using iterator = pointer;
0067 using const_iterator = const_pointer;
0068
0069 // A __split_buffer contains the following members which may be trivially relocatable:
0070 // - pointer: may be trivially relocatable, so it's checked
0071 // - allocator_type: may be trivially relocatable, so it's checked
0072 // __split_buffer doesn't have any self-references, so it's trivially relocatable if its members are.
0073 using __trivially_relocatable = __conditional_t<
0074 __libcpp_is_trivially_relocatable<pointer>::value && __libcpp_is_trivially_relocatable<allocator_type>::value,
0075 __split_buffer,
0076 void>;
0077
0078 pointer __first_;
0079 pointer __begin_;
0080 pointer __end_;
0081 __compressed_pair<pointer, allocator_type> __end_cap_;
0082
0083 using __alloc_ref = __add_lvalue_reference_t<allocator_type>;
0084 using __alloc_const_ref = __add_lvalue_reference_t<allocator_type>;
0085
0086 __split_buffer(const __split_buffer&) = delete;
0087 __split_buffer& operator=(const __split_buffer&) = delete;
0088
0089 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer()
0090 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
0091 : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __default_init_tag()) {}
0092
0093 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(__alloc_rr& __a)
0094 : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) {}
0095
0096 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(const __alloc_rr& __a)
0097 : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) {}
0098
0099 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
0100 __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a);
0101
0102 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer(__split_buffer&& __c)
0103 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
0104
0105 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer(__split_buffer&& __c, const __alloc_rr& __a);
0106
0107 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer& operator=(__split_buffer&& __c)
0108 _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
0109 is_nothrow_move_assignable<allocator_type>::value) ||
0110 !__alloc_traits::propagate_on_container_move_assignment::value);
0111
0112 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~__split_buffer();
0113
0114 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __alloc_rr& __alloc() _NOEXCEPT { return __end_cap_.second(); }
0115 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const __alloc_rr& __alloc() const _NOEXCEPT {
0116 return __end_cap_.second();
0117 }
0118
0119 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer& __end_cap() _NOEXCEPT { return __end_cap_.first(); }
0120 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const pointer& __end_cap() const _NOEXCEPT {
0121 return __end_cap_.first();
0122 }
0123
0124 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __begin_; }
0125 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __begin_; }
0126
0127 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __end_; }
0128 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __end_; }
0129
0130 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __destruct_at_end(__begin_); }
0131
0132 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const {
0133 return static_cast<size_type>(__end_ - __begin_);
0134 }
0135
0136 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __end_ == __begin_; }
0137
0138 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const {
0139 return static_cast<size_type>(__end_cap() - __first_);
0140 }
0141
0142 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const {
0143 return static_cast<size_type>(__begin_ - __first_);
0144 }
0145
0146 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const {
0147 return static_cast<size_type>(__end_cap() - __end_);
0148 }
0149
0150 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() { return *__begin_; }
0151 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return *__begin_; }
0152 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() { return *(__end_ - 1); }
0153 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return *(__end_ - 1); }
0154
0155 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n);
0156 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;
0157 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_front(const_reference __x);
0158 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_back(const_reference __x);
0159 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_front(value_type&& __x);
0160 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x);
0161
0162 template <class... _Args>
0163 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args);
0164
0165 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_front() { __destruct_at_begin(__begin_ + 1); }
0166 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back() { __destruct_at_end(__end_ - 1); }
0167
0168 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n);
0169 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x);
0170
0171 template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> = 0>
0172 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(_InputIter __first, _InputIter __last);
0173
0174 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
0175 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0176 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
0177
0178 template <class _Iterator, class _Sentinel>
0179 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0180 __construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last);
0181
0182 template <class _Iterator>
0183 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
0184 __construct_at_end_with_size(_Iterator __first, size_type __n);
0185
0186 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin) {
0187 __destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());
0188 }
0189
0190 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin, false_type);
0191 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin, true_type);
0192
0193 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT {
0194 __destruct_at_end(__new_last, false_type());
0195 }
0196
0197 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;
0198 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;
0199
0200 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer& __x)
0201 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>);
0202
0203 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
0204
0205 private:
0206 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer& __c, true_type)
0207 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
0208 __alloc() = std::move(__c.__alloc());
0209 }
0210
0211 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT {}
0212
0213 struct _ConstructTransaction {
0214 _LIBCPP_CONSTEXPR_SINCE_CXX20
0215 _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(pointer* __p, size_type __n) _NOEXCEPT
0216 : __pos_(*__p),
0217 __end_(*__p + __n),
0218 __dest_(__p) {}
0219
0220 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { *__dest_ = __pos_; }
0221
0222 pointer __pos_;
0223 const pointer __end_;
0224
0225 private:
0226 pointer* __dest_;
0227 };
0228 };
0229
0230 template <class _Tp, class _Allocator>
0231 _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __split_buffer<_Tp, _Allocator>::__invariants() const {
0232 if (__first_ == nullptr) {
0233 if (__begin_ != nullptr)
0234 return false;
0235 if (__end_ != nullptr)
0236 return false;
0237 if (__end_cap() != nullptr)
0238 return false;
0239 } else {
0240 if (__begin_ < __first_)
0241 return false;
0242 if (__end_ < __begin_)
0243 return false;
0244 if (__end_cap() < __end_)
0245 return false;
0246 }
0247 return true;
0248 }
0249
0250 // Default constructs __n objects starting at __end_
0251 // throws if construction throws
0252 // Precondition: __n > 0
0253 // Precondition: size() + __n <= capacity()
0254 // Postcondition: size() == size() + __n
0255 template <class _Tp, class _Allocator>
0256 _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) {
0257 _ConstructTransaction __tx(&this->__end_, __n);
0258 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
0259 __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_));
0260 }
0261 }
0262
0263 // Copy constructs __n objects starting at __end_ from __x
0264 // throws if construction throws
0265 // Precondition: __n > 0
0266 // Precondition: size() + __n <= capacity()
0267 // Postcondition: size() == old size() + __n
0268 // Postcondition: [i] == __x for all i in [size() - __n, __n)
0269 template <class _Tp, class _Allocator>
0270 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0271 __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) {
0272 _ConstructTransaction __tx(&this->__end_, __n);
0273 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
0274 __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_), __x);
0275 }
0276 }
0277
0278 template <class _Tp, class _Allocator>
0279 template <class _InputIter, __enable_if_t<__has_exactly_input_iterator_category<_InputIter>::value, int> >
0280 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0281 __split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last) {
0282 __construct_at_end_with_sentinel(__first, __last);
0283 }
0284
0285 template <class _Tp, class _Allocator>
0286 template <class _Iterator, class _Sentinel>
0287 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0288 __split_buffer<_Tp, _Allocator>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) {
0289 __alloc_rr& __a = this->__alloc();
0290 for (; __first != __last; ++__first) {
0291 if (__end_ == __end_cap()) {
0292 size_type __old_cap = __end_cap() - __first_;
0293 size_type __new_cap = std::max<size_type>(2 * __old_cap, 8);
0294 __split_buffer __buf(__new_cap, 0, __a);
0295 for (pointer __p = __begin_; __p != __end_; ++__p, (void)++__buf.__end_)
0296 __alloc_traits::construct(__buf.__alloc(), std::__to_address(__buf.__end_), std::move(*__p));
0297 swap(__buf);
0298 }
0299 __alloc_traits::construct(__a, std::__to_address(this->__end_), *__first);
0300 ++this->__end_;
0301 }
0302 }
0303 template <class _Tp, class _Allocator>
0304 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
0305 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0306 __split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) {
0307 __construct_at_end_with_size(__first, std::distance(__first, __last));
0308 }
0309
0310 template <class _Tp, class _Allocator>
0311 template <class _ForwardIterator>
0312 _LIBCPP_CONSTEXPR_SINCE_CXX20 void
0313 __split_buffer<_Tp, _Allocator>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) {
0314 _ConstructTransaction __tx(&this->__end_, __n);
0315 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__first) {
0316 __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_), *__first);
0317 }
0318 }
0319
0320 template <class _Tp, class _Allocator>
0321 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
0322 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) {
0323 while (__begin_ != __new_begin)
0324 __alloc_traits::destroy(__alloc(), std::__to_address(__begin_++));
0325 }
0326
0327 template <class _Tp, class _Allocator>
0328 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
0329 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) {
0330 __begin_ = __new_begin;
0331 }
0332
0333 template <class _Tp, class _Allocator>
0334 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
0335 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT {
0336 while (__new_last != __end_)
0337 __alloc_traits::destroy(__alloc(), std::__to_address(--__end_));
0338 }
0339
0340 template <class _Tp, class _Allocator>
0341 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
0342 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT {
0343 __end_ = __new_last;
0344 }
0345
0346 template <class _Tp, class _Allocator>
0347 _LIBCPP_CONSTEXPR_SINCE_CXX20
0348 __split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)
0349 : __end_cap_(nullptr, __a) {
0350 if (__cap == 0) {
0351 __first_ = nullptr;
0352 } else {
0353 auto __allocation = std::__allocate_at_least(__alloc(), __cap);
0354 __first_ = __allocation.ptr;
0355 __cap = __allocation.count;
0356 }
0357 __begin_ = __end_ = __first_ + __start;
0358 __end_cap() = __first_ + __cap;
0359 }
0360
0361 template <class _Tp, class _Allocator>
0362 _LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator>::~__split_buffer() {
0363 clear();
0364 if (__first_)
0365 __alloc_traits::deallocate(__alloc(), __first_, capacity());
0366 }
0367
0368 template <class _Tp, class _Allocator>
0369 _LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c)
0370 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
0371 : __first_(std::move(__c.__first_)),
0372 __begin_(std::move(__c.__begin_)),
0373 __end_(std::move(__c.__end_)),
0374 __end_cap_(std::move(__c.__end_cap_)) {
0375 __c.__first_ = nullptr;
0376 __c.__begin_ = nullptr;
0377 __c.__end_ = nullptr;
0378 __c.__end_cap() = nullptr;
0379 }
0380
0381 template <class _Tp, class _Allocator>
0382 _LIBCPP_CONSTEXPR_SINCE_CXX20
0383 __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a)
0384 : __end_cap_(nullptr, __a) {
0385 if (__a == __c.__alloc()) {
0386 __first_ = __c.__first_;
0387 __begin_ = __c.__begin_;
0388 __end_ = __c.__end_;
0389 __end_cap() = __c.__end_cap();
0390 __c.__first_ = nullptr;
0391 __c.__begin_ = nullptr;
0392 __c.__end_ = nullptr;
0393 __c.__end_cap() = nullptr;
0394 } else {
0395 auto __allocation = std::__allocate_at_least(__alloc(), __c.size());
0396 __first_ = __allocation.ptr;
0397 __begin_ = __end_ = __first_;
0398 __end_cap() = __first_ + __allocation.count;
0399 typedef move_iterator<iterator> _Ip;
0400 __construct_at_end(_Ip(__c.begin()), _Ip(__c.end()));
0401 }
0402 }
0403
0404 template <class _Tp, class _Allocator>
0405 _LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator>&
0406 __split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c)
0407 _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
0408 is_nothrow_move_assignable<allocator_type>::value) ||
0409 !__alloc_traits::propagate_on_container_move_assignment::value) {
0410 clear();
0411 shrink_to_fit();
0412 __first_ = __c.__first_;
0413 __begin_ = __c.__begin_;
0414 __end_ = __c.__end_;
0415 __end_cap() = __c.__end_cap();
0416 __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
0417 __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
0418 return *this;
0419 }
0420
0421 template <class _Tp, class _Allocator>
0422 _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x)
0423 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>) {
0424 std::swap(__first_, __x.__first_);
0425 std::swap(__begin_, __x.__begin_);
0426 std::swap(__end_, __x.__end_);
0427 std::swap(__end_cap(), __x.__end_cap());
0428 std::__swap_allocator(__alloc(), __x.__alloc());
0429 }
0430
0431 template <class _Tp, class _Allocator>
0432 _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::reserve(size_type __n) {
0433 if (__n < capacity()) {
0434 __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc());
0435 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));
0436 std::swap(__first_, __t.__first_);
0437 std::swap(__begin_, __t.__begin_);
0438 std::swap(__end_, __t.__end_);
0439 std::swap(__end_cap(), __t.__end_cap());
0440 }
0441 }
0442
0443 template <class _Tp, class _Allocator>
0444 _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT {
0445 if (capacity() > size()) {
0446 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
0447 try {
0448 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
0449 __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc());
0450 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));
0451 __t.__end_ = __t.__begin_ + (__end_ - __begin_);
0452 std::swap(__first_, __t.__first_);
0453 std::swap(__begin_, __t.__begin_);
0454 std::swap(__end_, __t.__end_);
0455 std::swap(__end_cap(), __t.__end_cap());
0456 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
0457 } catch (...) {
0458 }
0459 #endif // _LIBCPP_HAS_NO_EXCEPTIONS
0460 }
0461 }
0462
0463 template <class _Tp, class _Allocator>
0464 _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::push_front(const_reference __x) {
0465 if (__begin_ == __first_) {
0466 if (__end_ < __end_cap()) {
0467 difference_type __d = __end_cap() - __end_;
0468 __d = (__d + 1) / 2;
0469 __begin_ = std::move_backward(__begin_, __end_, __end_ + __d);
0470 __end_ += __d;
0471 } else {
0472 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
0473 __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
0474 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));
0475 std::swap(__first_, __t.__first_);
0476 std::swap(__begin_, __t.__begin_);
0477 std::swap(__end_, __t.__end_);
0478 std::swap(__end_cap(), __t.__end_cap());
0479 }
0480 }
0481 __alloc_traits::construct(__alloc(), std::__to_address(__begin_ - 1), __x);
0482 --__begin_;
0483 }
0484
0485 template <class _Tp, class _Allocator>
0486 _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::push_front(value_type&& __x) {
0487 if (__begin_ == __first_) {
0488 if (__end_ < __end_cap()) {
0489 difference_type __d = __end_cap() - __end_;
0490 __d = (__d + 1) / 2;
0491 __begin_ = std::move_backward(__begin_, __end_, __end_ + __d);
0492 __end_ += __d;
0493 } else {
0494 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
0495 __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
0496 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));
0497 std::swap(__first_, __t.__first_);
0498 std::swap(__begin_, __t.__begin_);
0499 std::swap(__end_, __t.__end_);
0500 std::swap(__end_cap(), __t.__end_cap());
0501 }
0502 }
0503 __alloc_traits::construct(__alloc(), std::__to_address(__begin_ - 1), std::move(__x));
0504 --__begin_;
0505 }
0506
0507 template <class _Tp, class _Allocator>
0508 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
0509 __split_buffer<_Tp, _Allocator>::push_back(const_reference __x) {
0510 if (__end_ == __end_cap()) {
0511 if (__begin_ > __first_) {
0512 difference_type __d = __begin_ - __first_;
0513 __d = (__d + 1) / 2;
0514 __end_ = std::move(__begin_, __end_, __begin_ - __d);
0515 __begin_ -= __d;
0516 } else {
0517 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
0518 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
0519 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));
0520 std::swap(__first_, __t.__first_);
0521 std::swap(__begin_, __t.__begin_);
0522 std::swap(__end_, __t.__end_);
0523 std::swap(__end_cap(), __t.__end_cap());
0524 }
0525 }
0526 __alloc_traits::construct(__alloc(), std::__to_address(__end_), __x);
0527 ++__end_;
0528 }
0529
0530 template <class _Tp, class _Allocator>
0531 _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::push_back(value_type&& __x) {
0532 if (__end_ == __end_cap()) {
0533 if (__begin_ > __first_) {
0534 difference_type __d = __begin_ - __first_;
0535 __d = (__d + 1) / 2;
0536 __end_ = std::move(__begin_, __end_, __begin_ - __d);
0537 __begin_ -= __d;
0538 } else {
0539 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
0540 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
0541 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));
0542 std::swap(__first_, __t.__first_);
0543 std::swap(__begin_, __t.__begin_);
0544 std::swap(__end_, __t.__end_);
0545 std::swap(__end_cap(), __t.__end_cap());
0546 }
0547 }
0548 __alloc_traits::construct(__alloc(), std::__to_address(__end_), std::move(__x));
0549 ++__end_;
0550 }
0551
0552 template <class _Tp, class _Allocator>
0553 template <class... _Args>
0554 _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args) {
0555 if (__end_ == __end_cap()) {
0556 if (__begin_ > __first_) {
0557 difference_type __d = __begin_ - __first_;
0558 __d = (__d + 1) / 2;
0559 __end_ = std::move(__begin_, __end_, __begin_ - __d);
0560 __begin_ -= __d;
0561 } else {
0562 size_type __c = std::max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
0563 __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
0564 __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_));
0565 std::swap(__first_, __t.__first_);
0566 std::swap(__begin_, __t.__begin_);
0567 std::swap(__end_, __t.__end_);
0568 std::swap(__end_cap(), __t.__end_cap());
0569 }
0570 }
0571 __alloc_traits::construct(__alloc(), std::__to_address(__end_), std::forward<_Args>(__args)...);
0572 ++__end_;
0573 }
0574
0575 template <class _Tp, class _Allocator>
0576 _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
0577 swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
0578 __x.swap(__y);
0579 }
0580
0581 _LIBCPP_END_NAMESPACE_STD
0582
0583 _LIBCPP_POP_MACROS
0584
0585 #endif // _LIBCPP___CXX03___SPLIT_BUFFER
