pstl/test/std/numerics/numeric.ops/scan.pass.cpp

   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++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 !defined(_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 }