]>
Commit | Line | Data |
---|---|---|
061f4578 TR |
1 | // -*- C++ -*- |
2 | // { dg-options "-std=gnu++17 -ltbb" } | |
3 | // { dg-do run { target c++17 } } | |
b6a8e347 | 4 | // { dg-timeout-factor 3 } |
061f4578 TR |
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 | } | |
f32ee8a2 TR |
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 | |
061f4578 TR |
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 | } |