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/in_out_result.h>
14#include <__algorithm/unwrap_iter.h>
15#include <__config>
16#include <__fwd/memory.h>
17#include <__iterator/iterator_traits.h>
18#include <__memory/addressof.h>
19#include <__memory/allocator_traits.h>
20#include <__memory/construct_at.h>
21#include <__memory/destroy.h>
22#include <__memory/pointer_traits.h>
23#include <__string/constexpr_c_functions.h>
24#include <__type_traits/enable_if.h>
25#include <__type_traits/is_always_bitcastable.h>
26#include <__type_traits/is_constant_evaluated.h>
27#include <__type_traits/is_nothrow_constructible.h>
28#include <__type_traits/is_reference.h>
29#include <__type_traits/is_relocatable.h>
30#include <__type_traits/is_same.h>
31#include <__type_traits/is_trivially_assignable.h>
32#include <__type_traits/is_trivially_constructible.h>
33#include <__type_traits/remove_const.h>
34#include <__utility/exception_guard.h>
35#include <__utility/move.h>
36#include <__utility/pair.h>
37
38#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
39# pragma GCC system_header
40#endif
41
42_LIBCPP_PUSH_MACROS
43#include <__undef_macros>
44
45_LIBCPP_BEGIN_NAMESPACE_STD
46
47struct __always_false {
48 template <class... _Args>
49 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool operator()(_Args&&...) const _NOEXCEPT {
50 return false;
51 }
52};
53
54// uninitialized_copy
55
56template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _EndPredicate>
57inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __in_out_result<_InputIterator, _ForwardIterator>
58__uninitialized_copy(
59 _InputIterator __ifirst, _Sentinel1 __ilast, _ForwardIterator __ofirst, _EndPredicate __stop_copying) {
60 _ForwardIterator __idx = __ofirst;
61 auto __guard = std::__make_exception_guard([&] { std::__destroy(__ofirst, __idx); });
62 for (; __ifirst != __ilast && !__stop_copying(__idx); ++__ifirst, (void)++__idx)
63 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(*__ifirst);
64 __guard.__complete();
65
66 return {std::move(__ifirst), std::move(__idx)};
67}
68
69template <class _InputIterator, class _ForwardIterator>
70_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
71uninitialized_copy(_InputIterator __ifirst, _InputIterator __ilast, _ForwardIterator __ofirst) {
72 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
73 auto __result = std::__uninitialized_copy<_ValueType>(
74 std::move(__ifirst), std::move(__ilast), std::move(__ofirst), __always_false());
75 return std::move(__result.__out_);
76}
77
78// uninitialized_copy_n
79
80template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _EndPredicate>
81inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __in_out_result<_InputIterator, _ForwardIterator>
82__uninitialized_copy_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst, _EndPredicate __stop_copying) {
83 _ForwardIterator __idx = __ofirst;
84 auto __guard = std::__make_exception_guard([&] { std::__destroy(__ofirst, __idx); });
85 for (; __n > 0 && !__stop_copying(__idx); ++__ifirst, (void)++__idx, (void)--__n)
86 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(*__ifirst);
87 __guard.__complete();
88
89 return {std::move(__ifirst), std::move(__idx)};
90}
91
92template <class _InputIterator, class _Size, class _ForwardIterator>
93inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
94uninitialized_copy_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) {
95 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
96 auto __result =
97 std::__uninitialized_copy_n<_ValueType>(std::move(__ifirst), __n, std::move(__ofirst), __always_false());
98 return std::move(__result.__out_);
99}
100
101// uninitialized_fill
102
103template <class _ValueType, class _ForwardIterator, class _Sentinel, class _Tp>
104inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
105__uninitialized_fill(_ForwardIterator __first, _Sentinel __last, const _Tp& __x) {
106 _ForwardIterator __idx = __first;
107 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });
108 for (; __idx != __last; ++__idx)
109 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(__x);
110 __guard.__complete();
111
112 return __idx;
113}
114
115template <class _ForwardIterator, class _Tp>
116inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
117uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __x) {
118 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
119 (void)std::__uninitialized_fill<_ValueType>(__first, __last, __x);
120}
121
122// uninitialized_fill_n
123
124template <class _Alloc, class _ForwardIterator, class _Size, class _Tp>
125_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
126__uninitialized_allocator_fill_n(_Alloc& __alloc, _ForwardIterator __first, _Size __n, const _Tp& __x) {
127 _ForwardIterator __idx = __first;
128 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });
129 for (; __n > 0; ++__idx, (void)--__n)
130 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__idx), __x);
131 __guard.__complete();
132
133 return __idx;
134}
135
136template <class _ValueType, class _ForwardIterator, class _Size, class _Tp>
137inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
138__uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) {
139 _ForwardIterator __idx = __first;
140 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });
141 for (; __n > 0; ++__idx, (void)--__n)
142 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(__x);
143 __guard.__complete();
144
145 return __idx;
146}
147
148template <class _ForwardIterator, class _Size, class _Tp>
149inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
150uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) {
151 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
152 return std::__uninitialized_fill_n<_ValueType>(__first, __n, __x);
153}
154
155// __uninitialized_allocator_value_construct_n
156
157template <class _Alloc, class _ForwardIterator, class _Size>
158_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
159__uninitialized_allocator_value_construct_n(_Alloc& __alloc, _ForwardIterator __first, _Size __n) {
160 auto __idx = __first;
161 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });
162 for (; __n > 0; ++__idx, (void)--__n)
163 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__idx));
164 __guard.__complete();
165
166 return __idx;
167}
168
169#if _LIBCPP_STD_VER >= 17
170
171template <class _Iter>
172_LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) __deref_move(_Iter& __it) {
173 if constexpr (is_lvalue_reference_v<decltype(*__it)>)
174 return std::move(*__it);
175 else
176 return *__it;
177}
178
179// uninitialized_default_construct
180
181template <class _ValueType, class _ForwardIterator, class _Sentinel>
182inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
183__uninitialized_default_construct(_ForwardIterator __first, _Sentinel __last) {
184 auto __idx = __first;
185 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });
186 for (; __idx != __last; ++__idx)
187 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType;
188 __guard.__complete();
189
190 return __idx;
191}
192
193template <class _ForwardIterator>
194inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
195uninitialized_default_construct(_ForwardIterator __first, _ForwardIterator __last) {
196 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
197 (void)std::__uninitialized_default_construct<_ValueType>(std::move(__first), std::move(__last));
198}
199
200// uninitialized_default_construct_n
201
202template <class _ValueType, class _ForwardIterator, class _Size>
203inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
204__uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {
205 auto __idx = __first;
206 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });
207 for (; __n > 0; ++__idx, (void)--__n)
208 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType;
209 __guard.__complete();
210
211 return __idx;
212}
213
214template <class _ForwardIterator, class _Size>
215inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
216uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {
217 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
218 return std::__uninitialized_default_construct_n<_ValueType>(std::move(__first), __n);
219}
220
221// uninitialized_value_construct
222
223template <class _ValueType, class _ForwardIterator, class _Sentinel>
224inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
225__uninitialized_value_construct(_ForwardIterator __first, _Sentinel __last) {
226 auto __idx = __first;
227 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });
228 for (; __idx != __last; ++__idx)
229 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType();
230 __guard.__complete();
231
232 return __idx;
233}
234
235template <class _ForwardIterator>
236inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 void
237uninitialized_value_construct(_ForwardIterator __first, _ForwardIterator __last) {
238 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
239 (void)std::__uninitialized_value_construct<_ValueType>(std::move(__first), std::move(__last));
240}
241
242// uninitialized_value_construct_n
243
244template <class _ValueType, class _ForwardIterator, class _Size>
245inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
246__uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) {
247 auto __idx = __first;
248 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });
249 for (; __n > 0; ++__idx, (void)--__n)
250 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType();
251 __guard.__complete();
252
253 return __idx;
254}
255
256template <class _ForwardIterator, class _Size>
257inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
258uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) {
259 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
260 return std::__uninitialized_value_construct_n<_ValueType>(std::move(__first), __n);
261}
262
263// uninitialized_move
264
265template <class _ValueType,
266 class _InputIterator,
267 class _Sentinel1,
268 class _ForwardIterator,
269 class _EndPredicate,
270 class _IterMove>
271inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __in_out_result<_InputIterator, _ForwardIterator>
272__uninitialized_move(_InputIterator __ifirst,
273 _Sentinel1 __ilast,
274 _ForwardIterator __ofirst,
275 _EndPredicate __stop_moving,
276 _IterMove __iter_move) {
277 auto __idx = __ofirst;
278 auto __guard = std::__make_exception_guard([&] { std::__destroy(__ofirst, __idx); });
279 for (; __ifirst != __ilast && !__stop_moving(__idx); ++__idx, (void)++__ifirst) {
280 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(__iter_move(__ifirst));
281 }
282 __guard.__complete();
283
284 return {std::move(__ifirst), std::move(__idx)};
285}
286
287template <class _InputIterator, class _ForwardIterator>
288inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 _ForwardIterator
289uninitialized_move(_InputIterator __ifirst, _InputIterator __ilast, _ForwardIterator __ofirst) {
290 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
291 auto __iter_move = [](auto&& __iter) -> decltype(auto) { return std::__deref_move(__iter); };
292
293 auto __result = std::__uninitialized_move<_ValueType>(
294 std::move(__ifirst), std::move(__ilast), std::move(__ofirst), __always_false(), __iter_move);
295 return std::move(__result.__out_);
296}
297
298// uninitialized_move_n
299
300template <class _ValueType,
301 class _InputIterator,
302 class _Size,
303 class _ForwardIterator,
304 class _EndPredicate,
305 class _IterMove>
306inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __in_out_result<_InputIterator, _ForwardIterator>
307__uninitialized_move_n(
308 _InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst, _EndPredicate __stop_moving, _IterMove __iter_move) {
309 auto __idx = __ofirst;
310 auto __guard = std::__make_exception_guard([&] { std::__destroy(__ofirst, __idx); });
311 for (; __n > 0 && !__stop_moving(__idx); ++__idx, (void)++__ifirst, --__n)
312 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(__iter_move(__ifirst));
313 __guard.__complete();
314
315 return {std::move(__ifirst), std::move(__idx)};
316}
317
318template <class _InputIterator, class _Size, class _ForwardIterator>
319inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 pair<_InputIterator, _ForwardIterator>
320uninitialized_move_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) {
321 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
322 auto __iter_move = [](auto&& __iter) -> decltype(auto) { return std::__deref_move(__iter); };
323
324 auto __result = std::__uninitialized_move_n<_ValueType>(
325 std::move(__ifirst), __n, std::move(__ofirst), __always_false(), __iter_move);
326 return {std::move(__result.__in_), std::move(__result.__out_)};
327}
328
329#endif // _LIBCPP_STD_VER >= 17
330
331// __uninitialized_relocate relocates the objects in [__first, __last) into __result element-by-element from __first to
332// __last. Relocation means that the objects in [__first, __last) are placed into __result as-if by move-construct and
333// destroy, except that the move constructor and destructor may never be called if they are known to be equivalent to a
334// memcpy.
335//
336// Preconditions: At __result there is no object and [__first, __last) contains objects
337// Postconditions: If no exceptions were thrown, __result contains the objects from [__first, __last), otherwise it
338// doesn't contain any objects.
339// [__first, __last) doesn't contain any objects.
340template <class _ContiguousIterator>
341_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
342__uninitialized_relocate(_ContiguousIterator __first, _ContiguousIterator __last, _ContiguousIterator __result) {
343 static_assert(__libcpp_is_contiguous_iterator<_ContiguousIterator>::value, "");
344 using _ValueType = typename iterator_traits<_ContiguousIterator>::value_type;
345
346 // TODO: Accept non-trivially relocatable types
347 static_assert(__is_trivially_relocatable_v<_ValueType>);
348
349 if (__libcpp_is_constant_evaluated()) {
350 auto __iter = __first;
351 while (__iter != __last) {
352 std::__construct_at(std::__to_address(__result), std::move(*__iter));
353 std::__destroy_at(std::__to_address(__iter));
354 ++__iter;
355 ++__result;
356 }
357 } else {
358 // Casting to void* to suppress clang complaining that this is technically UB.
359 __builtin_memmove(static_cast<void*>(std::__to_address(__result)),
360 std::__to_address(__first),
361 sizeof(_ValueType) * (__last - __first));
362 }
363}
364
365template <class _Alloc, class _Iter>
366class _AllocatorDestroyRangeReverse {
367public:
368 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
369 _AllocatorDestroyRangeReverse(_Alloc& __alloc, _Iter& __first, _Iter& __last)
370 : __alloc_(__alloc), __first_(__first), __last_(__last) {}
371
372 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void operator()() const {
373 std::__allocator_destroy_backward(__alloc_, __first_, __last_);
374 }
375
376private:
377 _Alloc& __alloc_;
378 _Iter& __first_;
379 _Iter& __last_;
380};
381
382// Copy-construct [__first1, __last1) in [__first2, __first2 + N), where N is distance(__first1, __last1).
383//
384// The caller has to ensure that __first2 can hold at least N uninitialized elements. If an exception is thrown the
385// already copied elements are destroyed in reverse order of their construction.
386template <class _Alloc, class _Iter1, class _Size, class _Iter2>
387_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2
388__uninitialized_allocator_copy_n_impl(_Alloc& __alloc, _Iter1 __first1, _Size __count, _Iter2 __first2) {
389 auto __destruct_first = __first2;
390 auto __guard =
391 std::__make_exception_guard(_AllocatorDestroyRangeReverse<_Alloc, _Iter2>(__alloc, __destruct_first, __first2));
392 for (_Size __i = 0; __i != __count; ++__i) {
393 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__first2), *__first1);
394 ++__first1;
395 ++__first2;
396 }
397 __guard.__complete();
398 return __first2;
399}
400
401template <class _Alloc, class _Type>
402inline const bool __allocator_has_trivial_copy_construct_v = !__has_construct_v<_Alloc, _Type*, const _Type&>;
403
404template <class _Type>
405inline const bool __allocator_has_trivial_copy_construct_v<allocator<_Type>, _Type> = true;
406
407template <class _Alloc,
408 class _In,
409 class _Size,
410 class _Out,
411 __enable_if_t<__is_always_bitcastable<_In, _Out>::value && is_trivially_constructible<_Out, _In>::value &&
412 is_trivially_assignable<_Out&, _In&>::value &&
413 is_same<__remove_const_t<_In>, __remove_const_t<_Out> >::value &&
414 __allocator_has_trivial_copy_construct_v<_Alloc, _In>,
415 int> = 0>
416_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Out*
417__uninitialized_allocator_copy_n_impl(_Alloc&, _In* __first1, _Size __count, _Out* __first2) {
418 if (__libcpp_is_constant_evaluated()) {
419 for (_Size __i = 0; __i != __count; ++__i) {
420 std::__construct_at(std::__to_address(__first2), *__first1);
421 ++__first1;
422 ++__first2;
423 }
424 return __first2;
425 } else {
426 std::__constexpr_memmove(__first2, __first1, __element_count(__count));
427 return __first2 + __count;
428 }
429}
430
431template <class _Alloc, class _Iter1, class _Size, class _Iter2>
432_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2
433__uninitialized_allocator_copy_n(_Alloc& __alloc, _Iter1 __first1, _Size __count, _Iter2 __first2) {
434 auto __result = std::__uninitialized_allocator_copy_n_impl(
435 __alloc, std::__unwrap_iter(std::move(__first1)), __count, std::__unwrap_iter(__first2));
436 return std::__rewrap_iter(__first2, __result);
437}
438
439template <class _Alloc, class _Type>
440inline const bool __allocator_has_trivial_move_construct_v = !__has_construct_v<_Alloc, _Type*, _Type&&>;
441
442template <class _Type>
443inline const bool __allocator_has_trivial_move_construct_v<allocator<_Type>, _Type> = true;
444
445template <class _Alloc, class _InIter, class _Sent, class _OutIter>
446_LIBCPP_CONSTEXPR_SINCE_CXX20 __in_out_result<_InIter, _OutIter>
447__uninitialized_allocator_move(_Alloc& __alloc, _InIter __first, _Sent __last, _OutIter __result) {
448 auto __destruct_first = __result;
449 auto __guard = std::__make_exception_guard([&] { std::__allocator_destroy(__alloc, __destruct_first, __result); });
450 while (__first != __last) {
451 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__result), std::move(*__first));
452 ++__first;
453 ++__result;
454 }
455 __guard.__complete();
456 return {std::move(__first), std::move(__result)};
457}
458
459template <class _Alloc, class _Tp>
460inline const bool __allocator_has_trivial_destroy_v = !__has_destroy_v<_Alloc, _Tp*>;
461
462template <class _Tp, class _Up>
463inline const bool __allocator_has_trivial_destroy_v<allocator<_Tp>, _Up> = true;
464
465// __uninitialized_allocator_relocate relocates the objects in [__first, __last) into __result.
466// Relocation means that the objects in [__first, __last) are placed into __result as-if by move-construct and destroy,
467// except that the move constructor and destructor may never be called if they are known to be equivalent to a memcpy.
468//
469// Preconditions: __result doesn't contain any objects and [__first, __last) contains objects
470// Postconditions: __result contains the objects from [__first, __last) and
471// [__first, __last) doesn't contain any objects
472//
473// The strong exception guarantee is provided if any of the following are true:
474// - is_nothrow_move_constructible<_ValueType>
475// - is_copy_constructible<_ValueType>
476// - __is_trivially_relocatable_v<_ValueType>
477template <class _Alloc, class _ContiguousIterator>
478_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __uninitialized_allocator_relocate(
479 _Alloc& __alloc, _ContiguousIterator __first, _ContiguousIterator __last, _ContiguousIterator __result) {
480 static_assert(__libcpp_is_contiguous_iterator<_ContiguousIterator>::value, "");
481 static_assert(
482 __is_cpp17_move_insertable_v<_Alloc>, "The specified type does not meet the requirements of Cpp17MoveInsertable");
483
484 using __value_type = typename iterator_traits<_ContiguousIterator>::value_type;
485
486 if _LIBCPP_CONSTEXPR (__allocator_has_trivial_move_construct_v<_Alloc, __value_type> &&
487 __allocator_has_trivial_destroy_v<_Alloc, __value_type> &&
488 __is_trivially_relocatable_v<__value_type>) {
489 if (!__libcpp_is_constant_evaluated()) {
490 // Casting to void* to suppress clang complaining that this is technically UB.
491 __builtin_memcpy(static_cast<void*>(std::__to_address(__result)),
492 std::__to_address(__first),
493 sizeof(__value_type) * (__last - __first));
494 return;
495 }
496 }
497
498 using __alloc_traits = allocator_traits<_Alloc>;
499#ifndef _LIBCPP_CXX03_LANG
500 if constexpr (!_LIBCPP_HAS_EXCEPTIONS || is_nothrow_move_constructible<__value_type>::value) {
501 while (__first != __last) {
502 __alloc_traits::construct(__alloc, std::__to_address(__result), std::move(*__first));
503 __alloc_traits::destroy(__alloc, std::__to_address(__first));
504 ++__first;
505 ++__result;
506 }
507 } else
508#endif
509 {
510 auto __destruct_first = __result;
511 auto __guard = std::__make_exception_guard(
512 _AllocatorDestroyRangeReverse<_Alloc, _ContiguousIterator>(__alloc, __destruct_first, __result));
513 auto __iter = __first;
514 while (__iter != __last) {
515 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__result), std::move_if_noexcept(*__iter));
516 ++__iter;
517 ++__result;
518 }
519 __guard.__complete();
520 std::__allocator_destroy(__alloc, __first, __last);
521 }
522}
523
524_LIBCPP_END_NAMESPACE_STD
525
526_LIBCPP_POP_MACROS
527
528#endif // _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H
529