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