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