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
168//////////////////////////////////////////////////////////////
169// find_if family
170//////////////////////////////////////////////////////////////
171template <class _ExecutionPolicy>
172struct __find<__default_backend_tag, _ExecutionPolicy> {
173 template <class _Policy, class _ForwardIterator, class _Tp>
174 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
175 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {
176 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
177 return _FindIf()(
178 __policy, std::move(__first), std::move(__last), [&](__iterator_reference<_ForwardIterator> __element) {
179 return __element == __value;
180 });
181 }
182};
183
184template <class _ExecutionPolicy>
185struct __find_if_not<__default_backend_tag, _ExecutionPolicy> {
186 template <class _Policy, class _ForwardIterator, class _Pred>
187 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
188 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
189 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
190 return _FindIf()(__policy, __first, __last, std::not_fn(std::forward<_Pred>(__pred)));
191 }
192};
193
194template <class _ExecutionPolicy>
195struct __any_of<__default_backend_tag, _ExecutionPolicy> {
196 template <class _Policy, class _ForwardIterator, class _Pred>
197 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
198 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
199 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
200 auto __res = _FindIf()(__policy, __first, __last, std::forward<_Pred>(__pred));
201 if (!__res)
202 return nullopt;
203 return *__res != __last;
204 }
205};
206
207template <class _ExecutionPolicy>
208struct __all_of<__default_backend_tag, _ExecutionPolicy> {
209 template <class _Policy, class _ForwardIterator, class _Pred>
210 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
211 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
212 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
213 auto __res = _AnyOf()(__policy, __first, __last, [&](__iterator_reference<_ForwardIterator> __value) {
214 return !__pred(__value);
215 });
216 if (!__res)
217 return nullopt;
218 return !*__res;
219 }
220};
221
222template <class _ExecutionPolicy>
223struct __none_of<__default_backend_tag, _ExecutionPolicy> {
224 template <class _Policy, class _ForwardIterator, class _Pred>
225 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
226 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
227 using _AnyOf = __dispatch<__any_of, __current_configuration, _ExecutionPolicy>;
228 auto __res = _AnyOf()(__policy, __first, __last, std::forward<_Pred>(__pred));
229 if (!__res)
230 return nullopt;
231 return !*__res;
232 }
233};
234
235template <class _ExecutionPolicy>
236struct __is_partitioned<__default_backend_tag, _ExecutionPolicy> {
237 template <class _Policy, class _ForwardIterator, class _Pred>
238 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
239 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
240 using _FindIfNot = __dispatch<__find_if_not, __current_configuration, _ExecutionPolicy>;
241 auto __maybe_first = _FindIfNot()(__policy, std::move(__first), __last, __pred);
242 if (__maybe_first == nullopt)
243 return nullopt;
244
245 __first = *__maybe_first;
246 if (__first == __last)
247 return true;
248 ++__first;
249 using _NoneOf = __dispatch<__none_of, __current_configuration, _ExecutionPolicy>;
250 return _NoneOf()(__policy, std::move(__first), std::move(__last), __pred);
251 }
252};
253
254template <class _ExecutionPolicy>
255struct __find_first_of<__default_backend_tag, _ExecutionPolicy> {
256 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
257 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
258 operator()(_Policy&& __policy,
259 _ForwardIterator1 __first1,
260 _ForwardIterator1 __last1,
261 _ForwardIterator2 __first2,
262 _ForwardIterator2 __last2,
263 _Predicate&& __pred) const noexcept {
264 using _FindIf = __dispatch<__find_if, __current_configuration, _ExecutionPolicy>;
265 using _Ref1 = __iterator_reference<_ForwardIterator1>;
266 using _Ref2 = __iterator_reference<_ForwardIterator2>;
267 return _FindIf()(__policy, std::move(__first1), std::move(__last1), [&](_Ref1 __element) {
268 if constexpr (__desugars_to_v<__equal_tag, _Predicate, _Ref1, _Ref2>) {
269 // bypass an equality predicate and call directly to std::find() to allow more vectorization
270 return std::find(__first2, __last2, __element) != __last2;
271 } else {
272 return std::find_if(__first2, __last2, [&](_Ref2 __value) { return __pred(__element, __value); }) != __last2;
273 }
274 });
275 }
276};
277
278//////////////////////////////////////////////////////////////
279// min_element family
280//////////////////////////////////////////////////////////////
281
282template <class _ExecutionPolicy>
283struct __max_element<__default_backend_tag, _ExecutionPolicy> {
284 template <class _Policy, class _ForwardIterator, class _Compare>
285 optional<_ForwardIterator>
286 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) const noexcept {
287 using _MinElement = __dispatch<__min_element, __current_configuration, _ExecutionPolicy>;
288 using _Ref = __iterator_reference<_ForwardIterator>;
289 // Express max_element via min_element by replacing the comparison
290 // "lhs OP rhs" with "rhs OP lhs".
291 return _MinElement()(
292 __policy, std::move(__first), std::move(__last), [__comp = std::move(__comp)](_Ref __lhs, _Ref __rhs) {
293 return __comp(__rhs, __lhs);
294 });
295 }
296};
297
298//////////////////////////////////////////////////////////////
299// mismatch family
300//////////////////////////////////////////////////////////////
301
302template <class _ExecutionPolicy>
303struct __lexicographical_compare<__default_backend_tag, _ExecutionPolicy> {
304 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Comp>
305 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
306 operator()(_Policy&& __policy,
307 _ForwardIterator1 __first1,
308 _ForwardIterator1 __last1,
309 _ForwardIterator2 __first2,
310 _ForwardIterator2 __last2,
311 _Comp __comp) const noexcept {
312 using _Mismatch = __dispatch<__mismatch, __current_configuration, _ExecutionPolicy>;
313 using _Ref1 = __iterator_reference<_ForwardIterator1>;
314 using _Ref2 = __iterator_reference<_ForwardIterator2>;
315 // find the first pair of elements that are not equal, or the end of one or both of the ranges
316 auto __res = _Mismatch()(__policy, __first1, __last1, __first2, __last2, [&](_Ref1 __lhs, _Ref2 __rhs) {
317 return !__comp(__lhs, __rhs) && !__comp(__rhs, __lhs); // derive equality from the less-than predicate
318 });
319 if (!__res) // if the underlying mismatch operation failed, return nullopt
320 return nullopt;
321 if (__res->first == __last1) // the first range is exhausted,
322 return __res->second != __last2; // it is lexicographically less if the second range is not exhausted.
323 if (__res->second == __last2) // the second range is exhausted,
324 return false; // the first range is not exhausted, so it is not lexicographically less.
325 return __comp(*__res->first, *__res->second); // otherwise, compare the first pair of non-equal elements
326 }
327};
328
329template <class _ExecutionPolicy>
330struct __mismatch_3leg<__default_backend_tag, _ExecutionPolicy> {
331 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Comp>
332 optional<pair<_ForwardIterator1, _ForwardIterator2>>
333 operator()(_Policy&& __policy,
334 _ForwardIterator1 __first1,
335 _ForwardIterator1 __last1,
336 _ForwardIterator2 __first2,
337 _Comp __comp) const noexcept {
338 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
339 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
340 // Forward to the 4-legged version of mismatch.
341 using _Mismatch = __dispatch<__mismatch, __current_configuration, _ExecutionPolicy>;
342 _ForwardIterator2 __last2 = __first2 + (__last1 - __first1);
343 return _Mismatch()(
344 __policy,
345 std::move(__first1),
346 std::move(__last1),
347 std::move(__first2),
348 std::move(__last2),
349 std::move(__comp));
350 } else {
351 // Currently only random access iterators are supported for parallel mismatch_3leg.
352 return std::mismatch(std::move(__first1), std::move(__last1), std::move(__first2), std::move(__comp));
353 }
354 }
355};
356
357template <class _ExecutionPolicy>
358struct __adjacent_find<__default_backend_tag, _ExecutionPolicy> {
359 template <class _Policy, class _ForwardIterator, class _BinaryPredicate>
360 optional<_ForwardIterator>
361 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __predicate)
362 const noexcept {
363 if constexpr (__has_bidirectional_iterator_category<_ForwardIterator>::value) {
364 using _Mismatch = __dispatch<__mismatch, __current_configuration, _ExecutionPolicy>;
365 if (__first == __last) {
366 return __last; // Empty range, return __last.
367 }
368 _ForwardIterator __first2 = std::next(__first);
369 if (__first2 == __last) {
370 return __last; // Single element range, no adjacent elements, return __last.
371 }
372 _ForwardIterator __last2 = std::prev(__last);
373 // Find the first match within two overlapping ranges, expressed as a double negation of the predicate:
374 // [first, __last - 1)
375 // [first + 1, __last)
376 auto __res = _Mismatch()(
377 __policy,
378 std::move(__first),
379 std::move(__last2),
380 std::move(__first2),
381 __last,
382 [&](__iterator_reference<_ForwardIterator> __lhs, __iterator_reference<_ForwardIterator> __rhs) {
383 return !__predicate(__lhs, __rhs);
384 });
385 if (!__res) {
386 return nullopt; // Failed to run the algorithm, propagate the error.
387 }
388 if (__res->second == __last) {
389 return __last; // No adjacent elements found, return __last.
390 }
391 return __res->first; // Return the first iterator of the pair of mismatched elements.
392 } else {
393 // Currently anything outside bidirectional iterators has to be processed serially
394 return std::adjacent_find(std::move(__first), std::move(__last), std::move(__predicate));
395 }
396 }
397};
398
399template <class _ExecutionPolicy>
400struct __is_heap<__default_backend_tag, _ExecutionPolicy> {
401 template <class _Policy, class _RandomAccessIterator, class _Comp>
402 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> operator()(
403 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
404 using _IsHeapUntil = __dispatch<__is_heap_until, __current_configuration, _ExecutionPolicy>;
405 auto __res = _IsHeapUntil()(__policy, std::move(__first), __last, std::forward<_Comp>(__comp));
406 if (!__res) {
407 return nullopt; // Failed to run the algorithm, propagate the error.
408 }
409 return *__res == __last; // is_heap_until returns the last iterator when no heap violations are found in the range.
410 }
411};
412
413template <class _ExecutionPolicy>
414struct __is_sorted_until<__default_backend_tag, _ExecutionPolicy> {
415 template <class _Policy, class _ForwardIterator, class _Comp>
416 optional<_ForwardIterator>
417 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept {
418 using _AdjacentFind = __dispatch<__adjacent_find, __current_configuration, _ExecutionPolicy>;
419 using _Ref = __iterator_reference<_ForwardIterator>;
420 // Find the first pair of adjacent elements that are not in sorted order (i.e. __comp(__rhs, __lhs) is true).
421 auto __res = _AdjacentFind()(__policy, std::move(__first), __last, [&](_Ref __lhs, _Ref __rhs) {
422 return __comp(__rhs, __lhs);
423 });
424 if (!__res) {
425 return nullopt; // Failed to run the algorithm, propagate the error.
426 }
427 if (*__res == __last) {
428 return __last; // Range is sorted, return __last.
429 }
430 ++*__res; // Advance the iterator to the first unsorted element.
431 return *__res;
432 }
433};
434
435template <class _ExecutionPolicy>
436struct __is_sorted<__default_backend_tag, _ExecutionPolicy> {
437 template <class _Policy, class _ForwardIterator, class _Comp>
438 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
439 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept {
440 using _IsSortedUntil = __dispatch<__is_sorted_until, __current_configuration, _ExecutionPolicy>;
441 auto __res = _IsSortedUntil()(__policy, std::move(__first), __last, std::forward<_Comp>(__comp));
442 if (!__res) {
443 return nullopt; // Failed to run the algorithm, propagate the error.
444 }
445 return *__res == __last; // If the first unsorted element is the end of the range, the range is sorted.
446 }
447};
448
449//////////////////////////////////////////////////////////////
450// for_each family
451//////////////////////////////////////////////////////////////
452
453template <class _ExecutionPolicy>
454struct __destroy<__default_backend_tag, _ExecutionPolicy> {
455 template <class _Policy, class _ForwardIterator>
456 optional<__empty> operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept {
457 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
458 using _Ref = __iterator_reference<_ForwardIterator>;
459 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {
460 std::destroy_at(std::addressof(__element));
461 });
462 }
463};
464
465template <class _ExecutionPolicy>
466struct __destroy_n<__default_backend_tag, _ExecutionPolicy> {
467 template <class _Policy, class _ForwardIterator, class _Size>
468 optional<_ForwardIterator> operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept {
469 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
470 using _Ref = __iterator_reference<_ForwardIterator>;
471 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) {
472 std::destroy_at(std::addressof(__element));
473 });
474 }
475};
476
477template <class _ExecutionPolicy>
478struct __for_each_n<__default_backend_tag, _ExecutionPolicy> {
479 template <class _Policy, class _ForwardIterator, class _Size, class _Function>
480 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
481 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) const noexcept {
482 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
483 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
484 _ForwardIterator __last = __first + __size;
485 auto __res = _ForEach()(__policy, std::move(__first), __last, std::move(__func));
486 if (!__res) {
487 return nullopt; // Failed to run the algorithm, propagate the error.
488 }
489 return __last;
490 } else {
491 // Otherwise, use the serial algorithm to avoid doing two passes over the input
492 return std::for_each_n(std::move(__first), __size, std::move(__func));
493 }
494 }
495};
496
497template <class _ExecutionPolicy>
498struct __fill<__default_backend_tag, _ExecutionPolicy> {
499 template <class _Policy, class _ForwardIterator, class _Tp>
500 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
501 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
502 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
503 using _Ref = __iterator_reference<_ForwardIterator>;
504 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; });
505 }
506};
507
508template <class _ExecutionPolicy>
509struct __fill_n<__default_backend_tag, _ExecutionPolicy> {
510 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
511 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
512 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept {
513 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
514 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
515 using _Ref = __iterator_reference<_ForwardIterator>;
516 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __value; });
517 } else {
518 // Otherwise, use the serial algorithm to avoid doing two passes over the input
519 return std::fill_n(std::move(__first), __n, __value);
520 }
521 }
522};
523
524template <class _ExecutionPolicy>
525struct __replace<__default_backend_tag, _ExecutionPolicy> {
526 template <class _Policy, class _ForwardIterator, class _Tp>
527 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
528 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new)
529 const noexcept {
530 using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>;
531 using _Ref = __iterator_reference<_ForwardIterator>;
532 return _ReplaceIf()(
533 __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new);
534 }
535};
536
537template <class _ExecutionPolicy>
538struct __replace_if<__default_backend_tag, _ExecutionPolicy> {
539 template <class _Policy, class _ForwardIterator, class _Pred, class _Tp>
540 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
541 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value)
542 const noexcept {
543 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
544 using _Ref = __iterator_reference<_ForwardIterator>;
545 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {
546 if (__pred(__element))
547 __element = __new_value;
548 });
549 }
550};
551
552template <class _ExecutionPolicy>
553struct __generate<__default_backend_tag, _ExecutionPolicy> {
554 template <class _Policy, class _ForwardIterator, class _Generator>
555 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
556 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept {
557 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
558 using _Ref = __iterator_reference<_ForwardIterator>;
559 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); });
560 }
561};
562
563template <class _ExecutionPolicy>
564struct __generate_n<__default_backend_tag, _ExecutionPolicy> {
565 template <class _Policy, class _ForwardIterator, class _Size, class _Generator>
566 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
567 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept {
568 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
569 using _Ref = __iterator_reference<_ForwardIterator>;
570 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); });
571 }
572};
573
574template <class _ExecutionPolicy>
575struct __uninitialized_default_construct<__default_backend_tag, _ExecutionPolicy> {
576 template <class _Policy, class _ForwardIterator>
577 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
578 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept {
579 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
580 using _ValueType = __iterator_value_type<_ForwardIterator>;
581 using _Ref = __iterator_reference<_ForwardIterator>;
582 return _ForEach()(__policy, std::move(__first), std::move(__last), [](_Ref __element) {
583 ::new (static_cast<void*>(std::addressof(__element))) _ValueType;
584 });
585 }
586};
587
588template <class _ExecutionPolicy>
589struct __uninitialized_default_construct_n<__default_backend_tag, _ExecutionPolicy> {
590 template <class _Policy, class _ForwardIterator, class _Size>
591 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
592 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept {
593 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
594 using _ValueType = __iterator_value_type<_ForwardIterator>;
595 using _Ref = __iterator_reference<_ForwardIterator>;
596 return _ForEachN()(__policy, std::move(__first), __n, [](_Ref __element) {
597 ::new (static_cast<void*>(std::addressof(__element))) _ValueType;
598 });
599 }
600};
601
602template <class _ExecutionPolicy>
603struct __uninitialized_value_construct<__default_backend_tag, _ExecutionPolicy> {
604 template <class _Policy, class _ForwardIterator>
605 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
606 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept {
607 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
608 using _ValueType = __iterator_value_type<_ForwardIterator>;
609 using _Ref = __iterator_reference<_ForwardIterator>;
610 return _ForEach()(__policy, std::move(__first), std::move(__last), [](_Ref __element) {
611 ::new (static_cast<void*>(std::addressof(__element))) _ValueType();
612 });
613 }
614};
615
616template <class _ExecutionPolicy>
617struct __uninitialized_value_construct_n<__default_backend_tag, _ExecutionPolicy> {
618 template <class _Policy, class _ForwardIterator, class _Size>
619 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
620 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept {
621 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
622 using _ValueType = __iterator_value_type<_ForwardIterator>;
623 using _Ref = __iterator_reference<_ForwardIterator>;
624 return _ForEachN()(__policy, std::move(__first), __n, [](_Ref __element) {
625 ::new (static_cast<void*>(std::addressof(__element))) _ValueType();
626 });
627 }
628};
629
630template <class _ExecutionPolicy>
631struct __uninitialized_fill<__default_backend_tag, _ExecutionPolicy> {
632 template <class _Policy, class _ForwardIterator, class _Tp>
633 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
634 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {
635 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
636 using _ValueType = __iterator_value_type<_ForwardIterator>;
637 using _Ref = __iterator_reference<_ForwardIterator>;
638 return _ForEach()(__policy, std::move(__first), std::move(__last), [&__value](_Ref __element) {
639 ::new (static_cast<void*>(std::addressof(__element))) _ValueType(__value);
640 });
641 }
642};
643
644template <class _ExecutionPolicy>
645struct __uninitialized_fill_n<__default_backend_tag, _ExecutionPolicy> {
646 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
647 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
648 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, const _Tp& __value) const noexcept {
649 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
650 using _ValueType = __iterator_value_type<_ForwardIterator>;
651 using _Ref = __iterator_reference<_ForwardIterator>;
652 return _ForEachN()(__policy, std::move(__first), __n, [&__value](_Ref __element) {
653 ::new (static_cast<void*>(std::addressof(__element))) _ValueType(__value);
654 });
655 }
656};
657
658//////////////////////////////////////////////////////////////
659// stable_sort family
660//////////////////////////////////////////////////////////////
661template <class _ExecutionPolicy>
662struct __sort<__default_backend_tag, _ExecutionPolicy> {
663 template <class _Policy, class _RandomAccessIterator, class _Comp>
664 _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
665 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
666 using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>;
667 return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
668 }
669};
670
671//////////////////////////////////////////////////////////////
672// transform_reduce family
673//////////////////////////////////////////////////////////////
674template <class _ExecutionPolicy>
675struct __count_if<__default_backend_tag, _ExecutionPolicy> {
676 template <class _Policy, class _ForwardIterator, class _Predicate>
677 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>> operator()(
678 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept {
679 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
680 using _DiffT = __iterator_difference_type<_ForwardIterator>;
681 using _Ref = __iterator_reference<_ForwardIterator>;
682 return _TransformReduce()(
683 __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT {
684 return __pred(__element) ? _DiffT(1) : _DiffT(0);
685 });
686 }
687};
688
689template <class _ExecutionPolicy>
690struct __count<__default_backend_tag, _ExecutionPolicy> {
691 template <class _Policy, class _ForwardIterator, class _Tp>
692 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>>
693 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
694 using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>;
695 using _Ref = __iterator_reference<_ForwardIterator>;
696 return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool {
697 return __element == __value;
698 });
699 }
700};
701
702template <class _ExecutionPolicy>
703struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> {
704 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
705 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
706 operator()(_Policy&& __policy,
707 _ForwardIterator1 __first1,
708 _ForwardIterator1 __last1,
709 _ForwardIterator2 __first2,
710 _Predicate&& __pred) const noexcept {
711 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;
712 return _TransformReduce()(
713 __policy,
714 std::move(__first1),
715 std::move(__last1),
716 std::move(__first2),
717 true,
718 std::logical_and{},
719 std::forward<_Predicate>(__pred));
720 }
721};
722
723template <class _ExecutionPolicy>
724struct __equal<__default_backend_tag, _ExecutionPolicy> {
725 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
726 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
727 operator()(_Policy&& __policy,
728 _ForwardIterator1 __first1,
729 _ForwardIterator1 __last1,
730 _ForwardIterator2 __first2,
731 _ForwardIterator2 __last2,
732 _Predicate&& __pred) const noexcept {
733 if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value &&
734 __has_random_access_iterator_category<_ForwardIterator2>::value) {
735 if (__last1 - __first1 != __last2 - __first2)
736 return false;
737 // Fall back to the 3 legged algorithm
738 using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>;
739 return _Equal3Leg()(
740 __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred));
741 } else {
742 // If we don't have random access, fall back to the serial algorithm cause we can't do much
743 return std::equal(
744 std::move(__first1),
745 std::move(__last1),
746 std::move(__first2),
747 std::move(__last2),
748 std::forward<_Predicate>(__pred));
749 }
750 }
751};
752
753template <class _ExecutionPolicy>
754struct __reduce<__default_backend_tag, _ExecutionPolicy> {
755 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation>
756 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp>
757 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op)
758 const noexcept {
759 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
760 return _TransformReduce()(
761 __policy,
762 std::move(__first),
763 std::move(__last),
764 std::move(__init),
765 std::forward<_BinaryOperation>(__op),
766 __identity{});
767 }
768};
769
770//////////////////////////////////////////////////////////////
771// transform family
772//////////////////////////////////////////////////////////////
773template <class _ExecutionPolicy>
774struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> {
775 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp>
776 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
777 operator()(_Policy&& __policy,
778 _ForwardIterator __first,
779 _ForwardIterator __last,
780 _ForwardOutIterator __out_it,
781 _Pred&& __pred,
782 _Tp const& __new_value) const noexcept {
783 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
784 using _Ref = __iterator_reference<_ForwardIterator>;
785 auto __res =
786 _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) {
787 return __pred(__element) ? __new_value : __element;
788 });
789 if (__res == nullopt)
790 return nullopt;
791 return __empty{};
792 }
793};
794
795template <class _ExecutionPolicy>
796struct __replace_copy<__default_backend_tag, _ExecutionPolicy> {
797 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp>
798 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
799 operator()(_Policy&& __policy,
800 _ForwardIterator __first,
801 _ForwardIterator __last,
802 _ForwardOutIterator __out_it,
803 _Tp const& __old_value,
804 _Tp const& __new_value) const noexcept {
805 using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>;
806 using _Ref = __iterator_reference<_ForwardIterator>;
807 return _ReplaceCopyIf()(
808 __policy,
809 std::move(__first),
810 std::move(__last),
811 std::move(__out_it),
812 [&](_Ref __element) { return __element == __old_value; },
813 __new_value);
814 }
815};
816
817// TODO: Use the std::copy/move shenanigans to forward to std::memmove
818// Investigate whether we want to still forward to std::transform(policy)
819// in that case for the execution::par part, or whether we actually want
820// to run everything serially in that case.
821template <class _ExecutionPolicy>
822struct __move<__default_backend_tag, _ExecutionPolicy> {
823 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
824 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
825 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
826 const noexcept {
827 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
828 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) {
829 return std::move(__element);
830 });
831 }
832};
833
834// TODO: Use the std::copy/move shenanigans to forward to std::memmove
835template <class _ExecutionPolicy>
836struct __copy<__default_backend_tag, _ExecutionPolicy> {
837 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
838 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
839 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
840 const noexcept {
841 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
842 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity());
843 }
844};
845
846template <class _ExecutionPolicy>
847struct __copy_n<__default_backend_tag, _ExecutionPolicy> {
848 template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator>
849 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
850 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept {
851 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
852 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
853 _ForwardIterator __last = __first + __n;
854 return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it));
855 } else {
856 // Otherwise, use the serial algorithm to avoid doing two passes over the input
857 return std::copy_n(std::move(__first), __n, std::move(__out_it));
858 }
859 }
860};
861
862template <class _ExecutionPolicy>
863struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> {
864 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
865 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
866 operator()(_Policy&& __policy,
867 _ForwardIterator __first,
868 _ForwardIterator __middle,
869 _ForwardIterator __last,
870 _ForwardOutIterator __out_it) const noexcept {
871 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
872 auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it));
873 if (__result_mid == nullopt)
874 return nullopt;
875 return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid));
876 }
877};
878
879template <class _ExecutionPolicy>
880struct __reverse_copy<__default_backend_tag, _ExecutionPolicy> {
881 template <class _Policy, class _BidirectionalIterator, class _ForwardIterator>
882 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
883 operator()(_Policy&& __policy,
884 _BidirectionalIterator __first,
885 _BidirectionalIterator __last,
886 _ForwardIterator __result) const noexcept {
887 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
888 return _Copy()(__policy,
889 std::reverse_iterator<_BidirectionalIterator>(std::move(__last)),
890 std::reverse_iterator<_BidirectionalIterator>(std::move(__first)),
891 std::move(__result));
892 }
893};
894
895template <class _ExecutionPolicy>
896struct __adjacent_difference<__default_backend_tag, _ExecutionPolicy> {
897 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
898 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2>
899 operator()(_Policy&& __policy,
900 _ForwardIterator1 __first1,
901 _ForwardIterator1 __last1,
902 _ForwardIterator2 __result,
903 _BinaryOperation&& __op) const noexcept {
904 using _TransformBinary = __dispatch<__transform_binary, __current_configuration, _ExecutionPolicy>;
905 if (__first1 == __last1)
906 return __result; // edge case: empty input range, just return the output iterator
907 *__result = *__first1;
908 ++__result;
909 _ForwardIterator1 __first2 = std::next(__first1);
910 if (__first2 == __last1)
911 return __result; // edge case: not enough elements to perform adjacent difference, just return the output
912 // iterator
913 // Process as a binary transform of two iterator ranges: [__first1 + 1, __last1) and [__first1, __last1 - 1)
914 return _TransformBinary()(
915 __policy,
916 std::move(__first2),
917 std::move(__last1),
918 std::move(__first1),
919 std::move(__result),
920 std::forward<_BinaryOperation>(__op));
921 }
922};
923
924//////////////////////////////////////////////////////////////
925// uninitialized_copy family
926//////////////////////////////////////////////////////////////
927
928template <class _ExecutionPolicy>
929struct __uninitialized_copy_n<__default_backend_tag, _ExecutionPolicy> {
930 template <class _Policy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
931 optional<_ForwardIterator2>
932 operator()(_Policy&& __policy, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) const noexcept {
933 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
934 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
935 using _UninitializedCopy = __dispatch<__uninitialized_copy, __current_configuration, _ExecutionPolicy>;
936 _ForwardIterator1 __last = __first + __n;
937 return _UninitializedCopy()(__policy, std::move(__first), std::move(__last), std::move(__result));
938 } else {
939 return std::uninitialized_copy_n(std::move(__first), __n, std::move(__result));
940 }
941 }
942};
943
944//////////////////////////////////////////////////////////////
945// uninitialized_move family
946//////////////////////////////////////////////////////////////
947
948template <class _ExecutionPolicy>
949struct __uninitialized_move_n<__default_backend_tag, _ExecutionPolicy> {
950 template <class _Policy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
951 optional<pair<_ForwardIterator1, _ForwardIterator2>>
952 operator()(_Policy&& __policy, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) const noexcept {
953 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
954 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
955 using _UninitializedMove = __dispatch<__uninitialized_move, __current_configuration, _ExecutionPolicy>;
956 _ForwardIterator1 __last = __first + __n;
957 auto __res = _UninitializedMove()(__policy, std::move(__first), __last, std::move(__result));
958 if (!__res)
959 return nullopt; // Failed to run the parallel algorithm, propagate the failure
960 return pair{__last, *__res};
961 } else {
962 return std::uninitialized_move_n(std::move(__first), __n, std::move(__result));
963 }
964 }
965};
966
967} // namespace __pstl
968_LIBCPP_END_NAMESPACE_STD
969
970#endif // _LIBCPP_STD_VER >= 17
971
972_LIBCPP_POP_MACROS
973
974#endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H
975