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_BACKEND_FWD_H
10#define _LIBCPP___PSTL_BACKEND_FWD_H
11
12#include <__config>
13
14#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
15# pragma GCC system_header
16#endif
17
18_LIBCPP_PUSH_MACROS
19#include <__undef_macros>
20
21//
22// This header declares available PSTL backends and the functions that must be implemented in order for the
23// PSTL algorithms to be provided.
24//
25// Backends often do not implement the full set of functions themselves -- a configuration of the PSTL is
26// usually a set of backends "stacked" together which each implement some algorithms under some execution
27// policies. It is only necessary for the "stack" of backends to implement all algorithms under all execution
28// policies, but a single backend is not required to implement everything on its own.
29//
30// The signatures used by each backend function are documented below.
31//
32// Exception handling
33// ==================
34//
35// PSTL backends are expected to report errors (i.e. failure to allocate) by returning a disengaged `optional` from
36// their implementation. Exceptions shouldn't be used to report an internal failure-to-allocate, since all exceptions
37// are turned into a program termination at the front-end level. When a backend returns a disengaged `optional` to the
38// frontend, the frontend will turn that into a call to `std::__throw_bad_alloc();` to report the internal failure to
39// the user.
40//
41
42#if _LIBCPP_STD_VER >= 17
43
44_LIBCPP_BEGIN_NAMESPACE_STD
45namespace __pstl {
46
47template <class... _Backends>
48struct __backend_configuration;
49
50struct __default_backend_tag;
51struct __libdispatch_backend_tag;
52struct __serial_backend_tag;
53struct __std_thread_backend_tag;
54
55# if defined(_LIBCPP_PSTL_BACKEND_SERIAL)
56using __current_configuration _LIBCPP_NODEBUG = __backend_configuration<__serial_backend_tag, __default_backend_tag>;
57# elif defined(_LIBCPP_PSTL_BACKEND_STD_THREAD)
58using __current_configuration _LIBCPP_NODEBUG =
59 __backend_configuration<__std_thread_backend_tag, __default_backend_tag>;
60# elif defined(_LIBCPP_PSTL_BACKEND_LIBDISPATCH)
61using __current_configuration _LIBCPP_NODEBUG =
62 __backend_configuration<__libdispatch_backend_tag, __default_backend_tag>;
63# else
64
65// ...New vendors can add parallel backends here...
66
67# error "Invalid PSTL backend configuration"
68# endif
69
70template <class _Backend, class _ExecutionPolicy>
71struct __find_if;
72// template <class _Policy, class _ForwardIterator, class _Predicate>
73// optional<_ForwardIterator>
74// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept;
75
76template <class _Backend, class _ExecutionPolicy>
77struct __find_if_not;
78// template <class _Policy, class _ForwardIterator, class _Predicate>
79// optional<_ForwardIterator>
80// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept;
81
82template <class _Backend, class _ExecutionPolicy>
83struct __find;
84// template <class _Policy, class _ForwardIterator, class _Tp>
85// optional<_ForwardIterator>
86// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) const noexcept;
87
88template <class _Backend, class _ExecutionPolicy>
89struct __any_of;
90// template <class _Policy, class _ForwardIterator, class _Predicate>
91// optional<bool>
92// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept;
93
94template <class _Backend, class _ExecutionPolicy>
95struct __all_of;
96// template <class _Policy, class _ForwardIterator, class _Predicate>
97// optional<bool>
98// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept;
99
100template <class _Backend, class _ExecutionPolicy>
101struct __none_of;
102// template <class _Policy, class _ForwardIterator, class _Predicate>
103// optional<bool>
104// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept;
105
106template <class _Backend, class _ExecutionPolicy>
107struct __is_partitioned;
108// template <class _Policy, class _ForwardIterator, class _Predicate>
109// optional<bool>
110// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept;
111
112template <class _Backend, class _ExecutionPolicy>
113struct __find_first_of;
114// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
115// optional<_ForwardIterator1>
116// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
117// _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Predicate __pred) const noexcept;
118
119template <class _Backend, class _ExecutionPolicy>
120struct __for_each;
121// template <class _Policy, class _ForwardIterator, class _Function>
122// optional<__empty>
123// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Function __func) const noexcept;
124
125template <class _Backend, class _ExecutionPolicy>
126struct __for_each_n;
127// template <class _Policy, class _ForwardIterator, class _Size, class _Function>
128// optional<__empty>
129// operator()(_Policy&&, _ForwardIterator __first, _Size __size, _Function __func) const noexcept;
130
131template <class _Backend, class _ExecutionPolicy>
132struct __fill;
133// template <class _Policy, class _ForwardIterator, class _Tp>
134// optional<__empty>
135// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept;
136
137template <class _Backend, class _ExecutionPolicy>
138struct __fill_n;
139// template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
140// optional<__empty>
141// operator()(_Policy&&, _ForwardIterator __first, _Size __n, _Tp const& __value) const noexcept;
142
143template <class _Backend, class _ExecutionPolicy>
144struct __search;
145// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
146// optional<_ForwardIterator1>
147// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
148// _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred) const noexcept;
149
150template <class _Backend, class _ExecutionPolicy>
151struct __replace;
152// template <class _Policy, class _ForwardIterator, class _Tp>
153// optional<__empty>
154// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
155// _Tp const& __old, _Tp const& __new) const noexcept;
156
157template <class _Backend, class _ExecutionPolicy>
158struct __replace_if;
159// template <class _Policy, class _ForwardIterator, class _Predicate, class _Tp>
160// optional<__empty>
161// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
162// _Predicate __pred, _Tp const& __new_value) const noexcept;
163
164template <class _Backend, class _ExecutionPolicy>
165struct __generate;
166// template <class _Policy, class _ForwardIterator, class _Generator>
167// optional<__empty>
168// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Generator __gen) const noexcept;
169
170template <class _Backend, class _ExecutionPolicy>
171struct __generate_n;
172// template <class _Policy, class _ForwardIterator, class _Size, class _Generator>
173// optional<__empty>
174// operator()(_Policy&&, _ForwardIterator __first, _Size __n, _Generator __gen) const noexcept;
175
176template <class _Backend, class _ExecutionPolicy>
177struct __reverse;
178// template <class _Policy, class _BidirectionalIterator>
179// optional<__empty>
180// operator()(_Policy&&, _BidirectionalIterator __first, _BidirectionalIterator __last) const noexcept;
181
182template <class _Backend, class _ExecutionPolicy>
183struct __reverse_copy;
184// template <class _Policy, class _BidirectionalIterator, class _ForwardIterator>
185// optional<_ForwardIterator>
186// operator()(_Policy&&, _BidirectionalIterator __first, _BidirectionalIterator __last,
187// _ForwardIterator __result) const noexcept;
188
189template <class _Backend, class _ExecutionPolicy>
190struct __merge;
191// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardOutIterator, class _Comp>
192// optional<_ForwardOutIterator>
193// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
194// _ForwardIterator2 __first2, _ForwardIterator2 __last2,
195// _ForwardOutIterator __result, _Comp __comp) const noexcept;
196
197template <class _Backend, class _ExecutionPolicy>
198struct __search_n;
199// template <class _Policy, class _ForwardIterator, class _Size, class _T, class _Predicate>
200// optional<_ForwardIterator>
201// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
202// _Size __count, const _T& __value, _Predicate __pred) const noexcept;
203
204template <class _Backend, class _ExecutionPolicy>
205struct __stable_sort;
206// template <class _Policy, class _RandomAccessIterator, class _Comp>
207// optional<__empty>
208// operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) const noexcept;
209
210template <class _Backend, class _ExecutionPolicy>
211struct __sort;
212// template <class _Policy, class _RandomAccessIterator, class _Comp>
213// optional<__empty>
214// operator()(_Policy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) const noexcept;
215
216template <class _Backend, class _ExecutionPolicy>
217struct __transform;
218// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation>
219// optional<_ForwardOutIterator>
220// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
221// _ForwardOutIterator __result,
222// _UnaryOperation __op) const noexcept;
223
224template <class _Backend, class _ExecutionPolicy>
225struct __transform_binary;
226// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2,
227// class _ForwardOutIterator,
228// class _BinaryOperation>
229// optional<_ForwardOutIterator>
230// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
231// _ForwardIterator2 __first2,
232// _ForwardOutIterator __result,
233// _BinaryOperation __op) const noexcept;
234
235template <class _Backend, class _ExecutionPolicy>
236struct __replace_copy_if;
237// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Predicate, class _Tp>
238// optional<__empty>
239// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
240// _ForwardOutIterator __out_it,
241// _Predicate __pred,
242// _Tp const& __new_value) const noexcept;
243
244template <class _Backend, class _ExecutionPolicy>
245struct __replace_copy;
246// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator, class _Tp>
247// optional<__empty>
248// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
249// _ForwardOutIterator __out_it,
250// _Tp const& __old_value,
251// _Tp const& __new_value) const noexcept;
252
253template <class _Backend, class _ExecutionPolicy>
254struct __move;
255// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
256// optional<_ForwardOutIterator>
257// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
258// _ForwardOutIterator __out_it) const noexcept;
259
260template <class _Backend, class _ExecutionPolicy>
261struct __copy;
262// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
263// optional<_ForwardOutIterator>
264// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
265// _ForwardOutIterator __out_it) const noexcept;
266
267template <class _Backend, class _ExecutionPolicy>
268struct __copy_n;
269// template <class _Policy, class _ForwardIterator, class _Size, class _ForwardOutIterator>
270// optional<_ForwardOutIterator>
271// operator()(_Policy&&, _ForwardIterator __first, _Size __n, _ForwardOutIterator __out_it) const noexcept;
272
273template <class _Backend, class _ExecutionPolicy>
274struct __rotate_copy;
275// template <class _Policy, class _ForwardIterator, class _ForwardOutIterator>
276// optional<_ForwardOutIterator>
277// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
278// _ForwardOutIterator __out_it) const noexcept;
279
280template <class _Backend, class _ExecutionPolicy>
281struct __transform_reduce;
282// template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
283// optional<_Tp>
284// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
285// _Tp __init,
286// _BinaryOperation __reduce,
287// _UnaryOperation __transform) const noexcept;
288
289template <class _Backend, class _ExecutionPolicy>
290struct __transform_reduce_binary;
291// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2,
292// class _Tp, class _BinaryOperation1, class _BinaryOperation2>
293// optional<_Tp> operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
294// _ForwardIterator2 __first2,
295// _Tp __init,
296// _BinaryOperation1 __reduce,
297// _BinaryOperation2 __transform) const noexcept;
298
299template <class _Backend, class _ExecutionPolicy>
300struct __count_if;
301// template <class _Policy, class _ForwardIterator, class _Predicate>
302// optional<__iter_diff_t<_ForwardIterator>>
303// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) const noexcept;
304
305template <class _Backend, class _ExecutionPolicy>
306struct __count;
307// template <class _Policy, class _ForwardIterator, class _Tp>
308// optional<__iter_diff_t<_ForwardIterator>>
309// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last, _Tp const& __value) const noexcept;
310
311template <class _Backend, class _ExecutionPolicy>
312struct __equal_3leg;
313// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
314// optional<bool>
315// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
316// _ForwardIterator2 __first2,
317// _Predicate __pred) const noexcept;
318
319template <class _Backend, class _ExecutionPolicy>
320struct __equal;
321// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
322// optional<bool>
323// operator()(_Policy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
324// _ForwardIterator2 __first2, _ForwardIterator2 __last2,
325// _Predicate __pred) const noexcept;
326
327template <class _Backend, class _ExecutionPolicy>
328struct __reduce;
329// template <class _Policy, class _ForwardIterator, class _Tp, class _BinaryOperation>
330// optional<_Tp>
331// operator()(_Policy&&, _ForwardIterator __first, _ForwardIterator __last,
332// _Tp __init, _BinaryOperation __op) const noexcept;
333
334template <class _Backend, class _ExecutionPolicy>
335struct __is_sorted;
336// template <class _Policy, class _ForwardIterator, class _Comp>
337// optional<bool>
338// operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept;
339
340template <class _Backend, class _ExecutionPolicy>
341struct __is_sorted_until;
342// template <class _Policy, class _ForwardIterator, class _Comp>
343// optional<_ForwardIterator>
344// operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Comp&& __comp) const noexcept;
345
346template <class _Backend, class _ExecutionPolicy>
347struct __adjacent_difference;
348// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
349// optional<_ForwardIterator2>
350// operator()(_Policy&& __policy, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
351// _ForwardIterator2 __first2, _BinaryOperation &&__op) const noexcept;
352
353template <class _Backend, class _ExecutionPolicy>
354struct __mismatch;
355// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Comp>
356// optional<pair<_ForwardIterator1, _ForwardIterator2>>
357// operator()(_Policy&& __policy, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
358// _ForwardIterator2 __first2, _ForwardIterator2 __last2,
359// _Comp __comp) const noexcept;
360
361template <class _Backend, class _ExecutionPolicy>
362struct __mismatch_3leg;
363// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Comp>
364// optional<pair<_ForwardIterator1, _ForwardIterator2>>
365// operator()(_Policy&& __policy, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
366// _ForwardIterator2 __first2, _Comp __comp) const noexcept;
367
368template <class _Backend, class _ExecutionPolicy>
369struct __adjacent_find;
370// template <class _Policy, class _ForwardIterator, class _BinaryPredicate>
371// optional<_ForwardIterator>
372// operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last,
373// _BinaryPredicate __predicate) const noexcept;
374
375template <class _Backend, class _ExecutionPolicy>
376struct __lexicographical_compare;
377// template <class _Policy, class _ForwardIterator1, class _ForwardIterator2, class _Comp>
378// optional<bool>
379// operator()(_Policy&& __policy, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
380// _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Comp __comp) const noexcept;
381
382template <class _Backend, class _ExecutionPolicy>
383struct __destroy;
384// template <class _Policy, class _ForwardIterator>
385// optional<__empty>
386// operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept;
387
388template <class _Backend, class _ExecutionPolicy>
389struct __destroy_n;
390// template <class _Policy, class _ForwardIterator, class _Size>
391// optional<__empty>
392// operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept;
393
394template <class _Backend, class _ExecutionPolicy>
395struct __uninitialized_default_construct;
396// template <class _Policy, class _ForwardIterator>
397// optional<__empty>
398// operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept;
399
400template <class _Backend, class _ExecutionPolicy>
401struct __uninitialized_default_construct_n;
402// template <class _Policy, class _ForwardIterator, class _Size>
403// optional<__empty>
404// operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept;
405
406template <class _Backend, class _ExecutionPolicy>
407struct __uninitialized_value_construct;
408// template <class _Policy, class _ForwardIterator>
409// optional<__empty>
410// operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last) const noexcept;
411
412template <class _Backend, class _ExecutionPolicy>
413struct __uninitialized_value_construct_n;
414// template <class _Policy, class _ForwardIterator, class _Size>
415// optional<__empty>
416// operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n) const noexcept;
417
418template <class _Backend, class _ExecutionPolicy>
419struct __uninitialized_fill;
420// template <class _Policy, class _ForwardIterator, class _Tp>
421// optional<__empty>
422// operator()(_Policy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp &__value) const noexcept;
423
424template <class _Backend, class _ExecutionPolicy>
425struct __uninitialized_fill_n;
426// template <class _Policy, class _ForwardIterator, class _Size, class _Tp>
427// optional<__empty>
428// operator()(_Policy&& __policy, _ForwardIterator __first, _Size __n, const _Tp &__value) const noexcept;
429
430} // namespace __pstl
431_LIBCPP_END_NAMESPACE_STD
432
433#endif // _LIBCPP_STD_VER >= 17
434
435_LIBCPP_POP_MACROS
436
437#endif // _LIBCPP___PSTL_BACKEND_FWD_H
438