1 /* 2 Copyright (c) 2005-2023 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 // reacquiring 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 // reacquiring 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 struct SimpleTransparentHashCompare { 685 using is_transparent = void; 686 687 template <typename T> 688 std::size_t hash(const T&) const { return 0; } 689 690 template <typename T, typename U> 691 bool equal(const T& key1, const U& key2) const { return key1 == key2; } 692 }; 693 694 template <typename Accessor> 695 struct IsWriterAccessor : public Accessor { 696 using Accessor::is_writer; 697 }; 698 699 template <typename Map, typename Accessor> 700 void test_chmap_access_mode(bool expect_write) { 701 static_assert(std::is_same<int, typename Map::key_type>::value, "Incorrect test setup"); 702 Map map; 703 Accessor acc; 704 705 // Test homogeneous insert 706 bool result = map.insert(acc, 1); 707 CHECK(result); 708 CHECK_MESSAGE(acc.is_writer() == expect_write, "Incorrect access into the map from homogeneous insert"); 709 710 // Test heterogeneous insert 711 result = map.insert(acc, 2L); 712 CHECK(result); 713 CHECK_MESSAGE(acc.is_writer() == expect_write, "Incorrect access into the map from heterogeneous insert"); 714 715 // Test lvalue insert 716 typename Map::value_type value{3, 3}; 717 result = map.insert(acc, value); 718 CHECK(result); 719 CHECK_MESSAGE(acc.is_writer() == expect_write, "Incorrect access into the map from lvalue insert"); 720 721 // Test rvalue insert 722 result = map.insert(acc, typename Map::value_type{4, 4}); 723 CHECK(result); 724 CHECK_MESSAGE(acc.is_writer() == expect_write, "Incorrect access into the map from rvalue insert"); 725 726 // Test homogeneous find 727 result = map.find(acc, 1); 728 CHECK(result); 729 CHECK_MESSAGE(acc.is_writer() == expect_write, "Incorrect access into the map from homogeneous find"); 730 731 // Test heterogeneous find 732 result = map.find(acc, 2L); 733 CHECK(result); 734 CHECK_MESSAGE(acc.is_writer() == expect_write, "Incorrect access into the map from heterogeneous find"); 735 } 736 737 //! Test of insert operation 738 //! \brief \ref error_guessing 739 TEST_CASE("testing range based for support"){ 740 TestRangeBasedFor(); 741 } 742 743 //! Test concurrent_hash_map with specific key/mapped types 744 //! \brief \ref regression \ref error_guessing 745 TEST_CASE("testing concurrent_hash_map with specific key/mapped types") { 746 TestSpecificTypes(); 747 } 748 749 //! Test work with scoped allocator 750 //! \brief \ref regression 751 TEST_CASE("testing work with scoped allocator") { 752 TestScopedAllocator(); 753 } 754 755 //! Test internal fast find for concurrent_hash_map 756 //! \brief \ref regression 757 TEST_CASE("testing internal fast find for concurrent_hash_map") { 758 TestInternalFastFind(); 759 } 760 761 //! Test constructor with move iterators 762 //! \brief \ref error_guessing 763 TEST_CASE("testing constructor with move iterators"){ 764 move_support_tests::test_constructor_with_move_iterators<hash_map_traits>(); 765 } 766 767 #if TBB_USE_EXCEPTIONS 768 //! Test exception in constructors 769 //! \brief \ref regression \ref error_guessing 770 TEST_CASE("Test exception in constructors") { 771 using allocator_type = StaticSharedCountingAllocator<std::allocator<std::pair<const int, int>>>; 772 using map_type = tbb::concurrent_hash_map<int, int, tbb::tbb_hash_compare<int>, allocator_type>; 773 774 auto init_list = {std::pair<const int, int>(1, 42), std::pair<const int, int>(2, 42), std::pair<const int, int>(3, 42), 775 std::pair<const int, int>(4, 42), std::pair<const int, int>(5, 42), std::pair<const int, int>(6, 42)}; 776 map_type map(init_list); 777 778 allocator_type::set_limits(1); 779 REQUIRE_THROWS_AS( [&] { 780 map_type map1(map); 781 utils::suppress_unused_warning(map1); 782 }(), const std::bad_alloc); 783 784 REQUIRE_THROWS_AS( [&] { 785 map_type map2(init_list.begin(), init_list.end()); 786 utils::suppress_unused_warning(map2); 787 }(), const std::bad_alloc); 788 789 tbb::tbb_hash_compare<int> test_hash; 790 791 REQUIRE_THROWS_AS( [&] { 792 map_type map3(init_list.begin(), init_list.end(), test_hash); 793 utils::suppress_unused_warning(map3); 794 }(), const std::bad_alloc); 795 796 REQUIRE_THROWS_AS( [&] { 797 map_type map4(init_list, test_hash); 798 utils::suppress_unused_warning(map4); 799 }(), const std::bad_alloc); 800 801 REQUIRE_THROWS_AS( [&] { 802 map_type map5(init_list); 803 utils::suppress_unused_warning(map5); 804 }(), const std::bad_alloc); 805 806 allocator_type::set_limits(0); 807 map_type big_map{}; 808 for (int i = 0; i < 1000; ++i) { 809 big_map.insert(std::pair<const int, int>(i, 42)); 810 } 811 812 allocator_type::init_counters(); 813 allocator_type::set_limits(300); 814 REQUIRE_THROWS_AS( [&] { 815 map_type map6(big_map); 816 utils::suppress_unused_warning(map6); 817 }(), const std::bad_alloc); 818 } 819 #endif // TBB_USE_EXCEPTIONS 820 821 //! \brief \ref error_guessing 822 TEST_CASE("swap with NotAlwaysEqualAllocator allocators") { 823 using allocator_type = NotAlwaysEqualAllocator<std::pair<const int, int>>; 824 using map_type = tbb::concurrent_hash_map<int, int, tbb::tbb_hash_compare<int>, allocator_type>; 825 826 map_type map1{}; 827 map_type map2({{42, 42}, {24, 42}}); 828 map_type map3(map2); 829 830 swap(map1, map2); 831 832 CHECK(map2.empty()); 833 CHECK(map1 == map3); 834 } 835 836 //! \brief \ref error_guessing 837 TEST_CASE("test concurrent_hash_map mutex customization") { 838 test_mutex_customization(); 839 } 840 841 // A test for an issue when const_accessor passed to find provides write access into the map after the lookup 842 //! \brief \ref regression 843 TEST_CASE("test concurrent_hash_map accessors issue") { 844 using map_type = tbb::concurrent_hash_map<int, int, SimpleTransparentHashCompare>; 845 using accessor = IsWriterAccessor<typename map_type::accessor>; 846 using const_accessor = IsWriterAccessor<typename map_type::const_accessor>; 847 848 test_chmap_access_mode<map_type, accessor>(/*expect_write = */true); 849 test_chmap_access_mode<map_type, const_accessor>(/*expect_write = */false); 850 } 851 852 #if __TBB_CPP20_CONCEPTS_PRESENT 853 template <bool ExpectSatisfies, typename Key, typename Mapped, typename... HCTypes> 854 requires (... && (utils::well_formed_instantiation<tbb::concurrent_hash_map, Key, Mapped, HCTypes> == ExpectSatisfies)) 855 void test_chmap_hash_compare_constraints() {} 856 857 //! \brief \ref error_guessing 858 TEST_CASE("tbb::concurrent_hash_map hash_compare constraints") { 859 using key_type = int; 860 using mapped_type = int; 861 using namespace test_concepts::hash_compare; 862 863 test_chmap_hash_compare_constraints</*Expected = */true, /*key = */key_type, /*mapped = */mapped_type, 864 Correct<key_type>, tbb::tbb_hash_compare<key_type>>(); 865 866 test_chmap_hash_compare_constraints</*Expected = */false, /*key = */key_type, /*mapped = */mapped_type, 867 NonCopyable<key_type>, NonDestructible<key_type>, 868 NoHash<key_type>, HashNonConst<key_type>, WrongInputHash<key_type>, WrongReturnHash<key_type>, 869 NoEqual<key_type>, EqualNonConst<key_type>, 870 WrongFirstInputEqual<key_type>, WrongSecondInputEqual<key_type>, WrongReturnEqual<key_type>>(); 871 } 872 873 template <bool ExpectSatisfies, typename Key, typename Mapped, typename... RWMutexes> 874 requires (... && (utils::well_formed_instantiation<tbb::concurrent_hash_map, Key, Mapped, 875 tbb::tbb_hash_compare<Key>, tbb::tbb_allocator<std::pair<const Key, Mapped>>, RWMutexes> == ExpectSatisfies)) 876 void test_chmap_mutex_constraints() {} 877 878 //! \brief \ref error_guessing 879 TEST_CASE("tbb::concurrent_hash_map rw_mutex constraints") { 880 using key_type = int; 881 using mapped_type = int; 882 using namespace test_concepts::rw_mutex; 883 884 test_chmap_mutex_constraints</*Expected = */true, key_type, mapped_type, 885 Correct>(); 886 887 test_chmap_mutex_constraints</*Expected = */false, key_type, mapped_type, 888 NoScopedLock, ScopedLockNoDefaultCtor, ScopedLockNoMutexCtor, 889 ScopedLockNoDtor, ScopedLockNoAcquire, ScopedLockWrongFirstInputAcquire, ScopedLockWrongSecondInputAcquire, ScopedLockNoTryAcquire, 890 ScopedLockWrongFirstInputTryAcquire, ScopedLockWrongSecondInputTryAcquire, ScopedLockWrongReturnTryAcquire, ScopedLockNoRelease, 891 ScopedLockNoUpgrade, ScopedLockWrongReturnUpgrade, ScopedLockNoDowngrade, ScopedLockWrongReturnDowngrade, 892 ScopedLockNoIsWriter, ScopedLockIsWriterNonConst, ScopedLockWrongReturnIsWriter>(); 893 } 894 895 //! \brief \ref error_guessing 896 TEST_CASE("container_range concept for tbb::concurrent_hash_map ranges") { 897 static_assert(test_concepts::container_range<tbb::concurrent_hash_map<int, int>::range_type>); 898 static_assert(test_concepts::container_range<tbb::concurrent_hash_map<int, int>::const_range_type>); 899 } 900 901 #endif // __TBB_CPP20_CONCEPTS_PRESENT 902