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