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 <__config> 14 #include <__iterator/iterator_traits.h> 15 #include <__memory/addressof.h> 16 #include <__memory/allocator_traits.h> 17 #include <__memory/construct_at.h> 18 #include <__memory/voidify.h> 19 #include <__utility/move.h> 20 #include <__utility/pair.h> 21 #include <__utility/transaction.h> 22 #include <type_traits> 23 24 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 25 # pragma GCC system_header 26 #endif 27 28 _LIBCPP_BEGIN_NAMESPACE_STD 29 30 // This is a simplified version of C++20 `unreachable_sentinel` that doesn't use concepts and thus can be used in any 31 // language mode. 32 struct __unreachable_sentinel { 33 template <class _Iter> 34 _LIBCPP_HIDE_FROM_ABI friend _LIBCPP_CONSTEXPR bool operator!=(const _Iter&, __unreachable_sentinel) _NOEXCEPT { 35 return true; 36 } 37 }; 38 39 // uninitialized_copy 40 41 template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _Sentinel2> 42 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 43 __uninitialized_copy(_InputIterator __ifirst, _Sentinel1 __ilast, 44 _ForwardIterator __ofirst, _Sentinel2 __olast) { 45 _ForwardIterator __idx = __ofirst; 46 #ifndef _LIBCPP_NO_EXCEPTIONS 47 try { 48 #endif 49 for (; __ifirst != __ilast && __idx != __olast; ++__ifirst, (void)++__idx) 50 ::new (_VSTD::__voidify(*__idx)) _ValueType(*__ifirst); 51 #ifndef _LIBCPP_NO_EXCEPTIONS 52 } catch (...) { 53 _VSTD::__destroy(__ofirst, __idx); 54 throw; 55 } 56 #endif 57 58 return pair<_InputIterator, _ForwardIterator>(_VSTD::move(__ifirst), _VSTD::move(__idx)); 59 } 60 61 template <class _InputIterator, class _ForwardIterator> 62 _ForwardIterator uninitialized_copy(_InputIterator __ifirst, _InputIterator __ilast, 63 _ForwardIterator __ofirst) { 64 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; 65 auto __result = _VSTD::__uninitialized_copy<_ValueType>(_VSTD::move(__ifirst), _VSTD::move(__ilast), 66 _VSTD::move(__ofirst), __unreachable_sentinel()); 67 return _VSTD::move(__result.second); 68 } 69 70 // uninitialized_copy_n 71 72 template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _Sentinel> 73 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 74 __uninitialized_copy_n(_InputIterator __ifirst, _Size __n, 75 _ForwardIterator __ofirst, _Sentinel __olast) { 76 _ForwardIterator __idx = __ofirst; 77 #ifndef _LIBCPP_NO_EXCEPTIONS 78 try { 79 #endif 80 for (; __n > 0 && __idx != __olast; ++__ifirst, (void)++__idx, (void)--__n) 81 ::new (_VSTD::__voidify(*__idx)) _ValueType(*__ifirst); 82 #ifndef _LIBCPP_NO_EXCEPTIONS 83 } catch (...) { 84 _VSTD::__destroy(__ofirst, __idx); 85 throw; 86 } 87 #endif 88 89 return pair<_InputIterator, _ForwardIterator>(_VSTD::move(__ifirst), _VSTD::move(__idx)); 90 } 91 92 template <class _InputIterator, class _Size, class _ForwardIterator> 93 inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator uninitialized_copy_n(_InputIterator __ifirst, _Size __n, 94 _ForwardIterator __ofirst) { 95 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; 96 auto __result = _VSTD::__uninitialized_copy_n<_ValueType>(_VSTD::move(__ifirst), __n, _VSTD::move(__ofirst), 97 __unreachable_sentinel()); 98 return _VSTD::move(__result.second); 99 } 100 101 // uninitialized_fill 102 103 template <class _ValueType, class _ForwardIterator, class _Sentinel, class _Tp> 104 inline _LIBCPP_HIDE_FROM_ABI 105 _ForwardIterator __uninitialized_fill(_ForwardIterator __first, _Sentinel __last, const _Tp& __x) 106 { 107 _ForwardIterator __idx = __first; 108 #ifndef _LIBCPP_NO_EXCEPTIONS 109 try 110 { 111 #endif 112 for (; __idx != __last; ++__idx) 113 ::new (_VSTD::__voidify(*__idx)) _ValueType(__x); 114 #ifndef _LIBCPP_NO_EXCEPTIONS 115 } 116 catch (...) 117 { 118 _VSTD::__destroy(__first, __idx); 119 throw; 120 } 121 #endif 122 123 return __idx; 124 } 125 126 template <class _ForwardIterator, class _Tp> 127 inline _LIBCPP_HIDE_FROM_ABI 128 void uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __x) 129 { 130 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; 131 (void)_VSTD::__uninitialized_fill<_ValueType>(__first, __last, __x); 132 } 133 134 // uninitialized_fill_n 135 136 template <class _ValueType, class _ForwardIterator, class _Size, class _Tp> 137 inline _LIBCPP_HIDE_FROM_ABI 138 _ForwardIterator __uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) 139 { 140 _ForwardIterator __idx = __first; 141 #ifndef _LIBCPP_NO_EXCEPTIONS 142 try 143 { 144 #endif 145 for (; __n > 0; ++__idx, (void) --__n) 146 ::new (_VSTD::__voidify(*__idx)) _ValueType(__x); 147 #ifndef _LIBCPP_NO_EXCEPTIONS 148 } 149 catch (...) 150 { 151 _VSTD::__destroy(__first, __idx); 152 throw; 153 } 154 #endif 155 156 return __idx; 157 } 158 159 template <class _ForwardIterator, class _Size, class _Tp> 160 inline _LIBCPP_HIDE_FROM_ABI 161 _ForwardIterator uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) 162 { 163 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; 164 return _VSTD::__uninitialized_fill_n<_ValueType>(__first, __n, __x); 165 } 166 167 #if _LIBCPP_STD_VER > 14 168 169 // uninitialized_default_construct 170 171 template <class _ValueType, class _ForwardIterator, class _Sentinel> 172 inline _LIBCPP_HIDE_FROM_ABI 173 _ForwardIterator __uninitialized_default_construct(_ForwardIterator __first, _Sentinel __last) { 174 auto __idx = __first; 175 #ifndef _LIBCPP_NO_EXCEPTIONS 176 try { 177 #endif 178 for (; __idx != __last; ++__idx) 179 ::new (_VSTD::__voidify(*__idx)) _ValueType; 180 #ifndef _LIBCPP_NO_EXCEPTIONS 181 } catch (...) { 182 _VSTD::__destroy(__first, __idx); 183 throw; 184 } 185 #endif 186 187 return __idx; 188 } 189 190 template <class _ForwardIterator> 191 inline _LIBCPP_HIDE_FROM_ABI 192 void uninitialized_default_construct(_ForwardIterator __first, _ForwardIterator __last) { 193 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 194 (void)_VSTD::__uninitialized_default_construct<_ValueType>( 195 _VSTD::move(__first), _VSTD::move(__last)); 196 } 197 198 // uninitialized_default_construct_n 199 200 template <class _ValueType, class _ForwardIterator, class _Size> 201 inline _LIBCPP_HIDE_FROM_ABI 202 _ForwardIterator __uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) { 203 auto __idx = __first; 204 #ifndef _LIBCPP_NO_EXCEPTIONS 205 try { 206 #endif 207 for (; __n > 0; ++__idx, (void) --__n) 208 ::new (_VSTD::__voidify(*__idx)) _ValueType; 209 #ifndef _LIBCPP_NO_EXCEPTIONS 210 } catch (...) { 211 _VSTD::__destroy(__first, __idx); 212 throw; 213 } 214 #endif 215 216 return __idx; 217 } 218 219 template <class _ForwardIterator, class _Size> 220 inline _LIBCPP_HIDE_FROM_ABI 221 _ForwardIterator uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) { 222 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 223 return _VSTD::__uninitialized_default_construct_n<_ValueType>(_VSTD::move(__first), __n); 224 } 225 226 // uninitialized_value_construct 227 228 template <class _ValueType, class _ForwardIterator, class _Sentinel> 229 inline _LIBCPP_HIDE_FROM_ABI 230 _ForwardIterator __uninitialized_value_construct(_ForwardIterator __first, _Sentinel __last) { 231 auto __idx = __first; 232 #ifndef _LIBCPP_NO_EXCEPTIONS 233 try { 234 #endif 235 for (; __idx != __last; ++__idx) 236 ::new (_VSTD::__voidify(*__idx)) _ValueType(); 237 #ifndef _LIBCPP_NO_EXCEPTIONS 238 } catch (...) { 239 _VSTD::__destroy(__first, __idx); 240 throw; 241 } 242 #endif 243 244 return __idx; 245 } 246 247 template <class _ForwardIterator> 248 inline _LIBCPP_HIDE_FROM_ABI 249 void uninitialized_value_construct(_ForwardIterator __first, _ForwardIterator __last) { 250 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 251 (void)_VSTD::__uninitialized_value_construct<_ValueType>( 252 _VSTD::move(__first), _VSTD::move(__last)); 253 } 254 255 // uninitialized_value_construct_n 256 257 template <class _ValueType, class _ForwardIterator, class _Size> 258 inline _LIBCPP_HIDE_FROM_ABI 259 _ForwardIterator __uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) { 260 auto __idx = __first; 261 #ifndef _LIBCPP_NO_EXCEPTIONS 262 try { 263 #endif 264 for (; __n > 0; ++__idx, (void) --__n) 265 ::new (_VSTD::__voidify(*__idx)) _ValueType(); 266 #ifndef _LIBCPP_NO_EXCEPTIONS 267 } catch (...) { 268 _VSTD::__destroy(__first, __idx); 269 throw; 270 } 271 #endif 272 273 return __idx; 274 } 275 276 template <class _ForwardIterator, class _Size> 277 inline _LIBCPP_HIDE_FROM_ABI 278 _ForwardIterator uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) { 279 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 280 return __uninitialized_value_construct_n<_ValueType>(_VSTD::move(__first), __n); 281 } 282 283 // uninitialized_move 284 285 template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _Sentinel2, 286 class _IterMove> 287 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 288 __uninitialized_move(_InputIterator __ifirst, _Sentinel1 __ilast, 289 _ForwardIterator __ofirst, _Sentinel2 __olast, _IterMove __iter_move) { 290 auto __idx = __ofirst; 291 #ifndef _LIBCPP_NO_EXCEPTIONS 292 try { 293 #endif 294 for (; __ifirst != __ilast && __idx != __olast; ++__idx, (void)++__ifirst) { 295 ::new (_VSTD::__voidify(*__idx)) _ValueType(__iter_move(__ifirst)); 296 } 297 #ifndef _LIBCPP_NO_EXCEPTIONS 298 } catch (...) { 299 _VSTD::__destroy(__ofirst, __idx); 300 throw; 301 } 302 #endif 303 304 return {_VSTD::move(__ifirst), _VSTD::move(__idx)}; 305 } 306 307 template <class _InputIterator, class _ForwardIterator> 308 inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator uninitialized_move(_InputIterator __ifirst, _InputIterator __ilast, 309 _ForwardIterator __ofirst) { 310 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 311 auto __iter_move = [](auto&& __iter) -> decltype(auto) { return _VSTD::move(*__iter); }; 312 313 auto __result = _VSTD::__uninitialized_move<_ValueType>(_VSTD::move(__ifirst), _VSTD::move(__ilast), 314 _VSTD::move(__ofirst), __unreachable_sentinel(), __iter_move); 315 return _VSTD::move(__result.second); 316 } 317 318 // uninitialized_move_n 319 320 template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _Sentinel, class _IterMove> 321 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 322 __uninitialized_move_n(_InputIterator __ifirst, _Size __n, 323 _ForwardIterator __ofirst, _Sentinel __olast, _IterMove __iter_move) { 324 auto __idx = __ofirst; 325 #ifndef _LIBCPP_NO_EXCEPTIONS 326 try { 327 #endif 328 for (; __n > 0 && __idx != __olast; ++__idx, (void)++__ifirst, --__n) 329 ::new (_VSTD::__voidify(*__idx)) _ValueType(__iter_move(__ifirst)); 330 #ifndef _LIBCPP_NO_EXCEPTIONS 331 } catch (...) { 332 _VSTD::__destroy(__ofirst, __idx); 333 throw; 334 } 335 #endif 336 337 return {_VSTD::move(__ifirst), _VSTD::move(__idx)}; 338 } 339 340 template <class _InputIterator, class _Size, class _ForwardIterator> 341 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 342 uninitialized_move_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) { 343 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 344 auto __iter_move = [](auto&& __iter) -> decltype(auto) { return _VSTD::move(*__iter); }; 345 346 return _VSTD::__uninitialized_move_n<_ValueType>(_VSTD::move(__ifirst), __n, _VSTD::move(__ofirst), 347 __unreachable_sentinel(), __iter_move); 348 } 349 350 #endif // _LIBCPP_STD_VER > 14 351 352 #if _LIBCPP_STD_VER > 17 353 354 // Destroys every element in the range [first, last) FROM RIGHT TO LEFT using allocator 355 // destruction. If elements are themselves C-style arrays, they are recursively destroyed 356 // in the same manner. 357 // 358 // This function assumes that destructors do not throw, and that the allocator is bound to 359 // the correct type. 360 template<class _Alloc, class _BidirIter, class = __enable_if_t< 361 __is_cpp17_bidirectional_iterator<_BidirIter>::value 362 >> 363 _LIBCPP_HIDE_FROM_ABI 364 constexpr void __allocator_destroy_multidimensional(_Alloc& __alloc, _BidirIter __first, _BidirIter __last) noexcept { 365 using _ValueType = typename iterator_traits<_BidirIter>::value_type; 366 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _ValueType>, 367 "The allocator should already be rebound to the correct type"); 368 369 if (__first == __last) 370 return; 371 372 if constexpr (is_array_v<_ValueType>) { 373 static_assert(!is_unbounded_array_v<_ValueType>, 374 "arrays of unbounded arrays don't exist, but if they did we would mess up here"); 375 376 using _Element = remove_extent_t<_ValueType>; 377 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc); 378 do { 379 --__last; 380 decltype(auto) __array = *__last; 381 std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + extent_v<_ValueType>); 382 } while (__last != __first); 383 } else { 384 do { 385 --__last; 386 allocator_traits<_Alloc>::destroy(__alloc, std::addressof(*__last)); 387 } while (__last != __first); 388 } 389 } 390 391 // Constructs the object at the given location using the allocator's construct method. 392 // 393 // If the object being constructed is an array, each element of the array is allocator-constructed, 394 // recursively. If an exception is thrown during the construction of an array, the initialized 395 // elements are destroyed in reverse order of initialization using allocator destruction. 396 // 397 // This function assumes that the allocator is bound to the correct type. 398 template<class _Alloc, class _Tp> 399 _LIBCPP_HIDE_FROM_ABI 400 constexpr void __allocator_construct_at(_Alloc& __alloc, _Tp* __loc) { 401 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>, 402 "The allocator should already be rebound to the correct type"); 403 404 if constexpr (is_array_v<_Tp>) { 405 using _Element = remove_extent_t<_Tp>; 406 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc); 407 size_t __i = 0; 408 _Tp& __array = *__loc; 409 410 // If an exception is thrown, destroy what we have constructed so far in reverse order. 411 __transaction __guard([&]() { std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i); }); 412 for (; __i != extent_v<_Tp>; ++__i) { 413 std::__allocator_construct_at(__elem_alloc, std::addressof(__array[__i])); 414 } 415 __guard.__complete(); 416 } else { 417 allocator_traits<_Alloc>::construct(__alloc, __loc); 418 } 419 } 420 421 // Constructs the object at the given location using the allocator's construct method, passing along 422 // the provided argument. 423 // 424 // If the object being constructed is an array, the argument is also assumed to be an array. Each 425 // each element of the array being constructed is allocator-constructed from the corresponding 426 // element of the argument array. If an exception is thrown during the construction of an array, 427 // the initialized elements are destroyed in reverse order of initialization using allocator 428 // destruction. 429 // 430 // This function assumes that the allocator is bound to the correct type. 431 template<class _Alloc, class _Tp, class _Arg> 432 _LIBCPP_HIDE_FROM_ABI 433 constexpr void __allocator_construct_at(_Alloc& __alloc, _Tp* __loc, _Arg const& __arg) { 434 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>, 435 "The allocator should already be rebound to the correct type"); 436 437 if constexpr (is_array_v<_Tp>) { 438 static_assert(is_array_v<_Arg>, 439 "Provided non-array initialization argument to __allocator_construct_at when " 440 "trying to construct an array."); 441 442 using _Element = remove_extent_t<_Tp>; 443 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc); 444 size_t __i = 0; 445 _Tp& __array = *__loc; 446 447 // If an exception is thrown, destroy what we have constructed so far in reverse order. 448 __transaction __guard([&]() { std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i); }); 449 for (; __i != extent_v<_Tp>; ++__i) { 450 std::__allocator_construct_at(__elem_alloc, std::addressof(__array[__i]), __arg[__i]); 451 } 452 __guard.__complete(); 453 } else { 454 allocator_traits<_Alloc>::construct(__alloc, __loc, __arg); 455 } 456 } 457 458 // Given a range starting at it and containing n elements, initializes each element in the 459 // range from left to right using the construct method of the allocator (rebound to the 460 // correct type). 461 // 462 // If an exception is thrown, the initialized elements are destroyed in reverse order of 463 // initialization using allocator_traits destruction. If the elements in the range are C-style 464 // arrays, they are initialized element-wise using allocator construction, and recursively so. 465 template<class _Alloc, class _BidirIter, class _Tp, class _Size = typename iterator_traits<_BidirIter>::difference_type> 466 _LIBCPP_HIDE_FROM_ABI 467 constexpr void __uninitialized_allocator_fill_n(_Alloc& __alloc, _BidirIter __it, _Size __n, _Tp const& __value) { 468 using _ValueType = typename iterator_traits<_BidirIter>::value_type; 469 __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc); 470 _BidirIter __begin = __it; 471 472 // If an exception is thrown, destroy what we have constructed so far in reverse order. 473 __transaction __guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); }); 474 for (; __n != 0; --__n, ++__it) { 475 std::__allocator_construct_at(__value_alloc, std::addressof(*__it), __value); 476 } 477 __guard.__complete(); 478 } 479 480 // Same as __uninitialized_allocator_fill_n, but doesn't pass any initialization argument 481 // to the allocator's construct method, which results in value initialization. 482 template<class _Alloc, class _BidirIter, class _Size = typename iterator_traits<_BidirIter>::difference_type> 483 _LIBCPP_HIDE_FROM_ABI 484 constexpr void __uninitialized_allocator_value_construct_n(_Alloc& __alloc, _BidirIter __it, _Size __n) { 485 using _ValueType = typename iterator_traits<_BidirIter>::value_type; 486 __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc); 487 _BidirIter __begin = __it; 488 489 // If an exception is thrown, destroy what we have constructed so far in reverse order. 490 __transaction __guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); }); 491 for (; __n != 0; --__n, ++__it) { 492 std::__allocator_construct_at(__value_alloc, std::addressof(*__it)); 493 } 494 __guard.__complete(); 495 } 496 497 #endif // _LIBCPP_STD_VER > 17 498 499 _LIBCPP_END_NAMESPACE_STD 500 501 #endif // _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H 502