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