1 /*
2     Copyright (c) 2005-2020 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>
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>
49     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>
56 void QueuePushHelper<false>::push( Q& q, T&& t ) {
57     q.push(std::move(t));
58 }
59 
60 template <bool HasCopyCtor, typename QueueType>
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>
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>
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>
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>
190     bool operator()( const T& t1, const T& t2 ) {
191         return *t1 < *t2;
192     }
193 
194     template <typename T>
195     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>
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>
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 
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 
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 
277     EmptyBody( T max, tbb::concurrent_priority_queue<T, C>* cpq )
278         : my_max(max), q(cpq) {}
279 
280     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 
301     FloggerBody( tbb::concurrent_priority_queue<T, C>* cpq )
302         : q(cpq) {}
303 
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>
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>
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