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#if _LIBCPP_STD_VER >= 17
37
38_LIBCPP_BEGIN_NAMESPACE_STD
39namespace __pstl {
40
41//
42// This file provides an incomplete PSTL backend that implements all of the PSTL algorithms
43// 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 more
46// 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 family
51// --------------
52// - find
53// - find_if_not
54// - any_of
55// - all_of
56// - none_of
57// - is_partitioned
58//
59// for_each family
60// ---------------
61// - for_each_n
62// - fill
63// - fill_n
64// - replace
65// - replace_if
66// - generate
67// - generate_n
68//
69// merge family
70// ------------
71// No other algorithms based on merge
72//
73// stable_sort family
74// ------------------
75// - sort
76//
77// transform_reduce and transform_reduce_binary family
78// ---------------------------------------------------
79// - count_if
80// - count
81// - equal(3 legs)
82// - equal
83// - reduce
84//
85// transform and transform_binary family
86// -------------------------------------
87// - replace_copy_if
88// - replace_copy
89// - move
90// - copy
91// - copy_n
92// - rotate_copy
93//
94
95//////////////////////////////////////////////////////////////
96// find_if family
97//////////////////////////////////////////////////////////////
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), [&](__iter_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, [&](__iter_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 family
183//////////////////////////////////////////////////////////////
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 input
195 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 = __iter_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 input
223 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 = __iter_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 = __iter_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 = __iter_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 = __iter_reference<_ForwardIterator>;
275 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); });
276 }
277};
278
279//////////////////////////////////////////////////////////////
280// stable_sort family
281//////////////////////////////////////////////////////////////
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 family
294//////////////////////////////////////////////////////////////
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<__iter_diff_t<_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 = __iter_diff_t<_ForwardIterator>;
302 using _Ref = __iter_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<__iter_diff_t<_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 = __iter_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 algorithm
359 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 much
364 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 family
393//////////////////////////////////////////////////////////////
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 = __iter_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 = __iter_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::memmove
439// Investigate whether we want to still forward to std::transform(policy)
440// in that case for the execution::par part, or whether we actually want
441// 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::memmove
456template <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 input
478 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 __pstl
501_LIBCPP_END_NAMESPACE_STD
502
503#endif // _LIBCPP_STD_VER >= 17
504
505_LIBCPP_POP_MACROS
506
507#endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H
508