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