865 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___SPLIT_BUFFER11#define _LIBCPP___SPLIT_BUFFER12 13#include <__algorithm/max.h>14#include <__algorithm/move.h>15#include <__algorithm/move_backward.h>16#include <__assert>17#include <__config>18#include <__iterator/distance.h>19#include <__iterator/iterator_traits.h>20#include <__iterator/move_iterator.h>21#include <__memory/addressof.h>22#include <__memory/allocate_at_least.h>23#include <__memory/allocator.h>24#include <__memory/allocator_traits.h>25#include <__memory/compressed_pair.h>26#include <__memory/pointer_traits.h>27#include <__memory/swap_allocator.h>28#include <__type_traits/conditional.h>29#include <__type_traits/enable_if.h>30#include <__type_traits/integral_constant.h>31#include <__type_traits/is_nothrow_assignable.h>32#include <__type_traits/is_nothrow_constructible.h>33#include <__type_traits/is_swappable.h>34#include <__type_traits/is_trivially_destructible.h>35#include <__type_traits/is_trivially_relocatable.h>36#include <__type_traits/remove_reference.h>37#include <__utility/forward.h>38#include <__utility/move.h>39 40#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)41# pragma GCC system_header42#endif43 44_LIBCPP_PUSH_MACROS45#include <__undef_macros>46 47_LIBCPP_BEGIN_NAMESPACE_STD48 49template <class _Tp, class _Allocator, template <class, class, class> class _Layout>50class __split_buffer;51 52template <class _SplitBuffer, class _Tp, class _Allocator>53class __split_buffer_pointer_layout {54protected:55 using value_type = _Tp;56 using allocator_type = _Allocator;57 using __alloc_rr _LIBCPP_NODEBUG = __libcpp_remove_reference_t<allocator_type>;58 using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<__alloc_rr>;59 using reference = value_type&;60 using const_reference = const value_type&;61 using size_type = typename __alloc_traits::size_type;62 using difference_type = typename __alloc_traits::difference_type;63 using pointer = typename __alloc_traits::pointer;64 using const_pointer = typename __alloc_traits::const_pointer;65 using iterator = pointer;66 using const_iterator = const_pointer;67 using __sentinel_type _LIBCPP_NODEBUG = pointer;68 69public:70 // Can't be defaulted due to _LIBCPP_COMPRESSED_PAIR not being an aggregate in C++03 and C++11.71 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer_pointer_layout() : __back_cap_(nullptr) {}72 73 _LIBCPP_CONSTEXPR_SINCE_CXX2074 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer_pointer_layout(const allocator_type& __alloc)75 : __back_cap_(nullptr), __alloc_(__alloc) {}76 77 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer __front_cap() _NOEXCEPT { return __front_cap_; }78 79 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer __front_cap() const _NOEXCEPT {80 return __front_cap_;81 }82 83 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer begin() _NOEXCEPT { return __begin_; }84 85 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer begin() const _NOEXCEPT { return __begin_; }86 87 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() _NOEXCEPT { return __end_; }88 89 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() const _NOEXCEPT { return __end_; }90 91 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT {92 return static_cast<size_type>(__end_ - __begin_);93 }94 95 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __begin_ == __end_; }96 97 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT {98 return static_cast<size_type>(__back_cap_ - __front_cap_);99 }100 101 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type& __get_allocator() _NOEXCEPT { return __alloc_; }102 103 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type const& __get_allocator() const _NOEXCEPT {104 return __alloc_;105 }106 107 // Returns the sentinel object directly. Should be used in conjunction with automatic type deduction,108 // not explicit types.109 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_sentinel() const _NOEXCEPT {110 return __end_;111 }112 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_capacity() const _NOEXCEPT {113 return __back_cap_;114 }115 116 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_data(pointer __new_first) _NOEXCEPT {117 __front_cap_ = __new_first;118 }119 120 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void121 __set_valid_range(pointer __new_begin, pointer __new_end) _NOEXCEPT {122 __begin_ = __new_begin;123 __end_ = __new_end;124 }125 126 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void127 __set_valid_range(pointer __new_begin, size_type __new_size) _NOEXCEPT {128 __begin_ = __new_begin;129 __end_ = __begin_ + __new_size;130 }131 132 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(pointer __new_end) _NOEXCEPT {133 _LIBCPP_ASSERT_INTERNAL(__front_cap_ <= __new_end, "__new_end cannot precede __front_cap_");134 __end_ = __new_end;135 }136 137 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(size_type __new_size) _NOEXCEPT {138 __end_ = __begin_ + __new_size;139 }140 141 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(size_type __new_capacity) _NOEXCEPT {142 __back_cap_ = __front_cap_ + __new_capacity;143 }144 145 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(pointer __new_capacity) _NOEXCEPT {146 __back_cap_ = __new_capacity;147 }148 149 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const _NOEXCEPT {150 return static_cast<size_type>(__begin_ - __front_cap_);151 }152 153 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const _NOEXCEPT {154 return static_cast<size_type>(__back_cap_ - __end_);155 }156 157 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT { return *(__end_ - 1); }158 159 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT { return *(__end_ - 1); }160 161 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator(162 __split_buffer_pointer_layout<__split_buffer<value_type, __alloc_rr&, __split_buffer_pointer_layout>,163 value_type,164 __alloc_rr&>& __other) _NOEXCEPT {165 std::swap(__front_cap_, __other.__front_cap_);166 std::swap(__begin_, __other.__begin_);167 std::swap(__back_cap_, __other.__back_cap_);168 std::swap(__end_, __other.__end_);169 }170 171 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer_pointer_layout& __other) _NOEXCEPT {172 std::swap(__front_cap_, __other.__front_cap_);173 std::swap(__begin_, __other.__begin_);174 std::swap(__back_cap_, __other.__back_cap_);175 std::swap(__end_, __other.__end_);176 std::__swap_allocator(__alloc_, __other.__alloc_);177 }178 179 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __reset() _NOEXCEPT {180 __front_cap_ = nullptr;181 __begin_ = nullptr;182 __end_ = nullptr;183 __back_cap_ = nullptr;184 }185 186 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void187 __copy_without_alloc(__split_buffer_pointer_layout const& __other)188 _NOEXCEPT_(is_nothrow_copy_assignable<pointer>::value) {189 __front_cap_ = __other.__front_cap_;190 __begin_ = __other.__begin_;191 __end_ = __other.__end_;192 __back_cap_ = __other.__back_cap_;193 }194 195private:196 pointer __front_cap_ = nullptr;197 pointer __begin_ = nullptr;198 pointer __end_ = nullptr;199 _LIBCPP_COMPRESSED_PAIR(pointer, __back_cap_, allocator_type, __alloc_);200 201 template <class, class, class>202 friend class __split_buffer_pointer_layout;203};204 205template <class _SplitBuffer, class _Tp, class _Allocator>206class __split_buffer_size_layout {207protected:208 using value_type = _Tp;209 using allocator_type = _Allocator;210 using __alloc_rr _LIBCPP_NODEBUG = __libcpp_remove_reference_t<allocator_type>;211 using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<__alloc_rr>;212 using reference = value_type&;213 using const_reference = const value_type&;214 using size_type = typename __alloc_traits::size_type;215 using difference_type = typename __alloc_traits::difference_type;216 using pointer = typename __alloc_traits::pointer;217 using const_pointer = typename __alloc_traits::const_pointer;218 using iterator = pointer;219 using const_iterator = const_pointer;220 using __sentinel_type _LIBCPP_NODEBUG = size_type;221 222public:223 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer_size_layout() = default;224 225 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer_size_layout(const allocator_type& __alloc)226 : __alloc_(__alloc) {}227 228 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer __front_cap() _NOEXCEPT { return __front_cap_; }229 230 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer __front_cap() const _NOEXCEPT {231 return __front_cap_;232 }233 234 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer begin() _NOEXCEPT { return __begin_; }235 236 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer begin() const _NOEXCEPT { return __begin_; }237 238 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() _NOEXCEPT { return __begin_ + __size_; }239 240 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() const _NOEXCEPT { return __begin_ + __size_; }241 242 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }243 244 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __size_ == 0; }245 246 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT { return __cap_; }247 248 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type& __get_allocator() _NOEXCEPT { return __alloc_; }249 250 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type const& __get_allocator() const _NOEXCEPT {251 return __alloc_;252 }253 254 // Returns the sentinel object directly. Should be used in conjunction with automatic type deduction,255 // not explicit types.256 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_sentinel() const _NOEXCEPT {257 return __size_;258 }259 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_capacity() const _NOEXCEPT {260 return __cap_;261 }262 263 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_data(pointer __new_first) _NOEXCEPT {264 __front_cap_ = __new_first;265 }266 267 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void268 __set_valid_range(pointer __new_begin, pointer __new_end) _NOEXCEPT {269 // Size-based __split_buffers track their size directly: we need to explicitly update the size270 // when the front is adjusted.271 __size_ -= __new_begin - __begin_;272 __begin_ = __new_begin;273 __set_sentinel(__new_end);274 }275 276 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void277 __set_valid_range(pointer __new_begin, size_type __new_size) _NOEXCEPT {278 // Size-based __split_buffers track their size directly: we need to explicitly update the size279 // when the front is adjusted.280 __size_ -= __new_begin - __begin_;281 __begin_ = __new_begin;282 __set_sentinel(__new_size);283 }284 285 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(pointer __new_end) _NOEXCEPT {286 _LIBCPP_ASSERT_INTERNAL(__front_cap_ <= __new_end, "__new_end cannot precede __front_cap_");287 __size_ += __new_end - end();288 }289 290 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(size_type __new_size) _NOEXCEPT {291 __size_ = __new_size;292 }293 294 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(size_type __new_capacity) _NOEXCEPT {295 __cap_ = __new_capacity;296 }297 298 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(pointer __new_capacity) _NOEXCEPT {299 __cap_ = __new_capacity - __begin_;300 }301 302 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const _NOEXCEPT {303 return static_cast<size_type>(__begin_ - __front_cap_);304 }305 306 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const _NOEXCEPT {307 // `__cap_ - __end_` tells us the total number of spares when in size-mode. We need to remove308 // the __front_spare from the count.309 return __cap_ - __size_ - __front_spare();310 }311 312 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT { return __begin_[__size_ - 1]; }313 314 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT {315 return __begin_[__size_ - 1];316 }317 318 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator(319 __split_buffer_pointer_layout<__split_buffer<value_type, __alloc_rr&, __split_buffer_pointer_layout>,320 value_type,321 __alloc_rr&>& __other) _NOEXCEPT {322 std::swap(__front_cap_, __other.__front_cap_);323 std::swap(__begin_, __other.__begin_);324 std::swap(__cap_, __other.__cap_);325 std::swap(__size_, __other.__size_);326 }327 328 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer_size_layout& __other) _NOEXCEPT {329 std::swap(__front_cap_, __other.__front_cap_);330 std::swap(__begin_, __other.__begin_);331 std::swap(__cap_, __other.__cap_);332 std::swap(__size_, __other.__size_);333 std::__swap_allocator(__alloc_, __other.__alloc_);334 }335 336 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __reset() _NOEXCEPT {337 __front_cap_ = nullptr;338 __begin_ = nullptr;339 __size_ = 0;340 __cap_ = 0;341 }342 343 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void344 __copy_without_alloc(__split_buffer_size_layout const& __other)345 _NOEXCEPT_(is_nothrow_copy_assignable<pointer>::value) {346 __front_cap_ = __other.__front_cap_;347 __begin_ = __other.__begin_;348 __cap_ = __other.__cap_;349 __size_ = __other.__size_;350 }351 352private:353 pointer __front_cap_ = nullptr;354 pointer __begin_ = nullptr;355 size_type __size_ = 0;356 size_type __cap_ = 0;357 _LIBCPP_NO_UNIQUE_ADDRESS allocator_type __alloc_;358 359 template <class, class, class>360 friend class __split_buffer_size_layout;361};362 363// `__split_buffer` is a contiguous array data structure. It may hold spare capacity at both ends of364// the sequence. This allows for a `__split_buffer` to grow from both the front and the back without365// relocating its contents until it runs out of room. This characteristic sets it apart from366// `std::vector`, which only holds spare capacity at its end. As such, `__split_buffer` is useful367// for implementing both `std::vector` and `std::deque`.368//369// The sequence is stored as a contiguous chunk of memory delimited by the following "pointers" (`o` denotes370// uninitialized memory and `x` denotes a valid object):371//372// |oooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoooooooooooooooooooooooo|373// ^ ^ ^ ^374// __front_cap_ __begin_ __end_ __back_cap_375//376// The range [__front_cap_, __begin_) contains uninitialized memory. It is referred to as the "front spare capacity".377// The range [__begin_, __end_) contains valid objects. It is referred to as the "valid range".378// The range [__end_, __back_cap_) contains uninitialized memory. It is referred to as the "back spare capacity".379//380// The layout of `__split_buffer` is determined by the `_Layout` template template parameter. This381// `_Layout` allows the above pointers to be stored as different representations, such as integer382// offsets. A layout class template must provide the following interface:383//384// template<class _Tp, class _Allocator, class _Layout>385// class __layout {386// protected:387// using value_type = _Tp;388// using allocator_type = _Allocator;389// using __alloc_rr = __libcpp_remove_reference_t<allocator_type>;390// using __alloc_traits = allocator_traits<__alloc_rr>;391// using reference = value_type&;392// using const_reference = const value_type&;393// using size_type = typename __alloc_traits::size_type;394// using difference_type = typename __alloc_traits::difference_type;395// using pointer = typename __alloc_traits::pointer;396// using const_pointer = typename __alloc_traits::const_pointer;397// using iterator = pointer;398// using const_iterator = const_pointer;399// using __sentinel_type = /* type that represents the layout's sentinel */;400//401// public:402// __layout() = default;403// explicit __layout(const allocator_type&);404//405// pointer __front_cap();406// const_pointer __front_cap() const;407//408// pointer begin();409// const_pointer begin() const;410//411// pointer end();412// pointer end() const;413//414// size_type size() const;415// bool empty() const;416// size_type capacity() const;417//418// allocator_type& __get_allocator();419// allocator_type const& __get_allocator() const;420//421// __sentinel_type __raw_sentinel() const;422// __sentinel_type __raw_capacity() const;423//424// void __set_data(pointer);425// void __set_valid_range(pointer __begin, pointer __end);426// void __set_valid_range(pointer __begin, size_type __size);427// void __set_sentinel(pointer __end);428// void __set_sentinel(size_type __size);429//430// void __set_capacity(size_type __capacity);431// void __set_capacity(pointer __capacity);432//433// size_type __front_spare() const;434// size_type __back_spare() const;435//436// reference back();437// const_reference back() const;438//439// template<class _OtherLayout>440// void __swap_without_allocator(_OtherLayout&);441// void swap(__layout&);442//443// void __reset();444// void __copy_without_alloc(__layout const&);445// };446//447template <class _Tp, class _Allocator, template <class, class, class> class _Layout>448class __split_buffer : _Layout<__split_buffer<_Tp, _Allocator, _Layout>, _Tp, _Allocator> {449 using __base_type _LIBCPP_NODEBUG = _Layout<__split_buffer<_Tp, _Allocator, _Layout>, _Tp, _Allocator>;450 451public:452 using __base_type::__back_spare;453 using __base_type::__copy_without_alloc;454 using __base_type::__front_cap;455 using __base_type::__front_spare;456 using __base_type::__get_allocator;457 using __base_type::__raw_capacity;458 using __base_type::__raw_sentinel;459 using __base_type::__reset;460 using __base_type::__set_capacity;461 using __base_type::__set_data;462 using __base_type::__set_sentinel;463 using __base_type::__set_valid_range;464 465 using typename __base_type::__alloc_rr;466 using typename __base_type::__alloc_traits;467 using typename __base_type::allocator_type;468 using typename __base_type::const_iterator;469 using typename __base_type::const_pointer;470 using typename __base_type::const_reference;471 using typename __base_type::difference_type;472 using typename __base_type::iterator;473 using typename __base_type::pointer;474 using typename __base_type::reference;475 using typename __base_type::size_type;476 using typename __base_type::value_type;477 478 // A __split_buffer contains the following members which may be trivially relocatable:479 // - pointer: may be trivially relocatable, so it's checked480 // - allocator_type: may be trivially relocatable, so it's checked481 // __split_buffer doesn't have any self-references, so it's trivially relocatable if its members are.482 using __trivially_relocatable _LIBCPP_NODEBUG = __conditional_t<483 __libcpp_is_trivially_relocatable<pointer>::value && __libcpp_is_trivially_relocatable<allocator_type>::value,484 __split_buffer,485 void>;486 487 __split_buffer(const __split_buffer&) = delete;488 __split_buffer& operator=(const __split_buffer&) = delete;489 490 _LIBCPP_HIDE_FROM_ABI __split_buffer() = default;491 492 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(__alloc_rr& __a) : __base_type(__a) {}493 494 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(const __alloc_rr& __a)495 : __base_type(__a) {}496 497 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI498 __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a);499 500 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer(__split_buffer&& __c)501 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);502 503 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer(__split_buffer&& __c, const __alloc_rr& __a);504 505 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer& operator=(__split_buffer&& __c)506 _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&507 is_nothrow_move_assignable<allocator_type>::value) ||508 !__alloc_traits::propagate_on_container_move_assignment::value);509 510 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~__split_buffer();511 512 using __base_type::back;513 using __base_type::begin;514 using __base_type::capacity;515 using __base_type::empty;516 using __base_type::end;517 using __base_type::size;518 519 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __destruct_at_end(begin()); }520 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() { return *begin(); }521 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return *begin(); }522 523 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;524 525 template <class... _Args>526 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void emplace_front(_Args&&... __args);527 template <class... _Args>528 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args);529 530 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_front() { __destruct_at_begin(begin() + 1); }531 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back() { __destruct_at_end(end() - 1); }532 533 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n);534 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x);535 536 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>537 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void538 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);539 540 template <class _Iterator, class _Sentinel>541 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void542 __construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last);543 544 template <class _Iterator>545 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void546 __construct_at_end_with_size(_Iterator __first, size_type __n);547 548 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin) {549 __destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());550 }551 552 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin, false_type);553 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin, true_type);554 555 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT {556 __destruct_at_end(__new_last, false_type());557 }558 559 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;560 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;561 562 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer& __x)563 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>);564 565 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const {566 if (__front_cap() == nullptr) {567 if (begin() != nullptr)568 return false;569 570 if (!empty())571 return false;572 573 if (capacity() != 0)574 return false;575 576 return true;577 } else {578 if (begin() < __front_cap())579 return false;580 581 if (capacity() < size())582 return false;583 584 if (end() < begin())585 return false;586 587 return true;588 }589 }590 591 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void592 __swap_without_allocator(__split_buffer<value_type, __alloc_rr&, _Layout>& __other) _NOEXCEPT {593 __base_type::__swap_without_allocator(__other);594 }595 596private:597 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer& __c, true_type)598 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {599 __get_allocator() = std::move(__c.__get_allocator());600 }601 602 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT {}603 604 struct _ConstructTransaction {605 _LIBCPP_CONSTEXPR_SINCE_CXX20606 _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(__split_buffer* __parent, pointer __p, size_type __n) _NOEXCEPT607 : __pos_(__p),608 __end_(__p + __n),609 __parent_(__parent) {}610 611 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { __parent_->__set_sentinel(__pos_); }612 613 pointer __pos_;614 const pointer __end_;615 616 private:617 __split_buffer* __parent_;618 };619 620 template <class _T2, class _A2, template <class, class, class> class _L2>621 friend class __split_buffer;622};623 624// Default constructs __n objects starting at `end()`625// throws if construction throws626// Precondition: __n > 0627// Precondition: size() + __n <= capacity()628// Postcondition: size() == size() + __n629template <class _Tp, class _Allocator, template <class, class, class> class _Layout>630_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(size_type __n) {631 _ConstructTransaction __tx(this, end(), __n);632 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {633 __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_));634 }635}636 637// Copy constructs __n objects starting at `end()` from __x638// throws if construction throws639// Precondition: __n > 0640// Precondition: size() + __n <= capacity()641// Postcondition: size() == old size() + __n642// Postcondition: [i] == __x for all i in [size() - __n, __n)643template <class _Tp, class _Allocator, template <class, class, class> class _Layout>644_LIBCPP_CONSTEXPR_SINCE_CXX20 void645__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(size_type __n, const_reference __x) {646 _ConstructTransaction __tx(this, end(), __n);647 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {648 __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_), __x);649 }650}651 652template <class _Tp, class _Allocator, template <class, class, class> class _Layout>653template <class _Iterator, class _Sentinel>654_LIBCPP_CONSTEXPR_SINCE_CXX20 void655__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) {656 __alloc_rr& __a = __get_allocator();657 for (; __first != __last; ++__first) {658 if (__back_spare() == 0) {659 size_type __old_cap = capacity();660 size_type __new_cap = std::max<size_type>(2 * __old_cap, 8);661 __split_buffer __buf(__new_cap, 0, __a);662 pointer __buf_end = __buf.end();663 pointer __end = end();664 for (pointer __p = begin(); __p != __end; ++__p) {665 __alloc_traits::construct(__buf.__get_allocator(), std::__to_address(__buf_end), std::move(*__p));666 __buf.__set_sentinel(++__buf_end);667 }668 swap(__buf);669 }670 671 __alloc_traits::construct(__a, std::__to_address(end()), *__first);672 __set_sentinel(size() + 1);673 }674}675 676template <class _Tp, class _Allocator, template <class, class, class> class _Layout>677template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >678_LIBCPP_CONSTEXPR_SINCE_CXX20 void679__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) {680 __construct_at_end_with_size(__first, std::distance(__first, __last));681}682 683template <class _Tp, class _Allocator, template <class, class, class> class _Layout>684template <class _ForwardIterator>685_LIBCPP_CONSTEXPR_SINCE_CXX20 void686__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) {687 _ConstructTransaction __tx(this, end(), __n);688 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__first) {689 __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_), *__first);690 }691}692 693template <class _Tp, class _Allocator, template <class, class, class> class _Layout>694_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void695__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_begin(pointer __new_begin, false_type) {696 pointer __begin = begin();697 // Updating begin at every iteration is unnecessary because destruction can't throw.698 while (__begin != __new_begin)699 __alloc_traits::destroy(__get_allocator(), std::__to_address(__begin++));700 __set_valid_range(__begin, end());701}702 703template <class _Tp, class _Allocator, template <class, class, class> class _Layout>704_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void705__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_begin(pointer __new_begin, true_type) {706 __set_valid_range(__new_begin, end());707}708 709template <class _Tp, class _Allocator, template <class, class, class> class _Layout>710_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void711__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT {712 pointer __end = end();713 // Updating begin at every iteration is unnecessary because destruction can't throw.714 while (__new_last != __end)715 __alloc_traits::destroy(__get_allocator(), std::__to_address(--__end));716 __set_sentinel(__end);717}718 719template <class _Tp, class _Allocator, template <class, class, class> class _Layout>720_LIBCPP_CONSTEXPR_SINCE_CXX20721__split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)722 : __base_type(__a) {723 _LIBCPP_ASSERT_INTERNAL(__cap >= __start, "can't have a start point outside the capacity");724 if (__cap > 0) {725 auto __allocation = std::__allocate_at_least(__get_allocator(), __cap);726 __set_data(__allocation.ptr);727 __cap = __allocation.count;728 }729 730 pointer __begin = __front_cap() + __start;731 __set_valid_range(__begin, __begin);732 __set_capacity(__cap);733}734 735template <class _Tp, class _Allocator, template <class, class, class> class _Layout>736_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>::~__split_buffer() {737 clear();738 if (__front_cap())739 __alloc_traits::deallocate(__get_allocator(), __front_cap(), capacity());740}741 742template <class _Tp, class _Allocator, template <class, class, class> class _Layout>743_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(__split_buffer&& __c)744 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)745 : __base_type(std::move(__c)) {746 __c.__reset();747}748 749template <class _Tp, class _Allocator, template <class, class, class> class _Layout>750_LIBCPP_CONSTEXPR_SINCE_CXX20751__split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a)752 : __base_type(__a) {753 if (__a == __c.__get_allocator()) {754 __set_data(__c.__front_cap());755 __set_valid_range(__c.begin(), __c.end());756 __set_capacity(__c.capacity());757 __c.__reset();758 } else {759 auto __allocation = std::__allocate_at_least(__get_allocator(), __c.size());760 __set_data(__allocation.ptr);761 __set_valid_range(__front_cap(), __front_cap());762 __set_capacity(__allocation.count);763 typedef move_iterator<iterator> _Ip;764 __construct_at_end(_Ip(__c.begin()), _Ip(__c.end()));765 }766}767 768template <class _Tp, class _Allocator, template <class, class, class> class _Layout>769_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>&770__split_buffer<_Tp, _Allocator, _Layout>::operator=(__split_buffer&& __c)771 _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&772 is_nothrow_move_assignable<allocator_type>::value) ||773 !__alloc_traits::propagate_on_container_move_assignment::value) {774 clear();775 shrink_to_fit();776 __copy_without_alloc(__c);777 __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());778 __c.__reset();779 return *this;780}781 782template <class _Tp, class _Allocator, template <class, class, class> class _Layout>783_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::swap(__split_buffer& __x)784 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>) {785 __base_type::swap(__x);786}787 788template <class _Tp, class _Allocator, template <class, class, class> class _Layout>789_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::shrink_to_fit() _NOEXCEPT {790 if (capacity() > size()) {791#if _LIBCPP_HAS_EXCEPTIONS792 try {793#endif // _LIBCPP_HAS_EXCEPTIONS794 __split_buffer<value_type, __alloc_rr&, _Layout> __t(size(), 0, __get_allocator());795 if (__t.capacity() < capacity()) {796 __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(end()));797 __t.__set_sentinel(size());798 __swap_without_allocator(__t);799 }800#if _LIBCPP_HAS_EXCEPTIONS801 } catch (...) {802 }803#endif // _LIBCPP_HAS_EXCEPTIONS804 }805}806 807template <class _Tp, class _Allocator, template <class, class, class> class _Layout>808template <class... _Args>809_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::emplace_front(_Args&&... __args) {810 if (__front_spare() == 0) {811 pointer __end = end();812 if (__back_spare() > 0) {813 // The elements are pressed up against the front of the buffer: we need to move them back a814 // little bit to make `emplace_front` have amortised O(1) complexity.815 difference_type __d = __back_spare();816 __d = (__d + 1) / 2;817 auto __new_end = __end + __d;818 __set_valid_range(std::move_backward(begin(), __end, __new_end), __new_end);819 } else {820 size_type __c = std::max<size_type>(2 * capacity(), 1);821 __split_buffer<value_type, __alloc_rr&, _Layout> __t(__c, (__c + 3) / 4, __get_allocator());822 __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(__end));823 __base_type::__swap_without_allocator(__t);824 }825 }826 827 __alloc_traits::construct(__get_allocator(), std::__to_address(begin() - 1), std::forward<_Args>(__args)...);828 __set_valid_range(begin() - 1, size() + 1);829}830 831template <class _Tp, class _Allocator, template <class, class, class> class _Layout>832template <class... _Args>833_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::emplace_back(_Args&&... __args) {834 pointer __end = end();835 if (__back_spare() == 0) {836 if (__front_spare() > 0) {837 difference_type __d = __front_spare();838 __d = (__d + 1) / 2;839 __end = std::move(begin(), __end, begin() - __d);840 __set_valid_range(begin() - __d, __end);841 } else {842 size_type __c = std::max<size_type>(2 * capacity(), 1);843 __split_buffer<value_type, __alloc_rr&, _Layout> __t(__c, __c / 4, __get_allocator());844 __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(__end));845 __base_type::__swap_without_allocator(__t);846 }847 }848 849 __alloc_traits::construct(__get_allocator(), std::__to_address(__end), std::forward<_Args>(__args)...);850 __set_sentinel(++__end);851}852 853template <class _Tp, class _Allocator, template <class, class, class> class _Layout>854_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void855swap(__split_buffer<_Tp, _Allocator, _Layout>& __x, __split_buffer<_Tp, _Allocator, _Layout>& __y)856 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {857 __x.swap(__y);858}859 860_LIBCPP_END_NAMESPACE_STD861 862_LIBCPP_POP_MACROS863 864#endif // _LIBCPP___SPLIT_BUFFER865