libcxx/include/__memory/uninitialized_algorithms.h

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