1 // -*- C++ -*-
2 //===-- glue_numeric_impl.h -----------------------------------------------===//
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 "utils.h"
16 #include "numeric_fwd.h"
17
18 namespace std
19 {
20
21 // [reduce]
22
23 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation>
24 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op)25 reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
26 _BinaryOperation __binary_op)
27 {
28 return transform_reduce(std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op,
29 __pstl::__internal::__no_op());
30 }
31
32 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
33 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_Tp __init)34 reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init)
35 {
36 return transform_reduce(std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, std::plus<_Tp>(),
37 __pstl::__internal::__no_op());
38 }
39
40 template <class _ExecutionPolicy, class _ForwardIterator>
41 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy,
42 typename iterator_traits<_ForwardIterator>::value_type>
reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last)43 reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
44 {
45 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
46 return transform_reduce(std::forward<_ExecutionPolicy>(__exec), __first, __last, _ValueType{},
47 std::plus<_ValueType>(), __pstl::__internal::__no_op());
48 }
49
50 // [transform.reduce]
51
52 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
53 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
transform_reduce(_ExecutionPolicy && __exec,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Tp __init)54 transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
55 _ForwardIterator2 __first2, _Tp __init)
56 {
57 typedef typename iterator_traits<_ForwardIterator1>::value_type _InputType;
58 return __pstl::__internal::__pattern_transform_reduce(
59 std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __init, std::plus<_InputType>(),
60 std::multiplies<_InputType>(),
61 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
62 __exec),
63 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
64 __exec));
65 }
66
67 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1,
68 class _BinaryOperation2>
69 __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)70 transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
71 _ForwardIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2)
72 {
73 return __pstl::__internal::__pattern_transform_reduce(
74 std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __init, __binary_op1, __binary_op2,
75 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
76 __exec),
77 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
78 __exec));
79 }
80
81 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
82 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
transform_reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op,_UnaryOperation __unary_op)83 transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
84 _BinaryOperation __binary_op, _UnaryOperation __unary_op)
85 {
86 return __pstl::__internal::__pattern_transform_reduce(
87 std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op, __unary_op,
88 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec),
89 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator>(__exec));
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 using namespace __pstl;
100 return __internal::__pattern_transform_scan(
101 std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __pstl::__internal::__no_op(), __init,
102 std::plus<_Tp>(), /*inclusive=*/std::false_type(),
103 __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec),
104 __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec));
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 using namespace __pstl;
113 return __internal::__pattern_transform_scan(
114 std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __pstl::__internal::__no_op(), __init,
115 __binary_op, /*inclusive=*/std::false_type(),
116 __internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec),
117 __internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(__exec));
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 return __pstl::__internal::__pattern_transform_scan(
160 std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __unary_op, __init, __binary_op,
161 /*inclusive=*/std::false_type(),
162 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
163 __exec),
164 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
165 __exec));
166 }
167
168 // [transform.inclusive.scan]
169
170 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation,
171 class _UnaryOperation, class _Tp>
172 __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)173 transform_inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
174 _ForwardIterator2 __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op,
175 _Tp __init)
176 {
177 return __pstl::__internal::__pattern_transform_scan(
178 std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, __unary_op, __init, __binary_op,
179 /*inclusive=*/std::true_type(),
180 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
181 __exec),
182 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
183 __exec));
184 }
185
186 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryOperation,
187 class _BinaryOperation>
188 __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)189 transform_inclusive_scan(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
190 _ForwardIterator2 __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op)
191 {
192 if (__first != __last)
193 {
194 auto __tmp = __unary_op(*__first);
195 *__result = __tmp;
196 return transform_inclusive_scan(std::forward<_ExecutionPolicy>(__exec), ++__first, __last, ++__result,
197 __binary_op, __unary_op, __tmp);
198 }
199 else
200 {
201 return __result;
202 }
203 }
204
205 // [adjacent.difference]
206
207 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
208 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
adjacent_difference(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __d_first,_BinaryOperation __op)209 adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
210 _ForwardIterator2 __d_first, _BinaryOperation __op)
211 {
212
213 if (__first == __last)
214 return __d_first;
215
216 return __pstl::__internal::__pattern_adjacent_difference(
217 std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first, __op,
218 __pstl::__internal::__is_vectorization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
219 __exec),
220 __pstl::__internal::__is_parallelization_preferred<_ExecutionPolicy, _ForwardIterator1, _ForwardIterator2>(
221 __exec));
222 }
223
224 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
225 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
adjacent_difference(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __d_first)226 adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
227 _ForwardIterator2 __d_first)
228 {
229 typedef typename iterator_traits<_ForwardIterator1>::value_type _ValueType;
230 return adjacent_difference(std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first,
231 std::minus<_ValueType>());
232 }
233
234 } // namespace std
235
236 #endif /* _PSTL_GLUE_NUMERIC_IMPL_H_ */
237