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 typedef typename iterator_traits<_ForwardIterator1>::value_type _InputType;
63 return __pstl::__internal::__pattern_transform_reduce(
64 std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __init, std::plus<_InputType>(),
65 std::multiplies<_InputType>(),
66 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
67 __exec),
68 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
69 __exec));
70 }
71
72 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1,
73 class _BinaryOperation2>
74 __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)75 transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
76 _ForwardIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2)
77 {
78 return __pstl::__internal::__pattern_transform_reduce(
79 std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __init, __binary_op1, __binary_op2,
80 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
81 __exec),
82 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
83 __exec));
84 }
85
86 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
87 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
transform_reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op,_UnaryOperation __unary_op)88 transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
89 _BinaryOperation __binary_op, _UnaryOperation __unary_op)
90 {
91 return __pstl::__internal::__pattern_transform_reduce(
92 std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op, __unary_op,
93 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec),
94 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec));
95 }
96
97 // [exclusive.scan]
98
99 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
100 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
exclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_Tp __init)101 exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
102 _ForwardIterator2 __result, _Tp __init)
103 {
104 using namespace __pstl;
105 return __internal::__pattern_transform_scan(
106 std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __pstl::__internal::__no_op(), __init,
107 std::plus<_Tp>(), /*inclusive=*/std::false_type(),
108 __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec),
109 __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec));
110 }
111
112 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation>
113 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
exclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_Tp __init,_BinaryOperation __binary_op)114 exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
115 _ForwardIterator2 __result, _Tp __init, _BinaryOperation __binary_op)
116 {
117 using namespace __pstl;
118 return __internal::__pattern_transform_scan(
119 std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __pstl::__internal::__no_op(), __init,
120 __binary_op, /*inclusive=*/std::false_type(),
121 __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec),
122 __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec));
123 }
124
125 // [inclusive.scan]
126
127 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
128 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
inclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result)129 inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
130 _ForwardIterator2 __result)
131 {
132 typedef typename iterator_traits<_ForwardIterator1>::value_type _InputType;
133 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result,
134 std::plus<_InputType>(), __pstl::__internal::__no_op());
135 }
136
137 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
138 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
inclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_BinaryOperation __binary_op)139 inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
140 _ForwardIterator2 __result, _BinaryOperation __binary_op)
141 {
142 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __binary_op,
143 __pstl::__internal::__no_op());
144 }
145
146 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation>
147 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
inclusive_scan(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __result,_BinaryOperation __binary_op,_Tp __init)148 inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
149 _ForwardIterator2 __result, _BinaryOperation __binary_op, _Tp __init)
150 {
151 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __binary_op,
152 __pstl::__internal::__no_op(), __init);
153 }
154
155 // [transform.exclusive.scan]
156
157 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation,
158 class _UnaryOperation>
159 __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)160 transform_exclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
161 _ForwardIterator2 __result, _Tp __init, _BinaryOperation __binary_op,
162 _UnaryOperation __unary_op)
163 {
164 return __pstl::__internal::__pattern_transform_scan(
165 std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __unary_op, __init, __binary_op,
166 /*inclusive=*/std::false_type(),
167 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
168 __exec),
169 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
170 __exec));
171 }
172
173 // [transform.inclusive.scan]
174
175 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation,
176 class _UnaryOperation, class _Tp>
177 __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)178 transform_inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
179 _ForwardIterator2 __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op,
180 _Tp __init)
181 {
182 return __pstl::__internal::__pattern_transform_scan(
183 std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __unary_op, __init, __binary_op,
184 /*inclusive=*/std::true_type(),
185 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
186 __exec),
187 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
188 __exec));
189 }
190
191 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryOperation,
192 class _BinaryOperation>
193 __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)194 transform_inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
195 _ForwardIterator2 __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op)
196 {
197 if (__first != __last)
198 {
199 auto __tmp = __unary_op(*__first);
200 *__result = __tmp;
201 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), ++__first, __last, ++__result,
202 __binary_op, __unary_op, __tmp);
203 }
204 else
205 {
206 return __result;
207 }
208 }
209
210 // [adjacent.difference]
211
212 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
213 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
adjacent_difference(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __d_first,_BinaryOperation __op)214 adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
215 _ForwardIterator2 __d_first, _BinaryOperation __op)
216 {
217
218 if (__first == __last)
219 return __d_first;
220
221 return __pstl::__internal::__pattern_adjacent_difference(
222 std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first, __op,
223 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
224 __exec),
225 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
226 __exec));
227 }
228
229 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
230 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
adjacent_difference(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __d_first)231 adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
232 _ForwardIterator2 __d_first)
233 {
234 typedef typename iterator_traits<_ForwardIterator1>::value_type _ValueType;
235 return adjacent_difference(std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first,
236 std::minus<_ValueType>());
237 }
238
239 } // namespace std
240
241 _PSTL_HIDE_FROM_ABI_POP
242
243 #endif /* _PSTL_GLUE_NUMERIC_IMPL_H_ */
244