1 /* 2 Copyright (c) 2005-2021 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 #if _MSC_VER 18 #if __INTEL_COMPILER 19 #pragma warning(disable : 2586) // decorated name length exceeded, name was truncated 20 #else 21 // Workaround for vs2015 and warning name was longer than the compiler limit (4096). 22 #pragma warning (disable: 4503) 23 #endif 24 #endif 25 26 #define TBB_DEFINE_STD_HASH_SPECIALIZATIONS 1 27 #define TBB_PREVIEW_CONCURRENT_HASH_MAP_EXTENSIONS 1 28 #include <common/test.h> 29 #include <common/utils.h> 30 #include <common/range_based_for_support.h> 31 #include <common/custom_allocators.h> 32 #include <common/containers_common.h> 33 #include <common/concepts_common.h> 34 #include <tbb/concurrent_hash_map.h> 35 #include <tbb/parallel_for.h> 36 #include <common/concurrent_associative_common.h> 37 #include <vector> 38 #include <list> 39 #include <algorithm> 40 #include <functional> 41 #include <scoped_allocator> 42 #include <mutex> 43 44 //! \file test_concurrent_hash_map.cpp 45 //! \brief Test for [containers.concurrent_hash_map containers.tbb_hash_compare] specification 46 47 void TestRangeBasedFor(){ 48 using namespace range_based_for_support_tests; 49 50 INFO("testing range based for loop compatibility \n"); 51 using ch_map = tbb::concurrent_hash_map<int,int>; 52 ch_map a_ch_map; 53 54 const int sequence_length = 100; 55 for (int i = 1; i <= sequence_length; ++i){ 56 a_ch_map.insert(ch_map::value_type(i,i)); 57 } 58 59 REQUIRE_MESSAGE((range_based_for_accumulate(a_ch_map, pair_second_summer(), 0) == gauss_summ_of_int_sequence(sequence_length)), 60 "incorrect accumulated value generated via range based for ?"); 61 } 62 63 // The helper to run a test only when a default construction is present. 64 template <bool default_construction_present> struct do_default_construction_test { 65 template<typename FuncType> void operator() ( FuncType func ) const { func(); } 66 }; 67 68 template <> struct do_default_construction_test<false> { 69 template<typename FuncType> void operator()( FuncType ) const {} 70 }; 71 72 template <typename Table> 73 class test_insert_by_key { 74 using value_type = typename Table::value_type; 75 Table &my_c; 76 const value_type &my_value; 77 public: 78 test_insert_by_key( Table &c, const value_type &value ) : my_c(c), my_value(value) {} 79 void operator()() const { 80 { 81 typename Table::accessor a; 82 CHECK(my_c.insert( a, my_value.first )); 83 CHECK(utils::IsEqual()(a->first, my_value.first)); 84 a->second = my_value.second; 85 } 86 { 87 typename Table::const_accessor ca; 88 CHECK(!my_c.insert( ca, my_value.first )); 89 CHECK(utils::IsEqual()(ca->first, my_value.first)); 90 CHECK(utils::IsEqual()(ca->second, my_value.second)); 91 } 92 } 93 }; 94 95 template <typename Table, typename Iterator, typename Range = typename Table::range_type> 96 class test_range { 97 using value_type = typename Table::value_type; 98 Table &my_c; 99 const std::list<value_type> &my_lst; 100 std::vector<detail::atomic_type<bool>>& my_marks; 101 public: 102 test_range( Table &c, const std::list<value_type> &lst, std::vector<detail::atomic_type<bool>> &marks ) : my_c(c), my_lst(lst), my_marks(marks) { 103 for (std::size_t i = 0; i < my_marks.size(); ++i) { 104 my_marks[i].store(false, std::memory_order_relaxed); 105 } 106 } 107 108 void operator()( const Range &r ) const { do_test_range( r.begin(), r.end() ); } 109 void do_test_range( Iterator i, Iterator j ) const { 110 for ( Iterator it = i; it != j; ) { 111 Iterator it_prev = it++; 112 typename std::list<value_type>::const_iterator it2 = std::search( my_lst.begin(), my_lst.end(), it_prev, it, utils::IsEqual() ); 113 CHECK(it2 != my_lst.end()); 114 typename std::list<value_type>::difference_type dist = std::distance( my_lst.begin(), it2 ); 115 CHECK(!my_marks[dist]); 116 my_marks[dist].store(true); 117 } 118 } 119 }; 120 121 template <bool default_construction_present, typename Table> 122 class check_value { 123 using const_iterator = typename Table::const_iterator; 124 using iterator = typename Table::iterator; 125 using size_type = typename Table::size_type; 126 Table &my_c; 127 public: 128 check_value( Table &c ) : my_c(c) {} 129 void operator()(const typename Table::value_type &value ) { 130 const Table &const_c = my_c; 131 CHECK(my_c.count( value.first ) == 1); 132 { // tests with a const accessor. 133 typename Table::const_accessor ca; 134 // find 135 CHECK(my_c.find( ca, value.first )); 136 CHECK(!ca.empty() ); 137 CHECK(utils::IsEqual()(ca->first, value.first)); 138 CHECK(utils::IsEqual()(ca->second, value.second)); 139 // erase 140 CHECK(my_c.erase( ca )); 141 CHECK(my_c.count( value.first ) == 0); 142 // insert (pair) 143 CHECK(my_c.insert( ca, value )); 144 CHECK(utils::IsEqual()(ca->first, value.first)); 145 CHECK(utils::IsEqual()(ca->second, value.second)); 146 } { // tests with a non-const accessor. 147 typename Table::accessor a; 148 // find 149 CHECK(my_c.find( a, value.first )); 150 CHECK(!a.empty() ); 151 CHECK(utils::IsEqual()(a->first, value.first)); 152 CHECK(utils::IsEqual()(a->second, value.second)); 153 // erase 154 CHECK(my_c.erase( a )); 155 CHECK(my_c.count( value.first ) == 0); 156 // insert 157 CHECK(my_c.insert( a, value )); 158 CHECK(utils::IsEqual()(a->first, value.first)); 159 CHECK(utils::IsEqual()(a->second, value.second)); 160 } 161 // erase by key 162 CHECK(my_c.erase( value.first )); 163 CHECK(my_c.count( value.first ) == 0); 164 do_default_construction_test<default_construction_present>()(test_insert_by_key<Table>( my_c, value )); 165 // insert by value 166 CHECK(my_c.insert( value ) != default_construction_present); 167 // equal_range 168 std::pair<iterator,iterator> r1 = my_c.equal_range( value.first ); 169 iterator r1_first_prev = r1.first++; 170 CHECK((utils::IsEqual()( *r1_first_prev, value ) && utils::IsEqual()( r1.first, r1.second ))); 171 std::pair<const_iterator,const_iterator> r2 = const_c.equal_range( value.first ); 172 const_iterator r2_first_prev = r2.first++; 173 CHECK((utils::IsEqual()( *r2_first_prev, value ) && utils::IsEqual()( r2.first, r2.second ))); 174 } 175 }; 176 177 template <typename Value, typename U = Value> 178 struct CompareTables { 179 template <typename T> 180 static bool IsEqual( const T& t1, const T& t2 ) { 181 return (t1 == t2) && !(t1 != t2); 182 } 183 }; 184 185 template <typename U> 186 struct CompareTables< std::pair<const std::weak_ptr<U>, std::weak_ptr<U> > > { 187 template <typename T> 188 static bool IsEqual( const T&, const T& ) { 189 /* do nothing for std::weak_ptr */ 190 return true; 191 } 192 }; 193 194 template <bool default_construction_present, typename Table> 195 void Examine( Table c, const std::list<typename Table::value_type> &lst) { 196 using const_table = const Table; 197 using const_iterator = typename Table::const_iterator; 198 using iterator = typename Table::iterator; 199 using value_type = typename Table::value_type; 200 using size_type = typename Table::size_type; 201 202 CHECK(!c.empty()); 203 CHECK(c.size() == lst.size()); 204 CHECK(c.max_size() >= c.size()); 205 206 const check_value<default_construction_present, Table> cv(c); 207 std::for_each( lst.begin(), lst.end(), cv ); 208 209 std::vector<detail::atomic_type<bool>> marks( lst.size() ); 210 211 test_range<Table,iterator>( c, lst, marks ).do_test_range( c.begin(), c.end() ); 212 CHECK(std::find( marks.begin(), marks.end(), false ) == marks.end()); 213 214 test_range<const_table,const_iterator>( c, lst, marks ).do_test_range( c.begin(), c.end() ); 215 CHECK(std::find( marks.begin(), marks.end(), false ) == marks.end()); 216 217 using range_type = typename Table::range_type; 218 tbb::parallel_for( c.range(), test_range<Table,typename range_type::iterator,range_type>( c, lst, marks ) ); 219 CHECK(std::find( marks.begin(), marks.end(), false ) == marks.end()); 220 221 const_table const_c = c; 222 CHECK(CompareTables<value_type>::IsEqual( c, const_c )); 223 224 const size_type new_bucket_count = 2*c.bucket_count(); 225 c.rehash( new_bucket_count ); 226 CHECK(c.bucket_count() >= new_bucket_count); 227 228 Table c2; 229 typename std::list<value_type>::const_iterator begin5 = lst.begin(); 230 std::advance( begin5, 5 ); 231 c2.insert( lst.begin(), begin5 ); 232 std::for_each( lst.begin(), begin5, check_value<default_construction_present, Table>( c2 ) ); 233 234 c2.swap( c ); 235 CHECK(CompareTables<value_type>::IsEqual( c2, const_c )); 236 CHECK(c.size() == 5); 237 std::for_each( lst.begin(), lst.end(), check_value<default_construction_present,Table>(c2) ); 238 239 swap( c, c2 ); 240 CHECK(CompareTables<value_type>::IsEqual( c, const_c )); 241 CHECK(c2.size() == 5); 242 243 c2.clear(); 244 CHECK(CompareTables<value_type>::IsEqual( c2, Table() )); 245 246 typename Table::allocator_type a = c.get_allocator(); 247 value_type *ptr = a.allocate(1); 248 CHECK(ptr); 249 a.deallocate( ptr, 1 ); 250 } 251 252 template <typename T> 253 struct debug_hash_compare : public tbb::detail::d1::tbb_hash_compare<T> {}; 254 255 template <bool default_construction_present, typename Value> 256 void TypeTester( const std::list<Value> &lst ) { 257 using first_type = typename Value::first_type; 258 using key_type = typename std::remove_const<first_type>::type; 259 using second_type = typename Value::second_type; 260 using ch_map = tbb::concurrent_hash_map<key_type, second_type>; 261 debug_hash_compare<key_type> compare{}; 262 // Construct an empty hash map. 263 ch_map c1; 264 c1.insert( lst.begin(), lst.end() ); 265 Examine<default_construction_present>( c1, lst ); 266 267 // Constructor from initializer_list. 268 typename std::list<Value>::const_iterator it = lst.begin(); 269 std::initializer_list<Value> il = { *it++, *it++, *it++ }; 270 ch_map c2( il ); 271 c2.insert( it, lst.end() ); 272 Examine<default_construction_present>( c2, lst ); 273 274 // Constructor from initializer_list and compare object 275 ch_map c3( il, compare); 276 c3.insert( it, lst.end() ); 277 Examine<default_construction_present>( c3, lst ); 278 279 // Constructor from initializer_list, compare object and allocator 280 ch_map c4( il, compare, typename ch_map::allocator_type()); 281 c4.insert( it, lst.end()); 282 Examine<default_construction_present>( c4, lst ); 283 284 // Copying constructor. 285 ch_map c5(c1); 286 Examine<default_construction_present>( c5, lst ); 287 // Construct with non-default allocator 288 using ch_map_debug_alloc = tbb::concurrent_hash_map<key_type, second_type, 289 tbb::detail::d1::tbb_hash_compare<key_type>, 290 LocalCountingAllocator<std::allocator<Value>>>; 291 ch_map_debug_alloc c6; 292 c6.insert( lst.begin(), lst.end() ); 293 Examine<default_construction_present>( c6, lst ); 294 // Copying constructor 295 ch_map_debug_alloc c7(c6); 296 Examine<default_construction_present>( c7, lst ); 297 // Construction empty table with n preallocated buckets. 298 ch_map c8( lst.size() ); 299 c8.insert( lst.begin(), lst.end() ); 300 Examine<default_construction_present>( c8, lst ); 301 ch_map_debug_alloc c9( lst.size() ); 302 c9.insert( lst.begin(), lst.end() ); 303 Examine<default_construction_present>( c9, lst ); 304 // Construction with copying iteration range. 305 ch_map c10_1( c1.begin(), c1.end() ), c10_2(c1.cbegin(), c1.cend()); 306 Examine<default_construction_present>( c10_1, lst ); 307 Examine<default_construction_present>( c10_2, lst ); 308 // Construction with copying iteration range and given allocator instance. 309 LocalCountingAllocator<std::allocator<Value>> allocator; 310 ch_map_debug_alloc c11( lst.begin(), lst.end(), allocator ); 311 Examine<default_construction_present>( c11, lst ); 312 313 using ch_map_debug_hash = tbb::concurrent_hash_map<key_type, second_type, 314 debug_hash_compare<key_type>, 315 typename ch_map::allocator_type>; 316 317 // Constructor with two iterators and hash_compare 318 ch_map_debug_hash c12(c1.begin(), c1.end(), compare); 319 Examine<default_construction_present>( c12, lst ); 320 321 ch_map_debug_hash c13(c1.begin(), c1.end(), compare, typename ch_map::allocator_type()); 322 Examine<default_construction_present>( c13, lst ); 323 } 324 325 void TestSpecificTypes() { 326 const int NUMBER = 10; 327 328 using int_int_t = std::pair<const int, int>; 329 std::list<int_int_t> arrIntInt; 330 for ( int i=0; i<NUMBER; ++i ) arrIntInt.push_back( int_int_t(i, NUMBER-i) ); 331 TypeTester</*default_construction_present = */true>( arrIntInt ); 332 333 using ref_int_t = std::pair<const std::reference_wrapper<const int>, int>; 334 std::list<ref_int_t> arrRefInt; 335 for ( std::list<int_int_t>::iterator it = arrIntInt.begin(); it != arrIntInt.end(); ++it ) 336 arrRefInt.push_back( ref_int_t( it->first, it->second ) ); 337 TypeTester</*default_construction_present = */true>( arrRefInt ); 338 339 using int_ref_t = std::pair< const int, std::reference_wrapper<int> >; 340 std::list<int_ref_t> arrIntRef; 341 for ( std::list<int_int_t>::iterator it = arrIntInt.begin(); it != arrIntInt.end(); ++it ) 342 arrIntRef.push_back( int_ref_t( it->first, it->second ) ); 343 TypeTester</*default_construction_present = */false>( arrIntRef ); 344 345 using shr_shr_t = std::pair< const std::shared_ptr<int>, std::shared_ptr<int> >; 346 std::list<shr_shr_t> arrShrShr; 347 for ( int i=0; i<NUMBER; ++i ) { 348 const int NUMBER_minus_i = NUMBER - i; 349 arrShrShr.push_back( shr_shr_t( std::make_shared<int>(i), std::make_shared<int>(NUMBER_minus_i) ) ); 350 } 351 TypeTester< /*default_construction_present = */true>( arrShrShr ); 352 353 using wk_wk_t = std::pair< const std::weak_ptr<int>, std::weak_ptr<int> >; 354 std::list< wk_wk_t > arrWkWk; 355 std::copy( arrShrShr.begin(), arrShrShr.end(), std::back_inserter(arrWkWk) ); 356 TypeTester< /*default_construction_present = */true>( arrWkWk ); 357 358 // Check working with deprecated hashers 359 using pair_key_type = std::pair<int, int>; 360 using pair_int_t = std::pair<const pair_key_type, int>; 361 std::list<pair_int_t> arr_pair_int; 362 for (int i = 0; i < NUMBER; ++i) { 363 arr_pair_int.push_back(pair_int_t(pair_key_type{i, i}, i)); 364 } 365 TypeTester</*default_construction_present = */true>(arr_pair_int); 366 367 using tbb_string_key_type = std::basic_string<char, std::char_traits<char>, tbb::tbb_allocator<char>>; 368 using pair_tbb_string_int_t = std::pair<const tbb_string_key_type, int>; 369 std::list<pair_tbb_string_int_t> arr_pair_string_int; 370 for (int i = 0; i < NUMBER; ++i) { 371 tbb_string_key_type key(i, char(i)); 372 arr_pair_string_int.push_back(pair_tbb_string_int_t(key, i)); 373 } 374 TypeTester</*default_construction_present = */true>(arr_pair_string_int); 375 } 376 377 struct custom_hash_compare { 378 template<typename Allocator> 379 size_t hash(const AllocatorAwareData<Allocator>& key) const { 380 return my_hash_compare.hash(key.value()); 381 } 382 383 template<typename Allocator> 384 bool equal(const AllocatorAwareData<Allocator>& key1, const AllocatorAwareData<Allocator>& key2) const { 385 return my_hash_compare.equal(key1.value(), key2.value()); 386 } 387 388 private: 389 tbb::tbb_hash_compare<int> my_hash_compare; 390 }; 391 392 void TestScopedAllocator() { 393 using allocator_data_type = AllocatorAwareData<std::scoped_allocator_adaptor<tbb::tbb_allocator<int>>>; 394 using allocator_type = std::scoped_allocator_adaptor<tbb::tbb_allocator<std::pair<const allocator_data_type, allocator_data_type>>>; 395 using hash_map_type = tbb::concurrent_hash_map<allocator_data_type, allocator_data_type, 396 custom_hash_compare, allocator_type>; 397 398 allocator_type allocator; 399 allocator_data_type key1(1, allocator), key2(2, allocator); 400 allocator_data_type data1(1, allocator), data2(data1, allocator); 401 hash_map_type map1(allocator), map2(allocator); 402 403 hash_map_type::value_type v1(key1, data1), v2(key2, data2); 404 405 auto init_list = { v1, v2 }; 406 407 allocator_data_type::assert_on_constructions = true; 408 map1.emplace(key1, data1); 409 map2.emplace(key2, std::move(data2)); 410 411 map1.clear(); 412 map2.clear(); 413 414 map1.insert(v1); 415 map2.insert(std::move(v2)); 416 417 map1.clear(); 418 map2.clear(); 419 420 map1.insert(init_list); 421 422 map1.clear(); 423 map2.clear(); 424 425 hash_map_type::accessor a; 426 map2.insert(a, allocator_data_type(3)); 427 a.release(); 428 429 map1 = map2; 430 map2 = std::move(map1); 431 432 hash_map_type map3(allocator); 433 map3.rehash(1000); 434 map3 = map2; 435 } 436 437 // A test for undocumented member function internal_fast_find 438 // which is declared protected in concurrent_hash_map for internal TBB use 439 void TestInternalFastFind() { 440 typedef tbb::concurrent_hash_map<int, int> basic_chmap_type; 441 typedef basic_chmap_type::const_pointer const_pointer; 442 443 class chmap : public basic_chmap_type { 444 public: 445 chmap() : basic_chmap_type() {} 446 447 using basic_chmap_type::internal_fast_find; 448 }; 449 450 chmap m; 451 int sz = 100; 452 453 for (int i = 0; i != sz; ++i) { 454 m.insert(std::make_pair(i, i * i)); 455 } 456 REQUIRE_MESSAGE(m.size() == 100, "Incorrect concurrent_hash_map size"); 457 458 for (int i = 0; i != sz; ++i) { 459 const_pointer res = m.internal_fast_find(i); 460 REQUIRE_MESSAGE(res != nullptr, "Incorrect internal_fast_find return value for existing key"); 461 basic_chmap_type::value_type val = *res; 462 REQUIRE_MESSAGE(val.first == i, "Incorrect key in internal_fast_find return value"); 463 REQUIRE_MESSAGE(val.second == i * i, "Incorrect mapped in internal_fast_find return value"); 464 } 465 466 for (int i = sz; i != 2 * sz; ++i) { 467 const_pointer res = m.internal_fast_find(i); 468 REQUIRE_MESSAGE(res == nullptr, "Incorrect internal_fast_find return value for not existing key"); 469 } 470 } 471 472 struct default_container_traits { 473 template <typename container_type, typename iterator_type> 474 static container_type& construct_container(typename std::aligned_storage<sizeof(container_type)>::type& storage, iterator_type begin, iterator_type end){ 475 container_type* ptr = reinterpret_cast<container_type*>(&storage); 476 new (ptr) container_type(begin, end); 477 return *ptr; 478 } 479 480 template <typename container_type, typename iterator_type, typename allocator_type> 481 static container_type& construct_container(typename std::aligned_storage<sizeof(container_type)>::type& storage, iterator_type begin, iterator_type end, allocator_type const& a){ 482 container_type* ptr = reinterpret_cast<container_type*>(&storage); 483 new (ptr) container_type(begin, end, a); 484 return *ptr; 485 } 486 }; 487 488 struct hash_map_traits : default_container_traits { 489 enum{ expected_number_of_items_to_allocate_for_steal_move = 0 }; 490 491 template<typename T> 492 struct hash_compare { 493 bool equal( const T& lhs, const T& rhs ) const { 494 return lhs==rhs; 495 } 496 size_t hash( const T& k ) const { 497 return my_hash_func(k); 498 } 499 std::hash<T> my_hash_func; 500 }; 501 502 template <typename T, typename Allocator> 503 using container_type = tbb::concurrent_hash_map<T, T, hash_compare<T>, Allocator>; 504 505 template <typename T> 506 using container_value_type = std::pair<const T, T>; 507 508 template<typename element_type, typename allocator_type> 509 struct apply { 510 using type = tbb::concurrent_hash_map<element_type, element_type, hash_compare<element_type>, allocator_type>; 511 }; 512 513 using init_iterator_type = move_support_tests::FooPairIterator; 514 template <typename hash_map_type, typename iterator> 515 static bool equal(hash_map_type const& c, iterator begin, iterator end){ 516 bool equal_sizes = ( static_cast<size_t>(std::distance(begin, end)) == c.size() ); 517 if (!equal_sizes) 518 return false; 519 520 for (iterator it = begin; it != end; ++it ){ 521 if (c.count( (*it).first) == 0){ 522 return false; 523 } 524 } 525 return true; 526 } 527 }; 528 529 template <bool SimulateReacquiring> 530 class MinimalisticMutex { 531 public: 532 static constexpr bool is_rw_mutex = true; 533 static constexpr bool is_recursive_mutex = false; 534 static constexpr bool is_fair_mutex = false; 535 536 class scoped_lock { 537 public: 538 constexpr scoped_lock() noexcept : my_mutex_ptr(nullptr) {} 539 540 scoped_lock( MinimalisticMutex& m, bool = true ) : my_mutex_ptr(&m) { 541 my_mutex_ptr->my_mutex.lock(); 542 } 543 544 scoped_lock( const scoped_lock& ) = delete; 545 scoped_lock& operator=( const scoped_lock& ) = delete; 546 547 ~scoped_lock() { 548 if (my_mutex_ptr) release(); 549 } 550 551 void acquire( MinimalisticMutex& m, bool = true ) { 552 CHECK(my_mutex_ptr == nullptr); 553 my_mutex_ptr = &m; 554 my_mutex_ptr->my_mutex.lock(); 555 } 556 557 bool try_acquire( MinimalisticMutex& m, bool = true ) { 558 if (m.my_mutex.try_lock()) { 559 my_mutex_ptr = &m; 560 return true; 561 } 562 return false; 563 } 564 565 void release() { 566 CHECK(my_mutex_ptr != nullptr); 567 my_mutex_ptr->my_mutex.unlock(); 568 my_mutex_ptr = nullptr; 569 } 570 571 bool upgrade_to_writer() const { 572 // upgrade_to_writer should return false if the mutex simulates 573 // reaquiring the lock on upgrade operation 574 return !SimulateReacquiring; 575 } 576 577 bool downgrade_to_reader() const { 578 // downgrade_to_reader should return false if the mutex simulates 579 // reaquiring the lock on upgrade operation 580 return !SimulateReacquiring; 581 } 582 583 bool is_writer() const { 584 CHECK(my_mutex_ptr != nullptr); 585 return true; // Always a writer 586 } 587 588 private: 589 MinimalisticMutex* my_mutex_ptr; 590 }; // class scoped_lock 591 private: 592 std::mutex my_mutex; 593 }; // class MinimalisticMutex 594 595 template <bool SimulateReacquiring> 596 void test_with_minimalistic_mutex() { 597 using mutex_type = MinimalisticMutex<SimulateReacquiring>; 598 using chmap_type = tbb::concurrent_hash_map<int, int, tbb::tbb_hash_compare<int>, 599 tbb::tbb_allocator<std::pair<const int, int>>, 600 mutex_type>; 601 602 chmap_type chmap; 603 604 // Insert pre-existing elements 605 for (int i = 0; i < 100; ++i) { 606 bool result = chmap.emplace(i, i); 607 CHECK(result); 608 } 609 610 // Insert elements to erase 611 for (int i = 10000; i < 10005; ++i) { 612 bool result = chmap.emplace(i, i); 613 CHECK(result); 614 } 615 616 auto thread_body = [&]( const tbb::blocked_range<std::size_t>& range ) { 617 for (std::size_t item = range.begin(); item != range.end(); ++item) { 618 switch(item % 4) { 619 case 0 : 620 // Insert new elements 621 for (int i = 100; i < 200; ++i) { 622 typename chmap_type::const_accessor acc; 623 chmap.emplace(acc, i, i); 624 CHECK(acc->first == i); 625 CHECK(acc->second == i); 626 } 627 break; 628 case 1 : 629 // Insert pre-existing elements 630 for (int i = 0; i < 100; ++i) { 631 typename chmap_type::const_accessor acc; 632 bool result = chmap.emplace(acc, i, i * 10000); 633 CHECK(!result); 634 CHECK(acc->first == i); 635 CHECK(acc->second == i); 636 } 637 break; 638 case 2 : 639 // Find pre-existing elements 640 for (int i = 0; i < 100; ++i) { 641 typename chmap_type::const_accessor acc; 642 bool result = chmap.find(acc, i); 643 CHECK(result); 644 CHECK(acc->first == i); 645 CHECK(acc->second == i); 646 } 647 break; 648 case 3 : 649 // Erase pre-existing elements 650 for (int i = 10000; i < 10005; ++i) { 651 chmap.erase(i); 652 } 653 break; 654 } 655 } 656 }; // thread_body 657 658 tbb::blocked_range<std::size_t> br(0, 1000, 8); 659 660 tbb::parallel_for(br, thread_body); 661 662 // Check pre-existing and new elements 663 for (int i = 0; i < 200; ++i) { 664 typename chmap_type::const_accessor acc; 665 bool result = chmap.find(acc, i); 666 REQUIRE_MESSAGE(result, "Some element was unexpectedly removed or not inserted"); 667 REQUIRE_MESSAGE(acc->first == i, "Incorrect key"); 668 REQUIRE_MESSAGE(acc->second == i, "Incorrect value"); 669 } 670 671 // Check elements for erasure 672 for (int i = 10000; i < 10005; ++i) { 673 typename chmap_type::const_accessor acc; 674 bool result = chmap.find(acc, i); 675 REQUIRE_MESSAGE(!result, "Some element was not removed"); 676 } 677 } 678 679 void test_mutex_customization() { 680 test_with_minimalistic_mutex</*SimulateReacquiring = */false>(); 681 test_with_minimalistic_mutex</*SimulateReacquiring = */true>(); 682 } 683 684 //! Test of insert operation 685 //! \brief \ref error_guessing 686 TEST_CASE("testing range based for support"){ 687 TestRangeBasedFor(); 688 } 689 690 //! Test concurrent_hash_map with specific key/mapped types 691 //! \brief \ref regression \ref error_guessing 692 TEST_CASE("testing concurrent_hash_map with specific key/mapped types") { 693 TestSpecificTypes(); 694 } 695 696 //! Test work with scoped allocator 697 //! \brief \ref regression 698 TEST_CASE("testing work with scoped allocator") { 699 TestScopedAllocator(); 700 } 701 702 //! Test internal fast find for concurrent_hash_map 703 //! \brief \ref regression 704 TEST_CASE("testing internal fast find for concurrent_hash_map") { 705 TestInternalFastFind(); 706 } 707 708 //! Test constructor with move iterators 709 //! \brief \ref error_guessing 710 TEST_CASE("testing constructor with move iterators"){ 711 move_support_tests::test_constructor_with_move_iterators<hash_map_traits>(); 712 } 713 714 #if TBB_USE_EXCEPTIONS 715 //! Test exception in constructors 716 //! \brief \ref regression \ref error_guessing 717 TEST_CASE("Test exception in constructors") { 718 using allocator_type = StaticSharedCountingAllocator<std::allocator<std::pair<const int, int>>>; 719 using map_type = tbb::concurrent_hash_map<int, int, tbb::tbb_hash_compare<int>, allocator_type>; 720 721 auto init_list = {std::pair<const int, int>(1, 42), std::pair<const int, int>(2, 42), std::pair<const int, int>(3, 42), 722 std::pair<const int, int>(4, 42), std::pair<const int, int>(5, 42), std::pair<const int, int>(6, 42)}; 723 map_type map(init_list); 724 725 allocator_type::set_limits(1); 726 REQUIRE_THROWS_AS( [&] { 727 map_type map1(map); 728 utils::suppress_unused_warning(map1); 729 }(), const std::bad_alloc); 730 731 REQUIRE_THROWS_AS( [&] { 732 map_type map2(init_list.begin(), init_list.end()); 733 utils::suppress_unused_warning(map2); 734 }(), const std::bad_alloc); 735 736 tbb::tbb_hash_compare<int> test_hash; 737 738 REQUIRE_THROWS_AS( [&] { 739 map_type map3(init_list.begin(), init_list.end(), test_hash); 740 utils::suppress_unused_warning(map3); 741 }(), const std::bad_alloc); 742 743 REQUIRE_THROWS_AS( [&] { 744 map_type map4(init_list, test_hash); 745 utils::suppress_unused_warning(map4); 746 }(), const std::bad_alloc); 747 748 REQUIRE_THROWS_AS( [&] { 749 map_type map5(init_list); 750 utils::suppress_unused_warning(map5); 751 }(), const std::bad_alloc); 752 753 allocator_type::set_limits(0); 754 map_type big_map{}; 755 for (int i = 0; i < 1000; ++i) { 756 big_map.insert(std::pair<const int, int>(i, 42)); 757 } 758 759 allocator_type::init_counters(); 760 allocator_type::set_limits(300); 761 REQUIRE_THROWS_AS( [&] { 762 map_type map6(big_map); 763 utils::suppress_unused_warning(map6); 764 }(), const std::bad_alloc); 765 } 766 #endif // TBB_USE_EXCEPTIONS 767 768 //! \brief \ref error_guessing 769 TEST_CASE("swap with NotAlwaysEqualAllocator allocators") { 770 using allocator_type = NotAlwaysEqualAllocator<std::pair<const int, int>>; 771 using map_type = tbb::concurrent_hash_map<int, int, tbb::tbb_hash_compare<int>, allocator_type>; 772 773 map_type map1{}; 774 map_type map2({{42, 42}, {24, 42}}); 775 map_type map3(map2); 776 777 swap(map1, map2); 778 779 CHECK(map2.empty()); 780 CHECK(map1 == map3); 781 } 782 783 //! \brief \ref error_guessing 784 TEST_CASE("test concurrent_hash_map mutex customization") { 785 test_mutex_customization(); 786 } 787 788 #if __TBB_CPP20_CONCEPTS_PRESENT 789 template <bool ExpectSatisfies, typename Key, typename Mapped, typename... HCTypes> 790 requires (... && (utils::well_formed_instantiation<tbb::concurrent_hash_map, Key, Mapped, HCTypes> == ExpectSatisfies)) 791 void test_chmap_hash_compare_constraints() {} 792 793 //! \brief \ref error_guessing 794 TEST_CASE("tbb::concurrent_hash_map hash_compare constraints") { 795 using key_type = int; 796 using mapped_type = int; 797 using namespace test_concepts::hash_compare; 798 799 test_chmap_hash_compare_constraints</*Expected = */true, /*key = */key_type, /*mapped = */mapped_type, 800 Correct<key_type>, tbb::tbb_hash_compare<key_type>>(); 801 802 test_chmap_hash_compare_constraints</*Expected = */false, /*key = */key_type, /*mapped = */mapped_type, 803 NonCopyable<key_type>, NonDestructible<key_type>, 804 NoHash<key_type>, HashNonConst<key_type>, WrongInputHash<key_type>, WrongReturnHash<key_type>, 805 NoEqual<key_type>, EqualNonConst<key_type>, 806 WrongFirstInputEqual<key_type>, WrongSecondInputEqual<key_type>, WrongReturnEqual<key_type>>(); 807 } 808 809 template <bool ExpectSatisfies, typename Key, typename Mapped, typename... RWMutexes> 810 requires (... && (utils::well_formed_instantiation<tbb::concurrent_hash_map, Key, Mapped, 811 tbb::tbb_hash_compare<Key>, tbb::tbb_allocator<std::pair<const Key, Mapped>>, RWMutexes> == ExpectSatisfies)) 812 void test_chmap_mutex_constraints() {} 813 814 //! \brief \ref error_guessing 815 TEST_CASE("tbb::concurrent_hash_map rw_mutex constraints") { 816 using key_type = int; 817 using mapped_type = int; 818 using namespace test_concepts::rw_mutex; 819 820 test_chmap_mutex_constraints</*Expected = */true, key_type, mapped_type, 821 Correct>(); 822 823 test_chmap_mutex_constraints</*Expected = */false, key_type, mapped_type, 824 NoScopedLock, ScopedLockNoDefaultCtor, ScopedLockNoMutexCtor, 825 ScopedLockNoDtor, ScopedLockNoAcquire, ScopedLockWrongFirstInputAcquire, ScopedLockWrongSecondInputAcquire, ScopedLockNoTryAcquire, 826 ScopedLockWrongFirstInputTryAcquire, ScopedLockWrongSecondInputTryAcquire, ScopedLockWrongReturnTryAcquire, ScopedLockNoRelease, 827 ScopedLockNoUpgrade, ScopedLockWrongReturnUpgrade, ScopedLockNoDowngrade, ScopedLockWrongReturnDowngrade, 828 ScopedLockNoIsWriter, ScopedLockIsWriterNonConst, ScopedLockWrongReturnIsWriter>(); 829 } 830 831 //! \brief \ref error_guessing 832 TEST_CASE("container_range concept for tbb::concurrent_hash_map ranges") { 833 static_assert(test_concepts::container_range<tbb::concurrent_hash_map<int, int>::range_type>); 834 static_assert(test_concepts::container_range<tbb::concurrent_hash_map<int, int>::const_range_type>); 835 } 836 837 #endif // __TBB_CPP20_CONCEPTS_PRESENT 838