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