1 /*
2 Copyright 2005-2014 Intel Corporation. All Rights Reserved.
3
4 This file is part of Threading Building Blocks. Threading Building Blocks is free software;
5 you can redistribute it and/or modify it under the terms of the GNU General Public License
6 version 2 as published by the Free Software Foundation. Threading Building Blocks is
7 distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
8 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
9 See the GNU General Public License for more details. You should have received a copy of
10 the GNU General Public License along with Threading Building Blocks; if not, write to the
11 Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
12
13 As a special exception, you may use this file as part of a free software library without
14 restriction. Specifically, if other files instantiate templates or use macros or inline
15 functions from this file, or you compile this file and link it with other files to produce
16 an executable, this file does not by itself cause the resulting executable to be covered
17 by the GNU General Public License. This exception does not however invalidate any other
18 reasons why the executable file might be covered by the GNU General Public License.
19 */
20
21 #ifndef __TBB_concurrent_hash_map_H
22 #define __TBB_concurrent_hash_map_H
23
24 #include "tbb_stddef.h"
25
26 #if !TBB_USE_EXCEPTIONS && _MSC_VER
27 // Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
28 #pragma warning (push)
29 #pragma warning (disable: 4530)
30 #endif
31
32 #include <iterator>
33 #include <utility> // Need std::pair
34 #include <cstring> // Need std::memset
35
36 #if !TBB_USE_EXCEPTIONS && _MSC_VER
37 #pragma warning (pop)
38 #endif
39
40 #include "cache_aligned_allocator.h"
41 #include "tbb_allocator.h"
42 #include "spin_rw_mutex.h"
43 #include "atomic.h"
44 #include "tbb_exception.h"
45 #include "tbb_profiling.h"
46 #include "internal/_concurrent_unordered_impl.h" // Need tbb_hasher
47 #if __TBB_INITIALIZER_LISTS_PRESENT
48 #include <initializer_list>
49 #endif
50 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
51 #include <typeinfo>
52 #endif
53 #if __TBB_STATISTICS
54 #include <stdio.h>
55 #endif
56
57 namespace tbb {
58
59 //! hash_compare that is default argument for concurrent_hash_map
60 template<typename Key>
61 struct tbb_hash_compare {
hashtbb_hash_compare62 static size_t hash( const Key& a ) { return tbb_hasher(a); }
equaltbb_hash_compare63 static bool equal( const Key& a, const Key& b ) { return a == b; }
64 };
65
66 namespace interface5 {
67
68 template<typename Key, typename T, typename HashCompare = tbb_hash_compare<Key>, typename A = tbb_allocator<std::pair<Key, T> > >
69 class concurrent_hash_map;
70
71 //! @cond INTERNAL
72 namespace internal {
73 using namespace tbb::internal;
74
75
76 //! Type of a hash code.
77 typedef size_t hashcode_t;
78 //! Node base type
79 struct hash_map_node_base : tbb::internal::no_copy {
80 //! Mutex type
81 typedef spin_rw_mutex mutex_t;
82 //! Scoped lock type for mutex
83 typedef mutex_t::scoped_lock scoped_t;
84 //! Next node in chain
85 hash_map_node_base *next;
86 mutex_t mutex;
87 };
88 //! Incompleteness flag value
89 static hash_map_node_base *const rehash_req = reinterpret_cast<hash_map_node_base*>(size_t(3));
90 //! Rehashed empty bucket flag
91 static hash_map_node_base *const empty_rehashed = reinterpret_cast<hash_map_node_base*>(size_t(0));
92 //! base class of concurrent_hash_map
93 class hash_map_base {
94 public:
95 //! Size type
96 typedef size_t size_type;
97 //! Type of a hash code.
98 typedef size_t hashcode_t;
99 //! Segment index type
100 typedef size_t segment_index_t;
101 //! Node base type
102 typedef hash_map_node_base node_base;
103 //! Bucket type
104 struct bucket : tbb::internal::no_copy {
105 //! Mutex type for buckets
106 typedef spin_rw_mutex mutex_t;
107 //! Scoped lock type for mutex
108 typedef mutex_t::scoped_lock scoped_t;
109 mutex_t mutex;
110 node_base *node_list;
111 };
112 //! Count of segments in the first block
113 static size_type const embedded_block = 1;
114 //! Count of segments in the first block
115 static size_type const embedded_buckets = 1<<embedded_block;
116 //! Count of segments in the first block
117 static size_type const first_block = 8; //including embedded_block. perfect with bucket size 16, so the allocations are power of 4096
118 //! Size of a pointer / table size
119 static size_type const pointers_per_table = sizeof(segment_index_t) * 8; // one segment per bit
120 //! Segment pointer
121 typedef bucket *segment_ptr_t;
122 //! Segment pointers table type
123 typedef segment_ptr_t segments_table_t[pointers_per_table];
124 //! Hash mask = sum of allocated segment sizes - 1
125 atomic<hashcode_t> my_mask;
126 //! Segment pointers table. Also prevents false sharing between my_mask and my_size
127 segments_table_t my_table;
128 //! Size of container in stored items
129 atomic<size_type> my_size; // It must be in separate cache line from my_mask due to performance effects
130 //! Zero segment
131 bucket my_embedded_segment[embedded_buckets];
132 #if __TBB_STATISTICS
133 atomic<unsigned> my_info_resizes; // concurrent ones
134 mutable atomic<unsigned> my_info_restarts; // race collisions
135 atomic<unsigned> my_info_rehashes; // invocations of rehash_bucket
136 #endif
137 //! Constructor
hash_map_base()138 hash_map_base() {
139 std::memset( this, 0, pointers_per_table*sizeof(segment_ptr_t) // 32*4=128 or 64*8=512
140 + sizeof(my_size) + sizeof(my_mask) // 4+4 or 8+8
141 + embedded_buckets*sizeof(bucket) ); // n*8 or n*16
142 for( size_type i = 0; i < embedded_block; i++ ) // fill the table
143 my_table[i] = my_embedded_segment + segment_base(i);
144 my_mask = embedded_buckets - 1;
145 __TBB_ASSERT( embedded_block <= first_block, "The first block number must include embedded blocks");
146 #if __TBB_STATISTICS
147 my_info_resizes = 0; // concurrent ones
148 my_info_restarts = 0; // race collisions
149 my_info_rehashes = 0; // invocations of rehash_bucket
150 #endif
151 }
152
153 //! @return segment index of given index in the array
segment_index_of(size_type index)154 static segment_index_t segment_index_of( size_type index ) {
155 return segment_index_t( __TBB_Log2( index|1 ) );
156 }
157
158 //! @return the first array index of given segment
segment_base(segment_index_t k)159 static segment_index_t segment_base( segment_index_t k ) {
160 return (segment_index_t(1)<<k & ~segment_index_t(1));
161 }
162
163 //! @return segment size except for @arg k == 0
segment_size(segment_index_t k)164 static size_type segment_size( segment_index_t k ) {
165 return size_type(1)<<k; // fake value for k==0
166 }
167
168 //! @return true if @arg ptr is valid pointer
is_valid(void * ptr)169 static bool is_valid( void *ptr ) {
170 return reinterpret_cast<uintptr_t>(ptr) > uintptr_t(63);
171 }
172
173 //! Initialize buckets
init_buckets(segment_ptr_t ptr,size_type sz,bool is_initial)174 static void init_buckets( segment_ptr_t ptr, size_type sz, bool is_initial ) {
175 if( is_initial ) std::memset(ptr, 0, sz*sizeof(bucket) );
176 else for(size_type i = 0; i < sz; i++, ptr++) {
177 *reinterpret_cast<intptr_t*>(&ptr->mutex) = 0;
178 ptr->node_list = rehash_req;
179 }
180 }
181
182 //! Add node @arg n to bucket @arg b
add_to_bucket(bucket * b,node_base * n)183 static void add_to_bucket( bucket *b, node_base *n ) {
184 __TBB_ASSERT(b->node_list != rehash_req, NULL);
185 n->next = b->node_list;
186 b->node_list = n; // its under lock and flag is set
187 }
188
189 //! Exception safety helper
190 struct enable_segment_failsafe : tbb::internal::no_copy {
191 segment_ptr_t *my_segment_ptr;
enable_segment_failsafeenable_segment_failsafe192 enable_segment_failsafe(segments_table_t &table, segment_index_t k) : my_segment_ptr(&table[k]) {}
~enable_segment_failsafeenable_segment_failsafe193 ~enable_segment_failsafe() {
194 if( my_segment_ptr ) *my_segment_ptr = 0; // indicate no allocation in progress
195 }
196 };
197
198 //! Enable segment
199 void enable_segment( segment_index_t k, bool is_initial = false ) {
200 __TBB_ASSERT( k, "Zero segment must be embedded" );
201 enable_segment_failsafe watchdog( my_table, k );
202 cache_aligned_allocator<bucket> alloc;
203 size_type sz;
204 __TBB_ASSERT( !is_valid(my_table[k]), "Wrong concurrent assignment");
205 if( k >= first_block ) {
206 sz = segment_size( k );
207 segment_ptr_t ptr = alloc.allocate( sz );
208 init_buckets( ptr, sz, is_initial );
209 itt_hide_store_word( my_table[k], ptr );
210 sz <<= 1;// double it to get entire capacity of the container
211 } else { // the first block
212 __TBB_ASSERT( k == embedded_block, "Wrong segment index" );
213 sz = segment_size( first_block );
214 segment_ptr_t ptr = alloc.allocate( sz - embedded_buckets );
215 init_buckets( ptr, sz - embedded_buckets, is_initial );
216 ptr -= segment_base(embedded_block);
217 for(segment_index_t i = embedded_block; i < first_block; i++) // calc the offsets
218 itt_hide_store_word( my_table[i], ptr + segment_base(i) );
219 }
220 itt_store_word_with_release( my_mask, sz-1 );
221 watchdog.my_segment_ptr = 0;
222 }
223
224 //! Get bucket by (masked) hashcode
get_bucket(hashcode_t h)225 bucket *get_bucket( hashcode_t h ) const throw() { // TODO: add throw() everywhere?
226 segment_index_t s = segment_index_of( h );
227 h -= segment_base(s);
228 segment_ptr_t seg = my_table[s];
229 __TBB_ASSERT( is_valid(seg), "hashcode must be cut by valid mask for allocated segments" );
230 return &seg[h];
231 }
232
233 // internal serial rehashing helper
mark_rehashed_levels(hashcode_t h)234 void mark_rehashed_levels( hashcode_t h ) throw () {
235 segment_index_t s = segment_index_of( h );
236 while( segment_ptr_t seg = my_table[++s] )
237 if( seg[h].node_list == rehash_req ) {
238 seg[h].node_list = empty_rehashed;
239 mark_rehashed_levels( h + ((hashcode_t)1<<s) ); // optimized segment_base(s)
240 }
241 }
242
243 //! Check for mask race
244 // Splitting into two functions should help inlining
check_mask_race(const hashcode_t h,hashcode_t & m)245 inline bool check_mask_race( const hashcode_t h, hashcode_t &m ) const {
246 hashcode_t m_now, m_old = m;
247 m_now = (hashcode_t) itt_load_word_with_acquire( my_mask );
248 if( m_old != m_now )
249 return check_rehashing_collision( h, m_old, m = m_now );
250 return false;
251 }
252
253 //! Process mask race, check for rehashing collision
check_rehashing_collision(const hashcode_t h,hashcode_t m_old,hashcode_t m)254 bool check_rehashing_collision( const hashcode_t h, hashcode_t m_old, hashcode_t m ) const {
255 __TBB_ASSERT(m_old != m, NULL); // TODO?: m arg could be optimized out by passing h = h&m
256 if( (h & m_old) != (h & m) ) { // mask changed for this hashcode, rare event
257 // condition above proves that 'h' has some other bits set beside 'm_old'
258 // find next applicable mask after m_old //TODO: look at bsl instruction
259 for( ++m_old; !(h & m_old); m_old <<= 1 ) // at maximum few rounds depending on the first block size
260 ;
261 m_old = (m_old<<1) - 1; // get full mask from a bit
262 __TBB_ASSERT((m_old&(m_old+1))==0 && m_old <= m, NULL);
263 // check whether it is rehashing/ed
264 if( itt_load_word_with_acquire(get_bucket(h & m_old)->node_list) != rehash_req )
265 {
266 #if __TBB_STATISTICS
267 my_info_restarts++; // race collisions
268 #endif
269 return true;
270 }
271 }
272 return false;
273 }
274
275 //! Insert a node and check for load factor. @return segment index to enable.
insert_new_node(bucket * b,node_base * n,hashcode_t mask)276 segment_index_t insert_new_node( bucket *b, node_base *n, hashcode_t mask ) {
277 size_type sz = ++my_size; // prefix form is to enforce allocation after the first item inserted
278 add_to_bucket( b, n );
279 // check load factor
280 if( sz >= mask ) { // TODO: add custom load_factor
281 segment_index_t new_seg = __TBB_Log2( mask+1 ); //optimized segment_index_of
282 __TBB_ASSERT( is_valid(my_table[new_seg-1]), "new allocations must not publish new mask until segment has allocated");
283 static const segment_ptr_t is_allocating = (segment_ptr_t)2;
284 if( !itt_hide_load_word(my_table[new_seg])
285 && as_atomic(my_table[new_seg]).compare_and_swap(is_allocating, NULL) == NULL )
286 return new_seg; // The value must be processed
287 }
288 return 0;
289 }
290
291 //! Prepare enough segments for number of buckets
reserve(size_type buckets)292 void reserve(size_type buckets) {
293 if( !buckets-- ) return;
294 bool is_initial = !my_size;
295 for( size_type m = my_mask; buckets > m; m = my_mask )
296 enable_segment( segment_index_of( m+1 ), is_initial );
297 }
298 //! Swap hash_map_bases
internal_swap(hash_map_base & table)299 void internal_swap(hash_map_base &table) {
300 using std::swap;
301 swap(this->my_mask, table.my_mask);
302 swap(this->my_size, table.my_size);
303 for(size_type i = 0; i < embedded_buckets; i++)
304 swap(this->my_embedded_segment[i].node_list, table.my_embedded_segment[i].node_list);
305 for(size_type i = embedded_block; i < pointers_per_table; i++)
306 swap(this->my_table[i], table.my_table[i]);
307 }
308 };
309
310 template<typename Iterator>
311 class hash_map_range;
312
313 //! Meets requirements of a forward iterator for STL */
314 /** Value is either the T or const T type of the container.
315 @ingroup containers */
316 template<typename Container, typename Value>
317 class hash_map_iterator
318 : public std::iterator<std::forward_iterator_tag,Value>
319 {
320 typedef Container map_type;
321 typedef typename Container::node node;
322 typedef hash_map_base::node_base node_base;
323 typedef hash_map_base::bucket bucket;
324
325 template<typename C, typename T, typename U>
326 friend bool operator==( const hash_map_iterator<C,T>& i, const hash_map_iterator<C,U>& j );
327
328 template<typename C, typename T, typename U>
329 friend bool operator!=( const hash_map_iterator<C,T>& i, const hash_map_iterator<C,U>& j );
330
331 template<typename C, typename T, typename U>
332 friend ptrdiff_t operator-( const hash_map_iterator<C,T>& i, const hash_map_iterator<C,U>& j );
333
334 template<typename C, typename U>
335 friend class hash_map_iterator;
336
337 template<typename I>
338 friend class hash_map_range;
339
advance_to_next_bucket()340 void advance_to_next_bucket() { // TODO?: refactor to iterator_base class
341 size_t k = my_index+1;
342 while( my_bucket && k <= my_map->my_mask ) {
343 // Following test uses 2's-complement wizardry
344 if( k& (k-2) ) // not the beginning of a segment
345 ++my_bucket;
346 else my_bucket = my_map->get_bucket( k );
347 my_node = static_cast<node*>( my_bucket->node_list );
348 if( hash_map_base::is_valid(my_node) ) {
349 my_index = k; return;
350 }
351 ++k;
352 }
353 my_bucket = 0; my_node = 0; my_index = k; // the end
354 }
355 #if !defined(_MSC_VER) || defined(__INTEL_COMPILER)
356 template<typename Key, typename T, typename HashCompare, typename A>
357 friend class interface5::concurrent_hash_map;
358 #else
359 public: // workaround
360 #endif
361 //! concurrent_hash_map over which we are iterating.
362 const Container *my_map;
363
364 //! Index in hash table for current item
365 size_t my_index;
366
367 //! Pointer to bucket
368 const bucket *my_bucket;
369
370 //! Pointer to node that has current item
371 node *my_node;
372
373 hash_map_iterator( const Container &map, size_t index, const bucket *b, node_base *n );
374
375 public:
376 //! Construct undefined iterator
hash_map_iterator()377 hash_map_iterator() {}
hash_map_iterator(const hash_map_iterator<Container,typename Container::value_type> & other)378 hash_map_iterator( const hash_map_iterator<Container,typename Container::value_type> &other ) :
379 my_map(other.my_map),
380 my_index(other.my_index),
381 my_bucket(other.my_bucket),
382 my_node(other.my_node)
383 {}
384 Value& operator*() const {
385 __TBB_ASSERT( hash_map_base::is_valid(my_node), "iterator uninitialized or at end of container?" );
386 return my_node->item;
387 }
388 Value* operator->() const {return &operator*();}
389 hash_map_iterator& operator++();
390
391 //! Post increment
392 hash_map_iterator operator++(int) {
393 hash_map_iterator old(*this);
394 operator++();
395 return old;
396 }
397 };
398
399 template<typename Container, typename Value>
hash_map_iterator(const Container & map,size_t index,const bucket * b,node_base * n)400 hash_map_iterator<Container,Value>::hash_map_iterator( const Container &map, size_t index, const bucket *b, node_base *n ) :
401 my_map(&map),
402 my_index(index),
403 my_bucket(b),
404 my_node( static_cast<node*>(n) )
405 {
406 if( b && !hash_map_base::is_valid(n) )
407 advance_to_next_bucket();
408 }
409
410 template<typename Container, typename Value>
411 hash_map_iterator<Container,Value>& hash_map_iterator<Container,Value>::operator++() {
412 my_node = static_cast<node*>( my_node->next );
413 if( !my_node ) advance_to_next_bucket();
414 return *this;
415 }
416
417 template<typename Container, typename T, typename U>
418 bool operator==( const hash_map_iterator<Container,T>& i, const hash_map_iterator<Container,U>& j ) {
419 return i.my_node == j.my_node && i.my_map == j.my_map;
420 }
421
422 template<typename Container, typename T, typename U>
423 bool operator!=( const hash_map_iterator<Container,T>& i, const hash_map_iterator<Container,U>& j ) {
424 return i.my_node != j.my_node || i.my_map != j.my_map;
425 }
426
427 //! Range class used with concurrent_hash_map
428 /** @ingroup containers */
429 template<typename Iterator>
430 class hash_map_range {
431 typedef typename Iterator::map_type map_type;
432 Iterator my_begin;
433 Iterator my_end;
434 mutable Iterator my_midpoint;
435 size_t my_grainsize;
436 //! Set my_midpoint to point approximately half way between my_begin and my_end.
437 void set_midpoint() const;
438 template<typename U> friend class hash_map_range;
439 public:
440 //! Type for size of a range
441 typedef std::size_t size_type;
442 typedef typename Iterator::value_type value_type;
443 typedef typename Iterator::reference reference;
444 typedef typename Iterator::difference_type difference_type;
445 typedef Iterator iterator;
446
447 //! True if range is empty.
empty()448 bool empty() const {return my_begin==my_end;}
449
450 //! True if range can be partitioned into two subranges.
is_divisible()451 bool is_divisible() const {
452 return my_midpoint!=my_end;
453 }
454 //! Split range.
hash_map_range(hash_map_range & r,split)455 hash_map_range( hash_map_range& r, split ) :
456 my_end(r.my_end),
457 my_grainsize(r.my_grainsize)
458 {
459 r.my_end = my_begin = r.my_midpoint;
460 __TBB_ASSERT( !empty(), "Splitting despite the range is not divisible" );
461 __TBB_ASSERT( !r.empty(), "Splitting despite the range is not divisible" );
462 set_midpoint();
463 r.set_midpoint();
464 }
465 //! type conversion
466 template<typename U>
hash_map_range(hash_map_range<U> & r)467 hash_map_range( hash_map_range<U>& r) :
468 my_begin(r.my_begin),
469 my_end(r.my_end),
470 my_midpoint(r.my_midpoint),
471 my_grainsize(r.my_grainsize)
472 {}
473 //! Init range with container and grainsize specified
474 hash_map_range( const map_type &map, size_type grainsize_ = 1 ) :
475 my_begin( Iterator( map, 0, map.my_embedded_segment, map.my_embedded_segment->node_list ) ),
476 my_end( Iterator( map, map.my_mask + 1, 0, 0 ) ),
477 my_grainsize( grainsize_ )
478 {
479 __TBB_ASSERT( grainsize_>0, "grainsize must be positive" );
480 set_midpoint();
481 }
begin()482 const Iterator& begin() const {return my_begin;}
end()483 const Iterator& end() const {return my_end;}
484 //! The grain size for this range.
grainsize()485 size_type grainsize() const {return my_grainsize;}
486 };
487
488 template<typename Iterator>
set_midpoint()489 void hash_map_range<Iterator>::set_midpoint() const {
490 // Split by groups of nodes
491 size_t m = my_end.my_index-my_begin.my_index;
492 if( m > my_grainsize ) {
493 m = my_begin.my_index + m/2u;
494 hash_map_base::bucket *b = my_begin.my_map->get_bucket(m);
495 my_midpoint = Iterator(*my_begin.my_map,m,b,b->node_list);
496 } else {
497 my_midpoint = my_end;
498 }
499 __TBB_ASSERT( my_begin.my_index <= my_midpoint.my_index,
500 "my_begin is after my_midpoint" );
501 __TBB_ASSERT( my_midpoint.my_index <= my_end.my_index,
502 "my_midpoint is after my_end" );
503 __TBB_ASSERT( my_begin != my_midpoint || my_begin == my_end,
504 "[my_begin, my_midpoint) range should not be empty" );
505 }
506
507 } // internal
508 //! @endcond
509
510 #if _MSC_VER && !defined(__INTEL_COMPILER)
511 // Suppress "conditional expression is constant" warning.
512 #pragma warning( push )
513 #pragma warning( disable: 4127 )
514 #endif
515
516 //! Unordered map from Key to T.
517 /** concurrent_hash_map is associative container with concurrent access.
518
519 @par Compatibility
520 The class meets all Container Requirements from C++ Standard (See ISO/IEC 14882:2003(E), clause 23.1).
521
522 @par Exception Safety
523 - Hash function is not permitted to throw an exception. User-defined types Key and T are forbidden from throwing an exception in destructors.
524 - If exception happens during insert() operations, it has no effect (unless exception raised by HashCompare::hash() function during grow_segment).
525 - If exception happens during operator=() operation, the container can have a part of source items, and methods size() and empty() can return wrong results.
526
527 @par Changes since TBB 2.1
528 - Replaced internal algorithm and data structure. Patent is pending.
529 - Added buckets number argument for constructor
530
531 @par Changes since TBB 2.0
532 - Fixed exception-safety
533 - Added template argument for allocator
534 - Added allocator argument in constructors
535 - Added constructor from a range of iterators
536 - Added several new overloaded insert() methods
537 - Added get_allocator()
538 - Added swap()
539 - Added count()
540 - Added overloaded erase(accessor &) and erase(const_accessor&)
541 - Added equal_range() [const]
542 - Added [const_]pointer, [const_]reference, and allocator_type types
543 - Added global functions: operator==(), operator!=(), and swap()
544
545 @ingroup containers */
546 template<typename Key, typename T, typename HashCompare, typename Allocator>
547 class concurrent_hash_map : protected internal::hash_map_base {
548 template<typename Container, typename Value>
549 friend class internal::hash_map_iterator;
550
551 template<typename I>
552 friend class internal::hash_map_range;
553
554 public:
555 typedef Key key_type;
556 typedef T mapped_type;
557 typedef std::pair<const Key,T> value_type;
558 typedef hash_map_base::size_type size_type;
559 typedef ptrdiff_t difference_type;
560 typedef value_type *pointer;
561 typedef const value_type *const_pointer;
562 typedef value_type &reference;
563 typedef const value_type &const_reference;
564 typedef internal::hash_map_iterator<concurrent_hash_map,value_type> iterator;
565 typedef internal::hash_map_iterator<concurrent_hash_map,const value_type> const_iterator;
566 typedef internal::hash_map_range<iterator> range_type;
567 typedef internal::hash_map_range<const_iterator> const_range_type;
568 typedef Allocator allocator_type;
569
570 protected:
571 friend class const_accessor;
572 struct node;
573 typedef typename Allocator::template rebind<node>::other node_allocator_type;
574 node_allocator_type my_allocator;
575 HashCompare my_hash_compare;
576
577 struct node : public node_base {
578 value_type item;
nodenode579 node( const Key &key ) : item(key, T()) {}
nodenode580 node( const Key &key, const T &t ) : item(key, t) {}
581 #if __TBB_CPP11_RVALUE_REF_PRESENT
nodenode582 node( value_type&& i ) : item(std::move(i)){}
583 #endif //__TBB_CPP11_RVALUE_REF_PRESENT
nodenode584 node( const value_type& i ) : item(i) {}
585
586 // exception-safe allocation, see C++ Standard 2003, clause 5.3.4p17
newnode587 void *operator new( size_t /*size*/, node_allocator_type &a ) {
588 void *ptr = a.allocate(1);
589 if(!ptr)
590 tbb::internal::throw_exception(tbb::internal::eid_bad_alloc);
591 return ptr;
592 }
593 // match placement-new form above to be called if exception thrown in constructor
deletenode594 void operator delete( void *ptr, node_allocator_type &a ) { a.deallocate(static_cast<node*>(ptr),1); }
595 };
596
delete_node(node_base * n)597 void delete_node( node_base *n ) {
598 my_allocator.destroy( static_cast<node*>(n) );
599 my_allocator.deallocate( static_cast<node*>(n), 1);
600 }
601
allocate_node_copy_construct(node_allocator_type & allocator,const Key & key,const T * t)602 static node* allocate_node_copy_construct(node_allocator_type& allocator, const Key &key, const T * t){
603 return new( allocator ) node(key, *t);
604 }
605
allocate_node_default_construct(node_allocator_type & allocator,const Key & key,const T *)606 static node* allocate_node_default_construct(node_allocator_type& allocator, const Key &key, const T * ){
607 return new( allocator ) node(key);
608 }
609
do_not_allocate_node(node_allocator_type &,const Key &,const T *)610 static node* do_not_allocate_node(node_allocator_type& , const Key &, const T * ){
611 __TBB_ASSERT(false,"this dummy function should not be called");
612 return NULL;
613 }
614
search_bucket(const key_type & key,bucket * b)615 node *search_bucket( const key_type &key, bucket *b ) const {
616 node *n = static_cast<node*>( b->node_list );
617 while( is_valid(n) && !my_hash_compare.equal(key, n->item.first) )
618 n = static_cast<node*>( n->next );
619 __TBB_ASSERT(n != internal::rehash_req, "Search can be executed only for rehashed bucket");
620 return n;
621 }
622
623 //! bucket accessor is to find, rehash, acquire a lock, and access a bucket
624 class bucket_accessor : public bucket::scoped_t {
625 bucket *my_b;
626 public:
627 bucket_accessor( concurrent_hash_map *base, const hashcode_t h, bool writer = false ) { acquire( base, h, writer ); }
628 //! find a bucket by masked hashcode, optionally rehash, and acquire the lock
629 inline void acquire( concurrent_hash_map *base, const hashcode_t h, bool writer = false ) {
630 my_b = base->get_bucket( h );
631 // TODO: actually, notification is unnecessary here, just hiding double-check
632 if( itt_load_word_with_acquire(my_b->node_list) == internal::rehash_req
633 && try_acquire( my_b->mutex, /*write=*/true ) )
634 {
635 if( my_b->node_list == internal::rehash_req ) base->rehash_bucket( my_b, h ); //recursive rehashing
636 }
637 else bucket::scoped_t::acquire( my_b->mutex, writer );
638 __TBB_ASSERT( my_b->node_list != internal::rehash_req, NULL);
639 }
640 //! check whether bucket is locked for write
is_writer()641 bool is_writer() { return bucket::scoped_t::is_writer; }
642 //! get bucket pointer
operator()643 bucket *operator() () { return my_b; }
644 };
645
646 // TODO refactor to hash_base
rehash_bucket(bucket * b_new,const hashcode_t h)647 void rehash_bucket( bucket *b_new, const hashcode_t h ) {
648 __TBB_ASSERT( *(intptr_t*)(&b_new->mutex), "b_new must be locked (for write)");
649 __TBB_ASSERT( h > 1, "The lowermost buckets can't be rehashed" );
650 __TBB_store_with_release(b_new->node_list, internal::empty_rehashed); // mark rehashed
651 hashcode_t mask = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
652 #if __TBB_STATISTICS
653 my_info_rehashes++; // invocations of rehash_bucket
654 #endif
655
656 bucket_accessor b_old( this, h & mask );
657
658 mask = (mask<<1) | 1; // get full mask for new bucket
659 __TBB_ASSERT( (mask&(mask+1))==0 && (h & mask) == h, NULL );
660 restart:
661 for( node_base **p = &b_old()->node_list, *n = __TBB_load_with_acquire(*p); is_valid(n); n = *p ) {
662 hashcode_t c = my_hash_compare.hash( static_cast<node*>(n)->item.first );
663 #if TBB_USE_ASSERT
664 hashcode_t bmask = h & (mask>>1);
665 bmask = bmask==0? 1 : ( 1u<<(__TBB_Log2( bmask )+1 ) ) - 1; // minimal mask of parent bucket
666 __TBB_ASSERT( (c & bmask) == (h & bmask), "hash() function changed for key in table" );
667 #endif
668 if( (c & mask) == h ) {
669 if( !b_old.is_writer() )
670 if( !b_old.upgrade_to_writer() ) {
671 goto restart; // node ptr can be invalid due to concurrent erase
672 }
673 *p = n->next; // exclude from b_old
674 add_to_bucket( b_new, n );
675 } else p = &n->next; // iterate to next item
676 }
677 }
678
679 struct call_clear_on_leave {
680 concurrent_hash_map* my_ch_map;
call_clear_on_leavecall_clear_on_leave681 call_clear_on_leave( concurrent_hash_map* a_ch_map ) : my_ch_map(a_ch_map) {}
dismisscall_clear_on_leave682 void dismiss() {my_ch_map = 0;}
~call_clear_on_leavecall_clear_on_leave683 ~call_clear_on_leave(){
684 if (my_ch_map){
685 my_ch_map->clear();
686 }
687 }
688 };
689 public:
690
691 class accessor;
692 //! Combines data access, locking, and garbage collection.
693 class const_accessor : private node::scoped_t /*which derived from no_copy*/ {
694 friend class concurrent_hash_map<Key,T,HashCompare,Allocator>;
695 friend class accessor;
696 public:
697 //! Type of value
698 typedef const typename concurrent_hash_map::value_type value_type;
699
700 //! True if result is empty.
empty()701 bool empty() const { return !my_node; }
702
703 //! Set to null
release()704 void release() {
705 if( my_node ) {
706 node::scoped_t::release();
707 my_node = 0;
708 }
709 }
710
711 //! Return reference to associated value in hash table.
712 const_reference operator*() const {
713 __TBB_ASSERT( my_node, "attempt to dereference empty accessor" );
714 return my_node->item;
715 }
716
717 //! Return pointer to associated value in hash table.
718 const_pointer operator->() const {
719 return &operator*();
720 }
721
722 //! Create empty result
const_accessor()723 const_accessor() : my_node(NULL) {}
724
725 //! Destroy result after releasing the underlying reference.
~const_accessor()726 ~const_accessor() {
727 my_node = NULL; // scoped lock's release() is called in its destructor
728 }
729 protected:
is_writer()730 bool is_writer() { return node::scoped_t::is_writer; }
731 node *my_node;
732 hashcode_t my_hash;
733 };
734
735 //! Allows write access to elements and combines data access, locking, and garbage collection.
736 class accessor: public const_accessor {
737 public:
738 //! Type of value
739 typedef typename concurrent_hash_map::value_type value_type;
740
741 //! Return reference to associated value in hash table.
742 reference operator*() const {
743 __TBB_ASSERT( this->my_node, "attempt to dereference empty accessor" );
744 return this->my_node->item;
745 }
746
747 //! Return pointer to associated value in hash table.
748 pointer operator->() const {
749 return &operator*();
750 }
751 };
752
753 //! Construct empty table.
754 concurrent_hash_map( const allocator_type &a = allocator_type() )
hash_map_base()755 : internal::hash_map_base(), my_allocator(a)
756 {}
757
758 //! Construct empty table with n preallocated buckets. This number serves also as initial concurrency level.
759 concurrent_hash_map( size_type n, const allocator_type &a = allocator_type() )
my_allocator(a)760 : my_allocator(a)
761 {
762 reserve( n );
763 }
764
765 //! Copy constructor
766 concurrent_hash_map( const concurrent_hash_map &table, const allocator_type &a = allocator_type() )
hash_map_base()767 : internal::hash_map_base(), my_allocator(a)
768 {
769 internal_copy(table);
770 }
771
772 #if __TBB_CPP11_RVALUE_REF_PRESENT
773 //! Move constructor
concurrent_hash_map(concurrent_hash_map && table)774 concurrent_hash_map( concurrent_hash_map &&table )
775 : internal::hash_map_base(), my_allocator(std::move(table.get_allocator()))
776 {
777 swap(table);
778 }
779
780 //! Move constructor
concurrent_hash_map(concurrent_hash_map && table,const allocator_type & a)781 concurrent_hash_map( concurrent_hash_map &&table, const allocator_type &a )
782 : internal::hash_map_base(), my_allocator(a)
783 {
784 if (a == table.get_allocator()){
785 this->swap(table);
786 }else{
787 call_clear_on_leave scope_guard(this);
788 internal_copy(std::make_move_iterator(table.begin()), std::make_move_iterator(table.end()));
789 scope_guard.dismiss();
790 }
791 }
792 #endif //__TBB_CPP11_RVALUE_REF_PRESENT
793
794 //! Construction with copying iteration range and given allocator instance
795 template<typename I>
796 concurrent_hash_map( I first, I last, const allocator_type &a = allocator_type() )
my_allocator(a)797 : my_allocator(a)
798 {
799 reserve( std::distance(first, last) ); // TODO: load_factor?
800 internal_copy(first, last);
801 }
802
803 #if __TBB_INITIALIZER_LISTS_PRESENT
804 //! Construct empty table with n preallocated buckets. This number serves also as initial concurrency level.
805 concurrent_hash_map( std::initializer_list<value_type> il, const allocator_type &a = allocator_type() )
my_allocator(a)806 : my_allocator(a)
807 {
808 reserve(il.size());
809 internal_copy(il.begin(), il.end());
810 }
811
812 #endif //__TBB_INITIALIZER_LISTS_PRESENT
813
814 //! Assignment
815 concurrent_hash_map& operator=( const concurrent_hash_map &table ) {
816 if( this!=&table ) {
817 clear();
818 internal_copy(table);
819 }
820 return *this;
821 }
822
823 #if __TBB_CPP11_RVALUE_REF_PRESENT
824 //! Move Assignment
825 concurrent_hash_map& operator=( concurrent_hash_map &&table ) {
826 if(this != &table){
827 typedef typename tbb::internal::allocator_traits<allocator_type>::propagate_on_container_move_assignment pocma_t;
828 if(pocma_t::value || this->my_allocator == table.my_allocator) {
829 concurrent_hash_map trash (std::move(*this));
830 //TODO: swapping allocators here may be a problem, replace with single direction moving iff pocma is set
831 this->swap(table);
832 } else {
833 //do per element move
834 concurrent_hash_map moved_copy(std::move(table), this->my_allocator);
835 this->swap(moved_copy);
836 }
837 }
838 return *this;
839 }
840 #endif //__TBB_CPP11_RVALUE_REF_PRESENT
841
842 #if __TBB_INITIALIZER_LISTS_PRESENT
843 //! Assignment
844 concurrent_hash_map& operator=( std::initializer_list<value_type> il ) {
845 clear();
846 reserve(il.size());
847 internal_copy(il.begin(), il.end());
848 return *this;
849 }
850 #endif //__TBB_INITIALIZER_LISTS_PRESENT
851
852
853 //! Rehashes and optionally resizes the whole table.
854 /** Useful to optimize performance before or after concurrent operations.
855 Also enables using of find() and count() concurrent methods in serial context. */
856 void rehash(size_type n = 0);
857
858 //! Clear table
859 void clear();
860
861 //! Clear table and destroy it.
~concurrent_hash_map()862 ~concurrent_hash_map() { clear(); }
863
864 //------------------------------------------------------------------------
865 // Parallel algorithm support
866 //------------------------------------------------------------------------
867 range_type range( size_type grainsize=1 ) {
868 return range_type( *this, grainsize );
869 }
870 const_range_type range( size_type grainsize=1 ) const {
871 return const_range_type( *this, grainsize );
872 }
873
874 //------------------------------------------------------------------------
875 // STL support - not thread-safe methods
876 //------------------------------------------------------------------------
begin()877 iterator begin() { return iterator( *this, 0, my_embedded_segment, my_embedded_segment->node_list ); }
end()878 iterator end() { return iterator( *this, 0, 0, 0 ); }
begin()879 const_iterator begin() const { return const_iterator( *this, 0, my_embedded_segment, my_embedded_segment->node_list ); }
end()880 const_iterator end() const { return const_iterator( *this, 0, 0, 0 ); }
equal_range(const Key & key)881 std::pair<iterator, iterator> equal_range( const Key& key ) { return internal_equal_range( key, end() ); }
equal_range(const Key & key)882 std::pair<const_iterator, const_iterator> equal_range( const Key& key ) const { return internal_equal_range( key, end() ); }
883
884 //! Number of items in table.
size()885 size_type size() const { return my_size; }
886
887 //! True if size()==0.
empty()888 bool empty() const { return my_size == 0; }
889
890 //! Upper bound on size.
max_size()891 size_type max_size() const {return (~size_type(0))/sizeof(node);}
892
893 //! Returns the current number of buckets
bucket_count()894 size_type bucket_count() const { return my_mask+1; }
895
896 //! return allocator object
get_allocator()897 allocator_type get_allocator() const { return this->my_allocator; }
898
899 //! swap two instances. Iterators are invalidated
900 void swap( concurrent_hash_map &table );
901
902 //------------------------------------------------------------------------
903 // concurrent map operations
904 //------------------------------------------------------------------------
905
906 //! Return count of items (0 or 1)
count(const Key & key)907 size_type count( const Key &key ) const {
908 return const_cast<concurrent_hash_map*>(this)->lookup(/*insert*/false, key, NULL, NULL, /*write=*/false, &do_not_allocate_node );
909 }
910
911 //! Find item and acquire a read lock on the item.
912 /** Return true if item is found, false otherwise. */
find(const_accessor & result,const Key & key)913 bool find( const_accessor &result, const Key &key ) const {
914 result.release();
915 return const_cast<concurrent_hash_map*>(this)->lookup(/*insert*/false, key, NULL, &result, /*write=*/false, &do_not_allocate_node );
916 }
917
918 //! Find item and acquire a write lock on the item.
919 /** Return true if item is found, false otherwise. */
find(accessor & result,const Key & key)920 bool find( accessor &result, const Key &key ) {
921 result.release();
922 return lookup(/*insert*/false, key, NULL, &result, /*write=*/true, &do_not_allocate_node );
923 }
924
925 //! Insert item (if not already present) and acquire a read lock on the item.
926 /** Returns true if item is new. */
insert(const_accessor & result,const Key & key)927 bool insert( const_accessor &result, const Key &key ) {
928 result.release();
929 return lookup(/*insert*/true, key, NULL, &result, /*write=*/false, &allocate_node_default_construct );
930 }
931
932 //! Insert item (if not already present) and acquire a write lock on the item.
933 /** Returns true if item is new. */
insert(accessor & result,const Key & key)934 bool insert( accessor &result, const Key &key ) {
935 result.release();
936 return lookup(/*insert*/true, key, NULL, &result, /*write=*/true, &allocate_node_default_construct );
937 }
938
939 //! Insert item by copying if there is no such key present already and acquire a read lock on the item.
940 /** Returns true if item is new. */
insert(const_accessor & result,const value_type & value)941 bool insert( const_accessor &result, const value_type &value ) {
942 result.release();
943 return lookup(/*insert*/true, value.first, &value.second, &result, /*write=*/false, &allocate_node_copy_construct );
944 }
945
946 //! Insert item by copying if there is no such key present already and acquire a write lock on the item.
947 /** Returns true if item is new. */
insert(accessor & result,const value_type & value)948 bool insert( accessor &result, const value_type &value ) {
949 result.release();
950 return lookup(/*insert*/true, value.first, &value.second, &result, /*write=*/true, &allocate_node_copy_construct );
951 }
952
953 //! Insert item by copying if there is no such key present already
954 /** Returns true if item is inserted. */
insert(const value_type & value)955 bool insert( const value_type &value ) {
956 return lookup(/*insert*/true, value.first, &value.second, NULL, /*write=*/false, &allocate_node_copy_construct );
957 }
958
959 //! Insert range [first, last)
960 template<typename I>
insert(I first,I last)961 void insert( I first, I last ) {
962 for ( ; first != last; ++first )
963 insert( *first );
964 }
965
966 #if __TBB_INITIALIZER_LISTS_PRESENT
967 //! Insert initializer list
insert(std::initializer_list<value_type> il)968 void insert( std::initializer_list<value_type> il ) {
969 insert( il.begin(), il.end() );
970 }
971 #endif //__TBB_INITIALIZER_LISTS_PRESENT
972
973 //! Erase item.
974 /** Return true if item was erased by particularly this call. */
975 bool erase( const Key& key );
976
977 //! Erase item by const_accessor.
978 /** Return true if item was erased by particularly this call. */
erase(const_accessor & item_accessor)979 bool erase( const_accessor& item_accessor ) {
980 return exclude( item_accessor );
981 }
982
983 //! Erase item by accessor.
984 /** Return true if item was erased by particularly this call. */
erase(accessor & item_accessor)985 bool erase( accessor& item_accessor ) {
986 return exclude( item_accessor );
987 }
988
989 protected:
990 //! Insert or find item and optionally acquire a lock on the item.
991 bool lookup(bool op_insert, const Key &key, const T *t, const_accessor *result, bool write, node* (*allocate_node)(node_allocator_type& , const Key &, const T * ) ) ;
992
993 //! delete item by accessor
994 bool exclude( const_accessor &item_accessor );
995
996 //! Returns an iterator for an item defined by the key, or for the next item after it (if upper==true)
997 template<typename I>
998 std::pair<I, I> internal_equal_range( const Key& key, I end ) const;
999
1000 //! Copy "source" to *this, where *this must start out empty.
1001 void internal_copy( const concurrent_hash_map& source );
1002
1003 template<typename I>
1004 void internal_copy( I first, I last );
1005
1006 //! Fast find when no concurrent erasure is used. For internal use inside TBB only!
1007 /** Return pointer to item with given key, or NULL if no such item exists.
1008 Must not be called concurrently with erasure operations. */
internal_fast_find(const Key & key)1009 const_pointer internal_fast_find( const Key& key ) const {
1010 hashcode_t h = my_hash_compare.hash( key );
1011 hashcode_t m = (hashcode_t) itt_load_word_with_acquire( my_mask );
1012 node *n;
1013 restart:
1014 __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
1015 bucket *b = get_bucket( h & m );
1016 // TODO: actually, notification is unnecessary here, just hiding double-check
1017 if( itt_load_word_with_acquire(b->node_list) == internal::rehash_req )
1018 {
1019 bucket::scoped_t lock;
1020 if( lock.try_acquire( b->mutex, /*write=*/true ) ) {
1021 if( b->node_list == internal::rehash_req)
1022 const_cast<concurrent_hash_map*>(this)->rehash_bucket( b, h & m ); //recursive rehashing
1023 }
1024 else lock.acquire( b->mutex, /*write=*/false );
1025 __TBB_ASSERT(b->node_list!=internal::rehash_req,NULL);
1026 }
1027 n = search_bucket( key, b );
1028 if( n )
1029 return &n->item;
1030 else if( check_mask_race( h, m ) )
1031 goto restart;
1032 return 0;
1033 }
1034 };
1035
1036 template<typename Key, typename T, typename HashCompare, typename A>
lookup(bool op_insert,const Key & key,const T * t,const_accessor * result,bool write,node * (* allocate_node)(node_allocator_type &,const Key &,const T *))1037 bool concurrent_hash_map<Key,T,HashCompare,A>::lookup( bool op_insert, const Key &key, const T *t, const_accessor *result, bool write, node* (*allocate_node)(node_allocator_type& , const Key&, const T*) ) {
1038 __TBB_ASSERT( !result || !result->my_node, NULL );
1039 bool return_value;
1040 hashcode_t const h = my_hash_compare.hash( key );
1041 hashcode_t m = (hashcode_t) itt_load_word_with_acquire( my_mask );
1042 segment_index_t grow_segment = 0;
1043 node *n, *tmp_n = 0;
1044 restart:
1045 {//lock scope
1046 __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
1047 return_value = false;
1048 // get bucket
1049 bucket_accessor b( this, h & m );
1050
1051 // find a node
1052 n = search_bucket( key, b() );
1053 if( op_insert ) {
1054 // [opt] insert a key
1055 if( !n ) {
1056 if( !tmp_n ) {
1057 tmp_n = allocate_node(my_allocator, key, t);
1058 }
1059 if( !b.is_writer() && !b.upgrade_to_writer() ) { // TODO: improved insertion
1060 // Rerun search_list, in case another thread inserted the item during the upgrade.
1061 n = search_bucket( key, b() );
1062 if( is_valid(n) ) { // unfortunately, it did
1063 b.downgrade_to_reader();
1064 goto exists;
1065 }
1066 }
1067 if( check_mask_race(h, m) )
1068 goto restart; // b.release() is done in ~b().
1069 // insert and set flag to grow the container
1070 grow_segment = insert_new_node( b(), n = tmp_n, m );
1071 tmp_n = 0;
1072 return_value = true;
1073 }
1074 } else { // find or count
1075 if( !n ) {
1076 if( check_mask_race( h, m ) )
1077 goto restart; // b.release() is done in ~b(). TODO: replace by continue
1078 return false;
1079 }
1080 return_value = true;
1081 }
1082 exists:
1083 if( !result ) goto check_growth;
1084 // TODO: the following seems as generic/regular operation
1085 // acquire the item
1086 if( !result->try_acquire( n->mutex, write ) ) {
1087 for( tbb::internal::atomic_backoff backoff(true);; ) {
1088 if( result->try_acquire( n->mutex, write ) ) break;
1089 if( !backoff.bounded_pause() ) {
1090 // the wait takes really long, restart the operation
1091 b.release();
1092 __TBB_ASSERT( !op_insert || !return_value, "Can't acquire new item in locked bucket?" );
1093 __TBB_Yield();
1094 m = (hashcode_t) itt_load_word_with_acquire( my_mask );
1095 goto restart;
1096 }
1097 }
1098 }
1099 }//lock scope
1100 result->my_node = n;
1101 result->my_hash = h;
1102 check_growth:
1103 // [opt] grow the container
1104 if( grow_segment ) {
1105 #if __TBB_STATISTICS
1106 my_info_resizes++; // concurrent ones
1107 #endif
1108 enable_segment( grow_segment );
1109 }
1110 if( tmp_n ) // if op_insert only
1111 delete_node( tmp_n );
1112 return return_value;
1113 }
1114
1115 template<typename Key, typename T, typename HashCompare, typename A>
1116 template<typename I>
internal_equal_range(const Key & key,I end_)1117 std::pair<I, I> concurrent_hash_map<Key,T,HashCompare,A>::internal_equal_range( const Key& key, I end_ ) const {
1118 hashcode_t h = my_hash_compare.hash( key );
1119 hashcode_t m = my_mask;
1120 __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
1121 h &= m;
1122 bucket *b = get_bucket( h );
1123 while( b->node_list == internal::rehash_req ) {
1124 m = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
1125 b = get_bucket( h &= m );
1126 }
1127 node *n = search_bucket( key, b );
1128 if( !n )
1129 return std::make_pair(end_, end_);
1130 iterator lower(*this, h, b, n), upper(lower);
1131 return std::make_pair(lower, ++upper);
1132 }
1133
1134 template<typename Key, typename T, typename HashCompare, typename A>
exclude(const_accessor & item_accessor)1135 bool concurrent_hash_map<Key,T,HashCompare,A>::exclude( const_accessor &item_accessor ) {
1136 __TBB_ASSERT( item_accessor.my_node, NULL );
1137 node_base *const n = item_accessor.my_node;
1138 hashcode_t const h = item_accessor.my_hash;
1139 hashcode_t m = (hashcode_t) itt_load_word_with_acquire( my_mask );
1140 do {
1141 // get bucket
1142 bucket_accessor b( this, h & m, /*writer=*/true );
1143 node_base **p = &b()->node_list;
1144 while( *p && *p != n )
1145 p = &(*p)->next;
1146 if( !*p ) { // someone else was first
1147 if( check_mask_race( h, m ) )
1148 continue;
1149 item_accessor.release();
1150 return false;
1151 }
1152 __TBB_ASSERT( *p == n, NULL );
1153 *p = n->next; // remove from container
1154 my_size--;
1155 break;
1156 } while(true);
1157 if( !item_accessor.is_writer() ) // need to get exclusive lock
1158 item_accessor.upgrade_to_writer(); // return value means nothing here
1159 item_accessor.release();
1160 delete_node( n ); // Only one thread can delete it
1161 return true;
1162 }
1163
1164 template<typename Key, typename T, typename HashCompare, typename A>
erase(const Key & key)1165 bool concurrent_hash_map<Key,T,HashCompare,A>::erase( const Key &key ) {
1166 node_base *n;
1167 hashcode_t const h = my_hash_compare.hash( key );
1168 hashcode_t m = (hashcode_t) itt_load_word_with_acquire( my_mask );
1169 restart:
1170 {//lock scope
1171 // get bucket
1172 bucket_accessor b( this, h & m );
1173 search:
1174 node_base **p = &b()->node_list;
1175 n = *p;
1176 while( is_valid(n) && !my_hash_compare.equal(key, static_cast<node*>(n)->item.first ) ) {
1177 p = &n->next;
1178 n = *p;
1179 }
1180 if( !n ) { // not found, but mask could be changed
1181 if( check_mask_race( h, m ) )
1182 goto restart;
1183 return false;
1184 }
1185 else if( !b.is_writer() && !b.upgrade_to_writer() ) {
1186 if( check_mask_race( h, m ) ) // contended upgrade, check mask
1187 goto restart;
1188 goto search;
1189 }
1190 *p = n->next;
1191 my_size--;
1192 }
1193 {
1194 typename node::scoped_t item_locker( n->mutex, /*write=*/true );
1195 }
1196 // note: there should be no threads pretending to acquire this mutex again, do not try to upgrade const_accessor!
1197 delete_node( n ); // Only one thread can delete it due to write lock on the bucket
1198 return true;
1199 }
1200
1201 template<typename Key, typename T, typename HashCompare, typename A>
swap(concurrent_hash_map<Key,T,HashCompare,A> & table)1202 void concurrent_hash_map<Key,T,HashCompare,A>::swap(concurrent_hash_map<Key,T,HashCompare,A> &table) {
1203 //TODO: respect C++11 allocator_traits<A>::propogate_on_constainer_swap
1204 using std::swap;
1205 swap(this->my_allocator, table.my_allocator);
1206 swap(this->my_hash_compare, table.my_hash_compare);
1207 internal_swap(table);
1208 }
1209
1210 template<typename Key, typename T, typename HashCompare, typename A>
rehash(size_type sz)1211 void concurrent_hash_map<Key,T,HashCompare,A>::rehash(size_type sz) {
1212 reserve( sz ); // TODO: add reduction of number of buckets as well
1213 hashcode_t mask = my_mask;
1214 hashcode_t b = (mask+1)>>1; // size or first index of the last segment
1215 __TBB_ASSERT((b&(b-1))==0, NULL); // zero or power of 2
1216 bucket *bp = get_bucket( b ); // only the last segment should be scanned for rehashing
1217 for(; b <= mask; b++, bp++ ) {
1218 node_base *n = bp->node_list;
1219 __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed || n == internal::rehash_req, "Broken internal structure" );
1220 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during rehash() execution" );
1221 if( n == internal::rehash_req ) { // rehash bucket, conditional because rehashing of a previous bucket may affect this one
1222 hashcode_t h = b; bucket *b_old = bp;
1223 do {
1224 __TBB_ASSERT( h > 1, "The lowermost buckets can't be rehashed" );
1225 hashcode_t m = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
1226 b_old = get_bucket( h &= m );
1227 } while( b_old->node_list == internal::rehash_req );
1228 // now h - is index of the root rehashed bucket b_old
1229 mark_rehashed_levels( h ); // mark all non-rehashed children recursively across all segments
1230 for( node_base **p = &b_old->node_list, *q = *p; is_valid(q); q = *p ) {
1231 hashcode_t c = my_hash_compare.hash( static_cast<node*>(q)->item.first );
1232 if( (c & mask) != h ) { // should be rehashed
1233 *p = q->next; // exclude from b_old
1234 bucket *b_new = get_bucket( c & mask );
1235 __TBB_ASSERT( b_new->node_list != internal::rehash_req, "hash() function changed for key in table or internal error" );
1236 add_to_bucket( b_new, q );
1237 } else p = &q->next; // iterate to next item
1238 }
1239 }
1240 }
1241 #if TBB_USE_PERFORMANCE_WARNINGS
1242 int current_size = int(my_size), buckets = int(mask)+1, empty_buckets = 0, overpopulated_buckets = 0; // usage statistics
1243 static bool reported = false;
1244 #endif
1245 #if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS
1246 for( b = 0; b <= mask; b++ ) {// only last segment should be scanned for rehashing
1247 if( b & (b-2) ) ++bp; // not the beginning of a segment
1248 else bp = get_bucket( b );
1249 node_base *n = bp->node_list;
1250 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during rehash() execution" );
1251 __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed, "Broken internal structure" );
1252 #if TBB_USE_PERFORMANCE_WARNINGS
1253 if( n == internal::empty_rehashed ) empty_buckets++;
1254 else if( n->next ) overpopulated_buckets++;
1255 #endif
1256 #if TBB_USE_ASSERT
1257 for( ; is_valid(n); n = n->next ) {
1258 hashcode_t h = my_hash_compare.hash( static_cast<node*>(n)->item.first ) & mask;
1259 __TBB_ASSERT( h == b, "hash() function changed for key in table or internal error" );
1260 }
1261 #endif
1262 }
1263 #endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS
1264 #if TBB_USE_PERFORMANCE_WARNINGS
1265 if( buckets > current_size) empty_buckets -= buckets - current_size;
1266 else overpopulated_buckets -= current_size - buckets; // TODO: load_factor?
1267 if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
1268 tbb::internal::runtime_warning(
1269 "Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
1270 typeid(*this).name(), current_size, empty_buckets, overpopulated_buckets );
1271 reported = true;
1272 }
1273 #endif
1274 }
1275
1276 template<typename Key, typename T, typename HashCompare, typename A>
clear()1277 void concurrent_hash_map<Key,T,HashCompare,A>::clear() {
1278 hashcode_t m = my_mask;
1279 __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
1280 #if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1281 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1282 int current_size = int(my_size), buckets = int(m)+1, empty_buckets = 0, overpopulated_buckets = 0; // usage statistics
1283 static bool reported = false;
1284 #endif
1285 bucket *bp = 0;
1286 // check consistency
1287 for( segment_index_t b = 0; b <= m; b++ ) {
1288 if( b & (b-2) ) ++bp; // not the beginning of a segment
1289 else bp = get_bucket( b );
1290 node_base *n = bp->node_list;
1291 __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed || n == internal::rehash_req, "Broken internal structure" );
1292 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during clear() execution" );
1293 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1294 if( n == internal::empty_rehashed ) empty_buckets++;
1295 else if( n == internal::rehash_req ) buckets--;
1296 else if( n->next ) overpopulated_buckets++;
1297 #endif
1298 #if __TBB_EXTRA_DEBUG
1299 for(; is_valid(n); n = n->next ) {
1300 hashcode_t h = my_hash_compare.hash( static_cast<node*>(n)->item.first );
1301 h &= m;
1302 __TBB_ASSERT( h == b || get_bucket(h)->node_list == internal::rehash_req, "hash() function changed for key in table or internal error" );
1303 }
1304 #endif
1305 }
1306 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1307 #if __TBB_STATISTICS
1308 printf( "items=%d buckets: capacity=%d rehashed=%d empty=%d overpopulated=%d"
1309 " concurrent: resizes=%u rehashes=%u restarts=%u\n",
1310 current_size, int(m+1), buckets, empty_buckets, overpopulated_buckets,
1311 unsigned(my_info_resizes), unsigned(my_info_rehashes), unsigned(my_info_restarts) );
1312 my_info_resizes = 0; // concurrent ones
1313 my_info_restarts = 0; // race collisions
1314 my_info_rehashes = 0; // invocations of rehash_bucket
1315 #endif
1316 if( buckets > current_size) empty_buckets -= buckets - current_size;
1317 else overpopulated_buckets -= current_size - buckets; // TODO: load_factor?
1318 if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
1319 tbb::internal::runtime_warning(
1320 "Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
1321 typeid(*this).name(), current_size, empty_buckets, overpopulated_buckets );
1322 reported = true;
1323 }
1324 #endif
1325 #endif//TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1326 my_size = 0;
1327 segment_index_t s = segment_index_of( m );
1328 __TBB_ASSERT( s+1 == pointers_per_table || !my_table[s+1], "wrong mask or concurrent grow" );
1329 cache_aligned_allocator<bucket> alloc;
1330 do {
1331 __TBB_ASSERT( is_valid( my_table[s] ), "wrong mask or concurrent grow" );
1332 segment_ptr_t buckets_ptr = my_table[s];
1333 size_type sz = segment_size( s ? s : 1 );
1334 for( segment_index_t i = 0; i < sz; i++ )
1335 for( node_base *n = buckets_ptr[i].node_list; is_valid(n); n = buckets_ptr[i].node_list ) {
1336 buckets_ptr[i].node_list = n->next;
1337 delete_node( n );
1338 }
1339 if( s >= first_block) // the first segment or the next
1340 alloc.deallocate( buckets_ptr, sz );
1341 else if( s == embedded_block && embedded_block != first_block )
1342 alloc.deallocate( buckets_ptr, segment_size(first_block)-embedded_buckets );
1343 if( s >= embedded_block ) my_table[s] = 0;
1344 } while(s-- > 0);
1345 my_mask = embedded_buckets - 1;
1346 }
1347
1348 template<typename Key, typename T, typename HashCompare, typename A>
internal_copy(const concurrent_hash_map & source)1349 void concurrent_hash_map<Key,T,HashCompare,A>::internal_copy( const concurrent_hash_map& source ) {
1350 reserve( source.my_size ); // TODO: load_factor?
1351 hashcode_t mask = source.my_mask;
1352 if( my_mask == mask ) { // optimized version
1353 bucket *dst = 0, *src = 0;
1354 bool rehash_required = false;
1355 for( hashcode_t k = 0; k <= mask; k++ ) {
1356 if( k & (k-2) ) ++dst,src++; // not the beginning of a segment
1357 else { dst = get_bucket( k ); src = source.get_bucket( k ); }
1358 __TBB_ASSERT( dst->node_list != internal::rehash_req, "Invalid bucket in destination table");
1359 node *n = static_cast<node*>( src->node_list );
1360 if( n == internal::rehash_req ) { // source is not rehashed, items are in previous buckets
1361 rehash_required = true;
1362 dst->node_list = internal::rehash_req;
1363 } else for(; n; n = static_cast<node*>( n->next ) ) {
1364 add_to_bucket( dst, new( my_allocator ) node(n->item.first, n->item.second) );
1365 ++my_size; // TODO: replace by non-atomic op
1366 }
1367 }
1368 if( rehash_required ) rehash();
1369 } else internal_copy( source.begin(), source.end() );
1370 }
1371
1372 template<typename Key, typename T, typename HashCompare, typename A>
1373 template<typename I>
internal_copy(I first,I last)1374 void concurrent_hash_map<Key,T,HashCompare,A>::internal_copy(I first, I last) {
1375 hashcode_t m = my_mask;
1376 for(; first != last; ++first) {
1377 hashcode_t h = my_hash_compare.hash( (*first).first );
1378 bucket *b = get_bucket( h & m );
1379 __TBB_ASSERT( b->node_list != internal::rehash_req, "Invalid bucket in destination table");
1380 node *n = new( my_allocator ) node(*first);
1381 add_to_bucket( b, n );
1382 ++my_size; // TODO: replace by non-atomic op
1383 }
1384 }
1385
1386 } // namespace interface5
1387
1388 using interface5::concurrent_hash_map;
1389
1390
1391 template<typename Key, typename T, typename HashCompare, typename A1, typename A2>
1392 inline bool operator==(const concurrent_hash_map<Key, T, HashCompare, A1> &a, const concurrent_hash_map<Key, T, HashCompare, A2> &b) {
1393 if(a.size() != b.size()) return false;
1394 typename concurrent_hash_map<Key, T, HashCompare, A1>::const_iterator i(a.begin()), i_end(a.end());
1395 typename concurrent_hash_map<Key, T, HashCompare, A2>::const_iterator j, j_end(b.end());
1396 for(; i != i_end; ++i) {
1397 j = b.equal_range(i->first).first;
1398 if( j == j_end || !(i->second == j->second) ) return false;
1399 }
1400 return true;
1401 }
1402
1403 template<typename Key, typename T, typename HashCompare, typename A1, typename A2>
1404 inline bool operator!=(const concurrent_hash_map<Key, T, HashCompare, A1> &a, const concurrent_hash_map<Key, T, HashCompare, A2> &b)
1405 { return !(a == b); }
1406
1407 template<typename Key, typename T, typename HashCompare, typename A>
swap(concurrent_hash_map<Key,T,HashCompare,A> & a,concurrent_hash_map<Key,T,HashCompare,A> & b)1408 inline void swap(concurrent_hash_map<Key, T, HashCompare, A> &a, concurrent_hash_map<Key, T, HashCompare, A> &b)
1409 { a.swap( b ); }
1410
1411 #if _MSC_VER && !defined(__INTEL_COMPILER)
1412 #pragma warning( pop )
1413 #endif // warning 4127 is back
1414
1415 } // namespace tbb
1416
1417 #endif /* __TBB_concurrent_hash_map_H */
1418