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/adjacent_find.h>
13#include <__algorithm/copy_n.h>
14#include <__algorithm/equal.h>
15#include <__algorithm/fill_n.h>
16#include <__algorithm/find.h>
17#include <__algorithm/find_if.h>
18#include <__algorithm/for_each_n.h>
19#include <__algorithm/is_sorted.h>
20#include <__algorithm/mismatch.h>
21#include <__config>
22#include <__functional/identity.h>
23#include <__functional/not_fn.h>
24#include <__functional/operations.h>
25#include <__iterator/concepts.h>
26#include <__iterator/iterator_traits.h>
27#include <__iterator/next.h>
28#include <__iterator/prev.h>
29#include <__iterator/reverse_iterator.h>
30#include <__memory/addressof.h>
31#include <__memory/construct_at.h>
32#include <__memory/uninitialized_algorithms.h>
33#include <__optional/comparison.h>
34#include <__optional/nullopt_t.h>
35#include <__optional/optional.h>
36#include <__pstl/backend_fwd.h>
37#include <__pstl/dispatch.h>
38#include <__type_traits/desugars_to.h>
39#include <__utility/empty.h>
40#include <__utility/forward.h>
41#include <__utility/move.h>
42
43#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
44# pragma GCC system_header
45#endif
46
47_LIBCPP_PUSH_MACROS
48#include <__undef_macros>
49
50#if _LIBCPP_STD_VER >= 17
51
52_LIBCPP_BEGIN_NAMESPACE_STD
53namespace __pstl {
54
55//
56// This file provides an incomplete PSTL backend that implements all of the PSTL algorithms
57// based on a smaller set of basis operations.
58//
59// It is intended as a building block for other PSTL backends that implement some operations more
60// efficiently but may not want to define the full set of PSTL algorithms.
61//
62// This backend implements all the PSTL algorithms based on the following basis operations:
63//
64// find_end family
65// ------------------
66// No other algorithms based on find_end
67//
68// is_heap_until family
69// --------------
70// - is_heap
71//
72// find_if family
73// --------------
74// - find
75// - find_if_not
76// - any_of
77// - all_of
78// - none_of
79// - is_partitioned
80// - find_first_of
81//
82// min_element family
83// ---------------
84// - max_element
85//
86// minmax_element family
87// -------------------
88// No other algorithms based on minmax_element
89//
90// mismatch family
91// ---------------
92// - adjacent_find
93// - is_sorted
94// - is_sorted_until
95// - lexicographical_compare
96// - mismatch_3leg
97//
98// for_each family
99// ---------------
100// - destroy
101// - destroy_n
102// - for_each_n
103// - fill
104// - fill_n
105// - replace
106// - replace_if
107// - generate
108// - generate_n
109// - uninitialized_default_construct
110// - uninitialized_default_construct_n
111// - uninitialized_value_construct
112// - uninitialized_value_construct_n
113// - uninitialized_fill
114// - uninitialized_fill_n
115//
116// merge family
117// ------------
118// No other algorithms based on merge
119//
120// reverse family
121// ------------
122// No other algorithms based on reverse
123//
124// search family
125// ------------
126// No other algorithms based on search
127//
128// search_n family
129// ------------------
130// No other algorithms based on search_n
131//
132// stable_sort family
133// ------------------
134// - sort
135//
136// swap_ranges family
137// ------------
138// No other algorithms based on swap_ranges
139//
140// transform_reduce and transform_reduce_binary family
141// ---------------------------------------------------
142// - count_if
143// - count
144// - equal(3 legs)
145// - equal
146// - reduce
147//
148// transform and transform_binary family
149// -------------------------------------
150// - adjacent_difference
151// - copy
152// - copy_n
153// - move
154// - replace_copy
155// - replace_copy_if
156// - reverse_copy
157// - rotate_copy
158//
159// uninitialized_copy family
160// -------------------------------------
161// - uninitialized_copy_n
162//
163// uninitialized_move family
164// -------------------------------------
165// - uninitialized_move_n
166//
167// transform_inclusive_scan_init family
168// -------------------------------------
169// - __inclusive_scan
170// - __inclusive_scan_init
171// - __transform_inclusive_scan
172//
173
174//////////////////////////////////////////////////////////////
175// find_if family
176//////////////////////////////////////////////////////////////
177template <class _ExecutionPolicy>
178struct __find<__default_backend_tag, _ExecutionPolicy> {
179 template <class _Policy, class _ForwardIterator, class _Tp>
180 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
181 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {
182 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
183 return _FindIf()(
184 __policy, std::move(__first), std::move(__last), [&](__iterator_reference<_ForwardIterator> __element) {
185 return __element == __value;
186 });
187 }
188};
189
190template <class _ExecutionPolicy>
191struct __find_if_not<__default_backend_tag, _ExecutionPolicy> {
192 template <class _Policy, class _ForwardIterator, class _Pred>
193 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
194 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
195 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
196 return _FindIf()(__policy, __first, __last, std::not_fn(std::forward<_Pred>(__pred)));
197 }
198};
199
200template <class _ExecutionPolicy>
201struct __any_of<__default_backend_tag, _ExecutionPolicy> {
202 template <class _Policy, class _ForwardIterator, class _Pred>
203 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
204 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
205 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
206 auto __res = _FindIf()(__policy, __first, __last, std::forward<_Pred>(__pred));
207 if (!__res)
208 return nullopt;
209 return *__res != __last;
210 }
211};
212
213template <class _ExecutionPolicy>
214struct __all_of<__default_backend_tag, _ExecutionPolicy> {
215 template <class _Policy, class _ForwardIterator, class _Pred>
216 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
217 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
218 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
219 auto __res = _AnyOf()(__policy, __first, __last, [&](__iterator_reference<_ForwardIterator> __value) {
220 return !__pred(__value);
221 });
222 if (!__res)
223 return nullopt;
224 return !*__res;
225 }
226};
227
228template <class _ExecutionPolicy>
229struct __none_of<__default_backend_tag, _ExecutionPolicy> {
230 template <class _Policy, class _ForwardIterator, class _Pred>
231 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
232 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
233 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
234 auto __res = _AnyOf()(__policy, __first, __last, std::forward<_Pred>(__pred));
235 if (!__res)
236 return nullopt;
237 return !*__res;
238 }
239};
240
241template <class _ExecutionPolicy>
242struct __is_partitioned<__default_backend_tag, _ExecutionPolicy> {
243 template <class _Policy, class _ForwardIterator, class _Pred>
244 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
245 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
246 using _FindIfNot = __dispatch<__find_if_not, __current_configuration, _ExecutionPolicy>;
247 auto __maybe_first = _FindIfNot()(__policy, std::move(__first), __last, __pred);
248 if (__maybe_first == nullopt)
249 return nullopt;
250
251 __first = *__maybe_first;
252 if (__first == __last)
253 return true;
254 ++__first;
255 using _NoneOf = __dispatch<__none_of, __current_configuration, _ExecutionPolicy>;
256 return _NoneOf()(__policy, std::move(__first), std::move(__last), __pred);
257 }
258};
259
260template <class _ExecutionPolicy>
261struct __find_first_of<__default_backend_tag, _ExecutionPolicy> {
262 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
263 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
264 operator()(_Policy&& __policy,
265 _ForwardIterator1 __first1,
266 _ForwardIterator1 __last1,
267 _ForwardIterator2 __first2,
268 _ForwardIterator2 __last2,
269 _Predicate&& __pred) const noexcept {
270 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
271 using _Ref1 = __iterator_reference<_ForwardIterator1>;
272 using _Ref2 = __iterator_reference<_ForwardIterator2>;
273 return _FindIf()(__policy, std::move(__first1), std::move(__last1), [&](_Ref1 __element) {
274 if constexpr (__desugars_to_v<__equal_tag, _Predicate, _Ref1, _Ref2>) {
275 // bypass an equality predicate and call directly to std::find() to allow more vectorization
276 return std::find(__first2, __last2, __element) != __last2;
277 } else {
278 return std::find_if(__first2, __last2, [&](_Ref2 __value) { return __pred(__element, __value); }) != __last2;
279 }
280 });
281 }
282};
283
284//////////////////////////////////////////////////////////////
285// min_element family
286//////////////////////////////////////////////////////////////
287
288template <class _ExecutionPolicy>
289struct __max_element<__default_backend_tag, _ExecutionPolicy> {
290 template <class _Policy, class _ForwardIterator, class _Compare>
291 optional<_ForwardIterator>
292 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) const noexcept {
293 using _MinElement = __dispatch<__min_element, __current_configuration, _ExecutionPolicy>;
294 using _Ref = __iterator_reference<_ForwardIterator>;
295 // Express max_element via min_element by replacing the comparison
296 // "lhs OP rhs" with "rhs OP lhs".
297 return _MinElement()(
298 __policy, std::move(__first), std::move(__last), [__comp = std::move(__comp)](_Ref __lhs, _Ref __rhs) {
299 return __comp(__rhs, __lhs);
300 });
301 }
302};
303
304//////////////////////////////////////////////////////////////
305// mismatch family
306//////////////////////////////////////////////////////////////
307
308template <class _ExecutionPolicy>
309struct __lexicographical_compare<__default_backend_tag, _ExecutionPolicy> {
310 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Comp>
311 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
312 operator()(_Policy&& __policy,
313 _ForwardIterator1 __first1,
314 _ForwardIterator1 __last1,
315 _ForwardIterator2 __first2,
316 _ForwardIterator2 __last2,
317 _Comp __comp) const noexcept {
318 using _Mismatch = __dispatch<__mismatch, __current_configuration, _ExecutionPolicy>;
319 using _Ref1 = __iterator_reference<_ForwardIterator1>;
320 using _Ref2 = __iterator_reference<_ForwardIterator2>;
321 // find the first pair of elements that are not equal, or the end of one or both of the ranges
322 auto __res = _Mismatch()(__policy, __first1, __last1, __first2, __last2, [&](_Ref1 __lhs, _Ref2 __rhs) {
323 return !__comp(__lhs, __rhs) && !__comp(__rhs, __lhs); // derive equality from the less-than predicate
324 });
325 if (!__res) // if the underlying mismatch operation failed, return nullopt
326 return nullopt;
327 if (__res->first == __last1) // the first range is exhausted,
328 return __res->second != __last2; // it is lexicographically less if the second range is not exhausted.
329 if (__res->second == __last2) // the second range is exhausted,
330 return false; // the first range is not exhausted, so it is not lexicographically less.
331 return __comp(*__res->first, *__res->second); // otherwise, compare the first pair of non-equal elements
332 }
333};
334
335template <class _ExecutionPolicy>
336struct __mismatch_3leg<__default_backend_tag, _ExecutionPolicy> {
337 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Comp>
338 optional<pair<_ForwardIterator1, _ForwardIterator2>>
339 operator()(_Policy&& __policy,
340 _ForwardIterator1 __first1,
341 _ForwardIterator1 __last1,
342 _ForwardIterator2 __first2,
343 _Comp __comp) const noexcept {
344 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
345 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
346 // Forward to the 4-legged version of mismatch.
347 using _Mismatch = __dispatch<__mismatch, __current_configuration, _ExecutionPolicy>;
348 _ForwardIterator2 __last2 = __first2 + (__last1 - __first1);
349 return _Mismatch()(
350 __policy,
351 std::move(__first1),
352 std::move(__last1),
353 std::move(__first2),
354 std::move(__last2),
355 std::move(__comp));
356 } else {
357 // Currently only random access iterators are supported for parallel mismatch_3leg.
358 return std::mismatch(std::move(__first1), std::move(__last1), std::move(__first2), std::move(__comp));
359 }
360 }
361};
362
363template <class _ExecutionPolicy>
364struct __adjacent_find<__default_backend_tag, _ExecutionPolicy> {
365 template <class _Policy, class _ForwardIterator, class _BinaryPredicate>
366 optional<_ForwardIterator>
367 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __predicate)
368 const noexcept {
369 if constexpr (__has_bidirectional_iterator_category<_ForwardIterator>::value) {
370 using _Mismatch = __dispatch<__mismatch, __current_configuration, _ExecutionPolicy>;
371 if (__first == __last) {
372 return __last; // Empty range, return __last.
373 }
374 _ForwardIterator __first2 = std::next(__first);
375 if (__first2 == __last) {
376 return __last; // Single element range, no adjacent elements, return __last.
377 }
378 _ForwardIterator __last2 = std::prev(__last);
379 // Find the first match within two overlapping ranges, expressed as a double negation of the predicate:
380 // [first, __last - 1)
381 // [first + 1, __last)
382 auto __res = _Mismatch()(
383 __policy,
384 std::move(__first),
385 std::move(__last2),
386 std::move(__first2),
387 __last,
388 [&](__iterator_reference<_ForwardIterator> __lhs, __iterator_reference<_ForwardIterator> __rhs) {
389 return !__predicate(__lhs, __rhs);
390 });
391 if (!__res) {
392 return nullopt; // Failed to run the algorithm, propagate the error.
393 }
394 if (__res->second == __last) {
395 return __last; // No adjacent elements found, return __last.
396 }
397 return __res->first; // Return the first iterator of the pair of mismatched elements.
398 } else {
399 // Currently anything outside bidirectional iterators has to be processed serially
400 return std::adjacent_find(std::move(__first), std::move(__last), std::move(__predicate));
401 }
402 }
403};
404
405template <class _ExecutionPolicy>
406struct __is_heap<__default_backend_tag, _ExecutionPolicy> {
407 template <class _Policy, class _RandomAccessIterator, class _Comp>
408 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> operator()(
409 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
410 using _IsHeapUntil = __dispatch<__is_heap_until, __current_configuration, _ExecutionPolicy>;
411 auto __res = _IsHeapUntil()(__policy, std::move(__first), __last, std::forward<_Comp>(__comp));
412 if (!__res) {
413 return nullopt; // Failed to run the algorithm, propagate the error.
414 }
415 return *__res == __last; // is_heap_until returns the last iterator when no heap violations are found in the range.
416 }
417};
418
419template <class _ExecutionPolicy>
420struct __is_sorted_until<__default_backend_tag, _ExecutionPolicy> {
421 template <class _Policy, class _ForwardIterator, class _Comp>
422 optional<_ForwardIterator>
423 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept {
424 using _AdjacentFind = __dispatch<__adjacent_find, __current_configuration, _ExecutionPolicy>;
425 using _Ref = __iterator_reference<_ForwardIterator>;
426 // Find the first pair of adjacent elements that are not in sorted order (i.e. __comp(__rhs, __lhs) is true).
427 auto __res = _AdjacentFind()(__policy, std::move(__first), __last, [&](_Ref __lhs, _Ref __rhs) {
428 return __comp(__rhs, __lhs);
429 });
430 if (!__res) {
431 return nullopt; // Failed to run the algorithm, propagate the error.
432 }
433 if (*__res == __last) {
434 return __last; // Range is sorted, return __last.
435 }
436 ++*__res; // Advance the iterator to the first unsorted element.
437 return *__res;
438 }
439};
440
441template <class _ExecutionPolicy>
442struct __is_sorted<__default_backend_tag, _ExecutionPolicy> {
443 template <class _Policy, class _ForwardIterator, class _Comp>
444 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
445 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept {
446 using _IsSortedUntil = __dispatch<__is_sorted_until, __current_configuration, _ExecutionPolicy>;
447 auto __res = _IsSortedUntil()(__policy, std::move(__first), __last, std::forward<_Comp>(__comp));
448 if (!__res) {
449 return nullopt; // Failed to run the algorithm, propagate the error.
450 }
451 return *__res == __last; // If the first unsorted element is the end of the range, the range is sorted.
452 }
453};
454
455//////////////////////////////////////////////////////////////
456// for_each family
457//////////////////////////////////////////////////////////////
458
459template <class _ExecutionPolicy>
460struct __destroy<__default_backend_tag, _ExecutionPolicy> {
461 template <class _Policy, class _ForwardIterator>
462 optional<__empty> operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept {
463 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
464 using _Ref = __iterator_reference<_ForwardIterator>;
465 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {
466 std::destroy_at(std::addressof(__element));
467 });
468 }
469};
470
471template <class _ExecutionPolicy>
472struct __destroy_n<__default_backend_tag, _ExecutionPolicy> {
473 template <class _Policy, class _ForwardIterator, class _Size>
474 optional<_ForwardIterator> operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept {
475 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
476 using _Ref = __iterator_reference<_ForwardIterator>;
477 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) {
478 std::destroy_at(std::addressof(__element));
479 });
480 }
481};
482
483template <class _ExecutionPolicy>
484struct __for_each_n<__default_backend_tag, _ExecutionPolicy> {
485 template <class _Policy, class _ForwardIterator, class _Size, class _Function>
486 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
487 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) const noexcept {
488 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
489 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
490 _ForwardIterator __last = __first + __size;
491 auto __res = _ForEach()(__policy, std::move(__first), __last, std::move(__func));
492 if (!__res) {
493 return nullopt; // Failed to run the algorithm, propagate the error.
494 }
495 return __last;
496 } else {
497 // Otherwise, use the serial algorithm to avoid doing two passes over the input
498 return std::for_each_n(std::move(__first), __size, std::move(__func));
499 }
500 }
501};
502
503template <class _ExecutionPolicy>
504struct __fill<__default_backend_tag, _ExecutionPolicy> {
505 template <class _Policy, class _ForwardIterator, class _Tp>
506 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
507 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
508 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
509 using _Ref = __iterator_reference<_ForwardIterator>;
510 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; });
511 }
512};
513
514template <class _ExecutionPolicy>
515struct __fill_n<__default_backend_tag, _ExecutionPolicy> {
516 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
517 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
518 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept {
519 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
520 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
521 using _Ref = __iterator_reference<_ForwardIterator>;
522 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __value; });
523 } else {
524 // Otherwise, use the serial algorithm to avoid doing two passes over the input
525 return std::fill_n(std::move(__first), __n, __value);
526 }
527 }
528};
529
530template <class _ExecutionPolicy>
531struct __replace<__default_backend_tag, _ExecutionPolicy> {
532 template <class _Policy, class _ForwardIterator, class _Tp>
533 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
534 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new)
535 const noexcept {
536 using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>;
537 using _Ref = __iterator_reference<_ForwardIterator>;
538 return _ReplaceIf()(
539 __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new);
540 }
541};
542
543template <class _ExecutionPolicy>
544struct __replace_if<__default_backend_tag, _ExecutionPolicy> {
545 template <class _Policy, class _ForwardIterator, class _Pred, class _Tp>
546 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
547 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value)
548 const noexcept {
549 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
550 using _Ref = __iterator_reference<_ForwardIterator>;
551 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {
552 if (__pred(__element))
553 __element = __new_value;
554 });
555 }
556};
557
558template <class _ExecutionPolicy>
559struct __generate<__default_backend_tag, _ExecutionPolicy> {
560 template <class _Policy, class _ForwardIterator, class _Generator>
561 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
562 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept {
563 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
564 using _Ref = __iterator_reference<_ForwardIterator>;
565 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); });
566 }
567};
568
569template <class _ExecutionPolicy>
570struct __generate_n<__default_backend_tag, _ExecutionPolicy> {
571 template <class _Policy, class _ForwardIterator, class _Size, class _Generator>
572 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
573 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept {
574 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
575 using _Ref = __iterator_reference<_ForwardIterator>;
576 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); });
577 }
578};
579
580template <class _ExecutionPolicy>
581struct __uninitialized_default_construct<__default_backend_tag, _ExecutionPolicy> {
582 template <class _Policy, class _ForwardIterator>
583 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
584 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept {
585 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
586 using _ValueType = __iterator_value_type<_ForwardIterator>;
587 using _Ref = __iterator_reference<_ForwardIterator>;
588 return _ForEach()(__policy, std::move(__first), std::move(__last), [](_Ref __element) {
589 ::new (static_cast<void*>(std::addressof(__element))) _ValueType;
590 });
591 }
592};
593
594template <class _ExecutionPolicy>
595struct __uninitialized_default_construct_n<__default_backend_tag, _ExecutionPolicy> {
596 template <class _Policy, class _ForwardIterator, class _Size>
597 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
598 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept {
599 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
600 using _ValueType = __iterator_value_type<_ForwardIterator>;
601 using _Ref = __iterator_reference<_ForwardIterator>;
602 return _ForEachN()(__policy, std::move(__first), __n, [](_Ref __element) {
603 ::new (static_cast<void*>(std::addressof(__element))) _ValueType;
604 });
605 }
606};
607
608template <class _ExecutionPolicy>
609struct __uninitialized_value_construct<__default_backend_tag, _ExecutionPolicy> {
610 template <class _Policy, class _ForwardIterator>
611 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
612 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept {
613 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
614 using _ValueType = __iterator_value_type<_ForwardIterator>;
615 using _Ref = __iterator_reference<_ForwardIterator>;
616 return _ForEach()(__policy, std::move(__first), std::move(__last), [](_Ref __element) {
617 ::new (static_cast<void*>(std::addressof(__element))) _ValueType();
618 });
619 }
620};
621
622template <class _ExecutionPolicy>
623struct __uninitialized_value_construct_n<__default_backend_tag, _ExecutionPolicy> {
624 template <class _Policy, class _ForwardIterator, class _Size>
625 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
626 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept {
627 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
628 using _ValueType = __iterator_value_type<_ForwardIterator>;
629 using _Ref = __iterator_reference<_ForwardIterator>;
630 return _ForEachN()(__policy, std::move(__first), __n, [](_Ref __element) {
631 ::new (static_cast<void*>(std::addressof(__element))) _ValueType();
632 });
633 }
634};
635
636template <class _ExecutionPolicy>
637struct __uninitialized_fill<__default_backend_tag, _ExecutionPolicy> {
638 template <class _Policy, class _ForwardIterator, class _Tp>
639 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
640 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {
641 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
642 using _ValueType = __iterator_value_type<_ForwardIterator>;
643 using _Ref = __iterator_reference<_ForwardIterator>;
644 return _ForEach()(__policy, std::move(__first), std::move(__last), [&__value](_Ref __element) {
645 ::new (static_cast<void*>(std::addressof(__element))) _ValueType(__value);
646 });
647 }
648};
649
650template <class _ExecutionPolicy>
651struct __uninitialized_fill_n<__default_backend_tag, _ExecutionPolicy> {
652 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
653 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
654 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, const _Tp& __value) const noexcept {
655 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
656 using _ValueType = __iterator_value_type<_ForwardIterator>;
657 using _Ref = __iterator_reference<_ForwardIterator>;
658 return _ForEachN()(__policy, std::move(__first), __n, [&__value](_Ref __element) {
659 ::new (static_cast<void*>(std::addressof(__element))) _ValueType(__value);
660 });
661 }
662};
663
664//////////////////////////////////////////////////////////////
665// stable_sort family
666//////////////////////////////////////////////////////////////
667template <class _ExecutionPolicy>
668struct __sort<__default_backend_tag, _ExecutionPolicy> {
669 template <class _Policy, class _RandomAccessIterator, class _Comp>
670 _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
671 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
672 using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>;
673 return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
674 }
675};
676
677//////////////////////////////////////////////////////////////
678// transform_reduce family
679//////////////////////////////////////////////////////////////
680template <class _ExecutionPolicy>
681struct __count_if<__default_backend_tag, _ExecutionPolicy> {
682 template <class _Policy, class _ForwardIterator, class _Predicate>
683 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>> operator()(
684 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept {
685 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
686 using _DiffT = __iterator_difference_type<_ForwardIterator>;
687 using _Ref = __iterator_reference<_ForwardIterator>;
688 return _TransformReduce()(
689 __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT {
690 return __pred(__element) ? _DiffT(1) : _DiffT(0);
691 });
692 }
693};
694
695template <class _ExecutionPolicy>
696struct __count<__default_backend_tag, _ExecutionPolicy> {
697 template <class _Policy, class _ForwardIterator, class _Tp>
698 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>>
699 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
700 using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>;
701 using _Ref = __iterator_reference<_ForwardIterator>;
702 return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool {
703 return __element == __value;
704 });
705 }
706};
707
708template <class _ExecutionPolicy>
709struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> {
710 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
711 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
712 operator()(_Policy&& __policy,
713 _ForwardIterator1 __first1,
714 _ForwardIterator1 __last1,
715 _ForwardIterator2 __first2,
716 _Predicate&& __pred) const noexcept {
717 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;
718 return _TransformReduce()(
719 __policy,
720 std::move(__first1),
721 std::move(__last1),
722 std::move(__first2),
723 true,
724 std::logical_and{},
725 std::forward<_Predicate>(__pred));
726 }
727};
728
729template <class _ExecutionPolicy>
730struct __equal<__default_backend_tag, _ExecutionPolicy> {
731 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
732 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
733 operator()(_Policy&& __policy,
734 _ForwardIterator1 __first1,
735 _ForwardIterator1 __last1,
736 _ForwardIterator2 __first2,
737 _ForwardIterator2 __last2,
738 _Predicate&& __pred) const noexcept {
739 if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value &&
740 __has_random_access_iterator_category<_ForwardIterator2>::value) {
741 if (__last1 - __first1 != __last2 - __first2)
742 return false;
743 // Fall back to the 3 legged algorithm
744 using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>;
745 return _Equal3Leg()(
746 __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred));
747 } else {
748 // If we don't have random access, fall back to the serial algorithm cause we can't do much
749 return std::equal(
750 std::move(__first1),
751 std::move(__last1),
752 std::move(__first2),
753 std::move(__last2),
754 std::forward<_Predicate>(__pred));
755 }
756 }
757};
758
759template <class _ExecutionPolicy>
760struct __reduce<__default_backend_tag, _ExecutionPolicy> {
761 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation>
762 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp>
763 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op)
764 const noexcept {
765 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
766 return _TransformReduce()(
767 __policy,
768 std::move(__first),
769 std::move(__last),
770 std::move(__init),
771 std::forward<_BinaryOperation>(__op),
772 __identity{});
773 }
774};
775
776//////////////////////////////////////////////////////////////
777// transform family
778//////////////////////////////////////////////////////////////
779template <class _ExecutionPolicy>
780struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> {
781 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp>
782 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
783 operator()(_Policy&& __policy,
784 _ForwardIterator __first,
785 _ForwardIterator __last,
786 _ForwardOutIterator __out_it,
787 _Pred&& __pred,
788 _Tp const& __new_value) const noexcept {
789 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
790 using _Ref = __iterator_reference<_ForwardIterator>;
791 auto __res =
792 _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) {
793 return __pred(__element) ? __new_value : __element;
794 });
795 if (__res == nullopt)
796 return nullopt;
797 return __empty{};
798 }
799};
800
801template <class _ExecutionPolicy>
802struct __replace_copy<__default_backend_tag, _ExecutionPolicy> {
803 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp>
804 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
805 operator()(_Policy&& __policy,
806 _ForwardIterator __first,
807 _ForwardIterator __last,
808 _ForwardOutIterator __out_it,
809 _Tp const& __old_value,
810 _Tp const& __new_value) const noexcept {
811 using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>;
812 using _Ref = __iterator_reference<_ForwardIterator>;
813 return _ReplaceCopyIf()(
814 __policy,
815 std::move(__first),
816 std::move(__last),
817 std::move(__out_it),
818 [&](_Ref __element) { return __element == __old_value; },
819 __new_value);
820 }
821};
822
823// TODO: Use the std::copy/move shenanigans to forward to std::memmove
824// Investigate whether we want to still forward to std::transform(policy)
825// in that case for the execution::par part, or whether we actually want
826// to run everything serially in that case.
827template <class _ExecutionPolicy>
828struct __move<__default_backend_tag, _ExecutionPolicy> {
829 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
830 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
831 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
832 const noexcept {
833 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
834 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) {
835 return std::move(__element);
836 });
837 }
838};
839
840// TODO: Use the std::copy/move shenanigans to forward to std::memmove
841template <class _ExecutionPolicy>
842struct __copy<__default_backend_tag, _ExecutionPolicy> {
843 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
844 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
845 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
846 const noexcept {
847 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
848 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity());
849 }
850};
851
852template <class _ExecutionPolicy>
853struct __copy_n<__default_backend_tag, _ExecutionPolicy> {
854 template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator>
855 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
856 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept {
857 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
858 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
859 _ForwardIterator __last = __first + __n;
860 return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it));
861 } else {
862 // Otherwise, use the serial algorithm to avoid doing two passes over the input
863 return std::copy_n(std::move(__first), __n, std::move(__out_it));
864 }
865 }
866};
867
868template <class _ExecutionPolicy>
869struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> {
870 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
871 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
872 operator()(_Policy&& __policy,
873 _ForwardIterator __first,
874 _ForwardIterator __middle,
875 _ForwardIterator __last,
876 _ForwardOutIterator __out_it) const noexcept {
877 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
878 auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it));
879 if (__result_mid == nullopt)
880 return nullopt;
881 return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid));
882 }
883};
884
885template <class _ExecutionPolicy>
886struct __reverse_copy<__default_backend_tag, _ExecutionPolicy> {
887 template <class _Policy, class _BidirectionalIterator, class _ForwardIterator>
888 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
889 operator()(_Policy&& __policy,
890 _BidirectionalIterator __first,
891 _BidirectionalIterator __last,
892 _ForwardIterator __result) const noexcept {
893 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
894 return _Copy()(__policy,
895 std::reverse_iterator<_BidirectionalIterator>(std::move(__last)),
896 std::reverse_iterator<_BidirectionalIterator>(std::move(__first)),
897 std::move(__result));
898 }
899};
900
901template <class _ExecutionPolicy>
902struct __adjacent_difference<__default_backend_tag, _ExecutionPolicy> {
903 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
904 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2>
905 operator()(_Policy&& __policy,
906 _ForwardIterator1 __first1,
907 _ForwardIterator1 __last1,
908 _ForwardIterator2 __result,
909 _BinaryOperation&& __op) const noexcept {
910 using _TransformBinary = __dispatch<__transform_binary, __current_configuration, _ExecutionPolicy>;
911 if (__first1 == __last1)
912 return __result; // edge case: empty input range, just return the output iterator
913 *__result = *__first1;
914 ++__result;
915 _ForwardIterator1 __first2 = std::next(__first1);
916 if (__first2 == __last1)
917 return __result; // edge case: not enough elements to perform adjacent difference, just return the output
918 // iterator
919 // Process as a binary transform of two iterator ranges: [__first1 + 1, __last1) and [__first1, __last1 - 1)
920 return _TransformBinary()(
921 __policy,
922 std::move(__first2),
923 std::move(__last1),
924 std::move(__first1),
925 std::move(__result),
926 std::forward<_BinaryOperation>(__op));
927 }
928};
929
930//////////////////////////////////////////////////////////////
931// uninitialized_copy family
932//////////////////////////////////////////////////////////////
933
934template <class _ExecutionPolicy>
935struct __uninitialized_copy_n<__default_backend_tag, _ExecutionPolicy> {
936 template <class _Policy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
937 optional<_ForwardIterator2>
938 operator()(_Policy&& __policy, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) const noexcept {
939 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
940 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
941 using _UninitializedCopy = __dispatch<__uninitialized_copy, __current_configuration, _ExecutionPolicy>;
942 _ForwardIterator1 __last = __first + __n;
943 return _UninitializedCopy()(__policy, std::move(__first), std::move(__last), std::move(__result));
944 } else {
945 return std::uninitialized_copy_n(std::move(__first), __n, std::move(__result));
946 }
947 }
948};
949
950//////////////////////////////////////////////////////////////
951// uninitialized_move family
952//////////////////////////////////////////////////////////////
953
954template <class _ExecutionPolicy>
955struct __uninitialized_move_n<__default_backend_tag, _ExecutionPolicy> {
956 template <class _Policy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
957 optional<pair<_ForwardIterator1, _ForwardIterator2>>
958 operator()(_Policy&& __policy, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) const noexcept {
959 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
960 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
961 using _UninitializedMove = __dispatch<__uninitialized_move, __current_configuration, _ExecutionPolicy>;
962 _ForwardIterator1 __last = __first + __n;
963 auto __res = _UninitializedMove()(__policy, std::move(__first), __last, std::move(__result));
964 if (!__res)
965 return nullopt; // Failed to run the parallel algorithm, propagate the failure
966 return pair{__last, *__res};
967 } else {
968 return std::uninitialized_move_n(std::move(__first), __n, std::move(__result));
969 }
970 }
971};
972
973//////////////////////////////////////////////////////////////
974// transform_inclusive_scan_init family
975//////////////////////////////////////////////////////////////
976
977template <class _ExecutionPolicy>
978struct __inclusive_scan<__default_backend_tag, _ExecutionPolicy> {
979 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
980 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2>
981 operator()(_Policy&& __policy,
982 _ForwardIterator1 __first,
983 _ForwardIterator1 __last,
984 _ForwardIterator2 __result,
985 _BinaryOperation __reduce) const noexcept {
986 using _TransformInclusiveScan = __dispatch<__transform_inclusive_scan, __current_configuration, _ExecutionPolicy>;
987 return _TransformInclusiveScan()(
988 __policy, std::move(__first), std::move(__last), std::move(__result), std::move(__reduce), __identity{});
989 }
990};
991
992template <class _ExecutionPolicy>
993struct __inclusive_scan_init<__default_backend_tag, _ExecutionPolicy> {
994 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation, class _Tp>
995 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2>
996 operator()(_Policy&& __policy,
997 _ForwardIterator1 __first,
998 _ForwardIterator1 __last,
999 _ForwardIterator2 __result,
1000 _BinaryOperation __reduce,
1001 _Tp __init) const noexcept {
1002 using _TransformInclusiveScanInit =
1003 __dispatch<__transform_inclusive_scan_init, __current_configuration, _ExecutionPolicy>;
1004 return _TransformInclusiveScanInit()(
1005 __policy,
1006 std::move(__first),
1007 std::move(__last),
1008 std::move(__result),
1009 std::move(__reduce),
1010 __identity{},
1011 std::move(__init));
1012 }
1013};
1014
1015template <class _ExecutionPolicy>
1016struct __transform_inclusive_scan<__default_backend_tag, _ExecutionPolicy> {
1017 template <class _Policy,
1018 class _ForwardIterator1,
1019 class _ForwardIterator2,
1020 class _BinaryOperation,
1021 class _UnaryOperation>
1022 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2>
1023 operator()(_Policy&& __policy,
1024 _ForwardIterator1 __first,
1025 _ForwardIterator1 __last,
1026 _ForwardIterator2 __result,
1027 _BinaryOperation __reduce,
1028 _UnaryOperation __transform) const noexcept {
1029 if (__first != __last) {
1030 using _TransformInclusiveScanInit =
1031 __dispatch<__transform_inclusive_scan_init, __current_configuration, _ExecutionPolicy>;
1032 using _ValueType = __iterator_value_type<_ForwardIterator1>;
1033 _ValueType __init = __transform(*__first);
1034 *__result++ = __init;
1035 if (++__first != __last)
1036 return _TransformInclusiveScanInit()(
1037 __policy,
1038 std::move(__first),
1039 std::move(__last),
1040 std::move(__result),
1041 std::move(__reduce),
1042 std::move(__transform),
1043 std::move(__init));
1044 }
1045 return __result;
1046 }
1047};
1048
1049} // namespace __pstl
1050_LIBCPP_END_NAMESPACE_STD
1051
1052#endif // _LIBCPP_STD_VER >= 17
1053
1054_LIBCPP_POP_MACROS
1055
1056#endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H
1057