1 /* 2 Copyright (c) 2005-2022 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 state_type state = LIVE; 1211 std::size_t m_unique_id; 1212 1213 allocator() : m_unique_id( 0 ) {} 1214 allocator(size_t unique_id) { m_unique_id = unique_id; } 1215 1216 ~allocator() { 1217 REQUIRE_MESSAGE(state == LIVE, "Destroyed allocator has been used."); 1218 state = DEAD; 1219 } 1220 1221 template<typename U> 1222 allocator(const allocator<U>& a) noexcept { 1223 REQUIRE_MESSAGE(a.state == LIVE, "Destroyed allocator has been used."); 1224 m_unique_id = a.m_unique_id; 1225 } 1226 1227 template<typename U> 1228 struct rebind { typedef allocator<U> other; }; 1229 1230 friend bool operator==(const allocator& lhs, const allocator& rhs) { 1231 REQUIRE_MESSAGE(lhs.state == LIVE, "Destroyed allocator has been used."); 1232 REQUIRE_MESSAGE(rhs.state == LIVE, "Destroyed allocator has been used."); 1233 return lhs.m_unique_id == rhs.m_unique_id; 1234 } 1235 }; 1236 1237 template <typename Queue> 1238 void AssertEquality(Queue &q, const std::vector<typename Queue::value_type> &vec) { 1239 CHECK(q.size() == typename Queue::size_type(vec.size())); 1240 CHECK(std::equal(q.unsafe_begin(), q.unsafe_end(), vec.begin())); 1241 } 1242 1243 template <typename Queue> 1244 void AssertEmptiness(Queue &q) { 1245 CHECK(q.empty()); 1246 CHECK(!q.size()); 1247 typename Queue::value_type elem; 1248 CHECK(!q.try_pop(elem)); 1249 } 1250 1251 template <push_t push_op, typename Queue> 1252 void FillTest(Queue &q, const std::vector<typename Queue::value_type> &vec) { 1253 for (typename std::vector<typename Queue::value_type>::const_iterator it = vec.begin(); it != vec.end(); ++it) 1254 CHECK(pusher<push_op>::push(q, *it)); 1255 AssertEquality(q, vec); 1256 } 1257 1258 template <pop_t pop_op, typename Queue> 1259 void EmptyTest(Queue &q, const std::vector<typename Queue::value_type> &vec) { 1260 typedef typename Queue::value_type value_type; 1261 1262 value_type elem; 1263 typename std::vector<value_type>::const_iterator it = vec.begin(); 1264 while (popper<pop_op>::pop(q, elem)) { 1265 CHECK(elem == *it); 1266 ++it; 1267 } 1268 CHECK(it == vec.end()); 1269 AssertEmptiness(q); 1270 } 1271 1272 template <typename T, typename A> 1273 void bounded_queue_specific_test(oneapi::tbb::concurrent_queue<T, A> &, const std::vector<T> &) { /* do nothing */ } 1274 1275 template <typename T, typename A> 1276 void bounded_queue_specific_test(oneapi::tbb::concurrent_bounded_queue<T, A> &q, const std::vector<T> &vec) { 1277 typedef typename oneapi::tbb::concurrent_bounded_queue<T, A>::size_type size_type; 1278 1279 FillTest<try_push_op>(q, vec); 1280 oneapi::tbb::concurrent_bounded_queue<T, A> q2 = q; 1281 EmptyTest<pop_op>(q, vec); 1282 1283 // capacity 1284 q2.set_capacity(size_type(vec.size())); 1285 CHECK(q2.capacity() == size_type(vec.size())); 1286 CHECK(q2.size() == size_type(vec.size())); 1287 CHECK(!q2.try_push(vec[0])); 1288 q.abort(); 1289 } 1290 1291 // Checks operability of the queue the data was moved from 1292 template<typename T, typename CQ> 1293 void TestQueueOperabilityAfterDataMove( CQ& queue ) { 1294 const std::size_t size = 10; 1295 std::vector<T> v(size); 1296 for( std::size_t i = 0; i < size; ++i ) v[i] = T( i * i + i ); 1297 1298 FillTest<push_op>(queue, v); 1299 EmptyTest<try_pop_op>(queue, v); 1300 bounded_queue_specific_test(queue, v); 1301 } 1302 1303 template<class CQ, class T> 1304 void TestMoveConstructors() { 1305 T::construction_num = T::destruction_num = 0; 1306 CQ src_queue( allocator<T>(0) ); 1307 const std::size_t size = 10; 1308 for( std::size_t i = 0; i < size; ++i ) 1309 src_queue.push( T(i + (i ^ size)) ); 1310 CHECK(T::construction_num == 2 * size); 1311 CHECK(T::destruction_num == size); 1312 1313 const T* locations[size]; 1314 typename CQ::const_iterator qit = src_queue.unsafe_begin(); 1315 for( std::size_t i = 0; i < size; ++i, ++qit ) 1316 locations[i] = &(*qit); 1317 1318 // Ensuring allocation operation takes place during move when allocators are different 1319 T::construction_num = T::destruction_num = 0; 1320 CQ dst_queue( std::move(src_queue), allocator<T>(1) ); 1321 CHECK(T::construction_num == size); 1322 CHECK(T::destruction_num == size); 1323 1324 TestQueueOperabilityAfterDataMove<T>( src_queue ); 1325 1326 qit = dst_queue.unsafe_begin(); 1327 for( std::size_t i = 0; i < size; ++i, ++qit ) { 1328 REQUIRE_MESSAGE(locations[i] != &(*qit), "an item should have been copied but was not" ); 1329 locations[i] = &(*qit); 1330 } 1331 1332 T::construction_num = T::destruction_num = 0; 1333 // Ensuring there is no allocation operation during move with equal allocators 1334 CQ dst_queue2( std::move(dst_queue), allocator<T>(1) ); 1335 CHECK(T::construction_num == 0); 1336 CHECK(T::destruction_num == 0); 1337 1338 TestQueueOperabilityAfterDataMove<T>( dst_queue ); 1339 1340 qit = dst_queue2.unsafe_begin(); 1341 for( std::size_t i = 0; i < size; ++i, ++qit ) { 1342 REQUIRE_MESSAGE(locations[i] == &(*qit), "an item should have been moved but was not" ); 1343 } 1344 1345 for( std::size_t i = 0; i < size; ++i) { 1346 T test(i + (i ^ size)); 1347 T popped; 1348 bool pop_result = dst_queue2.try_pop( popped ); 1349 CHECK(pop_result); 1350 CHECK(test == popped); 1351 } 1352 CHECK(dst_queue2.empty()); 1353 CHECK(dst_queue2.size() == 0); 1354 } 1355 1356 void TestMoveConstruction() { 1357 TestMoveConstructors<ConcQWithSizeWrapper<Bar, allocator<Bar>>, Bar>(); 1358 TestMoveConstructors<oneapi::tbb::concurrent_bounded_queue<Bar, allocator<Bar>>, Bar>(); 1359 } 1360 1361 class NonTrivialConstructorType { 1362 public: 1363 NonTrivialConstructorType( int a = 0 ) : m_a( a ), m_str( "" ) {} 1364 NonTrivialConstructorType( const std::string& str ) : m_a( 0 ), m_str( str ) {} 1365 NonTrivialConstructorType( int a, const std::string& str ) : m_a( a ), m_str( str ) {} 1366 int get_a() const { return m_a; } 1367 std::string get_str() const { return m_str; } 1368 private: 1369 int m_a; 1370 std::string m_str; 1371 }; 1372 1373 enum emplace_t { emplace_op, try_emplace_op }; 1374 1375 template<emplace_t emplace_op> 1376 struct emplacer { 1377 template<typename CQ, typename... Args> 1378 static void emplace( CQ& queue, Args&&... val ) { queue.emplace( std::forward<Args>( val )... ); } 1379 }; 1380 1381 template<> 1382 struct emplacer <try_emplace_op> { 1383 template<typename CQ, typename... Args> 1384 static void emplace( CQ& queue, Args&&... val ) { 1385 bool result = queue.try_emplace( std::forward<Args>( val )... ); 1386 REQUIRE_MESSAGE(result, "try_emplace error\n"); 1387 } 1388 }; 1389 1390 template<typename CQ, emplace_t emplace_op> 1391 void TestEmplaceInQueue() { 1392 CQ cq; 1393 std::string test_str = "I'm being emplaced!"; 1394 { 1395 emplacer<emplace_op>::emplace( cq, 5 ); 1396 CHECK(cq.size() == 1); 1397 NonTrivialConstructorType popped( -1 ); 1398 bool result = cq.try_pop( popped ); 1399 CHECK(result); 1400 CHECK(popped.get_a() == 5); 1401 CHECK(popped.get_str() == std::string( "" )); 1402 } 1403 1404 CHECK(cq.empty()); 1405 1406 { 1407 NonTrivialConstructorType popped( -1 ); 1408 emplacer<emplace_op>::emplace( cq, std::string(test_str) ); 1409 bool result = cq.try_pop( popped ); 1410 CHECK(result); 1411 CHECK(popped.get_a() == 0); 1412 CHECK(popped.get_str() == test_str); 1413 } 1414 1415 CHECK(cq.empty()); 1416 1417 { 1418 NonTrivialConstructorType popped( -1, "" ); 1419 emplacer<emplace_op>::emplace( cq, 5, std::string(test_str) ); 1420 bool result = cq.try_pop( popped ); 1421 CHECK(result); 1422 CHECK(popped.get_a() == 5); 1423 CHECK(popped.get_str() == test_str); 1424 } 1425 } 1426 void TestEmplace() { 1427 TestEmplaceInQueue<ConcQWithSizeWrapper<NonTrivialConstructorType>, emplace_op>(); 1428 TestEmplaceInQueue<oneapi::tbb::concurrent_bounded_queue<NonTrivialConstructorType>, emplace_op>(); 1429 TestEmplaceInQueue<oneapi::tbb::concurrent_bounded_queue<NonTrivialConstructorType>, try_emplace_op>(); 1430 } 1431 1432 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 1433 template <template <typename...> typename TQueue> 1434 void TestDeductionGuides() { 1435 using ComplexType = const std::string*; 1436 std::vector<ComplexType> v; 1437 1438 // check TQueue(InputIterator, InputIterator) 1439 TQueue q1(v.begin(), v.end()); 1440 static_assert(std::is_same<decltype(q1), TQueue<ComplexType>>::value); 1441 1442 // check TQueue(InputIterator, InputIterator, Allocator) 1443 TQueue q2(v.begin(), v.end(), std::allocator<ComplexType>()); 1444 static_assert(std::is_same<decltype(q2), TQueue<ComplexType, std::allocator<ComplexType>>>::value); 1445 1446 // check TQueue(TQueue &) 1447 TQueue q3(q1); 1448 static_assert(std::is_same<decltype(q3), decltype(q1)>::value); 1449 1450 // check TQueue(TQueue &, Allocator) 1451 TQueue q4(q2, std::allocator<ComplexType>()); 1452 static_assert(std::is_same<decltype(q4), decltype(q2)>::value); 1453 1454 // check TQueue(TQueue &&) 1455 TQueue q5(std::move(q1)); 1456 static_assert(std::is_same<decltype(q5), decltype(q1)>::value); 1457 1458 // check TQueue(TQueue &&, Allocator) 1459 TQueue q6(std::move(q4), std::allocator<ComplexType>()); 1460 static_assert(std::is_same<decltype(q6), decltype(q4)>::value); 1461 } 1462 #endif 1463 1464 template <typename Iterator, typename QueueType> 1465 void TestQueueIteratorComparisonsBasic( QueueType& q ) { 1466 REQUIRE_MESSAGE(!q.empty(), "Incorrect test setup"); 1467 using namespace comparisons_testing; 1468 Iterator it1, it2; 1469 testEqualityComparisons</*ExpectEqual = */true>(it1, it2); 1470 it1 = q.unsafe_begin(); 1471 testEqualityComparisons</*ExpectEqual = */false>(it1, it2); 1472 it2 = q.unsafe_begin(); 1473 testEqualityComparisons</*ExpectEqual = */true>(it1, it2); 1474 it2 = q.unsafe_end(); 1475 testEqualityComparisons</*ExpectEqual = */false>(it1, it2); 1476 } 1477 1478 template <typename QueueType> 1479 void TestQueueIteratorComparisons() { 1480 QueueType q; 1481 q.emplace(1); 1482 q.emplace(2); 1483 q.emplace(3); 1484 TestQueueIteratorComparisonsBasic<typename QueueType::iterator>(q); 1485 const QueueType& cq = q; 1486 TestQueueIteratorComparisonsBasic<typename QueueType::const_iterator>(cq); 1487 } 1488 1489 //! Test constructors 1490 //! \brief \ref interface \ref requirement 1491 TEST_CASE("testing constructors") { 1492 TestQueueConstructors(); 1493 } 1494 1495 //! Test work with empty queue 1496 //! \brief \ref interface \ref requirement 1497 TEST_CASE("testing work with empty queue") { 1498 TestEmptiness(); 1499 } 1500 1501 //! Test set capacity operation 1502 //! \brief \ref interface \ref requirement 1503 TEST_CASE("testing set capacity operation") { 1504 TestFullness(); 1505 } 1506 1507 //! Test clean operation 1508 //! \brief \ref interface \ref requirement 1509 TEST_CASE("testing clean operation") { 1510 TestClearWorks(); 1511 } 1512 1513 //! Test move constructors 1514 //! \brief \ref interface \ref requirement 1515 TEST_CASE("testing move constructor") { 1516 TestMoveConstruction(); 1517 } 1518 1519 //! Test move support in push and pop 1520 //! \brief \ref requirement 1521 TEST_CASE("testing move support in push and pop") { 1522 TestMoveSupportInPushPop(); 1523 } 1524 1525 //! Test emplace operation 1526 //! \brief \ref interface \ref requirement 1527 TEST_CASE("testing emplace") { 1528 TestEmplace(); 1529 } 1530 1531 //! Test concurrent_queues member types 1532 //! \brief \ref interface \ref requirement 1533 TEST_CASE("testing concurrent_queues member types"){ 1534 test_member_types<oneapi::tbb::concurrent_queue>(); 1535 test_member_types<oneapi::tbb::concurrent_bounded_queue>(); 1536 1537 // Test size_type 1538 static_assert(std::is_unsigned<typename oneapi::tbb::concurrent_queue<int>::size_type>::value, 1539 "Incorrect oneapi::tbb::concurrent_queue::size_type member type"); 1540 static_assert(std::is_signed<typename oneapi::tbb::concurrent_bounded_queue<int>::size_type>::value, 1541 "Incorrect oneapi::tbb::concurrent_bounded_queue::size_type member type"); 1542 } 1543 1544 //! Test iterators 1545 //! \brief \ref interface \ref requirement 1546 TEST_CASE("testing iterators") { 1547 TestQueueIteratorWorks(); 1548 } 1549 1550 //! Test concurrent oprations support 1551 //! \brief \ref requirement 1552 TEST_CASE("testing concurrent oprations support") { 1553 TestConcurrentPushPop(); 1554 } 1555 1556 #if TBB_USE_EXCEPTIONS 1557 //! Test exception safety 1558 //! \brief \ref requirement 1559 TEST_CASE("testing exception safety") { 1560 TestExceptions(); 1561 } 1562 1563 //! Test abort operation 1564 //! \brief \ref interface \ref requirement 1565 TEST_CASE("testing abort operation") { 1566 TestAbort(); 1567 } 1568 #endif 1569 1570 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 1571 //! Test deduction guides 1572 //! \brief \ref interface 1573 TEST_CASE("testing deduction guides") { 1574 TestDeductionGuides<oneapi::tbb::concurrent_queue>(); 1575 TestDeductionGuides<oneapi::tbb::concurrent_bounded_queue>(); 1576 } 1577 #endif 1578 1579 //! \brief \ref interface \ref requirement 1580 TEST_CASE("concurrent_queue iterator comparisons") { 1581 TestQueueIteratorComparisons<oneapi::tbb::concurrent_queue<int>>(); 1582 } 1583 1584 //! \brief \ref interface \ref requirement 1585 TEST_CASE("concurrent_bounded_queue iterator comparisons") { 1586 TestQueueIteratorComparisons<oneapi::tbb::concurrent_bounded_queue<int>>(); 1587 } 1588 1589 class MinimalisticObject { 1590 public: 1591 struct flag {}; 1592 1593 MinimalisticObject() = delete; 1594 MinimalisticObject(flag) : underlying_obj(default_obj) {} 1595 1596 MinimalisticObject(const MinimalisticObject&) = delete; 1597 MinimalisticObject& operator=(const MinimalisticObject&) = delete; 1598 1599 std::size_t get_obj() const { return underlying_obj; } 1600 std::size_t get_default_obj() const { return default_obj; } 1601 1602 protected: 1603 static constexpr std::size_t default_obj = 42; 1604 std::size_t underlying_obj; 1605 friend struct MoveAssignableMinimalisticObject; 1606 }; 1607 1608 struct MoveAssignableMinimalisticObject : MinimalisticObject { 1609 public: 1610 using MinimalisticObject::MinimalisticObject; 1611 1612 MoveAssignableMinimalisticObject& operator=(MoveAssignableMinimalisticObject&& other) { 1613 if (this != &other) { 1614 underlying_obj = other.underlying_obj; 1615 other.underlying_obj = 0; 1616 } 1617 return *this; 1618 } 1619 }; 1620 1621 template <typename Container> 1622 void test_basics(Container& container, std::size_t desired_size) { 1623 CHECK(!container.empty()); 1624 1625 std::size_t counter = 0; 1626 for (auto it = container.unsafe_begin(); it != container.unsafe_end(); ++it) { 1627 CHECK(it->get_obj() == it->get_default_obj()); 1628 ++counter; 1629 } 1630 CHECK(counter == desired_size); 1631 1632 container.clear(); 1633 CHECK(container.empty()); 1634 } 1635 1636 template <template <class...> class Container> 1637 void test_with_minimalistic_objects() { 1638 // Test with MinimalisticObject and no pop operations 1639 const std::size_t elements_count = 100; 1640 { 1641 Container<MinimalisticObject> default_container; 1642 1643 for (std::size_t i = 0; i < elements_count; ++i) { 1644 default_container.emplace(MinimalisticObject::flag{}); 1645 } 1646 test_basics(default_container, elements_count); 1647 } 1648 // Test with MoveAssignableMinimalisticObject with pop operation 1649 { 1650 Container<MoveAssignableMinimalisticObject> default_container; 1651 1652 for (std::size_t i = 0; i < elements_count; ++i) { 1653 default_container.emplace(MinimalisticObject::flag{}); 1654 } 1655 test_basics(default_container, elements_count); 1656 1657 // Refill again 1658 for (std::size_t i = 0; i < elements_count; ++i) { 1659 default_container.emplace(MinimalisticObject::flag{}); 1660 } 1661 1662 MoveAssignableMinimalisticObject result(MinimalisticObject::flag{}); 1663 1664 std::size_t element_counter = 0; 1665 while (!default_container.empty()) { 1666 CHECK(default_container.try_pop(result)); 1667 ++element_counter; 1668 } 1669 1670 CHECK(element_counter == elements_count); 1671 CHECK(default_container.empty()); 1672 } 1673 } 1674 1675 //! \brief \ref requirement 1676 TEST_CASE("Test with minimalistic object type") { 1677 test_with_minimalistic_objects<oneapi::tbb::concurrent_queue>(); 1678 test_with_minimalistic_objects<oneapi::tbb::concurrent_bounded_queue>(); 1679 } 1680