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 <tbb/concurrent_hash_map.h> 34 #include <tbb/parallel_for.h> 35 #include <common/concurrent_associative_common.h> 36 #include <vector> 37 #include <list> 38 #include <algorithm> 39 #include <functional> 40 #include <scoped_allocator> 41 42 //! \file test_concurrent_hash_map.cpp 43 //! \brief Test for [containers.concurrent_hash_map containers.tbb_hash_compare] specification 44 45 void TestRangeBasedFor(){ 46 using namespace range_based_for_support_tests; 47 48 INFO("testing range based for loop compatibility \n"); 49 using ch_map = tbb::concurrent_hash_map<int,int>; 50 ch_map a_ch_map; 51 52 const int sequence_length = 100; 53 for (int i = 1; i <= sequence_length; ++i){ 54 a_ch_map.insert(ch_map::value_type(i,i)); 55 } 56 57 REQUIRE_MESSAGE((range_based_for_accumulate(a_ch_map, pair_second_summer(), 0) == gauss_summ_of_int_sequence(sequence_length)), 58 "incorrect accumulated value generated via range based for ?"); 59 } 60 61 // The helper to run a test only when a default construction is present. 62 template <bool default_construction_present> struct do_default_construction_test { 63 template<typename FuncType> void operator() ( FuncType func ) const { func(); } 64 }; 65 66 template <> struct do_default_construction_test<false> { 67 template<typename FuncType> void operator()( FuncType ) const {} 68 }; 69 70 template <typename Table> 71 class test_insert_by_key { 72 using value_type = typename Table::value_type; 73 Table &my_c; 74 const value_type &my_value; 75 public: 76 test_insert_by_key( Table &c, const value_type &value ) : my_c(c), my_value(value) {} 77 void operator()() const { 78 { 79 typename Table::accessor a; 80 CHECK(my_c.insert( a, my_value.first )); 81 CHECK(utils::IsEqual()(a->first, my_value.first)); 82 a->second = my_value.second; 83 } 84 { 85 typename Table::const_accessor ca; 86 CHECK(!my_c.insert( ca, my_value.first )); 87 CHECK(utils::IsEqual()(ca->first, my_value.first)); 88 CHECK(utils::IsEqual()(ca->second, my_value.second)); 89 } 90 } 91 }; 92 93 template <typename Table, typename Iterator, typename Range = typename Table::range_type> 94 class test_range { 95 using value_type = typename Table::value_type; 96 Table &my_c; 97 const std::list<value_type> &my_lst; 98 std::vector<detail::atomic_type<bool>>& my_marks; 99 public: 100 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) { 101 for (std::size_t i = 0; i < my_marks.size(); ++i) { 102 my_marks[i].store(false, std::memory_order_relaxed); 103 } 104 } 105 106 void operator()( const Range &r ) const { do_test_range( r.begin(), r.end() ); } 107 void do_test_range( Iterator i, Iterator j ) const { 108 for ( Iterator it = i; it != j; ) { 109 Iterator it_prev = it++; 110 typename std::list<value_type>::const_iterator it2 = std::search( my_lst.begin(), my_lst.end(), it_prev, it, utils::IsEqual() ); 111 CHECK(it2 != my_lst.end()); 112 typename std::list<value_type>::difference_type dist = std::distance( my_lst.begin(), it2 ); 113 CHECK(!my_marks[dist]); 114 my_marks[dist].store(true); 115 } 116 } 117 }; 118 119 template <bool default_construction_present, typename Table> 120 class check_value { 121 using const_iterator = typename Table::const_iterator; 122 using iterator = typename Table::iterator; 123 using size_type = typename Table::size_type; 124 Table &my_c; 125 public: 126 check_value( Table &c ) : my_c(c) {} 127 void operator()(const typename Table::value_type &value ) { 128 const Table &const_c = my_c; 129 CHECK(my_c.count( value.first ) == 1); 130 { // tests with a const accessor. 131 typename Table::const_accessor ca; 132 // find 133 CHECK(my_c.find( ca, value.first )); 134 CHECK(!ca.empty() ); 135 CHECK(utils::IsEqual()(ca->first, value.first)); 136 CHECK(utils::IsEqual()(ca->second, value.second)); 137 // erase 138 CHECK(my_c.erase( ca )); 139 CHECK(my_c.count( value.first ) == 0); 140 // insert (pair) 141 CHECK(my_c.insert( ca, value )); 142 CHECK(utils::IsEqual()(ca->first, value.first)); 143 CHECK(utils::IsEqual()(ca->second, value.second)); 144 } { // tests with a non-const accessor. 145 typename Table::accessor a; 146 // find 147 CHECK(my_c.find( a, value.first )); 148 CHECK(!a.empty() ); 149 CHECK(utils::IsEqual()(a->first, value.first)); 150 CHECK(utils::IsEqual()(a->second, value.second)); 151 // erase 152 CHECK(my_c.erase( a )); 153 CHECK(my_c.count( value.first ) == 0); 154 // insert 155 CHECK(my_c.insert( a, value )); 156 CHECK(utils::IsEqual()(a->first, value.first)); 157 CHECK(utils::IsEqual()(a->second, value.second)); 158 } 159 // erase by key 160 CHECK(my_c.erase( value.first )); 161 CHECK(my_c.count( value.first ) == 0); 162 do_default_construction_test<default_construction_present>()(test_insert_by_key<Table>( my_c, value )); 163 // insert by value 164 CHECK(my_c.insert( value ) != default_construction_present); 165 // equal_range 166 std::pair<iterator,iterator> r1 = my_c.equal_range( value.first ); 167 iterator r1_first_prev = r1.first++; 168 CHECK((utils::IsEqual()( *r1_first_prev, value ) && utils::IsEqual()( r1.first, r1.second ))); 169 std::pair<const_iterator,const_iterator> r2 = const_c.equal_range( value.first ); 170 const_iterator r2_first_prev = r2.first++; 171 CHECK((utils::IsEqual()( *r2_first_prev, value ) && utils::IsEqual()( r2.first, r2.second ))); 172 } 173 }; 174 175 template <typename Value, typename U = Value> 176 struct CompareTables { 177 template <typename T> 178 static bool IsEqual( const T& t1, const T& t2 ) { 179 return (t1 == t2) && !(t1 != t2); 180 } 181 }; 182 183 template <typename U> 184 struct CompareTables< std::pair<const std::weak_ptr<U>, std::weak_ptr<U> > > { 185 template <typename T> 186 static bool IsEqual( const T&, const T& ) { 187 /* do nothing for std::weak_ptr */ 188 return true; 189 } 190 }; 191 192 template <bool default_construction_present, typename Table> 193 void Examine( Table c, const std::list<typename Table::value_type> &lst) { 194 using const_table = const Table; 195 using const_iterator = typename Table::const_iterator; 196 using iterator = typename Table::iterator; 197 using value_type = typename Table::value_type; 198 using size_type = typename Table::size_type; 199 200 CHECK(!c.empty()); 201 CHECK(c.size() == lst.size()); 202 CHECK(c.max_size() >= c.size()); 203 204 const check_value<default_construction_present, Table> cv(c); 205 std::for_each( lst.begin(), lst.end(), cv ); 206 207 std::vector<detail::atomic_type<bool>> marks( lst.size() ); 208 209 test_range<Table,iterator>( c, lst, marks ).do_test_range( c.begin(), c.end() ); 210 CHECK(std::find( marks.begin(), marks.end(), false ) == marks.end()); 211 212 test_range<const_table,const_iterator>( c, lst, marks ).do_test_range( c.begin(), c.end() ); 213 CHECK(std::find( marks.begin(), marks.end(), false ) == marks.end()); 214 215 using range_type = typename Table::range_type; 216 tbb::parallel_for( c.range(), test_range<Table,typename range_type::iterator,range_type>( c, lst, marks ) ); 217 CHECK(std::find( marks.begin(), marks.end(), false ) == marks.end()); 218 219 const_table const_c = c; 220 CHECK(CompareTables<value_type>::IsEqual( c, const_c )); 221 222 const size_type new_bucket_count = 2*c.bucket_count(); 223 c.rehash( new_bucket_count ); 224 CHECK(c.bucket_count() >= new_bucket_count); 225 226 Table c2; 227 typename std::list<value_type>::const_iterator begin5 = lst.begin(); 228 std::advance( begin5, 5 ); 229 c2.insert( lst.begin(), begin5 ); 230 std::for_each( lst.begin(), begin5, check_value<default_construction_present, Table>( c2 ) ); 231 232 c2.swap( c ); 233 CHECK(CompareTables<value_type>::IsEqual( c2, const_c )); 234 CHECK(c.size() == 5); 235 std::for_each( lst.begin(), lst.end(), check_value<default_construction_present,Table>(c2) ); 236 237 swap( c, c2 ); 238 CHECK(CompareTables<value_type>::IsEqual( c, const_c )); 239 CHECK(c2.size() == 5); 240 241 c2.clear(); 242 CHECK(CompareTables<value_type>::IsEqual( c2, Table() )); 243 244 typename Table::allocator_type a = c.get_allocator(); 245 value_type *ptr = a.allocate(1); 246 CHECK(ptr); 247 a.deallocate( ptr, 1 ); 248 } 249 250 template <typename T> 251 struct debug_hash_compare : public tbb::detail::d1::tbb_hash_compare<T> {}; 252 253 template <bool default_construction_present, typename Value> 254 void TypeTester( const std::list<Value> &lst ) { 255 using first_type = typename Value::first_type; 256 using key_type = typename std::remove_const<first_type>::type; 257 using second_type = typename Value::second_type; 258 using ch_map = tbb::concurrent_hash_map<key_type, second_type>; 259 debug_hash_compare<key_type> compare{}; 260 // Construct an empty hash map. 261 ch_map c1; 262 c1.insert( lst.begin(), lst.end() ); 263 Examine<default_construction_present>( c1, lst ); 264 265 // Constructor from initializer_list. 266 typename std::list<Value>::const_iterator it = lst.begin(); 267 std::initializer_list<Value> il = { *it++, *it++, *it++ }; 268 ch_map c2( il ); 269 c2.insert( it, lst.end() ); 270 Examine<default_construction_present>( c2, lst ); 271 272 // Constructor from initializer_list and compare object 273 ch_map c3( il, compare); 274 c3.insert( it, lst.end() ); 275 Examine<default_construction_present>( c3, lst ); 276 277 // Constructor from initializer_list, compare object and allocator 278 ch_map c4( il, compare, typename ch_map::allocator_type()); 279 c4.insert( it, lst.end()); 280 Examine<default_construction_present>( c4, lst ); 281 282 // Copying constructor. 283 ch_map c5(c1); 284 Examine<default_construction_present>( c5, lst ); 285 // Construct with non-default allocator 286 using ch_map_debug_alloc = tbb::concurrent_hash_map<key_type, second_type, 287 tbb::detail::d1::tbb_hash_compare<key_type>, 288 LocalCountingAllocator<std::allocator<Value>>>; 289 ch_map_debug_alloc c6; 290 c6.insert( lst.begin(), lst.end() ); 291 Examine<default_construction_present>( c6, lst ); 292 // Copying constructor 293 ch_map_debug_alloc c7(c6); 294 Examine<default_construction_present>( c7, lst ); 295 // Construction empty table with n preallocated buckets. 296 ch_map c8( lst.size() ); 297 c8.insert( lst.begin(), lst.end() ); 298 Examine<default_construction_present>( c8, lst ); 299 ch_map_debug_alloc c9( lst.size() ); 300 c9.insert( lst.begin(), lst.end() ); 301 Examine<default_construction_present>( c9, lst ); 302 // Construction with copying iteration range. 303 ch_map c10_1( c1.begin(), c1.end() ), c10_2(c1.cbegin(), c1.cend()); 304 Examine<default_construction_present>( c10_1, lst ); 305 Examine<default_construction_present>( c10_2, lst ); 306 // Construction with copying iteration range and given allocator instance. 307 LocalCountingAllocator<std::allocator<Value>> allocator; 308 ch_map_debug_alloc c11( lst.begin(), lst.end(), allocator ); 309 Examine<default_construction_present>( c11, lst ); 310 311 using ch_map_debug_hash = tbb::concurrent_hash_map<key_type, second_type, 312 debug_hash_compare<key_type>, 313 typename ch_map::allocator_type>; 314 315 // Constructor with two iterators and hash_compare 316 ch_map_debug_hash c12(c1.begin(), c1.end(), compare); 317 Examine<default_construction_present>( c12, lst ); 318 319 ch_map_debug_hash c13(c1.begin(), c1.end(), compare, typename ch_map::allocator_type()); 320 Examine<default_construction_present>( c13, lst ); 321 } 322 323 void TestSpecificTypes() { 324 const int NUMBER = 10; 325 326 using int_int_t = std::pair<const int, int>; 327 std::list<int_int_t> arrIntInt; 328 for ( int i=0; i<NUMBER; ++i ) arrIntInt.push_back( int_int_t(i, NUMBER-i) ); 329 TypeTester</*default_construction_present = */true>( arrIntInt ); 330 331 using ref_int_t = std::pair<const std::reference_wrapper<const int>, int>; 332 std::list<ref_int_t> arrRefInt; 333 for ( std::list<int_int_t>::iterator it = arrIntInt.begin(); it != arrIntInt.end(); ++it ) 334 arrRefInt.push_back( ref_int_t( it->first, it->second ) ); 335 TypeTester</*default_construction_present = */true>( arrRefInt ); 336 337 using int_ref_t = std::pair< const int, std::reference_wrapper<int> >; 338 std::list<int_ref_t> arrIntRef; 339 for ( std::list<int_int_t>::iterator it = arrIntInt.begin(); it != arrIntInt.end(); ++it ) 340 arrIntRef.push_back( int_ref_t( it->first, it->second ) ); 341 TypeTester</*default_construction_present = */false>( arrIntRef ); 342 343 using shr_shr_t = std::pair< const std::shared_ptr<int>, std::shared_ptr<int> >; 344 std::list<shr_shr_t> arrShrShr; 345 for ( int i=0; i<NUMBER; ++i ) { 346 const int NUMBER_minus_i = NUMBER - i; 347 arrShrShr.push_back( shr_shr_t( std::make_shared<int>(i), std::make_shared<int>(NUMBER_minus_i) ) ); 348 } 349 TypeTester< /*default_construction_present = */true>( arrShrShr ); 350 351 using wk_wk_t = std::pair< const std::weak_ptr<int>, std::weak_ptr<int> >; 352 std::list< wk_wk_t > arrWkWk; 353 std::copy( arrShrShr.begin(), arrShrShr.end(), std::back_inserter(arrWkWk) ); 354 TypeTester< /*default_construction_present = */true>( arrWkWk ); 355 356 // Check working with deprecated hashers 357 using pair_key_type = std::pair<int, int>; 358 using pair_int_t = std::pair<const pair_key_type, int>; 359 std::list<pair_int_t> arr_pair_int; 360 for (int i = 0; i < NUMBER; ++i) { 361 arr_pair_int.push_back(pair_int_t(pair_key_type{i, i}, i)); 362 } 363 TypeTester</*default_construction_present = */true>(arr_pair_int); 364 365 using tbb_string_key_type = std::basic_string<char, std::char_traits<char>, tbb::tbb_allocator<char>>; 366 using pair_tbb_string_int_t = std::pair<const tbb_string_key_type, int>; 367 std::list<pair_tbb_string_int_t> arr_pair_string_int; 368 for (int i = 0; i < NUMBER; ++i) { 369 tbb_string_key_type key(i, char(i)); 370 arr_pair_string_int.push_back(pair_tbb_string_int_t(key, i)); 371 } 372 TypeTester</*default_construction_present = */true>(arr_pair_string_int); 373 } 374 375 struct custom_hash_compare { 376 template<typename Allocator> 377 size_t hash(const AllocatorAwareData<Allocator>& key) const { 378 return my_hash_compare.hash(key.value()); 379 } 380 381 template<typename Allocator> 382 bool equal(const AllocatorAwareData<Allocator>& key1, const AllocatorAwareData<Allocator>& key2) const { 383 return my_hash_compare.equal(key1.value(), key2.value()); 384 } 385 386 private: 387 tbb::tbb_hash_compare<int> my_hash_compare; 388 }; 389 390 void TestScopedAllocator() { 391 using allocator_data_type = AllocatorAwareData<std::scoped_allocator_adaptor<tbb::tbb_allocator<int>>>; 392 using allocator_type = std::scoped_allocator_adaptor<tbb::tbb_allocator<std::pair<const allocator_data_type, allocator_data_type>>>; 393 using hash_map_type = tbb::concurrent_hash_map<allocator_data_type, allocator_data_type, 394 custom_hash_compare, allocator_type>; 395 396 allocator_type allocator; 397 allocator_data_type key1(1, allocator), key2(2, allocator); 398 allocator_data_type data1(1, allocator), data2(data1, allocator); 399 hash_map_type map1(allocator), map2(allocator); 400 401 hash_map_type::value_type v1(key1, data1), v2(key2, data2); 402 403 auto init_list = { v1, v2 }; 404 405 allocator_data_type::assert_on_constructions = true; 406 map1.emplace(key1, data1); 407 map2.emplace(key2, std::move(data2)); 408 409 map1.clear(); 410 map2.clear(); 411 412 map1.insert(v1); 413 map2.insert(std::move(v2)); 414 415 map1.clear(); 416 map2.clear(); 417 418 map1.insert(init_list); 419 420 map1.clear(); 421 map2.clear(); 422 423 hash_map_type::accessor a; 424 map2.insert(a, allocator_data_type(3)); 425 a.release(); 426 427 map1 = map2; 428 map2 = std::move(map1); 429 430 hash_map_type map3(allocator); 431 map3.rehash(1000); 432 map3 = map2; 433 } 434 435 // A test for undocumented member function internal_fast_find 436 // which is declared protected in concurrent_hash_map for internal TBB use 437 void TestInternalFastFind() { 438 typedef tbb::concurrent_hash_map<int, int> basic_chmap_type; 439 typedef basic_chmap_type::const_pointer const_pointer; 440 441 class chmap : public basic_chmap_type { 442 public: 443 chmap() : basic_chmap_type() {} 444 445 using basic_chmap_type::internal_fast_find; 446 }; 447 448 chmap m; 449 int sz = 100; 450 451 for (int i = 0; i != sz; ++i) { 452 m.insert(std::make_pair(i, i * i)); 453 } 454 REQUIRE_MESSAGE(m.size() == 100, "Incorrect concurrent_hash_map size"); 455 456 for (int i = 0; i != sz; ++i) { 457 const_pointer res = m.internal_fast_find(i); 458 REQUIRE_MESSAGE(res != nullptr, "Incorrect internal_fast_find return value for existing key"); 459 basic_chmap_type::value_type val = *res; 460 REQUIRE_MESSAGE(val.first == i, "Incorrect key in internal_fast_find return value"); 461 REQUIRE_MESSAGE(val.second == i * i, "Incorrect mapped in internal_fast_find return value"); 462 } 463 464 for (int i = sz; i != 2 * sz; ++i) { 465 const_pointer res = m.internal_fast_find(i); 466 REQUIRE_MESSAGE(res == nullptr, "Incorrect internal_fast_find return value for not existing key"); 467 } 468 } 469 470 struct default_container_traits { 471 template <typename container_type, typename iterator_type> 472 static container_type& construct_container(typename std::aligned_storage<sizeof(container_type)>::type& storage, iterator_type begin, iterator_type end){ 473 container_type* ptr = reinterpret_cast<container_type*>(&storage); 474 new (ptr) container_type(begin, end); 475 return *ptr; 476 } 477 478 template <typename container_type, typename iterator_type, typename allocator_type> 479 static container_type& construct_container(typename std::aligned_storage<sizeof(container_type)>::type& storage, iterator_type begin, iterator_type end, allocator_type const& a){ 480 container_type* ptr = reinterpret_cast<container_type*>(&storage); 481 new (ptr) container_type(begin, end, a); 482 return *ptr; 483 } 484 }; 485 486 struct hash_map_traits : default_container_traits { 487 enum{ expected_number_of_items_to_allocate_for_steal_move = 0 }; 488 489 template<typename T> 490 struct hash_compare { 491 bool equal( const T& lhs, const T& rhs ) const { 492 return lhs==rhs; 493 } 494 size_t hash( const T& k ) const { 495 return my_hash_func(k); 496 } 497 std::hash<T> my_hash_func; 498 }; 499 500 template <typename T, typename Allocator> 501 using container_type = tbb::concurrent_hash_map<T, T, hash_compare<T>, Allocator>; 502 503 template <typename T> 504 using container_value_type = std::pair<const T, T>; 505 506 template<typename element_type, typename allocator_type> 507 struct apply { 508 using type = tbb::concurrent_hash_map<element_type, element_type, hash_compare<element_type>, allocator_type>; 509 }; 510 511 using init_iterator_type = move_support_tests::FooPairIterator; 512 template <typename hash_map_type, typename iterator> 513 static bool equal(hash_map_type const& c, iterator begin, iterator end){ 514 bool equal_sizes = ( static_cast<size_t>(std::distance(begin, end)) == c.size() ); 515 if (!equal_sizes) 516 return false; 517 518 for (iterator it = begin; it != end; ++it ){ 519 if (c.count( (*it).first) == 0){ 520 return false; 521 } 522 } 523 return true; 524 } 525 }; 526 527 template <bool IsConstructible> 528 class HeterogeneousKey { 529 public: 530 static std::size_t heterogeneous_keys_count; 531 532 int integer_key() const { return my_key; } 533 534 template <bool I = IsConstructible, typename = typename std::enable_if<I>::type> 535 HeterogeneousKey(int key) : my_key(key) { ++heterogeneous_keys_count; } 536 537 HeterogeneousKey(const HeterogeneousKey&) = delete; 538 HeterogeneousKey& operator=(const HeterogeneousKey&) = delete; 539 540 static void reset() { heterogeneous_keys_count = 0; } 541 542 struct construct_flag {}; 543 544 HeterogeneousKey( construct_flag, int key ) : my_key(key) {} 545 546 private: 547 int my_key; 548 }; // class HeterogeneousKey 549 550 template <bool IsConstructible> 551 std::size_t HeterogeneousKey<IsConstructible>::heterogeneous_keys_count = 0; 552 553 struct HeterogeneousHashCompare { 554 using is_transparent = void; 555 556 template <bool IsConstructible> 557 std::size_t hash( const HeterogeneousKey<IsConstructible>& key ) const { 558 return my_hash_object(key.integer_key()); 559 } 560 561 std::size_t hash( const int& key ) const { 562 return my_hash_object(key); 563 } 564 565 bool equal( const int& key1, const int& key2 ) const { 566 return key1 == key2; 567 } 568 569 template <bool IsConstructible> 570 bool equal( const int& key1, const HeterogeneousKey<IsConstructible>& key2 ) const { 571 return key1 == key2.integer_key(); 572 } 573 574 template <bool IsConstructible> 575 bool equal( const HeterogeneousKey<IsConstructible>& key1, const int& key2 ) const { 576 return key1.integer_key() == key2; 577 } 578 579 template <bool IsConstructible> 580 bool equal( const HeterogeneousKey<IsConstructible>& key1, const HeterogeneousKey<IsConstructible>& key2 ) const { 581 return key1.integer_key() == key2.integer_key(); 582 } 583 584 std::hash<int> my_hash_object; 585 }; // struct HeterogeneousHashCompare 586 587 class DefaultConstructibleValue { 588 public: 589 DefaultConstructibleValue() : my_i(default_value) {}; 590 591 int value() const { return my_i; } 592 static constexpr int default_value = -4242; 593 private: 594 int my_i; 595 }; // class DefaultConstructibleValue 596 597 constexpr int DefaultConstructibleValue::default_value; 598 599 void test_heterogeneous_find() { 600 using key_type = HeterogeneousKey</*IsConstructible = */false>; 601 using chmap_type = tbb::concurrent_hash_map<key_type, int, HeterogeneousHashCompare>; 602 603 chmap_type chmap; 604 using const_accessor = typename chmap_type::const_accessor; 605 using accessor = typename chmap_type::accessor; 606 const_accessor cacc; 607 accessor acc; 608 609 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Incorrect test setup"); 610 611 key_type key(key_type::construct_flag{}, 1); 612 bool regular_result = chmap.find(cacc, key); 613 bool heterogeneous_result = chmap.find(cacc, int(1)); 614 615 REQUIRE(!regular_result); 616 REQUIRE_MESSAGE(regular_result == heterogeneous_result, 617 "Incorrect heterogeneous find result with const_accessor (no element)"); 618 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during find call with const_accessor (no element)"); 619 620 regular_result = chmap.find(acc, key); 621 heterogeneous_result = chmap.find(acc, int(1)); 622 623 REQUIRE(!regular_result); 624 REQUIRE_MESSAGE(regular_result == heterogeneous_result, 625 "Incorrect heterogeneous find result with accessor (no element)"); 626 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during find call with accessor (no element)"); 627 628 bool tmp_result = chmap.emplace(cacc, std::piecewise_construct, 629 std::forward_as_tuple(key_type::construct_flag{}, 1), std::forward_as_tuple(100)); 630 REQUIRE(tmp_result); 631 632 regular_result = chmap.find(cacc, key); 633 heterogeneous_result = chmap.find(cacc, int(1)); 634 635 REQUIRE(regular_result); 636 REQUIRE_MESSAGE(regular_result == heterogeneous_result, "Incorrect heterogeneous find result with const_accessor (element exists)"); 637 REQUIRE_MESSAGE(cacc->first.integer_key() == 1, "Incorrect accessor returned"); 638 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during find call with const_accessor (element exists)"); 639 cacc.release(); 640 641 regular_result = chmap.find(acc, key); 642 heterogeneous_result = chmap.find(acc, int(1)); 643 644 REQUIRE(regular_result); 645 REQUIRE_MESSAGE(regular_result == heterogeneous_result, "Incorrect heterogeneous find result with accessor (element exists)"); 646 REQUIRE_MESSAGE(acc->first.integer_key() == 1, "Incorrect accessor returned"); 647 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during find call with accessor (element exists)"); 648 key_type::reset(); 649 } 650 651 void test_heterogeneous_count() { 652 using key_type = HeterogeneousKey</*IsConstructible = */false>; 653 using chmap_type = tbb::concurrent_hash_map<key_type, int, HeterogeneousHashCompare>; 654 655 chmap_type chmap; 656 657 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Incorrect test setup"); 658 key_type key(key_type::construct_flag{}, 1); 659 660 typename chmap_type::size_type regular_count = chmap.count(key); 661 typename chmap_type::size_type heterogeneous_count = chmap.count(int(1)); 662 663 REQUIRE(regular_count == 0); 664 REQUIRE_MESSAGE(regular_count == heterogeneous_count, "Incorrect heterogeneous count result (no element)"); 665 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during count call (no element)"); 666 667 chmap.emplace(std::piecewise_construct, std::forward_as_tuple(key_type::construct_flag{}, 1), std::forward_as_tuple(100)); 668 669 regular_count = chmap.count(key); 670 heterogeneous_count = chmap.count(int(1)); 671 672 REQUIRE(regular_count == 1); 673 REQUIRE_MESSAGE(regular_count == heterogeneous_count, "Incorrect heterogeneous count result (element exists)"); 674 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during count call (element exists)"); 675 key_type::reset(); 676 } 677 678 void test_heterogeneous_equal_range() { 679 using key_type = HeterogeneousKey</*IsConstructible = */false>; 680 using chmap_type = tbb::concurrent_hash_map<key_type, int, HeterogeneousHashCompare>; 681 682 chmap_type chmap; 683 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Incorrect test setup"); 684 685 using iterator = typename chmap_type::iterator; 686 using const_iterator = typename chmap_type::const_iterator; 687 using result = std::pair<iterator, iterator>; 688 using const_result = std::pair<const_iterator, const_iterator>; 689 key_type key(key_type::construct_flag{}, 1); 690 691 result regular_result = chmap.equal_range(key); 692 result heterogeneous_result = chmap.equal_range(int(1)); 693 694 REQUIRE(regular_result.first == chmap.end()); 695 REQUIRE(regular_result.second == chmap.end()); 696 REQUIRE_MESSAGE(regular_result == heterogeneous_result, "Incorrect heterogeneous equal_range result (non const, no element)"); 697 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during equal_range call (non const, no element)"); 698 699 const chmap_type& cchmap = chmap; 700 701 const_result regular_const_result = cchmap.equal_range(key); 702 const_result heterogeneous_const_result = cchmap.equal_range(int(1)); 703 704 REQUIRE(regular_const_result.first == cchmap.end()); 705 REQUIRE(regular_const_result.second == cchmap.end()); 706 REQUIRE_MESSAGE(regular_const_result == heterogeneous_const_result, 707 "Incorrect heterogeneous equal_range result (const, no element)"); 708 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during equal_range call (const, no element)"); 709 710 chmap.emplace(std::piecewise_construct, std::forward_as_tuple(key_type::construct_flag{}, 1), std::forward_as_tuple(100)); 711 712 regular_result = chmap.equal_range(key); 713 heterogeneous_result = chmap.equal_range(int(1)); 714 715 REQUIRE(regular_result.first != chmap.end()); 716 REQUIRE(regular_result.first->first.integer_key() == 1); 717 REQUIRE(regular_result.second == chmap.end()); 718 REQUIRE_MESSAGE(regular_result == heterogeneous_result, "Incorrect heterogeneous equal_range result (non const, element exists)"); 719 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during equal_range call (non const, element exists)"); 720 721 regular_const_result = cchmap.equal_range(key); 722 heterogeneous_const_result = cchmap.equal_range(int(1)); 723 REQUIRE_MESSAGE(regular_const_result == heterogeneous_const_result, 724 "Incorrect heterogeneous equal_range result (const, element exists)"); 725 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Temporary key object was created during equal_range call (const, element exists)"); 726 key_type::reset(); 727 } 728 729 void test_heterogeneous_insert() { 730 using key_type = HeterogeneousKey</*IsConstructible = */true>; 731 using chmap_type = tbb::concurrent_hash_map<key_type, DefaultConstructibleValue, HeterogeneousHashCompare>; 732 733 chmap_type chmap; 734 using const_accessor = typename chmap_type::const_accessor; 735 using accessor = typename chmap_type::accessor; 736 const_accessor cacc; 737 accessor acc; 738 739 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Incorrect test setup"); 740 741 bool result = chmap.insert(cacc, int(1)); 742 743 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 1, "Only one heterogeneous key should be created"); 744 REQUIRE_MESSAGE(result, "Incorrect heterogeneous insert result (const_accessor)"); 745 REQUIRE_MESSAGE(cacc->first.integer_key() == 1, "Incorrect accessor"); 746 REQUIRE_MESSAGE(cacc->second.value() == DefaultConstructibleValue::default_value, "Value should be default constructed"); 747 748 result = chmap.insert(cacc, int(1)); 749 750 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 1, "No extra keys should be created"); 751 REQUIRE_MESSAGE(!result, "Incorrect heterogeneous insert result (const_accessor)"); 752 REQUIRE_MESSAGE(cacc->first.integer_key() == 1, "Incorrect accessor"); 753 REQUIRE_MESSAGE(cacc->second.value() == DefaultConstructibleValue::default_value, "Value should be default constructed"); 754 755 result = chmap.insert(acc, int(2)); 756 757 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 2, "Only one extra heterogeneous key should be created"); 758 REQUIRE_MESSAGE(result, "Incorrect heterogeneous insert result (accessor)"); 759 REQUIRE_MESSAGE(acc->first.integer_key() == 2, "Incorrect accessor"); 760 REQUIRE_MESSAGE(acc->second.value() == DefaultConstructibleValue::default_value, "Value should be default constructed"); 761 762 result = chmap.insert(acc, int(2)); 763 764 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 2, "No extra keys should be created"); 765 REQUIRE_MESSAGE(!result, "Incorrect heterogeneous insert result (accessor)"); 766 REQUIRE_MESSAGE(acc->first.integer_key() == 2, "Incorrect accessor"); 767 REQUIRE_MESSAGE(acc->second.value() == DefaultConstructibleValue::default_value, "Value should be default constructed"); 768 769 key_type::reset(); 770 } 771 772 void test_heterogeneous_erase() { 773 using key_type = HeterogeneousKey</*IsConstructible = */false>; 774 using chmap_type = tbb::concurrent_hash_map<key_type, int, HeterogeneousHashCompare>; 775 776 chmap_type chmap; 777 778 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "Incorrect test setup"); 779 780 chmap.emplace(std::piecewise_construct, std::forward_as_tuple(key_type::construct_flag{}, 1), std::forward_as_tuple(100)); 781 chmap.emplace(std::piecewise_construct, std::forward_as_tuple(key_type::construct_flag{}, 2), std::forward_as_tuple(200)); 782 783 typename chmap_type::const_accessor cacc; 784 785 REQUIRE(chmap.find(cacc, int(1))); 786 REQUIRE(chmap.find(cacc, int(2))); 787 788 cacc.release(); 789 790 bool result = chmap.erase(int(1)); 791 REQUIRE_MESSAGE(result, "Erasure should be successful"); 792 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "No extra keys should be created"); 793 REQUIRE_MESSAGE(!chmap.find(cacc, int(1)), "Element was not erased"); 794 795 796 result = chmap.erase(int(1)); 797 REQUIRE_MESSAGE(!result, "Erasure should fail"); 798 REQUIRE_MESSAGE(key_type::heterogeneous_keys_count == 0, "No extra keys should be created"); 799 key_type::reset(); 800 } 801 802 void test_heterogeneous_lookup() { 803 test_heterogeneous_find(); 804 test_heterogeneous_count(); 805 test_heterogeneous_equal_range(); 806 } 807 808 //! Test of insert operation 809 //! \brief \ref error_guessing 810 TEST_CASE("testing range based for support"){ 811 TestRangeBasedFor(); 812 } 813 814 //! Test concurrent_hash_map with specific key/mapped types 815 //! \brief \ref regression \ref error_guessing 816 TEST_CASE("testing concurrent_hash_map with specific key/mapped types") { 817 TestSpecificTypes(); 818 } 819 820 //! Test work with scoped allocator 821 //! \brief \ref regression 822 TEST_CASE("testing work with scoped allocator") { 823 TestScopedAllocator(); 824 } 825 826 //! Test internal fast find for concurrent_hash_map 827 //! \brief \ref regression 828 TEST_CASE("testing internal fast find for concurrent_hash_map") { 829 TestInternalFastFind(); 830 } 831 832 //! Test constructor with move iterators 833 //! \brief \ref error_guessing 834 TEST_CASE("testing constructor with move iterators"){ 835 move_support_tests::test_constructor_with_move_iterators<hash_map_traits>(); 836 } 837 838 #if TBB_USE_EXCEPTIONS 839 //! Test exception in constructors 840 //! \brief \ref regression \ref error_guessing 841 TEST_CASE("Test exception in constructors") { 842 using allocator_type = StaticSharedCountingAllocator<std::allocator<std::pair<const int, int>>>; 843 using map_type = tbb::concurrent_hash_map<int, int, tbb::tbb_hash_compare<int>, allocator_type>; 844 845 auto init_list = {std::pair<const int, int>(1, 42), std::pair<const int, int>(2, 42), std::pair<const int, int>(3, 42), 846 std::pair<const int, int>(4, 42), std::pair<const int, int>(5, 42), std::pair<const int, int>(6, 42)}; 847 map_type map(init_list); 848 849 allocator_type::set_limits(1); 850 REQUIRE_THROWS_AS( [&] { 851 map_type map1(map); 852 utils::suppress_unused_warning(map1); 853 }(), const std::bad_alloc); 854 855 REQUIRE_THROWS_AS( [&] { 856 map_type map2(init_list.begin(), init_list.end()); 857 utils::suppress_unused_warning(map2); 858 }(), const std::bad_alloc); 859 860 tbb::tbb_hash_compare<int> test_hash; 861 862 REQUIRE_THROWS_AS( [&] { 863 map_type map3(init_list.begin(), init_list.end(), test_hash); 864 utils::suppress_unused_warning(map3); 865 }(), const std::bad_alloc); 866 867 REQUIRE_THROWS_AS( [&] { 868 map_type map4(init_list, test_hash); 869 utils::suppress_unused_warning(map4); 870 }(), const std::bad_alloc); 871 872 REQUIRE_THROWS_AS( [&] { 873 map_type map5(init_list); 874 utils::suppress_unused_warning(map5); 875 }(), const std::bad_alloc); 876 877 allocator_type::set_limits(0); 878 map_type big_map{}; 879 for (std::size_t i = 0; i < 1000; ++i) { 880 big_map.insert(std::pair<const int, int>(i, 42)); 881 } 882 883 allocator_type::init_counters(); 884 allocator_type::set_limits(300); 885 REQUIRE_THROWS_AS( [&] { 886 map_type map6(big_map); 887 utils::suppress_unused_warning(map6); 888 }(), const std::bad_alloc); 889 } 890 #endif // TBB_USE_EXCEPTIONS 891 892 //! \brief \ref error_guessing 893 TEST_CASE("swap with NotAlwaysEqualAllocator allocators"){ 894 using allocator_type = NotAlwaysEqualAllocator<std::pair<const int, int>>; 895 using map_type = tbb::concurrent_hash_map<int, int, tbb::tbb_hash_compare<int>, allocator_type>; 896 897 map_type map1{}; 898 map_type map2({{42, 42}, {24, 42}}); 899 map_type map3(map2); 900 901 swap(map1, map2); 902 903 CHECK(map2.empty()); 904 CHECK(map1 == map3); 905 } 906 907 //! \brief \ref error_guessing 908 TEST_CASE("test concurrent_hash_map heterogeneous lookup") { 909 test_heterogeneous_lookup(); 910 } 911 912 //! \brief \ref error_guessing 913 TEST_CASE("test concurrent_hash_map heterogeneous insert") { 914 test_heterogeneous_insert(); 915 } 916 917 //! \brief \ref error_guessing 918 TEST_CASE("test concurrent_hash_map heterogeneous erase") { 919 test_heterogeneous_erase(); 920 } 921