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 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 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 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> 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> 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 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 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 163 main() 164 { 165 for (int32_t mode = 0; mode < 2; ++mode) 166 { 167 inclusive = mode != 0; 168 #if !_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