578 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H11#define _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H12 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_header43#endif44 45_LIBCPP_PUSH_MACROS46#include <__undef_macros>47 48_LIBCPP_BEGIN_NAMESPACE_STD49 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_copy58 59template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _EndPredicate>60inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> __uninitialized_copy(61 _InputIterator __ifirst, _Sentinel1 __ilast, _ForwardIterator __ofirst, _EndPredicate __stop_copying) {62 _ForwardIterator __idx = __ofirst;63 auto __guard = std::__make_exception_guard([&] { std::__destroy(__ofirst, __idx); });64 for (; __ifirst != __ilast && !__stop_copying(__idx); ++__ifirst, (void)++__idx)65 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(*__ifirst);66 __guard.__complete();67 68 return pair<_InputIterator, _ForwardIterator>(std::move(__ifirst), std::move(__idx));69}70 71template <class _InputIterator, class _ForwardIterator>72_LIBCPP_HIDE_FROM_ABI _ForwardIterator73uninitialized_copy(_InputIterator __ifirst, _InputIterator __ilast, _ForwardIterator __ofirst) {74 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;75 auto __result = std::__uninitialized_copy<_ValueType>(76 std::move(__ifirst), std::move(__ilast), std::move(__ofirst), __always_false());77 return std::move(__result.second);78}79 80// uninitialized_copy_n81 82template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _EndPredicate>83inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator>84__uninitialized_copy_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst, _EndPredicate __stop_copying) {85 _ForwardIterator __idx = __ofirst;86 auto __guard = std::__make_exception_guard([&] { std::__destroy(__ofirst, __idx); });87 for (; __n > 0 && !__stop_copying(__idx); ++__ifirst, (void)++__idx, (void)--__n)88 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(*__ifirst);89 __guard.__complete();90 91 return pair<_InputIterator, _ForwardIterator>(std::move(__ifirst), std::move(__idx));92}93 94template <class _InputIterator, class _Size, class _ForwardIterator>95inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator96uninitialized_copy_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) {97 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;98 auto __result =99 std::__uninitialized_copy_n<_ValueType>(std::move(__ifirst), __n, std::move(__ofirst), __always_false());100 return std::move(__result.second);101}102 103// uninitialized_fill104 105template <class _ValueType, class _ForwardIterator, class _Sentinel, class _Tp>106inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator107__uninitialized_fill(_ForwardIterator __first, _Sentinel __last, const _Tp& __x) {108 _ForwardIterator __idx = __first;109 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });110 for (; __idx != __last; ++__idx)111 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(__x);112 __guard.__complete();113 114 return __idx;115}116 117template <class _ForwardIterator, class _Tp>118inline _LIBCPP_HIDE_FROM_ABI void119uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __x) {120 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;121 (void)std::__uninitialized_fill<_ValueType>(__first, __last, __x);122}123 124// uninitialized_fill_n125 126template <class _ValueType, class _ForwardIterator, class _Size, class _Tp>127inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator128__uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) {129 _ForwardIterator __idx = __first;130 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });131 for (; __n > 0; ++__idx, (void)--__n)132 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(__x);133 __guard.__complete();134 135 return __idx;136}137 138template <class _ForwardIterator, class _Size, class _Tp>139inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator140uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) {141 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;142 return std::__uninitialized_fill_n<_ValueType>(__first, __n, __x);143}144 145#if _LIBCPP_STD_VER >= 17146 147// uninitialized_default_construct148 149template <class _ValueType, class _ForwardIterator, class _Sentinel>150inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator151__uninitialized_default_construct(_ForwardIterator __first, _Sentinel __last) {152 auto __idx = __first;153 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });154 for (; __idx != __last; ++__idx)155 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType;156 __guard.__complete();157 158 return __idx;159}160 161template <class _ForwardIterator>162inline _LIBCPP_HIDE_FROM_ABI void uninitialized_default_construct(_ForwardIterator __first, _ForwardIterator __last) {163 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;164 (void)std::__uninitialized_default_construct<_ValueType>(std::move(__first), std::move(__last));165}166 167// uninitialized_default_construct_n168 169template <class _ValueType, class _ForwardIterator, class _Size>170inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator __uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {171 auto __idx = __first;172 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });173 for (; __n > 0; ++__idx, (void)--__n)174 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType;175 __guard.__complete();176 177 return __idx;178}179 180template <class _ForwardIterator, class _Size>181inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {182 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;183 return std::__uninitialized_default_construct_n<_ValueType>(std::move(__first), __n);184}185 186// uninitialized_value_construct187 188template <class _ValueType, class _ForwardIterator, class _Sentinel>189inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator190__uninitialized_value_construct(_ForwardIterator __first, _Sentinel __last) {191 auto __idx = __first;192 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });193 for (; __idx != __last; ++__idx)194 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType();195 __guard.__complete();196 197 return __idx;198}199 200template <class _ForwardIterator>201inline _LIBCPP_HIDE_FROM_ABI void uninitialized_value_construct(_ForwardIterator __first, _ForwardIterator __last) {202 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;203 (void)std::__uninitialized_value_construct<_ValueType>(std::move(__first), std::move(__last));204}205 206// uninitialized_value_construct_n207 208template <class _ValueType, class _ForwardIterator, class _Size>209inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator __uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) {210 auto __idx = __first;211 auto __guard = std::__make_exception_guard([&] { std::__destroy(__first, __idx); });212 for (; __n > 0; ++__idx, (void)--__n)213 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType();214 __guard.__complete();215 216 return __idx;217}218 219template <class _ForwardIterator, class _Size>220inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) {221 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;222 return std::__uninitialized_value_construct_n<_ValueType>(std::move(__first), __n);223}224 225// uninitialized_move226 227template <class _ValueType,228 class _InputIterator,229 class _Sentinel1,230 class _ForwardIterator,231 class _EndPredicate,232 class _IterMove>233inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> __uninitialized_move(234 _InputIterator __ifirst,235 _Sentinel1 __ilast,236 _ForwardIterator __ofirst,237 _EndPredicate __stop_moving,238 _IterMove __iter_move) {239 auto __idx = __ofirst;240 auto __guard = std::__make_exception_guard([&] { std::__destroy(__ofirst, __idx); });241 for (; __ifirst != __ilast && !__stop_moving(__idx); ++__idx, (void)++__ifirst) {242 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(__iter_move(__ifirst));243 }244 __guard.__complete();245 246 return {std::move(__ifirst), std::move(__idx)};247}248 249template <class _InputIterator, class _ForwardIterator>250inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator251uninitialized_move(_InputIterator __ifirst, _InputIterator __ilast, _ForwardIterator __ofirst) {252 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;253 auto __iter_move = [](auto&& __iter) -> decltype(auto) { return std::move(*__iter); };254 255 auto __result = std::__uninitialized_move<_ValueType>(256 std::move(__ifirst), std::move(__ilast), std::move(__ofirst), __always_false(), __iter_move);257 return std::move(__result.second);258}259 260// uninitialized_move_n261 262template <class _ValueType,263 class _InputIterator,264 class _Size,265 class _ForwardIterator,266 class _EndPredicate,267 class _IterMove>268inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> __uninitialized_move_n(269 _InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst, _EndPredicate __stop_moving, _IterMove __iter_move) {270 auto __idx = __ofirst;271 auto __guard = std::__make_exception_guard([&] { std::__destroy(__ofirst, __idx); });272 for (; __n > 0 && !__stop_moving(__idx); ++__idx, (void)++__ifirst, --__n)273 ::new (static_cast<void*>(std::addressof(*__idx))) _ValueType(__iter_move(__ifirst));274 __guard.__complete();275 276 return {std::move(__ifirst), std::move(__idx)};277}278 279template <class _InputIterator, class _Size, class _ForwardIterator>280inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator>281uninitialized_move_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) {282 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;283 auto __iter_move = [](auto&& __iter) -> decltype(auto) { return std::move(*__iter); };284 285 return std::__uninitialized_move_n<_ValueType>(286 std::move(__ifirst), __n, std::move(__ofirst), __always_false(), __iter_move);287}288 289// TODO: Rewrite this to iterate left to right and use reverse_iterators when calling290// Destroys every element in the range [first, last) FROM RIGHT TO LEFT using allocator291// destruction. If elements are themselves C-style arrays, they are recursively destroyed292// in the same manner.293//294// This function assumes that destructors do not throw, and that the allocator is bound to295// the correct type.296template <class _Alloc,297 class _BidirIter,298 __enable_if_t<__has_bidirectional_iterator_category<_BidirIter>::value, int> = 0>299_LIBCPP_HIDE_FROM_ABI constexpr void300__allocator_destroy_multidimensional(_Alloc& __alloc, _BidirIter __first, _BidirIter __last) noexcept {301 using _ValueType = typename iterator_traits<_BidirIter>::value_type;302 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _ValueType>,303 "The allocator should already be rebound to the correct type");304 305 if (__first == __last)306 return;307 308 if constexpr (is_array_v<_ValueType>) {309 static_assert(!__is_unbounded_array_v<_ValueType>,310 "arrays of unbounded arrays don't exist, but if they did we would mess up here");311 312 using _Element = remove_extent_t<_ValueType>;313 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);314 do {315 --__last;316 decltype(auto) __array = *__last;317 std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + extent_v<_ValueType>);318 } while (__last != __first);319 } else {320 do {321 --__last;322 allocator_traits<_Alloc>::destroy(__alloc, std::addressof(*__last));323 } while (__last != __first);324 }325}326 327// Constructs the object at the given location using the allocator's construct method.328//329// If the object being constructed is an array, each element of the array is allocator-constructed,330// recursively. If an exception is thrown during the construction of an array, the initialized331// elements are destroyed in reverse order of initialization using allocator destruction.332//333// This function assumes that the allocator is bound to the correct type.334template <class _Alloc, class _Tp>335_LIBCPP_HIDE_FROM_ABI constexpr void __allocator_construct_at_multidimensional(_Alloc& __alloc, _Tp* __loc) {336 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>,337 "The allocator should already be rebound to the correct type");338 339 if constexpr (is_array_v<_Tp>) {340 using _Element = remove_extent_t<_Tp>;341 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);342 size_t __i = 0;343 _Tp& __array = *__loc;344 345 // If an exception is thrown, destroy what we have constructed so far in reverse order.346 auto __guard = std::__make_exception_guard([&]() {347 std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i);348 });349 350 for (; __i != extent_v<_Tp>; ++__i) {351 std::__allocator_construct_at_multidimensional(__elem_alloc, std::addressof(__array[__i]));352 }353 __guard.__complete();354 } else {355 allocator_traits<_Alloc>::construct(__alloc, __loc);356 }357}358 359// Constructs the object at the given location using the allocator's construct method, passing along360// the provided argument.361//362// If the object being constructed is an array, the argument is also assumed to be an array. Each363// each element of the array being constructed is allocator-constructed from the corresponding364// element of the argument array. If an exception is thrown during the construction of an array,365// the initialized elements are destroyed in reverse order of initialization using allocator366// destruction.367//368// This function assumes that the allocator is bound to the correct type.369template <class _Alloc, class _Tp, class _Arg>370_LIBCPP_HIDE_FROM_ABI constexpr void371__allocator_construct_at_multidimensional(_Alloc& __alloc, _Tp* __loc, _Arg const& __arg) {372 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>,373 "The allocator should already be rebound to the correct type");374 375 if constexpr (is_array_v<_Tp>) {376 static_assert(is_array_v<_Arg>,377 "Provided non-array initialization argument to __allocator_construct_at_multidimensional when "378 "trying to construct an array.");379 380 using _Element = remove_extent_t<_Tp>;381 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);382 size_t __i = 0;383 _Tp& __array = *__loc;384 385 // If an exception is thrown, destroy what we have constructed so far in reverse order.386 auto __guard = std::__make_exception_guard([&]() {387 std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i);388 });389 for (; __i != extent_v<_Tp>; ++__i) {390 std::__allocator_construct_at_multidimensional(__elem_alloc, std::addressof(__array[__i]), __arg[__i]);391 }392 __guard.__complete();393 } else {394 allocator_traits<_Alloc>::construct(__alloc, __loc, __arg);395 }396}397 398// Given a range starting at it and containing n elements, initializes each element in the399// range from left to right using the construct method of the allocator (rebound to the400// correct type).401//402// If an exception is thrown, the initialized elements are destroyed in reverse order of403// initialization using allocator_traits destruction. If the elements in the range are C-style404// arrays, they are initialized element-wise using allocator construction, and recursively so.405template <class _Alloc,406 class _BidirIter,407 class _Tp,408 class _Size = typename iterator_traits<_BidirIter>::difference_type>409_LIBCPP_HIDE_FROM_ABI constexpr void410__uninitialized_allocator_fill_n_multidimensional(_Alloc& __alloc, _BidirIter __it, _Size __n, _Tp const& __value) {411 using _ValueType = typename iterator_traits<_BidirIter>::value_type;412 __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc);413 _BidirIter __begin = __it;414 415 // If an exception is thrown, destroy what we have constructed so far in reverse order.416 auto __guard =417 std::__make_exception_guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); });418 for (; __n != 0; --__n, ++__it) {419 std::__allocator_construct_at_multidimensional(__value_alloc, std::addressof(*__it), __value);420 }421 __guard.__complete();422}423 424// Same as __uninitialized_allocator_fill_n_multidimensional, but doesn't pass any initialization argument425// to the allocator's construct method, which results in value initialization.426template <class _Alloc, class _BidirIter, class _Size = typename iterator_traits<_BidirIter>::difference_type>427_LIBCPP_HIDE_FROM_ABI constexpr void428__uninitialized_allocator_value_construct_n_multidimensional(_Alloc& __alloc, _BidirIter __it, _Size __n) {429 using _ValueType = typename iterator_traits<_BidirIter>::value_type;430 __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc);431 _BidirIter __begin = __it;432 433 // If an exception is thrown, destroy what we have constructed so far in reverse order.434 auto __guard =435 std::__make_exception_guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); });436 for (; __n != 0; --__n, ++__it) {437 std::__allocator_construct_at_multidimensional(__value_alloc, std::addressof(*__it));438 }439 __guard.__complete();440}441 442#endif // _LIBCPP_STD_VER >= 17443 444template <class _Alloc, class _Iter>445class _AllocatorDestroyRangeReverse {446public:447 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14448 _AllocatorDestroyRangeReverse(_Alloc& __alloc, _Iter& __first, _Iter& __last)449 : __alloc_(__alloc), __first_(__first), __last_(__last) {}450 451 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void operator()() const {452 std::__allocator_destroy(__alloc_, std::reverse_iterator<_Iter>(__last_), std::reverse_iterator<_Iter>(__first_));453 }454 455private:456 _Alloc& __alloc_;457 _Iter& __first_;458 _Iter& __last_;459};460 461// Copy-construct [__first1, __last1) in [__first2, __first2 + N), where N is distance(__first1, __last1).462//463// The caller has to ensure that __first2 can hold at least N uninitialized elements. If an exception is thrown the464// already copied elements are destroyed in reverse order of their construction.465template <class _Alloc, class _Iter1, class _Sent1, class _Iter2>466_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2467__uninitialized_allocator_copy_impl(_Alloc& __alloc, _Iter1 __first1, _Sent1 __last1, _Iter2 __first2) {468 auto __destruct_first = __first2;469 auto __guard =470 std::__make_exception_guard(_AllocatorDestroyRangeReverse<_Alloc, _Iter2>(__alloc, __destruct_first, __first2));471 while (__first1 != __last1) {472 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__first2), *__first1);473 ++__first1;474 ++__first2;475 }476 __guard.__complete();477 return __first2;478}479 480template <class _Alloc, class _Type>481inline const bool __allocator_has_trivial_copy_construct_v = !__has_construct_v<_Alloc, _Type*, const _Type&>;482 483template <class _Type>484inline const bool __allocator_has_trivial_copy_construct_v<allocator<_Type>, _Type> = true;485 486template <class _Alloc,487 class _In,488 class _Out,489 __enable_if_t<is_trivially_copy_constructible<_In>::value && is_trivially_copy_assignable<_In>::value &&490 is_same<__remove_const_t<_In>, __remove_const_t<_Out> >::value &&491 __allocator_has_trivial_copy_construct_v<_Alloc, _In>,492 int> = 0>493_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Out*494__uninitialized_allocator_copy_impl(_Alloc&, _In* __first1, _In* __last1, _Out* __first2) {495 if (__libcpp_is_constant_evaluated()) {496 while (__first1 != __last1) {497 std::__construct_at(std::__to_address(__first2), *__first1);498 ++__first1;499 ++__first2;500 }501 return __first2;502 } else {503 return std::copy(__first1, __last1, __first2);504 }505}506 507template <class _Alloc, class _Iter1, class _Sent1, class _Iter2>508_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2509__uninitialized_allocator_copy(_Alloc& __alloc, _Iter1 __first1, _Sent1 __last1, _Iter2 __first2) {510 auto __unwrapped_range = std::__unwrap_range(std::move(__first1), std::move(__last1));511 auto __result = std::__uninitialized_allocator_copy_impl(512 __alloc, std::move(__unwrapped_range.first), std::move(__unwrapped_range.second), std::__unwrap_iter(__first2));513 return std::__rewrap_iter(__first2, __result);514}515 516template <class _Alloc, class _Type>517inline const bool __allocator_has_trivial_move_construct_v = !__has_construct_v<_Alloc, _Type*, _Type&&>;518 519template <class _Type>520inline const bool __allocator_has_trivial_move_construct_v<allocator<_Type>, _Type> = true;521 522template <class _Alloc, class _Tp>523inline const bool __allocator_has_trivial_destroy_v = !__has_destroy_v<_Alloc, _Tp*>;524 525template <class _Tp, class _Up>526inline const bool __allocator_has_trivial_destroy_v<allocator<_Tp>, _Up> = true;527 528// __uninitialized_allocator_relocate relocates the objects in [__first, __last) into __result.529// Relocation means that the objects in [__first, __last) are placed into __result as-if by move-construct and destroy,530// except that the move constructor and destructor may never be called if they are known to be equivalent to a memcpy.531//532// Preconditions: __result doesn't contain any objects and [__first, __last) contains objects533// Postconditions: __result contains the objects from [__first, __last) and534// [__first, __last) doesn't contain any objects535//536// The strong exception guarantee is provided if any of the following are true:537// - is_nothrow_move_constructible<_ValueType>538// - is_copy_constructible<_ValueType>539// - __libcpp_is_trivially_relocatable<_ValueType>540template <class _Alloc, class _ContiguousIterator>541_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __uninitialized_allocator_relocate(542 _Alloc& __alloc, _ContiguousIterator __first, _ContiguousIterator __last, _ContiguousIterator __result) {543 static_assert(__libcpp_is_contiguous_iterator<_ContiguousIterator>::value, "");544 using _ValueType = typename iterator_traits<_ContiguousIterator>::value_type;545 static_assert(546 __is_cpp17_move_insertable_v<_Alloc>, "The specified type does not meet the requirements of Cpp17MoveInsertable");547 if (__libcpp_is_constant_evaluated() || !__libcpp_is_trivially_relocatable<_ValueType>::value ||548 !__allocator_has_trivial_move_construct_v<_Alloc, _ValueType> ||549 !__allocator_has_trivial_destroy_v<_Alloc, _ValueType>) {550 auto __destruct_first = __result;551 auto __guard = std::__make_exception_guard(552 _AllocatorDestroyRangeReverse<_Alloc, _ContiguousIterator>(__alloc, __destruct_first, __result));553 auto __iter = __first;554 while (__iter != __last) {555#if _LIBCPP_HAS_EXCEPTIONS556 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__result), std::move_if_noexcept(*__iter));557#else558 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__result), std::move(*__iter));559#endif560 ++__iter;561 ++__result;562 }563 __guard.__complete();564 std::__allocator_destroy(__alloc, __first, __last);565 } else {566 // Casting to void* to suppress clang complaining that this is technically UB.567 __builtin_memcpy(static_cast<void*>(std::__to_address(__result)),568 std::__to_address(__first),569 sizeof(_ValueType) * (__last - __first));570 }571}572 573_LIBCPP_END_NAMESPACE_STD574 575_LIBCPP_POP_MACROS576 577#endif // _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H578