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