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