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 #include "harness_defs.h"
18 #include "tbb/concurrent_priority_queue.h"
19 #include "tbb/atomic.h"
20 #include "tbb/blocked_range.h"
21 #include "harness.h"
22 #include <functional>
23 #include <algorithm>
24 #include "harness_allocator.h"
25 #include <vector>
26 #include "test_container_move_support.h"
27
28 #if _MSC_VER==1500 && !__INTEL_COMPILER
29 // VS2008/VC9 seems to have an issue; limits pull in math.h
30 #pragma warning( push )
31 #pragma warning( disable: 4985 )
32 #endif
33 #include <climits>
34 #if _MSC_VER==1500 && !__INTEL_COMPILER
35 #pragma warning( pop )
36 #endif
37
38 #if __INTEL_COMPILER && (_WIN32 || _WIN64) && TBB_USE_DEBUG && _CPPLIB_VER<520
39 // The Intel Compiler has an issue that causes the Microsoft Iterator
40 // Debugging code to crash in vector::pop_back when it is called after a
41 // vector::push_back throws an exception.
42 // #define _HAS_ITERATOR_DEBUGGING 0 // Setting this to 0 doesn't solve the problem
43 // and also provokes a redefinition warning
44 #define __TBB_ITERATOR_DEBUGGING_EXCEPTIONS_BROKEN
45 #endif
46
47 using namespace tbb;
48
49 const size_t MAX_ITER = 10000;
50
51 tbb::atomic<unsigned int> counter;
52
53 class my_data_type {
54 public:
55 int priority;
56 char padding[tbb::internal::NFS_MaxLineSize - sizeof(int) % tbb::internal::NFS_MaxLineSize];
my_data_type()57 my_data_type() {}
my_data_type(int init_val)58 my_data_type(int init_val) : priority(init_val) {}
operator +(const my_data_type & other) const59 const my_data_type operator+(const my_data_type& other) const {
60 return my_data_type(priority+other.priority);
61 }
operator ==(const my_data_type & other) const62 bool operator==(const my_data_type& other) const {
63 return this->priority == other.priority;
64 }
65 };
66
67 const my_data_type DATA_MIN(INT_MIN);
68 const my_data_type DATA_MAX(INT_MAX);
69
70 class my_less {
71 public:
operator ()(const my_data_type d1,const my_data_type d2) const72 bool operator()(const my_data_type d1, const my_data_type d2) const {
73 return d1.priority<d2.priority;
74 }
75 };
76
77 #if TBB_USE_EXCEPTIONS
78 class my_throwing_type : public my_data_type {
79 public:
80 static int throw_flag;
my_throwing_type()81 my_throwing_type() : my_data_type() {}
my_throwing_type(const my_throwing_type & src)82 my_throwing_type(const my_throwing_type& src) : my_data_type(src) {
83 if (my_throwing_type::throw_flag) throw 42;
84 }
operator =(const my_throwing_type & src)85 my_throwing_type& operator=(const my_throwing_type& src) {
86 priority = src.priority;
87 return *this;
88 }
89 };
90 int my_throwing_type::throw_flag = 0;
91
92 typedef concurrent_priority_queue<my_throwing_type, my_less > cpq_ex_test_type;
93 #endif
94
95 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_RVALUE_REF_PRESENT
96 const size_t push_selector_variants = 3;
97 #elif __TBB_CPP11_RVALUE_REF_PRESENT
98 const size_t push_selector_variants = 2;
99 #else
100 const size_t push_selector_variants = 1;
101 #endif
102
103 template <typename Q, typename E>
push_selector(Q & q,E e,size_t i)104 void push_selector(Q& q, E e, size_t i) {
105 switch (i%push_selector_variants) {
106 case 0: q->push(e); break;
107 #if __TBB_CPP11_RVALUE_REF_PRESENT
108 case 1: q->push(tbb::internal::move(e)); break;
109 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
110 case 2: q->emplace(e); break;
111 #endif
112 #endif
113 }
114 }
115
116 template<typename T, typename C>
117 class FillBody : NoAssign {
118 int nThread;
119 T my_max, my_min;
120 concurrent_priority_queue<T, C> *q;
121 C less_than;
122 public:
FillBody(int nThread_,T max_,T min_,concurrent_priority_queue<T,C> * q_)123 FillBody(int nThread_, T max_, T min_, concurrent_priority_queue<T, C> *q_) : nThread(nThread_), my_max(max_), my_min(min_), q(q_) {}
operator ()(const int threadID) const124 void operator()(const int threadID) const {
125 T elem = my_min + T(threadID);
126 for (size_t i=0; i<MAX_ITER; ++i) {
127 // do some pushes
128 push_selector(q, elem, i);
129 if (elem == my_max) elem = my_min;
130 elem = elem + T(nThread);
131 }
132 }
133 };
134
135 template<typename T, typename C>
136 struct EmptyBody : NoAssign {
137 int nThread;
138 T my_max;
139 concurrent_priority_queue<T, C> *q;
140 C less_than;
141 public:
EmptyBodyEmptyBody142 EmptyBody(int nThread_, T max_, concurrent_priority_queue<T, C> *q_) : nThread(nThread_), my_max(max_), q(q_) {}
operator ()EmptyBody143 void operator()(const int /*threadID*/) const {
144 T elem(my_max), last;
145 if (q->try_pop(last)) {
146 ++counter;
147 while(q->try_pop(elem)) {
148 ASSERT(!less_than(last, elem), "FAILED pop/priority test in EmptyBody.");
149 last = elem;
150 elem = my_max;
151 ++counter;
152 }
153 }
154 }
155 };
156
157 template <typename T, typename C>
158 class FloggerBody : NoAssign {
159 int nThread;
160 concurrent_priority_queue<T, C> *q;
161 public:
FloggerBody(int nThread_,concurrent_priority_queue<T,C> * q_)162 FloggerBody(int nThread_, concurrent_priority_queue<T, C> *q_) :
163 nThread(nThread_), q(q_) {}
operator ()(const int threadID) const164 void operator()(const int threadID) const {
165 T elem = T(threadID+1);
166 for (size_t i=0; i<MAX_ITER; ++i) {
167 push_selector(q, elem, i);
168 (void) q->try_pop(elem);
169 }
170 }
171 };
172
173 namespace equality_comparison_helpers {
174 struct to_vector{
175 template <typename element_type, typename compare_t, typename allocator_t>
operator ()equality_comparison_helpers::to_vector176 std::vector<element_type> operator()(tbb::concurrent_priority_queue<element_type, compare_t, allocator_t> const& source) const{
177 tbb::concurrent_priority_queue<element_type, compare_t, allocator_t> cpq((source));
178 std::vector<element_type> v; v.reserve(cpq.size());
179 element_type element;
180 while (cpq.try_pop(element)){ v.push_back(element);}
181 std::reverse(v.begin(),v.end());
182 return v;
183 }
184 };
185 }
186 //TODO: make CPQ more testable instead of hacking ad-hoc operator ==
187 template <typename element_type, typename compare_t, typename allocator_t>
operator ==(tbb::concurrent_priority_queue<element_type,compare_t,allocator_t> const & lhs,tbb::concurrent_priority_queue<element_type,compare_t,allocator_t> const & rhs)188 bool operator==(tbb::concurrent_priority_queue<element_type, compare_t, allocator_t> const& lhs, tbb::concurrent_priority_queue<element_type, compare_t, allocator_t> const& rhs){
189 using equality_comparison_helpers::to_vector;
190 return to_vector()(lhs) == to_vector()(rhs);
191 }
192
193 template <typename range, typename element_type, typename compare_t, typename allocator_t>
operator ==(tbb::concurrent_priority_queue<element_type,compare_t,allocator_t> const & lhs,range const & rhs)194 bool operator==(tbb::concurrent_priority_queue<element_type, compare_t, allocator_t> const& lhs, range const & rhs ){
195 using equality_comparison_helpers::to_vector;
196 return to_vector()(lhs) == std::vector<element_type>(rhs.begin(),rhs.end());
197 }
198
TestToVector()199 void TestToVector(){
200 using equality_comparison_helpers::to_vector;
201 int array[] = {1,5,6,8,4,7};
202 tbb::blocked_range<int *> range = Harness::make_blocked_range(array);
203 std::vector<int> source(range.begin(),range.end());
204 tbb::concurrent_priority_queue<int> q(source.begin(),source.end());
205 std::vector<int> from_cpq = to_vector()(q);
206 std::sort(source.begin(),source.end());
207 ASSERT(source == from_cpq,"equality_comparison_helpers::to_vector incorrectly copied items from CPQ?");
208 }
209
TestHelpers()210 void TestHelpers(){
211 TestToVector();
212 }
213
214 //Comparator with assert in default constructor
215 template<typename T>
216 class less_a : public std::less<T>
217 {
218 public:
less_a(bool no_assert=false)219 explicit less_a(bool no_assert = false) {
220 ASSERT(no_assert,"empty constructor should not be called");
221 };
222 };
223
TestConstructorsDestructorsAccessors()224 void TestConstructorsDestructorsAccessors() {
225 std::vector<int> v;
226 std::allocator<int> a;
227 concurrent_priority_queue<int, std::less<int> > *q, *qo;
228 concurrent_priority_queue<int, std::less<int>, std::allocator<int> > *qi;
229
230 less_a<int> l(true);
231 concurrent_priority_queue<int, less_a<int> > *ql;
232 concurrent_priority_queue<int, less_a<int>, std::allocator<int> > *qla;
233
234 // Test constructors/destructors
235 REMARK("Testing default constructor.\n");
236 q = new concurrent_priority_queue<int, std::less<int> >();
237 REMARK("Default constructor complete.\n");
238 ASSERT(q->size()==0, "FAILED size test.");
239 ASSERT(q->empty(), "FAILED empty test.");
240 REMARK("Testing destructor.\n");
241 delete q;
242 REMARK("Destruction complete.\n");
243 REMARK("Testing capacity constructor.\n");
244 q = new concurrent_priority_queue<int, std::less<int> >(42);
245 REMARK("Capacity constructor complete.\n");
246 ASSERT(q->size()==0, "FAILED size test.");
247 ASSERT(q->empty(), "FAILED empty test.");
248 REMARK("Testing destructor.\n");
249 delete q;
250 REMARK("Destruction complete.\n");
251
252 REMARK("Testing allocator constructor.\n");
253 qi = new concurrent_priority_queue<int, std::less<int>, std::allocator<int> >(a);
254 REMARK("Allocator constructor complete.\n");
255 ASSERT(qi->size()==0, "FAILED size test.");
256 ASSERT(qi->empty(), "FAILED empty test.");
257 REMARK("Testing destructor.\n");
258 delete qi;
259 REMARK("Destruction complete.\n");
260
261 REMARK("Testing compare constructor.\n");
262 ql = new concurrent_priority_queue<int, less_a<int> >(l);
263 REMARK("Compare constructor complete.\n");
264 ASSERT(ql->size()==0, "FAILED size test.");
265 ASSERT(ql->empty(), "FAILED empty test.");
266 REMARK("Testing destructor.\n");
267 delete ql;
268 REMARK("Destruction complete.\n");
269
270 REMARK("Testing compare+allocator constructor.\n");
271 qla = new concurrent_priority_queue<int, less_a<int>, std::allocator<int> >(l, a);
272 REMARK("Compare+allocator constructor complete.\n");
273 ASSERT(qla->size()==0, "FAILED size test.");
274 ASSERT(qla->empty(), "FAILED empty test.");
275 REMARK("Testing destructor.\n");
276 delete qla;
277 REMARK("Destruction complete.\n");
278
279 REMARK("Testing capacity+allocator constructor.\n");
280 qi = new concurrent_priority_queue<int, std::less<int>, std::allocator<int> >(42, a);
281 REMARK("Capacity+allocator constructor complete.\n");
282 ASSERT(qi->size()==0, "FAILED size test.");
283 ASSERT(qi->empty(), "FAILED empty test.");
284 REMARK("Testing destructor.\n");
285 delete qi;
286 REMARK("Destruction complete.\n");
287
288 REMARK("Testing capacity+compare constructor.\n");
289 ql = new concurrent_priority_queue<int, less_a<int> >(42, l);
290 REMARK("Capacity+compare constructor complete.\n");
291 ASSERT(ql->size()==0, "FAILED size test.");
292 ASSERT(ql->empty(), "FAILED empty test.");
293 REMARK("Testing destructor.\n");
294 delete ql;
295 REMARK("Destruction complete.\n");
296
297 REMARK("Testing capacity+compare+allocator constructor.\n");
298 qla = new concurrent_priority_queue<int, less_a<int>, std::allocator<int> >(42, l, a);
299 REMARK("Capacity+compare+allocator constructor complete.\n");
300 ASSERT(qla->size()==0, "FAILED size test.");
301 ASSERT(qla->empty(), "FAILED empty test.");
302 REMARK("Testing destructor.\n");
303 delete qla;
304 REMARK("Destruction complete.\n");
305
306 REMARK("Destruction complete.\n");
307 REMARK("Testing iterator filler constructor.\n");
308 for (int i=0; i<42; ++i)
309 v.push_back(i);
310 q = new concurrent_priority_queue<int, std::less<int> >(v.begin(), v.end());
311 REMARK("Iterator filler constructor complete.\n");
312 ASSERT(q->size()==42, "FAILED vector/size test.");
313 ASSERT(!q->empty(), "FAILED vector/empty test.");
314 ASSERT(*q == v, "FAILED vector/equality test.");
315
316 REMARK("Destruction complete.\n");
317 REMARK("Testing iterator filler +compare constructor.\n");
318 ql = new concurrent_priority_queue<int, less_a<int> >(v.begin(), v.end(), l);
319 REMARK("Iterator filler +compare constructor complete.\n");
320 ASSERT(ql->size()==42, "FAILED vector/size test.");
321 ASSERT(!ql->empty(), "FAILED vector/empty test.");
322 REMARK("Testing destructor.\n");
323 delete ql;
324 REMARK("Destruction complete.\n");
325
326 REMARK("Testing copy constructor.\n");
327 qo = new concurrent_priority_queue<int, std::less<int> >(*q);
328 REMARK("Copy constructor complete.\n");
329 ASSERT(qo->size()==42, "FAILED cpq/size test.");
330 ASSERT(!qo->empty(), "FAILED cpq/empty test.");
331 ASSERT(*q == *qo, "FAILED cpq/equality test.");
332
333 REMARK("Testing destructor.\n");
334 delete q;
335 delete qo;
336 REMARK("Destruction complete.\n");
337 }
338
TestAssignmentClearSwap()339 void TestAssignmentClearSwap() {
340 typedef concurrent_priority_queue<int, std::less<int> > cpq_type;
341 std::vector<int> v;
342 cpq_type *q, *qo;
343 int e;
344
345 for (int i=0; i<42; ++i)
346 v.push_back(i);
347 q = new cpq_type(v.begin(), v.end());
348 qo = new cpq_type();
349
350 REMARK("Testing assignment (1).\n");
351 *qo = *q;
352 REMARK("Assignment complete.\n");
353 ASSERT(qo->size()==42, "FAILED assignment/size test.");
354 ASSERT(!qo->empty(), "FAILED assignment/empty test.");
355 ASSERT(*qo == v,"FAILED assignment/equality test");
356
357 cpq_type assigned_q;
358 REMARK("Testing assign(begin,end) (2).\n");
359 assigned_q.assign(v.begin(), v.end());
360 REMARK("Assignment complete.\n");
361 ASSERT(assigned_q.size()==42, "FAILED assignment/size test.");
362 ASSERT(!assigned_q.empty(), "FAILED assignment/empty test.");
363 ASSERT(assigned_q == v,"FAILED assignment/equality test");
364
365 REMARK("Testing clear.\n");
366 q->clear();
367 REMARK("Clear complete.\n");
368 ASSERT(q->size()==0, "FAILED clear/size test.");
369 ASSERT(q->empty(), "FAILED clear/empty test.");
370
371 for (size_t i=0; i<5; ++i)
372 (void) qo->try_pop(e);
373
374 REMARK("Testing assignment (3).\n");
375 *q = *qo;
376 REMARK("Assignment complete.\n");
377 ASSERT(q->size()==37, "FAILED assignment/size test.");
378 ASSERT(!q->empty(), "FAILED assignment/empty test.");
379
380 for (size_t i=0; i<5; ++i)
381 (void) qo->try_pop(e);
382
383 REMARK("Testing swap.\n");
384 q->swap(*qo);
385 REMARK("Swap complete.\n");
386 ASSERT(q->size()==32, "FAILED swap/size test.");
387 ASSERT(!q->empty(), "FAILED swap/empty test.");
388 ASSERT(qo->size()==37, "FAILED swap_operand/size test.");
389 ASSERT(!qo->empty(), "FAILED swap_operand/empty test.");
390 delete q;
391 delete qo;
392 }
393
TestSerialPushPop()394 void TestSerialPushPop() {
395 concurrent_priority_queue<int, std::less<int> > *q;
396 int e=42, prev=INT_MAX;
397 size_t count=0;
398
399 q = new concurrent_priority_queue<int, std::less<int> >(MAX_ITER);
400 REMARK("Testing serial push.\n");
401 for (size_t i=0; i<MAX_ITER; ++i) {
402 push_selector(q, e, i);
403 e = e*-1 + int(i);
404 }
405 REMARK("Pushing complete.\n");
406 ASSERT(q->size()==MAX_ITER, "FAILED push/size test.");
407 ASSERT(!q->empty(), "FAILED push/empty test.");
408
409 REMARK("Testing serial pop.\n");
410 while (!q->empty()) {
411 ASSERT(q->try_pop(e), "FAILED pop test.");
412 ASSERT(prev>=e, "FAILED pop/priority test.");
413 prev = e;
414 ++count;
415 ASSERT(q->size()==MAX_ITER-count, "FAILED swap/size test.");
416 ASSERT(!q->empty() || count==MAX_ITER, "FAILED swap/empty test.");
417 }
418 ASSERT(!q->try_pop(e), "FAILED: successful pop from the empty queue.");
419 REMARK("Popping complete.\n");
420 delete q;
421 }
422
423 template <typename T, typename C>
TestParallelPushPop(int nThreads,T t_max,T t_min,C)424 void TestParallelPushPop(int nThreads, T t_max, T t_min, C /*compare*/) {
425 size_t qsize;
426
427 concurrent_priority_queue<T, C> *q = new concurrent_priority_queue<T, C>(0);
428 FillBody<T, C> filler(nThreads, t_max, t_min, q);
429 EmptyBody<T, C> emptier(nThreads, t_max, q);
430 counter = 0;
431 REMARK("Testing parallel push.\n");
432 NativeParallelFor(nThreads, filler);
433 REMARK("Pushing complete.\n");
434 qsize = q->size();
435 ASSERT(q->size()==nThreads*MAX_ITER, "FAILED push/size test.");
436 ASSERT(!q->empty(), "FAILED push/empty test.");
437
438 REMARK("Testing parallel pop.\n");
439 NativeParallelFor(nThreads, emptier);
440 REMARK("Popping complete.\n");
441 ASSERT(counter==qsize, "FAILED pop/size test.");
442 ASSERT(q->size()==0, "FAILED pop/empty test.");
443
444 q->clear();
445 delete(q);
446 }
447
TestExceptions()448 void TestExceptions() {
449 #if TBB_USE_EXCEPTIONS
450 const size_t TOO_LARGE_SZ = 1000000000;
451 my_throwing_type elem;
452
453 REMARK("Testing basic constructor exceptions.\n");
454 // Allocate empty queue should not throw no matter the type
455 try {
456 my_throwing_type::throw_flag = 1;
457 cpq_ex_test_type q;
458 } catch(...) {
459 #if !(_MSC_VER==1900)
460 ASSERT(false, "FAILED: allocating empty queue should not throw exception.\n");
461 // VS2015 warns about the code in this catch block being unreachable
462 #endif
463 }
464 // Allocate small queue should not throw for reasonably sized type
465 try {
466 my_throwing_type::throw_flag = 1;
467 cpq_ex_test_type q(42);
468 } catch(...) {
469 ASSERT(false, "FAILED: allocating small queue should not throw exception.\n");
470 }
471 // Allocate a queue with too large initial size
472 try {
473 my_throwing_type::throw_flag = 0;
474 cpq_ex_test_type q(TOO_LARGE_SZ);
475 REMARK("FAILED: Huge queue did not throw exception.\n");
476 } catch(...) {}
477
478 cpq_ex_test_type *pq;
479 try {
480 my_throwing_type::throw_flag = 0;
481 pq = NULL;
482 pq = new cpq_ex_test_type(TOO_LARGE_SZ);
483 REMARK("FAILED: Huge queue did not throw exception.\n");
484 delete pq;
485 } catch(...) {
486 ASSERT(!pq, "FAILED: pq should not be touched when constructor throws.\n");
487 }
488 REMARK("Basic constructor exceptions testing complete.\n");
489 REMARK("Testing copy constructor exceptions.\n");
490 my_throwing_type::throw_flag = 0;
491 cpq_ex_test_type src_q(42);
492 elem.priority = 42;
493 for (size_t i=0; i<42; ++i) src_q.push(elem);
494 try {
495 my_throwing_type::throw_flag = 1;
496 cpq_ex_test_type q(src_q);
497 REMARK("FAILED: Copy construct did not throw exception.\n");
498 } catch(...) {}
499 try {
500 my_throwing_type::throw_flag = 1;
501 pq = NULL;
502 pq = new concurrent_priority_queue<my_throwing_type, my_less >(src_q);
503 REMARK("FAILED: Copy construct did not throw exception.\n");
504 delete pq;
505 } catch(...) {
506 ASSERT(!pq, "FAILED: pq should not be touched when constructor throws.\n");
507 }
508 REMARK("Copy constructor exceptions testing complete.\n");
509 REMARK("Testing assignment exceptions.\n");
510 // Assignment is copy-swap, so it should be exception safe
511 my_throwing_type::throw_flag = 0;
512 cpq_ex_test_type assign_q(24);
513 try {
514 my_throwing_type::throw_flag = 1;
515 assign_q = src_q;
516 REMARK("FAILED: Assign did not throw exception.\n");
517 } catch(...) {
518 ASSERT(assign_q.empty(), "FAILED: assign_q should be empty.\n");
519 }
520 REMARK("Assignment exceptions testing complete.\n");
521 #ifndef __TBB_ITERATOR_DEBUGGING_EXCEPTIONS_BROKEN
522 REMARK("Testing push exceptions.\n");
523 for (size_t i=0; i<push_selector_variants; ++i) {
524 my_throwing_type::throw_flag = 0;
525 pq = new cpq_ex_test_type(3);
526 try {
527 push_selector(pq, elem, i);
528 push_selector(pq, elem, i);
529 push_selector(pq, elem, i);
530 } catch(...) {
531 ASSERT(false, "FAILED: Push should not throw exception... yet.\n");
532 }
533 try { // should crash on copy during expansion of vector
534 my_throwing_type::throw_flag = 1;
535 push_selector(pq, elem, i);
536 REMARK("FAILED: Push did not throw exception.\n");
537 } catch(...) {
538 ASSERT(!pq->empty(), "FAILED: pq should not be empty.\n");
539 ASSERT(pq->size()==3, "FAILED: pq should be only three elements.\n");
540 ASSERT(pq->try_pop(elem), "FAILED: pq is not functional.\n");
541 }
542 delete pq;
543
544 my_throwing_type::throw_flag = 0;
545 pq = new cpq_ex_test_type(3);
546 try {
547 push_selector(pq, elem, i);
548 push_selector(pq, elem, i);
549 } catch(...) {
550 ASSERT(false, "FAILED: Push should not throw exception... yet.\n");
551 }
552 try { // should crash on push copy of element
553 my_throwing_type::throw_flag = 1;
554 push_selector(pq, elem, i);
555 REMARK("FAILED: Push did not throw exception.\n");
556 } catch(...) {
557 ASSERT(!pq->empty(), "FAILED: pq should not be empty.\n");
558 ASSERT(pq->size()==2, "FAILED: pq should be only two elements.\n");
559 ASSERT(pq->try_pop(elem), "FAILED: pq is not functional.\n");
560 }
561 delete pq;
562 }
563 REMARK("Push exceptions testing complete.\n");
564 #endif
565 #endif // TBB_USE_EXCEPTIONS
566 }
567
568 template <typename T, typename C>
TestFlogger(int nThreads,T,C)569 void TestFlogger(int nThreads, T /*max*/, C /*compare*/) {
570 REMARK("Testing queue flogger.\n");
571 concurrent_priority_queue<T, C> *q = new concurrent_priority_queue<T, C> (0);
572 NativeParallelFor(nThreads, FloggerBody<T, C >(nThreads, q));
573 ASSERT(q->empty(), "FAILED flogger/empty test.");
574 ASSERT(!q->size(), "FAILED flogger/size test.");
575 REMARK("Flogging complete.\n");
576 delete q;
577 }
578
579 #if __TBB_INITIALIZER_LISTS_PRESENT
580 #include "test_initializer_list.h"
581
TestInitList()582 void TestInitList(){
583 REMARK("testing initializer_list methods \n");
584 using namespace initializer_list_support_tests;
585 TestInitListSupport<tbb::concurrent_priority_queue<char> >({1,2,3,4,5});
586 TestInitListSupport<tbb::concurrent_priority_queue<int> >({});
587 }
588 #endif //if __TBB_INITIALIZER_LISTS_PRESENT
589
590 struct special_member_calls_t {
591 size_t copy_constructor_called_times;
592 size_t move_constructor_called_times;
593 size_t copy_assignment_called_times;
594 size_t move_assignment_called_times;
595
operator ==(special_member_calls_t const & lhs,special_member_calls_t const & rhs)596 bool friend operator==(special_member_calls_t const& lhs, special_member_calls_t const& rhs){
597 return
598 lhs.copy_constructor_called_times == rhs.copy_constructor_called_times
599 && lhs.move_constructor_called_times == rhs.move_constructor_called_times
600 && lhs.copy_assignment_called_times == rhs.copy_assignment_called_times
601 && lhs.move_assignment_called_times == rhs.move_assignment_called_times;
602 }
603
604 };
605 #if __TBB_CPP11_RVALUE_REF_PRESENT
606 struct MoveOperationTracker {
607 static size_t copy_constructor_called_times;
608 static size_t move_constructor_called_times;
609 static size_t copy_assignment_called_times;
610 static size_t move_assignment_called_times;
611
special_member_callsMoveOperationTracker612 static special_member_calls_t special_member_calls(){
613 special_member_calls_t calls = {copy_constructor_called_times, move_constructor_called_times, copy_assignment_called_times, move_assignment_called_times};
614 return calls;
615 }
616 static size_t value_counter;
617
618 size_t value;
619
MoveOperationTrackerMoveOperationTracker620 MoveOperationTracker() : value(++value_counter) {}
MoveOperationTrackerMoveOperationTracker621 MoveOperationTracker( const size_t value_ ) : value( value_ ) {}
__TBB_NOEXCEPTMoveOperationTracker622 ~MoveOperationTracker() __TBB_NOEXCEPT( true ) {
623 value = 0;
624 }
MoveOperationTrackerMoveOperationTracker625 MoveOperationTracker(const MoveOperationTracker& m) : value(m.value) {
626 ASSERT(m.value, "The object has been moved or destroyed");
627 ++copy_constructor_called_times;
628 }
__TBB_NOEXCEPTMoveOperationTracker629 MoveOperationTracker(MoveOperationTracker&& m) __TBB_NOEXCEPT(true) : value(m.value) {
630 ASSERT(m.value, "The object has been moved or destroyed");
631 m.value = 0;
632 ++move_constructor_called_times;
633 }
operator =MoveOperationTracker634 MoveOperationTracker& operator=(MoveOperationTracker const& m) {
635 ASSERT(m.value, "The object has been moved or destroyed");
636 value = m.value;
637 ++copy_assignment_called_times;
638 return *this;
639 }
operator =MoveOperationTracker640 MoveOperationTracker& operator=(MoveOperationTracker&& m) __TBB_NOEXCEPT(true) {
641 ASSERT(m.value, "The object has been moved or destroyed");
642 value = m.value;
643 m.value = 0;
644 ++move_assignment_called_times;
645 return *this;
646 }
647
operator <MoveOperationTracker648 bool operator<(MoveOperationTracker const &m) const {
649 ASSERT(value, "The object has been moved or destroyed");
650 ASSERT(m.value, "The object has been moved or destroyed");
651 return value < m.value;
652 }
653
operator ==(MoveOperationTracker const & lhs,MoveOperationTracker const & rhs)654 friend bool operator==(MoveOperationTracker const &lhs, MoveOperationTracker const &rhs){
655 return !(lhs < rhs) && !(rhs <lhs);
656 }
657 };
658 size_t MoveOperationTracker::copy_constructor_called_times = 0;
659 size_t MoveOperationTracker::move_constructor_called_times = 0;
660 size_t MoveOperationTracker::copy_assignment_called_times = 0;
661 size_t MoveOperationTracker::move_assignment_called_times = 0;
662 size_t MoveOperationTracker::value_counter = 0;
663
664 template<typename allocator = tbb::cache_aligned_allocator<MoveOperationTracker> >
665 struct cpq_src_fixture : NoAssign {
666 enum {default_container_size = 100};
667 typedef concurrent_priority_queue<MoveOperationTracker, std::less<MoveOperationTracker>, typename allocator:: template rebind<MoveOperationTracker>::other > cpq_t;
668
669 cpq_t cpq_src;
670 const size_t container_size;
671
initcpq_src_fixture672 void init(){
673 size_t &mcct = MoveOperationTracker::move_constructor_called_times;
674 size_t &ccct = MoveOperationTracker::copy_constructor_called_times;
675 size_t &cact = MoveOperationTracker::copy_assignment_called_times;
676 size_t &mact = MoveOperationTracker::move_assignment_called_times;
677 mcct = ccct = cact = mact = 0;
678
679 for (size_t i=1; i <= container_size; ++i){
680 cpq_src.push(MoveOperationTracker(i));
681 }
682 ASSERT(cpq_src.size() == container_size, "error in test setup ?" );
683 }
684
cpq_src_fixturecpq_src_fixture685 cpq_src_fixture(size_t size = default_container_size) : container_size(size){
686 init();
687 }
688
cpq_src_fixturecpq_src_fixture689 cpq_src_fixture(typename cpq_t::allocator_type const& a, size_t size = default_container_size) : cpq_src(a), container_size(size){
690 init();
691 }
692
693 };
694
695
TestStealingMoveConstructor()696 void TestStealingMoveConstructor(){
697 typedef cpq_src_fixture<> fixture_t;
698 fixture_t fixture;
699 fixture_t::cpq_t src_copy(fixture.cpq_src);
700
701 special_member_calls_t previous = MoveOperationTracker::special_member_calls();
702 fixture_t::cpq_t dst(std::move(fixture.cpq_src));
703 ASSERT(previous == MoveOperationTracker::special_member_calls(), "stealing move constructor should not create any new elements");
704
705 ASSERT(dst == src_copy, "cpq content changed during stealing move ?");
706 }
707
TestStealingMoveConstructorOtherAllocatorInstance()708 void TestStealingMoveConstructorOtherAllocatorInstance(){
709 typedef two_memory_arenas_fixture<MoveOperationTracker> arena_fixture_t;
710 typedef cpq_src_fixture<arena_fixture_t::allocator_t > fixture_t;
711
712 arena_fixture_t arena_fixture(8 * fixture_t::default_container_size, "TestStealingMoveConstructorOtherAllocatorInstance");
713 fixture_t fixture(arena_fixture.source_allocator);
714 fixture_t::cpq_t src_copy(fixture.cpq_src);
715
716 special_member_calls_t previous = MoveOperationTracker::special_member_calls();
717 fixture_t::cpq_t dst(std::move(fixture.cpq_src), arena_fixture.source_allocator);
718 ASSERT(previous == MoveOperationTracker::special_member_calls(), "stealing move constructor should not create any new elements");
719
720 ASSERT(dst == src_copy, "cpq content changed during stealing move ?");
721 }
722
TestPerElementMoveConstructorOtherAllocatorInstance()723 void TestPerElementMoveConstructorOtherAllocatorInstance(){
724 typedef two_memory_arenas_fixture<MoveOperationTracker> arena_fixture_t;
725 typedef cpq_src_fixture<arena_fixture_t::allocator_t > fixture_t;
726
727 arena_fixture_t arena_fixture(8 * fixture_t::default_container_size, "TestPerElementMoveConstructorOtherAllocatorInstance");
728 fixture_t fixture(arena_fixture.source_allocator);
729 fixture_t::cpq_t src_copy(fixture.cpq_src);
730
731 special_member_calls_t move_ctor_called_cpq_size_times = MoveOperationTracker::special_member_calls();
732 move_ctor_called_cpq_size_times.move_constructor_called_times += fixture.container_size;
733
734 fixture_t::cpq_t dst(std::move(fixture.cpq_src), arena_fixture.dst_allocator);
735 ASSERT(move_ctor_called_cpq_size_times == MoveOperationTracker::special_member_calls(), "Per element move constructor should move initialize all new elements");
736 ASSERT(dst == src_copy, "cpq content changed during move ?");
737 }
738
TestgMoveConstructor()739 void TestgMoveConstructor(){
740 TestStealingMoveConstructor();
741 TestStealingMoveConstructorOtherAllocatorInstance();
742 TestPerElementMoveConstructorOtherAllocatorInstance();
743 }
744
TestStealingMoveAssignOperator()745 void TestStealingMoveAssignOperator(){
746 typedef cpq_src_fixture<> fixture_t;
747 fixture_t fixture;
748 fixture_t::cpq_t src_copy(fixture.cpq_src);
749
750 fixture_t::cpq_t dst;
751 special_member_calls_t previous = MoveOperationTracker::special_member_calls();
752 dst = std::move(fixture.cpq_src);
753 ASSERT(previous == MoveOperationTracker::special_member_calls(), "stealing move assign operator should not create any new elements");
754
755 ASSERT(dst == src_copy, "cpq content changed during stealing move ?");
756 }
757
TestStealingMoveAssignOperatorWithStatefulAllocator()758 void TestStealingMoveAssignOperatorWithStatefulAllocator(){
759 //Use stateful allocator which is propagated on assignment , i.e. POCMA = true
760 typedef two_memory_arenas_fixture<MoveOperationTracker, /*pocma =*/Harness::true_type> arena_fixture_t;
761 typedef cpq_src_fixture<arena_fixture_t::allocator_t > fixture_t;
762
763 arena_fixture_t arena_fixture(8 * fixture_t::default_container_size, "TestStealingMoveAssignOperatorWithStatefullAllocator");
764 fixture_t fixture(arena_fixture.source_allocator);
765 fixture_t::cpq_t src_copy(fixture.cpq_src);
766 fixture_t::cpq_t dst(arena_fixture.dst_allocator);
767
768 special_member_calls_t previous = MoveOperationTracker::special_member_calls();
769 dst = std::move(fixture.cpq_src);
770 ASSERT(previous == MoveOperationTracker::special_member_calls(), "stealing move assignment operator should not create any new elements");
771
772 ASSERT(dst == src_copy, "cpq content changed during stealing move ?");
773 }
774
TestPerElementMoveAssignOperator()775 void TestPerElementMoveAssignOperator(){
776 //use stateful allocator which is not propagate on assignment , i.e. POCMA = false
777 typedef two_memory_arenas_fixture<MoveOperationTracker, /*pocma =*/Harness::false_type> arena_fixture_t;
778 typedef cpq_src_fixture<arena_fixture_t::allocator_t > fixture_t;
779
780 arena_fixture_t arena_fixture(8 * fixture_t::default_container_size, "TestPerElementMoveAssignOperator");
781 fixture_t fixture(arena_fixture.source_allocator);
782 fixture_t::cpq_t src_copy(fixture.cpq_src);
783 fixture_t::cpq_t dst(arena_fixture.dst_allocator);
784
785 special_member_calls_t move_ctor_called_cpq_size_times = MoveOperationTracker::special_member_calls();
786 move_ctor_called_cpq_size_times.move_constructor_called_times += fixture.container_size;
787 dst = std::move(fixture.cpq_src);
788 ASSERT(move_ctor_called_cpq_size_times == MoveOperationTracker::special_member_calls(), "per element move assignment should move initialize new elements");
789
790 ASSERT(dst == src_copy, "cpq content changed during per element move ?");
791 }
792
TestgMoveAssignOperator()793 void TestgMoveAssignOperator(){
794 TestStealingMoveAssignOperator();
795 #if __TBB_ALLOCATOR_TRAITS_PRESENT
796 TestStealingMoveAssignOperatorWithStatefulAllocator();
797 #endif //__TBB_ALLOCATOR_TRAITS_PRESENT
798 TestPerElementMoveAssignOperator();
799 }
800
801 struct ForwardInEmplaceTester {
802 int a;
803 static bool moveCtorCalled;
ForwardInEmplaceTesterForwardInEmplaceTester804 ForwardInEmplaceTester( int a_val ) : a( a_val ) {}
ForwardInEmplaceTesterForwardInEmplaceTester805 ForwardInEmplaceTester( ForwardInEmplaceTester&& obj, int a_val ) : a( obj.a ) {
806 moveCtorCalled = true;
807 obj.a = a_val;
808 }
operator <ForwardInEmplaceTester809 bool operator<( ForwardInEmplaceTester const& ) const { return true; }
810 };
811 bool ForwardInEmplaceTester::moveCtorCalled = false;
812
813 struct NoDefaultCtorType {
814 size_t value1, value2;
NoDefaultCtorTypeNoDefaultCtorType815 NoDefaultCtorType( size_t value1_, size_t value2_ ) : value1( value1_ ), value2( value2_ ) {}
operator <NoDefaultCtorType816 bool operator<(NoDefaultCtorType const &m) const {
817 return value1+value2 < m.value1+m.value2;
818 }
819 };
820
TestMoveSupportInPushPop()821 void TestMoveSupportInPushPop() {
822 REMARK("Testing Move Support in Push/Pop...");
823 size_t &mcct = MoveOperationTracker::move_constructor_called_times;
824 size_t &ccct = MoveOperationTracker::copy_constructor_called_times;
825 size_t &cact = MoveOperationTracker::copy_assignment_called_times;
826 size_t &mact = MoveOperationTracker::move_assignment_called_times;
827 mcct = ccct = cact = mact = 0;
828
829 concurrent_priority_queue<MoveOperationTracker> q1;
830
831 ASSERT(mcct == 0, "Value must be zero-initialized");
832 ASSERT(ccct == 0, "Value must be zero-initialized");
833
834 q1.push(MoveOperationTracker());
835 ASSERT(mcct > 0, "Not working push(T&&)?");
836 ASSERT(ccct == 0, "Copying of arg occurred during push(T&&)");
837
838 MoveOperationTracker ob;
839 const size_t prev_mcct = mcct;
840 q1.push(std::move(ob));
841 ASSERT(mcct > prev_mcct, "Not working push(T&&)?");
842 ASSERT(ccct == 0, "Copying of arg occurred during push(T&&)");
843
844 ASSERT(cact == 0, "Copy assignment called during push(T&&)");
845 const size_t prev_mact = mact;
846 q1.try_pop(ob);
847 ASSERT(cact == 0, "Copy assignment called during try_pop(T&)");
848 ASSERT(mact > prev_mact, "Move assignment was not called during try_pop(T&)");
849
850 REMARK(" works.\n");
851
852 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
853 REMARK("Testing Emplace...");
854
855 concurrent_priority_queue<NoDefaultCtorType> q2;
856 q2.emplace(15, 3);
857 q2.emplace(2, 35);
858 q2.emplace(8, 8);
859
860 NoDefaultCtorType o(0, 0);
861 q2.try_pop(o);
862 ASSERT(o.value1 == 2 && o.value2 == 35, "Unexpected data popped; possible emplace() failure.");
863 q2.try_pop(o);
864 ASSERT(o.value1 == 15 && o.value2 == 3, "Unexpected data popped; possible emplace() failure.");
865 q2.try_pop(o);
866 ASSERT(o.value1 == 8 && o.value2 == 8, "Unexpected data popped; possible emplace() failure.");
867 ASSERT(!q2.try_pop(o), "The queue should be empty.");
868
869 //TODO: revise this test
870 concurrent_priority_queue<ForwardInEmplaceTester> q3;
871 ASSERT( ForwardInEmplaceTester::moveCtorCalled == false, NULL );
872 q3.emplace( ForwardInEmplaceTester(5), 2 );
873 ASSERT( ForwardInEmplaceTester::moveCtorCalled == true, "Not used std::forward in emplace()?" );
874 ForwardInEmplaceTester obj( 0 );
875 q3.try_pop( obj );
876 ASSERT( obj.a == 5, "Not used std::forward in emplace()?" );
877 ASSERT(!q3.try_pop( obj ), "The queue should be empty.");
878
879 REMARK(" works.\n");
880 #endif /* __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT */
881 }
882 #endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
883
TestCpqOnNThreads(int nThreads)884 void TestCpqOnNThreads( int nThreads ) {
885 std::less<int> int_compare;
886 my_less data_compare;
887
888 TestConstructorsDestructorsAccessors();
889 TestAssignmentClearSwap();
890 TestSerialPushPop();
891
892 TestParallelPushPop( nThreads, INT_MAX, INT_MIN, int_compare );
893 TestParallelPushPop( nThreads, (unsigned char)CHAR_MAX, (unsigned char)CHAR_MIN, int_compare );
894 TestParallelPushPop( nThreads, DATA_MAX, DATA_MIN, data_compare );
895
896 TestFlogger( nThreads, INT_MAX, int_compare );
897 TestFlogger( nThreads, (unsigned char)CHAR_MAX, int_compare );
898 TestFlogger( nThreads, DATA_MAX, data_compare );
899 #if __TBB_CPP11_RVALUE_REF_PRESENT
900 MoveOperationTracker::copy_assignment_called_times = 0;
901 TestFlogger( nThreads, MoveOperationTracker(), std::less<MoveOperationTracker>() );
902 ASSERT( MoveOperationTracker::copy_assignment_called_times == 0, "Copy assignment called during try_pop(T&)?" );
903 #endif
904
905 #if TBB_USE_EXCEPTIONS && !__TBB_THROW_ACROSS_MODULE_BOUNDARY_BROKEN
906 TestExceptions();
907 #else
908 REPORT( "Known issue: exception handling tests are skipped.\n" );
909 #endif
910 }
911
912 #if __TBB_CPP11_SMART_POINTERS_PRESENT
913 struct SmartPointersCompare {
operator ()SmartPointersCompare914 template <typename Type> bool operator() (const std::shared_ptr<Type> &t1, const std::shared_ptr<Type> &t2) {
915 return *t1 < *t2;
916 }
operator ()SmartPointersCompare917 template <typename Type> bool operator() (const std::weak_ptr<Type> &t1, const std::weak_ptr<Type> &t2) {
918 return *t1.lock().get() < *t2.lock().get();
919 }
operator ()SmartPointersCompare920 template <typename Type> bool operator() (const std::unique_ptr<Type> &t1, const std::unique_ptr<Type> &t2) {
921 return *t1 < *t2;
922 }
923 };
924 #endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
925
926 #if __TBB_CPP11_RVALUE_REF_PRESENT
927 // The helper calls copying or moving push operator if an element has copy constructor.
928 // Otherwise it calls only moving push operator.
929 template <bool hasCopyCtor>
930 struct QueuePushHelper {
931 template <typename Q, typename T>
pushQueuePushHelper932 static void push( Q &q, T &&t ) {
933 q.push( std::forward<T>(t) );
934 }
935 };
936 template <>
937 template <typename Q, typename T>
push(Q & q,T && t)938 void QueuePushHelper<false>::push( Q &q, T &&t ) {
939 q.push( std::move(t) );
940 }
941 #else
942 template <bool hasCopyCtor>
943 struct QueuePushHelper {
944 template <typename Q, typename T>
pushQueuePushHelper945 static void push( Q &q, const T &t ) {
946 q.push( t );
947 }
948 };
949 #endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
950
951 template <bool hasCopyCtor, typename Queue>
Examine(Queue & q1,Queue & q2,const std::vector<typename Queue::value_type> & vecSorted)952 void Examine(Queue &q1, Queue &q2, const std::vector<typename Queue::value_type> &vecSorted) {
953 typedef typename Queue::value_type ValueType;
954
955 ASSERT(!q1.empty() && q1.size() == vecSorted.size(), NULL);
956
957 ValueType elem;
958
959 q2.clear();
960 ASSERT(q2.empty() && !q2.size() && !q2.try_pop(elem), NULL);
961
962 typename std::vector<ValueType>::const_reverse_iterator it1;
963 for (it1 = vecSorted.rbegin(); q1.try_pop(elem); it1++) {
964 ASSERT( Harness::IsEqual()(elem, *it1), NULL );
965 if ( std::distance(vecSorted.rbegin(), it1) % 2 )
966 QueuePushHelper<hasCopyCtor>::push(q2,elem);
967 else
968 QueuePushHelper<hasCopyCtor>::push(q2,tbb::internal::move(elem));
969 }
970 ASSERT(it1 == vecSorted.rend(), NULL);
971 ASSERT(q1.empty() && !q1.size(), NULL);
972 ASSERT(!q2.empty() && q2.size() == vecSorted.size(), NULL);
973
974 q1.swap(q2);
975 ASSERT(q2.empty() && !q2.size(), NULL);
976 ASSERT(!q1.empty() && q1.size() == vecSorted.size(), NULL);
977 for (it1 = vecSorted.rbegin(); q1.try_pop(elem); it1++) ASSERT(Harness::IsEqual()(elem, *it1), NULL);
978 ASSERT(it1 == vecSorted.rend(), NULL);
979
980 typename Queue::allocator_type a = q1.get_allocator();
981 ValueType *ptr = a.allocate(1);
982 ASSERT(ptr, NULL);
983 a.deallocate(ptr, 1);
984 }
985
986 template <typename Queue>
Examine(const Queue & q,const std::vector<typename Queue::value_type> & vecSorted)987 void Examine(const Queue &q, const std::vector<typename Queue::value_type> &vecSorted) {
988 Queue q1(q), q2(q);
989 Examine</*hasCopyCtor=*/true>( q1, q2, vecSorted );
990 }
991
992 template <typename ValueType, typename Compare>
TypeTester(const std::vector<ValueType> & vec,Compare comp)993 void TypeTester(const std::vector<ValueType> &vec, Compare comp) {
994 typedef tbb::concurrent_priority_queue<ValueType, Compare> Queue;
995 typedef tbb::concurrent_priority_queue< ValueType, Compare, debug_allocator<ValueType> > QueueDebugAlloc;
996 __TBB_ASSERT(vec.size() >= 5, "Array should have at least 5 elements");
997
998 std::vector<ValueType> vecSorted(vec);
999 std::sort( vecSorted.begin(), vecSorted.end(), comp );
1000
1001 // Construct an empty queue.
1002 Queue q1;
1003 q1.assign(vec.begin(), vec.end());
1004 Examine(q1, vecSorted);
1005 #if __TBB_INITIALIZER_LISTS_PRESENT
1006 // Constructor from initializer_list.
1007 Queue q2({ vec[0], vec[1], vec[2] });
1008 for (typename std::vector<ValueType>::const_iterator it = vec.begin() + 3; it != vec.end(); ++it) q2.push(*it);
1009 Examine(q2, vecSorted);
1010 Queue q3;
1011 q3 = { vec[0], vec[1], vec[2] };
1012 for (typename std::vector<ValueType>::const_iterator it = vec.begin() + 3; it != vec.end(); ++it) q3.push(*it);
1013 Examine(q3, vecSorted);
1014 #endif
1015 // Copying constructor.
1016 Queue q4(q1);
1017 Examine(q4, vecSorted);
1018 // Construct with non-default allocator.
1019 QueueDebugAlloc q5;
1020 q5.assign(vec.begin(), vec.end());
1021 Examine(q5, vecSorted);
1022 // Copying constructor for vector with different allocator type.
1023 QueueDebugAlloc q6(q5);
1024 Examine(q6, vecSorted);
1025 // Construction with copying iteration range and given allocator instance.
1026 Queue q7(vec.begin(), vec.end());
1027 Examine(q7, vecSorted);
1028 typename QueueDebugAlloc::allocator_type a;
1029 QueueDebugAlloc q8(a);
1030 q8.assign(vec.begin(), vec.end());
1031 Examine(q8, vecSorted);
1032 }
1033
1034 #if __TBB_CPP11_SMART_POINTERS_PRESENT && __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
1035 template <typename T>
TypeTesterUniquePtr(const std::vector<T> & vec)1036 void TypeTesterUniquePtr(const std::vector<T> &vec) {
1037 __TBB_ASSERT(vec.size() >= 5, "Array should have at least 5 elements");
1038
1039 typedef std::unique_ptr<T> ValueType;
1040 typedef tbb::concurrent_priority_queue<ValueType, SmartPointersCompare> Queue;
1041 typedef tbb::concurrent_priority_queue< ValueType, SmartPointersCompare, debug_allocator<ValueType> > QueueDebugAlloc;
1042
1043 std::vector<ValueType> vecSorted;
1044 for ( typename std::vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it ) {
1045 vecSorted.push_back( ValueType(new T(*it)) );
1046 }
1047 std::sort( vecSorted.begin(), vecSorted.end(), SmartPointersCompare() );
1048
1049 Queue q1, q1Copy;
1050 QueueDebugAlloc q2, q2Copy;
1051 for ( typename std::vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it ) {
1052 q1.push( ValueType(new T(*it)) );
1053 q1Copy.push( ValueType(new T(*it)) );
1054 q2.push( ValueType(new T(*it)) );
1055 q2Copy.push( ValueType(new T(*it)) );
1056 }
1057 Examine</*isCopyCtor=*/false>(q1, q1Copy, vecSorted);
1058 Examine</*isCopyCtor=*/false>(q2, q2Copy, vecSorted);
1059
1060 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
1061 Queue q3Copy;
1062 QueueDebugAlloc q4Copy;
1063
1064 q1.clear();
1065 q2.clear();
1066 for ( typename std::vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it ) {
1067 q1.emplace( new T(*it) );
1068 q3Copy.emplace( new T(*it) );
1069 q2.emplace( new T(*it) );
1070 q4Copy.emplace( new T(*it) );
1071 }
1072
1073 Queue q3( std::move(q1) );
1074 QueueDebugAlloc q4( std::move(q2) );
1075 Examine</*isCopyCtor=*/false>(q3, q3Copy, vecSorted);
1076 Examine</*isCopyCtor=*/false>(q4, q4Copy, vecSorted);
1077 #endif //__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
1078 }
1079 #endif /* __TBB_CPP11_SMART_POINTERS_PRESENT && __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT */
1080
1081 template <typename ValueType>
TypeTester(const std::vector<ValueType> & vec)1082 void TypeTester(const std::vector<ValueType> &vec) { TypeTester(vec, std::less<ValueType>()); }
1083
TestTypes()1084 void TestTypes() {
1085 const int NUMBER = 10;
1086
1087 Harness::FastRandom rnd(1234);
1088
1089 std::vector<int> arrInt;
1090 for (int i = 0; i<NUMBER; ++i) arrInt.push_back(rnd.get());
1091 std::vector< tbb::atomic<int> > arrTbb;
1092 for (int i = 0; i<NUMBER; ++i) {
1093 tbb::atomic<int> a;
1094 a = rnd.get();
1095 arrTbb.push_back(a);
1096 }
1097
1098 TypeTester(arrInt);
1099 TypeTester(arrTbb);
1100
1101 #if __TBB_CPP11_SMART_POINTERS_PRESENT
1102 std::vector< std::shared_ptr<int> > arrShr;
1103 for (int i = 0; i<NUMBER; ++i) {
1104 const int rnd_get = rnd.get();
1105 arrShr.push_back(std::make_shared<int>(rnd_get));
1106 }
1107 std::vector< std::weak_ptr<int> > arrWk;
1108 std::copy(arrShr.begin(), arrShr.end(), std::back_inserter(arrWk));
1109 TypeTester(arrShr, SmartPointersCompare());
1110 TypeTester(arrWk, SmartPointersCompare());
1111
1112 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT
1113 #if __TBB_IS_COPY_CONSTRUCTIBLE_BROKEN
1114 REPORT( "Known issue: std::is_copy_constructible is broken for move-only types. So the std::unique_ptr test is skipped.\n" );
1115 #else
1116 TypeTesterUniquePtr(arrInt);
1117 #endif /* __TBB_IS_COPY_CONSTRUCTIBLE_BROKEN */
1118 #endif /* __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_IS_COPY_CONSTRUCTIBLE_PRESENT */
1119 #else
1120 REPORT( "Known issue: C++11 smart pointer tests are skipped.\n" );
1121 #endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
1122 }
1123
1124 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1125 template <template <typename...>typename TQueue>
TestDeductionGuides()1126 void TestDeductionGuides() {
1127 using ComplexType = const std::string*;
1128 std::string s("s");
1129 std::vector<ComplexType> v;
1130 auto l = {ComplexType(&s), ComplexType(&s) };
1131
1132 // check TQueue(InputIterator, InputIterator)
1133 TQueue qv(v.begin(), v.end());
1134 static_assert(std::is_same<decltype(qv), TQueue<ComplexType> >::value);
1135
1136 // check TQueue(InputIterator, InputIterator, Allocator)
1137 TQueue qva(v.begin(), v.end(), std::allocator<ComplexType>());
1138 static_assert(std::is_same<decltype(qva), TQueue<ComplexType, std::less<ComplexType>,
1139 std::allocator<ComplexType>>>::value);
1140
1141 // check TQueue(InputIterator, InputIterator, Compare)
1142 TQueue qvc(v.begin(), v.end(), less_a<ComplexType>(true));
1143 static_assert(std::is_same<decltype(qvc), TQueue<ComplexType, less_a<ComplexType>>>::value);
1144
1145 // check TQueue(InputIterator, InputIterator, Compare, Allocator)
1146 TQueue qvca(v.begin(), v.end(), less_a<ComplexType>(true), std::allocator<ComplexType>());
1147 static_assert(std::is_same<decltype(qvca), TQueue<ComplexType, less_a<ComplexType>,
1148 std::allocator<ComplexType>>>::value);
1149
1150 // check TQueue(std::initializer_list)
1151 TQueue ql(l);
1152 static_assert(std::is_same<decltype(ql), TQueue<ComplexType>>::value);
1153
1154 // check TQueue(std::initializer_list, Allocator)
1155 TQueue qla(l, std::allocator<ComplexType>());
1156 static_assert(std::is_same<decltype(qla), TQueue<ComplexType, std::less<ComplexType>,
1157 std::allocator<ComplexType>>>::value);
1158
1159 // check TQueue(std::initializer_list, Compare)
1160 TQueue qlc(l, less_a<ComplexType>(true));
1161 static_assert(std::is_same<decltype(qlc), TQueue<ComplexType, less_a<ComplexType>>>::value);
1162
1163 // check TQueue(std::initializer_list, Compare, Allocator)
1164 TQueue qlca(l, less_a<ComplexType>(true), std::allocator<ComplexType>());
1165 static_assert(std::is_same<decltype(qlca), TQueue<ComplexType, less_a<ComplexType>,
1166 std::allocator<ComplexType>>>::value);
1167
1168 // check TQueue(TQueue &)
1169 TQueue qc(qv);
1170 static_assert(std::is_same<decltype(qv), decltype(qv)>::value);
1171
1172 // check TQueue(TQueue &, Allocator)
1173 TQueue qca(qva, std::allocator<ComplexType>());
1174 static_assert(std::is_same<decltype(qca), decltype(qva)>::value);
1175
1176 // check TQueue(TQueue &&)
1177 TQueue qm(std::move(qv));
1178 static_assert(std::is_same<decltype(qm), decltype(qv)>::value);
1179
1180 // check TQueue(TQueue &&, Allocator)
1181 TQueue qma(std::move(qva), std::allocator<ComplexType>());
1182 static_assert(std::is_same<decltype(qma), decltype(qva)>::value);
1183 }
1184 #endif
1185
TestMain()1186 int TestMain() {
1187 if (MinThread < 1)
1188 MinThread = 1;
1189
1190 TestHelpers();
1191 #if __TBB_INITIALIZER_LISTS_PRESENT
1192 TestInitList();
1193 #else
1194 REPORT("Known issue: initializer list tests are skipped.\n");
1195 #endif
1196
1197 TestTypes();
1198
1199 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1200 TestDeductionGuides<tbb::concurrent_priority_queue>();
1201 #endif
1202
1203 #if __TBB_CPP11_RVALUE_REF_PRESENT
1204 TestgMoveConstructor();
1205 TestgMoveAssignOperator();
1206 TestMoveSupportInPushPop();
1207 #else
1208 REPORT("Known issue: move support tests are skipped.\n");
1209 #endif
1210
1211 for (int p = MinThread; p <= MaxThread; ++p) {
1212 REMARK("Testing on %d threads.\n", p);
1213 TestCpqOnNThreads(p);
1214 }
1215 return Harness::Done;
1216 }
1217