1 // -*- C++ -*-
2 //===-- transform_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 // Most of the framework required for testing inclusive and exclusive transform-scans is identical,
22 // so the tests for both are in this file. Which is being tested is controlled by the global
23 // flag inclusive, which is set to each alternative by main().
24 static bool inclusive;
25
26 template <typename Iterator, typename Size, typename T>
27 void
check_and_reset(Iterator expected_first,Iterator out_first,Size n,T trash)28 check_and_reset(Iterator expected_first, Iterator out_first, Size n, T trash)
29 {
30 EXPECT_EQ_N(expected_first, out_first, n,
31 inclusive ? "wrong result from transform_inclusive_scan"
32 : "wrong result from transform_exclusive_scan");
33 std::fill_n(out_first, n, trash);
34 }
35
36 struct test_transform_scan
37 {
38 template <typename Policy, typename InputIterator, typename OutputIterator, typename Size, typename UnaryOp,
39 typename T, typename BinaryOp>
40 typename std::enable_if<!TestUtils::isReverse<InputIterator>::value, void>::type
operator ()test_transform_scan41 operator()(Policy&& exec, InputIterator first, InputIterator last, OutputIterator out_first,
42 OutputIterator out_last, OutputIterator expected_first, OutputIterator, Size n, UnaryOp unary_op, T init,
43 BinaryOp binary_op, T trash)
44 {
45 using namespace std;
46
47 auto orr1 =
48 inclusive
49 ? transform_inclusive_scan(std::execution::seq, first, last, expected_first, binary_op, unary_op, init)
50 : transform_exclusive_scan(std::execution::seq, first, last, expected_first, init, binary_op, unary_op);
51 auto orr2 = inclusive ? transform_inclusive_scan(exec, first, last, out_first, binary_op, unary_op, init)
52 : transform_exclusive_scan(exec, first, last, out_first, init, binary_op, unary_op);
53 EXPECT_TRUE(out_last == orr2, "transform...scan returned wrong iterator");
54 check_and_reset(expected_first, out_first, n, trash);
55
56 // Checks inclusive scan if init is not provided
57 if (inclusive && n > 0)
58 {
59 orr1 = transform_inclusive_scan(std::execution::seq, first, last, expected_first, binary_op, unary_op);
60 orr2 = transform_inclusive_scan(exec, first, last, out_first, binary_op, unary_op);
61 EXPECT_TRUE(out_last == orr2, "transform...scan returned wrong iterator");
62 check_and_reset(expected_first, out_first, n, trash);
63 }
64 }
65
66 template <typename Policy, typename InputIterator, typename OutputIterator, typename Size, typename UnaryOp,
67 typename T, typename BinaryOp>
68 typename std::enable_if<TestUtils::isReverse<InputIterator>::value, void>::type
operator ()test_transform_scan69 operator()(Policy&&, InputIterator, InputIterator, OutputIterator, OutputIterator, OutputIterator, OutputIterator,
70 Size, UnaryOp, T, BinaryOp, T)
71 {
72 }
73 };
74
75 const uint32_t encryption_mask = 0x314;
76
77 template <typename InputIterator, typename OutputIterator, typename UnaryOperation, typename T,
78 typename BinaryOperation>
79 std::pair<OutputIterator, T>
transform_inclusive_scan_serial(InputIterator first,InputIterator last,OutputIterator result,UnaryOperation unary_op,T init,BinaryOperation binary_op)80 transform_inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unary_op,
81 T init, BinaryOperation binary_op) noexcept
82 {
83 for (; first != last; ++first, ++result)
84 {
85 init = binary_op(init, unary_op(*first));
86 *result = init;
87 }
88 return std::make_pair(result, init);
89 }
90
91 template <typename InputIterator, typename OutputIterator, typename UnaryOperation, typename T,
92 typename BinaryOperation>
93 std::pair<OutputIterator, T>
transform_exclusive_scan_serial(InputIterator first,InputIterator last,OutputIterator result,UnaryOperation unary_op,T init,BinaryOperation binary_op)94 transform_exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unary_op,
95 T init, BinaryOperation binary_op) noexcept
96 {
97 for (; first != last; ++first, ++result)
98 {
99 *result = init;
100 init = binary_op(init, unary_op(*first));
101 }
102 return std::make_pair(result, init);
103 }
104
105 template <typename In, typename Out, typename UnaryOp, typename BinaryOp>
106 void
test(UnaryOp unary_op,Out init,BinaryOp binary_op,Out trash)107 test(UnaryOp unary_op, Out init, BinaryOp binary_op, Out trash)
108 {
109 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
110 {
111 Sequence<In> in(n, [](size_t k) { return In(k ^ encryption_mask); });
112
113 Out tmp = init;
114 Sequence<Out> expected(n, [&](size_t k) -> Out {
115 if (inclusive)
116 {
117 tmp = binary_op(tmp, unary_op(in[k]));
118 return tmp;
119 }
120 else
121 {
122 Out val = tmp;
123 tmp = binary_op(tmp, unary_op(in[k]));
124 return val;
125 }
126 });
127
128 Sequence<Out> out(n, [&](size_t) { return trash; });
129
130 auto result =
131 inclusive
132 ? transform_inclusive_scan_serial(in.cbegin(), in.cend(), out.fbegin(), unary_op, init, binary_op)
133 : transform_exclusive_scan_serial(in.cbegin(), in.cend(), out.fbegin(), unary_op, init, binary_op);
134 (void)result;
135 check_and_reset(expected.begin(), out.begin(), out.size(), trash);
136
137 invoke_on_all_policies(test_transform_scan(), in.begin(), in.end(), out.begin(), out.end(), expected.begin(),
138 expected.end(), in.size(), unary_op, init, binary_op, trash);
139 invoke_on_all_policies(test_transform_scan(), in.cbegin(), in.cend(), out.begin(), out.end(), expected.begin(),
140 expected.end(), in.size(), unary_op, init, binary_op, trash);
141 }
142 }
143
144 template <typename In, typename Out, typename UnaryOp, typename BinaryOp>
145 void
test_matrix(UnaryOp unary_op,Out init,BinaryOp binary_op,Out trash)146 test_matrix(UnaryOp unary_op, Out init, BinaryOp binary_op, Out trash)
147 {
148 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
149 {
150 Sequence<In> in(n, [](size_t k) { return In(k, k + 1); });
151
152 Sequence<Out> out(n, [&](size_t) { return trash; });
153 Sequence<Out> expected(n, [&](size_t) { return trash; });
154
155 invoke_on_all_policies(test_transform_scan(), in.begin(), in.end(), out.begin(), out.end(), expected.begin(),
156 expected.end(), in.size(), unary_op, init, binary_op, trash);
157 invoke_on_all_policies(test_transform_scan(), in.cbegin(), in.cend(), out.begin(), out.end(), expected.begin(),
158 expected.end(), in.size(), unary_op, init, binary_op, trash);
159 }
160 }
161
162 int
main()163 main()
164 {
165 for (int32_t mode = 0; mode < 2; ++mode)
166 {
167 inclusive = mode != 0;
168 #if !defined(_PSTL_ICC_19_TEST_SIMD_UDS_WINDOWS_RELEASE_BROKEN)
169 test_matrix<Matrix2x2<int32_t>, Matrix2x2<int32_t>>([](const Matrix2x2<int32_t> x) { return x; },
170 Matrix2x2<int32_t>(), multiply_matrix<int32_t>,
171 Matrix2x2<int32_t>(-666, 666));
172 #endif
173 test<int32_t, uint32_t>([](int32_t x) { return x++; }, -123, [](int32_t x, int32_t y) { return x + y; }, 666);
174 }
175 std::cout << done() << std::endl;
176 return 0;
177 }
178