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_copy_assignable.h> 29 #include <__type_traits/is_trivially_copy_constructible.h> 30 #include <__type_traits/is_trivially_move_assignable.h> 31 #include <__type_traits/is_trivially_move_constructible.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 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS 64 try { 65 #endif 66 for (; __ifirst != __ilast && !__stop_copying(__idx); ++__ifirst, (void)++__idx) 67 ::new (std::__voidify(*__idx)) _ValueType(*__ifirst); 68 #ifndef _LIBCPP_HAS_NO_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 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS 94 try { 95 #endif 96 for (; __n > 0 && !__stop_copying(__idx); ++__ifirst, (void)++__idx, (void)--__n) 97 ::new (std::__voidify(*__idx)) _ValueType(*__ifirst); 98 #ifndef _LIBCPP_HAS_NO_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 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS 124 try { 125 #endif 126 for (; __idx != __last; ++__idx) 127 ::new (std::__voidify(*__idx)) _ValueType(__x); 128 #ifndef _LIBCPP_HAS_NO_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 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS 152 try { 153 #endif 154 for (; __n > 0; ++__idx, (void)--__n) 155 ::new (std::__voidify(*__idx)) _ValueType(__x); 156 #ifndef _LIBCPP_HAS_NO_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 # ifndef _LIBCPP_HAS_NO_EXCEPTIONS 182 try { 183 # endif 184 for (; __idx != __last; ++__idx) 185 ::new (std::__voidify(*__idx)) _ValueType; 186 # ifndef _LIBCPP_HAS_NO_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 # ifndef _LIBCPP_HAS_NO_EXCEPTIONS 208 try { 209 # endif 210 for (; __n > 0; ++__idx, (void)--__n) 211 ::new (std::__voidify(*__idx)) _ValueType; 212 # ifndef _LIBCPP_HAS_NO_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 # ifndef _LIBCPP_HAS_NO_EXCEPTIONS 235 try { 236 # endif 237 for (; __idx != __last; ++__idx) 238 ::new (std::__voidify(*__idx)) _ValueType(); 239 # ifndef _LIBCPP_HAS_NO_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 # ifndef _LIBCPP_HAS_NO_EXCEPTIONS 261 try { 262 # endif 263 for (; __n > 0; ++__idx, (void)--__n) 264 ::new (std::__voidify(*__idx)) _ValueType(); 265 # ifndef _LIBCPP_HAS_NO_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 # ifndef _LIBCPP_HAS_NO_EXCEPTIONS 297 try { 298 # endif 299 for (; __ifirst != __ilast && !__stop_moving(__idx); ++__idx, (void)++__ifirst) { 300 ::new (std::__voidify(*__idx)) _ValueType(__iter_move(__ifirst)); 301 } 302 # ifndef _LIBCPP_HAS_NO_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 # ifndef _LIBCPP_HAS_NO_EXCEPTIONS 335 try { 336 # endif 337 for (; __n > 0 && !__stop_moving(__idx); ++__idx, (void)++__ifirst, --__n) 338 ::new (std::__voidify(*__idx)) _ValueType(__iter_move(__ifirst)); 339 # ifndef _LIBCPP_HAS_NO_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 class = __enable_if_t< __has_bidirectional_iterator_category<_BidirIter>::value >> 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(!__libcpp_is_unbounded_array<_ValueType>::value, 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 _RawTypeIn = __remove_const_t<_In>, 567 class _Out, 568 __enable_if_t< 569 // using _RawTypeIn because of the allocator<T const> extension 570 is_trivially_copy_constructible<_RawTypeIn>::value && is_trivially_copy_assignable<_RawTypeIn>::value && 571 is_same<__remove_const_t<_In>, __remove_const_t<_Out> >::value && 572 __allocator_has_trivial_copy_construct<_Alloc, _RawTypeIn>::value>* = nullptr> 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 // Move-construct the elements [__first1, __last1) into [__first2, __first2 + N) 598 // if the move constructor is noexcept, where N is distance(__first1, __last1). 599 // 600 // Otherwise try to copy all elements. If an exception is thrown the already copied 601 // elements are destroyed in reverse order of their construction. 602 template <class _Alloc, class _Iter1, class _Sent1, class _Iter2> 603 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2 604 __uninitialized_allocator_move_if_noexcept(_Alloc& __alloc, _Iter1 __first1, _Sent1 __last1, _Iter2 __first2) { 605 static_assert(__is_cpp17_move_insertable<_Alloc>::value, 606 "The specified type does not meet the requirements of Cpp17MoveInsertable"); 607 auto __destruct_first = __first2; 608 auto __guard = 609 std::__make_exception_guard(_AllocatorDestroyRangeReverse<_Alloc, _Iter2>(__alloc, __destruct_first, __first2)); 610 while (__first1 != __last1) { 611 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS 612 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__first2), std::move_if_noexcept(*__first1)); 613 #else 614 allocator_traits<_Alloc>::construct(__alloc, std::__to_address(__first2), std::move(*__first1)); 615 #endif 616 ++__first1; 617 ++__first2; 618 } 619 __guard.__complete(); 620 return __first2; 621 } 622 623 template <class _Alloc, class _Type> 624 struct __allocator_has_trivial_move_construct : _Not<__has_construct<_Alloc, _Type*, _Type&&> > {}; 625 626 template <class _Type> 627 struct __allocator_has_trivial_move_construct<allocator<_Type>, _Type> : true_type {}; 628 629 #ifndef _LIBCPP_COMPILER_GCC 630 template < 631 class _Alloc, 632 class _Iter1, 633 class _Iter2, 634 class _Type = typename iterator_traits<_Iter1>::value_type, 635 class = __enable_if_t<is_trivially_move_constructible<_Type>::value && is_trivially_move_assignable<_Type>::value && 636 __allocator_has_trivial_move_construct<_Alloc, _Type>::value> > 637 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter2 638 __uninitialized_allocator_move_if_noexcept(_Alloc&, _Iter1 __first1, _Iter1 __last1, _Iter2 __first2) { 639 if (__libcpp_is_constant_evaluated()) { 640 while (__first1 != __last1) { 641 std::__construct_at(std::__to_address(__first2), std::move(*__first1)); 642 ++__first1; 643 ++__first2; 644 } 645 return __first2; 646 } else { 647 return std::move(__first1, __last1, __first2); 648 } 649 } 650 #endif // _LIBCPP_COMPILER_GCC 651 652 _LIBCPP_END_NAMESPACE_STD 653 654 _LIBCPP_POP_MACROS 655 656 #endif // _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H 657