1 // -*- C++ -*-
2 //===-- scan.pass.cpp -----------------------------------------------------===//
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 // UNSUPPORTED: c++03, c++11, c++14
11
12 #include "support/pstl_test_config.h"
13
14 #include <execution>
15 #include <numeric>
16
17 #include "support/utils.h"
18
19 using namespace TestUtils;
20
21 // We provide the no execution policy versions of the exclusive_scan and inclusive_scan due checking correctness result of the versions with execution policies.
22 //TODO: to add a macro for availability of ver implementations
23 template <class InputIterator, class OutputIterator, class T>
24 OutputIterator
exclusive_scan_serial(InputIterator first,InputIterator last,OutputIterator result,T init)25 exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, T init)
26 {
27 for (; first != last; ++first, ++result)
28 {
29 *result = init;
30 init = init + *first;
31 }
32 return result;
33 }
34
35 template <class InputIterator, class OutputIterator, class T, class BinaryOperation>
36 OutputIterator
exclusive_scan_serial(InputIterator first,InputIterator last,OutputIterator result,T init,BinaryOperation binary_op)37 exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op)
38 {
39 for (; first != last; ++first, ++result)
40 {
41 *result = init;
42 init = binary_op(init, *first);
43 }
44 return result;
45 }
46
47 // Note: N4582 is missing the ", class T". Issue was reported 2016-Apr-11 to cxxeditor@gmail.com
48 template <class InputIterator, class OutputIterator, class BinaryOperation, class T>
49 OutputIterator
inclusive_scan_serial(InputIterator first,InputIterator last,OutputIterator result,BinaryOperation binary_op,T init)50 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op, T init)
51 {
52 for (; first != last; ++first, ++result)
53 {
54 init = binary_op(init, *first);
55 *result = init;
56 }
57 return result;
58 }
59
60 template <class InputIterator, class OutputIterator, class BinaryOperation>
61 OutputIterator
inclusive_scan_serial(InputIterator first,InputIterator last,OutputIterator result,BinaryOperation binary_op)62 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op)
63 {
64 if (first != last)
65 {
66 auto tmp = *first;
67 *result = tmp;
68 return inclusive_scan_serial(++first, last, ++result, binary_op, tmp);
69 }
70 else
71 {
72 return result;
73 }
74 }
75
76 template <class InputIterator, class OutputIterator>
77 OutputIterator
inclusive_scan_serial(InputIterator first,InputIterator last,OutputIterator result)78 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result)
79 {
80 typedef typename std::iterator_traits<InputIterator>::value_type input_type;
81 return inclusive_scan_serial(first, last, result, std::plus<input_type>());
82 }
83
84 // Most of the framework required for testing inclusive and exclusive scan is identical,
85 // so the tests for both are in this file. Which is being tested is controlled by the global
86 // flag inclusive, which is set to each alternative by main().
87 static bool inclusive;
88
89 template <typename Iterator, typename Size, typename T>
90 void
check_and_reset(Iterator expected_first,Iterator out_first,Size n,T trash)91 check_and_reset(Iterator expected_first, Iterator out_first, Size n, T trash)
92 {
93 EXPECT_EQ_N(expected_first, out_first, n,
94 inclusive ? "wrong result from inclusive_scan" : "wrong result from exclusive_scan");
95 std::fill_n(out_first, n, trash);
96 }
97
98 struct test_scan_with_plus
99 {
100 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T>
101 void
operator ()test_scan_with_plus102 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last,
103 Iterator3 expected_first, Iterator3, Size n, T init, T trash)
104 {
105 using namespace std;
106
107 auto orr1 = inclusive ? inclusive_scan_serial(in_first, in_last, expected_first)
108 : exclusive_scan_serial(in_first, in_last, expected_first, init);
109 (void)orr1;
110 auto orr = inclusive ? inclusive_scan(exec, in_first, in_last, out_first)
111 : exclusive_scan(exec, in_first, in_last, out_first, init);
112 EXPECT_TRUE(out_last == orr,
113 inclusive ? "inclusive_scan returned wrong iterator" : "exclusive_scan returned wrong iterator");
114
115 check_and_reset(expected_first, out_first, n, trash);
116 fill(out_first, out_last, trash);
117 }
118 };
119
120 template <typename T, typename Convert>
121 void
test_with_plus(T init,T trash,Convert convert)122 test_with_plus(T init, T trash, Convert convert)
123 {
124 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
125 {
126 Sequence<T> in(n, convert);
127 Sequence<T> expected(in);
128 Sequence<T> out(n, [&](int32_t) { return trash; });
129
130 invoke_on_all_policies(test_scan_with_plus(), in.begin(), in.end(), out.begin(), out.end(), expected.begin(),
131 expected.end(), in.size(), init, trash);
132 invoke_on_all_policies(test_scan_with_plus(), in.cbegin(), in.cend(), out.begin(), out.end(), expected.begin(),
133 expected.end(), in.size(), init, trash);
134 }
135 }
136 struct test_scan_with_binary_op
137 {
138 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T,
139 typename BinaryOp>
140 typename std::enable_if<!TestUtils::isReverse<Iterator1>::value, void>::type
operator ()test_scan_with_binary_op141 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last,
142 Iterator3 expected_first, Iterator3, Size n, T init, BinaryOp binary_op, T trash)
143 {
144 using namespace std;
145
146 auto orr1 = inclusive ? inclusive_scan_serial(in_first, in_last, expected_first, binary_op, init)
147 : exclusive_scan_serial(in_first, in_last, expected_first, init, binary_op);
148 (void)orr1;
149 auto orr = inclusive ? inclusive_scan(exec, in_first, in_last, out_first, binary_op, init)
150 : exclusive_scan(exec, in_first, in_last, out_first, init, binary_op);
151
152 EXPECT_TRUE(out_last == orr, "scan returned wrong iterator");
153 check_and_reset(expected_first, out_first, n, trash);
154 }
155
156 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T,
157 typename BinaryOp>
158 typename std::enable_if<TestUtils::isReverse<Iterator1>::value, void>::type
operator ()test_scan_with_binary_op159 operator()(Policy&&, Iterator1, Iterator1, Iterator2, Iterator2, Iterator3, Iterator3, Size, T, BinaryOp, T)
160 {
161 }
162 };
163
164 template <typename In, typename Out, typename BinaryOp>
165 void
test_matrix(Out init,BinaryOp binary_op,Out trash)166 test_matrix(Out init, BinaryOp binary_op, Out trash)
167 {
168 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
169 {
170 Sequence<In> in(n, [](size_t k) { return In(k, k + 1); });
171
172 Sequence<Out> out(n, [&](size_t) { return trash; });
173 Sequence<Out> expected(n, [&](size_t) { return trash; });
174
175 invoke_on_all_policies(test_scan_with_binary_op(), in.begin(), in.end(), out.begin(), out.end(),
176 expected.begin(), expected.end(), in.size(), init, binary_op, trash);
177 invoke_on_all_policies(test_scan_with_binary_op(), in.cbegin(), in.cend(), out.begin(), out.end(),
178 expected.begin(), expected.end(), in.size(), init, binary_op, trash);
179 }
180 }
181
182 int
main()183 main()
184 {
185 for (int32_t mode = 0; mode < 2; ++mode)
186 {
187 inclusive = mode != 0;
188 #if !defined(_PSTL_ICC_19_TEST_SIMD_UDS_WINDOWS_RELEASE_BROKEN)
189 // Test with highly restricted type and associative but not commutative operation
190 test_matrix<Matrix2x2<int32_t>, Matrix2x2<int32_t>>(Matrix2x2<int32_t>(), multiply_matrix<int32_t>,
191 Matrix2x2<int32_t>(-666, 666));
192 #endif
193
194 // Since the implict "+" forms of the scan delegate to the generic forms,
195 // there's little point in using a highly restricted type, so just use double.
196 test_with_plus<float64_t>(inclusive ? 0.0 : -1.0, -666.0,
197 [](uint32_t k) { return float64_t((k % 991 + 1) ^ (k % 997 + 2)); });
198 }
199 std::cout << done() << std::endl;
200 return 0;
201 }
202