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