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 
NumNum37     Num() : val(0) {}
NumNum38     Num(T v) : val(v) {}
NumNum39     Num(const Num<T>& v) : val(v.val) {}
NumNum40     Num(Num<T>&& v) : val(v.val) {}
41     Num<T>&
operator =Num42     operator=(const Num<T>& v)
43     {
44         val = v.val;
45         return *this;
46     }
operator TNum47     operator T() const { return val; }
48     bool
operator <Num49     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)
test_one_policytest_one_policy63     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
operator ()test_one_policy71     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
operator ()test_one_policy78     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
operator ()test_one_policy85     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
operator ()test_one_policy92     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
operator ()test_one_policy100     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
operator ()test_one_policy113     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
prepare_datatest_one_policy126     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
test_partial_sort_copy(Compare compare)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
operator ()test_non_const182     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
main()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 }
201