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/find_end.h>
14#include <__algorithm/find_if.h>
15#include <__algorithm/for_each.h>
16#include <__algorithm/is_heap_until.h>
17#include <__algorithm/merge.h>
18#include <__algorithm/min_element.h>
19#include <__algorithm/minmax_element.h>
20#include <__algorithm/mismatch.h>
21#include <__algorithm/reverse.h>
22#include <__algorithm/search.h>
23#include <__algorithm/search_n.h>
24#include <__algorithm/stable_sort.h>
25#include <__algorithm/swap_ranges.h>
26#include <__algorithm/transform.h>
27#include <__config>
28#include <__memory/uninitialized_algorithms.h>
29#include <__numeric/transform_reduce.h>
30#include <__optional/optional.h>
31#include <__pstl/backend_fwd.h>
32#include <__utility/empty.h>
33#include <__utility/forward.h>
34#include <__utility/move.h>
35#include <__utility/pair.h>
36
37#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
38# pragma GCC system_header
39#endif
40
41_LIBCPP_PUSH_MACROS
42#include <__undef_macros>
43
44#if _LIBCPP_STD_VER >= 17
45
46_LIBCPP_BEGIN_NAMESPACE_STD
47namespace __pstl {
48
49//
50// This partial PSTL backend runs everything serially.
51//
52// TODO: Right now, the serial backend must be used with another backend
53// like the "default backend" because it doesn't implement all the
54// necessary PSTL operations. It would be better to dispatch all
55// algorithms to their serial counterpart directly, since this can
56// often be more efficient than the "default backend"'s implementation
57// if we end up running serially anyways.
58//
59
60template <class _ExecutionPolicy>
61struct __find_end<__serial_backend_tag, _ExecutionPolicy> {
62 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
63 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
64 operator()(_Policy&&,
65 _ForwardIterator1 __first1,
66 _ForwardIterator1 __last1,
67 _ForwardIterator2 __first2,
68 _ForwardIterator2 __last2,
69 _BinaryPredicate __pred) const noexcept {
70 return std::find_end(
71 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::move(__pred));
72 }
73};
74
75template <class _ExecutionPolicy>
76struct __find_if<__serial_backend_tag, _ExecutionPolicy> {
77 template <class _Policy, class _ForwardIterator, class _Pred>
78 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
79 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Pred&& __pred) const noexcept {
80 return std::find_if(std::move(__first), std::move(__last), std::forward<_Pred>(__pred));
81 }
82};
83
84template <class _ExecutionPolicy>
85struct __mismatch<__serial_backend_tag, _ExecutionPolicy> {
86 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
87 _LIBCPP_HIDE_FROM_ABI optional<pair<_ForwardIterator1, _ForwardIterator2>>
88 operator()(_Policy&&,
89 _ForwardIterator1 __first1,
90 _ForwardIterator1 __last1,
91 _ForwardIterator2 __first2,
92 _ForwardIterator2 __last2,
93 _Predicate&& __pred) const noexcept {
94 return std::mismatch(
95 std::move(__first1),
96 std::move(__last1),
97 std::move(__first2),
98 std::move(__last2),
99 std::forward<_Predicate>(__pred));
100 }
101};
102
103template <class _ExecutionPolicy>
104struct __for_each<__serial_backend_tag, _ExecutionPolicy> {
105 template <class _Policy, class _ForwardIterator, class _Function>
106 _LIBCPP_HIDE_FROM_ABI optional<__empty>
107 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Function&& __func) const noexcept {
108 std::for_each(std::move(__first), std::move(__last), std::forward<_Function>(__func));
109 return __empty{};
110 }
111};
112
113template <class _Backend, class _RawExecutionPolicy>
114struct __is_heap_until {
115 template <class _Policy, class _RandomAccessIterator, class _Comp>
116 _LIBCPP_HIDE_FROM_ABI optional<_RandomAccessIterator>
117 operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) const noexcept {
118 return std::is_heap_until(std::move(__first), std::move(__last), std::move(__comp));
119 }
120};
121
122template <class _ExecutionPolicy>
123struct __merge<__serial_backend_tag, _ExecutionPolicy> {
124 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp>
125 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()(
126 _Policy&&,
127 _ForwardIterator1 __first1,
128 _ForwardIterator1 __last1,
129 _ForwardIterator2 __first2,
130 _ForwardIterator2 __last2,
131 _ForwardOutIterator __outit,
132 _Comp&& __comp) const noexcept {
133 return std::merge(
134 std::move(__first1),
135 std::move(__last1),
136 std::move(__first2),
137 std::move(__last2),
138 std::move(__outit),
139 std::forward<_Comp>(__comp));
140 }
141};
142
143template <class _ExecutionPolicy>
144struct __min_element<__serial_backend_tag, _ExecutionPolicy> {
145 template <class _Policy, class _ForwardIterator, class _Compare>
146 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
147 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) const noexcept {
148 return std::min_element(std::move(__first), std::move(__last), std::move(__comp));
149 }
150};
151
152template <class _ExecutionPolicy>
153struct __minmax_element<__serial_backend_tag, _ExecutionPolicy> {
154 template <class _Policy, class _ForwardIterator, class _Compare>
155 _LIBCPP_HIDE_FROM_ABI optional<pair<_ForwardIterator, _ForwardIterator>>
156 operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp) const noexcept {
157 return std::minmax_element(std::move(__first), std::move(__last), std::move(__comp));
158 }
159};
160
161template <class _ExecutionPolicy>
162struct __reverse<__serial_backend_tag, _ExecutionPolicy> {
163 template <class _Policy, class _BidirectionalIterator>
164 _LIBCPP_HIDE_FROM_ABI optional<__empty>
165 operator()(_Policy&&, _BidirectionalIterator __first, _BidirectionalIterator __last) const noexcept {
166 std::reverse(std::move(__first), std::move(__last));
167 return __empty{};
168 }
169};
170
171template <class _ExecutionPolicy>
172struct __search<__serial_backend_tag, _ExecutionPolicy> {
173 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
174 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator1>
175 operator()(_Policy&&,
176 _ForwardIterator1 __first1,
177 _ForwardIterator1 __last1,
178 _ForwardIterator2 __first2,
179 _ForwardIterator2 __last2,
180 _BinaryPredicate __pred) const noexcept {
181 return std::search(
182 std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::move(__pred));
183 }
184};
185
186template <class _ExecutionPolicy>
187struct __search_n<__serial_backend_tag, _ExecutionPolicy> {
188 template <class _Policy, class _ForwardIterator, class _Size, class _Tp, class _Predicate>
189 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
190 operator()(_Policy&&,
191 _ForwardIterator __first,
192 _ForwardIterator __last,
193 _Size __count,
194 const _Tp& __value,
195 _Predicate __pred) const noexcept {
196 return std::search_n(std::move(__first), std::move(__last), __count, __value, std::move(__pred));
197 }
198};
199
200template <class _ExecutionPolicy>
201struct __stable_sort<__serial_backend_tag, _ExecutionPolicy> {
202 template <class _Policy, class _RandomAccessIterator, class _Comp>
203 _LIBCPP_HIDE_FROM_ABI optional<__empty>
204 operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp&& __comp) const noexcept {
205 std::stable_sort(std::move(__first), std::move(__last), std::forward<_Comp>(__comp));
206 return __empty{};
207 }
208};
209
210template <class _ExecutionPolicy>
211struct __swap_ranges<__serial_backend_tag, _ExecutionPolicy> {
212 template <class _Policy, class _ForwardIterator1, class _ForwardIterator2>
213 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator2> operator()(
214 _Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) const noexcept {
215 return std::swap_ranges(std::move(__first1), std::move(__last1), std::move(__first2));
216 }
217};
218
219template <class _ExecutionPolicy>
220struct __transform<__serial_backend_tag, _ExecutionPolicy> {
221 template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation>
222 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> operator()(
223 _Policy&&, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __outit, _UnaryOperation&& __op)
224 const noexcept {
225 return std::transform(
226 std::move(__first), std::move(__last), std::move(__outit), std::forward<_UnaryOperation>(__op));
227 }
228};
229
230template <class _ExecutionPolicy>
231struct __transform_binary<__serial_backend_tag, _ExecutionPolicy> {
232 template <class _Policy,
233 class _ForwardIterator1,
234 class _ForwardIterator2,
235 class _ForwardOutIterator,
236 class _BinaryOperation>
237 _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
238 operator()(_Policy&&,
239 _ForwardIterator1 __first1,
240 _ForwardIterator1 __last1,
241 _ForwardIterator2 __first2,
242 _ForwardOutIterator __outit,
243 _BinaryOperation&& __op) const noexcept {
244 return std::transform(
245 std::move(__first1),
246 std::move(__last1),
247 std::move(__first2),
248 std::move(__outit),
249 std::forward<_BinaryOperation>(__op));
250 }
251};
252
253template <class _ExecutionPolicy>
254struct __transform_reduce<__serial_backend_tag, _ExecutionPolicy> {
255 template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
256 _LIBCPP_HIDE_FROM_ABI optional<_Tp>
257 operator()(_Policy&&,
258 _ForwardIterator __first,
259 _ForwardIterator __last,
260 _Tp __init,
261 _BinaryOperation&& __reduce,
262 _UnaryOperation&& __transform) const noexcept {
263 return std::transform_reduce(
264 std::move(__first),
265 std::move(__last),
266 std::move(__init),
267 std::forward<_BinaryOperation>(__reduce),
268 std::forward<_UnaryOperation>(__transform));
269 }
270};
271
272template <class _ExecutionPolicy>
273struct __transform_reduce_binary<__serial_backend_tag, _ExecutionPolicy> {
274 template <class _Policy,
275 class _ForwardIterator1,
276 class _ForwardIterator2,
277 class _Tp,
278 class _BinaryOperation1,
279 class _BinaryOperation2>
280 _LIBCPP_HIDE_FROM_ABI optional<_Tp> operator()(
281 _Policy&&,
282 _ForwardIterator1 __first1,
283 _ForwardIterator1 __last1,
284 _ForwardIterator2 __first2,
285 _Tp __init,
286 _BinaryOperation1&& __reduce,
287 _BinaryOperation2&& __transform) const noexcept {
288 return std::transform_reduce(
289 std::move(__first1),
290 std::move(__last1),
291 std::move(__first2),
292 std::move(__init),
293 std::forward<_BinaryOperation1>(__reduce),
294 std::forward<_BinaryOperation2>(__transform));
295 }
296};
297
298template <class _ExecutionPolicy>
299struct __uninitialized_copy<__serial_backend_tag, _ExecutionPolicy> {
300 template <class _Policy, class _InputIterator, class _ForwardIterator>
301 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
302 operator()(_Policy&&, _InputIterator __first, _InputIterator __last, _ForwardIterator __result) const noexcept {
303 return std::uninitialized_copy(std::move(__first), std::move(__last), std::move(__result));
304 }
305};
306
307template <class _ExecutionPolicy>
308struct __uninitialized_move<__serial_backend_tag, _ExecutionPolicy> {
309 template <class _Policy, class _InputIterator, class _ForwardIterator>
310 _LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
311 operator()(_Policy&&, _InputIterator __first, _InputIterator __last, _ForwardIterator __result) const noexcept {
312 return std::uninitialized_move(std::move(__first), std::move(__last), std::move(__result));
313 }
314};
315
316} // namespace __pstl
317_LIBCPP_END_NAMESPACE_STD
318
319#endif // _LIBCPP_STD_VER >= 17
320
321_LIBCPP_POP_MACROS
322
323#endif // _LIBCPP___PSTL_BACKENDS_SERIAL_H
324