1 /*
2 Copyright (c) 2005-2021 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 #ifndef __TBB_test_common_concurrent_priority_queue_common_H
18 #define __TBB_test_common_concurrent_priority_queue_common_H
19
20 // We need to skip allocator_traits::is_always_equal tests for C++11 and C++14
21 #define __TBB_TEST_SKIP_IS_ALWAYS_EQUAL_CHECK (__cplusplus < 201703L)
22 #include <common/test.h>
23 #include <common/utils.h>
24 #include <oneapi/tbb/concurrent_priority_queue.h>
25 #include <oneapi/tbb/blocked_range.h>
26 #include <vector>
27
28 namespace equality_comparison_helpers {
29
30 template <typename ElementType, typename Compare, typename Allocator>
toVector(const tbb::concurrent_priority_queue<ElementType,Compare,Allocator> & source)31 std::vector<ElementType> toVector( const tbb::concurrent_priority_queue<ElementType, Compare, Allocator>& source ) {
32 auto cpq = source;
33 std::vector<ElementType> v;
34 v.reserve(cpq.size());
35
36 ElementType element;
37 while(cpq.try_pop(element)) {
38 v.emplace_back(element);
39 }
40 std::reverse(v.begin(), v.end());
41 return v;
42 }
43
44 }; // namespace equality_comparison_helpers
45
46 template <bool HasCopyCtor>
47 struct QueuePushHelper {
48 template <typename Q, typename T>
pushQueuePushHelper49 static void push(Q& q, T&& t) {
50 q.push(std::forward<T>(t));
51 }
52 };
53
54 template<>
55 template <typename Q, typename T>
push(Q & q,T && t)56 void QueuePushHelper<false>::push( Q& q, T&& t ) {
57 q.push(std::move(t));
58 }
59
60 template <bool HasCopyCtor, typename QueueType>
examine(QueueType & q1,QueueType & q2,const std::vector<typename QueueType::value_type> & vec_sorted)61 void examine( QueueType& q1, QueueType& q2, const std::vector<typename QueueType::value_type>& vec_sorted ) {
62 using value_type = typename QueueType::value_type;
63
64 REQUIRE((!q1.empty() && q1.size() == vec_sorted.size()));
65 value_type elem;
66
67 q2.clear();
68 REQUIRE((q2.empty() && !q2.size() && !q2.try_pop(elem)));
69
70 typename std::vector<value_type>::const_reverse_iterator it1;
71 for (it1 = vec_sorted.rbegin(); q1.try_pop(elem); ++it1) {
72 REQUIRE(utils::IsEqual{}(elem, *it1));
73 if (std::distance(vec_sorted.rbegin(), it1) % 2) {
74 QueuePushHelper<HasCopyCtor>::push(q2, elem);
75 } else {
76 QueuePushHelper<HasCopyCtor>::push(q2, std::move(elem));
77 }
78 }
79 REQUIRE(it1 == vec_sorted.rend());
80 REQUIRE((q1.empty() && !q1.size()));
81 REQUIRE((!q2.empty() && q2.size() == vec_sorted.size()));
82
83 q1.swap(q2);
84 REQUIRE((q2.empty() && !q2.size()));
85 REQUIRE((!q1.empty() && q1.size() == vec_sorted.size()));
86 for (it1 = vec_sorted.rbegin(); q1.try_pop(elem); ++it1)
87 REQUIRE(utils::IsEqual{}(elem, *it1));
88 REQUIRE(it1 == vec_sorted.rend());
89 };
90
91 template <typename QueueType>
examine(const QueueType & q,const std::vector<typename QueueType::value_type> & vec_sorted)92 void examine( const QueueType& q, const std::vector<typename QueueType::value_type>& vec_sorted ) {
93 QueueType q1(q), q2(q);
94 examine</*HasCopyCtor=*/true>(q1, q2, vec_sorted);
95 }
96
97 // TODO: consider wrapping each constructor test into separate TEST_CASE
98 template <typename ValueType, typename Compare>
type_tester(const std::vector<ValueType> & vec,Compare comp)99 void type_tester( const std::vector<ValueType>& vec, Compare comp ) {
100 using queue_type = tbb::concurrent_priority_queue<ValueType, Compare>;
101 REQUIRE_MESSAGE(vec.size() >= 5, "Array should have at least 5 elements");
102
103 std::vector<ValueType> vec_sorted(vec);
104 std::sort(vec_sorted.begin(), vec_sorted.end(), comp);
105
106 // Construct an empty queue
107 queue_type q1;
108 q1.assign(vec.begin(), vec.end());
109 examine(q1, vec_sorted);
110
111 // Constructor from std::initializer_list
112 queue_type q2({vec[0], vec[1], vec[2]});
113 for (auto it = vec.begin() + 3; it != vec.end(); ++it)
114 q2.push(*it);
115 examine(q2, vec_sorted);
116
117 // Assignment operator with std::initializer_list
118 queue_type q3;
119 q3 = {vec[0], vec[1], vec[2]};
120 for (auto it = vec.begin() + 3; it != vec.end(); ++it)
121 q3.push(*it);
122 examine(q3, vec_sorted);
123
124 // Copy ctor
125 queue_type q4(q1);
126 examine(q4, vec_sorted);
127
128 // Copy ctor with allocator
129 auto alloc = q1.get_allocator();
130 queue_type q4_alloc(q1, alloc);
131 examine(q4_alloc, vec_sorted);
132
133 // Constructor from the half-open interval
134 queue_type q5(vec.begin(), vec.end());
135 examine(q5, vec_sorted);
136
137 // Constructor from the allocator object
138 queue_type q6(alloc);
139 q6.assign(vec.begin(), vec.end());
140 examine(q6, vec_sorted);
141
142 // Constructor from the comparator and allocator object
143 queue_type q7(comp);
144 q7.assign(vec.begin(), vec.end());
145 examine(q7, vec_sorted);
146
147 queue_type q8(comp, alloc);
148 q8.assign(vec.begin(), vec.end());
149 examine(q8, vec_sorted);
150
151 // Constructor from the initial capacity, comparator and allocator
152 queue_type q9(100);
153 q9.assign(vec.begin(), vec.end());
154 examine(q9, vec_sorted);
155
156 queue_type q10(100, comp);
157 q10.assign(vec.begin(), vec.end());
158 examine(q10, vec_sorted);
159
160 queue_type q11(100, alloc);
161 q11.assign(vec.begin(), vec.end());
162 examine(q11, vec_sorted);
163
164 // Constructor from the half-open interval, compare and allocator object
165 queue_type q12(vec.begin(), vec.end(), comp);
166 examine(q12, vec_sorted);
167
168 queue_type q13(vec.begin(), vec.end(), alloc);
169 examine(q13, vec_sorted);
170
171 // Constructor from the std::initializer_list from the half-open interval, compare and allocator object
172 queue_type q14({vec[0], vec[1], vec[2]}, comp);
173 for (auto it = vec.begin() + 3; it != vec.end(); ++it)
174 q14.push(*it);
175 examine(q14, vec_sorted);
176
177 queue_type q15({vec[0], vec[1], vec[2]}, alloc);
178 for (auto it = vec.begin() + 3; it != vec.end(); ++it)
179 q15.push(*it);
180 examine(q15, vec_sorted);
181 }
182
183 template <typename ValueType>
type_tester(const std::vector<ValueType> & vec)184 void type_tester( const std::vector<ValueType>& vec ) {
185 type_tester(vec, std::less<ValueType>{});
186 }
187
188 struct LessForSmartPointers {
189 template <typename T>
operatorLessForSmartPointers190 bool operator()( const T& t1, const T& t2 ) {
191 return *t1 < *t2;
192 }
193
194 template <typename T>
operatorLessForSmartPointers195 bool operator()( const std::weak_ptr<T>& t1, const std::weak_ptr<T>& t2 ) {
196 return *t1.lock().get() < *t2.lock().get();
197 }
198 }; // struct LessForSmartPointers
199
200 template <typename T>
type_tester_unique_ptr(const std::vector<T> & vec)201 void type_tester_unique_ptr( const std::vector<T>& vec ) {
202 REQUIRE_MESSAGE(vec.size() >= 5, "Array should have at least 5 elements");
203
204 using value_type = std::unique_ptr<T>;
205 using queue_type = tbb::concurrent_priority_queue<value_type, LessForSmartPointers>;
206
207 std::vector<value_type> vec_sorted;
208 for (auto& item : vec) {
209 vec_sorted.push_back(value_type(new T(item)));
210 }
211 std::sort(vec_sorted.begin(), vec_sorted.end(), LessForSmartPointers{});
212
213 queue_type q1, q1_copy;
214 for (auto& item : vec) {
215 q1.push(value_type(new T(item)));
216 q1_copy.push(value_type(new T(item)));
217 }
218 examine</*HasCopyCtor=*/false>(q1, q1_copy, vec_sorted);
219
220 queue_type q3_copy;
221 q1.clear();
222
223 for (auto& item : vec) {
224 q1.emplace(new T(item));
225 }
226
227 queue_type q3(std::move(q1));
228 examine</*HasCopyCtor=*/false>(q3, q3_copy, vec_sorted);
229 }
230
231 const std::size_t MAX_ITER = 10000;
232 const std::size_t push_selector_variants = 3; // push, push rvalue and emplace
233
234 template <typename Q, typename E>
push_selector(Q & q,E e,std::size_t i)235 void push_selector(Q& q, E e, std::size_t i) {
236 switch(i % push_selector_variants) {
237 case 0: q.push(e); break;
238 case 1: q.push(std::move(e)); break;
239 case 2: q.emplace(e); break;
240 }
241 }
242
243 static std::atomic<std::size_t> counter;
244
245 template <typename T, typename C>
246 class FillBody {
247 std::size_t n_thread;
248 T my_min, my_max;
249 tbb::concurrent_priority_queue<T, C>* q;
250 public:
251 FillBody( const FillBody& ) = delete;
252 FillBody& operator=( const FillBody& ) = delete;
253
FillBody(std::size_t n,T max,T min,tbb::concurrent_priority_queue<T,C> * cpq)254 FillBody( std::size_t n, T max, T min, tbb::concurrent_priority_queue<T, C>* cpq )
255 : n_thread(n), my_min(min), my_max(max), q(cpq) {}
256
operator()257 void operator()( const std::size_t thread_id ) const {
258 T elem = my_min + T(int(thread_id));
259 for (std::size_t i = 0; i < MAX_ITER; ++i) {
260 // do some pushes
261 push_selector(*q, elem, i);
262 if (elem == my_max) elem = my_min;
263 elem = elem + T(int(n_thread));
264 }
265 }
266 }; // class FillBody
267
268 template <typename T, typename C>
269 struct EmptyBody {
270 T my_max;
271 tbb::concurrent_priority_queue<T, C>* q;
272 C less_than;
273 public:
274 EmptyBody( const EmptyBody& ) = delete;
275 EmptyBody& operator=( const EmptyBody& ) = delete;
276
EmptyBodyEmptyBody277 EmptyBody( T max, tbb::concurrent_priority_queue<T, C>* cpq )
278 : my_max(max), q(cpq) {}
279
operatorEmptyBody280 void operator()( const std::size_t ) const {
281 T elem(my_max), last;
282 if (q->try_pop(last)) {
283 ++counter;
284 while(q->try_pop(elem)) {
285 REQUIRE_MESSAGE(!less_than(last, elem), "Failed pop/priority test in EmptyBody");
286 last = elem;
287 elem = my_max;
288 ++counter;
289 }
290 }
291 }
292 }; // struct EmptyBody
293
294 template <typename T, typename C>
295 class FloggerBody {
296 tbb::concurrent_priority_queue<T, C>* q;
297 public:
298 FloggerBody( const FloggerBody& ) = delete;
299 FloggerBody& operator=( const FloggerBody& ) = delete;
300
FloggerBody(tbb::concurrent_priority_queue<T,C> * cpq)301 FloggerBody( tbb::concurrent_priority_queue<T, C>* cpq )
302 : q(cpq) {}
303
operator()304 void operator()( const std::size_t thread_id ) const {
305 T elem = T(int(thread_id + 1));
306 for (std::size_t i = 0; i < MAX_ITER; ++i) {
307 push_selector(*q, elem, i);
308 q->try_pop(elem);
309 }
310 }
311 }; // class FloggerBody
312
313 template <typename C, typename T>
test_parallel_push_pop(std::size_t n,T t_max,T t_min)314 void test_parallel_push_pop( std::size_t n, T t_max, T t_min ) {
315 std::size_t qsize;
316
317 tbb::concurrent_priority_queue<T, C> q(0);
318 FillBody<T, C> filler(n, t_max, t_min, &q);
319 EmptyBody<T, C> emptier(t_max, &q);
320
321 counter = 0;
322 utils::NativeParallelFor(n, filler);
323
324 qsize = q.size();
325 REQUIRE_MESSAGE(q.size() == n * MAX_ITER, "Failed concurrent push size test");
326 REQUIRE_MESSAGE(!q.empty(), "Failed concurrent push empty test");
327
328 utils::NativeParallelFor(n, emptier);
329 REQUIRE_MESSAGE(counter == qsize, "Failed pop size test");
330 REQUIRE_MESSAGE(q.size() == 0, "Failed pop empty test");
331 }
332
333 template <typename C, typename T>
test_flogger(std::size_t n)334 void test_flogger( std::size_t n ) {
335 tbb::concurrent_priority_queue<T, C> q(0);
336 utils::NativeParallelFor(n, FloggerBody<T, C>{&q});
337 REQUIRE_MESSAGE(q.empty(), "Failed flogger empty test");
338 REQUIRE_MESSAGE(!q.size(), "Failed flogger size test");
339 }
340
341 #endif // __TBB_test_common_concurrent_priority_queue_common_H
342