508 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___PSTL_BACKENDS_DEFAULT_H10#define _LIBCPP___PSTL_BACKENDS_DEFAULT_H11 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_header31#endif32 33_LIBCPP_PUSH_MACROS34#include <__undef_macros>35 36#if _LIBCPP_STD_VER >= 1737 38_LIBCPP_BEGIN_NAMESPACE_STD39namespace __pstl {40 41//42// This file provides an incomplete PSTL backend that implements all of the PSTL algorithms43// based on a smaller set of basis operations.44//45// It is intended as a building block for other PSTL backends that implement some operations more46// efficiently but may not want to define the full set of PSTL algorithms.47//48// This backend implements all the PSTL algorithms based on the following basis operations:49//50// find_if family51// --------------52// - find53// - find_if_not54// - any_of55// - all_of56// - none_of57// - is_partitioned58//59// for_each family60// ---------------61// - for_each_n62// - fill63// - fill_n64// - replace65// - replace_if66// - generate67// - generate_n68//69// merge family70// ------------71// No other algorithms based on merge72//73// stable_sort family74// ------------------75// - sort76//77// transform_reduce and transform_reduce_binary family78// ---------------------------------------------------79// - count_if80// - count81// - equal(3 legs)82// - equal83// - reduce84//85// transform and transform_binary family86// -------------------------------------87// - replace_copy_if88// - replace_copy89// - move90// - copy91// - copy_n92// - rotate_copy93//94 95//////////////////////////////////////////////////////////////96// find_if family97//////////////////////////////////////////////////////////////98template <class _ExecutionPolicy>99struct __find<__default_backend_tag, _ExecutionPolicy> {100 template <class _Policy, class _ForwardIterator, class _Tp>101 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>102 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {103 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;104 return _FindIf()(105 __policy, std::move(__first), std::move(__last), [&](__iterator_reference<_ForwardIterator> __element) {106 return __element == __value;107 });108 }109};110 111template <class _ExecutionPolicy>112struct __find_if_not<__default_backend_tag, _ExecutionPolicy> {113 template <class _Policy, class _ForwardIterator, class _Pred>114 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>115 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {116 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;117 return _FindIf()(__policy, __first, __last, std::not_fn(std::forward<_Pred>(__pred)));118 }119};120 121template <class _ExecutionPolicy>122struct __any_of<__default_backend_tag, _ExecutionPolicy> {123 template <class _Policy, class _ForwardIterator, class _Pred>124 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>125 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {126 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;127 auto __res = _FindIf()(__policy, __first, __last, std::forward<_Pred>(__pred));128 if (!__res)129 return nullopt;130 return *__res != __last;131 }132};133 134template <class _ExecutionPolicy>135struct __all_of<__default_backend_tag, _ExecutionPolicy> {136 template <class _Policy, class _ForwardIterator, class _Pred>137 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>138 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {139 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;140 auto __res = _AnyOf()(__policy, __first, __last, [&](__iterator_reference<_ForwardIterator> __value) {141 return !__pred(__value);142 });143 if (!__res)144 return nullopt;145 return !*__res;146 }147};148 149template <class _ExecutionPolicy>150struct __none_of<__default_backend_tag, _ExecutionPolicy> {151 template <class _Policy, class _ForwardIterator, class _Pred>152 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>153 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {154 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;155 auto __res = _AnyOf()(__policy, __first, __last, std::forward<_Pred>(__pred));156 if (!__res)157 return nullopt;158 return !*__res;159 }160};161 162template <class _ExecutionPolicy>163struct __is_partitioned<__default_backend_tag, _ExecutionPolicy> {164 template <class _Policy, class _ForwardIterator, class _Pred>165 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>166 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {167 using _FindIfNot = __dispatch<__find_if_not, __current_configuration, _ExecutionPolicy>;168 auto __maybe_first = _FindIfNot()(__policy, std::move(__first), __last, __pred);169 if (__maybe_first == nullopt)170 return nullopt;171 172 __first = *__maybe_first;173 if (__first == __last)174 return true;175 ++__first;176 using _NoneOf = __dispatch<__none_of, __current_configuration, _ExecutionPolicy>;177 return _NoneOf()(__policy, std::move(__first), std::move(__last), __pred);178 }179};180 181//////////////////////////////////////////////////////////////182// for_each family183//////////////////////////////////////////////////////////////184template <class _ExecutionPolicy>185struct __for_each_n<__default_backend_tag, _ExecutionPolicy> {186 template <class _Policy, class _ForwardIterator, class _Size, class _Function>187 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>188 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) const noexcept {189 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {190 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;191 _ForwardIterator __last = __first + __size;192 return _ForEach()(__policy, std::move(__first), std::move(__last), std::move(__func));193 } else {194 // Otherwise, use the serial algorithm to avoid doing two passes over the input195 std::for_each_n(std::move(__first), __size, std::move(__func));196 return __empty{};197 }198 }199};200 201template <class _ExecutionPolicy>202struct __fill<__default_backend_tag, _ExecutionPolicy> {203 template <class _Policy, class _ForwardIterator, class _Tp>204 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>205 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {206 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;207 using _Ref = __iterator_reference<_ForwardIterator>;208 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; });209 }210};211 212template <class _ExecutionPolicy>213struct __fill_n<__default_backend_tag, _ExecutionPolicy> {214 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>215 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>216 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept {217 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {218 using _Fill = __dispatch<__fill, __current_configuration, _ExecutionPolicy>;219 _ForwardIterator __last = __first + __n;220 return _Fill()(__policy, std::move(__first), std::move(__last), __value);221 } else {222 // Otherwise, use the serial algorithm to avoid doing two passes over the input223 std::fill_n(std::move(__first), __n, __value);224 return optional<__empty>{__empty{}};225 }226 }227};228 229template <class _ExecutionPolicy>230struct __replace<__default_backend_tag, _ExecutionPolicy> {231 template <class _Policy, class _ForwardIterator, class _Tp>232 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>233 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new)234 const noexcept {235 using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>;236 using _Ref = __iterator_reference<_ForwardIterator>;237 return _ReplaceIf()(238 __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new);239 }240};241 242template <class _ExecutionPolicy>243struct __replace_if<__default_backend_tag, _ExecutionPolicy> {244 template <class _Policy, class _ForwardIterator, class _Pred, class _Tp>245 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(246 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value)247 const noexcept {248 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;249 using _Ref = __iterator_reference<_ForwardIterator>;250 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {251 if (__pred(__element))252 __element = __new_value;253 });254 }255};256 257template <class _ExecutionPolicy>258struct __generate<__default_backend_tag, _ExecutionPolicy> {259 template <class _Policy, class _ForwardIterator, class _Generator>260 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>261 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept {262 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;263 using _Ref = __iterator_reference<_ForwardIterator>;264 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); });265 }266};267 268template <class _ExecutionPolicy>269struct __generate_n<__default_backend_tag, _ExecutionPolicy> {270 template <class _Policy, class _ForwardIterator, class _Size, class _Generator>271 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>272 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept {273 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;274 using _Ref = __iterator_reference<_ForwardIterator>;275 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); });276 }277};278 279//////////////////////////////////////////////////////////////280// stable_sort family281//////////////////////////////////////////////////////////////282template <class _ExecutionPolicy>283struct __sort<__default_backend_tag, _ExecutionPolicy> {284 template <class _Policy, class _RandomAccessIterator, class _Comp>285 _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(286 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {287 using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>;288 return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp));289 }290};291 292//////////////////////////////////////////////////////////////293// transform_reduce family294//////////////////////////////////////////////////////////////295template <class _ExecutionPolicy>296struct __count_if<__default_backend_tag, _ExecutionPolicy> {297 template <class _Policy, class _ForwardIterator, class _Predicate>298 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>> operator()(299 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept {300 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;301 using _DiffT = __iterator_difference_type<_ForwardIterator>;302 using _Ref = __iterator_reference<_ForwardIterator>;303 return _TransformReduce()(304 __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT {305 return __pred(__element) ? _DiffT(1) : _DiffT(0);306 });307 }308};309 310template <class _ExecutionPolicy>311struct __count<__default_backend_tag, _ExecutionPolicy> {312 template <class _Policy, class _ForwardIterator, class _Tp>313 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>>314 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {315 using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>;316 using _Ref = __iterator_reference<_ForwardIterator>;317 return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool {318 return __element == __value;319 });320 }321};322 323template <class _ExecutionPolicy>324struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> {325 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>326 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>327 operator()(_Policy&& __policy,328 _ForwardIterator1 __first1,329 _ForwardIterator1 __last1,330 _ForwardIterator2 __first2,331 _Predicate&& __pred) const noexcept {332 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;333 return _TransformReduce()(334 __policy,335 std::move(__first1),336 std::move(__last1),337 std::move(__first2),338 true,339 std::logical_and{},340 std::forward<_Predicate>(__pred));341 }342};343 344template <class _ExecutionPolicy>345struct __equal<__default_backend_tag, _ExecutionPolicy> {346 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>347 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>348 operator()(_Policy&& __policy,349 _ForwardIterator1 __first1,350 _ForwardIterator1 __last1,351 _ForwardIterator2 __first2,352 _ForwardIterator2 __last2,353 _Predicate&& __pred) const noexcept {354 if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value &&355 __has_random_access_iterator_category<_ForwardIterator2>::value) {356 if (__last1 - __first1 != __last2 - __first2)357 return false;358 // Fall back to the 3 legged algorithm359 using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>;360 return _Equal3Leg()(361 __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred));362 } else {363 // If we don't have random access, fall back to the serial algorithm cause we can't do much364 return std::equal(365 std::move(__first1),366 std::move(__last1),367 std::move(__first2),368 std::move(__last2),369 std::forward<_Predicate>(__pred));370 }371 }372};373 374template <class _ExecutionPolicy>375struct __reduce<__default_backend_tag, _ExecutionPolicy> {376 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation>377 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp>378 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op)379 const noexcept {380 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;381 return _TransformReduce()(382 __policy,383 std::move(__first),384 std::move(__last),385 std::move(__init),386 std::forward<_BinaryOperation>(__op),387 __identity{});388 }389};390 391//////////////////////////////////////////////////////////////392// transform family393//////////////////////////////////////////////////////////////394template <class _ExecutionPolicy>395struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> {396 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp>397 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>398 operator()(_Policy&& __policy,399 _ForwardIterator __first,400 _ForwardIterator __last,401 _ForwardOutIterator __out_it,402 _Pred&& __pred,403 _Tp const& __new_value) const noexcept {404 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;405 using _Ref = __iterator_reference<_ForwardIterator>;406 auto __res =407 _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) {408 return __pred(__element) ? __new_value : __element;409 });410 if (__res == nullopt)411 return nullopt;412 return __empty{};413 }414};415 416template <class _ExecutionPolicy>417struct __replace_copy<__default_backend_tag, _ExecutionPolicy> {418 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp>419 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>420 operator()(_Policy&& __policy,421 _ForwardIterator __first,422 _ForwardIterator __last,423 _ForwardOutIterator __out_it,424 _Tp const& __old_value,425 _Tp const& __new_value) const noexcept {426 using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>;427 using _Ref = __iterator_reference<_ForwardIterator>;428 return _ReplaceCopyIf()(429 __policy,430 std::move(__first),431 std::move(__last),432 std::move(__out_it),433 [&](_Ref __element) { return __element == __old_value; },434 __new_value);435 }436};437 438// TODO: Use the std::copy/move shenanigans to forward to std::memmove439// Investigate whether we want to still forward to std::transform(policy)440// in that case for the execution::par part, or whether we actually want441// to run everything serially in that case.442template <class _ExecutionPolicy>443struct __move<__default_backend_tag, _ExecutionPolicy> {444 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>445 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>446 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)447 const noexcept {448 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;449 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) {450 return std::move(__element);451 });452 }453};454 455// TODO: Use the std::copy/move shenanigans to forward to std::memmove456template <class _ExecutionPolicy>457struct __copy<__default_backend_tag, _ExecutionPolicy> {458 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>459 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>460 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)461 const noexcept {462 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;463 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity());464 }465};466 467template <class _ExecutionPolicy>468struct __copy_n<__default_backend_tag, _ExecutionPolicy> {469 template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator>470 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>471 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept {472 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {473 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;474 _ForwardIterator __last = __first + __n;475 return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it));476 } else {477 // Otherwise, use the serial algorithm to avoid doing two passes over the input478 return std::copy_n(std::move(__first), __n, std::move(__out_it));479 }480 }481};482 483template <class _ExecutionPolicy>484struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> {485 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>486 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>487 operator()(_Policy&& __policy,488 _ForwardIterator __first,489 _ForwardIterator __middle,490 _ForwardIterator __last,491 _ForwardOutIterator __out_it) const noexcept {492 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;493 auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it));494 if (__result_mid == nullopt)495 return nullopt;496 return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid));497 }498};499 500} // namespace __pstl501_LIBCPP_END_NAMESPACE_STD502 503#endif // _LIBCPP_STD_VER >= 17504 505_LIBCPP_POP_MACROS506 507#endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H508