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