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
37namespace __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//////////////////////////////////////////////////////////////
96template <class _ExecutionPolicy>
97struct __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
109template <class _ExecutionPolicy>
110struct __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
119template <class _ExecutionPolicy>
120struct __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
132template <class _ExecutionPolicy>
133struct __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
147template <class _ExecutionPolicy>
148struct __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
160template <class _ExecutionPolicy>
161struct __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//////////////////////////////////////////////////////////////
182template <class _ExecutionPolicy>
183struct __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
199template <class _ExecutionPolicy>
200struct __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
210template <class _ExecutionPolicy>
211struct __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
227template <class _ExecutionPolicy>
228struct __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
240template <class _ExecutionPolicy>
241struct __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
255template <class _ExecutionPolicy>
256struct __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
266template <class _ExecutionPolicy>
267struct __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//////////////////////////////////////////////////////////////
280template <class _ExecutionPolicy>
281struct __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//////////////////////////////////////////////////////////////
293template <class _ExecutionPolicy>
294struct __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
308template <class _ExecutionPolicy>
309struct __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
321template <class _ExecutionPolicy>
322struct __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
342template <class _ExecutionPolicy>
343struct __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
372template <class _ExecutionPolicy>
373struct __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//////////////////////////////////////////////////////////////
392template <class _ExecutionPolicy>
393struct __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
414template <class _ExecutionPolicy>
415struct __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.
440template <class _ExecutionPolicy>
441struct __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
454template <class _ExecutionPolicy>
455struct __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
465template <class _ExecutionPolicy>
466struct __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
481template <class _ExecutionPolicy>
482struct __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