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<__empty> 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<__empty>
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 return _ForEach()(__policy, std::move(__first), std::move(__last), std::move(__func));
486 } else {
487 // Otherwise, use the serial algorithm to avoid doing two passes over the input
488 std::for_each_n(std::move(__first), __size, std::move(__func));
489 return __empty{};
490 }
491 }
492};
493
494template <class _ExecutionPolicy>
495struct __fill<__default_backend_tag, _ExecutionPolicy> {
496 template <class _Policy, class _ForwardIterator, class _Tp>
497 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
498 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
499 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
500 using _Ref = __iterator_reference<_ForwardIterator>;
501 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __value; });
502 }
503};
504
505template <class _ExecutionPolicy>
506struct __fill_n<__default_backend_tag, _ExecutionPolicy> {
507 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
508 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
509 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept {
510 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
511 using _Fill = __dispatch<__fill, __current_configuration, _ExecutionPolicy>;
512 _ForwardIterator __last = __first + __n;
513 return _Fill()(__policy, std::move(__first), std::move(__last), __value);
514 } else {
515 // Otherwise, use the serial algorithm to avoid doing two passes over the input
516 std::fill_n(std::move(__first), __n, __value);
517 return optional<__empty>{__empty{}};
518 }
519 }
520};
521
522template <class _ExecutionPolicy>
523struct __replace<__default_backend_tag, _ExecutionPolicy> {
524 template <class _Policy, class _ForwardIterator, class _Tp>
525 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
526 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __old, _Tp const& __new)
527 const noexcept {
528 using _ReplaceIf = __dispatch<__replace_if, __current_configuration, _ExecutionPolicy>;
529 using _Ref = __iterator_reference<_ForwardIterator>;
530 return _ReplaceIf()(
531 __policy, std::move(__first), std::move(__last), [&](_Ref __element) { return __element == __old; }, __new);
532 }
533};
534
535template <class _ExecutionPolicy>
536struct __replace_if<__default_backend_tag, _ExecutionPolicy> {
537 template <class _Policy, class _ForwardIterator, class _Pred, class _Tp>
538 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
539 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred, _Tp const& __new_value)
540 const noexcept {
541 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
542 using _Ref = __iterator_reference<_ForwardIterator>;
543 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) {
544 if (__pred(__element))
545 __element = __new_value;
546 });
547 }
548};
549
550template <class _ExecutionPolicy>
551struct __generate<__default_backend_tag, _ExecutionPolicy> {
552 template <class _Policy, class _ForwardIterator, class _Generator>
553 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
554 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator&& __gen) const noexcept {
555 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
556 using _Ref = __iterator_reference<_ForwardIterator>;
557 return _ForEach()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) { __element = __gen(); });
558 }
559};
560
561template <class _ExecutionPolicy>
562struct __generate_n<__default_backend_tag, _ExecutionPolicy> {
563 template <class _Policy, class _ForwardIterator, class _Size, class _Generator>
564 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
565 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _Generator&& __gen) const noexcept {
566 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
567 using _Ref = __iterator_reference<_ForwardIterator>;
568 return _ForEachN()(__policy, std::move(__first), __n, [&](_Ref __element) { __element = __gen(); });
569 }
570};
571
572template <class _ExecutionPolicy>
573struct __uninitialized_default_construct<__default_backend_tag, _ExecutionPolicy> {
574 template <class _Policy, class _ForwardIterator>
575 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
576 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept {
577 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
578 using _ValueType = __iterator_value_type<_ForwardIterator>;
579 using _Ref = __iterator_reference<_ForwardIterator>;
580 return _ForEach()(__policy, std::move(__first), std::move(__last), [](_Ref __element) {
581 ::new (static_cast<void*>(std::addressof(__element))) _ValueType;
582 });
583 }
584};
585
586template <class _ExecutionPolicy>
587struct __uninitialized_default_construct_n<__default_backend_tag, _ExecutionPolicy> {
588 template <class _Policy, class _ForwardIterator, class _Size>
589 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
590 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept {
591 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
592 using _ValueType = __iterator_value_type<_ForwardIterator>;
593 using _Ref = __iterator_reference<_ForwardIterator>;
594 return _ForEachN()(__policy, std::move(__first), __n, [](_Ref __element) {
595 ::new (static_cast<void*>(std::addressof(__element))) _ValueType;
596 });
597 }
598};
599
600template <class _ExecutionPolicy>
601struct __uninitialized_value_construct<__default_backend_tag, _ExecutionPolicy> {
602 template <class _Policy, class _ForwardIterator>
603 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
604 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept {
605 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
606 using _ValueType = __iterator_value_type<_ForwardIterator>;
607 using _Ref = __iterator_reference<_ForwardIterator>;
608 return _ForEach()(__policy, std::move(__first), std::move(__last), [](_Ref __element) {
609 ::new (static_cast<void*>(std::addressof(__element))) _ValueType();
610 });
611 }
612};
613
614template <class _ExecutionPolicy>
615struct __uninitialized_value_construct_n<__default_backend_tag, _ExecutionPolicy> {
616 template <class _Policy, class _ForwardIterator, class _Size>
617 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
618 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept {
619 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
620 using _ValueType = __iterator_value_type<_ForwardIterator>;
621 using _Ref = __iterator_reference<_ForwardIterator>;
622 return _ForEachN()(__policy, std::move(__first), __n, [](_Ref __element) {
623 ::new (static_cast<void*>(std::addressof(__element))) _ValueType();
624 });
625 }
626};
627
628template <class _ExecutionPolicy>
629struct __uninitialized_fill<__default_backend_tag, _ExecutionPolicy> {
630 template <class _Policy, class _ForwardIterator, class _Tp>
631 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
632 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept {
633 using _ForEach = __dispatch<__for_each, __current_configuration, _ExecutionPolicy>;
634 using _ValueType = __iterator_value_type<_ForwardIterator>;
635 using _Ref = __iterator_reference<_ForwardIterator>;
636 return _ForEach()(__policy, std::move(__first), std::move(__last), [&__value](_Ref __element) {
637 ::new (static_cast<void*>(std::addressof(__element))) _ValueType(__value);
638 });
639 }
640};
641
642template <class _ExecutionPolicy>
643struct __uninitialized_fill_n<__default_backend_tag, _ExecutionPolicy> {
644 template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
645 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
646 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, const _Tp& __value) const noexcept {
647 using _ForEachN = __dispatch<__for_each_n, __current_configuration, _ExecutionPolicy>;
648 using _ValueType = __iterator_value_type<_ForwardIterator>;
649 using _Ref = __iterator_reference<_ForwardIterator>;
650 return _ForEachN()(__policy, std::move(__first), __n, [&__value](_Ref __element) {
651 ::new (static_cast<void*>(std::addressof(__element))) _ValueType(__value);
652 });
653 }
654};
655
656//////////////////////////////////////////////////////////////
657// stable_sort family
658//////////////////////////////////////////////////////////////
659template <class _ExecutionPolicy>
660struct __sort<__default_backend_tag, _ExecutionPolicy> {
661 template <class _Policy, class _RandomAccessIterator, class _Comp>
662 _LIBCPP_HIDE_FROM_ABI optional<__empty> operator()(
663 _Policy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
664 using _StableSort = __dispatch<__stable_sort, __current_configuration, _ExecutionPolicy>;
665 return _StableSort()(__policy, std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
666 }
667};
668
669//////////////////////////////////////////////////////////////
670// transform_reduce family
671//////////////////////////////////////////////////////////////
672template <class _ExecutionPolicy>
673struct __count_if<__default_backend_tag, _ExecutionPolicy> {
674 template <class _Policy, class _ForwardIterator, class _Predicate>
675 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>> operator()(
676 _Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate&& __pred) const noexcept {
677 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
678 using _DiffT = __iterator_difference_type<_ForwardIterator>;
679 using _Ref = __iterator_reference<_ForwardIterator>;
680 return _TransformReduce()(
681 __policy, std::move(__first), std::move(__last), _DiffT{}, std::plus{}, [&](_Ref __element) -> _DiffT {
682 return __pred(__element) ? _DiffT(1) : _DiffT(0);
683 });
684 }
685};
686
687template <class _ExecutionPolicy>
688struct __count<__default_backend_tag, _ExecutionPolicy> {
689 template <class _Policy, class _ForwardIterator, class _Tp>
690 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iterator_difference_type<_ForwardIterator>>
691 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept {
692 using _CountIf = __dispatch<__count_if, __current_configuration, _ExecutionPolicy>;
693 using _Ref = __iterator_reference<_ForwardIterator>;
694 return _CountIf()(__policy, std::move(__first), std::move(__last), [&](_Ref __element) -> bool {
695 return __element == __value;
696 });
697 }
698};
699
700template <class _ExecutionPolicy>
701struct __equal_3leg<__default_backend_tag, _ExecutionPolicy> {
702 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
703 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
704 operator()(_Policy&& __policy,
705 _ForwardIterator1 __first1,
706 _ForwardIterator1 __last1,
707 _ForwardIterator2 __first2,
708 _Predicate&& __pred) const noexcept {
709 using _TransformReduce = __dispatch<__transform_reduce_binary, __current_configuration, _ExecutionPolicy>;
710 return _TransformReduce()(
711 __policy,
712 std::move(__first1),
713 std::move(__last1),
714 std::move(__first2),
715 true,
716 std::logical_and{},
717 std::forward<_Predicate>(__pred));
718 }
719};
720
721template <class _ExecutionPolicy>
722struct __equal<__default_backend_tag, _ExecutionPolicy> {
723 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
724 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
725 operator()(_Policy&& __policy,
726 _ForwardIterator1 __first1,
727 _ForwardIterator1 __last1,
728 _ForwardIterator2 __first2,
729 _ForwardIterator2 __last2,
730 _Predicate&& __pred) const noexcept {
731 if constexpr (__has_random_access_iterator_category<_ForwardIterator1>::value &&
732 __has_random_access_iterator_category<_ForwardIterator2>::value) {
733 if (__last1 - __first1 != __last2 - __first2)
734 return false;
735 // Fall back to the 3 legged algorithm
736 using _Equal3Leg = __dispatch<__equal_3leg, __current_configuration, _ExecutionPolicy>;
737 return _Equal3Leg()(
738 __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::forward<_Predicate>(__pred));
739 } else {
740 // If we don't have random access, fall back to the serial algorithm cause we can't do much
741 return std::equal(
742 std::move(__first1),
743 std::move(__last1),
744 std::move(__first2),
745 std::move(__last2),
746 std::forward<_Predicate>(__pred));
747 }
748 }
749};
750
751template <class _ExecutionPolicy>
752struct __reduce<__default_backend_tag, _ExecutionPolicy> {
753 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation>
754 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_Tp>
755 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation&& __op)
756 const noexcept {
757 using _TransformReduce = __dispatch<__transform_reduce, __current_configuration, _ExecutionPolicy>;
758 return _TransformReduce()(
759 __policy,
760 std::move(__first),
761 std::move(__last),
762 std::move(__init),
763 std::forward<_BinaryOperation>(__op),
764 __identity{});
765 }
766};
767
768//////////////////////////////////////////////////////////////
769// transform family
770//////////////////////////////////////////////////////////////
771template <class _ExecutionPolicy>
772struct __replace_copy_if<__default_backend_tag, _ExecutionPolicy> {
773 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Pred, class _Tp>
774 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
775 operator()(_Policy&& __policy,
776 _ForwardIterator __first,
777 _ForwardIterator __last,
778 _ForwardOutIterator __out_it,
779 _Pred&& __pred,
780 _Tp const& __new_value) const noexcept {
781 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
782 using _Ref = __iterator_reference<_ForwardIterator>;
783 auto __res =
784 _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](_Ref __element) {
785 return __pred(__element) ? __new_value : __element;
786 });
787 if (__res == nullopt)
788 return nullopt;
789 return __empty{};
790 }
791};
792
793template <class _ExecutionPolicy>
794struct __replace_copy<__default_backend_tag, _ExecutionPolicy> {
795 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp>
796 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
797 operator()(_Policy&& __policy,
798 _ForwardIterator __first,
799 _ForwardIterator __last,
800 _ForwardOutIterator __out_it,
801 _Tp const& __old_value,
802 _Tp const& __new_value) const noexcept {
803 using _ReplaceCopyIf = __dispatch<__replace_copy_if, __current_configuration, _ExecutionPolicy>;
804 using _Ref = __iterator_reference<_ForwardIterator>;
805 return _ReplaceCopyIf()(
806 __policy,
807 std::move(__first),
808 std::move(__last),
809 std::move(__out_it),
810 [&](_Ref __element) { return __element == __old_value; },
811 __new_value);
812 }
813};
814
815// TODO: Use the std::copy/move shenanigans to forward to std::memmove
816// Investigate whether we want to still forward to std::transform(policy)
817// in that case for the execution::par part, or whether we actually want
818// to run everything serially in that case.
819template <class _ExecutionPolicy>
820struct __move<__default_backend_tag, _ExecutionPolicy> {
821 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
822 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
823 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
824 const noexcept {
825 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
826 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), [&](auto&& __element) {
827 return std::move(__element);
828 });
829 }
830};
831
832// TODO: Use the std::copy/move shenanigans to forward to std::memmove
833template <class _ExecutionPolicy>
834struct __copy<__default_backend_tag, _ExecutionPolicy> {
835 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
836 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
837 operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it)
838 const noexcept {
839 using _Transform = __dispatch<__transform, __current_configuration, _ExecutionPolicy>;
840 return _Transform()(__policy, std::move(__first), std::move(__last), std::move(__out_it), __identity());
841 }
842};
843
844template <class _ExecutionPolicy>
845struct __copy_n<__default_backend_tag, _ExecutionPolicy> {
846 template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator>
847 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
848 operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept {
849 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
850 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
851 _ForwardIterator __last = __first + __n;
852 return _Copy()(__policy, std::move(__first), std::move(__last), std::move(__out_it));
853 } else {
854 // Otherwise, use the serial algorithm to avoid doing two passes over the input
855 return std::copy_n(std::move(__first), __n, std::move(__out_it));
856 }
857 }
858};
859
860template <class _ExecutionPolicy>
861struct __rotate_copy<__default_backend_tag, _ExecutionPolicy> {
862 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
863 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
864 operator()(_Policy&& __policy,
865 _ForwardIterator __first,
866 _ForwardIterator __middle,
867 _ForwardIterator __last,
868 _ForwardOutIterator __out_it) const noexcept {
869 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
870 auto __result_mid = _Copy()(__policy, __middle, std::move(__last), std::move(__out_it));
871 if (__result_mid == nullopt)
872 return nullopt;
873 return _Copy()(__policy, std::move(__first), std::move(__middle), *std::move(__result_mid));
874 }
875};
876
877template <class _ExecutionPolicy>
878struct __reverse_copy<__default_backend_tag, _ExecutionPolicy> {
879 template <class _Policy, class _BidirectionalIterator, class _ForwardIterator>
880 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
881 operator()(_Policy&& __policy,
882 _BidirectionalIterator __first,
883 _BidirectionalIterator __last,
884 _ForwardIterator __result) const noexcept {
885 using _Copy = __dispatch<__copy, __current_configuration, _ExecutionPolicy>;
886 return _Copy()(__policy,
887 std::reverse_iterator<_BidirectionalIterator>(std::move(__last)),
888 std::reverse_iterator<_BidirectionalIterator>(std::move(__first)),
889 std::move(__result));
890 }
891};
892
893template <class _ExecutionPolicy>
894struct __adjacent_difference<__default_backend_tag, _ExecutionPolicy> {
895 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
896 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2>
897 operator()(_Policy&& __policy,
898 _ForwardIterator1 __first1,
899 _ForwardIterator1 __last1,
900 _ForwardIterator2 __result,
901 _BinaryOperation&& __op) const noexcept {
902 using _TransformBinary = __dispatch<__transform_binary, __current_configuration, _ExecutionPolicy>;
903 if (__first1 == __last1)
904 return __result; // edge case: empty input range, just return the output iterator
905 *__result = *__first1;
906 ++__result;
907 _ForwardIterator1 __first2 = std::next(__first1);
908 if (__first2 == __last1)
909 return __result; // edge case: not enough elements to perform adjacent difference, just return the output
910 // iterator
911 // Process as a binary transform of two iterator ranges: [__first1 + 1, __last1) and [__first1, __last1 - 1)
912 return _TransformBinary()(
913 __policy,
914 std::move(__first2),
915 std::move(__last1),
916 std::move(__first1),
917 std::move(__result),
918 std::forward<_BinaryOperation>(__op));
919 }
920};
921
922//////////////////////////////////////////////////////////////
923// uninitialized_copy family
924//////////////////////////////////////////////////////////////
925
926template <class _ExecutionPolicy>
927struct __uninitialized_copy_n<__default_backend_tag, _ExecutionPolicy> {
928 template <class _Policy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
929 optional<_ForwardIterator2>
930 operator()(_Policy&& __policy, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) const noexcept {
931 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
932 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
933 using _UninitializedCopy = __dispatch<__uninitialized_copy, __current_configuration, _ExecutionPolicy>;
934 _ForwardIterator1 __last = __first + __n;
935 return _UninitializedCopy()(__policy, std::move(__first), std::move(__last), std::move(__result));
936 } else {
937 return std::uninitialized_copy_n(std::move(__first), __n, std::move(__result));
938 }
939 }
940};
941
942//////////////////////////////////////////////////////////////
943// uninitialized_move family
944//////////////////////////////////////////////////////////////
945
946template <class _ExecutionPolicy>
947struct __uninitialized_move_n<__default_backend_tag, _ExecutionPolicy> {
948 template <class _Policy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
949 optional<pair<_ForwardIterator1, _ForwardIterator2>>
950 operator()(_Policy&& __policy, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) const noexcept {
951 if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
952 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
953 using _UninitializedMove = __dispatch<__uninitialized_move, __current_configuration, _ExecutionPolicy>;
954 _ForwardIterator1 __last = __first + __n;
955 auto __res = _UninitializedMove()(__policy, std::move(__first), __last, std::move(__result));
956 if (!__res)
957 return nullopt; // Failed to run the parallel algorithm, propagate the failure
958 return pair{__last, *__res};
959 } else {
960 return std::uninitialized_move_n(std::move(__first), __n, std::move(__result));
961 }
962 }
963};
964
965} // namespace __pstl
966_LIBCPP_END_NAMESPACE_STD
967
968#endif // _LIBCPP_STD_VER >= 17
969
970_LIBCPP_POP_MACROS
971
972#endif // _LIBCPP___PSTL_BACKENDS_DEFAULT_H
973