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

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