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
19using 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().
24static bool inclusive;
25
26template <typename Iterator, typename Size, typename T>
27void
28check_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
36struct 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
41 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
69 operator()(Policy&&, InputIterator, InputIterator, OutputIterator, OutputIterator, OutputIterator, OutputIterator,
70 Size, UnaryOp, T, BinaryOp, T)
71 {
72 }
73};
74
75const uint32_t encryption_mask = 0x314;
76
77template <typename InputIterator, typename OutputIterator, typename UnaryOperation, typename T,
78 typename BinaryOperation>
79std::pair<OutputIterator, T>
80transform_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
91template <typename InputIterator, typename OutputIterator, typename UnaryOperation, typename T,
92 typename BinaryOperation>
93std::pair<OutputIterator, T>
94transform_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
105template <typename In, typename Out, typename UnaryOp, typename BinaryOp>
106void
107test(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
144template <typename In, typename Out, typename UnaryOp, typename BinaryOp>
145void
146test_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
162int
163main()
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>>(unary_op: [](const Matrix2x2<int32_t> x) { return x; },
170 init: Matrix2x2<int32_t>(), binary_op: multiply_matrix<int32_t>,
171 trash: Matrix2x2<int32_t>(-666, 666));
172#endif
173 test<int32_t, uint32_t>(unary_op: [](int32_t x) { return x++; }, init: -123, binary_op: [](int32_t x, int32_t y) { return x + y; }, trash: 666);
174 }
175 std::cout << done() << std::endl;
176 return 0;
177}
178

source code of pstl/test/std/numerics/numeric.ops/transform_scan.pass.cpp