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++98, 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, 43 UnaryOp unary_op, T init, BinaryOp binary_op, T trash) 44 { 45 using namespace std; 46 47 auto orr1 = inclusive ? transform_inclusive_scan(std::execution::seq, first, last, expected_first, binary_op, 48 unary_op, init) 49 : transform_exclusive_scan(std::execution::seq, first, last, expected_first, init, 50 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, 70 OutputIterator, OutputIterator, OutputIterator, Size, 71 UnaryOp, T, BinaryOp, T) 72 { 73 } 74 }; 75 76 const uint32_t encryption_mask = 0x314; 77 78 template <typename InputIterator, typename OutputIterator, typename UnaryOperation, typename T, 79 typename BinaryOperation> 80 std::pair<OutputIterator, T> 81 transform_inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unary_op, 82 T init, BinaryOperation binary_op) noexcept 83 { 84 for (; first != last; ++first, ++result) 85 { 86 init = binary_op(init, unary_op(*first)); 87 *result = init; 88 } 89 return std::make_pair(result, init); 90 } 91 92 template <typename InputIterator, typename OutputIterator, typename UnaryOperation, typename T, 93 typename BinaryOperation> 94 std::pair<OutputIterator, T> 95 transform_exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unary_op, 96 T init, BinaryOperation binary_op) noexcept 97 { 98 for (; first != last; ++first, ++result) 99 { 100 *result = init; 101 init = binary_op(init, unary_op(*first)); 102 } 103 return std::make_pair(result, init); 104 } 105 106 template <typename In, typename Out, typename UnaryOp, typename BinaryOp> 107 void 108 test(UnaryOp unary_op, Out init, BinaryOp binary_op, Out trash) 109 { 110 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) 111 { 112 Sequence<In> in(n, [](size_t k) { return In(k ^ encryption_mask); }); 113 114 Out tmp = init; 115 Sequence<Out> expected(n, [&](size_t k) -> Out { 116 if (inclusive) 117 { 118 tmp = binary_op(tmp, unary_op(in[k])); 119 return tmp; 120 } 121 else 122 { 123 Out val = tmp; 124 tmp = binary_op(tmp, unary_op(in[k])); 125 return val; 126 } 127 }); 128 129 Sequence<Out> out(n, [&](size_t) { return trash; }); 130 131 auto result = 132 inclusive 133 ? transform_inclusive_scan_serial(in.cbegin(), in.cend(), out.fbegin(), unary_op, init, binary_op) 134 : transform_exclusive_scan_serial(in.cbegin(), in.cend(), out.fbegin(), unary_op, init, binary_op); 135 (void)result; 136 check_and_reset(expected.begin(), out.begin(), out.size(), trash); 137 138 invoke_on_all_policies(test_transform_scan(), in.begin(), in.end(), out.begin(), out.end(), expected.begin(), 139 expected.end(), in.size(), unary_op, init, binary_op, trash); 140 invoke_on_all_policies(test_transform_scan(), in.cbegin(), in.cend(), out.begin(), out.end(), expected.begin(), 141 expected.end(), in.size(), unary_op, init, binary_op, trash); 142 } 143 } 144 145 template <typename In, typename Out, typename UnaryOp, typename BinaryOp> 146 void 147 test_matrix(UnaryOp unary_op, Out init, BinaryOp binary_op, Out trash) 148 { 149 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) 150 { 151 Sequence<In> in(n, [](size_t k) { return In(k, k + 1); }); 152 153 Sequence<Out> out(n, [&](size_t) { return trash; }); 154 Sequence<Out> expected(n, [&](size_t) { return trash; }); 155 156 invoke_on_all_policies(test_transform_scan(), in.begin(), in.end(), out.begin(), out.end(), expected.begin(), 157 expected.end(), in.size(), unary_op, init, binary_op, trash); 158 invoke_on_all_policies(test_transform_scan(), in.cbegin(), in.cend(), out.begin(), out.end(), expected.begin(), 159 expected.end(), in.size(), unary_op, init, binary_op, trash); 160 } 161 } 162 163 int 164 main() 165 { 166 for (int32_t mode = 0; mode < 2; ++mode) 167 { 168 inclusive = mode != 0; 169 #if !_PSTL_ICC_19_TEST_SIMD_UDS_WINDOWS_RELEASE_BROKEN 170 test_matrix<Matrix2x2<int32_t>, Matrix2x2<int32_t>>([](const Matrix2x2<int32_t> x) { return x; }, 171 Matrix2x2<int32_t>(), multiply_matrix<int32_t>, 172 Matrix2x2<int32_t>(-666, 666)); 173 #endif 174 test<int32_t, uint32_t>([](int32_t x) { return x++; }, -123, [](int32_t x, int32_t y) { return x + y; }, 666); 175 } 176 std::cout << done() << std::endl; 177 return 0; 178 } 179