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