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