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