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