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