libstdc++-v3/testsuite/25_algorithms/pstl/alg_sorting/partial_sort_copy.cc

   1 // -*- C++ -*-
   2 // { dg-options "-std=gnu++17 -ltbb" }
   3 // { dg-do run { target c++17 } }
   4 // { dg-timeout-factor 3 }
   5 // { dg-require-effective-target tbb-backend }
   6
   7 //===-- partial_sort_copy.pass.cpp ----------------------------------------===//
   8 //
   9 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  10 // See https://llvm.org/LICENSE.txt for license information.
  11 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 // Tests for partial_sort_copy
  16
  17 #include <cmath>
  18 #include "pstl/pstl_test_config.h"
  19
  20 #ifdef PSTL_STANDALONE_TESTS
  21 #include "pstl/execution"
  22 #include "pstl/algorithm"
  23 #else
  24 #include <execution>
  25 #include <algorithm>
  26 #endif // PSTL_STANDALONE_TESTS
  27
  28 #include "pstl/test_utils.h"
  29
  30 using namespace TestUtils;
  31
  32 template <typename T>
  33 struct Num
  34 {
  35     T val;
  36
  37     Num() : val(0) {}
  38     Num(T v) : val(v) {}
  39     Num(const Num<T>& v) : val(v.val) {}
  40     Num(Num<T>&& v) : val(v.val) {}
  41     Num<T>&
  42     operator=(const Num<T>& v)
  43     {
  44         val = v.val;
  45         return *this;
  46     }
  47     operator T() const { return val; }
  48     bool
  49     operator<(const Num<T>& v) const
  50     {
  51         return val < v.val;
  52     }
  53 };
  54
  55 template <typename RandomAccessIterator>
  56 struct test_one_policy
  57 {
  58     RandomAccessIterator d_first;
  59     RandomAccessIterator d_last;
  60     RandomAccessIterator exp_first;
  61     RandomAccessIterator exp_last;
  62     // This ctor is needed because output shouldn't be transformed to any iterator type (only random access iterators are allowed)
  63     test_one_policy(RandomAccessIterator b1, RandomAccessIterator e1, RandomAccessIterator b2, RandomAccessIterator e2)
  64         : d_first(b1), d_last(e1), exp_first(b2), exp_last(e2)
  65     {
  66     }
  67 #if _PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN ||                                                            \
  68     _PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN // dummy specialization by policy type, in case of broken configuration
  69     template <typename InputIterator, typename Size, typename T, typename Compare>
  70     void
  71     operator()(pstl::execution::unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
  72                const T& trash, Compare compare)
  73     {
  74     }
  75
  76     template <typename InputIterator, typename Size, typename T, typename Compare>
  77     void
  78     operator()(pstl::execution::parallel_unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
  79                const T& trash, Compare compare)
  80     {
  81     }
  82
  83     template <typename InputIterator, typename Size, typename T>
  84     void
  85     operator()(pstl::execution::unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
  86                const T& trash)
  87     {
  88     }
  89
  90     template <typename InputIterator, typename Size, typename T>
  91     void
  92     operator()(pstl::execution::parallel_unsequenced_policy, InputIterator first, InputIterator last, Size n1, Size n2,
  93                const T& trash)
  94     {
  95     }
  96 #endif
  97
  98     template <typename Policy, typename InputIterator, typename Size, typename T, typename Compare>
  99     void
 100     operator()(Policy&& exec, InputIterator first, InputIterator last, Size n1, Size n2, const T& trash,
 101                Compare compare)
 102     {
 103         prepare_data(first, last, n1, trash);
 104         RandomAccessIterator exp = std::partial_sort_copy(first, last, exp_first, exp_last, compare);
 105         RandomAccessIterator res = std::partial_sort_copy(exec, first, last, d_first, d_last, compare);
 106
 107         EXPECT_TRUE((exp - exp_first) == (res - d_first), "wrong result from partial_sort_copy with predicate");
 108         EXPECT_EQ_N(exp_first, d_first, n2, "wrong effect from partial_sort_copy with predicate");
 109     }
 110
 111     template <typename Policy, typename InputIterator, typename Size, typename T>
 112     void
 113     operator()(Policy&& exec, InputIterator first, InputIterator last, Size n1, Size n2, const T& trash)
 114     {
 115         prepare_data(first, last, n1, trash);
 116         RandomAccessIterator exp = std::partial_sort_copy(first, last, exp_first, exp_last);
 117         RandomAccessIterator res = std::partial_sort_copy(exec, first, last, d_first, d_last);
 118
 119         EXPECT_TRUE((exp - exp_first) == (res - d_first), "wrong result from partial_sort_copy without predicate");
 120         EXPECT_EQ_N(exp_first, d_first, n2, "wrong effect from partial_sort_copy without predicate");
 121     }
 122
 123   private:
 124     template <typename InputIterator, typename Size, typename T>
 125     void
 126     prepare_data(InputIterator first, InputIterator last, Size n1, const T& trash)
 127     {
 128         // The rand()%(2*n+1) encourages generation of some duplicates.
 129         std::srand(42);
 130         std::generate(first, last, [n1]() { return T(rand() % (2 * n1 + 1)); });
 131
 132         std::fill(exp_first, exp_last, trash);
 133         std::fill(d_first, d_last, trash);
 134     }
 135 };
 136
 137 template <typename T, typename Compare>
 138 void
 139 test_partial_sort_copy(Compare compare)
 140 {
 141
 142     typedef typename Sequence<T>::iterator iterator_type;
 143     const std::size_t n_max = 100000;
 144     Sequence<T> in(n_max);
 145     Sequence<T> out(2 * n_max);
 146     Sequence<T> exp(2 * n_max);
 147     std::size_t n1 = 0;
 148     std::size_t n2;
 149     T trash = T(-666);
 150     for (; n1 < n_max; n1 = n1 <= 16 ? n1 + 1 : size_t(3.1415 * n1))
 151     {
 152         // If both sequences are equal
 153         n2 = n1;
 154         invoke_on_all_policies(
 155             test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
 156             in.begin() + n1, n1, n2, trash, compare);
 157
 158         // If first sequence is greater than second
 159         n2 = n1 / 3;
 160         invoke_on_all_policies(
 161             test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
 162             in.begin() + n1, n1, n2, trash, compare);
 163
 164         // If first sequence is less than second
 165         n2 = 2 * n1;
 166         invoke_on_all_policies(
 167             test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2), in.begin(),
 168             in.begin() + n1, n1, n2, trash, compare);
 169     }
 170     // Test partial_sort_copy without predicate
 171     n1 = n_max;
 172     n2 = 2 * n1;
 173     invoke_on_all_policies(test_one_policy<iterator_type>(out.begin(), out.begin() + n2, exp.begin(), exp.begin() + n2),
 174                            in.begin(), in.begin() + n1, n1, n2, trash);
 175 }
 176
 177 template <typename T>
 178 struct test_non_const
 179 {
 180     template <typename Policy, typename InputIterator, typename OutputInterator>
 181     void
 182     operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
 183     {
 184         invoke_if(exec, [&]() {
 185             partial_sort_copy(exec, input_iter, input_iter, out_iter, out_iter, non_const(std::less<T>()));
 186         });
 187     }
 188 };
 189
 190 int32_t
 191 main()
 192 {
 193     test_partial_sort_copy<Num<float32_t>>([](Num<float32_t> x, Num<float32_t> y) { return x < y; });
 194     test_partial_sort_copy<int32_t>([](int32_t x, int32_t y) { return x > y; });
 195
 196     test_algo_basic_double<int32_t>(run_for_rnd<test_non_const<int32_t>>());
 197
 198     std::cout << done() << std::endl;
 199     return 0;
 200 }