1/*
2 Copyright (c) 2005-2019 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#ifndef TBB_USE_PERFORMANCE_WARNINGS
18#define TBB_USE_PERFORMANCE_WARNINGS 1
19#endif
20
21// Our tests usually include the header under test first. But this test needs
22// to use the preprocessor to edit the identifier runtime_warning in concurrent_hash_map.h.
23// Hence we include a few other headers before doing the abusive edit.
24#include "tbb/tbb_stddef.h" /* Defines runtime_warning */
25#include "harness_assert.h" /* Prerequisite for defining hooked_warning */
26
27// The symbol internal::runtime_warning is normally an entry point into the TBB library.
28// Here for sake of testing, we define it to be hooked_warning, a routine peculiar to this unit test.
29#define runtime_warning hooked_warning
30
31static bool bad_hashing = false;
32
33namespace tbb {
34 namespace internal {
35 static void hooked_warning( const char* /*format*/, ... ) {
36 ASSERT(bad_hashing, "unexpected runtime_warning: bad hashing");
37 }
38 } // namespace internal
39} // namespace tbb
40#define __TBB_EXTRA_DEBUG 1 // enables additional checks
41#include "tbb/concurrent_hash_map.h"
42
43// Restore runtime_warning as an entry point into the TBB library.
44#undef runtime_warning
45
46namespace Jungle {
47 struct Tiger {};
48 size_t tbb_hasher( const Tiger& ) {return 0;}
49}
50
51#if !defined(_MSC_VER) || _MSC_VER>=1400 || __INTEL_COMPILER
52void test_ADL() {
53 tbb::tbb_hash_compare<Jungle::Tiger>::hash(Jungle::Tiger()); // Instantiation chain finds tbb_hasher via Argument Dependent Lookup
54}
55#endif
56
57struct UserDefinedKeyType {
58};
59
60namespace tbb {
61 // Test whether tbb_hash_compare can be partially specialized as stated in Reference manual.
62 template<> struct tbb_hash_compare<UserDefinedKeyType> {
63 size_t hash( UserDefinedKeyType ) const {return 0;}
64 bool equal( UserDefinedKeyType /*x*/, UserDefinedKeyType /*y*/ ) {return true;}
65 };
66}
67
68#include "harness_runtime_loader.h"
69
70tbb::concurrent_hash_map<UserDefinedKeyType,int> TestInstantiationWithUserDefinedKeyType;
71
72// Test whether a sufficient set of headers were included to instantiate a concurrent_hash_map. OSS Bug #120 (& #130):
73// http://www.threadingbuildingblocks.org/bug_desc.php?id=120
74tbb::concurrent_hash_map<std::pair<std::pair<int,std::string>,const char*>,int> TestInstantiation;
75
76#include "tbb/parallel_for.h"
77#include "tbb/blocked_range.h"
78#include "tbb/atomic.h"
79#include "tbb/tick_count.h"
80#include "harness.h"
81#include "harness_allocator.h"
82
83class MyException : public std::bad_alloc {
84public:
85 virtual const char *what() const throw() __TBB_override { return "out of items limit"; }
86 virtual ~MyException() throw() {}
87};
88
89/** Has tightly controlled interface so that we can verify
90 that concurrent_hash_map uses only the required interface. */
91class MyKey {
92private:
93 void operator=( const MyKey& ); // Deny access
94 int key;
95 friend class MyHashCompare;
96 friend class YourHashCompare;
97public:
98 static MyKey make( int i ) {
99 MyKey result;
100 result.key = i;
101 return result;
102 }
103 int value_of() const {return key;}
104};
105//TODO: unify with Harness::Foo ?
106tbb::atomic<long> MyDataCount;
107long MyDataCountLimit = 0;
108
109class MyData {
110protected:
111 friend class MyData2;
112 int data;
113 enum state_t {
114 LIVE=0x1234,
115 DEAD=0x5678
116 } my_state;
117 void operator=( const MyData& ); // Deny access
118public:
119 MyData(int i = 0) {
120 my_state = LIVE;
121 data = i;
122 if(MyDataCountLimit && MyDataCount + 1 >= MyDataCountLimit)
123 __TBB_THROW( MyException() );
124 ++MyDataCount;
125 }
126 MyData( const MyData& other ) {
127 ASSERT( other.my_state==LIVE, NULL );
128 my_state = LIVE;
129 data = other.data;
130 if(MyDataCountLimit && MyDataCount + 1 >= MyDataCountLimit)
131 __TBB_THROW( MyException() );
132 ++MyDataCount;
133 }
134 ~MyData() {
135 --MyDataCount;
136 my_state = DEAD;
137 }
138 static MyData make( int i ) {
139 MyData result;
140 result.data = i;
141 return result;
142 }
143 int value_of() const {
144 ASSERT( my_state==LIVE, NULL );
145 return data;
146 }
147 void set_value( int i ) {
148 ASSERT( my_state==LIVE, NULL );
149 data = i;
150 }
151 bool operator==( const MyData& other ) const {
152 ASSERT( other.my_state==LIVE, NULL );
153 ASSERT( my_state==LIVE, NULL );
154 return data == other.data;
155 }
156};
157
158class MyData2 : public MyData {
159public:
160 MyData2( ) {}
161 MyData2( const MyData& other ) {
162 ASSERT( other.my_state==LIVE, NULL );
163 ASSERT( my_state==LIVE, NULL );
164 data = other.data;
165 }
166 void operator=( const MyData& other ) {
167 ASSERT( other.my_state==LIVE, NULL );
168 ASSERT( my_state==LIVE, NULL );
169 data = other.data;
170 }
171 void operator=( const MyData2& other ) {
172 ASSERT( other.my_state==LIVE, NULL );
173 ASSERT( my_state==LIVE, NULL );
174 data = other.data;
175 }
176 bool operator==( const MyData2& other ) const {
177 ASSERT( other.my_state==LIVE, NULL );
178 ASSERT( my_state==LIVE, NULL );
179 return data == other.data;
180 }
181};
182
183class MyHashCompare {
184public:
185 bool equal( const MyKey& j, const MyKey& k ) const {
186 return j.key==k.key;
187 }
188 unsigned long hash( const MyKey& k ) const {
189 return k.key;
190 }
191};
192
193class YourHashCompare {
194public:
195 bool equal( const MyKey& j, const MyKey& k ) const {
196 return j.key==k.key;
197 }
198 unsigned long hash( const MyKey& ) const {
199 return 1;
200 }
201};
202
203typedef local_counting_allocator<std::allocator<MyData> > MyAllocator;
204typedef tbb::concurrent_hash_map<MyKey,MyData,MyHashCompare,MyAllocator> MyTable;
205typedef tbb::concurrent_hash_map<MyKey,MyData2,MyHashCompare> MyTable2;
206typedef tbb::concurrent_hash_map<MyKey,MyData,YourHashCompare> YourTable;
207
208template<typename MyTable>
209inline void CheckAllocator(MyTable &table, size_t expected_allocs, size_t expected_frees, bool exact = true) {
210 size_t items_allocated = table.get_allocator().items_allocated, items_freed = table.get_allocator().items_freed;
211 size_t allocations = table.get_allocator().allocations, frees = table.get_allocator().frees;
212 REMARK("checking allocators: items %u/%u, allocs %u/%u\n",
213 unsigned(items_allocated), unsigned(items_freed), unsigned(allocations), unsigned(frees) );
214 ASSERT( items_allocated == allocations, NULL); ASSERT( items_freed == frees, NULL);
215 if(exact) {
216 ASSERT( allocations == expected_allocs, NULL); ASSERT( frees == expected_frees, NULL);
217 } else {
218 ASSERT( allocations >= expected_allocs, NULL); ASSERT( frees >= expected_frees, NULL);
219 ASSERT( allocations - frees == expected_allocs - expected_frees, NULL );
220 }
221}
222
223inline bool UseKey( size_t i ) {
224 return (i&3)!=3;
225}
226
227struct Insert {
228 static void apply( MyTable& table, int i ) {
229 if( UseKey(i) ) {
230 if( i&4 ) {
231 MyTable::accessor a;
232 table.insert( a, MyKey::make(i) );
233 if( i&1 )
234 (*a).second.set_value(i*i);
235 else
236 a->second.set_value(i*i);
237 } else
238 if( i&1 ) {
239 MyTable::accessor a;
240 table.insert( a, std::make_pair(MyKey::make(i), MyData(i*i)) );
241 ASSERT( (*a).second.value_of()==i*i, NULL );
242 } else {
243 MyTable::const_accessor ca;
244 table.insert( ca, std::make_pair(MyKey::make(i), MyData(i*i)) );
245 ASSERT( ca->second.value_of()==i*i, NULL );
246 }
247 }
248 }
249};
250
251#if __TBB_CPP11_RVALUE_REF_PRESENT
252#include "test_container_move_support.h"
253typedef tbb::concurrent_hash_map<MyKey,Foo,MyHashCompare> DataStateTrackedTable;
254
255struct RvalueInsert {
256 static void apply( DataStateTrackedTable& table, int i ) {
257 DataStateTrackedTable::accessor a;
258 ASSERT( (table.insert( a, std::make_pair(MyKey::make(i), Foo(i + 1)))),"already present while should not ?" );
259 ASSERT( (*a).second == i + 1, NULL );
260 ASSERT( (*a).second.state == Harness::StateTrackableBase::MoveInitialized, "");
261 }
262};
263
264#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
265struct Emplace {
266 static void apply( DataStateTrackedTable& table, int i ) {
267 DataStateTrackedTable::accessor a;
268 ASSERT( (table.emplace( a, MyKey::make(i), (i + 1))),"already present while should not ?" );
269 ASSERT( (*a).second == i + 1, NULL );
270 ASSERT( (*a).second.state == Harness::StateTrackableBase::DirectInitialized, "");
271 }
272};
273#endif // __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
274#endif // __TBB_CPP11_RVALUE_REF_PRESENT
275
276#if __TBB_INITIALIZER_LISTS_PRESENT
277struct InsertInitList {
278 static void apply( MyTable& table, int i ) {
279 if ( UseKey( i ) ) {
280 // TODO: investigate why the following sequence causes an additional allocation sometimes:
281 // table.insert( MyTable::value_type( MyKey::make( i ), i*i ) );
282 // table.insert( MyTable::value_type( MyKey::make( i ), i*i+1 ) );
283 std::initializer_list<MyTable::value_type> il = { MyTable::value_type( MyKey::make( i ), i*i )/*, MyTable::value_type( MyKey::make( i ), i*i+1 ) */ };
284 table.insert( il );
285 }
286 }
287};
288#endif /* __TBB_INITIALIZER_LISTS_PRESENT */
289
290struct Find {
291 static void apply( MyTable& table, int i ) {
292 MyTable::accessor a;
293 const MyTable::accessor& ca = a;
294 bool b = table.find( a, MyKey::make(i) );
295 ASSERT( b==!a.empty(), NULL );
296 if( b ) {
297 if( !UseKey(i) )
298 REPORT("Line %d: unexpected key %d present\n",__LINE__,i);
299 AssertSameType( &*a, static_cast<MyTable::value_type*>(0) );
300 ASSERT( ca->second.value_of()==i*i, NULL );
301 ASSERT( (*ca).second.value_of()==i*i, NULL );
302 if( i&1 )
303 ca->second.set_value( ~ca->second.value_of() );
304 else
305 (*ca).second.set_value( ~ca->second.value_of() );
306 } else {
307 if( UseKey(i) )
308 REPORT("Line %d: key %d missing\n",__LINE__,i);
309 }
310 }
311};
312
313struct FindConst {
314 static void apply( const MyTable& table, int i ) {
315 MyTable::const_accessor a;
316 const MyTable::const_accessor& ca = a;
317 bool b = table.find( a, MyKey::make(i) );
318 ASSERT( b==(table.count(MyKey::make(i))>0), NULL );
319 ASSERT( b==!a.empty(), NULL );
320 ASSERT( b==UseKey(i), NULL );
321 if( b ) {
322 AssertSameType( &*ca, static_cast<const MyTable::value_type*>(0) );
323 ASSERT( ca->second.value_of()==~(i*i), NULL );
324 ASSERT( (*ca).second.value_of()==~(i*i), NULL );
325 }
326 }
327};
328
329tbb::atomic<int> EraseCount;
330
331struct Erase {
332 static void apply( MyTable& table, int i ) {
333 bool b;
334 if(i&4) {
335 if(i&8) {
336 MyTable::const_accessor a;
337 b = table.find( a, MyKey::make(i) ) && table.erase( a );
338 } else {
339 MyTable::accessor a;
340 b = table.find( a, MyKey::make(i) ) && table.erase( a );
341 }
342 } else
343 b = table.erase( MyKey::make(i) );
344 if( b ) ++EraseCount;
345 ASSERT( table.count(MyKey::make(i)) == 0, NULL );
346 }
347};
348
349static const int IE_SIZE = 2;
350tbb::atomic<YourTable::size_type> InsertEraseCount[IE_SIZE];
351
352struct InsertErase {
353 static void apply( YourTable& table, int i ) {
354 if ( i%3 ) {
355 int key = i%IE_SIZE;
356 if ( table.insert( std::make_pair(MyKey::make(key), MyData2()) ) )
357 ++InsertEraseCount[key];
358 } else {
359 int key = i%IE_SIZE;
360 if( i&1 ) {
361 YourTable::accessor res;
362 if(table.find( res, MyKey::make(key) ) && table.erase( res ) )
363 --InsertEraseCount[key];
364 } else {
365 YourTable::const_accessor res;
366 if(table.find( res, MyKey::make(key) ) && table.erase( res ) )
367 --InsertEraseCount[key];
368 }
369 }
370 }
371};
372
373// Test for the deadlock discussed at:
374// http://softwarecommunity.intel.com/isn/Community/en-US/forums/permalink/30253302/30253302/ShowThread.aspx#30253302
375struct InnerInsert {
376 static void apply( YourTable& table, int i ) {
377 YourTable::accessor a1, a2;
378 if(i&1) __TBB_Yield();
379 table.insert( a1, MyKey::make(1) );
380 __TBB_Yield();
381 table.insert( a2, MyKey::make(1 + (1<<30)) ); // the same chain
382 table.erase( a2 ); // if erase by key it would lead to deadlock for single thread
383 }
384};
385
386#include "harness_barrier.h"
387// Test for the misuse of constness
388struct FakeExclusive : NoAssign {
389 Harness::SpinBarrier& barrier;
390 YourTable& table;
391 FakeExclusive(Harness::SpinBarrier& b, YourTable&t) : barrier(b), table(t) {}
392 void operator()( int i ) const {
393 if(i) {
394 YourTable::const_accessor real_ca;
395 // const accessor on non-const table acquired as reader (shared)
396 ASSERT( table.find(real_ca,MyKey::make(1)), NULL );
397 barrier.wait(); // item can be erased
398 Harness::Sleep(10); // let it enter the erase
399 real_ca->second.value_of(); // check the state while holding accessor
400 } else {
401 YourTable::accessor fake_ca;
402 const YourTable &const_table = table;
403 // non-const accessor on const table acquired as reader (shared)
404 ASSERT( const_table.find(fake_ca,MyKey::make(1)), NULL );
405 barrier.wait(); // readers acquired
406 // can mistakenly remove the item while other readers still refers to it
407 table.erase( fake_ca );
408 }
409 }
410};
411
412template<typename Op, typename MyTable>
413class TableOperation: NoAssign {
414 MyTable& my_table;
415public:
416 void operator()( const tbb::blocked_range<int>& range ) const {
417 for( int i=range.begin(); i!=range.end(); ++i )
418 Op::apply(my_table,i);
419 }
420 TableOperation( MyTable& table ) : my_table(table) {}
421};
422
423template<typename Op, typename TableType>
424void DoConcurrentOperations( TableType& table, int n, const char* what, int nthread ) {
425 REMARK("testing %s with %d threads\n",what,nthread);
426 tbb::tick_count t0 = tbb::tick_count::now();
427 tbb::parallel_for( tbb::blocked_range<int>(0,n,100), TableOperation<Op,TableType>(table) );
428 tbb::tick_count t1 = tbb::tick_count::now();
429 REMARK("time for %s = %g with %d threads\n",what,(t1-t0).seconds(),nthread);
430}
431
432//! Test traversing the table with an iterator.
433void TraverseTable( MyTable& table, size_t n, size_t expected_size ) {
434 REMARK("testing traversal\n");
435 size_t actual_size = table.size();
436 ASSERT( actual_size==expected_size, NULL );
437 size_t count = 0;
438 bool* array = new bool[n];
439 memset( array, 0, n*sizeof(bool) );
440 const MyTable& const_table = table;
441 MyTable::const_iterator ci = const_table.begin();
442 for( MyTable::iterator i = table.begin(); i!=table.end(); ++i ) {
443 // Check iterator
444 int k = i->first.value_of();
445 ASSERT( UseKey(k), NULL );
446 ASSERT( (*i).first.value_of()==k, NULL );
447 ASSERT( 0<=k && size_t(k)<n, "out of bounds key" );
448 ASSERT( !array[k], "duplicate key" );
449 array[k] = true;
450 ++count;
451
452 // Check lower/upper bounds
453 std::pair<MyTable::iterator, MyTable::iterator> er = table.equal_range(i->first);
454 std::pair<MyTable::const_iterator, MyTable::const_iterator> cer = const_table.equal_range(i->first);
455 ASSERT(cer.first == er.first && cer.second == er.second, NULL);
456 ASSERT(cer.first == i, NULL);
457 ASSERT(std::distance(cer.first, cer.second) == 1, NULL);
458
459 // Check const_iterator
460 MyTable::const_iterator cic = ci++;
461 ASSERT( cic->first.value_of()==k, NULL );
462 ASSERT( (*cic).first.value_of()==k, NULL );
463 }
464 ASSERT( ci==const_table.end(), NULL );
465 delete[] array;
466 if( count!=expected_size ) {
467 REPORT("Line %d: count=%ld but should be %ld\n",__LINE__,long(count),long(expected_size));
468 }
469}
470
471typedef tbb::atomic<unsigned char> AtomicByte;
472
473template<typename RangeType>
474struct ParallelTraverseBody: NoAssign {
475 const size_t n;
476 AtomicByte* const array;
477 ParallelTraverseBody( AtomicByte array_[], size_t n_ ) :
478 n(n_),
479 array(array_)
480 {}
481 void operator()( const RangeType& range ) const {
482 for( typename RangeType::iterator i = range.begin(); i!=range.end(); ++i ) {
483 int k = i->first.value_of();
484 ASSERT( 0<=k && size_t(k)<n, NULL );
485 ++array[k];
486 }
487 }
488};
489
490void Check( AtomicByte array[], size_t n, size_t expected_size ) {
491 if( expected_size )
492 for( size_t k=0; k<n; ++k ) {
493 if( array[k] != int(UseKey(k)) ) {
494 REPORT("array[%d]=%d != %d=UseKey(%d)\n",
495 int(k), int(array[k]), int(UseKey(k)), int(k));
496 ASSERT(false,NULL);
497 }
498 }
499}
500
501//! Test traversing the table with a parallel range
502void ParallelTraverseTable( MyTable& table, size_t n, size_t expected_size ) {
503 REMARK("testing parallel traversal\n");
504 ASSERT( table.size()==expected_size, NULL );
505 AtomicByte* array = new AtomicByte[n];
506
507 memset( static_cast<void*>(array), 0, n*sizeof(AtomicByte) );
508 MyTable::range_type r = table.range(10);
509 tbb::parallel_for( r, ParallelTraverseBody<MyTable::range_type>( array, n ));
510 Check( array, n, expected_size );
511
512 const MyTable& const_table = table;
513 memset( static_cast<void*>(array), 0, n*sizeof(AtomicByte) );
514 MyTable::const_range_type cr = const_table.range(10);
515 tbb::parallel_for( cr, ParallelTraverseBody<MyTable::const_range_type>( array, n ));
516 Check( array, n, expected_size );
517
518 delete[] array;
519}
520
521void TestInsertFindErase( int nthread ) {
522 int n=250000;
523
524 // compute m = number of unique keys
525 int m = 0;
526 for( int i=0; i<n; ++i )
527 m += UseKey(i);
528
529 MyAllocator a; a.items_freed = a.frees = 100;
530 ASSERT( MyDataCount==0, NULL );
531 MyTable table(a);
532 TraverseTable(table,n,0);
533 ParallelTraverseTable(table,n,0);
534 CheckAllocator(table, 0, 100);
535
536 int expected_allocs = 0, expected_frees = 100;
537#if __TBB_INITIALIZER_LISTS_PRESENT
538 for ( int i = 0; i < 2; ++i ) {
539 if ( i==0 )
540 DoConcurrentOperations<InsertInitList, MyTable>( table, n, "insert(std::initializer_list)", nthread );
541 else
542#endif
543 DoConcurrentOperations<Insert, MyTable>( table, n, "insert", nthread );
544 ASSERT( MyDataCount == m, NULL );
545 TraverseTable( table, n, m );
546 ParallelTraverseTable( table, n, m );
547 expected_allocs += m;
548 CheckAllocator( table, expected_allocs, expected_frees );
549
550 DoConcurrentOperations<Find, MyTable>( table, n, "find", nthread );
551 ASSERT( MyDataCount == m, NULL );
552 CheckAllocator( table, expected_allocs, expected_frees );
553
554 DoConcurrentOperations<FindConst, MyTable>( table, n, "find(const)", nthread );
555 ASSERT( MyDataCount == m, NULL );
556 CheckAllocator( table, expected_allocs, expected_frees );
557
558 EraseCount = 0;
559 DoConcurrentOperations<Erase, MyTable>( table, n, "erase", nthread );
560 ASSERT( EraseCount == m, NULL );
561 ASSERT( MyDataCount == 0, NULL );
562 TraverseTable( table, n, 0 );
563 expected_frees += m;
564 CheckAllocator( table, expected_allocs, expected_frees );
565
566 bad_hashing = true;
567 table.clear();
568 bad_hashing = false;
569#if __TBB_INITIALIZER_LISTS_PRESENT
570 }
571#endif
572
573 if(nthread > 1) {
574 YourTable ie_table;
575 for( int i=0; i<IE_SIZE; ++i )
576 InsertEraseCount[i] = 0;
577 DoConcurrentOperations<InsertErase,YourTable>(ie_table,n/2,"insert_erase",nthread);
578 for( int i=0; i<IE_SIZE; ++i )
579 ASSERT( InsertEraseCount[i]==ie_table.count(MyKey::make(i)), NULL );
580
581 DoConcurrentOperations<InnerInsert,YourTable>(ie_table,2000,"inner insert",nthread);
582 Harness::SpinBarrier barrier(nthread);
583 REMARK("testing erase on fake exclusive accessor\n");
584 NativeParallelFor( nthread, FakeExclusive(barrier, ie_table));
585 }
586}
587
588volatile int Counter;
589
590class AddToTable: NoAssign {
591 MyTable& my_table;
592 const int my_nthread;
593 const int my_m;
594public:
595 AddToTable( MyTable& table, int nthread, int m ) : my_table(table), my_nthread(nthread), my_m(m) {}
596 void operator()( int ) const {
597 for( int i=0; i<my_m; ++i ) {
598 // Busy wait to synchronize threads
599 int j = 0;
600 while( Counter<i ) {
601 if( ++j==1000000 ) {
602 // If Counter<i after a million iterations, then we almost surely have
603 // more logical threads than physical threads, and should yield in
604 // order to let suspended logical threads make progress.
605 j = 0;
606 __TBB_Yield();
607 }
608 }
609 // Now all threads attempt to simultaneously insert a key.
610 int k;
611 {
612 MyTable::accessor a;
613 MyKey key = MyKey::make(i);
614 if( my_table.insert( a, key ) )
615 a->second.set_value( 1 );
616 else
617 a->second.set_value( a->second.value_of()+1 );
618 k = a->second.value_of();
619 }
620 if( k==my_nthread )
621 Counter=i+1;
622 }
623 }
624};
625
626class RemoveFromTable: NoAssign {
627 MyTable& my_table;
628 const int my_m;
629public:
630 RemoveFromTable( MyTable& table, int m ) : my_table(table), my_m(m) {}
631 void operator()(int) const {
632 for( int i=0; i<my_m; ++i ) {
633 bool b;
634 if(i&4) {
635 if(i&8) {
636 MyTable::const_accessor a;
637 b = my_table.find( a, MyKey::make(i) ) && my_table.erase( a );
638 } else {
639 MyTable::accessor a;
640 b = my_table.find( a, MyKey::make(i) ) && my_table.erase( a );
641 }
642 } else
643 b = my_table.erase( MyKey::make(i) );
644 if( b ) ++EraseCount;
645 }
646 }
647};
648
649//! Test for memory leak in concurrent_hash_map (TR #153).
650void TestConcurrency( int nthread ) {
651 REMARK("testing multiple insertions/deletions of same key with %d threads\n", nthread);
652 {
653 ASSERT( MyDataCount==0, NULL );
654 MyTable table;
655 const int m = 1000;
656 Counter = 0;
657 tbb::tick_count t0 = tbb::tick_count::now();
658 NativeParallelFor( nthread, AddToTable(table,nthread,m) );
659 tbb::tick_count t1 = tbb::tick_count::now();
660 REMARK("time for %u insertions = %g with %d threads\n",unsigned(MyDataCount),(t1-t0).seconds(),nthread);
661 ASSERT( MyDataCount==m, "memory leak detected" );
662
663 EraseCount = 0;
664 t0 = tbb::tick_count::now();
665 NativeParallelFor( nthread, RemoveFromTable(table,m) );
666 t1 = tbb::tick_count::now();
667 REMARK("time for %u deletions = %g with %d threads\n",unsigned(EraseCount),(t1-t0).seconds(),nthread);
668 ASSERT( MyDataCount==0, "memory leak detected" );
669 ASSERT( EraseCount==m, "return value of erase() is broken" );
670
671 CheckAllocator(table, m, m, /*exact*/nthread <= 1);
672 }
673 ASSERT( MyDataCount==0, "memory leak detected" );
674}
675
676void TestTypes() {
677 AssertSameType( static_cast<MyTable::key_type*>(0), static_cast<MyKey*>(0) );
678 AssertSameType( static_cast<MyTable::mapped_type*>(0), static_cast<MyData*>(0) );
679 AssertSameType( static_cast<MyTable::value_type*>(0), static_cast<std::pair<const MyKey,MyData>*>(0) );
680 AssertSameType( static_cast<MyTable::accessor::value_type*>(0), static_cast<MyTable::value_type*>(0) );
681 AssertSameType( static_cast<MyTable::const_accessor::value_type*>(0), static_cast<const MyTable::value_type*>(0) );
682 AssertSameType( static_cast<MyTable::size_type*>(0), static_cast<size_t*>(0) );
683 AssertSameType( static_cast<MyTable::difference_type*>(0), static_cast<ptrdiff_t*>(0) );
684}
685
686template<typename Iterator, typename T>
687void TestIteratorTraits() {
688 AssertSameType( static_cast<typename Iterator::difference_type*>(0), static_cast<ptrdiff_t*>(0) );
689 AssertSameType( static_cast<typename Iterator::value_type*>(0), static_cast<T*>(0) );
690 AssertSameType( static_cast<typename Iterator::pointer*>(0), static_cast<T**>(0) );
691 AssertSameType( static_cast<typename Iterator::iterator_category*>(0), static_cast<std::forward_iterator_tag*>(0) );
692 T x;
693 typename Iterator::reference xr = x;
694 typename Iterator::pointer xp = &x;
695 ASSERT( &xr==xp, NULL );
696}
697
698template<typename Iterator1, typename Iterator2>
699void TestIteratorAssignment( Iterator2 j ) {
700 Iterator1 i(j), k;
701 ASSERT( i==j, NULL ); ASSERT( !(i!=j), NULL );
702 k = j;
703 ASSERT( k==j, NULL ); ASSERT( !(k!=j), NULL );
704}
705
706template<typename Range1, typename Range2>
707void TestRangeAssignment( Range2 r2 ) {
708 Range1 r1(r2); r1 = r2;
709}
710//------------------------------------------------------------------------
711// Test for copy constructor and assignment
712//------------------------------------------------------------------------
713
714template<typename MyTable>
715static void FillTable( MyTable& x, int n ) {
716 for( int i=1; i<=n; ++i ) {
717 MyKey key( MyKey::make(-i) ); // hash values must not be specified in direct order
718 typename MyTable::accessor a;
719 bool b = x.insert(a,key);
720 ASSERT(b, NULL);
721 a->second.set_value( i*i );
722 }
723}
724
725template<typename MyTable>
726static void CheckTable( const MyTable& x, int n ) {
727 ASSERT( x.size()==size_t(n), "table is different size than expected" );
728 ASSERT( x.empty()==(n==0), NULL );
729 ASSERT( x.size()<=x.max_size(), NULL );
730 for( int i=1; i<=n; ++i ) {
731 MyKey key( MyKey::make(-i) );
732 typename MyTable::const_accessor a;
733 bool b = x.find(a,key);
734 ASSERT( b, NULL );
735 ASSERT( a->second.value_of()==i*i, NULL );
736 }
737 int count = 0;
738 int key_sum = 0;
739 for( typename MyTable::const_iterator i(x.begin()); i!=x.end(); ++i ) {
740 ++count;
741 key_sum += -i->first.value_of();
742 }
743 ASSERT( count==n, NULL );
744 ASSERT( key_sum==n*(n+1)/2, NULL );
745}
746
747static void TestCopy() {
748 REMARK("testing copy\n");
749 MyTable t1;
750 for( int i=0; i<10000; i=(i<100 ? i+1 : i*3) ) {
751 MyDataCount = 0;
752
753 FillTable(t1,i);
754 // Do not call CheckTable(t1,i) before copying, it enforces rehashing
755
756 MyTable t2(t1);
757 // Check that copy constructor did not mangle source table.
758 CheckTable(t1,i);
759 swap(t1, t2);
760 CheckTable(t1,i);
761 ASSERT( !(t1 != t2), NULL );
762
763 // Clear original table
764 t2.clear();
765 swap(t2, t1);
766 CheckTable(t1,0);
767
768 // Verify that copy of t1 is correct, even after t1 is cleared.
769 CheckTable(t2,i);
770 t2.clear();
771 t1.swap( t2 );
772 CheckTable(t1,0);
773 CheckTable(t2,0);
774 ASSERT( MyDataCount==0, "data leak?" );
775 }
776}
777
778void TestAssignment() {
779 REMARK("testing assignment\n");
780 for( int i=0; i<1000; i=(i<30 ? i+1 : i*5) ) {
781 for( int j=0; j<1000; j=(j<30 ? j+1 : j*7) ) {
782 MyTable t1;
783 MyTable t2;
784 FillTable(t1,i);
785 FillTable(t2,j);
786 ASSERT( (t1 == t2) == (i == j), NULL );
787 CheckTable(t2,j);
788
789 MyTable& tref = t2=t1;
790 ASSERT( &tref==&t2, NULL );
791 ASSERT( t1 == t2, NULL );
792 CheckTable(t1,i);
793 CheckTable(t2,i);
794
795 t1.clear();
796 CheckTable(t1,0);
797 CheckTable(t2,i);
798 ASSERT( MyDataCount==i, "data leak?" );
799
800 t2.clear();
801 CheckTable(t1,0);
802 CheckTable(t2,0);
803 ASSERT( MyDataCount==0, "data leak?" );
804 }
805 }
806}
807
808void TestIteratorsAndRanges() {
809 REMARK("testing iterators compliance\n");
810 TestIteratorTraits<MyTable::iterator,MyTable::value_type>();
811 TestIteratorTraits<MyTable::const_iterator,const MyTable::value_type>();
812
813 MyTable v;
814 MyTable const &u = v;
815
816 TestIteratorAssignment<MyTable::const_iterator>( u.begin() );
817 TestIteratorAssignment<MyTable::const_iterator>( v.begin() );
818 TestIteratorAssignment<MyTable::iterator>( v.begin() );
819 // doesn't compile as expected: TestIteratorAssignment<typename V::iterator>( u.begin() );
820
821 // check for non-existing
822 ASSERT(v.equal_range(MyKey::make(-1)) == std::make_pair(v.end(), v.end()), NULL);
823 ASSERT(u.equal_range(MyKey::make(-1)) == std::make_pair(u.end(), u.end()), NULL);
824
825 REMARK("testing ranges compliance\n");
826 TestRangeAssignment<MyTable::const_range_type>( u.range() );
827 TestRangeAssignment<MyTable::const_range_type>( v.range() );
828 TestRangeAssignment<MyTable::range_type>( v.range() );
829 // doesn't compile as expected: TestRangeAssignment<typename V::range_type>( u.range() );
830
831 REMARK("testing construction and insertion from iterators range\n");
832 FillTable( v, 1000 );
833 MyTable2 t(v.begin(), v.end());
834 v.rehash();
835 CheckTable(t, 1000);
836 t.insert(v.begin(), v.end()); // do nothing
837 CheckTable(t, 1000);
838 t.clear();
839 t.insert(v.begin(), v.end()); // restore
840 CheckTable(t, 1000);
841
842 REMARK("testing comparison\n");
843 typedef tbb::concurrent_hash_map<MyKey,MyData2,YourHashCompare,MyAllocator> YourTable1;
844 typedef tbb::concurrent_hash_map<MyKey,MyData2,YourHashCompare> YourTable2;
845 YourTable1 t1;
846 FillTable( t1, 10 );
847 CheckTable(t1, 10 );
848 YourTable2 t2(t1.begin(), t1.end());
849 MyKey key( MyKey::make(-5) ); MyData2 data;
850 ASSERT(t2.erase(key), NULL);
851 YourTable2::accessor a;
852 ASSERT(t2.insert(a, key), NULL);
853 data.set_value(0); a->second = data;
854 ASSERT( t1 != t2, NULL);
855 data.set_value(5*5); a->second = data;
856 ASSERT( t1 == t2, NULL);
857}
858
859void TestRehash() {
860 REMARK("testing rehashing\n");
861 MyTable w;
862 w.insert( std::make_pair(MyKey::make(-5), MyData()) );
863 w.rehash(); // without this, assertion will fail
864 MyTable::iterator it = w.begin();
865 int i = 0; // check for non-rehashed buckets
866 for( ; it != w.end(); i++ )
867 w.count( (it++)->first );
868 ASSERT( i == 1, NULL );
869 for( i=0; i<1000; i=(i<29 ? i+1 : i*2) ) {
870 for( int j=max(256+i, i*2); j<10000; j*=3 ) {
871 MyTable v;
872 FillTable( v, i );
873 ASSERT(int(v.size()) == i, NULL);
874 ASSERT(int(v.bucket_count()) <= j, NULL);
875 v.rehash( j );
876 ASSERT(int(v.bucket_count()) >= j, NULL);
877 CheckTable( v, i );
878 }
879 }
880}
881
882template<typename base_alloc_t, typename count_t = tbb::atomic<size_t> >
883class only_node_counting_allocator : public local_counting_allocator<base_alloc_t, count_t> {
884 typedef local_counting_allocator<base_alloc_t, count_t> base_type;
885public:
886 template<typename U>
887 struct rebind {
888 typedef only_node_counting_allocator<typename base_alloc_t::template rebind<U>::other,count_t> other;
889 };
890
891 only_node_counting_allocator() : base_type() {}
892 only_node_counting_allocator(const only_node_counting_allocator& a) : base_type(a) {}
893
894 template<typename U>
895 only_node_counting_allocator(const only_node_counting_allocator<U>& a) : base_type(a) {}
896
897 typename base_type::pointer allocate(const typename base_type::size_type n) {
898 if ( n > 1) {
899 return base_alloc_t::allocate(n);
900 } else {
901 return base_type::allocate(n);
902 }
903 }
904};
905
906#if TBB_USE_EXCEPTIONS
907void TestExceptions() {
908 typedef only_node_counting_allocator<tbb::tbb_allocator<MyData2> > allocator_t;
909 typedef tbb::concurrent_hash_map<MyKey,MyData2,MyHashCompare,allocator_t> ThrowingTable;
910 enum methods {
911 zero_method = 0,
912 ctor_copy, op_assign, op_insert,
913 all_methods
914 };
915 REMARK("testing exception-safety guarantees\n");
916 ThrowingTable src;
917 FillTable( src, 1000 );
918 ASSERT( MyDataCount==1000, NULL );
919
920 try {
921 for(int t = 0; t < 2; t++) // exception type
922 for(int m = zero_method+1; m < all_methods; m++)
923 {
924 allocator_t a;
925 if(t) MyDataCountLimit = 101;
926 else a.set_limits(101);
927 ThrowingTable victim(a);
928 MyDataCount = 0;
929
930 try {
931 switch(m) {
932 case ctor_copy: {
933 ThrowingTable acopy(src, a);
934 } break;
935 case op_assign: {
936 victim = src;
937 } break;
938 case op_insert: {
939#if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_TUPLE_PRESENT
940 // Insertion in cpp11 don't make copy constructions
941 // during the insertion, so we need to decrement limit
942 // to throw an exception in the right place and to prevent
943 // successful insertion of one unexpected item
944 if (MyDataCountLimit)
945 --MyDataCountLimit;
946#endif
947 FillTable( victim, 1000 );
948 } break;
949 default:;
950 }
951 ASSERT(false, "should throw an exception");
952 } catch(std::bad_alloc &e) {
953 MyDataCountLimit = 0;
954 size_t size = victim.size();
955 switch(m) {
956 case op_assign:
957 ASSERT( MyDataCount==100, "data leak?" );
958 ASSERT( size>=100, NULL );
959 CheckAllocator(victim, 100+t, t);
960 __TBB_fallthrough;
961 case ctor_copy:
962 CheckTable(src, 1000);
963 break;
964 case op_insert:
965 ASSERT( size==size_t(100-t), NULL );
966 ASSERT( MyDataCount==100-t, "data leak?" );
967 CheckTable(victim, 100-t);
968 CheckAllocator(victim, 100, t);
969 break;
970
971 default:; // nothing to check here
972 }
973 REMARK("Exception %d: %s\t- ok ()\n", m, e.what());
974 }
975 catch ( ... ) {
976 ASSERT ( __TBB_EXCEPTION_TYPE_INFO_BROKEN, "Unrecognized exception" );
977 }
978 }
979 } catch(...) {
980 ASSERT(false, "unexpected exception");
981 }
982 src.clear(); MyDataCount = 0;
983}
984#endif /* TBB_USE_EXCEPTIONS */
985
986
987#if __TBB_INITIALIZER_LISTS_PRESENT
988#include "test_initializer_list.h"
989
990struct test_insert {
991 template<typename container_type, typename element_type>
992 static void do_test( std::initializer_list<element_type> il, container_type const& expected ) {
993 container_type vd;
994 vd.insert( il );
995 ASSERT( vd == expected, "inserting with an initializer list failed" );
996 }
997};
998
999void TestInitList(){
1000 using namespace initializer_list_support_tests;
1001 REMARK("testing initializer_list methods \n");
1002
1003 typedef tbb::concurrent_hash_map<int,int> ch_map_type;
1004 std::initializer_list<ch_map_type::value_type> pairs_il = {{1,1},{2,2},{3,3},{4,4},{5,5}};
1005
1006 TestInitListSupportWithoutAssign<ch_map_type, test_insert>( pairs_il );
1007 TestInitListSupportWithoutAssign<ch_map_type, test_insert>( {} );
1008}
1009#endif //if __TBB_INITIALIZER_LISTS_PRESENT
1010
1011#if __TBB_RANGE_BASED_FOR_PRESENT
1012#include "test_range_based_for.h"
1013
1014void TestRangeBasedFor(){
1015 using namespace range_based_for_support_tests;
1016
1017 REMARK("testing range based for loop compatibility \n");
1018 typedef tbb::concurrent_hash_map<int,int> ch_map;
1019 ch_map a_ch_map;
1020
1021 const int sequence_length = 100;
1022 for (int i = 1; i <= sequence_length; ++i){
1023 a_ch_map.insert(ch_map::value_type(i,i));
1024 }
1025
1026 ASSERT( range_based_for_accumulate(a_ch_map, pair_second_summer(), 0) == gauss_summ_of_int_sequence(sequence_length), "incorrect accumulated value generated via range based for ?");
1027}
1028#endif //if __TBB_RANGE_BASED_FOR_PRESENT
1029
1030#include "harness_defs.h"
1031
1032// The helper to run a test only when a default construction is present.
1033template <bool default_construction_present> struct do_default_construction_test {
1034 template<typename FuncType> void operator() ( FuncType func ) const { func(); }
1035};
1036template <> struct do_default_construction_test<false> {
1037 template<typename FuncType> void operator()( FuncType ) const {}
1038};
1039
1040template <typename Table>
1041class test_insert_by_key : NoAssign {
1042 typedef typename Table::value_type value_type;
1043 Table &my_c;
1044 const value_type &my_value;
1045public:
1046 test_insert_by_key( Table &c, const value_type &value ) : my_c(c), my_value(value) {}
1047 void operator()() const {
1048 {
1049 typename Table::accessor a;
1050 ASSERT( my_c.insert( a, my_value.first ), NULL );
1051 ASSERT( Harness::IsEqual()(a->first, my_value.first), NULL );
1052 a->second = my_value.second;
1053 } {
1054 typename Table::const_accessor ca;
1055 ASSERT( !my_c.insert( ca, my_value.first ), NULL );
1056 ASSERT( Harness::IsEqual()(ca->first, my_value.first), NULL);
1057 ASSERT( Harness::IsEqual()(ca->second, my_value.second), NULL);
1058 }
1059 }
1060};
1061
1062#include <vector>
1063#include <list>
1064#include <algorithm>
1065#if __TBB_CPP11_REFERENCE_WRAPPER_PRESENT
1066#include <functional>
1067#endif
1068
1069template <typename Table, typename Iterator, typename Range = typename Table::range_type>
1070class test_range : NoAssign {
1071 typedef typename Table::value_type value_type;
1072 Table &my_c;
1073 const std::list<value_type> &my_lst;
1074 std::vector< tbb::atomic<bool> >& my_marks;
1075public:
1076 test_range( Table &c, const std::list<value_type> &lst, std::vector< tbb::atomic<bool> > &marks ) : my_c(c), my_lst(lst), my_marks(marks) {
1077 std::fill( my_marks.begin(), my_marks.end(), false );
1078 }
1079 void operator()( const Range &r ) const { do_test_range( r.begin(), r.end() ); }
1080 void do_test_range( Iterator i, Iterator j ) const {
1081 for ( Iterator it = i; it != j; ) {
1082 Iterator it_prev = it++;
1083 typename std::list<value_type>::const_iterator it2 = std::search( my_lst.begin(), my_lst.end(), it_prev, it, Harness::IsEqual() );
1084 ASSERT( it2 != my_lst.end(), NULL );
1085 typename std::list<value_type>::difference_type dist = std::distance( my_lst.begin(), it2 );
1086 ASSERT( !my_marks[dist], NULL );
1087 my_marks[dist] = true;
1088 }
1089 }
1090};
1091
1092template <bool default_construction_present, typename Table>
1093class check_value : NoAssign {
1094 typedef typename Table::const_iterator const_iterator;
1095 typedef typename Table::iterator iterator;
1096 typedef typename Table::size_type size_type;
1097 Table &my_c;
1098public:
1099 check_value( Table &c ) : my_c(c) {}
1100 void operator()(const typename Table::value_type &value ) {
1101 const Table &const_c = my_c;
1102 ASSERT( my_c.count( value.first ) == 1, NULL );
1103 { // tests with a const accessor.
1104 typename Table::const_accessor ca;
1105 // find
1106 ASSERT( my_c.find( ca, value.first ), NULL);
1107 ASSERT( !ca.empty() , NULL);
1108 ASSERT( Harness::IsEqual()(ca->first, value.first), NULL );
1109 ASSERT( Harness::IsEqual()(ca->second, value.second), NULL );
1110 // erase
1111 ASSERT( my_c.erase( ca ), NULL );
1112 ASSERT( my_c.count( value.first ) == 0, NULL );
1113 // insert (pair)
1114 ASSERT( my_c.insert( ca, value ), NULL);
1115 ASSERT( Harness::IsEqual()(ca->first, value.first), NULL );
1116 ASSERT( Harness::IsEqual()(ca->second, value.second), NULL );
1117 } { // tests with a non-const accessor.
1118 typename Table::accessor a;
1119 // find
1120 ASSERT( my_c.find( a, value.first ), NULL);
1121 ASSERT( !a.empty() , NULL);
1122 ASSERT( Harness::IsEqual()(a->first, value.first), NULL );
1123 ASSERT( Harness::IsEqual()(a->second, value.second), NULL );
1124 // erase
1125 ASSERT( my_c.erase( a ), NULL );
1126 ASSERT( my_c.count( value.first ) == 0, NULL );
1127 // insert
1128 ASSERT( my_c.insert( a, value ), NULL);
1129 ASSERT( Harness::IsEqual()(a->first, value.first), NULL );
1130 ASSERT( Harness::IsEqual()(a->second, value.second), NULL );
1131 }
1132 // erase by key
1133 ASSERT( my_c.erase( value.first ), NULL );
1134 ASSERT( my_c.count( value.first ) == 0, NULL );
1135 do_default_construction_test<default_construction_present>()(test_insert_by_key<Table>( my_c, value ));
1136 // insert by value
1137 ASSERT( my_c.insert( value ) != default_construction_present, NULL );
1138 // equal_range
1139 std::pair<iterator,iterator> r1 = my_c.equal_range( value.first );
1140 iterator r1_first_prev = r1.first++;
1141 ASSERT( Harness::IsEqual()( *r1_first_prev, value ) && Harness::IsEqual()( r1.first, r1.second ), NULL );
1142 std::pair<const_iterator,const_iterator> r2 = const_c.equal_range( value.first );
1143 const_iterator r2_first_prev = r2.first++;
1144 ASSERT( Harness::IsEqual()( *r2_first_prev, value ) && Harness::IsEqual()( r2.first, r2.second ), NULL );
1145 }
1146};
1147
1148#include "tbb/task_scheduler_init.h"
1149
1150template <typename Value, typename U = Value>
1151struct CompareTables {
1152 template <typename T>
1153 static bool IsEqual( const T& t1, const T& t2 ) {
1154 return (t1 == t2) && !(t1 != t2);
1155 }
1156};
1157
1158#if __TBB_CPP11_SMART_POINTERS_PRESENT
1159template <typename U>
1160struct CompareTables< std::pair<const std::weak_ptr<U>, std::weak_ptr<U> > > {
1161 template <typename T>
1162 static bool IsEqual( const T&, const T& ) {
1163 /* do nothing for std::weak_ptr */
1164 return true;
1165 }
1166};
1167#endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
1168
1169template <bool default_construction_present, typename Table>
1170void Examine( Table c, const std::list<typename Table::value_type> &lst) {
1171 typedef const Table const_table;
1172 typedef typename Table::const_iterator const_iterator;
1173 typedef typename Table::iterator iterator;
1174 typedef typename Table::value_type value_type;
1175 typedef typename Table::size_type size_type;
1176
1177 ASSERT( !c.empty(), NULL );
1178 ASSERT( c.size() == lst.size(), NULL );
1179 ASSERT( c.max_size() >= c.size(), NULL );
1180
1181 const check_value<default_construction_present,Table> cv(c);
1182 std::for_each( lst.begin(), lst.end(), cv );
1183
1184 std::vector< tbb::atomic<bool> > marks( lst.size() );
1185
1186 test_range<Table,iterator>( c, lst, marks ).do_test_range( c.begin(), c.end() );
1187 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
1188
1189 test_range<const_table,const_iterator>( c, lst, marks ).do_test_range( c.begin(), c.end() );
1190 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
1191
1192 tbb::task_scheduler_init init;
1193
1194 typedef typename Table::range_type range_type;
1195 tbb::parallel_for( c.range(), test_range<Table,typename range_type::iterator,range_type>( c, lst, marks ) );
1196 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
1197
1198 const_table const_c = c;
1199 ASSERT( CompareTables<value_type>::IsEqual( c, const_c ), NULL );
1200
1201 typedef typename const_table::const_range_type const_range_type;
1202 tbb::parallel_for( c.range(), test_range<const_table,typename const_range_type::iterator,const_range_type>( const_c, lst, marks ) );
1203 ASSERT( std::find( marks.begin(), marks.end(), false ) == marks.end(), NULL );
1204
1205 const size_type new_bucket_count = 2*c.bucket_count();
1206 c.rehash( new_bucket_count );
1207 ASSERT( c.bucket_count() >= new_bucket_count, NULL );
1208
1209 Table c2;
1210 typename std::list<value_type>::const_iterator begin5 = lst.begin();
1211 std::advance( begin5, 5 );
1212 c2.insert( lst.begin(), begin5 );
1213 std::for_each( lst.begin(), begin5, check_value<default_construction_present, Table>( c2 ) );
1214
1215 c2.swap( c );
1216 ASSERT( CompareTables<value_type>::IsEqual( c2, const_c ), NULL );
1217 ASSERT( c.size() == 5, NULL );
1218 std::for_each( lst.begin(), lst.end(), check_value<default_construction_present,Table>(c2) );
1219
1220 tbb::swap( c, c2 );
1221 ASSERT( CompareTables<value_type>::IsEqual( c, const_c ), NULL );
1222 ASSERT( c2.size() == 5, NULL );
1223
1224 c2.clear();
1225 ASSERT( CompareTables<value_type>::IsEqual( c2, Table() ), NULL );
1226
1227 typename Table::allocator_type a = c.get_allocator();
1228 value_type *ptr = a.allocate(1);
1229 ASSERT( ptr, NULL );
1230 a.deallocate( ptr, 1 );
1231}
1232
1233template<typename T>
1234struct debug_hash_compare : tbb::tbb_hash_compare<T> {};
1235
1236template <bool default_construction_present, typename Value>
1237void TypeTester( const std::list<Value> &lst ) {
1238 __TBB_ASSERT( lst.size() >= 5, "Array should have at least 5 elements" );
1239 typedef typename Value::first_type first_type;
1240 typedef typename Value::second_type second_type;
1241 typedef tbb::concurrent_hash_map<first_type,second_type> ch_map;
1242 debug_hash_compare<first_type> compare;
1243 // Construct an empty hash map.
1244 ch_map c1;
1245 c1.insert( lst.begin(), lst.end() );
1246 Examine<default_construction_present>( c1, lst );
1247#if __TBB_INITIALIZER_LISTS_PRESENT && !__TBB_CPP11_INIT_LIST_TEMP_OBJS_LIFETIME_BROKEN
1248 // Constructor from initializer_list.
1249 typename std::list<Value>::const_iterator it = lst.begin();
1250 std::initializer_list<Value> il = { *it++, *it++, *it++ };
1251 ch_map c2( il );
1252 c2.insert( it, lst.end() );
1253 Examine<default_construction_present>( c2, lst );
1254
1255 // Constructor from initializer_list and compare object
1256 ch_map c3( il, compare);
1257 c3.insert( it, lst.end() );
1258 Examine<default_construction_present>( c3, lst );
1259
1260 // Constructor from initializer_list, compare object and allocator
1261 ch_map c4( il, compare, typename ch_map::allocator_type());
1262 c4.insert( it, lst.end());
1263 Examine<default_construction_present>( c4, lst );
1264#endif
1265 // Copying constructor.
1266 ch_map c5(c1);
1267 Examine<default_construction_present>( c5, lst );
1268 // Construct with non-default allocator
1269 typedef tbb::concurrent_hash_map< first_type,second_type,tbb::tbb_hash_compare<first_type>,debug_allocator<Value> > ch_map_debug_alloc;
1270 ch_map_debug_alloc c6;
1271 c6.insert( lst.begin(), lst.end() );
1272 Examine<default_construction_present>( c6, lst );
1273 // Copying constructor
1274 ch_map_debug_alloc c7(c6);
1275 Examine<default_construction_present>( c7, lst );
1276 // Construction empty table with n preallocated buckets.
1277 ch_map c8( lst.size() );
1278 c8.insert( lst.begin(), lst.end() );
1279 Examine<default_construction_present>( c8, lst );
1280 ch_map_debug_alloc c9( lst.size() );
1281 c9.insert( lst.begin(), lst.end() );
1282 Examine<default_construction_present>( c9, lst );
1283 // Construction with copying iteration range.
1284 ch_map c10( c1.begin(), c1.end() );
1285 Examine<default_construction_present>( c10, lst );
1286 // Construction with copying iteration range and given allocator instance.
1287 debug_allocator<Value> allocator;
1288 ch_map_debug_alloc c11( lst.begin(), lst.end(), allocator );
1289 Examine<default_construction_present>( c11, lst );
1290
1291 typedef tbb::concurrent_hash_map< first_type,second_type,debug_hash_compare<first_type>,typename ch_map::allocator_type> ch_map_debug_hash;
1292
1293 // Constructor with two iterators and hash_compare
1294 ch_map_debug_hash c12(c1.begin(), c1.end(), compare);
1295 Examine<default_construction_present>( c12, lst );
1296
1297 ch_map_debug_hash c13(c1.begin(), c1.end(), compare, typename ch_map::allocator_type());
1298 Examine<default_construction_present>( c13, lst );
1299}
1300
1301#if __TBB_CPP11_SMART_POINTERS_PRESENT
1302namespace tbb {
1303 template<> struct tbb_hash_compare< const std::shared_ptr<int> > {
1304 static size_t hash( const std::shared_ptr<int>& ptr ) { return static_cast<size_t>( *ptr ) * interface5::internal::hash_multiplier; }
1305 static bool equal( const std::shared_ptr<int>& ptr1, const std::shared_ptr<int>& ptr2 ) { return ptr1 == ptr2; }
1306 };
1307 template<> struct tbb_hash_compare< const std::weak_ptr<int> > {
1308 static size_t hash( const std::weak_ptr<int>& ptr ) { return static_cast<size_t>( *ptr.lock() ) * interface5::internal::hash_multiplier; }
1309 static bool equal( const std::weak_ptr<int>& ptr1, const std::weak_ptr<int>& ptr2 ) { return ptr1.lock() == ptr2.lock(); }
1310 };
1311}
1312#endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
1313
1314void TestCPP11Types() {
1315 const int NUMBER = 10;
1316
1317 typedef std::pair<const int, int> int_int_t;
1318 std::list<int_int_t> arrIntInt;
1319 for ( int i=0; i<NUMBER; ++i ) arrIntInt.push_back( int_int_t(i, NUMBER-i) );
1320 TypeTester</*default_construction_present = */true>( arrIntInt );
1321
1322#if __TBB_CPP11_REFERENCE_WRAPPER_PRESENT && !__TBB_REFERENCE_WRAPPER_COMPILATION_BROKEN
1323 typedef std::pair<const std::reference_wrapper<const int>, int> ref_int_t;
1324 std::list<ref_int_t> arrRefInt;
1325 for ( std::list<int_int_t>::iterator it = arrIntInt.begin(); it != arrIntInt.end(); ++it )
1326 arrRefInt.push_back( ref_int_t( it->first, it->second ) );
1327 TypeTester</*default_construction_present = */true>( arrRefInt );
1328
1329 typedef std::pair< const int, std::reference_wrapper<int> > int_ref_t;
1330 std::list<int_ref_t> arrIntRef;
1331 for ( std::list<int_int_t>::iterator it = arrIntInt.begin(); it != arrIntInt.end(); ++it )
1332 arrIntRef.push_back( int_ref_t( it->first, it->second ) );
1333 TypeTester</*default_construction_present = */false>( arrIntRef );
1334#else
1335 REPORT("Known issue: C++11 reference wrapper tests are skipped.\n");
1336#endif /* __TBB_CPP11_REFERENCE_WRAPPER_PRESENT && !__TBB_REFERENCE_WRAPPER_COMPILATION_BROKEN*/
1337
1338 typedef std::pair< const int, tbb::atomic<int> > int_tbb_t;
1339 std::list<int_tbb_t> arrIntTbb;
1340 for ( int i=0; i<NUMBER; ++i ) {
1341 tbb::atomic<int> b;
1342 b = NUMBER-i;
1343 arrIntTbb.push_back( int_tbb_t(i, b) );
1344 }
1345 TypeTester</*default_construction_present = */true>( arrIntTbb );
1346
1347#if __TBB_CPP11_SMART_POINTERS_PRESENT
1348 typedef std::pair< const std::shared_ptr<int>, std::shared_ptr<int> > shr_shr_t;
1349 std::list<shr_shr_t> arrShrShr;
1350 for ( int i=0; i<NUMBER; ++i ) {
1351 const int NUMBER_minus_i = NUMBER - i;
1352 arrShrShr.push_back( shr_shr_t( std::make_shared<int>(i), std::make_shared<int>(NUMBER_minus_i) ) );
1353 }
1354 TypeTester< /*default_construction_present = */true>( arrShrShr );
1355
1356 typedef std::pair< const std::weak_ptr<int>, std::weak_ptr<int> > wk_wk_t;
1357 std::list< wk_wk_t > arrWkWk;
1358 std::copy( arrShrShr.begin(), arrShrShr.end(), std::back_inserter(arrWkWk) );
1359 TypeTester< /*default_construction_present = */true>( arrWkWk );
1360#else
1361 REPORT("Known issue: C++11 smart pointer tests are skipped.\n");
1362#endif /* __TBB_CPP11_SMART_POINTERS_PRESENT */
1363}
1364
1365#if __TBB_CPP11_RVALUE_REF_PRESENT
1366
1367struct hash_map_move_traits : default_container_traits {
1368 enum{ expected_number_of_items_to_allocate_for_steal_move = 0 };
1369
1370 template<typename T>
1371 struct hash_compare {
1372 bool equal( const T& lhs, const T& rhs ) const {
1373 return lhs==rhs;
1374 }
1375 size_t hash( const T& k ) const {
1376 return tbb::tbb_hasher(k);
1377 }
1378 };
1379 template<typename element_type, typename allocator_type>
1380 struct apply {
1381 typedef tbb::concurrent_hash_map<element_type, element_type, hash_compare<element_type>, allocator_type > type;
1382 };
1383
1384 typedef FooPairIterator init_iterator_type;
1385 template<typename hash_map_type, typename iterator>
1386 static bool equal(hash_map_type const& c, iterator begin, iterator end){
1387 bool equal_sizes = ( static_cast<size_t>(std::distance(begin, end)) == c.size() );
1388 if (!equal_sizes)
1389 return false;
1390
1391 for (iterator it = begin; it != end; ++it ){
1392 if (c.count( (*it).first) == 0){
1393 return false;
1394 }
1395 }
1396 return true;
1397 }
1398};
1399
1400void TestMoveSupport(){
1401 TestMoveConstructor<hash_map_move_traits>();
1402 TestConstructorWithMoveIterators<hash_map_move_traits>();
1403 TestMoveAssignOperator<hash_map_move_traits>();
1404#if TBB_USE_EXCEPTIONS
1405 TestExceptionSafetyGuaranteesMoveConstructorWithUnEqualAllocatorMemoryFailure<hash_map_move_traits>();
1406 TestExceptionSafetyGuaranteesMoveConstructorWithUnEqualAllocatorExceptionInElementCtor<hash_map_move_traits>();
1407#else
1408 REPORT("Known issue: exception safety tests for C++11 move semantics support are skipped.\n");
1409#endif //TBB_USE_EXCEPTIONS
1410}
1411#else
1412void TestMoveSupport(){
1413 REPORT("Known issue: tests for C++11 move semantics support are skipped.\n");
1414}
1415#endif //__TBB_CPP11_RVALUE_REF_PRESENT
1416
1417#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1418
1419template <template <typename...> typename TMap>
1420void TestDeductionGuides() {
1421 using Key = int;
1422 using Value = std::string;
1423
1424 using ComplexType = std::pair<Key, Value>;
1425 using ComplexTypeConst = std::pair<const Key, Value>;
1426
1427 using DefaultCompare = tbb::tbb_hash_compare<Key>;
1428 using Compare = debug_hash_compare<Key>;
1429 using DefaultAllocator = tbb::tbb_allocator<ComplexTypeConst>;
1430 using Allocator = std::allocator<ComplexType>;
1431
1432 std::vector<ComplexType> v;
1433 auto l = { ComplexTypeConst(1, "one"), ComplexTypeConst(2, "two") };
1434 Compare compare;
1435 Allocator allocator;
1436
1437 // check TMap(InputIterator, InputIterator)
1438 TMap m1(v.begin(), v.end());
1439 static_assert(std::is_same<decltype(m1), TMap<Key, Value, DefaultCompare, DefaultAllocator>>::value);
1440
1441 // check TMap(InputIterator, InputIterator, HashCompare)
1442 TMap m2(v.begin(), v.end(), compare);
1443 static_assert(std::is_same<decltype(m2), TMap<Key, Value, Compare>>::value);
1444
1445 // check TMap(InputIterator, InputIterator, HashCompare, Allocator)
1446 TMap m3(v.begin(), v.end(), compare, allocator);
1447 static_assert(std::is_same<decltype(m3), TMap<Key, Value, Compare, Allocator>>::value);
1448
1449 // check TMap(InputIterator, InputIterator, Allocator)
1450 TMap m4(v.begin(), v.end(), allocator);
1451 static_assert(std::is_same<decltype(m4), TMap<Key, Value, DefaultCompare, Allocator>>::value);
1452
1453 // check TMap(std::initializer_list)
1454 TMap m5(l);
1455 static_assert(std::is_same<decltype(m5), TMap<Key, Value, DefaultCompare, DefaultAllocator>>::value);
1456
1457 // check TMap(std::initializer_list, HashCompare)
1458 TMap m6(l, compare);
1459 static_assert(std::is_same<decltype(m6), TMap<Key, Value, Compare, DefaultAllocator>>::value);
1460
1461 // check TMap(std::initializer_list, HashCompare, Allocator)
1462 TMap m7(l, compare, allocator);
1463 static_assert(std::is_same<decltype(m7), TMap<Key, Value, Compare, Allocator>>::value);
1464
1465 // check TMap(std::initializer_list, Allocator)
1466 TMap m8(l, allocator);
1467 static_assert(std::is_same<decltype(m8), TMap<Key, Value, DefaultCompare, Allocator>>::value);
1468
1469 // check TMap(TMap &)
1470 TMap m9(m1);
1471 static_assert(std::is_same<decltype(m9), decltype(m1)>::value);
1472
1473 // check TMap(TMap &, Allocator)
1474 TMap m10(m4, allocator);
1475 static_assert(std::is_same<decltype(m10), decltype(m4)>::value);
1476
1477 // check TMap(TMap &&)
1478 TMap m11(std::move(m1));
1479 static_assert(std::is_same<decltype(m11), decltype(m1)>::value);
1480
1481 // check TMap(TMap &&, Allocator)
1482 TMap m12(std::move(m4), allocator);
1483 static_assert(std::is_same<decltype(m12), decltype(m4)>::value);
1484}
1485#endif // __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1486
1487template<typename Key>
1488struct non_default_constructible_hash_compare : tbb::tbb_hash_compare<Key> {
1489 non_default_constructible_hash_compare() {
1490 ASSERT(false, "Hash compare object must not default construct during the construction of hash_map with compare argument");
1491 }
1492
1493 non_default_constructible_hash_compare(int) {}
1494};
1495
1496void TestHashCompareConstructors() {
1497 typedef int key_type;
1498 typedef tbb::concurrent_hash_map<key_type, key_type, non_default_constructible_hash_compare<key_type> > map_type;
1499
1500 non_default_constructible_hash_compare<key_type> compare(0);
1501 map_type::allocator_type allocator;
1502
1503 map_type map1(compare);
1504 map_type map2(compare, allocator);
1505
1506 map_type map3(1, compare);
1507 map_type map4(1, compare, allocator);
1508
1509 std::vector<map_type::value_type> reference_vector;
1510 map_type map5(reference_vector.begin(), reference_vector.end(), compare);
1511 map_type map6(reference_vector.begin(), reference_vector.end(), compare, allocator);
1512
1513#if __TBB_INITIALIZER_LISTS_PRESENT
1514 map_type map7({}, compare);
1515 map_type map8({}, compare, allocator);
1516#endif
1517}
1518
1519#if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && !__TBB_SCOPED_ALLOCATOR_BROKEN
1520#include <scoped_allocator>
1521
1522struct custom_hash_compare {
1523 template<typename Allocator>
1524 static size_t hash(const allocator_aware_data<Allocator>& key) {
1525 return tbb::tbb_hash_compare<int>::hash(key.value());
1526 }
1527
1528 template<typename Allocator>
1529 static bool equal(const allocator_aware_data<Allocator>& key1, const allocator_aware_data<Allocator>& key2) {
1530 return tbb::tbb_hash_compare<int>::equal(key1.value(), key2.value());
1531 }
1532};
1533
1534void TestScopedAllocator() {
1535 typedef allocator_aware_data<std::scoped_allocator_adaptor<tbb::tbb_allocator<int>>> allocator_data_type;
1536 typedef std::scoped_allocator_adaptor<tbb::tbb_allocator<allocator_data_type>> allocator_type;
1537 typedef tbb::concurrent_hash_map<allocator_data_type, allocator_data_type,
1538 custom_hash_compare, allocator_type> hash_map_type;
1539
1540 allocator_type allocator;
1541 allocator_data_type key1(1, allocator), key2(2, allocator);
1542 allocator_data_type data1(1, allocator), data2(data1, allocator);
1543 hash_map_type map1(allocator), map2(allocator);
1544
1545 hash_map_type::value_type v1(key1, data1), v2(key2, data2);
1546
1547 auto init_list = { v1, v2 };
1548
1549 allocator_data_type::assert_on_constructions = true;
1550 map1.emplace(key1, data1);
1551 map2.emplace(key2, std::move(data2));
1552
1553 map1.clear();
1554 map2.clear();
1555
1556 map1.insert(v1);
1557 map2.insert(std::move(v2));
1558
1559 map1.clear();
1560 map2.clear();
1561
1562 map1.insert(init_list);
1563
1564 map1.clear();
1565 map2.clear();
1566
1567 hash_map_type::accessor a;
1568 map2.insert(a, allocator_data_type(3));
1569 a.release();
1570
1571 map1 = map2;
1572 map2 = std::move(map1);
1573
1574 hash_map_type map3(allocator);
1575 map3.rehash(1000);
1576 map3 = map2;
1577}
1578#endif
1579
1580#if __TBB_ALLOCATOR_TRAITS_PRESENT
1581void TestAllocatorTraits() {
1582 using namespace propagating_allocators;
1583 typedef int key;
1584 typedef int mapped;
1585 typedef tbb::tbb_hash_compare<key> compare;
1586
1587 typedef tbb::concurrent_hash_map<key, mapped, compare, always_propagating_allocator> always_propagating_map;
1588 typedef tbb::concurrent_hash_map<key, mapped, compare, never_propagating_allocator> never_propagating_map;
1589 typedef tbb::concurrent_hash_map<key, mapped, compare, pocma_allocator> pocma_map;
1590 typedef tbb::concurrent_hash_map<key, mapped, compare, pocca_allocator> pocca_map;
1591 typedef tbb::concurrent_hash_map<key, mapped, compare, pocs_allocator> pocs_map;
1592
1593 test_allocator_traits_support<always_propagating_map>();
1594 test_allocator_traits_support<never_propagating_map>();
1595 test_allocator_traits_support<pocma_map>();
1596 test_allocator_traits_support<pocca_map>();
1597 test_allocator_traits_support<pocs_map>();
1598
1599#if __TBB_CPP11_RVALUE_REF_PRESENT
1600 test_allocator_traits_with_non_movable_value_type<pocma_map>();
1601#endif
1602}
1603#endif // __TBB_ALLOCATOR_TRAITS_PRESENT
1604
1605//------------------------------------------------------------------------
1606// Test driver
1607//------------------------------------------------------------------------
1608int TestMain () {
1609 if( MinThread<0 ) {
1610 REPORT("ERROR: must use at least one thread\n");
1611 exit(1);
1612 }
1613 if( MaxThread<2 ) MaxThread=2;
1614
1615 // Do serial tests
1616 TestTypes();
1617 TestCopy();
1618 TestRehash();
1619 TestAssignment();
1620 TestIteratorsAndRanges();
1621#if __TBB_INITIALIZER_LISTS_PRESENT
1622 TestInitList();
1623#endif //__TBB_INITIALIZER_LISTS_PRESENT
1624
1625#if __TBB_RANGE_BASED_FOR_PRESENT
1626 TestRangeBasedFor();
1627#endif //#if __TBB_RANGE_BASED_FOR_PRESENT
1628
1629#if TBB_USE_EXCEPTIONS
1630 TestExceptions();
1631#endif /* TBB_USE_EXCEPTIONS */
1632
1633 TestMoveSupport();
1634 {
1635#if __TBB_CPP11_RVALUE_REF_PRESENT
1636 tbb::task_scheduler_init init( 1 );
1637 int n=250000;
1638 {
1639 DataStateTrackedTable table;
1640 DoConcurrentOperations<RvalueInsert, DataStateTrackedTable>( table, n, "rvalue ref insert", 1 );
1641 }
1642#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
1643 {
1644 DataStateTrackedTable table;
1645 DoConcurrentOperations<Emplace, DataStateTrackedTable>( table, n, "emplace", 1 );
1646 }
1647#endif //__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
1648#endif // __TBB_CPP11_RVALUE_REF_PRESENT
1649 }
1650
1651 // Do concurrency tests.
1652 for( int nthread=MinThread; nthread<=MaxThread; ++nthread ) {
1653 tbb::task_scheduler_init init( nthread );
1654 TestInsertFindErase( nthread );
1655 TestConcurrency( nthread );
1656 }
1657 // check linking
1658 if(bad_hashing) { //should be false
1659 tbb::internal::runtime_warning("none\nERROR: it must not be executed");
1660 }
1661
1662 TestCPP11Types();
1663 TestHashCompareConstructors();
1664
1665#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
1666 TestDeductionGuides<tbb::concurrent_hash_map>();
1667#endif
1668#if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && !__TBB_SCOPED_ALLOCATOR_BROKEN
1669 TestScopedAllocator();
1670#endif
1671
1672#if __TBB_ALLOCATOR_TRAITS_PRESENT
1673 TestAllocatorTraits();
1674#endif
1675
1676 return Harness::Done;
1677}
1678