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