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/construct_at.h> 17 #include <__memory/voidify.h> 18 #include <__utility/move.h> 19 #include <__utility/pair.h> 20 21 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 22 # pragma GCC system_header 23 #endif 24 25 _LIBCPP_BEGIN_NAMESPACE_STD 26 27 // This is a simplified version of C++20 `unreachable_sentinel` that doesn't use concepts and thus can be used in any 28 // language mode. 29 struct __unreachable_sentinel { 30 template <class _Iter> 31 _LIBCPP_HIDE_FROM_ABI friend _LIBCPP_CONSTEXPR bool operator!=(const _Iter&, __unreachable_sentinel) _NOEXCEPT { 32 return true; 33 } 34 }; 35 36 // uninitialized_copy 37 38 template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _Sentinel2> 39 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 40 __uninitialized_copy(_InputIterator __ifirst, _Sentinel1 __ilast, 41 _ForwardIterator __ofirst, _Sentinel2 __olast) { 42 _ForwardIterator __idx = __ofirst; 43 #ifndef _LIBCPP_NO_EXCEPTIONS 44 try { 45 #endif 46 for (; __ifirst != __ilast && __idx != __olast; ++__ifirst, (void)++__idx) 47 ::new (_VSTD::__voidify(*__idx)) _ValueType(*__ifirst); 48 #ifndef _LIBCPP_NO_EXCEPTIONS 49 } catch (...) { 50 _VSTD::__destroy(__ofirst, __idx); 51 throw; 52 } 53 #endif 54 55 return pair<_InputIterator, _ForwardIterator>(_VSTD::move(__ifirst), _VSTD::move(__idx)); 56 } 57 58 template <class _InputIterator, class _ForwardIterator> 59 _ForwardIterator uninitialized_copy(_InputIterator __ifirst, _InputIterator __ilast, 60 _ForwardIterator __ofirst) { 61 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; 62 auto __result = _VSTD::__uninitialized_copy<_ValueType>(_VSTD::move(__ifirst), _VSTD::move(__ilast), 63 _VSTD::move(__ofirst), __unreachable_sentinel()); 64 return _VSTD::move(__result.second); 65 } 66 67 // uninitialized_copy_n 68 69 template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _Sentinel> 70 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 71 __uninitialized_copy_n(_InputIterator __ifirst, _Size __n, 72 _ForwardIterator __ofirst, _Sentinel __olast) { 73 _ForwardIterator __idx = __ofirst; 74 #ifndef _LIBCPP_NO_EXCEPTIONS 75 try { 76 #endif 77 for (; __n > 0 && __idx != __olast; ++__ifirst, (void)++__idx, (void)--__n) 78 ::new (_VSTD::__voidify(*__idx)) _ValueType(*__ifirst); 79 #ifndef _LIBCPP_NO_EXCEPTIONS 80 } catch (...) { 81 _VSTD::__destroy(__ofirst, __idx); 82 throw; 83 } 84 #endif 85 86 return pair<_InputIterator, _ForwardIterator>(_VSTD::move(__ifirst), _VSTD::move(__idx)); 87 } 88 89 template <class _InputIterator, class _Size, class _ForwardIterator> 90 inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator uninitialized_copy_n(_InputIterator __ifirst, _Size __n, 91 _ForwardIterator __ofirst) { 92 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; 93 auto __result = _VSTD::__uninitialized_copy_n<_ValueType>(_VSTD::move(__ifirst), __n, _VSTD::move(__ofirst), 94 __unreachable_sentinel()); 95 return _VSTD::move(__result.second); 96 } 97 98 // uninitialized_fill 99 100 template <class _ValueType, class _ForwardIterator, class _Sentinel, class _Tp> 101 inline _LIBCPP_HIDE_FROM_ABI 102 _ForwardIterator __uninitialized_fill(_ForwardIterator __first, _Sentinel __last, const _Tp& __x) 103 { 104 _ForwardIterator __idx = __first; 105 #ifndef _LIBCPP_NO_EXCEPTIONS 106 try 107 { 108 #endif 109 for (; __idx != __last; ++__idx) 110 ::new (_VSTD::__voidify(*__idx)) _ValueType(__x); 111 #ifndef _LIBCPP_NO_EXCEPTIONS 112 } 113 catch (...) 114 { 115 _VSTD::__destroy(__first, __idx); 116 throw; 117 } 118 #endif 119 120 return __idx; 121 } 122 123 template <class _ForwardIterator, class _Tp> 124 inline _LIBCPP_HIDE_FROM_ABI 125 void uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __x) 126 { 127 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; 128 (void)_VSTD::__uninitialized_fill<_ValueType>(__first, __last, __x); 129 } 130 131 // uninitialized_fill_n 132 133 template <class _ValueType, class _ForwardIterator, class _Size, class _Tp> 134 inline _LIBCPP_HIDE_FROM_ABI 135 _ForwardIterator __uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) 136 { 137 _ForwardIterator __idx = __first; 138 #ifndef _LIBCPP_NO_EXCEPTIONS 139 try 140 { 141 #endif 142 for (; __n > 0; ++__idx, (void) --__n) 143 ::new (_VSTD::__voidify(*__idx)) _ValueType(__x); 144 #ifndef _LIBCPP_NO_EXCEPTIONS 145 } 146 catch (...) 147 { 148 _VSTD::__destroy(__first, __idx); 149 throw; 150 } 151 #endif 152 153 return __idx; 154 } 155 156 template <class _ForwardIterator, class _Size, class _Tp> 157 inline _LIBCPP_HIDE_FROM_ABI 158 _ForwardIterator uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x) 159 { 160 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; 161 return _VSTD::__uninitialized_fill_n<_ValueType>(__first, __n, __x); 162 } 163 164 #if _LIBCPP_STD_VER > 14 165 166 // uninitialized_default_construct 167 168 template <class _ValueType, class _ForwardIterator, class _Sentinel> 169 inline _LIBCPP_HIDE_FROM_ABI 170 _ForwardIterator __uninitialized_default_construct(_ForwardIterator __first, _Sentinel __last) { 171 auto __idx = __first; 172 #ifndef _LIBCPP_NO_EXCEPTIONS 173 try { 174 #endif 175 for (; __idx != __last; ++__idx) 176 ::new (_VSTD::__voidify(*__idx)) _ValueType; 177 #ifndef _LIBCPP_NO_EXCEPTIONS 178 } catch (...) { 179 _VSTD::__destroy(__first, __idx); 180 throw; 181 } 182 #endif 183 184 return __idx; 185 } 186 187 template <class _ForwardIterator> 188 inline _LIBCPP_HIDE_FROM_ABI 189 void uninitialized_default_construct(_ForwardIterator __first, _ForwardIterator __last) { 190 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 191 (void)_VSTD::__uninitialized_default_construct<_ValueType>( 192 _VSTD::move(__first), _VSTD::move(__last)); 193 } 194 195 // uninitialized_default_construct_n 196 197 template <class _ValueType, class _ForwardIterator, class _Size> 198 inline _LIBCPP_HIDE_FROM_ABI 199 _ForwardIterator __uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) { 200 auto __idx = __first; 201 #ifndef _LIBCPP_NO_EXCEPTIONS 202 try { 203 #endif 204 for (; __n > 0; ++__idx, (void) --__n) 205 ::new (_VSTD::__voidify(*__idx)) _ValueType; 206 #ifndef _LIBCPP_NO_EXCEPTIONS 207 } catch (...) { 208 _VSTD::__destroy(__first, __idx); 209 throw; 210 } 211 #endif 212 213 return __idx; 214 } 215 216 template <class _ForwardIterator, class _Size> 217 inline _LIBCPP_HIDE_FROM_ABI 218 _ForwardIterator uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) { 219 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 220 return _VSTD::__uninitialized_default_construct_n<_ValueType>(_VSTD::move(__first), __n); 221 } 222 223 // uninitialized_value_construct 224 225 template <class _ValueType, class _ForwardIterator, class _Sentinel> 226 inline _LIBCPP_HIDE_FROM_ABI 227 _ForwardIterator __uninitialized_value_construct(_ForwardIterator __first, _Sentinel __last) { 228 auto __idx = __first; 229 #ifndef _LIBCPP_NO_EXCEPTIONS 230 try { 231 #endif 232 for (; __idx != __last; ++__idx) 233 ::new (_VSTD::__voidify(*__idx)) _ValueType(); 234 #ifndef _LIBCPP_NO_EXCEPTIONS 235 } catch (...) { 236 _VSTD::__destroy(__first, __idx); 237 throw; 238 } 239 #endif 240 241 return __idx; 242 } 243 244 template <class _ForwardIterator> 245 inline _LIBCPP_HIDE_FROM_ABI 246 void uninitialized_value_construct(_ForwardIterator __first, _ForwardIterator __last) { 247 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 248 (void)_VSTD::__uninitialized_value_construct<_ValueType>( 249 _VSTD::move(__first), _VSTD::move(__last)); 250 } 251 252 // uninitialized_value_construct_n 253 254 template <class _ValueType, class _ForwardIterator, class _Size> 255 inline _LIBCPP_HIDE_FROM_ABI 256 _ForwardIterator __uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) { 257 auto __idx = __first; 258 #ifndef _LIBCPP_NO_EXCEPTIONS 259 try { 260 #endif 261 for (; __n > 0; ++__idx, (void) --__n) 262 ::new (_VSTD::__voidify(*__idx)) _ValueType(); 263 #ifndef _LIBCPP_NO_EXCEPTIONS 264 } catch (...) { 265 _VSTD::__destroy(__first, __idx); 266 throw; 267 } 268 #endif 269 270 return __idx; 271 } 272 273 template <class _ForwardIterator, class _Size> 274 inline _LIBCPP_HIDE_FROM_ABI 275 _ForwardIterator uninitialized_value_construct_n(_ForwardIterator __first, _Size __n) { 276 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 277 return __uninitialized_value_construct_n<_ValueType>(_VSTD::move(__first), __n); 278 } 279 280 // uninitialized_move 281 282 template <class _ValueType, class _InputIterator, class _Sentinel1, class _ForwardIterator, class _Sentinel2, 283 class _IterMove> 284 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 285 __uninitialized_move(_InputIterator __ifirst, _Sentinel1 __ilast, 286 _ForwardIterator __ofirst, _Sentinel2 __olast, _IterMove __iter_move) { 287 auto __idx = __ofirst; 288 #ifndef _LIBCPP_NO_EXCEPTIONS 289 try { 290 #endif 291 for (; __ifirst != __ilast && __idx != __olast; ++__idx, (void)++__ifirst) { 292 ::new (_VSTD::__voidify(*__idx)) _ValueType(__iter_move(__ifirst)); 293 } 294 #ifndef _LIBCPP_NO_EXCEPTIONS 295 } catch (...) { 296 _VSTD::__destroy(__ofirst, __idx); 297 throw; 298 } 299 #endif 300 301 return {_VSTD::move(__ifirst), _VSTD::move(__idx)}; 302 } 303 304 template <class _InputIterator, class _ForwardIterator> 305 inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator uninitialized_move(_InputIterator __ifirst, _InputIterator __ilast, 306 _ForwardIterator __ofirst) { 307 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 308 auto __iter_move = [](auto&& __iter) -> decltype(auto) { return _VSTD::move(*__iter); }; 309 310 auto __result = _VSTD::__uninitialized_move<_ValueType>(_VSTD::move(__ifirst), _VSTD::move(__ilast), 311 _VSTD::move(__ofirst), __unreachable_sentinel(), __iter_move); 312 return _VSTD::move(__result.second); 313 } 314 315 // uninitialized_move_n 316 317 template <class _ValueType, class _InputIterator, class _Size, class _ForwardIterator, class _Sentinel, class _IterMove> 318 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 319 __uninitialized_move_n(_InputIterator __ifirst, _Size __n, 320 _ForwardIterator __ofirst, _Sentinel __olast, _IterMove __iter_move) { 321 auto __idx = __ofirst; 322 #ifndef _LIBCPP_NO_EXCEPTIONS 323 try { 324 #endif 325 for (; __n > 0 && __idx != __olast; ++__idx, (void)++__ifirst, --__n) 326 ::new (_VSTD::__voidify(*__idx)) _ValueType(__iter_move(__ifirst)); 327 #ifndef _LIBCPP_NO_EXCEPTIONS 328 } catch (...) { 329 _VSTD::__destroy(__ofirst, __idx); 330 throw; 331 } 332 #endif 333 334 return {_VSTD::move(__ifirst), _VSTD::move(__idx)}; 335 } 336 337 template <class _InputIterator, class _Size, class _ForwardIterator> 338 inline _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _ForwardIterator> 339 uninitialized_move_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) { 340 using _ValueType = typename iterator_traits<_ForwardIterator>::value_type; 341 auto __iter_move = [](auto&& __iter) -> decltype(auto) { return _VSTD::move(*__iter); }; 342 343 return _VSTD::__uninitialized_move_n<_ValueType>(_VSTD::move(__ifirst), __n, _VSTD::move(__ofirst), 344 __unreachable_sentinel(), __iter_move); 345 } 346 347 #endif // _LIBCPP_STD_VER > 14 348 349 _LIBCPP_END_NAMESPACE_STD 350 351 #endif // _LIBCPP___MEMORY_UNINITIALIZED_ALGORITHMS_H 352