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 // Destroys every element in the range [first, last) FROM RIGHT TO LEFT using allocator 351 // destruction. If elements are themselves C-style arrays, they are recursively destroyed 352 // in the same manner. 353 // 354 // This function assumes that destructors do not throw, and that the allocator is bound to 355 // the correct type. 356 template<class _Alloc, class _BidirIter, class = __enable_if_t< 357 __is_cpp17_bidirectional_iterator<_BidirIter>::value 358 >> 359 _LIBCPP_HIDE_FROM_ABI 360 constexpr void __allocator_destroy_multidimensional(_Alloc& __alloc, _BidirIter __first, _BidirIter __last) noexcept { 361 using _ValueType = typename iterator_traits<_BidirIter>::value_type; 362 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _ValueType>, 363 "The allocator should already be rebound to the correct type"); 364 365 if (__first == __last) 366 return; 367 368 if constexpr (is_array_v<_ValueType>) { 369 static_assert(!__libcpp_is_unbounded_array<_ValueType>::value, 370 "arrays of unbounded arrays don't exist, but if they did we would mess up here"); 371 372 using _Element = remove_extent_t<_ValueType>; 373 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc); 374 do { 375 --__last; 376 decltype(auto) __array = *__last; 377 std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + extent_v<_ValueType>); 378 } while (__last != __first); 379 } else { 380 do { 381 --__last; 382 allocator_traits<_Alloc>::destroy(__alloc, std::addressof(*__last)); 383 } while (__last != __first); 384 } 385 } 386 387 // Constructs the object at the given location using the allocator's construct method. 388 // 389 // If the object being constructed is an array, each element of the array is allocator-constructed, 390 // recursively. If an exception is thrown during the construction of an array, the initialized 391 // elements are destroyed in reverse order of initialization using allocator destruction. 392 // 393 // This function assumes that the allocator is bound to the correct type. 394 template<class _Alloc, class _Tp> 395 _LIBCPP_HIDE_FROM_ABI 396 constexpr void __allocator_construct_at(_Alloc& __alloc, _Tp* __loc) { 397 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>, 398 "The allocator should already be rebound to the correct type"); 399 400 if constexpr (is_array_v<_Tp>) { 401 using _Element = remove_extent_t<_Tp>; 402 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc); 403 size_t __i = 0; 404 _Tp& __array = *__loc; 405 406 // If an exception is thrown, destroy what we have constructed so far in reverse order. 407 __transaction __guard([&]() { std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i); }); 408 for (; __i != extent_v<_Tp>; ++__i) { 409 std::__allocator_construct_at(__elem_alloc, std::addressof(__array[__i])); 410 } 411 __guard.__complete(); 412 } else { 413 allocator_traits<_Alloc>::construct(__alloc, __loc); 414 } 415 } 416 417 // Constructs the object at the given location using the allocator's construct method, passing along 418 // the provided argument. 419 // 420 // If the object being constructed is an array, the argument is also assumed to be an array. Each 421 // each element of the array being constructed is allocator-constructed from the corresponding 422 // element of the argument array. If an exception is thrown during the construction of an array, 423 // the initialized elements are destroyed in reverse order of initialization using allocator 424 // destruction. 425 // 426 // This function assumes that the allocator is bound to the correct type. 427 template<class _Alloc, class _Tp, class _Arg> 428 _LIBCPP_HIDE_FROM_ABI 429 constexpr void __allocator_construct_at(_Alloc& __alloc, _Tp* __loc, _Arg const& __arg) { 430 static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>, 431 "The allocator should already be rebound to the correct type"); 432 433 if constexpr (is_array_v<_Tp>) { 434 static_assert(is_array_v<_Arg>, 435 "Provided non-array initialization argument to __allocator_construct_at when " 436 "trying to construct an array."); 437 438 using _Element = remove_extent_t<_Tp>; 439 __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc); 440 size_t __i = 0; 441 _Tp& __array = *__loc; 442 443 // If an exception is thrown, destroy what we have constructed so far in reverse order. 444 __transaction __guard([&]() { std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i); }); 445 for (; __i != extent_v<_Tp>; ++__i) { 446 std::__allocator_construct_at(__elem_alloc, std::addressof(__array[__i]), __arg[__i]); 447 } 448 __guard.__complete(); 449 } else { 450 allocator_traits<_Alloc>::construct(__alloc, __loc, __arg); 451 } 452 } 453 454 // Given a range starting at it and containing n elements, initializes each element in the 455 // range from left to right using the construct method of the allocator (rebound to the 456 // correct type). 457 // 458 // If an exception is thrown, the initialized elements are destroyed in reverse order of 459 // initialization using allocator_traits destruction. If the elements in the range are C-style 460 // arrays, they are initialized element-wise using allocator construction, and recursively so. 461 template<class _Alloc, class _BidirIter, class _Tp, class _Size = typename iterator_traits<_BidirIter>::difference_type> 462 _LIBCPP_HIDE_FROM_ABI 463 constexpr void __uninitialized_allocator_fill_n(_Alloc& __alloc, _BidirIter __it, _Size __n, _Tp const& __value) { 464 using _ValueType = typename iterator_traits<_BidirIter>::value_type; 465 __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc); 466 _BidirIter __begin = __it; 467 468 // If an exception is thrown, destroy what we have constructed so far in reverse order. 469 __transaction __guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); }); 470 for (; __n != 0; --__n, ++__it) { 471 std::__allocator_construct_at(__value_alloc, std::addressof(*__it), __value); 472 } 473 __guard.__complete(); 474 } 475 476 // Same as __uninitialized_allocator_fill_n, but doesn't pass any initialization argument 477 // to the allocator's construct method, which results in value initialization. 478 template<class _Alloc, class _BidirIter, class _Size = typename iterator_traits<_BidirIter>::difference_type> 479 _LIBCPP_HIDE_FROM_ABI 480 constexpr void __uninitialized_allocator_value_construct_n(_Alloc& __alloc, _BidirIter __it, _Size __n) { 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 __transaction __guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); }); 487 for (; __n != 0; --__n, ++__it) { 488 std::__allocator_construct_at(__value_alloc, std::addressof(*__it)); 489 } 490 __guard.__complete(); 491 } 492 493 #endif // _LIBCPP_STD_VER > 14 494 495 _LIBCPP_END_NAMESPACE_STD 496 497 #endif // _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H 498