1 // -*- C++ -*- 2 //===-- 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 #ifdef PSTL_STANDALONE_TESTS 13 #include "pstl/execution" 14 #include "pstl/numeric" 15 #else 16 #include <execution> 17 #include <numeric> 18 #endif // PSTL_STANDALONE_TESTS 19 20 #include "support/utils.h" 21 22 using namespace TestUtils; 23 24 // We provide the no execution policy versions of the exclusive_scan and inclusive_scan due checking correctness result of the versions with execution policies. 25 //TODO: to add a macro for availability of ver implementations 26 template <class InputIterator, class OutputIterator, class T> 27 OutputIterator 28 exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, T init) 29 { 30 for (; first != last; ++first, ++result) 31 { 32 *result = init; 33 init = init + *first; 34 } 35 return result; 36 } 37 38 template <class InputIterator, class OutputIterator, class T, class BinaryOperation> 39 OutputIterator 40 exclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op) 41 { 42 for (; first != last; ++first, ++result) 43 { 44 *result = init; 45 init = binary_op(init, *first); 46 } 47 return result; 48 } 49 50 // Note: N4582 is missing the ", class T". Issue was reported 2016-Apr-11 to cxxeditor@gmail.com 51 template <class InputIterator, class OutputIterator, class BinaryOperation, class T> 52 OutputIterator 53 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op, T init) 54 { 55 for (; first != last; ++first, ++result) 56 { 57 init = binary_op(init, *first); 58 *result = init; 59 } 60 return result; 61 } 62 63 template <class InputIterator, class OutputIterator, class BinaryOperation> 64 OutputIterator 65 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op) 66 { 67 if (first != last) 68 { 69 auto tmp = *first; 70 *result = tmp; 71 return inclusive_scan_serial(++first, last, ++result, binary_op, tmp); 72 } 73 else 74 { 75 return result; 76 } 77 } 78 79 template <class InputIterator, class OutputIterator> 80 OutputIterator 81 inclusive_scan_serial(InputIterator first, InputIterator last, OutputIterator result) 82 { 83 typedef typename std::iterator_traits<InputIterator>::value_type input_type; 84 return inclusive_scan_serial(first, last, result, std::plus<input_type>()); 85 } 86 87 // Most of the framework required for testing inclusive and exclusive scan is identical, 88 // so the tests for both are in this file. Which is being tested is controlled by the global 89 // flag inclusive, which is set to each alternative by main(). 90 static bool inclusive; 91 92 template <typename Iterator, typename Size, typename T> 93 void 94 check_and_reset(Iterator expected_first, Iterator out_first, Size n, T trash) 95 { 96 EXPECT_EQ_N(expected_first, out_first, n, 97 inclusive ? "wrong result from inclusive_scan" : "wrong result from exclusive_scan"); 98 std::fill_n(out_first, n, trash); 99 } 100 101 struct test_scan_with_plus 102 { 103 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T> 104 void 105 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last, 106 Iterator3 expected_first, Iterator3 expected_last, Size n, T init, T trash) 107 { 108 using namespace std; 109 110 auto orr1 = inclusive ? inclusive_scan_serial(in_first, in_last, expected_first) 111 : exclusive_scan_serial(in_first, in_last, expected_first, init); 112 auto orr = inclusive ? inclusive_scan(exec, in_first, in_last, out_first) 113 : exclusive_scan(exec, in_first, in_last, out_first, init); 114 EXPECT_TRUE(out_last == orr, 115 inclusive ? "inclusive_scan returned wrong iterator" : "exclusive_scan returned wrong iterator"); 116 117 check_and_reset(expected_first, out_first, n, trash); 118 fill(out_first, out_last, trash); 119 } 120 }; 121 122 template <typename T, typename Convert> 123 void 124 test_with_plus(T init, T trash, Convert convert) 125 { 126 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) 127 { 128 Sequence<T> in(n, convert); 129 Sequence<T> expected(in); 130 Sequence<T> out(n, [&](int32_t) { return trash; }); 131 132 invoke_on_all_policies(test_scan_with_plus(), in.begin(), in.end(), out.begin(), out.end(), expected.begin(), 133 expected.end(), in.size(), init, trash); 134 invoke_on_all_policies(test_scan_with_plus(), in.cbegin(), in.cend(), out.begin(), out.end(), expected.begin(), 135 expected.end(), in.size(), init, trash); 136 } 137 } 138 struct test_scan_with_binary_op 139 { 140 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T, 141 typename BinaryOp> 142 typename std::enable_if<!TestUtils::isReverse<Iterator1>::value, void>::type 143 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last, 144 Iterator3 expected_first, Iterator3 expected_last, Size n, T init, BinaryOp binary_op, T trash) 145 { 146 using namespace std; 147 148 auto orr1 = inclusive ? inclusive_scan_serial(in_first, in_last, expected_first, binary_op, init) 149 : exclusive_scan_serial(in_first, in_last, expected_first, init, binary_op); 150 auto orr = inclusive ? inclusive_scan(exec, in_first, in_last, out_first, binary_op, init) 151 : exclusive_scan(exec, in_first, in_last, out_first, init, binary_op); 152 153 EXPECT_TRUE(out_last == orr, "scan returned wrong iterator"); 154 check_and_reset(expected_first, out_first, n, trash); 155 } 156 157 template <typename Policy, typename Iterator1, typename Iterator2, typename Iterator3, typename Size, typename T, 158 typename BinaryOp> 159 typename std::enable_if<TestUtils::isReverse<Iterator1>::value, void>::type 160 operator()(Policy&& exec, Iterator1 in_first, Iterator1 in_last, Iterator2 out_first, Iterator2 out_last, 161 Iterator3 expected_first, Iterator3 expected_last, Size n, T init, BinaryOp binary_op, T trash) 162 { 163 } 164 }; 165 166 template <typename In, typename Out, typename BinaryOp> 167 void 168 test_matrix(Out init, BinaryOp binary_op, Out trash) 169 { 170 for (size_t n = 0; n <= 100000; n = n <= 16 ? n + 1 : size_t(3.1415 * n)) 171 { 172 Sequence<In> in(n, [](size_t k) { return In(k, k + 1); }); 173 174 Sequence<Out> out(n, [&](size_t) { return trash; }); 175 Sequence<Out> expected(n, [&](size_t) { return trash; }); 176 177 invoke_on_all_policies(test_scan_with_binary_op(), in.begin(), in.end(), out.begin(), out.end(), 178 expected.begin(), expected.end(), in.size(), init, binary_op, trash); 179 invoke_on_all_policies(test_scan_with_binary_op(), in.cbegin(), in.cend(), out.begin(), out.end(), 180 expected.begin(), expected.end(), in.size(), init, binary_op, trash); 181 } 182 } 183 184 int32_t 185 main() 186 { 187 for (int32_t mode = 0; mode < 2; ++mode) 188 { 189 inclusive = mode != 0; 190 #if !__PSTL_ICC_19_TEST_SIMD_UDS_WINDOWS_RELEASE_BROKEN 191 // Test with highly restricted type and associative but not commutative operation 192 test_matrix<Matrix2x2<int32_t>, Matrix2x2<int32_t>>(Matrix2x2<int32_t>(), multiply_matrix<int32_t>, 193 Matrix2x2<int32_t>(-666, 666)); 194 #endif 195 196 // Since the implict "+" forms of the scan delegate to the generic forms, 197 // there's little point in using a highly restricted type, so just use double. 198 test_with_plus<float64_t>(inclusive ? 0.0 : -1.0, -666.0, 199 [](uint32_t k) { return float64_t((k % 991 + 1) ^ (k % 997 + 2)); }); 200 } 201 std::cout << done() << std::endl; 202 return 0; 203 } 204