1/*
2 Copyright (c) 2005-2019 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#define NOMINMAX
18#include "harness_defs.h"
19#include "tbb/concurrent_queue.h"
20#include "tbb/tick_count.h"
21#include "harness.h"
22#include "harness_allocator.h"
23
24using tbb::internal::spin_wait_while;
25
26#include <vector>
27
28static tbb::atomic<long> FooConstructed;
29static tbb::atomic<long> FooDestroyed;
30
31enum state_t{
32 LIVE=0x1234,
33 DEAD=0xDEAD
34};
35
36class Foo {
37 state_t state;
38public:
39 int thread_id;
40 int serial;
41 Foo() : state(LIVE), thread_id(0), serial(0) {
42 ++FooConstructed;
43 }
44 Foo( const Foo& item ) : state(LIVE) {
45 ASSERT( item.state==LIVE, NULL );
46 ++FooConstructed;
47 thread_id = item.thread_id;
48 serial = item.serial;
49 }
50 ~Foo() {
51 ASSERT( state==LIVE, NULL );
52 ++FooDestroyed;
53 state=DEAD;
54 thread_id=DEAD;
55 serial=DEAD;
56 }
57 void operator=( const Foo& item ) {
58 ASSERT( item.state==LIVE, NULL );
59 ASSERT( state==LIVE, NULL );
60 thread_id = item.thread_id;
61 serial = item.serial;
62 }
63 bool is_const() {return false;}
64 bool is_const() const {return true;}
65 static void clear_counters() { FooConstructed = 0; FooDestroyed = 0; }
66 static long get_n_constructed() { return FooConstructed; }
67 static long get_n_destroyed() { return FooDestroyed; }
68};
69
70// problem size
71static const int N = 50000; // # of bytes
72
73#if TBB_USE_EXCEPTIONS
74//! Exception for concurrent_queue
75class Foo_exception : public std::bad_alloc {
76public:
77 virtual const char *what() const throw() __TBB_override { return "out of Foo limit"; }
78 virtual ~Foo_exception() throw() {}
79};
80
81static tbb::atomic<long> FooExConstructed;
82static tbb::atomic<long> FooExDestroyed;
83static tbb::atomic<long> serial_source;
84static long MaxFooCount = 0;
85static const long Threshold = 400;
86
87class FooEx {
88 state_t state;
89public:
90 int serial;
91 FooEx() : state(LIVE) {
92 ++FooExConstructed;
93 serial = serial_source++;
94 }
95 FooEx( const FooEx& item ) : state(LIVE) {
96 ASSERT( item.state == LIVE, NULL );
97 ++FooExConstructed;
98 if( MaxFooCount && (FooExConstructed-FooExDestroyed) >= MaxFooCount ) // in push()
99 throw Foo_exception();
100 serial = item.serial;
101 }
102 ~FooEx() {
103 ASSERT( state==LIVE, NULL );
104 ++FooExDestroyed;
105 state=DEAD;
106 serial=DEAD;
107 }
108 void operator=( FooEx& item ) {
109 ASSERT( item.state==LIVE, NULL );
110 ASSERT( state==LIVE, NULL );
111 serial = item.serial;
112 if( MaxFooCount==2*Threshold && (FooExConstructed-FooExDestroyed) <= MaxFooCount/4 ) // in pop()
113 throw Foo_exception();
114 }
115#if __TBB_CPP11_RVALUE_REF_PRESENT
116 void operator=( FooEx&& item ) {
117 operator=( item );
118 item.serial = 0;
119 }
120#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
121} ;
122#endif /* TBB_USE_EXCEPTIONS */
123
124const size_t MAXTHREAD = 256;
125
126static int Sum[MAXTHREAD];
127
128//! Count of various pop operations
129/** [0] = pop_if_present that failed
130 [1] = pop_if_present that succeeded
131 [2] = pop */
132static tbb::atomic<long> PopKind[3];
133
134const int M = 10000;
135
136#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_RVALUE_REF_PRESENT
137const size_t push_selector_variants = 3;
138#elif __TBB_CPP11_RVALUE_REF_PRESENT
139const size_t push_selector_variants = 2;
140#else
141const size_t push_selector_variants = 1;
142#endif
143
144template<typename CQ, typename ValueType, typename CounterType>
145void push( CQ& q, ValueType v, CounterType i ) {
146 switch( i % push_selector_variants ) {
147 case 0: q.push( v ); break;
148#if __TBB_CPP11_RVALUE_REF_PRESENT
149 case 1: q.push( std::move(v) ); break;
150#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
151 case 2: q.emplace( v ); break;
152#endif
153#endif
154 default: ASSERT( false, NULL ); break;
155 }
156}
157
158template<typename CQ,typename T>
159struct Body: NoAssign {
160 CQ* queue;
161 const int nthread;
162 Body( int nthread_ ) : nthread(nthread_) {}
163 void operator()( int thread_id ) const {
164 long pop_kind[3] = {0,0,0};
165 int serial[MAXTHREAD+1];
166 memset( serial, 0, nthread*sizeof(int) );
167 ASSERT( thread_id<nthread, NULL );
168
169 long sum = 0;
170 for( long j=0; j<M; ++j ) {
171 T f;
172 f.thread_id = DEAD;
173 f.serial = DEAD;
174 bool prepopped = false;
175 if( j&1 ) {
176 prepopped = queue->try_pop( f );
177 ++pop_kind[prepopped];
178 }
179 T g;
180 g.thread_id = thread_id;
181 g.serial = j+1;
182 push( *queue, g, j );
183 if( !prepopped ) {
184 while( !(queue)->try_pop(f) ) __TBB_Yield();
185 ++pop_kind[2];
186 }
187 ASSERT( f.thread_id<=nthread, NULL );
188 ASSERT( f.thread_id==nthread || serial[f.thread_id]<f.serial, "partial order violation" );
189 serial[f.thread_id] = f.serial;
190 sum += f.serial-1;
191 }
192 Sum[thread_id] = sum;
193 for( int k=0; k<3; ++k )
194 PopKind[k] += pop_kind[k];
195 }
196};
197
198// Define wrapper classes to test tbb::concurrent_queue<T>
199template<typename T, typename A = tbb::cache_aligned_allocator<T> >
200class ConcQWithSizeWrapper : public tbb::concurrent_queue<T, A> {
201public:
202 ConcQWithSizeWrapper() {}
203 ConcQWithSizeWrapper( const ConcQWithSizeWrapper& q ) : tbb::concurrent_queue<T, A>( q ) {}
204 ConcQWithSizeWrapper(const A& a) : tbb::concurrent_queue<T, A>( a ) {}
205#if __TBB_CPP11_RVALUE_REF_PRESENT
206 ConcQWithSizeWrapper(ConcQWithSizeWrapper&& q) : tbb::concurrent_queue<T>( std::move(q) ) {}
207 ConcQWithSizeWrapper(ConcQWithSizeWrapper&& q, const A& a)
208 : tbb::concurrent_queue<T, A>( std::move(q), a ) { }
209#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
210 template<typename InputIterator>
211 ConcQWithSizeWrapper( InputIterator begin, InputIterator end, const A& a = A())
212 : tbb::concurrent_queue<T, A>(begin,end,a) {}
213 size_t size() const { return this->unsafe_size(); }
214};
215
216template<typename T>
217class ConcQPushPopWrapper : public tbb::concurrent_queue<T> {
218public:
219 ConcQPushPopWrapper() : my_capacity( size_t(-1)/(sizeof(void*)+sizeof(T)) ) {}
220 size_t size() const { return this->unsafe_size(); }
221 void set_capacity( const ptrdiff_t n ) { my_capacity = n; }
222 bool try_push( const T& source ) { return this->push( source ); }
223 bool try_pop( T& dest ) { return this->tbb::concurrent_queue<T>::try_pop( dest ); }
224 size_t my_capacity;
225};
226
227template<typename T>
228class ConcQWithCapacity : public tbb::concurrent_queue<T> {
229public:
230 ConcQWithCapacity() : my_capacity( size_t(-1)/(sizeof(void*)+sizeof(T)) ) {}
231 size_t size() const { return this->unsafe_size(); }
232 size_t capacity() const { return my_capacity; }
233 void set_capacity( const int n ) { my_capacity = n; }
234 bool try_push( const T& source ) { this->push( source ); return (size_t)source.serial<my_capacity; }
235 bool try_pop( T& dest ) { this->tbb::concurrent_queue<T>::try_pop( dest ); return (size_t)dest.serial<my_capacity; }
236 size_t my_capacity;
237};
238
239template <typename Queue>
240void AssertEquality(Queue &q, const std::vector<typename Queue::value_type> &vec) {
241 ASSERT(q.size() == typename Queue::size_type(vec.size()), NULL);
242 ASSERT(std::equal(q.unsafe_begin(), q.unsafe_end(), vec.begin(), Harness::IsEqual()), NULL);
243}
244
245template <typename Queue>
246void AssertEmptiness(Queue &q) {
247 ASSERT(q.empty(), NULL);
248 ASSERT(!q.size(), NULL);
249 typename Queue::value_type elem;
250 ASSERT(!q.try_pop(elem), NULL);
251}
252
253enum push_t { push_op, try_push_op };
254
255template<push_t push_op>
256struct pusher {
257#if __TBB_CPP11_RVALUE_REF_PRESENT
258 template<typename CQ, typename VType>
259 static bool push( CQ& queue, VType&& val ) {
260 queue.push( std::forward<VType>( val ) );
261 return true;
262 }
263#else
264 template<typename CQ, typename VType>
265 static bool push( CQ& queue, const VType& val ) {
266 queue.push( val );
267 return true;
268 }
269#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
270};
271
272template<>
273struct pusher< try_push_op > {
274#if __TBB_CPP11_RVALUE_REF_PRESENT
275 template<typename CQ, typename VType>
276 static bool push( CQ& queue, VType&& val ) {
277 return queue.try_push( std::forward<VType>( val ) );
278 }
279#else
280 template<typename CQ, typename VType>
281 static bool push( CQ& queue, const VType& val ) {
282 return queue.try_push( val );
283 }
284#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
285};
286
287enum pop_t { pop_op, try_pop_op };
288
289template<pop_t pop_op>
290struct popper {
291#if __TBB_CPP11_RVALUE_REF_PRESENT
292 template<typename CQ, typename VType>
293 static bool pop( CQ& queue, VType&& val ) {
294 if( queue.empty() ) return false;
295 queue.pop( std::forward<VType>( val ) );
296 return true;
297 }
298#else
299 template<typename CQ, typename VType>
300 static bool pop( CQ& queue, VType& val ) {
301 if( queue.empty() ) return false;
302 queue.pop( val );
303 return true;
304 }
305#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
306};
307
308template<>
309struct popper< try_pop_op > {
310#if __TBB_CPP11_RVALUE_REF_PRESENT
311 template<typename CQ, typename VType>
312 static bool pop( CQ& queue, VType&& val ) {
313 return queue.try_pop( std::forward<VType>( val ) );
314 }
315#else
316 template<typename CQ, typename VType>
317 static bool pop( CQ& queue, VType& val ) {
318 return queue.try_pop( val );
319 }
320#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
321};
322
323template <push_t push_op, typename Queue>
324void FillTest(Queue &q, const std::vector<typename Queue::value_type> &vec) {
325 for (typename std::vector<typename Queue::value_type>::const_iterator it = vec.begin(); it != vec.end(); ++it)
326 ASSERT(pusher<push_op>::push(q, *it), NULL);
327 AssertEquality(q, vec);
328}
329
330template <pop_t pop_op, typename Queue>
331void EmptyTest(Queue &q, const std::vector<typename Queue::value_type> &vec) {
332 typedef typename Queue::value_type value_type;
333
334 value_type elem;
335 typename std::vector<value_type>::const_iterator it = vec.begin();
336 while (popper<pop_op>::pop(q, elem)) {
337 ASSERT(Harness::IsEqual()(elem, *it), NULL);
338 ++it;
339 }
340 ASSERT(it == vec.end(), NULL);
341 AssertEmptiness(q);
342}
343
344template <typename T, typename A>
345void bounded_queue_specific_test(tbb::concurrent_queue<T, A> &, const std::vector<T> &) { /* do nothing */ }
346
347template <typename T, typename A>
348void bounded_queue_specific_test(tbb::concurrent_bounded_queue<T, A> &q, const std::vector<T> &vec) {
349 typedef typename tbb::concurrent_bounded_queue<T, A>::size_type size_type;
350
351 FillTest<try_push_op>(q, vec);
352 tbb::concurrent_bounded_queue<T, A> q2 = q;
353 EmptyTest<pop_op>(q, vec);
354
355 // capacity
356 q2.set_capacity(size_type(vec.size()));
357 ASSERT(q2.capacity() == size_type(vec.size()), NULL);
358 ASSERT(q2.size() == size_type(vec.size()), NULL);
359 ASSERT(!q2.try_push(vec[0]), NULL);
360
361#if TBB_USE_EXCEPTIONS
362 q.abort();
363#endif
364}
365
366template<typename CQ, typename T>
367void TestPushPop( size_t prefill, ptrdiff_t capacity, int nthread ) {
368 ASSERT( nthread>0, "nthread must be positive" );
369 ptrdiff_t signed_prefill = ptrdiff_t(prefill);
370 if( signed_prefill+1>=capacity )
371 return;
372 bool success = false;
373 for( int k=0; k<3; ++k )
374 PopKind[k] = 0;
375 for( int trial=0; !success; ++trial ) {
376 T::clear_counters();
377 Body<CQ,T> body(nthread);
378 CQ queue;
379 queue.set_capacity( capacity );
380 body.queue = &queue;
381 for( size_t i=0; i<prefill; ++i ) {
382 T f;
383 f.thread_id = nthread;
384 f.serial = 1+int(i);
385 push(queue, f, i);
386 ASSERT( unsigned(queue.size())==i+1, NULL );
387 ASSERT( !queue.empty(), NULL );
388 }
389 tbb::tick_count t0 = tbb::tick_count::now();
390 NativeParallelFor( nthread, body );
391 tbb::tick_count t1 = tbb::tick_count::now();
392 double timing = (t1-t0).seconds();
393 REMARK("prefill=%d capacity=%d threads=%d time = %g = %g nsec/operation\n", int(prefill), int(capacity), nthread, timing, timing/(2*M*nthread)*1.E9);
394 int sum = 0;
395 for( int k=0; k<nthread; ++k )
396 sum += Sum[k];
397 int expected = int(nthread*((M-1)*M/2) + ((prefill-1)*prefill)/2);
398 for( int i=int(prefill); --i>=0; ) {
399 ASSERT( !queue.empty(), NULL );
400 T f;
401 bool result = queue.try_pop(f);
402 ASSERT( result, NULL );
403 ASSERT( int(queue.size())==i, NULL );
404 sum += f.serial-1;
405 }
406 ASSERT( queue.empty(), "The queue should be empty" );
407 ASSERT( queue.size()==0, "The queue should have zero size" );
408 if( sum!=expected )
409 REPORT("sum=%d expected=%d\n",sum,expected);
410 ASSERT( T::get_n_constructed()==T::get_n_destroyed(), NULL );
411 // TODO: checks by counting allocators
412
413 success = true;
414 if( nthread>1 && prefill==0 ) {
415 // Check that pop_if_present got sufficient exercise
416 for( int k=0; k<2; ++k ) {
417#if (_WIN32||_WIN64)
418 // The TBB library on Windows seems to have a tough time generating
419 // the desired interleavings for pop_if_present, so the code tries longer, and settles
420 // for fewer desired interleavings.
421 const int max_trial = 100;
422 const int min_requirement = 20;
423#else
424 const int min_requirement = 100;
425 const int max_trial = 20;
426#endif /* _WIN32||_WIN64 */
427 if( PopKind[k]<min_requirement ) {
428 if( trial>=max_trial ) {
429 if( Verbose )
430 REPORT("Warning: %d threads had only %ld pop_if_present operations %s after %d trials (expected at least %d). "
431 "This problem may merely be unlucky scheduling. "
432 "Investigate only if it happens repeatedly.\n",
433 nthread, long(PopKind[k]), k==0?"failed":"succeeded", max_trial, min_requirement);
434 else
435 REPORT("Warning: the number of %s pop_if_present operations is less than expected for %d threads. Investigate if it happens repeatedly.\n",
436 k==0?"failed":"succeeded", nthread );
437
438 } else {
439 success = false;
440 }
441 }
442 }
443 }
444 }
445}
446
447class Bar {
448 state_t state;
449public:
450 static size_t construction_num, destruction_num;
451 ptrdiff_t my_id;
452 Bar() : state(LIVE), my_id(-1) {}
453 Bar(size_t _i) : state(LIVE), my_id(_i) { construction_num++; }
454 Bar( const Bar& a_bar ) : state(LIVE) {
455 ASSERT( a_bar.state==LIVE, NULL );
456 my_id = a_bar.my_id;
457 construction_num++;
458 }
459 ~Bar() {
460 ASSERT( state==LIVE, NULL );
461 state = DEAD;
462 my_id = DEAD;
463 destruction_num++;
464 }
465 void operator=( const Bar& a_bar ) {
466 ASSERT( a_bar.state==LIVE, NULL );
467 ASSERT( state==LIVE, NULL );
468 my_id = a_bar.my_id;
469 }
470 friend bool operator==(const Bar& bar1, const Bar& bar2 ) ;
471} ;
472
473size_t Bar::construction_num = 0;
474size_t Bar::destruction_num = 0;
475
476bool operator==(const Bar& bar1, const Bar& bar2) {
477 ASSERT( bar1.state==LIVE, NULL );
478 ASSERT( bar2.state==LIVE, NULL );
479 return bar1.my_id == bar2.my_id;
480}
481
482class BarIterator
483{
484 Bar* bar_ptr;
485 BarIterator(Bar* bp_) : bar_ptr(bp_) {}
486public:
487 ~BarIterator() {}
488 BarIterator& operator=( const BarIterator& other ) {
489 bar_ptr = other.bar_ptr;
490 return *this;
491 }
492 Bar& operator*() const {
493 return *bar_ptr;
494 }
495 BarIterator& operator++() {
496 ++bar_ptr;
497 return *this;
498 }
499 Bar* operator++(int) {
500 Bar* result = &operator*();
501 operator++();
502 return result;
503 }
504 friend bool operator==(const BarIterator& bia, const BarIterator& bib) ;
505 friend bool operator!=(const BarIterator& bia, const BarIterator& bib) ;
506 template<typename CQ, typename T, typename TIter, typename CQ_EX, typename T_EX>
507 friend void TestConstructors ();
508} ;
509
510bool operator==(const BarIterator& bia, const BarIterator& bib) {
511 return bia.bar_ptr==bib.bar_ptr;
512}
513
514bool operator!=(const BarIterator& bia, const BarIterator& bib) {
515 return bia.bar_ptr!=bib.bar_ptr;
516}
517
518#if TBB_USE_EXCEPTIONS
519class Bar_exception : public std::bad_alloc {
520public:
521 virtual const char *what() const throw() __TBB_override { return "making the entry invalid"; }
522 virtual ~Bar_exception() throw() {}
523};
524
525class BarEx {
526 static int count;
527public:
528 state_t state;
529 typedef enum {
530 PREPARATION,
531 COPY_CONSTRUCT
532 } mode_t;
533 static mode_t mode;
534 ptrdiff_t my_id;
535 ptrdiff_t my_tilda_id;
536 static int button;
537 BarEx() : state(LIVE), my_id(-1), my_tilda_id(-1) {}
538 BarEx(size_t _i) : state(LIVE), my_id(_i), my_tilda_id(my_id^(-1)) {}
539 BarEx( const BarEx& a_bar ) : state(LIVE) {
540 ASSERT( a_bar.state==LIVE, NULL );
541 my_id = a_bar.my_id;
542 if( mode==PREPARATION )
543 if( !( ++count % 100 ) )
544 throw Bar_exception();
545 my_tilda_id = a_bar.my_tilda_id;
546 }
547 ~BarEx() {
548 ASSERT( state==LIVE, NULL );
549 state = DEAD;
550 my_id = DEAD;
551 }
552 static void set_mode( mode_t m ) { mode = m; }
553 void operator=( const BarEx& a_bar ) {
554 ASSERT( a_bar.state==LIVE, NULL );
555 ASSERT( state==LIVE, NULL );
556 my_id = a_bar.my_id;
557 my_tilda_id = a_bar.my_tilda_id;
558 }
559 friend bool operator==(const BarEx& bar1, const BarEx& bar2 ) ;
560} ;
561
562int BarEx::count = 0;
563BarEx::mode_t BarEx::mode = BarEx::PREPARATION;
564
565bool operator==(const BarEx& bar1, const BarEx& bar2) {
566 ASSERT( bar1.state==LIVE, NULL );
567 ASSERT( bar2.state==LIVE, NULL );
568 ASSERT( (bar1.my_id ^ bar1.my_tilda_id) == -1, NULL );
569 ASSERT( (bar2.my_id ^ bar2.my_tilda_id) == -1, NULL );
570 return bar1.my_id==bar2.my_id && bar1.my_tilda_id==bar2.my_tilda_id;
571}
572#endif /* TBB_USE_EXCEPTIONS */
573
574template<typename CQ, typename T, typename TIter, typename CQ_EX, typename T_EX>
575void TestConstructors ()
576{
577 CQ src_queue;
578 typename CQ::const_iterator dqb;
579 typename CQ::const_iterator dqe;
580 typename CQ::const_iterator iter;
581
582 for( size_t size=0; size<1001; ++size ) {
583 for( size_t i=0; i<size; ++i )
584 src_queue.push(T(i+(i^size)));
585 typename CQ::const_iterator sqb( src_queue.unsafe_begin() );
586 typename CQ::const_iterator sqe( src_queue.unsafe_end() );
587
588 CQ dst_queue(sqb, sqe);
589
590 ASSERT(src_queue.size()==dst_queue.size(), "different size");
591
592 src_queue.clear();
593 }
594
595 T bar_array[1001];
596 for( size_t size=0; size<1001; ++size ) {
597 for( size_t i=0; i<size; ++i )
598 bar_array[i] = T(i+(i^size));
599
600 const TIter sab(bar_array+0);
601 const TIter sae(bar_array+size);
602
603 CQ dst_queue2(sab, sae);
604
605 ASSERT( size==unsigned(dst_queue2.size()), NULL );
606 ASSERT( sab==TIter(bar_array+0), NULL );
607 ASSERT( sae==TIter(bar_array+size), NULL );
608
609 dqb = dst_queue2.unsafe_begin();
610 dqe = dst_queue2.unsafe_end();
611 TIter v_iter(sab);
612 for( ; dqb != dqe; ++dqb, ++v_iter )
613 ASSERT( *dqb == *v_iter, "unexpected element" );
614 ASSERT( v_iter==sae, "different size?" );
615 }
616
617 src_queue.clear();
618
619 CQ dst_queue3( src_queue );
620 ASSERT( src_queue.size()==dst_queue3.size(), NULL );
621 ASSERT( 0==dst_queue3.size(), NULL );
622
623 int k=0;
624 for( size_t i=0; i<1001; ++i ) {
625 T tmp_bar;
626 src_queue.push(T(++k));
627 src_queue.push(T(++k));
628 src_queue.try_pop(tmp_bar);
629
630 CQ dst_queue4( src_queue );
631
632 ASSERT( src_queue.size()==dst_queue4.size(), NULL );
633
634 dqb = dst_queue4.unsafe_begin();
635 dqe = dst_queue4.unsafe_end();
636 iter = src_queue.unsafe_begin();
637
638 for( ; dqb != dqe; ++dqb, ++iter )
639 ASSERT( *dqb == *iter, "unexpected element" );
640
641 ASSERT( iter==src_queue.unsafe_end(), "different size?" );
642 }
643
644 CQ dst_queue5( src_queue );
645
646 ASSERT( src_queue.size()==dst_queue5.size(), NULL );
647 dqb = dst_queue5.unsafe_begin();
648 dqe = dst_queue5.unsafe_end();
649 iter = src_queue.unsafe_begin();
650 for( ; dqb != dqe; ++dqb, ++iter )
651 ASSERT( *dqb == *iter, "unexpected element" );
652
653 for( size_t i=0; i<100; ++i) {
654 T tmp_bar;
655 src_queue.push(T(i+1000));
656 src_queue.push(T(i+1000));
657 src_queue.try_pop(tmp_bar);
658
659 dst_queue5.push(T(i+1000));
660 dst_queue5.push(T(i+1000));
661 dst_queue5.try_pop(tmp_bar);
662 }
663
664 ASSERT( src_queue.size()==dst_queue5.size(), NULL );
665 dqb = dst_queue5.unsafe_begin();
666 dqe = dst_queue5.unsafe_end();
667 iter = src_queue.unsafe_begin();
668 for( ; dqb != dqe; ++dqb, ++iter )
669 ASSERT( *dqb == *iter, "unexpected element" );
670 ASSERT( iter==src_queue.unsafe_end(), "different size?" );
671
672#if __TBB_THROW_ACROSS_MODULE_BOUNDARY_BROKEN || __TBB_PLACEMENT_NEW_EXCEPTION_SAFETY_BROKEN
673 REPORT("Known issue: part of the constructor test is skipped.\n");
674#elif TBB_USE_EXCEPTIONS
675 k = 0;
676 typename CQ_EX::size_type n_elements=0;
677 CQ_EX src_queue_ex;
678 for( size_t size=0; size<1001; ++size ) {
679 T_EX tmp_bar_ex;
680 typename CQ_EX::size_type n_successful_pushes=0;
681 T_EX::set_mode( T_EX::PREPARATION );
682 try {
683 src_queue_ex.push(T_EX(k+(k^size)));
684 ++n_successful_pushes;
685 } catch (...) {
686 }
687 ++k;
688 try {
689 src_queue_ex.push(T_EX(k+(k^size)));
690 ++n_successful_pushes;
691 } catch (...) {
692 }
693 ++k;
694 src_queue_ex.try_pop(tmp_bar_ex);
695 n_elements += (n_successful_pushes - 1);
696 ASSERT( src_queue_ex.size()==n_elements, NULL);
697
698 T_EX::set_mode( T_EX::COPY_CONSTRUCT );
699 CQ_EX dst_queue_ex( src_queue_ex );
700
701 ASSERT( src_queue_ex.size()==dst_queue_ex.size(), NULL );
702
703 typename CQ_EX::const_iterator dqb_ex = dst_queue_ex.unsafe_begin();
704 typename CQ_EX::const_iterator dqe_ex = dst_queue_ex.unsafe_end();
705 typename CQ_EX::const_iterator iter_ex = src_queue_ex.unsafe_begin();
706
707 for( ; dqb_ex != dqe_ex; ++dqb_ex, ++iter_ex )
708 ASSERT( *dqb_ex == *iter_ex, "unexpected element" );
709 ASSERT( iter_ex==src_queue_ex.unsafe_end(), "different size?" );
710 }
711#endif /* TBB_USE_EXCEPTIONS */
712
713#if __TBB_CPP11_RVALUE_REF_PRESENT
714 // Testing work of move constructors. TODO: merge into TestMoveConstructors?
715 src_queue.clear();
716
717 typedef typename CQ::size_type qsize_t;
718 for( qsize_t size = 0; size < 1001; ++size ) {
719 for( qsize_t i = 0; i < size; ++i )
720 src_queue.push( T(i + (i ^ size)) );
721 std::vector<const T*> locations(size);
722 typename CQ::const_iterator qit = src_queue.unsafe_begin();
723 for( qsize_t i = 0; i < size; ++i, ++qit )
724 locations[i] = &(*qit);
725
726 qsize_t size_of_queue = src_queue.size();
727 CQ dst_queue( std::move(src_queue) );
728
729 ASSERT( src_queue.empty() && src_queue.size() == 0, "not working move constructor?" );
730 ASSERT( size == size_of_queue && size_of_queue == dst_queue.size(),
731 "not working move constructor?" );
732
733 qit = dst_queue.unsafe_begin();
734 for( qsize_t i = 0; i < size; ++i, ++qit )
735 ASSERT( locations[i] == &(*qit), "there was data movement during move constructor" );
736
737 for( qsize_t i = 0; i < size; ++i ) {
738 T test(i + (i ^ size));
739 T popped;
740 bool pop_result = dst_queue.try_pop( popped );
741
742 ASSERT( pop_result, NULL );
743 ASSERT( test == popped, NULL );
744 }
745 }
746#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
747}
748
749#if __TBB_CPP11_RVALUE_REF_PRESENT
750template<class T>
751class allocator: public tbb::cache_aligned_allocator<T> {
752public:
753 size_t m_unique_id;
754
755 allocator() : m_unique_id( 0 ) {}
756
757 allocator(size_t unique_id) { m_unique_id = unique_id; }
758
759 template<typename U>
760 allocator(const allocator<U>& a) throw() { m_unique_id = a.m_unique_id; }
761
762 template<typename U>
763 struct rebind { typedef allocator<U> other; };
764
765 friend bool operator==(const allocator& lhs, const allocator& rhs) {
766 return lhs.m_unique_id == rhs.m_unique_id;
767 }
768};
769
770// Checks operability of the queue the data was moved from
771template<typename T, typename CQ>
772void TestQueueOperabilityAfterDataMove( CQ& queue ) {
773 const size_t size = 10;
774 std::vector<T> v(size);
775 for( size_t i = 0; i < size; ++i ) v[i] = T( i * i + i );
776
777 FillTest<push_op>(queue, v);
778 EmptyTest<try_pop_op>(queue, v);
779 bounded_queue_specific_test(queue, v);
780}
781
782template<class CQ, class T>
783void TestMoveConstructors() {
784 T::construction_num = T::destruction_num = 0;
785 CQ src_queue( allocator<T>(0) );
786 const size_t size = 10;
787 for( size_t i = 0; i < size; ++i )
788 src_queue.push( T(i + (i ^ size)) );
789 ASSERT( T::construction_num == 2 * size, NULL );
790 ASSERT( T::destruction_num == size, NULL );
791
792 const T* locations[size];
793 typename CQ::const_iterator qit = src_queue.unsafe_begin();
794 for( size_t i = 0; i < size; ++i, ++qit )
795 locations[i] = &(*qit);
796
797 // Ensuring allocation operation takes place during move when allocators are different
798 T::construction_num = T::destruction_num = 0;
799 CQ dst_queue( std::move(src_queue), allocator<T>(1) );
800 ASSERT( T::construction_num == size, NULL );
801 ASSERT( T::destruction_num == size+1, NULL ); // One item is used by the queue destructor
802
803 TestQueueOperabilityAfterDataMove<T>( src_queue );
804
805 qit = dst_queue.unsafe_begin();
806 for( size_t i = 0; i < size; ++i, ++qit ) {
807 ASSERT( locations[i] != &(*qit), "an item should have been copied but was not" );
808 locations[i] = &(*qit);
809 }
810
811 T::construction_num = T::destruction_num = 0;
812 // Ensuring there is no allocation operation during move with equal allocators
813 CQ dst_queue2( std::move(dst_queue), allocator<T>(1) );
814 ASSERT( T::construction_num == 0, NULL );
815 ASSERT( T::destruction_num == 0, NULL );
816
817 TestQueueOperabilityAfterDataMove<T>( dst_queue );
818
819 qit = dst_queue2.unsafe_begin();
820 for( size_t i = 0; i < size; ++i, ++qit ) {
821 ASSERT( locations[i] == &(*qit), "an item should have been moved but was not" );
822 }
823
824 for( size_t i = 0; i < size; ++i) {
825 T test(i + (i ^ size));
826 T popped;
827 bool pop_result = dst_queue2.try_pop( popped );
828 ASSERT( pop_result, NULL );
829 ASSERT( test == popped, NULL );
830 }
831 ASSERT( dst_queue2.empty(), NULL );
832 ASSERT( dst_queue2.size() == 0, NULL );
833}
834
835void TestMoveConstruction() {
836 REMARK("Testing move constructors with specified allocators...");
837 TestMoveConstructors< ConcQWithSizeWrapper< Bar, allocator<Bar> >, Bar >();
838 TestMoveConstructors< tbb::concurrent_bounded_queue< Bar, allocator<Bar> >, Bar >();
839 // TODO: add tests with movable data
840 REMARK(" work\n");
841}
842#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
843
844template<typename Iterator1, typename Iterator2>
845void TestIteratorAux( Iterator1 i, Iterator2 j, int size ) {
846 Iterator1 old_i; // assigned at first iteration below
847 for( int k=0; k<size; ++k ) {
848 ASSERT( i!=j, NULL );
849 ASSERT( !(i==j), NULL );
850 // Test "->"
851 ASSERT( k+1==i->serial, NULL );
852 if( k&1 ) {
853 // Test post-increment
854 Foo f = *old_i++;
855 ASSERT( k+1==f.serial, NULL );
856 // Test assignment
857 i = old_i;
858 } else {
859 // Test pre-increment
860 if( k<size-1 ) {
861 Foo f = *++i;
862 ASSERT( k+2==f.serial, NULL );
863 } else ++i;
864 // Test assignment
865 old_i = i;
866 }
867 }
868 ASSERT( !(i!=j), NULL );
869 ASSERT( i==j, NULL );
870}
871
872template<typename Iterator1, typename Iterator2>
873void TestIteratorAssignment( Iterator2 j ) {
874 Iterator1 i(j);
875 ASSERT( i==j, NULL );
876 ASSERT( !(i!=j), NULL );
877 Iterator1 k;
878 k = j;
879 ASSERT( k==j, NULL );
880 ASSERT( !(k!=j), NULL );
881}
882
883template<typename Iterator, typename T>
884void TestIteratorTraits() {
885 AssertSameType( static_cast<typename Iterator::difference_type*>(0), static_cast<ptrdiff_t*>(0) );
886 AssertSameType( static_cast<typename Iterator::value_type*>(0), static_cast<T*>(0) );
887 AssertSameType( static_cast<typename Iterator::pointer*>(0), static_cast<T**>(0) );
888 AssertSameType( static_cast<typename Iterator::iterator_category*>(0), static_cast<std::forward_iterator_tag*>(0) );
889 T x;
890 typename Iterator::reference xr = x;
891 typename Iterator::pointer xp = &x;
892 ASSERT( &xr==xp, NULL );
893}
894
895//! Test the iterators for concurrent_queue
896template<typename CQ>
897void TestIterator() {
898 CQ queue;
899 const CQ& const_queue = queue;
900 for( int j=0; j<500; ++j ) {
901 TestIteratorAux( queue.unsafe_begin() , queue.unsafe_end() , j );
902 TestIteratorAux( const_queue.unsafe_begin(), const_queue.unsafe_end(), j );
903 TestIteratorAux( const_queue.unsafe_begin(), queue.unsafe_end() , j );
904 TestIteratorAux( queue.unsafe_begin() , const_queue.unsafe_end(), j );
905 Foo f;
906 f.serial = j+1;
907 queue.push(f);
908 }
909 TestIteratorAssignment<typename CQ::const_iterator>( const_queue.unsafe_begin() );
910 TestIteratorAssignment<typename CQ::const_iterator>( queue.unsafe_begin() );
911 TestIteratorAssignment<typename CQ::iterator>( queue.unsafe_begin() );
912 TestIteratorTraits<typename CQ::const_iterator, const Foo>();
913 TestIteratorTraits<typename CQ::iterator, Foo>();
914}
915
916template<typename CQ>
917void TestConcurrentQueueType() {
918 AssertSameType( typename CQ::value_type(), Foo() );
919 Foo f;
920 const Foo g;
921 typename CQ::reference r = f;
922 ASSERT( &r==&f, NULL );
923 ASSERT( !r.is_const(), NULL );
924 typename CQ::const_reference cr = g;
925 ASSERT( &cr==&g, NULL );
926 ASSERT( cr.is_const(), NULL );
927}
928
929template<typename CQ, typename T>
930void TestEmptyQueue() {
931 const CQ queue;
932 ASSERT( queue.size()==0, NULL );
933 ASSERT( queue.capacity()>0, NULL );
934 ASSERT( size_t(queue.capacity())>=size_t(-1)/(sizeof(void*)+sizeof(T)), NULL );
935}
936
937template<typename CQ,typename T>
938void TestFullQueue() {
939 for( int n=0; n<10; ++n ) {
940 T::clear_counters();
941 CQ queue;
942 queue.set_capacity(n);
943 for( int i=0; i<=n; ++i ) {
944 T f;
945 f.serial = i;
946 bool result = queue.try_push( f );
947 ASSERT( result==(i<n), NULL );
948 }
949 for( int i=0; i<=n; ++i ) {
950 T f;
951 bool result = queue.try_pop( f );
952 ASSERT( result==(i<n), NULL );
953 ASSERT( !result || f.serial==i, NULL );
954 }
955 ASSERT( T::get_n_constructed()==T::get_n_destroyed(), NULL );
956 }
957}
958
959template<typename CQ>
960void TestClear() {
961 FooConstructed = 0;
962 FooDestroyed = 0;
963 const unsigned int n=5;
964
965 CQ queue;
966 const int q_capacity=10;
967 queue.set_capacity(q_capacity);
968 for( size_t i=0; i<n; ++i ) {
969 Foo f;
970 f.serial = int(i);
971 queue.push( f );
972 }
973 ASSERT( unsigned(queue.size())==n, NULL );
974 queue.clear();
975 ASSERT( queue.size()==0, NULL );
976 for( size_t i=0; i<n; ++i ) {
977 Foo f;
978 f.serial = int(i);
979 queue.push( f );
980 }
981 ASSERT( unsigned(queue.size())==n, NULL );
982 queue.clear();
983 ASSERT( queue.size()==0, NULL );
984 for( size_t i=0; i<n; ++i ) {
985 Foo f;
986 f.serial = int(i);
987 queue.push( f );
988 }
989 ASSERT( unsigned(queue.size())==n, NULL );
990}
991
992template<typename T>
993struct TestNegativeQueueBody: NoAssign {
994 tbb::concurrent_bounded_queue<T>& queue;
995 const int nthread;
996 TestNegativeQueueBody( tbb::concurrent_bounded_queue<T>& q, int n ) : queue(q), nthread(n) {}
997 void operator()( int k ) const {
998 if( k==0 ) {
999 int number_of_pops = nthread-1;
1000 // Wait for all pops to pend.
1001 while( queue.size()>-number_of_pops ) {
1002 __TBB_Yield();
1003 }
1004 for( int i=0; ; ++i ) {
1005 ASSERT( queue.size()==i-number_of_pops, NULL );
1006 ASSERT( queue.empty()==(queue.size()<=0), NULL );
1007 if( i==number_of_pops ) break;
1008 // Satisfy another pop
1009 queue.push( T() );
1010 }
1011 } else {
1012 // Pop item from queue
1013 T item;
1014 queue.pop(item);
1015 }
1016 }
1017};
1018
1019//! Test a queue with a negative size.
1020template<typename T>
1021void TestNegativeQueue( int nthread ) {
1022 tbb::concurrent_bounded_queue<T> queue;
1023 NativeParallelFor( nthread, TestNegativeQueueBody<T>(queue,nthread) );
1024}
1025
1026#if TBB_USE_EXCEPTIONS
1027template<template<typename, typename> class CQ,typename A1,typename A2,typename T>
1028void TestExceptionBody() {
1029 enum methods {
1030 m_push = 0,
1031 m_pop
1032 };
1033
1034 REMARK("Testing exception safety\n");
1035 MaxFooCount = 5;
1036 // verify 'clear()' on exception; queue's destructor calls its clear()
1037 // Do test on queues of two different types at the same time to
1038 // catch problem with incorrect sharing between templates.
1039 {
1040 CQ<T,A1> queue0;
1041 CQ<int,A1> queue1;
1042 for( int i=0; i<2; ++i ) {
1043 bool caught = false;
1044 try {
1045 // concurrent_queue internally rebinds the allocator to the one for 'char'
1046 A2::init_counters();
1047 A2::set_limits(N/2);
1048 for( int k=0; k<N; k++ ) {
1049 if( i==0 )
1050 push(queue0, T(), i);
1051 else
1052 queue1.push( k );
1053 }
1054 } catch (...) {
1055 caught = true;
1056 }
1057 ASSERT( caught, "call to push should have thrown exception" );
1058 }
1059 }
1060 REMARK("... queue destruction test passed\n");
1061
1062 try {
1063 int n_pushed=0, n_popped=0;
1064 for(int t = 0; t <= 1; t++)// exception type -- 0 : from allocator(), 1 : from Foo's constructor
1065 {
1066 CQ<T,A1> queue_test;
1067 for( int m=m_push; m<=m_pop; m++ ) {
1068 // concurrent_queue internally rebinds the allocator to the one for 'char'
1069 A2::init_counters();
1070
1071 if(t) MaxFooCount = MaxFooCount + 400;
1072 else A2::set_limits(N/2);
1073
1074 try {
1075 switch(m) {
1076 case m_push:
1077 for( int k=0; k<N; k++ ) {
1078 push( queue_test, T(), k );
1079 n_pushed++;
1080 }
1081 break;
1082 case m_pop:
1083 n_popped=0;
1084 for( int k=0; k<n_pushed; k++ ) {
1085 T elt;
1086 queue_test.try_pop( elt );
1087 n_popped++;
1088 }
1089 n_pushed = 0;
1090 A2::set_limits();
1091 break;
1092 }
1093 if( !t && m==m_push ) ASSERT(false, "should throw an exception");
1094 } catch ( Foo_exception & ) {
1095 long tc = MaxFooCount;
1096 MaxFooCount = 0; // disable exception
1097 switch(m) {
1098 case m_push:
1099 ASSERT( ptrdiff_t(queue_test.size())==n_pushed, "incorrect queue size" );
1100 for( int k=0; k<(int)tc; k++ ) {
1101 push( queue_test, T(), k );
1102 n_pushed++;
1103 }
1104 break;
1105 case m_pop:
1106 n_pushed -= (n_popped+1); // including one that threw the exception
1107 ASSERT( n_pushed>=0, "n_pushed cannot be less than 0" );
1108 for( int k=0; k<1000; k++ ) {
1109 push( queue_test, T(), k );
1110 n_pushed++;
1111 }
1112 ASSERT( !queue_test.empty(), "queue must not be empty" );
1113 ASSERT( ptrdiff_t(queue_test.size())==n_pushed, "queue size must be equal to n pushed" );
1114 for( int k=0; k<n_pushed; k++ ) {
1115 T elt;
1116 queue_test.try_pop( elt );
1117 }
1118 ASSERT( queue_test.empty(), "queue must be empty" );
1119 ASSERT( queue_test.size()==0, "queue must be empty" );
1120 break;
1121 }
1122 MaxFooCount = tc;
1123 } catch ( std::bad_alloc & ) {
1124 A2::set_limits(); // disable exception from allocator
1125 size_t size = queue_test.size();
1126 switch(m) {
1127 case m_push:
1128 ASSERT( size>0, "incorrect queue size");
1129 break;
1130 case m_pop:
1131 if( !t ) ASSERT( false, "should not throw an exception" );
1132 break;
1133 }
1134 }
1135 REMARK("... for t=%d and m=%d, exception test passed\n", t, m);
1136 }
1137 }
1138 } catch(...) {
1139 ASSERT(false, "unexpected exception");
1140 }
1141}
1142#endif /* TBB_USE_EXCEPTIONS */
1143
1144void TestExceptions() {
1145#if __TBB_THROW_ACROSS_MODULE_BOUNDARY_BROKEN
1146 REPORT("Known issue: exception safety test is skipped.\n");
1147#elif TBB_USE_EXCEPTIONS
1148 typedef static_counting_allocator<std::allocator<FooEx>, size_t> allocator_t;
1149 typedef static_counting_allocator<std::allocator<char>, size_t> allocator_char_t;
1150 TestExceptionBody<ConcQWithSizeWrapper,allocator_t,allocator_char_t,FooEx>();
1151 TestExceptionBody<tbb::concurrent_bounded_queue,allocator_t,allocator_char_t,FooEx>();
1152#endif /* TBB_USE_EXCEPTIONS */
1153}
1154
1155template<typename CQ, typename T>
1156struct TestQueueElements: NoAssign {
1157 CQ& queue;
1158 const int nthread;
1159 TestQueueElements( CQ& q, int n ) : queue(q), nthread(n) {}
1160 void operator()( int k ) const {
1161 for( int i=0; i<1000; ++i ) {
1162 if( (i&0x1)==0 ) {
1163 ASSERT( T(k)<T(nthread), NULL );
1164 queue.push( T(k) );
1165 } else {
1166 // Pop item from queue
1167 T item = 0;
1168 queue.try_pop(item);
1169 ASSERT( item<=T(nthread), NULL );
1170 }
1171 }
1172 }
1173};
1174
1175//! Test concurrent queue with primitive data type
1176template<typename CQ, typename T>
1177void TestPrimitiveTypes( int nthread, T exemplar )
1178{
1179 CQ queue;
1180 for( int i=0; i<100; ++i )
1181 queue.push( exemplar );
1182 NativeParallelFor( nthread, TestQueueElements<CQ,T>(queue,nthread) );
1183}
1184
1185#include "harness_m128.h"
1186
1187#if HAVE_m128 || HAVE_m256
1188
1189//! Test concurrent queue with vector types
1190/** Type Queue should be a queue of ClassWithSSE/ClassWithAVX. */
1191template<typename ClassWithVectorType, typename Queue>
1192void TestVectorTypes() {
1193 Queue q1;
1194 for( int i=0; i<100; ++i ) {
1195 // VC8 does not properly align a temporary value; to work around, use explicit variable
1196 ClassWithVectorType bar(i);
1197 q1.push(bar);
1198 }
1199
1200 // Copy the queue
1201 Queue q2 = q1;
1202 // Check that elements of the copy are correct
1203 typename Queue::const_iterator ci = q2.unsafe_begin();
1204 for( int i=0; i<100; ++i ) {
1205 ClassWithVectorType foo = *ci;
1206 ClassWithVectorType bar(i);
1207 ASSERT( *ci==bar, NULL );
1208 ++ci;
1209 }
1210
1211 for( int i=0; i<101; ++i ) {
1212 ClassWithVectorType tmp;
1213 bool b = q1.try_pop( tmp );
1214 ASSERT( b==(i<100), NULL );
1215 ClassWithVectorType bar(i);
1216 ASSERT( !b || tmp==bar, NULL );
1217 }
1218}
1219#endif /* HAVE_m128 || HAVE_m256 */
1220
1221void TestEmptiness()
1222{
1223 REMARK(" Test Emptiness\n");
1224 TestEmptyQueue<ConcQWithCapacity<char>, char>();
1225 TestEmptyQueue<ConcQWithCapacity<Foo>, Foo>();
1226 TestEmptyQueue<tbb::concurrent_bounded_queue<char>, char>();
1227 TestEmptyQueue<tbb::concurrent_bounded_queue<Foo>, Foo>();
1228}
1229
1230void TestFullness()
1231{
1232 REMARK(" Test Fullness\n");
1233 TestFullQueue<ConcQWithCapacity<Foo>,Foo>();
1234 TestFullQueue<tbb::concurrent_bounded_queue<Foo>,Foo>();
1235}
1236
1237void TestClearWorks()
1238{
1239 REMARK(" Test concurrent_queue::clear() works\n");
1240 TestClear<ConcQWithCapacity<Foo> >();
1241 TestClear<tbb::concurrent_bounded_queue<Foo> >();
1242}
1243
1244void TestQueueTypeDeclaration()
1245{
1246 REMARK(" Test concurrent_queue's types work\n");
1247 TestConcurrentQueueType<tbb::concurrent_queue<Foo> >();
1248 TestConcurrentQueueType<tbb::concurrent_bounded_queue<Foo> >();
1249}
1250
1251void TestQueueIteratorWorks()
1252{
1253 REMARK(" Test concurrent_queue's iterators work\n");
1254 TestIterator<tbb::concurrent_queue<Foo> >();
1255 TestIterator<tbb::concurrent_bounded_queue<Foo> >();
1256}
1257
1258#if TBB_USE_EXCEPTIONS
1259#define BAR_EX BarEx
1260#else
1261#define BAR_EX Empty /* passed as template arg but should not be used */
1262#endif
1263class Empty;
1264
1265void TestQueueConstructors()
1266{
1267 REMARK(" Test concurrent_queue's constructors work\n");
1268 TestConstructors<ConcQWithSizeWrapper<Bar>,Bar,BarIterator,ConcQWithSizeWrapper<BAR_EX>,BAR_EX>();
1269 TestConstructors<tbb::concurrent_bounded_queue<Bar>,Bar,BarIterator,tbb::concurrent_bounded_queue<BAR_EX>,BAR_EX>();
1270}
1271
1272void TestQueueWorksWithPrimitiveTypes()
1273{
1274 REMARK(" Test concurrent_queue works with primitive types\n");
1275 TestPrimitiveTypes<tbb::concurrent_queue<char>, char>( MaxThread, (char)1 );
1276 TestPrimitiveTypes<tbb::concurrent_queue<int>, int>( MaxThread, (int)-12 );
1277 TestPrimitiveTypes<tbb::concurrent_queue<float>, float>( MaxThread, (float)-1.2f );
1278 TestPrimitiveTypes<tbb::concurrent_queue<double>, double>( MaxThread, (double)-4.3 );
1279 TestPrimitiveTypes<tbb::concurrent_bounded_queue<char>, char>( MaxThread, (char)1 );
1280 TestPrimitiveTypes<tbb::concurrent_bounded_queue<int>, int>( MaxThread, (int)-12 );
1281 TestPrimitiveTypes<tbb::concurrent_bounded_queue<float>, float>( MaxThread, (float)-1.2f );
1282 TestPrimitiveTypes<tbb::concurrent_bounded_queue<double>, double>( MaxThread, (double)-4.3 );
1283}
1284
1285void TestQueueWorksWithSSE()
1286{
1287 REMARK(" Test concurrent_queue works with SSE data\n");
1288#if HAVE_m128
1289 TestVectorTypes<ClassWithSSE, tbb::concurrent_queue<ClassWithSSE> >();
1290 TestVectorTypes<ClassWithSSE, tbb::concurrent_bounded_queue<ClassWithSSE> >();
1291#endif /* HAVE_m128 */
1292#if HAVE_m256
1293 if( have_AVX() ) {
1294 TestVectorTypes<ClassWithAVX, tbb::concurrent_queue<ClassWithAVX> >();
1295 TestVectorTypes<ClassWithAVX, tbb::concurrent_bounded_queue<ClassWithAVX> >();
1296 }
1297#endif /* HAVE_m256 */
1298}
1299
1300void TestConcurrentPushPop()
1301{
1302 REMARK(" Test concurrent_queue's concurrent push and pop\n");
1303 for( int nthread=MinThread; nthread<=MaxThread; ++nthread ) {
1304 REMARK(" Testing with %d thread(s)\n", nthread );
1305 TestNegativeQueue<Foo>(nthread);
1306 for( size_t prefill=0; prefill<64; prefill+=(1+prefill/3) ) {
1307 TestPushPop<ConcQPushPopWrapper<Foo>,Foo>(prefill,ptrdiff_t(-1),nthread);
1308 TestPushPop<ConcQPushPopWrapper<Foo>,Foo>(prefill,ptrdiff_t(1),nthread);
1309 TestPushPop<ConcQPushPopWrapper<Foo>,Foo>(prefill,ptrdiff_t(2),nthread);
1310 TestPushPop<ConcQPushPopWrapper<Foo>,Foo>(prefill,ptrdiff_t(10),nthread);
1311 TestPushPop<ConcQPushPopWrapper<Foo>,Foo>(prefill,ptrdiff_t(100),nthread);
1312 }
1313 for( size_t prefill=0; prefill<64; prefill+=(1+prefill/3) ) {
1314 TestPushPop<tbb::concurrent_bounded_queue<Foo>,Foo>(prefill,ptrdiff_t(-1),nthread);
1315 TestPushPop<tbb::concurrent_bounded_queue<Foo>,Foo>(prefill,ptrdiff_t(1),nthread);
1316 TestPushPop<tbb::concurrent_bounded_queue<Foo>,Foo>(prefill,ptrdiff_t(2),nthread);
1317 TestPushPop<tbb::concurrent_bounded_queue<Foo>,Foo>(prefill,ptrdiff_t(10),nthread);
1318 TestPushPop<tbb::concurrent_bounded_queue<Foo>,Foo>(prefill,ptrdiff_t(100),nthread);
1319 }
1320 }
1321}
1322
1323#if TBB_USE_EXCEPTIONS
1324tbb::atomic<size_t> num_pushed;
1325tbb::atomic<size_t> num_popped;
1326tbb::atomic<size_t> failed_pushes;
1327tbb::atomic<size_t> failed_pops;
1328
1329class SimplePushBody {
1330 tbb::concurrent_bounded_queue<int>* q;
1331 int max;
1332public:
1333 SimplePushBody(tbb::concurrent_bounded_queue<int>* _q, int hi_thr) : q(_q), max(hi_thr) {}
1334 bool operator()() { // predicate for spin_wait_while
1335 return q->size()<max;
1336 }
1337 void operator()(int thread_id) const {
1338 if (thread_id == max) {
1339 spin_wait_while( *this );
1340 q->abort();
1341 return;
1342 }
1343 try {
1344 q->push(42);
1345 ++num_pushed;
1346 } catch ( tbb::user_abort& ) {
1347 ++failed_pushes;
1348 }
1349 }
1350};
1351
1352class SimplePopBody {
1353 tbb::concurrent_bounded_queue<int>* q;
1354 int max;
1355 int prefill;
1356public:
1357 SimplePopBody(tbb::concurrent_bounded_queue<int>* _q, int hi_thr, int nitems)
1358 : q(_q), max(hi_thr), prefill(nitems) {}
1359 bool operator()() { // predicate for spin_wait_while
1360 // There should be `max` pops, and `prefill` should succeed
1361 return q->size()>prefill-max;
1362 }
1363 void operator()(int thread_id) const {
1364 int e;
1365 if (thread_id == max) {
1366 spin_wait_while( *this );
1367 q->abort();
1368 return;
1369 }
1370 try {
1371 q->pop(e);
1372 ++num_popped;
1373 } catch ( tbb::user_abort& ) {
1374 ++failed_pops;
1375 }
1376 }
1377};
1378#endif /* TBB_USE_EXCEPTIONS */
1379
1380void TestAbort() {
1381#if TBB_USE_EXCEPTIONS
1382 for (int nthreads=MinThread; nthreads<=MaxThread; ++nthreads) {
1383 REMARK("Testing Abort on %d thread(s).\n", nthreads);
1384
1385 REMARK("...testing pushing to zero-sized queue\n");
1386 tbb::concurrent_bounded_queue<int> iq1;
1387 iq1.set_capacity(0);
1388 for (int i=0; i<10; ++i) {
1389 num_pushed = num_popped = failed_pushes = failed_pops = 0;
1390 SimplePushBody my_push_body1(&iq1, nthreads);
1391 NativeParallelFor( nthreads+1, my_push_body1 );
1392 ASSERT(num_pushed == 0, "no elements should have been pushed to zero-sized queue");
1393 ASSERT((int)failed_pushes == nthreads, "All threads should have failed to push an element to zero-sized queue");
1394 // Do not test popping each time in order to test queue destruction with no previous pops
1395 if (nthreads < (MaxThread+MinThread)/2) {
1396 int e;
1397 bool queue_empty = !iq1.try_pop(e);
1398 ASSERT(queue_empty, "no elements should have been popped from zero-sized queue");
1399 }
1400 }
1401
1402 REMARK("...testing pushing to small-sized queue\n");
1403 tbb::concurrent_bounded_queue<int> iq2;
1404 iq2.set_capacity(2);
1405 for (int i=0; i<10; ++i) {
1406 num_pushed = num_popped = failed_pushes = failed_pops = 0;
1407 SimplePushBody my_push_body2(&iq2, nthreads);
1408 NativeParallelFor( nthreads+1, my_push_body2 );
1409 ASSERT(num_pushed <= 2, "at most 2 elements should have been pushed to queue of size 2");
1410 if (nthreads >= 2)
1411 ASSERT((int)failed_pushes == nthreads-2, "nthreads-2 threads should have failed to push an element to queue of size 2");
1412 int e;
1413 while (iq2.try_pop(e)) ;
1414 }
1415
1416 REMARK("...testing popping from small-sized queue\n");
1417 tbb::concurrent_bounded_queue<int> iq3;
1418 iq3.set_capacity(2);
1419 for (int i=0; i<10; ++i) {
1420 num_pushed = num_popped = failed_pushes = failed_pops = 0;
1421 iq3.push(42);
1422 iq3.push(42);
1423 SimplePopBody my_pop_body(&iq3, nthreads, 2);
1424 NativeParallelFor( nthreads+1, my_pop_body );
1425 ASSERT(num_popped <= 2, "at most 2 elements should have been popped from queue of size 2");
1426 if (nthreads >= 2)
1427 ASSERT((int)failed_pops == nthreads-2, "nthreads-2 threads should have failed to pop an element from queue of size 2");
1428 else {
1429 int e;
1430 iq3.pop(e);
1431 }
1432 }
1433
1434 REMARK("...testing pushing and popping from small-sized queue\n");
1435 tbb::concurrent_bounded_queue<int> iq4;
1436 int cap = nthreads/2;
1437 if (!cap) cap=1;
1438 iq4.set_capacity(cap);
1439 for (int i=0; i<10; ++i) {
1440 num_pushed = num_popped = failed_pushes = failed_pops = 0;
1441 SimplePushBody my_push_body2(&iq4, nthreads);
1442 NativeParallelFor( nthreads+1, my_push_body2 );
1443 ASSERT((int)num_pushed <= cap, "at most cap elements should have been pushed to queue of size cap");
1444 if (nthreads >= cap)
1445 ASSERT((int)failed_pushes == nthreads-cap, "nthreads-cap threads should have failed to push an element to queue of size cap");
1446 SimplePopBody my_pop_body(&iq4, nthreads, (int)num_pushed);
1447 NativeParallelFor( nthreads+1, my_pop_body );
1448 ASSERT((int)num_popped <= cap, "at most cap elements should have been popped from queue of size cap");
1449 if (nthreads >= cap)
1450 ASSERT((int)failed_pops == nthreads-cap, "nthreads-cap threads should have failed to pop an element from queue of size cap");
1451 else {
1452 int e;
1453 while (iq4.try_pop(e)) ;
1454 }
1455 }
1456 }
1457#endif
1458}
1459
1460#if __TBB_CPP11_RVALUE_REF_PRESENT
1461struct MoveOperationTracker {
1462 static size_t copy_constructor_called_times;
1463 static size_t move_constructor_called_times;
1464 static size_t copy_assignment_called_times;
1465 static size_t move_assignment_called_times;
1466
1467 MoveOperationTracker() {}
1468 MoveOperationTracker(const MoveOperationTracker&) {
1469 ++copy_constructor_called_times;
1470 }
1471 MoveOperationTracker(MoveOperationTracker&&) {
1472 ++move_constructor_called_times;
1473 }
1474 MoveOperationTracker& operator=(MoveOperationTracker const&) {
1475 ++copy_assignment_called_times;
1476 return *this;
1477 }
1478 MoveOperationTracker& operator=(MoveOperationTracker&&) {
1479 ++move_assignment_called_times;
1480 return *this;
1481 }
1482};
1483size_t MoveOperationTracker::copy_constructor_called_times = 0;
1484size_t MoveOperationTracker::move_constructor_called_times = 0;
1485size_t MoveOperationTracker::copy_assignment_called_times = 0;
1486size_t MoveOperationTracker::move_assignment_called_times = 0;
1487
1488template <class CQ, push_t push_op, pop_t pop_op>
1489void TestMoveSupport() {
1490 size_t &mcct = MoveOperationTracker::move_constructor_called_times;
1491 size_t &ccct = MoveOperationTracker::copy_constructor_called_times;
1492 size_t &cact = MoveOperationTracker::copy_assignment_called_times;
1493 size_t &mact = MoveOperationTracker::move_assignment_called_times;
1494 mcct = ccct = cact = mact = 0;
1495
1496 CQ q;
1497
1498 ASSERT(mcct == 0, "Value must be zero-initialized");
1499 ASSERT(ccct == 0, "Value must be zero-initialized");
1500 ASSERT(pusher<push_op>::push( q, MoveOperationTracker() ), NULL);
1501 ASSERT(mcct == 1, "Not working push(T&&) or try_push(T&&)?");
1502 ASSERT(ccct == 0, "Copying of arg occurred during push(T&&) or try_push(T&&)");
1503
1504 MoveOperationTracker ob;
1505 ASSERT(pusher<push_op>::push( q, std::move(ob) ), NULL);
1506 ASSERT(mcct == 2, "Not working push(T&&) or try_push(T&&)?");
1507 ASSERT(ccct == 0, "Copying of arg occurred during push(T&&) or try_push(T&&)");
1508
1509 ASSERT(cact == 0, "Copy assignment called during push(T&&) or try_push(T&&)");
1510 ASSERT(mact == 0, "Move assignment called during push(T&&) or try_push(T&&)");
1511
1512 bool result = popper<pop_op>::pop( q, ob );
1513 ASSERT(result, NULL);
1514 ASSERT(cact == 0, "Copy assignment called during try_pop(T&&)");
1515 ASSERT(mact == 1, "Move assignment was not called during try_pop(T&&)");
1516}
1517
1518void TestMoveSupportInPushPop() {
1519 REMARK("Testing Move Support in Push/Pop...");
1520 TestMoveSupport< tbb::concurrent_queue<MoveOperationTracker>, push_op, try_pop_op >();
1521 TestMoveSupport< tbb::concurrent_bounded_queue<MoveOperationTracker>, push_op, pop_op >();
1522 TestMoveSupport< tbb::concurrent_bounded_queue<MoveOperationTracker>, try_push_op, try_pop_op >();
1523 REMARK(" works.\n");
1524}
1525
1526#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
1527class NonTrivialConstructorType {
1528public:
1529 NonTrivialConstructorType( int a = 0 ) : m_a( a ), m_str( "" ) {}
1530 NonTrivialConstructorType( const std::string& str ) : m_a( 0 ), m_str( str ) {}
1531 NonTrivialConstructorType( int a, const std::string& str ) : m_a( a ), m_str( str ) {}
1532 int get_a() const { return m_a; }
1533 std::string get_str() const { return m_str; }
1534private:
1535 int m_a;
1536 std::string m_str;
1537};
1538
1539enum emplace_t { emplace_op, try_emplace_op };
1540
1541template< emplace_t emplace_op >
1542struct emplacer {
1543 template< typename CQ, typename... Args>
1544 static void emplace( CQ& queue, Args&&... val ) { queue.emplace( std::forward<Args>( val )... ); }
1545};
1546
1547template<>
1548struct emplacer< try_emplace_op > {
1549 template<typename CQ, typename... Args>
1550 static void emplace( CQ& queue, Args&&... val ) {
1551 bool result = queue.try_emplace( std::forward<Args>( val )... );
1552 ASSERT( result, "try_emplace error\n" );
1553 }
1554};
1555
1556template<typename CQ, emplace_t emplace_op>
1557void TestEmplaceInQueue() {
1558 CQ cq;
1559 std::string test_str = "I'm being emplaced!";
1560 {
1561 emplacer<emplace_op>::emplace( cq, 5 );
1562 ASSERT( cq.size() == 1, NULL );
1563 NonTrivialConstructorType popped( -1 );
1564 bool result = cq.try_pop( popped );
1565 ASSERT( result, NULL );
1566 ASSERT( popped.get_a() == 5, NULL );
1567 ASSERT( popped.get_str() == std::string( "" ), NULL );
1568 }
1569
1570 ASSERT( cq.empty(), NULL );
1571
1572 {
1573 NonTrivialConstructorType popped( -1 );
1574 emplacer<emplace_op>::emplace( cq, std::string(test_str) );
1575 bool result = cq.try_pop( popped );
1576 ASSERT( result, NULL );
1577 ASSERT( popped.get_a() == 0, NULL );
1578 ASSERT( popped.get_str() == test_str, NULL );
1579 }
1580
1581 ASSERT( cq.empty(), NULL );
1582
1583 {
1584 NonTrivialConstructorType popped( -1, "" );
1585 emplacer<emplace_op>::emplace( cq, 5, std::string(test_str) );
1586 bool result = cq.try_pop( popped );
1587 ASSERT( result, NULL );
1588 ASSERT( popped.get_a() == 5, NULL );
1589 ASSERT( popped.get_str() == test_str, NULL );
1590 }
1591}
1592void TestEmplace() {
1593 REMARK("Testing support for 'emplace' method...");
1594 TestEmplaceInQueue< ConcQWithSizeWrapper<NonTrivialConstructorType>, emplace_op >();
1595 TestEmplaceInQueue< tbb::concurrent_bounded_queue<NonTrivialConstructorType>, emplace_op >();
1596 TestEmplaceInQueue< tbb::concurrent_bounded_queue<NonTrivialConstructorType>, try_emplace_op >();
1597 REMARK(" works.\n");
1598}
1599#endif /* __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT */
1600#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
1601
1602template <typename Queue>
1603void Examine(Queue q, const std::vector<typename Queue::value_type> &vec) {
1604 typedef typename Queue::value_type value_type;
1605
1606 AssertEquality(q, vec);
1607
1608 const Queue cq = q;
1609 AssertEquality(cq, vec);
1610
1611 q.clear();
1612 AssertEmptiness(q);
1613
1614 FillTest<push_op>(q, vec);
1615 EmptyTest<try_pop_op>(q, vec);
1616
1617 bounded_queue_specific_test(q, vec);
1618
1619 typename Queue::allocator_type a = q.get_allocator();
1620 value_type *ptr = a.allocate(1);
1621 ASSERT(ptr, NULL);
1622 a.deallocate(ptr, 1);
1623}
1624
1625template <typename Queue, typename QueueDebugAlloc>
1626void TypeTester(const std::vector<typename Queue::value_type> &vec) {
1627 typedef typename std::vector<typename Queue::value_type>::const_iterator iterator;
1628 ASSERT(vec.size() >= 5, "Array should have at least 5 elements");
1629 // Construct an empty queue.
1630 Queue q1;
1631 for (iterator it = vec.begin(); it != vec.end(); ++it) q1.push(*it);
1632 Examine(q1, vec);
1633 // Copying constructor.
1634 Queue q3(q1);
1635 Examine(q3, vec);
1636 // Construct with non-default allocator.
1637 QueueDebugAlloc q4;
1638 for (iterator it = vec.begin(); it != vec.end(); ++it) q4.push(*it);
1639 Examine(q4, vec);
1640 // Copying constructor with the same allocator type.
1641 QueueDebugAlloc q5(q4);
1642 Examine(q5, vec);
1643 // Construction with given allocator instance.
1644 typename QueueDebugAlloc::allocator_type a;
1645 QueueDebugAlloc q6(a);
1646 for (iterator it = vec.begin(); it != vec.end(); ++it) q6.push(*it);
1647 Examine(q6, vec);
1648 // Construction with copying iteration range and given allocator instance.
1649 QueueDebugAlloc q7(q1.unsafe_begin(), q1.unsafe_end(), a);
1650 Examine<QueueDebugAlloc>(q7, vec);
1651}
1652
1653template <typename value_type>
1654void TestTypes(const std::vector<value_type> &vec) {
1655 TypeTester< ConcQWithSizeWrapper<value_type>, ConcQWithSizeWrapper<value_type, debug_allocator<value_type> > >(vec);
1656 TypeTester< tbb::concurrent_bounded_queue<value_type>, tbb::concurrent_bounded_queue<value_type, debug_allocator<value_type> > >(vec);
1657}
1658
1659void TestTypes() {
1660 const int NUMBER = 10;
1661
1662 std::vector<int> arrInt;
1663 for (int i = 0; i < NUMBER; ++i) arrInt.push_back(i);
1664 std::vector< tbb::atomic<int> > arrTbb;
1665 for (int i = 0; i < NUMBER; ++i) {
1666 tbb::atomic<int> a;
1667 a = i;
1668 arrTbb.push_back(a);
1669 }
1670 TestTypes(arrInt);
1671 TestTypes(arrTbb);
1672
1673#if __TBB_CPP11_SMART_POINTERS_PRESENT
1674 std::vector< std::shared_ptr<int> > arrShr;
1675 for (int i = 0; i < NUMBER; ++i) arrShr.push_back(std::make_shared<int>(i));
1676 std::vector< std::weak_ptr<int> > arrWk;
1677 std::copy(arrShr.begin(), arrShr.end(), std::back_inserter(arrWk));
1678 TestTypes(arrShr);
1679 TestTypes(arrWk);
1680#else
1681 REPORT("Known issue: C++11 smart pointer tests are skipped.\n");
1682#endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
1683}
1684
1685#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1686template <template <typename...> typename TQueue>
1687void TestDeductionGuides() {
1688 using ComplexType = const std::string*;
1689 std::vector<ComplexType> v;
1690
1691 // check TQueue(InputIterator, InputIterator)
1692 TQueue q1(v.begin(), v.end());
1693 static_assert(std::is_same<decltype(q1), TQueue<ComplexType>>::value);
1694
1695 // check TQueue(InputIterator, InputIterator, Allocator)
1696 TQueue q2(v.begin(), v.end(), std::allocator<ComplexType>());
1697 static_assert(std::is_same<decltype(q2), TQueue<ComplexType, std::allocator<ComplexType>>>::value);
1698
1699 // check TQueue(TQueue &)
1700 TQueue q3(q1);
1701 static_assert(std::is_same<decltype(q3), decltype(q1)>::value);
1702
1703 // check TQueue(TQueue &, Allocator)
1704 TQueue q4(q2, std::allocator<ComplexType>());
1705 static_assert(std::is_same<decltype(q4), decltype(q2)>::value);
1706
1707 // check TQueue(TQueue &&)
1708 TQueue q5(std::move(q1));
1709 static_assert(std::is_same<decltype(q5), decltype(q1)>::value);
1710
1711 // check TQueue(TQueue &&, Allocator)
1712 TQueue q6(std::move(q4), std::allocator<ComplexType>());
1713 static_assert(std::is_same<decltype(q6), decltype(q4)>::value);
1714}
1715#endif
1716
1717int TestMain () {
1718 TestEmptiness();
1719
1720 TestFullness();
1721
1722 TestClearWorks();
1723
1724 TestQueueTypeDeclaration();
1725
1726 TestQueueIteratorWorks();
1727
1728 TestQueueConstructors();
1729
1730 TestQueueWorksWithPrimitiveTypes();
1731
1732 TestQueueWorksWithSSE();
1733
1734 // Test concurrent operations
1735 TestConcurrentPushPop();
1736
1737 TestExceptions();
1738
1739 TestAbort();
1740
1741#if __TBB_CPP11_RVALUE_REF_PRESENT
1742 TestMoveSupportInPushPop();
1743 TestMoveConstruction();
1744#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
1745 TestEmplace();
1746#endif /* __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT */
1747#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
1748
1749 TestTypes();
1750
1751#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1752 TestDeductionGuides<tbb::concurrent_queue>();
1753 TestDeductionGuides<tbb::concurrent_bounded_queue>();
1754#endif
1755
1756 return Harness::Done;
1757}
1758