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 _PSTL_GLUE_NUMERIC_IMPL_H
11 #define _PSTL_GLUE_NUMERIC_IMPL_H
12
13 #include <functional>
14
15 #include "pstl_config.h"
16
17 #include "utils.h"
18 #include "numeric_fwd.h"
19 #include "execution_impl.h"
20
21 _PSTL_HIDE_FROM_ABI_PUSH
22
23 namespace std
24 {
25
26 // [reduce]
27
28 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation>
29 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op)30 reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
31 _BinaryOperation __binary_op)
32 {
33 return transform_reduce(std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op,
34 __pstl::__internal::__no_op());
35 }
36
37 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
38 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_Tp __init)39 reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init)
40 {
41 return transform_reduce(std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, std::plus<_Tp>(),
42 __pstl::__internal::__no_op());
43 }
44
45 template <class _ExecutionPolicy, class _ForwardIterator>
46 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy,
47 typename iterator_traits<_ForwardIterator>::value_type>
reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last)48 reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
49 {
50 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
51 return transform_reduce(std::forward<_ExecutionPolicy>(__exec), __first, __last, _ValueType{},
52 std::plus<_ValueType>(), __pstl::__internal::__no_op());
53 }
54
55 // [transform.reduce]
56
57 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
58 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
transform_reduce(_ExecutionPolicy && __exec,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Tp __init)59 transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
60 _ForwardIterator2 __first2, _Tp __init)
61 {
62 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
63
64 typedef typename iterator_traits<_ForwardIterator1>::value_type _InputType;
65 return __pstl::__internal::__pattern_transform_reduce(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
66 __first1, __last1, __first2, __init, std::plus<_InputType>(),
67 std::multiplies<_InputType>());
68 }
69
70 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1,
71 class _BinaryOperation2>
72 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
transform_reduce(_ExecutionPolicy && __exec,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Tp __init,_BinaryOperation1 __binary_op1,_BinaryOperation2 __binary_op2)73 transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
74 _ForwardIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2)
75 {
76 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
77 return __pstl::__internal::__pattern_transform_reduce(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
78 __first1, __last1, __first2, __init, __binary_op1,
79 __binary_op2);
80 }
81
82 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
83 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
transform_reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op,_UnaryOperation __unary_op)84 transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
85 _BinaryOperation __binary_op, _UnaryOperation __unary_op)
86 {
87 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
88 return __pstl::__internal::__pattern_transform_reduce(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
89 __first, __last, __init, __binary_op, __unary_op);
90 }
91
92 // [exclusive.scan]
93
94 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
95 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
exclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_Tp __init)96 exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
97 _ForwardIterator2 __result, _Tp __init)
98 {
99 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
100
101 using namespace __pstl;
102 return __internal::__pattern_transform_scan(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
103 __result, __pstl::__internal::__no_op(), __init, std::plus<_Tp>(),
104 /*inclusive=*/std::false_type());
105 }
106
107 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation>
108 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
exclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_Tp __init,_BinaryOperation __binary_op)109 exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
110 _ForwardIterator2 __result, _Tp __init, _BinaryOperation __binary_op)
111 {
112 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
113
114 using namespace __pstl;
115 return __internal::__pattern_transform_scan(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
116 __result, __pstl::__internal::__no_op(), __init, __binary_op,
117 /*inclusive=*/std::false_type());
118 }
119
120 // [inclusive.scan]
121
122 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
123 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
inclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result)124 inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
125 _ForwardIterator2 __result)
126 {
127 typedef typename iterator_traits<_ForwardIterator1>::value_type _InputType;
128 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result,
129 std::plus<_InputType>(), __pstl::__internal::__no_op());
130 }
131
132 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
133 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
inclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_BinaryOperation __binary_op)134 inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
135 _ForwardIterator2 __result, _BinaryOperation __binary_op)
136 {
137 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __binary_op,
138 __pstl::__internal::__no_op());
139 }
140
141 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation>
142 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
inclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_BinaryOperation __binary_op,_Tp __init)143 inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
144 _ForwardIterator2 __result, _BinaryOperation __binary_op, _Tp __init)
145 {
146 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __binary_op,
147 __pstl::__internal::__no_op(), __init);
148 }
149
150 // [transform.exclusive.scan]
151
152 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation,
153 class _UnaryOperation>
154 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
transform_exclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_Tp __init,_BinaryOperation __binary_op,_UnaryOperation __unary_op)155 transform_exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
156 _ForwardIterator2 __result, _Tp __init, _BinaryOperation __binary_op,
157 _UnaryOperation __unary_op)
158 {
159 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
160
161 return __pstl::__internal::__pattern_transform_scan(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
162 __last, __result, __unary_op, __init, __binary_op,
163 /*inclusive=*/std::false_type());
164 }
165
166 // [transform.inclusive.scan]
167
168 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation,
169 class _UnaryOperation, class _Tp>
170 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
transform_inclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_BinaryOperation __binary_op,_UnaryOperation __unary_op,_Tp __init)171 transform_inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
172 _ForwardIterator2 __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op,
173 _Tp __init)
174 {
175 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
176
177 return __pstl::__internal::__pattern_transform_scan(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
178 __last, __result, __unary_op, __init, __binary_op,
179 /*inclusive=*/std::true_type());
180 }
181
182 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryOperation,
183 class _BinaryOperation>
184 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
transform_inclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_BinaryOperation __binary_op,_UnaryOperation __unary_op)185 transform_inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
186 _ForwardIterator2 __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op)
187 {
188 if (__first != __last)
189 {
190 auto __tmp = __unary_op(*__first);
191 *__result = __tmp;
192 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), ++__first, __last, ++__result,
193 __binary_op, __unary_op, __tmp);
194 }
195 else
196 {
197 return __result;
198 }
199 }
200
201 // [adjacent.difference]
202
203 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
204 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
adjacent_difference(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __d_first,_BinaryOperation __op)205 adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
206 _ForwardIterator2 __d_first, _BinaryOperation __op)
207 {
208
209 if (__first == __last)
210 return __d_first;
211
212 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __d_first);
213
214 return __pstl::__internal::__pattern_adjacent_difference(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
215 __first, __last, __d_first, __op);
216 }
217
218 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
219 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
adjacent_difference(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __d_first)220 adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
221 _ForwardIterator2 __d_first)
222 {
223 typedef typename iterator_traits<_ForwardIterator1>::value_type _ValueType;
224 return adjacent_difference(std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first,
225 std::minus<_ValueType>());
226 }
227
228 } // namespace std
229
230 _PSTL_HIDE_FROM_ABI_POP
231
232 #endif /* _PSTL_GLUE_NUMERIC_IMPL_H_ */
233