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