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/find.h>
16#include <__algorithm/find_if.h>
17#include <__algorithm/for_each_n.h>
18#include <__algorithm/is_sorted.h>
19#include <__config>
20#include <__functional/identity.h>
21#include <__functional/not_fn.h>
22#include <__functional/operations.h>
23#include <__iterator/concepts.h>
24#include <__iterator/iterator_traits.h>
25#include <__iterator/next.h>
26#include <__iterator/reverse_iterator.h>
27#include <__pstl/backend_fwd.h>
28#include <__pstl/dispatch.h>
29#include <__type_traits/desugars_to.h>
30#include <__utility/empty.h>
31#include <__utility/forward.h>
32#include <__utility/move.h>
33#include <optional>
34
35#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
36# pragma GCC system_header
37#endif
38
39_LIBCPP_PUSH_MACROS
40#include <__undef_macros>
41
42#if _LIBCPP_STD_VER >= 17
43
44_LIBCPP_BEGIN_NAMESPACE_STD
45namespace __pstl {
46
47//
48// This file provides an incomplete PSTL backend that implements all of the PSTL algorithms
49// based on a smaller set of basis operations.
50//
51// It is intended as a building block for other PSTL backends that implement some operations more
52// efficiently but may not want to define the full set of PSTL algorithms.
53//
54// This backend implements all the PSTL algorithms based on the following basis operations:
55//
56// find_if family
57// --------------
58// - find
59// - find_if_not
60// - any_of
61// - all_of
62// - none_of
63// - is_partitioned
64// - find_first_of
65//
66// for_each family
67// ---------------
68// - for_each_n
69// - fill
70// - fill_n
71// - replace
72// - replace_if
73// - generate
74// - generate_n
75//
76// merge family
77// ------------
78// No other algorithms based on merge
79//
80// stable_sort family
81// ------------------
82// - sort
83//
84// transform_reduce and transform_reduce_binary family
85// ---------------------------------------------------
86// - count_if
87// - count
88// - equal(3 legs)
89// - equal
90// - is_sorted
91// - reduce
92//
93// transform and transform_binary family
94// -------------------------------------
95// - adjacent_difference
96// - copy
97// - copy_n
98// - move
99// - replace_copy
100// - replace_copy_if
101// - reverse_copy
102// - rotate_copy
103//
104
105//////////////////////////////////////////////////////////////
106// find_if family
107//////////////////////////////////////////////////////////////
108template <class _ExecutionPolicy>
109struct __find<__default_backend_tag, _ExecutionPolicy> {
110 template <class _Policy, class _ForwardIterator, class _Tp>
111 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
112 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {
113 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
114 return _FindIf()(
115 __policy, std::move(__first), std::move(__last), [&](__iterator_reference<_ForwardIterator> __element) {
116 return __element == __value;
117 });
118 }
119};
120
121template <class _ExecutionPolicy>
122struct __find_if_not<__default_backend_tag, _ExecutionPolicy> {
123 template <class _Policy, class _ForwardIterator, class _Pred>
124 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
125 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
126 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
127 return _FindIf()(__policy, __first, __last, std::not_fn(std::forward<_Pred>(__pred)));
128 }
129};
130
131template <class _ExecutionPolicy>
132struct __any_of<__default_backend_tag, _ExecutionPolicy> {
133 template <class _Policy, class _ForwardIterator, class _Pred>
134 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
135 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
136 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
137 auto __res = _FindIf()(__policy, __first, __last, std::forward<_Pred>(__pred));
138 if (!__res)
139 return nullopt;
140 return *__res != __last;
141 }
142};
143
144template <class _ExecutionPolicy>
145struct __all_of<__default_backend_tag, _ExecutionPolicy> {
146 template <class _Policy, class _ForwardIterator, class _Pred>
147 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
148 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
149 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
150 auto __res = _AnyOf()(__policy, __first, __last, [&](__iterator_reference<_ForwardIterator> __value) {
151 return !__pred(__value);
152 });
153 if (!__res)
154 return nullopt;
155 return !*__res;
156 }
157};
158
159template <class _ExecutionPolicy>
160struct __none_of<__default_backend_tag, _ExecutionPolicy> {
161 template <class _Policy, class _ForwardIterator, class _Pred>
162 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
163 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
164 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
165 auto __res = _AnyOf()(__policy, __first, __last, std::forward<_Pred>(__pred));
166 if (!__res)
167 return nullopt;
168 return !*__res;
169 }
170};
171
172template <class _ExecutionPolicy>
173struct __is_partitioned<__default_backend_tag, _ExecutionPolicy> {
174 template <class _Policy, class _ForwardIterator, class _Pred>
175 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
176 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
177 using _FindIfNot = __dispatch<__find_if_not, __current_configuration, _ExecutionPolicy>;
178 auto __maybe_first = _FindIfNot()(__policy, std::move(__first), __last, __pred);
179 if (__maybe_first == nullopt)
180 return nullopt;
181
182 __first = *__maybe_first;
183 if (__first == __last)
184 return true;
185 ++__first;
186 using _NoneOf = __dispatch<__none_of, __current_configuration, _ExecutionPolicy>;
187 return _NoneOf()(__policy, std::move(__first), std::move(__last), __pred);
188 }
189};
190
191template <class _ExecutionPolicy>
192struct __find_first_of<__default_backend_tag, _ExecutionPolicy> {
193 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
194 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
195 operator()(_Policy&& __policy,
196 _ForwardIterator1 __first1,
197 _ForwardIterator1 __last1,
198 _ForwardIterator2 __first2,
199 _ForwardIterator2 __last2,
200 _Predicate&& __pred) const noexcept {
201 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
202 using _Ref1 = __iterator_reference<_ForwardIterator1>;
203 using _Ref2 = __iterator_reference<_ForwardIterator2>;
204 return _FindIf()(__policy, std::move(__first1), std::move(__last1), [&](_Ref1 __element) {
205 if constexpr (__desugars_to_v<__equal_tag, _Predicate, _Ref1, _Ref2>) {
206 // bypass an equality predicate and call directly to std::find() to allow more vectorization
207 return std::find(__first2, __last2, __element) != __last2;
208 } else {
209 return std::find_if(__first2, __last2, [&](_Ref2 __value) { return __pred(__element, __value); }) != __last2;
210 }
211 });
212 }
213};
214
215//////////////////////////////////////////////////////////////
216// for_each family
217//////////////////////////////////////////////////////////////
218template <class _ExecutionPolicy>
219struct __for_each_n<__default_backend_tag, _ExecutionPolicy> {
220 template <class _Policy, class _ForwardIterator, class _Size, class _Function>
221 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
222 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) const noexcept {
223 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
224 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
225 _ForwardIterator __last = __first + __size;
226 return _ForEach()(__policy, std::move(__first), std::move(__last), std::move(__func));
227 } else {
228 // Otherwise, use the serial algorithm to avoid doing two passes over the input
229 std::for_each_n(std::move(__first), __size, std::move(__func));
230 return __empty{};
231 }
232 }
233};
234
235template <class _ExecutionPolicy>
236struct __fill<__default_backend_tag, _ExecutionPolicy> {
237 template <class _Policy, class _ForwardIterator, class _Tp>
238 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
239 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
240 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
241 using _Ref = __iterator_reference<_ForwardIterator>;
242 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; });
243 }
244};
245
246template <class _ExecutionPolicy>
247struct __fill_n<__default_backend_tag, _ExecutionPolicy> {
248 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
249 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
250 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept {
251 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
252 using _Fill = __dispatch<__fill, __current_configuration, _ExecutionPolicy>;
253 _ForwardIterator __last = __first + __n;
254 return _Fill()(__policy, std::move(__first), std::move(__last), __value);
255 } else {
256 // Otherwise, use the serial algorithm to avoid doing two passes over the input
257 std::fill_n(std::move(__first), __n, __value);
258 return optional<__empty>{__empty{}};
259 }
260 }
261};
262
263template <class _ExecutionPolicy>
264struct __replace<__default_backend_tag, _ExecutionPolicy> {
265 template <class _Policy, class _ForwardIterator, class _Tp>
266 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
267 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new)
268 const noexcept {
269 using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>;
270 using _Ref = __iterator_reference<_ForwardIterator>;
271 return _ReplaceIf()(
272 __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new);
273 }
274};
275
276template <class _ExecutionPolicy>
277struct __replace_if<__default_backend_tag, _ExecutionPolicy> {
278 template <class _Policy, class _ForwardIterator, class _Pred, class _Tp>
279 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
280 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value)
281 const noexcept {
282 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
283 using _Ref = __iterator_reference<_ForwardIterator>;
284 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {
285 if (__pred(__element))
286 __element = __new_value;
287 });
288 }
289};
290
291template <class _ExecutionPolicy>
292struct __generate<__default_backend_tag, _ExecutionPolicy> {
293 template <class _Policy, class _ForwardIterator, class _Generator>
294 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
295 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept {
296 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
297 using _Ref = __iterator_reference<_ForwardIterator>;
298 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); });
299 }
300};
301
302template <class _ExecutionPolicy>
303struct __generate_n<__default_backend_tag, _ExecutionPolicy> {
304 template <class _Policy, class _ForwardIterator, class _Size, class _Generator>
305 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
306 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept {
307 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
308 using _Ref = __iterator_reference<_ForwardIterator>;
309 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); });
310 }
311};
312
313//////////////////////////////////////////////////////////////
314// stable_sort family
315//////////////////////////////////////////////////////////////
316template <class _ExecutionPolicy>
317struct __sort<__default_backend_tag, _ExecutionPolicy> {
318 template <class _Policy, class _RandomAccessIterator, class _Comp>
319 _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
320 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
321 using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>;
322 return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
323 }
324};
325
326//////////////////////////////////////////////////////////////
327// transform_reduce family
328//////////////////////////////////////////////////////////////
329template <class _ExecutionPolicy>
330struct __count_if<__default_backend_tag, _ExecutionPolicy> {
331 template <class _Policy, class _ForwardIterator, class _Predicate>
332 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>> operator()(
333 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept {
334 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
335 using _DiffT = __iterator_difference_type<_ForwardIterator>;
336 using _Ref = __iterator_reference<_ForwardIterator>;
337 return _TransformReduce()(
338 __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT {
339 return __pred(__element) ? _DiffT(1) : _DiffT(0);
340 });
341 }
342};
343
344template <class _ExecutionPolicy>
345struct __count<__default_backend_tag, _ExecutionPolicy> {
346 template <class _Policy, class _ForwardIterator, class _Tp>
347 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>>
348 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
349 using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>;
350 using _Ref = __iterator_reference<_ForwardIterator>;
351 return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool {
352 return __element == __value;
353 });
354 }
355};
356
357template <class _ExecutionPolicy>
358struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> {
359 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
360 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
361 operator()(_Policy&& __policy,
362 _ForwardIterator1 __first1,
363 _ForwardIterator1 __last1,
364 _ForwardIterator2 __first2,
365 _Predicate&& __pred) const noexcept {
366 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;
367 return _TransformReduce()(
368 __policy,
369 std::move(__first1),
370 std::move(__last1),
371 std::move(__first2),
372 true,
373 std::logical_and{},
374 std::forward<_Predicate>(__pred));
375 }
376};
377
378template <class _ExecutionPolicy>
379struct __equal<__default_backend_tag, _ExecutionPolicy> {
380 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
381 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
382 operator()(_Policy&& __policy,
383 _ForwardIterator1 __first1,
384 _ForwardIterator1 __last1,
385 _ForwardIterator2 __first2,
386 _ForwardIterator2 __last2,
387 _Predicate&& __pred) const noexcept {
388 if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value &&
389 __has_random_access_iterator_category<_ForwardIterator2>::value) {
390 if (__last1 - __first1 != __last2 - __first2)
391 return false;
392 // Fall back to the 3 legged algorithm
393 using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>;
394 return _Equal3Leg()(
395 __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred));
396 } else {
397 // If we don't have random access, fall back to the serial algorithm cause we can't do much
398 return std::equal(
399 std::move(__first1),
400 std::move(__last1),
401 std::move(__first2),
402 std::move(__last2),
403 std::forward<_Predicate>(__pred));
404 }
405 }
406};
407
408template <class _ExecutionPolicy>
409struct __reduce<__default_backend_tag, _ExecutionPolicy> {
410 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation>
411 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp>
412 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op)
413 const noexcept {
414 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
415 return _TransformReduce()(
416 __policy,
417 std::move(__first),
418 std::move(__last),
419 std::move(__init),
420 std::forward<_BinaryOperation>(__op),
421 __identity{});
422 }
423};
424
425template <class _ExecutionPolicy>
426struct __is_sorted<__default_backend_tag, _ExecutionPolicy> {
427 template <class _Policy, class _ForwardIterator, class _Comp>
428 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
429 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept {
430 if constexpr (__has_bidirectional_iterator_category<_ForwardIterator>::value) {
431 if (__first == __last)
432 return true; // Empty, sorted by definition
433 _ForwardIterator __first2 = std::next(__first);
434 if (__first2 == __last)
435 return true; // Only one element, sorted by definition
436 --__last; // Make two iterator ranges: [__first, __first + n - 1) and [__first + 1, __first + n)
437 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;
438 using _Ref = __iterator_reference<_ForwardIterator>;
439 return _TransformReduce()(
440 __policy,
441 std::move(__first),
442 std::move(__last),
443 std::move(__first2),
444 true,
445 std::logical_and{},
446 [&](_Ref __left, _Ref __right) -> bool { return !__comp(__right, __left); });
447 } else {
448 // Currently anything outside bidirectional iterators has to be processed serially
449 return std::is_sorted(std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
450 }
451 }
452};
453
454//////////////////////////////////////////////////////////////
455// transform family
456//////////////////////////////////////////////////////////////
457template <class _ExecutionPolicy>
458struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> {
459 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp>
460 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
461 operator()(_Policy&& __policy,
462 _ForwardIterator __first,
463 _ForwardIterator __last,
464 _ForwardOutIterator __out_it,
465 _Pred&& __pred,
466 _Tp const& __new_value) const noexcept {
467 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
468 using _Ref = __iterator_reference<_ForwardIterator>;
469 auto __res =
470 _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) {
471 return __pred(__element) ? __new_value : __element;
472 });
473 if (__res == nullopt)
474 return nullopt;
475 return __empty{};
476 }
477};
478
479template <class _ExecutionPolicy>
480struct __replace_copy<__default_backend_tag, _ExecutionPolicy> {
481 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp>
482 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
483 operator()(_Policy&& __policy,
484 _ForwardIterator __first,
485 _ForwardIterator __last,
486 _ForwardOutIterator __out_it,
487 _Tp const& __old_value,
488 _Tp const& __new_value) const noexcept {
489 using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>;
490 using _Ref = __iterator_reference<_ForwardIterator>;
491 return _ReplaceCopyIf()(
492 __policy,
493 std::move(__first),
494 std::move(__last),
495 std::move(__out_it),
496 [&](_Ref __element) { return __element == __old_value; },
497 __new_value);
498 }
499};
500
501// TODO: Use the std::copy/move shenanigans to forward to std::memmove
502// Investigate whether we want to still forward to std::transform(policy)
503// in that case for the execution::par part, or whether we actually want
504// to run everything serially in that case.
505template <class _ExecutionPolicy>
506struct __move<__default_backend_tag, _ExecutionPolicy> {
507 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
508 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
509 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
510 const noexcept {
511 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
512 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) {
513 return std::move(__element);
514 });
515 }
516};
517
518// TODO: Use the std::copy/move shenanigans to forward to std::memmove
519template <class _ExecutionPolicy>
520struct __copy<__default_backend_tag, _ExecutionPolicy> {
521 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
522 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
523 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
524 const noexcept {
525 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
526 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity());
527 }
528};
529
530template <class _ExecutionPolicy>
531struct __copy_n<__default_backend_tag, _ExecutionPolicy> {
532 template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator>
533 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
534 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept {
535 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
536 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
537 _ForwardIterator __last = __first + __n;
538 return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it));
539 } else {
540 // Otherwise, use the serial algorithm to avoid doing two passes over the input
541 return std::copy_n(std::move(__first), __n, std::move(__out_it));
542 }
543 }
544};
545
546template <class _ExecutionPolicy>
547struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> {
548 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
549 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
550 operator()(_Policy&& __policy,
551 _ForwardIterator __first,
552 _ForwardIterator __middle,
553 _ForwardIterator __last,
554 _ForwardOutIterator __out_it) const noexcept {
555 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
556 auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it));
557 if (__result_mid == nullopt)
558 return nullopt;
559 return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid));
560 }
561};
562
563template <class _ExecutionPolicy>
564struct __reverse_copy<__default_backend_tag, _ExecutionPolicy> {
565 template <class _Policy, class _BidirectionalIterator, class _ForwardIterator>
566 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
567 operator()(_Policy&& __policy,
568 _BidirectionalIterator __first,
569 _BidirectionalIterator __last,
570 _ForwardIterator __result) const noexcept {
571 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
572 return _Copy()(__policy,
573 std::reverse_iterator<_BidirectionalIterator>(std::move(__last)),
574 std::reverse_iterator<_BidirectionalIterator>(std::move(__first)),
575 std::move(__result));
576 }
577};
578
579template <class _ExecutionPolicy>
580struct __adjacent_difference<__default_backend_tag, _ExecutionPolicy> {
581 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
582 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2>
583 operator()(_Policy&& __policy,
584 _ForwardIterator1 __first1,
585 _ForwardIterator1 __last1,
586 _ForwardIterator2 __result,
587 _BinaryOperation&& __op) const noexcept {
588 using _TransformBinary = __dispatch<__transform_binary, __current_configuration, _ExecutionPolicy>;
589 if (__first1 == __last1)
590 return __result; // edge case: empty input range, just return the output iterator
591 *__result = *__first1;
592 ++__result;
593 _ForwardIterator1 __first2 = std::next(__first1);
594 if (__first2 == __last1)
595 return __result; // edge case: not enough elements to perform adjacent difference, just return the output iterator
596 // Process as a binary transform of two iterator ranges: [__first1 + 1, __last1) and [__first1, __last1 - 1)
597 return _TransformBinary()(
598 __policy,
599 std::move(__first2),
600 std::move(__last1),
601 std::move(__first1),
602 std::move(__result),
603 std::forward<_BinaryOperation>(__op));
604 }
605};
606
607} // namespace __pstl
608_LIBCPP_END_NAMESPACE_STD
609
610#endif // _LIBCPP_STD_VER >= 17
611
612_LIBCPP_POP_MACROS
613
614#endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H
615