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