Line data Source code
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___MEMORY_UNINITIALIZED_ALGORITHMS_H
11 : #define _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H
12 :
13 : #include <__algorithm/copy.h>
14 : #include <__algorithm/move.h>
15 : #include <__config>
16 : #include <__iterator/iterator_traits.h>
17 : #include <__iterator/reverse_iterator.h>
18 : #include <__memory/addressof.h>
19 : #include <__memory/allocator_traits.h>
20 : #include <__memory/construct_at.h>
21 : #include <__memory/pointer_traits.h>
22 : #include <__memory/voidify.h>
23 : #include <__type_traits/extent.h>
24 : #include <__type_traits/is_array.h>
25 : #include <__type_traits/is_constant_evaluated.h>
26 : #include <__type_traits/is_trivially_copy_assignable.h>
27 : #include <__type_traits/is_trivially_copy_constructible.h>
28 : #include <__type_traits/is_trivially_move_assignable.h>
29 : #include <__type_traits/is_trivially_move_constructible.h>
30 : #include <__type_traits/is_unbounded_array.h>
31 : #include <__type_traits/negation.h>
32 : #include <__type_traits/remove_const.h>
33 : #include <__type_traits/remove_extent.h>
34 : #include <__utility/exception_guard.h>
35 : #include <__utility/move.h>
36 : #include <__utility/pair.h>
37 : #include <new>
38 :
39 : #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
40 : # pragma GCC system_header
41 : #endif
42 :
43 : _LIBCPP_BEGIN_NAMESPACE_STD
44 :
45 : // This is a simplified version of C++20 `unreachable_sentinel` that doesn't use concepts and thus can be used in any
46 : // language mode.
47 : struct __unreachable_sentinel {
48 : template <class _Iter>
49 : _LIBCPP_HIDE_FROM_ABI friend _LIBCPP_CONSTEXPR bool operator!=(const _Iter&, __unreachable_sentinel) _NOEXCEPT {
50 : return true;
51 : }
52 : };
53 :
54 : // uninitialized_copy
55 :
56 : template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _Sentinel2>
57 : inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator>
58 : __uninitialized_copy(_InputIterator __ifirst, _Sentinel1 __ilast,
59 : _ForwardIterator __ofirst, _Sentinel2 __olast) {
60 : _ForwardIterator __idx = __ofirst;
61 : #ifndef _LIBCPP_NO_EXCEPTIONS
62 : try {
63 : #endif
64 : for (; __ifirst != __ilast && __idx != __olast; ++__ifirst, (void)++__idx)
65 : ::new (_VSTD::__voidify(*__idx)) _ValueType(*__ifirst);
66 : #ifndef _LIBCPP_NO_EXCEPTIONS
67 : } catch (...) {
68 : _VSTD::__destroy(__ofirst, __idx);
69 : throw;
70 : }
71 : #endif
72 :
73 : return pair<_InputIterator, _ForwardIterator>(_VSTD::move(__ifirst), _VSTD::move(__idx));
74 : }
75 :
76 : template <class _InputIterator, class _ForwardIterator>
77 : _LIBCPP_HIDE_FROM_ABI
78 : _ForwardIterator uninitialized_copy(_InputIterator __ifirst, _InputIterator __ilast,
79 : _ForwardIterator __ofirst) {
80 : typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
81 : auto __result = _VSTD::__uninitialized_copy<_ValueType>(_VSTD::move(__ifirst), _VSTD::move(__ilast),
82 : _VSTD::move(__ofirst), __unreachable_sentinel());
83 : return _VSTD::move(__result.second);
84 : }
85 :
86 : // uninitialized_copy_n
87 :
88 : template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _Sentinel>
89 : inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator>
90 : __uninitialized_copy_n(_InputIterator __ifirst, _Size __n,
91 : _ForwardIterator __ofirst, _Sentinel __olast) {
92 : _ForwardIterator __idx = __ofirst;
93 : #ifndef _LIBCPP_NO_EXCEPTIONS
94 : try {
95 : #endif
96 : for (; __n > 0 && __idx != __olast; ++__ifirst, (void)++__idx, (void)--__n)
97 : ::new (_VSTD::__voidify(*__idx)) _ValueType(*__ifirst);
98 : #ifndef _LIBCPP_NO_EXCEPTIONS
99 : } catch (...) {
100 : _VSTD::__destroy(__ofirst, __idx);
101 : throw;
102 : }
103 : #endif
104 :
105 : return pair<_InputIterator, _ForwardIterator>(_VSTD::move(__ifirst), _VSTD::move(__idx));
106 : }
107 :
108 : template <class _InputIterator, class _Size, class _ForwardIterator>
109 : inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator uninitialized_copy_n(_InputIterator __ifirst, _Size __n,
110 : _ForwardIterator __ofirst) {
111 : typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
112 : auto __result = _VSTD::__uninitialized_copy_n<_ValueType>(_VSTD::move(__ifirst), __n, _VSTD::move(__ofirst),
113 : __unreachable_sentinel());
114 : return _VSTD::move(__result.second);
115 : }
116 :
117 : // uninitialized_fill
118 :
119 : template <class _ValueType, class _ForwardIterator, class _Sentinel, class _Tp>
120 : inline _LIBCPP_HIDE_FROM_ABI
121 : _ForwardIterator __uninitialized_fill(_ForwardIterator __first, _Sentinel __last, const _Tp& __x)
122 : {
123 : _ForwardIterator __idx = __first;
124 : #ifndef _LIBCPP_NO_EXCEPTIONS
125 : try
126 : {
127 : #endif
128 : for (; __idx != __last; ++__idx)
129 : ::new (_VSTD::__voidify(*__idx)) _ValueType(__x);
130 : #ifndef _LIBCPP_NO_EXCEPTIONS
131 : }
132 : catch (...)
133 : {
134 : _VSTD::__destroy(__first, __idx);
135 : throw;
136 : }
137 : #endif
138 :
139 : return __idx;
140 : }
141 :
142 : template <class _ForwardIterator, class _Tp>
143 : inline _LIBCPP_HIDE_FROM_ABI
144 : void uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __x)
145 : {
146 : typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
147 : (void)_VSTD::__uninitialized_fill<_ValueType>(__first, __last, __x);
148 : }
149 :
150 : // uninitialized_fill_n
151 :
152 : template <class _ValueType, class _ForwardIterator, class _Size, class _Tp>
153 : inline _LIBCPP_HIDE_FROM_ABI
154 : _ForwardIterator __uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x)
155 : {
156 : _ForwardIterator __idx = __first;
157 : #ifndef _LIBCPP_NO_EXCEPTIONS
158 : try
159 : {
160 : #endif
161 : for (; __n > 0; ++__idx, (void) --__n)
162 : ::new (_VSTD::__voidify(*__idx)) _ValueType(__x);
163 : #ifndef _LIBCPP_NO_EXCEPTIONS
164 : }
165 : catch (...)
166 : {
167 : _VSTD::__destroy(__first, __idx);
168 : throw;
169 : }
170 : #endif
171 :
172 : return __idx;
173 : }
174 :
175 : template <class _ForwardIterator, class _Size, class _Tp>
176 : inline _LIBCPP_HIDE_FROM_ABI
177 : _ForwardIterator uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x)
178 : {
179 : typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
180 : return _VSTD::__uninitialized_fill_n<_ValueType>(__first, __n, __x);
181 : }
182 :
183 : #if _LIBCPP_STD_VER > 14
184 :
185 : // uninitialized_default_construct
186 :
187 : template <class _ValueType, class _ForwardIterator, class _Sentinel>
188 : inline _LIBCPP_HIDE_FROM_ABI
189 : _ForwardIterator __uninitialized_default_construct(_ForwardIterator __first, _Sentinel __last) {
190 : auto __idx = __first;
191 : #ifndef _LIBCPP_NO_EXCEPTIONS
192 : try {
193 : #endif
194 : for (; __idx != __last; ++__idx)
195 : ::new (_VSTD::__voidify(*__idx)) _ValueType;
196 : #ifndef _LIBCPP_NO_EXCEPTIONS
197 : } catch (...) {
198 : _VSTD::__destroy(__first, __idx);
199 : throw;
200 : }
201 : #endif
202 :
203 : return __idx;
204 : }
205 :
206 : template <class _ForwardIterator>
207 : inline _LIBCPP_HIDE_FROM_ABI
208 : void uninitialized_default_construct(_ForwardIterator __first, _ForwardIterator __last) {
209 : using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
210 : (void)_VSTD::__uninitialized_default_construct<_ValueType>(
211 : _VSTD::move(__first), _VSTD::move(__last));
212 : }
213 :
214 : // uninitialized_default_construct_n
215 :
216 : template <class _ValueType, class _ForwardIterator, class _Size>
217 : inline _LIBCPP_HIDE_FROM_ABI
218 : _ForwardIterator __uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {
219 : auto __idx = __first;
220 : #ifndef _LIBCPP_NO_EXCEPTIONS
221 : try {
222 : #endif
223 : for (; __n > 0; ++__idx, (void) --__n)
224 : ::new (_VSTD::__voidify(*__idx)) _ValueType;
225 : #ifndef _LIBCPP_NO_EXCEPTIONS
226 : } catch (...) {
227 : _VSTD::__destroy(__first, __idx);
228 : throw;
229 : }
230 : #endif
231 :
232 : return __idx;
233 : }
234 :
235 : template <class _ForwardIterator, class _Size>
236 : inline _LIBCPP_HIDE_FROM_ABI
237 : _ForwardIterator uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {
238 : using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
239 : return _VSTD::__uninitialized_default_construct_n<_ValueType>(_VSTD::move(__first), __n);
240 : }
241 :
242 : // uninitialized_value_construct
243 :
244 : template <class _ValueType, class _ForwardIterator, class _Sentinel>
245 : inline _LIBCPP_HIDE_FROM_ABI
246 : _ForwardIterator __uninitialized_value_construct(_ForwardIterator __first, _Sentinel __last) {
247 : auto __idx = __first;
248 : #ifndef _LIBCPP_NO_EXCEPTIONS
249 : try {
250 : #endif
251 : for (; __idx != __last; ++__idx)
252 : ::new (_VSTD::__voidify(*__idx)) _ValueType();
253 : #ifndef _LIBCPP_NO_EXCEPTIONS
254 : } catch (...) {
255 : _VSTD::__destroy(__first, __idx);
256 : throw;
257 : }
258 : #endif
259 :
260 : return __idx;
261 : }
262 :
263 : template <class _ForwardIterator>
264 : inline _LIBCPP_HIDE_FROM_ABI
265 : void uninitialized_value_construct(_ForwardIterator __first, _ForwardIterator __last) {
266 : using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
267 : (void)_VSTD::__uninitialized_value_construct<_ValueType>(
268 : _VSTD::move(__first), _VSTD::move(__last));
269 : }
270 :
271 : // uninitialized_value_construct_n
272 :
273 : template <class _ValueType, class _ForwardIterator, class _Size>
274 : inline _LIBCPP_HIDE_FROM_ABI
275 : _ForwardIterator __uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) {
276 : auto __idx = __first;
277 : #ifndef _LIBCPP_NO_EXCEPTIONS
278 : try {
279 : #endif
280 : for (; __n > 0; ++__idx, (void) --__n)
281 : ::new (_VSTD::__voidify(*__idx)) _ValueType();
282 : #ifndef _LIBCPP_NO_EXCEPTIONS
283 : } catch (...) {
284 : _VSTD::__destroy(__first, __idx);
285 : throw;
286 : }
287 : #endif
288 :
289 : return __idx;
290 : }
291 :
292 : template <class _ForwardIterator, class _Size>
293 : inline _LIBCPP_HIDE_FROM_ABI
294 : _ForwardIterator uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) {
295 : using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
296 : return std::__uninitialized_value_construct_n<_ValueType>(_VSTD::move(__first), __n);
297 : }
298 :
299 : // uninitialized_move
300 :
301 : template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _Sentinel2,
302 : class _IterMove>
303 : inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator>
304 : __uninitialized_move(_InputIterator __ifirst, _Sentinel1 __ilast,
305 : _ForwardIterator __ofirst, _Sentinel2 __olast, _IterMove __iter_move) {
306 : auto __idx = __ofirst;
307 : #ifndef _LIBCPP_NO_EXCEPTIONS
308 : try {
309 : #endif
310 : for (; __ifirst != __ilast && __idx != __olast; ++__idx, (void)++__ifirst) {
311 : ::new (_VSTD::__voidify(*__idx)) _ValueType(__iter_move(__ifirst));
312 : }
313 : #ifndef _LIBCPP_NO_EXCEPTIONS
314 : } catch (...) {
315 : _VSTD::__destroy(__ofirst, __idx);
316 : throw;
317 : }
318 : #endif
319 :
320 : return {_VSTD::move(__ifirst), _VSTD::move(__idx)};
321 : }
322 :
323 : template <class _InputIterator, class _ForwardIterator>
324 : inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator uninitialized_move(_InputIterator __ifirst, _InputIterator __ilast,
325 : _ForwardIterator __ofirst) {
326 : using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
327 : auto __iter_move = [](auto&& __iter) -> decltype(auto) { return _VSTD::move(*__iter); };
328 :
329 : auto __result = _VSTD::__uninitialized_move<_ValueType>(_VSTD::move(__ifirst), _VSTD::move(__ilast),
330 : _VSTD::move(__ofirst), __unreachable_sentinel(), __iter_move);
331 : return _VSTD::move(__result.second);
332 : }
333 :
334 : // uninitialized_move_n
335 :
336 : template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _Sentinel, class _IterMove>
337 : inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator>
338 : __uninitialized_move_n(_InputIterator __ifirst, _Size __n,
339 : _ForwardIterator __ofirst, _Sentinel __olast, _IterMove __iter_move) {
340 : auto __idx = __ofirst;
341 : #ifndef _LIBCPP_NO_EXCEPTIONS
342 : try {
343 : #endif
344 : for (; __n > 0 && __idx != __olast; ++__idx, (void)++__ifirst, --__n)
345 : ::new (_VSTD::__voidify(*__idx)) _ValueType(__iter_move(__ifirst));
346 : #ifndef _LIBCPP_NO_EXCEPTIONS
347 : } catch (...) {
348 : _VSTD::__destroy(__ofirst, __idx);
349 : throw;
350 : }
351 : #endif
352 :
353 : return {_VSTD::move(__ifirst), _VSTD::move(__idx)};
354 : }
355 :
356 : template <class _InputIterator, class _Size, class _ForwardIterator>
357 : inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator>
358 : uninitialized_move_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) {
359 : using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
360 : auto __iter_move = [](auto&& __iter) -> decltype(auto) { return _VSTD::move(*__iter); };
361 :
362 : return _VSTD::__uninitialized_move_n<_ValueType>(_VSTD::move(__ifirst), __n, _VSTD::move(__ofirst),
363 : __unreachable_sentinel(), __iter_move);
364 : }
365 :
366 : // TODO: Rewrite this to iterate left to right and use reverse_iterators when calling
367 : // Destroys every element in the range [first, last) FROM RIGHT TO LEFT using allocator
368 : // destruction. If elements are themselves C-style arrays, they are recursively destroyed
369 : // in the same manner.
370 : //
371 : // This function assumes that destructors do not throw, and that the allocator is bound to
372 : // the correct type.
373 : template<class _Alloc, class _BidirIter, class = __enable_if_t<
374 : __is_cpp17_bidirectional_iterator<_BidirIter>::value
375 : >>
376 : _LIBCPP_HIDE_FROM_ABI
377 : constexpr void __allocator_destroy_multidimensional(_Alloc& __alloc, _BidirIter __first, _BidirIter __last) noexcept {
378 : using _ValueType = typename iterator_traits<_BidirIter>::value_type;
379 : static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _ValueType>,
380 : "The allocator should already be rebound to the correct type");
381 :
382 : if (__first == __last)
383 : return;
384 :
385 : if constexpr (is_array_v<_ValueType>) {
386 : static_assert(!__libcpp_is_unbounded_array<_ValueType>::value,
387 : "arrays of unbounded arrays don't exist, but if they did we would mess up here");
388 :
389 : using _Element = remove_extent_t<_ValueType>;
390 : __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);
391 : do {
392 : --__last;
393 : decltype(auto) __array = *__last;
394 : std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + extent_v<_ValueType>);
395 : } while (__last != __first);
396 : } else {
397 : do {
398 : --__last;
399 : allocator_traits<_Alloc>::destroy(__alloc, std::addressof(*__last));
400 : } while (__last != __first);
401 : }
402 : }
403 :
404 : // Constructs the object at the given location using the allocator's construct method.
405 : //
406 : // If the object being constructed is an array, each element of the array is allocator-constructed,
407 : // recursively. If an exception is thrown during the construction of an array, the initialized
408 : // elements are destroyed in reverse order of initialization using allocator destruction.
409 : //
410 : // This function assumes that the allocator is bound to the correct type.
411 : template<class _Alloc, class _Tp>
412 : _LIBCPP_HIDE_FROM_ABI
413 : constexpr void __allocator_construct_at_multidimensional(_Alloc& __alloc, _Tp* __loc) {
414 : static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>,
415 : "The allocator should already be rebound to the correct type");
416 :
417 : if constexpr (is_array_v<_Tp>) {
418 : using _Element = remove_extent_t<_Tp>;
419 : __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);
420 : size_t __i = 0;
421 : _Tp& __array = *__loc;
422 :
423 : // If an exception is thrown, destroy what we have constructed so far in reverse order.
424 : auto __guard = std::__make_exception_guard([&]() {
425 : std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i);
426 : });
427 :
428 : for (; __i != extent_v<_Tp>; ++__i) {
429 : std::__allocator_construct_at_multidimensional(__elem_alloc, std::addressof(__array[__i]));
430 : }
431 : __guard.__complete();
432 : } else {
433 : allocator_traits<_Alloc>::construct(__alloc, __loc);
434 : }
435 : }
436 :
437 : // Constructs the object at the given location using the allocator's construct method, passing along
438 : // the provided argument.
439 : //
440 : // If the object being constructed is an array, the argument is also assumed to be an array. Each
441 : // each element of the array being constructed is allocator-constructed from the corresponding
442 : // element of the argument array. If an exception is thrown during the construction of an array,
443 : // the initialized elements are destroyed in reverse order of initialization using allocator
444 : // destruction.
445 : //
446 : // This function assumes that the allocator is bound to the correct type.
447 : template<class _Alloc, class _Tp, class _Arg>
448 : _LIBCPP_HIDE_FROM_ABI
449 : constexpr void __allocator_construct_at_multidimensional(_Alloc& __alloc, _Tp* __loc, _Arg const& __arg) {
450 : static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>,
451 : "The allocator should already be rebound to the correct type");
452 :
453 : if constexpr (is_array_v<_Tp>) {
454 : static_assert(is_array_v<_Arg>,
455 : "Provided non-array initialization argument to __allocator_construct_at_multidimensional when "
456 : "trying to construct an array.");
457 :
458 : using _Element = remove_extent_t<_Tp>;
459 : __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);
460 : size_t __i = 0;
461 : _Tp& __array = *__loc;
462 :
463 : // If an exception is thrown, destroy what we have constructed so far in reverse order.
464 : auto __guard = std::__make_exception_guard([&]() {
465 : std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i);
466 : });
467 : for (; __i != extent_v<_Tp>; ++__i) {
468 : std::__allocator_construct_at_multidimensional(__elem_alloc, std::addressof(__array[__i]), __arg[__i]);
469 : }
470 : __guard.__complete();
471 : } else {
472 : allocator_traits<_Alloc>::construct(__alloc, __loc, __arg);
473 : }
474 : }
475 :
476 : // Given a range starting at it and containing n elements, initializes each element in the
477 : // range from left to right using the construct method of the allocator (rebound to the
478 : // correct type).
479 : //
480 : // If an exception is thrown, the initialized elements are destroyed in reverse order of
481 : // initialization using allocator_traits destruction. If the elements in the range are C-style
482 : // arrays, they are initialized element-wise using allocator construction, and recursively so.
483 : template<class _Alloc, class _BidirIter, class _Tp, class _Size = typename iterator_traits<_BidirIter>::difference_type>
484 : _LIBCPP_HIDE_FROM_ABI constexpr void
485 : __uninitialized_allocator_fill_n_multidimensional(_Alloc& __alloc, _BidirIter __it, _Size __n, _Tp const& __value) {
486 : using _ValueType = typename iterator_traits<_BidirIter>::value_type;
487 : __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc);
488 : _BidirIter __begin = __it;
489 :
490 : // If an exception is thrown, destroy what we have constructed so far in reverse order.
491 : auto __guard = std::__make_exception_guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); });
492 : for (; __n != 0; --__n, ++__it) {
493 : std::__allocator_construct_at_multidimensional(__value_alloc, std::addressof(*__it), __value);
494 : }
495 : __guard.__complete();
496 : }
497 :
498 : // Same as __uninitialized_allocator_fill_n_multidimensional, but doesn't pass any initialization argument
499 : // to the allocator's construct method, which results in value initialization.
500 : template <class _Alloc, class _BidirIter, class _Size = typename iterator_traits<_BidirIter>::difference_type>
501 : _LIBCPP_HIDE_FROM_ABI constexpr void
502 : __uninitialized_allocator_value_construct_n_multidimensional(_Alloc& __alloc, _BidirIter __it, _Size __n) {
503 : using _ValueType = typename iterator_traits<_BidirIter>::value_type;
504 : __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc);
505 : _BidirIter __begin = __it;
506 :
507 : // If an exception is thrown, destroy what we have constructed so far in reverse order.
508 : auto __guard = std::__make_exception_guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); });
509 : for (; __n != 0; --__n, ++__it) {
510 : std::__allocator_construct_at_multidimensional(__value_alloc, std::addressof(*__it));
511 : }
512 : __guard.__complete();
513 : }
514 :
515 : #endif // _LIBCPP_STD_VER > 14
516 :
517 : // Destroy all elements in [__first, __last) from left to right using allocator destruction.
518 : template <class _Alloc, class _Iter, class _Sent>
519 : _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
520 0 : __allocator_destroy(_Alloc& __alloc, _Iter __first, _Sent __last) {
521 0 : for (; __first != __last; ++__first)
522 0 : allocator_traits<_Alloc>::destroy(__alloc, std::__to_address(__first));
523 0 : }
524 :
525 : template <class _Alloc, class _Iter>
526 : class _AllocatorDestroyRangeReverse {
527 : public:
528 : _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
529 30 : _AllocatorDestroyRangeReverse(_Alloc& __alloc, _Iter& __first, _Iter& __last)
530 30 : : __alloc_(__alloc), __first_(__first), __last_(__last) {}
531 :
532 0 : _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void operator()() const {
533 0 : std::__allocator_destroy(__alloc_, std::reverse_iterator<_Iter>(__last_), std::reverse_iterator<_Iter>(__first_));
534 0 : }
535 :
536 : private:
537 : _Alloc& __alloc_;
538 : _Iter& __first_;
539 : _Iter& __last_;
540 : };
541 :
542 : // Copy-construct [__first1, __last1) in [__first2, __first2 + N), where N is distance(__first1, __last1).
543 : //
544 : // The caller has to ensure that __first2 can hold at least N uninitialized elements. If an exception is thrown the
545 : // already copied elements are destroyed in reverse order of their construction.
546 : template <class _Alloc, class _Iter1, class _Sent1, class _Iter2>
547 : _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2
548 : __uninitialized_allocator_copy(_Alloc& __alloc, _Iter1 __first1, _Sent1 __last1, _Iter2 __first2) {
549 : auto __destruct_first = __first2;
550 : auto __guard =
551 : std::__make_exception_guard(_AllocatorDestroyRangeReverse<_Alloc, _Iter2>(__alloc, __destruct_first, __first2));
552 : while (__first1 != __last1) {
553 : allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__first2), *__first1);
554 : ++__first1;
555 : ++__first2;
556 : }
557 : __guard.__complete();
558 : return __first2;
559 : }
560 :
561 : template <class _Alloc, class _Type>
562 : struct __allocator_has_trivial_copy_construct : _Not<__has_construct<_Alloc, _Type*, const _Type&> > {};
563 :
564 : template <class _Type>
565 : struct __allocator_has_trivial_copy_construct<allocator<_Type>, _Type> : true_type {};
566 :
567 : template <class _Alloc,
568 : class _Type,
569 : class _RawType = __remove_const_t<_Type>,
570 : __enable_if_t<
571 : // using _RawType because of the allocator<T const> extension
572 : is_trivially_copy_constructible<_RawType>::value && is_trivially_copy_assignable<_RawType>::value &&
573 : __allocator_has_trivial_copy_construct<_Alloc, _RawType>::value>* = nullptr>
574 : _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Type*
575 : __uninitialized_allocator_copy(_Alloc&, const _Type* __first1, const _Type* __last1, _Type* __first2) {
576 : // TODO: Remove the const_cast once we drop support for std::allocator<T const>
577 : if (__libcpp_is_constant_evaluated()) {
578 : while (__first1 != __last1) {
579 : std::__construct_at(std::__to_address(__first2), *__first1);
580 : ++__first1;
581 : ++__first2;
582 : }
583 : return __first2;
584 : } else {
585 : return std::copy(__first1, __last1, const_cast<_RawType*>(__first2));
586 : }
587 : }
588 :
589 : // Move-construct the elements [__first1, __last1) into [__first2, __first2 + N)
590 : // if the move constructor is noexcept, where N is distance(__first1, __last1).
591 : //
592 : // Otherwise try to copy all elements. If an exception is thrown the already copied
593 : // elements are destroyed in reverse order of their construction.
594 : template <class _Alloc, class _Iter1, class _Sent1, class _Iter2>
595 15 : _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2 __uninitialized_allocator_move_if_noexcept(
596 : _Alloc& __alloc, _Iter1 __first1, _Sent1 __last1, _Iter2 __first2) {
597 : static_assert(__is_cpp17_move_insertable<_Alloc>::value,
598 : "The specified type does not meet the requirements of Cpp17MoveInsertable");
599 15 : auto __destruct_first = __first2;
600 : auto __guard =
601 15 : std::__make_exception_guard(_AllocatorDestroyRangeReverse<_Alloc, _Iter2>(__alloc, __destruct_first, __first2));
602 60 : while (__first1 != __last1) {
603 : #ifndef _LIBCPP_NO_EXCEPTIONS
604 45 : allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__first2), std::move_if_noexcept(*__first1));
605 : #else
606 : allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__first2), std::move(*__first1));
607 : #endif
608 45 : ++__first1;
609 45 : ++__first2;
610 : }
611 15 : __guard.__complete();
612 15 : return __first2;
613 15 : }
614 :
615 : template <class _Alloc, class _Type>
616 : struct __allocator_has_trivial_move_construct : _Not<__has_construct<_Alloc, _Type*, _Type&&> > {};
617 :
618 : template <class _Type>
619 : struct __allocator_has_trivial_move_construct<allocator<_Type>, _Type> : true_type {};
620 :
621 : #ifndef _LIBCPP_COMPILER_GCC
622 : template <
623 : class _Alloc,
624 : class _Iter1,
625 : class _Iter2,
626 : class _Type = typename iterator_traits<_Iter1>::value_type,
627 : class = __enable_if_t<is_trivially_move_constructible<_Type>::value && is_trivially_move_assignable<_Type>::value &&
628 : __allocator_has_trivial_move_construct<_Alloc, _Type>::value> >
629 : _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2
630 27 : __uninitialized_allocator_move_if_noexcept(_Alloc&, _Iter1 __first1, _Iter1 __last1, _Iter2 __first2) {
631 27 : if (__libcpp_is_constant_evaluated()) {
632 0 : while (__first1 != __last1) {
633 0 : std::__construct_at(std::__to_address(__first2), std::move(*__first1));
634 0 : ++__first1;
635 0 : ++__first2;
636 : }
637 0 : return __first2;
638 : } else {
639 27 : return std::move(__first1, __last1, __first2);
640 : }
641 27 : }
642 : #endif // _LIBCPP_COMPILER_GCC
643 :
644 : _LIBCPP_END_NAMESPACE_STD
645 :
646 : #endif // _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H
|
