1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef _LIBCPP___PSTL_BACKENDS_DEFAULT_H 10 #define _LIBCPP___PSTL_BACKENDS_DEFAULT_H 11 12 #include <__algorithm/copy_n.h> 13 #include <__algorithm/equal.h> 14 #include <__algorithm/fill_n.h> 15 #include <__algorithm/for_each_n.h> 16 #include <__config> 17 #include <__functional/identity.h> 18 #include <__functional/not_fn.h> 19 #include <__functional/operations.h> 20 #include <__iterator/concepts.h> 21 #include <__iterator/iterator_traits.h> 22 #include <__pstl/backend_fwd.h> 23 #include <__pstl/dispatch.h> 24 #include <__utility/empty.h> 25 #include <__utility/forward.h> 26 #include <__utility/move.h> 27 #include <optional> 28 29 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 30 # pragma GCC system_header 31 #endif 32 33 _LIBCPP_PUSH_MACROS 34 #include <__undef_macros> 35 36 _LIBCPP_BEGIN_NAMESPACE_STD 37 namespace __pstl { 38 39 // 40 // This file provides an incomplete PSTL backend that implements all of the PSTL algorithms 41 // based on a smaller set of basis operations. 42 // 43 // It is intended as a building block for other PSTL backends that implement some operations more 44 // efficiently but may not want to define the full set of PSTL algorithms. 45 // 46 // This backend implements all the PSTL algorithms based on the following basis operations: 47 // 48 // find_if family 49 // -------------- 50 // - find 51 // - find_if_not 52 // - any_of 53 // - all_of 54 // - none_of 55 // - is_partitioned 56 // 57 // for_each family 58 // --------------- 59 // - for_each_n 60 // - fill 61 // - fill_n 62 // - replace 63 // - replace_if 64 // - generate 65 // - generate_n 66 // 67 // merge family 68 // ------------ 69 // No other algorithms based on merge 70 // 71 // stable_sort family 72 // ------------------ 73 // - sort 74 // 75 // transform_reduce and transform_reduce_binary family 76 // --------------------------------------------------- 77 // - count_if 78 // - count 79 // - equal(3 legs) 80 // - equal 81 // - reduce 82 // 83 // transform and transform_binary family 84 // ------------------------------------- 85 // - replace_copy_if 86 // - replace_copy 87 // - move 88 // - copy 89 // - copy_n 90 // - rotate_copy 91 // 92 93 ////////////////////////////////////////////////////////////// 94 // find_if family 95 ////////////////////////////////////////////////////////////// 96 template <class _ExecutionPolicy> 97 struct __find<__default_backend_tag, _ExecutionPolicy> { 98 template <class _Policy, class _ForwardIterator, class _Tp> 99 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator> 100 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept { 101 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>; 102 return _FindIf()( 103 __policy, std::move(__first), std::move(__last), [&](__iter_reference<_ForwardIterator> __element) { 104 return __element == __value; 105 }); 106 } 107 }; 108 109 template <class _ExecutionPolicy> 110 struct __find_if_not<__default_backend_tag, _ExecutionPolicy> { 111 template <class _Policy, class _ForwardIterator, class _Pred> 112 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator> 113 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { 114 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>; 115 return _FindIf()(__policy, __first, __last, std::not_fn(std::forward<_Pred>(__pred))); 116 } 117 }; 118 119 template <class _ExecutionPolicy> 120 struct __any_of<__default_backend_tag, _ExecutionPolicy> { 121 template <class _Policy, class _ForwardIterator, class _Pred> 122 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> 123 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { 124 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>; 125 auto __res = _FindIf()(__policy, __first, __last, std::forward<_Pred>(__pred)); 126 if (!__res) 127 return nullopt; 128 return *__res != __last; 129 } 130 }; 131 132 template <class _ExecutionPolicy> 133 struct __all_of<__default_backend_tag, _ExecutionPolicy> { 134 template <class _Policy, class _ForwardIterator, class _Pred> 135 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> 136 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { 137 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>; 138 auto __res = _AnyOf()(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) { 139 return !__pred(__value); 140 }); 141 if (!__res) 142 return nullopt; 143 return !*__res; 144 } 145 }; 146 147 template <class _ExecutionPolicy> 148 struct __none_of<__default_backend_tag, _ExecutionPolicy> { 149 template <class _Policy, class _ForwardIterator, class _Pred> 150 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> 151 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { 152 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>; 153 auto __res = _AnyOf()(__policy, __first, __last, std::forward<_Pred>(__pred)); 154 if (!__res) 155 return nullopt; 156 return !*__res; 157 } 158 }; 159 160 template <class _ExecutionPolicy> 161 struct __is_partitioned<__default_backend_tag, _ExecutionPolicy> { 162 template <class _Policy, class _ForwardIterator, class _Pred> 163 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> 164 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept { 165 using _FindIfNot = __dispatch<__find_if_not, __current_configuration, _ExecutionPolicy>; 166 auto __maybe_first = _FindIfNot()(__policy, std::move(__first), std::move(__last), __pred); 167 if (__maybe_first == nullopt) 168 return nullopt; 169 170 __first = *__maybe_first; 171 if (__first == __last) 172 return true; 173 ++__first; 174 using _NoneOf = __dispatch<__none_of, __current_configuration, _ExecutionPolicy>; 175 return _NoneOf()(__policy, std::move(__first), std::move(__last), __pred); 176 } 177 }; 178 179 ////////////////////////////////////////////////////////////// 180 // for_each family 181 ////////////////////////////////////////////////////////////// 182 template <class _ExecutionPolicy> 183 struct __for_each_n<__default_backend_tag, _ExecutionPolicy> { 184 template <class _Policy, class _ForwardIterator, class _Size, class _Function> 185 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> 186 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) const noexcept { 187 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { 188 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>; 189 _ForwardIterator __last = __first + __size; 190 return _ForEach()(__policy, std::move(__first), std::move(__last), std::move(__func)); 191 } else { 192 // Otherwise, use the serial algorithm to avoid doing two passes over the input 193 std::for_each_n(std::move(__first), __size, std::move(__func)); 194 return __empty{}; 195 } 196 } 197 }; 198 199 template <class _ExecutionPolicy> 200 struct __fill<__default_backend_tag, _ExecutionPolicy> { 201 template <class _Policy, class _ForwardIterator, class _Tp> 202 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> 203 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept { 204 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>; 205 using _Ref = __iter_reference<_ForwardIterator>; 206 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; }); 207 } 208 }; 209 210 template <class _ExecutionPolicy> 211 struct __fill_n<__default_backend_tag, _ExecutionPolicy> { 212 template <class _Policy, class _ForwardIterator, class _Size, class _Tp> 213 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> 214 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept { 215 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { 216 using _Fill = __dispatch<__fill, __current_configuration, _ExecutionPolicy>; 217 _ForwardIterator __last = __first + __n; 218 return _Fill()(__policy, std::move(__first), std::move(__last), __value); 219 } else { 220 // Otherwise, use the serial algorithm to avoid doing two passes over the input 221 std::fill_n(std::move(__first), __n, __value); 222 return optional<__empty>{__empty{}}; 223 } 224 } 225 }; 226 227 template <class _ExecutionPolicy> 228 struct __replace<__default_backend_tag, _ExecutionPolicy> { 229 template <class _Policy, class _ForwardIterator, class _Tp> 230 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> 231 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new) 232 const noexcept { 233 using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>; 234 using _Ref = __iter_reference<_ForwardIterator>; 235 return _ReplaceIf()( 236 __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new); 237 } 238 }; 239 240 template <class _ExecutionPolicy> 241 struct __replace_if<__default_backend_tag, _ExecutionPolicy> { 242 template <class _Policy, class _ForwardIterator, class _Pred, class _Tp> 243 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()( 244 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value) 245 const noexcept { 246 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>; 247 using _Ref = __iter_reference<_ForwardIterator>; 248 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { 249 if (__pred(__element)) 250 __element = __new_value; 251 }); 252 } 253 }; 254 255 template <class _ExecutionPolicy> 256 struct __generate<__default_backend_tag, _ExecutionPolicy> { 257 template <class _Policy, class _ForwardIterator, class _Generator> 258 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> 259 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept { 260 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>; 261 using _Ref = __iter_reference<_ForwardIterator>; 262 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); }); 263 } 264 }; 265 266 template <class _ExecutionPolicy> 267 struct __generate_n<__default_backend_tag, _ExecutionPolicy> { 268 template <class _Policy, class _ForwardIterator, class _Size, class _Generator> 269 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> 270 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept { 271 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>; 272 using _Ref = __iter_reference<_ForwardIterator>; 273 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); }); 274 } 275 }; 276 277 ////////////////////////////////////////////////////////////// 278 // stable_sort family 279 ////////////////////////////////////////////////////////////// 280 template <class _ExecutionPolicy> 281 struct __sort<__default_backend_tag, _ExecutionPolicy> { 282 template <class _Policy, class _RandomAccessIterator, class _Comp> 283 _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()( 284 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept { 285 using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>; 286 return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp)); 287 } 288 }; 289 290 ////////////////////////////////////////////////////////////// 291 // transform_reduce family 292 ////////////////////////////////////////////////////////////// 293 template <class _ExecutionPolicy> 294 struct __count_if<__default_backend_tag, _ExecutionPolicy> { 295 template <class _Policy, class _ForwardIterator, class _Predicate> 296 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iter_diff_t<_ForwardIterator>> operator()( 297 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept { 298 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>; 299 using _DiffT = __iter_diff_t<_ForwardIterator>; 300 using _Ref = __iter_reference<_ForwardIterator>; 301 return _TransformReduce()( 302 __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT { 303 return __pred(__element) ? _DiffT(1) : _DiffT(0); 304 }); 305 } 306 }; 307 308 template <class _ExecutionPolicy> 309 struct __count<__default_backend_tag, _ExecutionPolicy> { 310 template <class _Policy, class _ForwardIterator, class _Tp> 311 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iter_diff_t<_ForwardIterator>> 312 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept { 313 using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>; 314 using _Ref = __iter_reference<_ForwardIterator>; 315 return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool { 316 return __element == __value; 317 }); 318 } 319 }; 320 321 template <class _ExecutionPolicy> 322 struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> { 323 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate> 324 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> 325 operator()(_Policy&& __policy, 326 _ForwardIterator1 __first1, 327 _ForwardIterator1 __last1, 328 _ForwardIterator2 __first2, 329 _Predicate&& __pred) const noexcept { 330 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>; 331 return _TransformReduce()( 332 __policy, 333 std::move(__first1), 334 std::move(__last1), 335 std::move(__first2), 336 true, 337 std::logical_and{}, 338 std::forward<_Predicate>(__pred)); 339 } 340 }; 341 342 template <class _ExecutionPolicy> 343 struct __equal<__default_backend_tag, _ExecutionPolicy> { 344 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate> 345 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> 346 operator()(_Policy&& __policy, 347 _ForwardIterator1 __first1, 348 _ForwardIterator1 __last1, 349 _ForwardIterator2 __first2, 350 _ForwardIterator2 __last2, 351 _Predicate&& __pred) const noexcept { 352 if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value && 353 __has_random_access_iterator_category<_ForwardIterator2>::value) { 354 if (__last1 - __first1 != __last2 - __first2) 355 return false; 356 // Fall back to the 3 legged algorithm 357 using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>; 358 return _Equal3Leg()( 359 __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred)); 360 } else { 361 // If we don't have random access, fall back to the serial algorithm cause we can't do much 362 return std::equal( 363 std::move(__first1), 364 std::move(__last1), 365 std::move(__first2), 366 std::move(__last2), 367 std::forward<_Predicate>(__pred)); 368 } 369 } 370 }; 371 372 template <class _ExecutionPolicy> 373 struct __reduce<__default_backend_tag, _ExecutionPolicy> { 374 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation> 375 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp> 376 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op) 377 const noexcept { 378 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>; 379 return _TransformReduce()( 380 __policy, 381 std::move(__first), 382 std::move(__last), 383 std::move(__init), 384 std::forward<_BinaryOperation>(__op), 385 __identity{}); 386 } 387 }; 388 389 ////////////////////////////////////////////////////////////// 390 // transform family 391 ////////////////////////////////////////////////////////////// 392 template <class _ExecutionPolicy> 393 struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> { 394 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp> 395 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> 396 operator()(_Policy&& __policy, 397 _ForwardIterator __first, 398 _ForwardIterator __last, 399 _ForwardOutIterator __out_it, 400 _Pred&& __pred, 401 _Tp const& __new_value) const noexcept { 402 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>; 403 using _Ref = __iter_reference<_ForwardIterator>; 404 auto __res = 405 _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) { 406 return __pred(__element) ? __new_value : __element; 407 }); 408 if (__res == nullopt) 409 return nullopt; 410 return __empty{}; 411 } 412 }; 413 414 template <class _ExecutionPolicy> 415 struct __replace_copy<__default_backend_tag, _ExecutionPolicy> { 416 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp> 417 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> 418 operator()(_Policy&& __policy, 419 _ForwardIterator __first, 420 _ForwardIterator __last, 421 _ForwardOutIterator __out_it, 422 _Tp const& __old_value, 423 _Tp const& __new_value) const noexcept { 424 using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>; 425 using _Ref = __iter_reference<_ForwardIterator>; 426 return _ReplaceCopyIf()( 427 __policy, 428 std::move(__first), 429 std::move(__last), 430 std::move(__out_it), 431 [&](_Ref __element) { return __element == __old_value; }, 432 __new_value); 433 } 434 }; 435 436 // TODO: Use the std::copy/move shenanigans to forward to std::memmove 437 // Investigate whether we want to still forward to std::transform(policy) 438 // in that case for the execution::par part, or whether we actually want 439 // to run everything serially in that case. 440 template <class _ExecutionPolicy> 441 struct __move<__default_backend_tag, _ExecutionPolicy> { 442 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> 443 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> 444 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it) 445 const noexcept { 446 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>; 447 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) { 448 return std::move(__element); 449 }); 450 } 451 }; 452 453 // TODO: Use the std::copy/move shenanigans to forward to std::memmove 454 template <class _ExecutionPolicy> 455 struct __copy<__default_backend_tag, _ExecutionPolicy> { 456 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> 457 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> 458 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it) 459 const noexcept { 460 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>; 461 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity()); 462 } 463 }; 464 465 template <class _ExecutionPolicy> 466 struct __copy_n<__default_backend_tag, _ExecutionPolicy> { 467 template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator> 468 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> 469 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept { 470 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) { 471 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>; 472 _ForwardIterator __last = __first + __n; 473 return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it)); 474 } else { 475 // Otherwise, use the serial algorithm to avoid doing two passes over the input 476 return std::copy_n(std::move(__first), __n, std::move(__out_it)); 477 } 478 } 479 }; 480 481 template <class _ExecutionPolicy> 482 struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> { 483 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator> 484 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> 485 operator()(_Policy&& __policy, 486 _ForwardIterator __first, 487 _ForwardIterator __middle, 488 _ForwardIterator __last, 489 _ForwardOutIterator __out_it) const noexcept { 490 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>; 491 auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it)); 492 if (__result_mid == nullopt) 493 return nullopt; 494 return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid)); 495 } 496 }; 497 498 } // namespace __pstl 499 _LIBCPP_END_NAMESPACE_STD 500 501 _LIBCPP_POP_MACROS 502 503 #endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H 504