1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___PSTL_BACKENDS_SERIAL_H
11#define _LIBCPP___PSTL_BACKENDS_SERIAL_H
12
13#include <__algorithm/copy_if.h>
14#include <__algorithm/find_end.h>
15#include <__algorithm/find_if.h>
16#include <__algorithm/for_each.h>
17#include <__algorithm/includes.h>
18#include <__algorithm/is_heap_until.h>
19#include <__algorithm/merge.h>
20#include <__algorithm/min_element.h>
21#include <__algorithm/minmax_element.h>
22#include <__algorithm/mismatch.h>
23#include <__algorithm/partition.h>
24#include <__algorithm/partition_copy.h>
25#include <__algorithm/reverse.h>
26#include <__algorithm/search.h>
27#include <__algorithm/search_n.h>
28#include <__algorithm/set_difference.h>
29#include <__algorithm/set_intersection.h>
30#include <__algorithm/set_symmetric_difference.h>
31#include <__algorithm/set_union.h>
32#include <__algorithm/stable_partition.h>
33#include <__algorithm/stable_sort.h>
34#include <__algorithm/swap_ranges.h>
35#include <__algorithm/transform.h>
36#include <__config>
37#include <__memory/uninitialized_algorithms.h>
38#include <__numeric/transform_inclusive_scan.h>
39#include <__numeric/transform_reduce.h>
40#include <__optional/optional.h>
41#include <__pstl/backend_fwd.h>
42#include <__utility/empty.h>
43#include <__utility/forward.h>
44#include <__utility/move.h>
45#include <__utility/pair.h>
46
47#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
48# pragma GCC system_header
49#endif
50
51_LIBCPP_PUSH_MACROS
52#include <__undef_macros>
53
54#if _LIBCPP_STD_VER >= 17
55
56_LIBCPP_BEGIN_NAMESPACE_STD
57namespace __pstl {
58
59//
60// This partial PSTL backend runs everything serially.
61//
62// TODO: Right now, the serial backend must be used with another backend
63// like the "default backend" because it doesn't implement all the
64// necessary PSTL operations. It would be better to dispatch all
65// algorithms to their serial counterpart directly, since this can
66// often be more efficient than the "default backend"'s implementation
67// if we end up running serially anyways.
68//
69
70template <class _ExecutionPolicy>
71struct __find_end<__serial_backend_tag, _ExecutionPolicy> {
72 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
73 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
74 operator()(_Policy&&,
75 _ForwardIterator1 __first1,
76 _ForwardIterator1 __last1,
77 _ForwardIterator2 __first2,
78 _ForwardIterator2 __last2,
79 _BinaryPredicate __pred) const noexcept {
80 return std::find_end(
81 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::move(__pred));
82 }
83};
84
85template <class _ExecutionPolicy>
86struct __find_if<__serial_backend_tag, _ExecutionPolicy> {
87 template <class _Policy, class _ForwardIterator, class _Pred>
88 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
89 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
90 return std::find_if(std::move(__first), std::move(__last), std::forward<_Pred>(__pred));
91 }
92};
93
94template <class _ExecutionPolicy>
95struct __mismatch<__serial_backend_tag, _ExecutionPolicy> {
96 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
97 _LIBCPP_HIDE_FROM_ABI optional<pair<_ForwardIterator1, _ForwardIterator2>>
98 operator()(_Policy&&,
99 _ForwardIterator1 __first1,
100 _ForwardIterator1 __last1,
101 _ForwardIterator2 __first2,
102 _ForwardIterator2 __last2,
103 _Predicate&& __pred) const noexcept {
104 return std::mismatch(
105 std::move(__first1),
106 std::move(__last1),
107 std::move(__first2),
108 std::move(__last2),
109 std::forward<_Predicate>(__pred));
110 }
111};
112
113template <class _ExecutionPolicy>
114struct __for_each<__serial_backend_tag, _ExecutionPolicy> {
115 template <class _Policy, class _ForwardIterator, class _Function>
116 _LIBCPP_HIDE_FROM_ABI optional<__empty>
117 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Function&& __func) const noexcept {
118 std::for_each(std::move(__first), std::move(__last), std::forward<_Function>(__func));
119 return __empty{};
120 }
121};
122
123template <class _Backend, class _RawExecutionPolicy>
124struct __is_heap_until {
125 template <class _Policy, class _RandomAccessIterator, class _Comp>
126 _LIBCPP_HIDE_FROM_ABI optional<_RandomAccessIterator>
127 operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) const noexcept {
128 return std::is_heap_until(std::move(__first), std::move(__last), std::move(__comp));
129 }
130};
131
132template <class _ExecutionPolicy>
133struct __merge<__serial_backend_tag, _ExecutionPolicy> {
134 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp>
135 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()(
136 _Policy&&,
137 _ForwardIterator1 __first1,
138 _ForwardIterator1 __last1,
139 _ForwardIterator2 __first2,
140 _ForwardIterator2 __last2,
141 _ForwardOutIterator __outit,
142 _Comp&& __comp) const noexcept {
143 return std::merge(
144 std::move(__first1),
145 std::move(__last1),
146 std::move(__first2),
147 std::move(__last2),
148 std::move(__outit),
149 std::forward<_Comp>(__comp));
150 }
151};
152
153template <class _ExecutionPolicy>
154struct __min_element<__serial_backend_tag, _ExecutionPolicy> {
155 template <class _Policy, class _ForwardIterator, class _Compare>
156 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
157 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) const noexcept {
158 return std::min_element(std::move(__first), std::move(__last), std::move(__comp));
159 }
160};
161
162template <class _ExecutionPolicy>
163struct __minmax_element<__serial_backend_tag, _ExecutionPolicy> {
164 template <class _Policy, class _ForwardIterator, class _Compare>
165 _LIBCPP_HIDE_FROM_ABI optional<pair<_ForwardIterator, _ForwardIterator>>
166 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) const noexcept {
167 return std::minmax_element(std::move(__first), std::move(__last), std::move(__comp));
168 }
169};
170
171template <class _ExecutionPolicy>
172struct __reverse<__serial_backend_tag, _ExecutionPolicy> {
173 template <class _Policy, class _BidirectionalIterator>
174 _LIBCPP_HIDE_FROM_ABI optional<__empty>
175 operator()(_Policy&&, _BidirectionalIterator __first, _BidirectionalIterator __last) const noexcept {
176 std::reverse(std::move(__first), std::move(__last));
177 return __empty{};
178 }
179};
180
181template <class _ExecutionPolicy>
182struct __search<__serial_backend_tag, _ExecutionPolicy> {
183 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
184 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
185 operator()(_Policy&&,
186 _ForwardIterator1 __first1,
187 _ForwardIterator1 __last1,
188 _ForwardIterator2 __first2,
189 _ForwardIterator2 __last2,
190 _BinaryPredicate __pred) const noexcept {
191 return std::search(
192 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::move(__pred));
193 }
194};
195
196template <class _ExecutionPolicy>
197struct __search_n<__serial_backend_tag, _ExecutionPolicy> {
198 template <class _Policy, class _ForwardIterator, class _Size, class _Tp, class _Predicate>
199 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
200 operator()(_Policy&&,
201 _ForwardIterator __first,
202 _ForwardIterator __last,
203 _Size __count,
204 const _Tp& __value,
205 _Predicate __pred) const noexcept {
206 return std::search_n(std::move(__first), std::move(__last), __count, __value, std::move(__pred));
207 }
208};
209
210template <class _ExecutionPolicy>
211struct __stable_sort<__serial_backend_tag, _ExecutionPolicy> {
212 template <class _Policy, class _RandomAccessIterator, class _Comp>
213 _LIBCPP_HIDE_FROM_ABI optional<__empty>
214 operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
215 std::stable_sort(std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
216 return __empty{};
217 }
218};
219
220template <class _ExecutionPolicy>
221struct __swap_ranges<__serial_backend_tag, _ExecutionPolicy> {
222 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2>
223 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2> operator()(
224 _Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) const noexcept {
225 return std::swap_ranges(std::move(__first1), std::move(__last1), std::move(__first2));
226 }
227};
228
229template <class _ExecutionPolicy>
230struct __transform<__serial_backend_tag, _ExecutionPolicy> {
231 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation>
232 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()(
233 _Policy&&, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __outit, _UnaryOperation&& __op)
234 const noexcept {
235 return std::transform(
236 std::move(__first), std::move(__last), std::move(__outit), std::forward<_UnaryOperation>(__op));
237 }
238};
239
240template <class _ExecutionPolicy>
241struct __transform_binary<__serial_backend_tag, _ExecutionPolicy> {
242 template <class _Policy,
243 class _ForwardIterator1,
244 class _ForwardIterator2,
245 class _ForwardOutIterator,
246 class _BinaryOperation>
247 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
248 operator()(_Policy&&,
249 _ForwardIterator1 __first1,
250 _ForwardIterator1 __last1,
251 _ForwardIterator2 __first2,
252 _ForwardOutIterator __outit,
253 _BinaryOperation&& __op) const noexcept {
254 return std::transform(
255 std::move(__first1),
256 std::move(__last1),
257 std::move(__first2),
258 std::move(__outit),
259 std::forward<_BinaryOperation>(__op));
260 }
261};
262
263template <class _ExecutionPolicy>
264struct __transform_inclusive_scan_init<__serial_backend_tag, _ExecutionPolicy> {
265 template <class _Policy,
266 class _ForwardIterator1,
267 class _ForwardIterator2,
268 class _BinaryOperation,
269 class _UnaryOperation,
270 class _Tp>
271 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2> operator()(
272 _Policy&&,
273 _ForwardIterator1 __first,
274 _ForwardIterator1 __last,
275 _ForwardIterator2 __result,
276 _BinaryOperation __reduce,
277 _UnaryOperation __transform,
278 _Tp __init) const noexcept {
279 return std::transform_inclusive_scan(
280 std::move(__first),
281 std::move(__last),
282 std::move(__result),
283 std::move(__reduce),
284 std::move(__transform),
285 std::move(__init));
286 }
287};
288
289template <class _ExecutionPolicy>
290struct __transform_reduce<__serial_backend_tag, _ExecutionPolicy> {
291 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
292 _LIBCPP_HIDE_FROM_ABI optional<_Tp>
293 operator()(_Policy&&,
294 _ForwardIterator __first,
295 _ForwardIterator __last,
296 _Tp __init,
297 _BinaryOperation&& __reduce,
298 _UnaryOperation&& __transform) const noexcept {
299 return std::transform_reduce(
300 std::move(__first),
301 std::move(__last),
302 std::move(__init),
303 std::forward<_BinaryOperation>(__reduce),
304 std::forward<_UnaryOperation>(__transform));
305 }
306};
307
308template <class _ExecutionPolicy>
309struct __transform_reduce_binary<__serial_backend_tag, _ExecutionPolicy> {
310 template <class _Policy,
311 class _ForwardIterator1,
312 class _ForwardIterator2,
313 class _Tp,
314 class _BinaryOperation1,
315 class _BinaryOperation2>
316 _LIBCPP_HIDE_FROM_ABI optional<_Tp> operator()(
317 _Policy&&,
318 _ForwardIterator1 __first1,
319 _ForwardIterator1 __last1,
320 _ForwardIterator2 __first2,
321 _Tp __init,
322 _BinaryOperation1&& __reduce,
323 _BinaryOperation2&& __transform) const noexcept {
324 return std::transform_reduce(
325 std::move(__first1),
326 std::move(__last1),
327 std::move(__first2),
328 std::move(__init),
329 std::forward<_BinaryOperation1>(__reduce),
330 std::forward<_BinaryOperation2>(__transform));
331 }
332};
333
334template <class _ExecutionPolicy>
335struct __uninitialized_copy<__serial_backend_tag, _ExecutionPolicy> {
336 template <class _Policy, class _InputIterator, class _ForwardIterator>
337 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
338 operator()(_Policy&&, _InputIterator __first, _InputIterator __last, _ForwardIterator __result) const noexcept {
339 return std::uninitialized_copy(std::move(__first), std::move(__last), std::move(__result));
340 }
341};
342
343template <class _ExecutionPolicy>
344struct __uninitialized_move<__serial_backend_tag, _ExecutionPolicy> {
345 template <class _Policy, class _InputIterator, class _ForwardIterator>
346 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
347 operator()(_Policy&&, _InputIterator __first, _InputIterator __last, _ForwardIterator __result) const noexcept {
348 return std::uninitialized_move(std::move(__first), std::move(__last), std::move(__result));
349 }
350};
351
352template <class _ExecutionPolicy>
353struct __includes<__serial_backend_tag, _ExecutionPolicy> {
354 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Compare>
355 optional<bool>
356 operator()(_Policy&&,
357 _ForwardIterator1 __first1,
358 _ForwardIterator1 __last1,
359 _ForwardIterator2 __first2,
360 _ForwardIterator2 __last2,
361 _Compare __comp) const noexcept {
362 return std::includes(
363 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::move(__comp));
364 }
365};
366
367template <class _ExecutionPolicy>
368struct __set_difference<__serial_backend_tag, _ExecutionPolicy> {
369 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Compare>
370 optional<_ForwardOutIterator> operator()(
371 _Policy&&,
372 _ForwardIterator1 __first1,
373 _ForwardIterator1 __last1,
374 _ForwardIterator2 __first2,
375 _ForwardIterator2 __last2,
376 _ForwardOutIterator __result,
377 _Compare __comp) const noexcept {
378 return std::set_difference(
379 std::move(__first1),
380 std::move(__last1),
381 std::move(__first2),
382 std::move(__last2),
383 std::move(__result),
384 std::move(__comp));
385 }
386};
387
388template <class _ExecutionPolicy>
389struct __set_symmetric_difference<__serial_backend_tag, _ExecutionPolicy> {
390 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Compare>
391 optional<_ForwardOutIterator> operator()(
392 _Policy&&,
393 _ForwardIterator1 __first1,
394 _ForwardIterator1 __last1,
395 _ForwardIterator2 __first2,
396 _ForwardIterator2 __last2,
397 _ForwardOutIterator __result,
398 _Compare __comp) const noexcept {
399 return std::set_symmetric_difference(
400 std::move(__first1),
401 std::move(__last1),
402 std::move(__first2),
403 std::move(__last2),
404 std::move(__result),
405 std::move(__comp));
406 }
407};
408
409template <class _ExecutionPolicy>
410struct __set_union<__serial_backend_tag, _ExecutionPolicy> {
411 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Compare>
412 optional<_ForwardOutIterator> operator()(
413 _Policy&&,
414 _ForwardIterator1 __first1,
415 _ForwardIterator1 __last1,
416 _ForwardIterator2 __first2,
417 _ForwardIterator2 __last2,
418 _ForwardOutIterator __result,
419 _Compare __comp) const noexcept {
420 return std::set_union(
421 std::move(__first1),
422 std::move(__last1),
423 std::move(__first2),
424 std::move(__last2),
425 std::move(__result),
426 std::move(__comp));
427 }
428};
429
430template <class _ExecutionPolicy>
431struct __set_intersection<__serial_backend_tag, _ExecutionPolicy> {
432 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Compare>
433 optional<_ForwardOutIterator> operator()(
434 _Policy&&,
435 _ForwardIterator1 __first1,
436 _ForwardIterator1 __last1,
437 _ForwardIterator2 __first2,
438 _ForwardIterator2 __last2,
439 _ForwardOutIterator __result,
440 _Compare __comp) const noexcept {
441 return std::set_intersection(
442 std::move(__first1),
443 std::move(__last1),
444 std::move(__first2),
445 std::move(__last2),
446 std::move(__result),
447 std::move(__comp));
448 }
449};
450
451template <class _ExecutionPolicy>
452struct __partition<__serial_backend_tag, _ExecutionPolicy> {
453 template <class _Policy, class _ForwardIterator, class _Predicate>
454 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
455 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept {
456 return std::partition(std::move(__first), std::move(__last), std::move(__pred));
457 }
458};
459
460template <class _ExecutionPolicy>
461struct __stable_partition<__serial_backend_tag, _ExecutionPolicy> {
462 template <class _Policy, class _BidirectionalIterator, class _Predicate>
463 optional<_BidirectionalIterator> operator()(
464 _Policy&&, _BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred) const noexcept {
465 return std::stable_partition(std::move(__first), std::move(__last), std::move(__pred));
466 }
467};
468
469template <class _ExecutionPolicy>
470struct __partition_copy<__serial_backend_tag, _ExecutionPolicy> {
471 template <class _Policy,
472 class _ForwardIterator,
473 class _ForwardOutIterator1,
474 class _ForwardOutIterator2,
475 class _Predicate>
476 optional<pair<_ForwardOutIterator1, _ForwardOutIterator2>>
477 operator()(_Policy&&,
478 _ForwardIterator __first,
479 _ForwardIterator __last,
480 _ForwardOutIterator1 __out_true,
481 _ForwardOutIterator2 __out_false,
482 _Predicate __pred) const noexcept {
483 return std::partition_copy(
484 std::move(__first), std::move(__last), std::move(__out_true), std::move(__out_false), std::move(__pred));
485 }
486};
487
488template <class _ExecutionPolicy>
489struct __copy_if<__serial_backend_tag, _ExecutionPolicy> {
490 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Predicate>
491 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()(
492 _Policy&&, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __out_it, _Predicate __pred)
493 const noexcept {
494 return std::copy_if(std::move(__first), std::move(__last), std::move(__out_it), std::move(__pred));
495 }
496};
497
498} // namespace __pstl
499_LIBCPP_END_NAMESPACE_STD
500
501#endif // _LIBCPP_STD_VER >= 17
502
503_LIBCPP_POP_MACROS
504
505#endif // _LIBCPP___PSTL_BACKENDS_SERIAL_H
506