17 #ifndef __TBB_concurrent_hash_map_H 18 #define __TBB_concurrent_hash_map_H 20 #define __TBB_concurrent_hash_map_H_include_area 27 #include __TBB_STD_SWAP_HEADER 38 #if __TBB_INITIALIZER_LISTS_PRESENT 39 #include <initializer_list> 41 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 47 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_TUPLE_PRESENT 55 namespace interface5 {
57 template<
typename Key,
typename T,
typename HashCompare = tbb_hash_compare<Key>,
typename A = tbb_allocator<std::pair<const Key, T> > >
102 static size_type
const embedded_block = 1;
104 static size_type
const embedded_buckets = 1<<embedded_block;
106 static size_type
const first_block = 8;
108 static size_type
const pointers_per_table =
sizeof(segment_index_t) * 8;
112 typedef segment_ptr_t segments_table_t[pointers_per_table];
120 bucket my_embedded_segment[embedded_buckets];
122 atomic<unsigned> my_info_resizes;
123 mutable atomic<unsigned> my_info_restarts;
124 atomic<unsigned> my_info_rehashes;
128 std::memset(my_table, 0,
sizeof(my_table));
131 std::memset(my_embedded_segment, 0,
sizeof(my_embedded_segment));
132 for( size_type i = 0; i < embedded_block; i++ )
133 my_table[i] = my_embedded_segment + segment_base(i);
134 my_mask = embedded_buckets - 1;
135 __TBB_ASSERT( embedded_block <= first_block,
"The first block number must include embedded blocks");
138 my_info_restarts = 0;
139 my_info_rehashes = 0;
145 return segment_index_t(
__TBB_Log2( index|1 ) );
150 return (segment_index_t(1)<<k & ~segment_index_t(1));
155 return size_type(1)<<k;
160 return reinterpret_cast<uintptr_t
>(ptr) > uintptr_t(63);
164 static void init_buckets( segment_ptr_t ptr, size_type sz,
bool is_initial ) {
165 if( is_initial ) std::memset( static_cast<void*>(ptr), 0, sz*
sizeof(
bucket) );
166 else for(size_type i = 0; i < sz; i++, ptr++) {
167 *
reinterpret_cast<intptr_t*
>(&ptr->
mutex) = 0;
184 if( my_segment_ptr ) *my_segment_ptr = 0;
189 template<
typename Allocator>
190 void enable_segment( segment_index_t k,
const Allocator& allocator,
bool is_initial =
false ) {
193 bucket_allocator_type bucket_allocator(allocator);
197 __TBB_ASSERT( !is_valid(my_table[k]),
"Wrong concurrent assignment");
198 if( k >= first_block ) {
199 sz = segment_size( k );
200 segment_ptr_t ptr = bucket_allocator_traits::allocate(bucket_allocator, sz);
201 init_buckets( ptr, sz, is_initial );
205 __TBB_ASSERT( k == embedded_block,
"Wrong segment index" );
206 sz = segment_size( first_block );
207 segment_ptr_t ptr = bucket_allocator_traits::allocate(bucket_allocator, sz - embedded_buckets);
208 init_buckets( ptr, sz - embedded_buckets, is_initial );
209 ptr -= segment_base(embedded_block);
210 for(segment_index_t i = embedded_block; i < first_block; i++)
217 template<
typename Allocator>
221 bucket_allocator_type bucket_allocator(allocator);
222 segment_ptr_t buckets_ptr = my_table[
s];
223 size_type sz = segment_size( s ? s : 1 );
225 if( s >= first_block)
226 bucket_allocator_traits::deallocate(bucket_allocator, buckets_ptr, sz);
227 else if( s == embedded_block && embedded_block != first_block )
228 bucket_allocator_traits::deallocate(bucket_allocator, buckets_ptr,
229 segment_size(first_block) - embedded_buckets);
230 if( s >= embedded_block ) my_table[
s] = 0;
235 segment_index_t
s = segment_index_of(
h );
236 h -= segment_base(s);
237 segment_ptr_t seg = my_table[
s];
238 __TBB_ASSERT( is_valid(seg),
"hashcode must be cut by valid mask for allocated segments" );
244 segment_index_t
s = segment_index_of(
h );
245 while( segment_ptr_t seg = my_table[++s] )
246 if( seg[
h].node_list == rehash_req ) {
248 mark_rehashed_levels(
h + ((hashcode_t)1<<s) );
255 hashcode_t m_now, m_old = m;
258 return check_rehashing_collision( h, m_old, m = m_now );
265 if( (h & m_old) != (h & m) ) {
268 for( ++m_old; !(h & m_old); m_old <<= 1 )
270 m_old = (m_old<<1) - 1;
286 size_type sz = ++my_size;
287 add_to_bucket( b, n );
290 segment_index_t new_seg =
__TBB_Log2( mask+1 );
291 __TBB_ASSERT( is_valid(my_table[new_seg-1]),
"new allocations must not publish new mask until segment has allocated");
292 static const segment_ptr_t is_allocating = (segment_ptr_t)2;
294 &&
as_atomic(my_table[new_seg]).compare_and_swap(is_allocating, NULL) == NULL )
301 template<
typename Allocator>
302 void reserve(size_type buckets,
const Allocator& allocator) {
303 if( !buckets-- )
return;
304 bool is_initial = !my_size;
305 for( size_type m = my_mask; buckets > m; m = my_mask )
306 enable_segment( segment_index_of( m+1 ), allocator, is_initial );
313 for(size_type i = 0; i < embedded_buckets; i++)
315 for(size_type i = embedded_block; i < pointers_per_table; i++)
319 #if __TBB_CPP11_RVALUE_REF_PRESENT 321 my_mask = other.my_mask;
322 other.my_mask = embedded_buckets - 1;
323 my_size = other.my_size;
326 for(size_type i = 0; i < embedded_buckets; ++i) {
327 my_embedded_segment[i].
node_list = other.my_embedded_segment[i].node_list;
328 other.my_embedded_segment[i].node_list = NULL;
331 for(size_type i = embedded_block; i < pointers_per_table; ++i) {
332 my_table[i] = other.my_table[i];
333 other.my_table[i] = NULL;
336 #endif // __TBB_CPP11_RVALUE_REF_PRESENT 339 template<
typename Iterator>
345 template<
typename Container,
typename Value>
347 :
public std::iterator<std::forward_iterator_tag,Value>
350 typedef typename Container::node
node;
354 template<
typename C,
typename T,
typename U>
357 template<
typename C,
typename T,
typename U>
360 template<
typename C,
typename T,
typename U>
363 template<
typename C,
typename U>
370 size_t k = my_index+1;
371 __TBB_ASSERT( my_bucket,
"advancing an invalid iterator?");
372 while( k <= my_map->my_mask ) {
376 else my_bucket = my_map->get_bucket( k );
377 my_node =
static_cast<node*
>( my_bucket->node_list );
379 my_index = k;
return;
383 my_bucket = 0; my_node = 0; my_index = k;
385 #if !defined(_MSC_VER) || defined(__INTEL_COMPILER) 386 template<
typename Key,
typename T,
typename HashCompare,
typename A>
391 const Container *my_map;
403 hash_map_iterator(
const Container &map,
size_t index,
const bucket *b, node_base *n );
409 my_map(other.my_map),
410 my_index(other.my_index),
411 my_bucket(other.my_bucket),
412 my_node(other.my_node)
424 return my_node->value();
437 template<
typename Container,
typename Value>
442 my_node( static_cast<
node*>(n) )
448 template<
typename Container,
typename Value>
455 template<
typename Container,
typename T,
typename U>
460 template<
typename Container,
typename T,
typename U>
467 template<
typename Iterator>
475 void set_midpoint()
const;
486 bool empty()
const {
return my_begin==my_end;}
490 return my_midpoint!=my_end;
495 my_grainsize(r.my_grainsize)
498 __TBB_ASSERT( !empty(),
"Splitting despite the range is not divisible" );
506 my_begin(r.my_begin),
508 my_midpoint(r.my_midpoint),
509 my_grainsize(r.my_grainsize)
513 my_begin( Iterator( map, 0, map.my_embedded_segment, map.my_embedded_segment->node_list ) ),
514 my_end( Iterator( map, map.my_mask + 1, 0, 0 ) ),
515 my_grainsize( grainsize_ )
517 __TBB_ASSERT( grainsize_>0,
"grainsize must be positive" );
520 const Iterator&
begin()
const {
return my_begin;}
521 const Iterator&
end()
const {
return my_end;}
526 template<
typename Iterator>
529 size_t m = my_end.my_index-my_begin.my_index;
530 if( m > my_grainsize ) {
531 m = my_begin.my_index + m/2u;
533 my_midpoint = Iterator(*my_begin.my_map,m,b,b->
node_list);
535 my_midpoint = my_end;
537 __TBB_ASSERT( my_begin.my_index <= my_midpoint.my_index,
538 "my_begin is after my_midpoint" );
540 "my_midpoint is after my_end" );
541 __TBB_ASSERT( my_begin != my_midpoint || my_begin == my_end,
542 "[my_begin, my_midpoint) range should not be empty" );
548 #if _MSC_VER && !defined(__INTEL_COMPILER) 550 #pragma warning( push ) 551 #pragma warning( disable: 4127 ) 584 template<
typename Key,
typename T,
typename HashCompare,
typename Allocator>
586 template<
typename Container,
typename Value>
616 class node :
public node_base {
619 value_type*
storage() {
return my_value.begin(); }
620 value_type&
value() {
return *storage(); }
624 node_allocator_traits::destroy(my_allocator, static_cast<node*>(n)->storage());
625 node_allocator_traits::destroy(my_allocator, static_cast<node*>(n));
626 node_allocator_traits::deallocate(my_allocator, static_cast<node*>(n), 1);
636 node_allocator_traits::destroy(my_alloc, my_node);
637 node_allocator_traits::deallocate(my_alloc, my_node, 1);
643 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 644 template<
typename... Args>
647 template<
typename Arg1,
typename Arg2>
651 node* node_ptr = node_allocator_traits::allocate(allocator, 1);
653 node_allocator_traits::construct(allocator, node_ptr);
654 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 655 node_allocator_traits::construct(allocator, node_ptr->
storage(), std::forward<Args>(args)...);
657 node_allocator_traits::construct(allocator, node_ptr->
storage(), tbb::internal::forward<Arg1>(arg1), tbb::internal::forward<Arg2>(arg2));
664 return create_node(allocator, key, *t);
667 #if __TBB_CPP11_RVALUE_REF_PRESENT 669 return create_node(allocator, key,
std::move(*const_cast<T*>(t)));
674 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_TUPLE_PRESENT 676 return create_node(allocator, std::piecewise_construct,
677 std::forward_as_tuple(key), std::forward_as_tuple());
685 __TBB_ASSERT(
false,
"this dummy function should not be called");
691 while( is_valid(n) && !my_hash_compare.equal(key, n->
value().first) )
692 n =
static_cast<node*
>( n->next );
707 && try_acquire( my_b->
mutex,
true ) )
723 __TBB_ASSERT( h > 1,
"The lowermost buckets can't be rehashed" );
732 mask = (mask<<1) | 1;
733 __TBB_ASSERT( (mask&(mask+1))==0 && (h & mask) == h, NULL );
736 hashcode_t c = my_hash_compare.hash( static_cast<node*>(n)->
value().
first );
738 hashcode_t bmask = h & (mask>>1);
739 bmask = bmask==0? 1 : ( 1u<<(
__TBB_Log2( bmask )+1 ) ) - 1;
740 __TBB_ASSERT( (c & bmask) == (h & bmask),
"hash() function changed for key in table" );
742 if( (c & mask) == h ) {
744 if( !b_old.upgrade_to_writer() ) {
748 add_to_bucket( b_new, n );
829 :
internal::hash_map_base(), my_allocator(a)
833 :
internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
838 :
internal::hash_map_base(), my_allocator(a)
840 reserve( n, my_allocator );
843 concurrent_hash_map( size_type n,
const HashCompare& compare,
const allocator_type& a = allocator_type() )
844 :
internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
846 reserve( n, my_allocator );
852 my_allocator(node_allocator_traits::select_on_container_copy_construction(table.get_allocator()))
855 internal_copy(table);
860 :
internal::hash_map_base(), my_allocator(a)
863 internal_copy(table);
867 #if __TBB_CPP11_RVALUE_REF_PRESENT 877 :
internal::hash_map_base(), my_allocator(a)
879 if (a == table.get_allocator()){
883 internal_copy(std::make_move_iterator(table.begin()), std::make_move_iterator(table.end()), table.size());
887 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 892 :
internal::hash_map_base(), my_allocator(a)
895 internal_copy(first, last, std::distance(first, last));
900 concurrent_hash_map( I first, I last,
const HashCompare& compare,
const allocator_type& a = allocator_type() )
901 :
internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
904 internal_copy(first, last, std::distance(first, last));
908 #if __TBB_INITIALIZER_LISTS_PRESENT 909 concurrent_hash_map( std::initializer_list<value_type> il,
const allocator_type &a = allocator_type() )
914 internal_copy(il.begin(), il.end(), il.size());
918 concurrent_hash_map( std::initializer_list<value_type> il,
const HashCompare& compare,
const allocator_type& a = allocator_type() )
919 :
internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
922 internal_copy(il.begin(), il.end(), il.size());
926 #endif //__TBB_INITIALIZER_LISTS_PRESENT 934 internal_copy(table);
939 #if __TBB_CPP11_RVALUE_REF_PRESENT 944 internal_move_assign(
std::move(table), pocma_type());
948 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 950 #if __TBB_INITIALIZER_LISTS_PRESENT 954 internal_copy(il.begin(), il.end(), il.size());
957 #endif //__TBB_INITIALIZER_LISTS_PRESENT 963 void rehash(size_type n = 0);
974 range_type
range( size_type grainsize=1 ) {
975 return range_type( *
this, grainsize );
977 const_range_type
range( size_type grainsize=1 )
const {
978 return const_range_type( *
this, grainsize );
984 iterator
begin() {
return iterator( *
this, 0, my_embedded_segment, my_embedded_segment->
node_list ); }
985 iterator
end() {
return iterator( *
this, 0, 0, 0 ); }
986 const_iterator
begin()
const {
return const_iterator( *
this, 0, my_embedded_segment, my_embedded_segment->
node_list ); }
987 const_iterator
end()
const {
return const_iterator( *
this, 0, 0, 0 ); }
988 std::pair<iterator, iterator>
equal_range(
const Key&
key ) {
return internal_equal_range( key,
end() ); }
989 std::pair<const_iterator, const_iterator>
equal_range(
const Key&
key )
const {
return internal_equal_range( key,
end() ); }
992 size_type
size()
const {
return my_size; }
995 bool empty()
const {
return my_size == 0; }
1015 return const_cast<concurrent_hash_map*
>(
this)->lookup(
false, key, NULL, NULL,
false, &do_not_allocate_node );
1022 return const_cast<concurrent_hash_map*
>(
this)->lookup(
false, key, NULL, &result,
false, &do_not_allocate_node );
1029 return lookup(
false, key, NULL, &result,
true, &do_not_allocate_node );
1036 return lookup(
true, key, NULL, &result,
false, &allocate_node_default_construct );
1043 return lookup(
true, key, NULL, &result,
true, &allocate_node_default_construct );
1050 return lookup(
true, value.first, &value.second, &result,
false, &allocate_node_copy_construct );
1057 return lookup(
true, value.first, &value.second, &result,
true, &allocate_node_copy_construct );
1063 return lookup(
true, value.first, &value.second, NULL,
false, &allocate_node_copy_construct );
1066 #if __TBB_CPP11_RVALUE_REF_PRESENT 1085 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 1088 template<
typename... Args>
1090 return generic_emplace(result, std::forward<Args>(args)...);
1095 template<
typename... Args>
1097 return generic_emplace(result, std::forward<Args>(args)...);
1102 template<
typename... Args>
1106 #endif //__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 1107 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 1110 template<
typename I>
1116 #if __TBB_INITIALIZER_LISTS_PRESENT 1117 void insert( std::initializer_list<value_type> il ) {
1119 insert( il.begin(), il.end() );
1121 #endif //__TBB_INITIALIZER_LISTS_PRESENT 1125 bool erase(
const Key&
key );
1130 return exclude( item_accessor );
1136 return exclude( item_accessor );
1141 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 ) ;
1151 #if __TBB_CPP11_RVALUE_REF_PRESENT 1152 template<
typename Accessor>
1155 return lookup(
true,
value.first, &
value.second, accessor_location(result), is_write_access_needed(result), &allocate_node_move_construct );
1158 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 1159 template<
typename Accessor,
typename... Args>
1162 node * node_ptr = create_node(my_allocator, std::forward<Args>(args)...);
1163 return lookup(
true, node_ptr->
value().first, NULL, accessor_location(result), is_write_access_needed(result), &do_not_allocate_node, node_ptr );
1165 #endif //__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 1166 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 1172 template<
typename I>
1173 std::pair<I, I> internal_equal_range(
const Key& key, I
end )
const;
1178 template<
typename I>
1179 void internal_copy( I first, I last, size_type reserve_size );
1181 #if __TBB_CPP11_RVALUE_REF_PRESENT 1189 if (this->my_allocator == other.my_allocator) {
1193 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()), other.size());
1202 hashcode_t
h = my_hash_compare.hash( key );
1206 __TBB_ASSERT((m&(m+1))==0,
"data structure is invalid");
1207 bucket *b = get_bucket( h & m );
1212 if( lock.try_acquire( b->
mutex,
true ) ) {
1216 else lock.acquire( b->
mutex,
false );
1219 n = search_bucket( key, b );
1222 else if( check_mask_race( h, m ) )
1228 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 1232 template<
template<
typename...>
typename Map,
typename Key,
typename T,
typename... Args>
1233 using hash_map_t = Map<
1235 std::conditional_t< (
sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
1237 std::conditional_t< (
sizeof...(Args)>0) && is_allocator_v< pack_element_t<
sizeof...(Args)-1, Args...> >,
1243 template<
typename I,
typename... Args>
1245 -> internal::hash_map_t<concurrent_hash_map, internal::iterator_key_t<I>,internal::iterator_mapped_t<I>, Args...>;
1249 template<
typename Key,
typename T,
typename CompareOrAllocator>
1251 -> internal::hash_map_t<concurrent_hash_map, Key, T, CompareOrAllocator>;
1255 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1256 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*),
node *tmp_n ) {
1259 hashcode_t
const h = my_hash_compare.hash( key );
1261 segment_index_t grow_segment = 0;
1265 __TBB_ASSERT((m&(m+1))==0,
"data structure is invalid");
1266 return_value =
false;
1271 n = search_bucket( key, b() );
1276 tmp_n = allocate_node(my_allocator, key, t);
1278 if( !b.
is_writer() && !b.upgrade_to_writer() ) {
1280 n = search_bucket( key, b() );
1282 b.downgrade_to_reader();
1286 if( check_mask_race(h, m) )
1289 grow_segment = insert_new_node( b(), n = tmp_n, m );
1291 return_value =
true;
1295 if( check_mask_race( h, m ) )
1299 return_value =
true;
1302 if( !result )
goto check_growth;
1305 if( !result->try_acquire( n->mutex, write ) ) {
1307 if( result->try_acquire( n->mutex, write ) )
break;
1308 if( !backoff.bounded_pause() ) {
1311 __TBB_ASSERT( !op_insert || !return_value,
"Can't acquire new item in locked bucket?" );
1323 if( grow_segment ) {
1324 #if __TBB_STATISTICS 1327 enable_segment( grow_segment, my_allocator );
1330 delete_node( tmp_n );
1331 return return_value;
1334 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1335 template<
typename I>
1337 hashcode_t
h = my_hash_compare.hash( key );
1338 hashcode_t m = my_mask;
1339 __TBB_ASSERT((m&(m+1))==0,
"data structure is invalid");
1341 bucket *b = get_bucket( h );
1344 b = get_bucket( h &= m );
1346 node *n = search_bucket( key, b );
1348 return std::make_pair(end_, end_);
1349 iterator lower(*
this, h, b, n), upper(lower);
1350 return std::make_pair(lower, ++upper);
1353 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1356 node_base *
const n = item_accessor.
my_node;
1357 hashcode_t
const h = item_accessor.
my_hash;
1362 node_base **
p = &b()->node_list;
1363 while( *p && *p != n )
1366 if( check_mask_race( h, m ) )
1377 item_accessor.upgrade_to_writer();
1383 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1386 hashcode_t
const h = my_hash_compare.hash( key );
1393 node_base **
p = &b()->node_list;
1395 while( is_valid(n) && !my_hash_compare.equal(key, static_cast<node*>(n)->value().first ) ) {
1400 if( check_mask_race( h, m ) )
1404 else if( !b.
is_writer() && !b.upgrade_to_writer() ) {
1405 if( check_mask_race( h, m ) )
1413 typename node::scoped_t item_locker( n->
mutex,
true );
1420 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1427 internal_swap(table);
1431 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1433 reserve( sz, my_allocator );
1434 hashcode_t
mask = my_mask;
1435 hashcode_t b = (mask+1)>>1;
1437 bucket *bp = get_bucket( b );
1438 for(; b <=
mask; b++, bp++ ) {
1441 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->
mutex) == 0,
"concurrent or unexpectedly terminated operation during rehash() execution" );
1443 hashcode_t
h = b;
bucket *b_old = bp;
1445 __TBB_ASSERT( h > 1,
"The lowermost buckets can't be rehashed" );
1447 b_old = get_bucket( h &= m );
1450 mark_rehashed_levels( h );
1451 for( node_base **
p = &b_old->
node_list, *q = *
p; is_valid(q); q = *
p ) {
1452 hashcode_t c = my_hash_compare.hash( static_cast<node*>(q)->
value().first );
1453 if( (c & mask) != h ) {
1455 bucket *b_new = get_bucket( c & mask );
1457 add_to_bucket( b_new, q );
1458 }
else p = &q->next;
1462 #if TBB_USE_PERFORMANCE_WARNINGS 1463 int current_size =
int(my_size), buckets =
int(mask)+1, empty_buckets = 0, overpopulated_buckets = 0;
1464 static bool reported =
false;
1466 #if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS 1467 for( b = 0; b <=
mask; b++ ) {
1468 if( b & (b-2) ) ++bp;
1469 else bp = get_bucket( b );
1471 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->
mutex) == 0,
"concurrent or unexpectedly terminated operation during rehash() execution" );
1473 #if TBB_USE_PERFORMANCE_WARNINGS 1475 else if( n->
next ) overpopulated_buckets++;
1478 for( ; is_valid(n); n = n->
next ) {
1479 hashcode_t
h = my_hash_compare.hash( static_cast<node*>(n)->
value().first ) &
mask;
1480 __TBB_ASSERT( h == b,
"hash() function changed for key in table or internal error" );
1484 #endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS 1485 #if TBB_USE_PERFORMANCE_WARNINGS 1486 if( buckets > current_size) empty_buckets -= buckets - current_size;
1487 else overpopulated_buckets -= current_size - buckets;
1488 if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
1490 "Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
1492 typeid(*this).name(),
1494 "concurrent_hash_map",
1496 current_size, empty_buckets, overpopulated_buckets );
1502 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1504 hashcode_t m = my_mask;
1505 __TBB_ASSERT((m&(m+1))==0,
"data structure is invalid");
1506 #if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1507 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1508 int current_size =
int(my_size), buckets =
int(m)+1, empty_buckets = 0, overpopulated_buckets = 0;
1509 static bool reported =
false;
1513 for( segment_index_t b = 0; b <= m; b++ ) {
1514 if( b & (b-2) ) ++bp;
1515 else bp = get_bucket( b );
1518 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->
mutex) == 0,
"concurrent or unexpectedly terminated operation during clear() execution" );
1519 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1522 else if( n->
next ) overpopulated_buckets++;
1524 #if __TBB_EXTRA_DEBUG 1525 for(; is_valid(n); n = n->
next ) {
1526 hashcode_t
h = my_hash_compare.hash( static_cast<node*>(n)->
value().first );
1532 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1533 #if __TBB_STATISTICS 1534 printf(
"items=%d buckets: capacity=%d rehashed=%d empty=%d overpopulated=%d" 1535 " concurrent: resizes=%u rehashes=%u restarts=%u\n",
1536 current_size,
int(m+1), buckets, empty_buckets, overpopulated_buckets,
1537 unsigned(my_info_resizes),
unsigned(my_info_rehashes),
unsigned(my_info_restarts) );
1538 my_info_resizes = 0;
1539 my_info_restarts = 0;
1540 my_info_rehashes = 0;
1542 if( buckets > current_size) empty_buckets -= buckets - current_size;
1543 else overpopulated_buckets -= current_size - buckets;
1544 if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
1546 "Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
1548 typeid(*this).name(),
1550 "concurrent_hash_map",
1552 current_size, empty_buckets, overpopulated_buckets );
1556 #endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1558 segment_index_t
s = segment_index_of( m );
1559 __TBB_ASSERT( s+1 == pointers_per_table || !my_table[s+1],
"wrong mask or concurrent grow" );
1561 __TBB_ASSERT( is_valid( my_table[s] ),
"wrong mask or concurrent grow" );
1562 segment_ptr_t buckets_ptr = my_table[
s];
1563 size_type sz = segment_size( s ? s : 1 );
1564 for( segment_index_t i = 0; i < sz; i++ )
1565 for( node_base *n = buckets_ptr[i].node_list; is_valid(n); n = buckets_ptr[i].
node_list ) {
1569 delete_segment(s, my_allocator);
1571 my_mask = embedded_buckets - 1;
1574 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1577 if( my_mask == mask ) {
1578 reserve( source.
my_size, my_allocator );
1579 bucket *dst = 0, *src = 0;
1580 bool rehash_required =
false;
1581 for( hashcode_t k = 0; k <=
mask; k++ ) {
1582 if( k & (k-2) ) ++dst,src++;
1583 else { dst = get_bucket( k ); src = source.
get_bucket( k ); }
1585 node *n =
static_cast<node*
>( src->node_list );
1587 rehash_required =
true;
1589 }
else for(; n; n =
static_cast<node*
>( n->next ) ) {
1590 node* node_ptr = create_node(my_allocator, n->
value().first, n->
value().second);
1591 add_to_bucket( dst, node_ptr);
1595 if( rehash_required ) rehash();
1599 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1600 template<
typename I>
1602 reserve( reserve_size, my_allocator );
1603 hashcode_t m = my_mask;
1605 hashcode_t
h = my_hash_compare.hash( (*first).first );
1606 bucket *b = get_bucket( h & m );
1608 node* node_ptr = create_node(my_allocator, (*first).first, (*first).second);
1609 add_to_bucket( b, node_ptr );
1619 template<
typename Key,
typename T,
typename HashCompare,
typename A1,
typename A2>
1621 if(a.
size() != b.
size())
return false;
1624 for(; i != i_end; ++i) {
1626 if( j == j_end || !(i->second == j->second) )
return false;
1631 template<
typename Key,
typename T,
typename HashCompare,
typename A1,
typename A2>
1633 {
return !(a == b); }
1635 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1639 #if _MSC_VER && !defined(__INTEL_COMPILER) 1640 #pragma warning( pop ) 1641 #endif // warning 4127 is back 1646 #undef __TBB_concurrent_hash_map_H_include_area size_t size_type
Size type.
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int mask
void enable_segment(segment_index_t k, const Allocator &allocator, bool is_initial=false)
Enable segment.
Iterator::map_type map_type
hash_map_iterator operator++(int)
Post increment.
node_allocator_type & my_alloc
std::pair< I, I > internal_equal_range(const Key &key, I end) const
Returns an iterator for an item defined by the key, or for the next item after it (if upper==true) ...
pointer operator->() const
Return pointer to associated value in hash table.
const_reference operator*() const
Return reference to associated value in hash table.
node_allocator_type my_allocator
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void * lock
void move(tbb_thread &t1, tbb_thread &t2)
const concurrent_hash_map::value_type value_type
Type of value.
bool empty() const
True if result is empty.
void internal_move_assign(concurrent_hash_map &&other, tbb::internal::traits_false_type)
void itt_hide_store_word(T &dst, T src)
concurrent_hash_map(const concurrent_hash_map &table, const allocator_type &a)
hash_map_base::size_type size_type
bool generic_move_insert(Accessor &&result, value_type &&value)
Value * operator->() const
hash_map_iterator(const hash_map_iterator< Container, typename Container::value_type > &other)
concurrent_hash_map(I first, I last, const HashCompare &compare, const allocator_type &a=allocator_type())
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.
bool operator==(const hash_map_iterator< Container, T > &i, const hash_map_iterator< Container, U > &j)
size_type max_size() const
Upper bound on size.
Combines data access, locking, and garbage collection.
std::pair< iterator, iterator > equal_range(const Key &key)
void const char const char int ITT_FORMAT __itt_group_sync s
Dummy type that distinguishes splitting constructor from copy constructor.
bool empty() const
True if size()==0.
bool insert(const_accessor &result, const value_type &value)
Insert item by copying if there is no such key present already and acquire a read lock on the item...
friend bool operator==(const hash_map_iterator< C, T > &i, const hash_map_iterator< C, U > &j)
bool is_writer
If mutex!=NULL, then is_writer is true if holding a writer lock, false if holding a reader lock...
range_type range(size_type grainsize=1)
bool check_rehashing_collision(const hashcode_t h, hashcode_t m_old, hashcode_t m) const
Process mask race, check for rehashing collision.
const_range_type range(size_type grainsize=1) const
static void init_buckets(segment_ptr_t ptr, size_type sz, bool is_initial)
Initialize buckets.
const Iterator & begin() const
void __TBB_store_with_release(volatile T &location, V value)
bool emplace(Args &&... args)
Insert item by copying if there is no such key present already.
Class that implements exponential backoff.
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
bool operator!=(const hash_map_iterator< Container, T > &i, const hash_map_iterator< Container, U > &j)
void set_midpoint() const
Set my_midpoint to point approximately half way between my_begin and my_end.
void internal_move_assign(concurrent_hash_map &&other, tbb::internal::traits_true_type)
mutex_t::scoped_lock scoped_t
Scoped lock type for mutex.
size_type bucket_count() const
Returns the current number of buckets.
internal::hash_map_range< const_iterator > const_range_type
The scoped locking pattern.
size_t segment_index_t
Segment index type.
size_t hashcode_t
Type of a hash code.
size_type grainsize() const
The grain size for this range.
size_type size() const
Number of items in table.
concurrent_hash_map & operator=(const concurrent_hash_map &table)
Assignment.
concurrent_hash_map(size_type n, const allocator_type &a=allocator_type())
Construct empty table with n preallocated buckets. This number serves also as initial concurrency lev...
void delete_segment(segment_index_t s, const Allocator &allocator)
bool insert(const value_type &value)
Insert item by copying if there is no such key present already.
size_t my_index
Index in hash table for current item.
bool insert(const_accessor &result, const Key &key)
Insert item (if not already present) and acquire a read lock on the item.
spin_rw_mutex mutex_t
Mutex type.
concurrent_hash_map * my_ch_map
size_t hashcode_t
Type of a hash code.
#define __TBB_FORWARDING_REF(A)
hash_map_range(hash_map_range< U > &r)
type conversion
bool emplace(const_accessor &result, Args &&... args)
Insert item by copying if there is no such key present already and acquire a read lock on the item...
bool erase(const_accessor &item_accessor)
Erase item by const_accessor.
const_pointer internal_fast_find(const Key &key) const
Fast find when no concurrent erasure is used. For internal use inside TBB only!
hash_map_range(const map_type &map, size_type grainsize_=1)
Init range with container and grainsize specified.
static bool is_valid(void *ptr)
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
friend const_accessor * accessor_location(const_accessor &a)
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void ITT_FORMAT p const __itt_domain __itt_id __itt_string_handle const wchar_t size_t ITT_FORMAT lu const __itt_domain __itt_id __itt_relation __itt_id ITT_FORMAT p const wchar_t int ITT_FORMAT __itt_group_mark d int
void advance_to_next_bucket()
bool erase(const Key &key)
Erase item.
Allows write access to elements and combines data access, locking, and garbage collection.
bool emplace(accessor &result, Args &&... args)
Insert item by copying if there is no such key present already and acquire a write lock on the item...
node * my_node
Pointer to node that has current item.
concurrent_hash_map(concurrent_hash_map &&table, const allocator_type &a)
Move constructor.
bucket_accessor(concurrent_hash_map *base, const hashcode_t h, bool writer=false)
intptr_t __TBB_Log2(uintptr_t x)
static hash_map_node_base *const rehash_req
Incompleteness flag value.
tbb::internal::allocator_traits< node_allocator_type > node_allocator_traits
bucket * segment_ptr_t
Segment pointer.
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
auto first(Container &c) -> decltype(begin(c))
hash_compare that is default argument for concurrent_hash_map
bool find(accessor &result, const Key &key)
Find item and acquire a write lock on the item.
concurrent_hash_map(size_type n, const HashCompare &compare, const allocator_type &a=allocator_type())
friend bool is_write_access_needed(accessor const &)
internal::hash_map_range< iterator > range_type
bool insert(value_type &&value)
Insert item by copying if there is no such key present already.
allocator_traits< Alloc >::template rebind_alloc< T >::other type
atomic< T > & as_atomic(T &t)
std::pair< const Key, T > value_type
node_scoped_guard(node *n, node_allocator_type &alloc)
Iterator::reference reference
enable_segment_failsafe(segments_table_t &table, segment_index_t k)
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)
Insert or find item and optionally acquire a lock on the item.
size_type count(const Key &key) const
Return count of items (0 or 1)
auto last(Container &c) -> decltype(begin(c))
Iterator::value_type value_type
Meets requirements of a forward iterator for STL */.
ptrdiff_t difference_type
~const_accessor()
Destroy result after releasing the underlying reference.
static node * allocate_node_default_construct(node_allocator_type &allocator, const Key &key, const T *)
const value_type * const_pointer
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function h
Unordered map from Key to T.
segment_index_t insert_new_node(bucket *b, node_base *n, hashcode_t mask)
Insert a node and check for load factor.
bool is_writer()
check whether bucket is locked for write
hash_map_range(hash_map_range &r, split)
Split range.
void reserve(size_type buckets, const Allocator &allocator)
Prepare enough segments for number of buckets.
void internal_move(hash_map_base &&other)
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp end
concurrent_hash_map::value_type value_type
Type of value.
hash_map_iterator & operator=(const hash_map_iterator< Container, typename Container::value_type > &other)
T itt_hide_load_word(const T &src)
segment_ptr_t * my_segment_ptr
const Container * my_map
concurrent_hash_map over which we are iterating.
static node * do_not_allocate_node(node_allocator_type &, const Key &, const T *)
Base class for types that should not be copied or assigned.
internal::hash_map_iterator< concurrent_hash_map, value_type > iterator
spin_rw_mutex mutex_t
Mutex type for buckets.
bool insert(accessor &result, const Key &key)
Insert item (if not already present) and acquire a write lock on the item.
const_iterator end() const
void acquire(concurrent_hash_map *base, const hashcode_t h, bool writer=false)
find a bucket by masked hashcode, optionally rehash, and acquire the lock
bool insert(accessor &result, value_type &&value)
Insert item by copying if there is no such key present already and acquire a write lock on the item...
Identifiers declared inside namespace internal should never be used directly by client code...
Range class used with concurrent_hash_map.
bool insert(accessor &result, const value_type &value)
Insert item by copying if there is no such key present already and acquire a write lock on the item...
bool empty() const
True if range is empty.
HashCompare my_hash_compare
reference operator*() const
Return reference to associated value in hash table.
void acquire(spin_rw_mutex &m, bool write=true)
Acquire lock on given mutex.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
std::size_t size_type
Type for size of a range.
void rehash(size_type n=0)
Rehashes and optionally resizes the whole table.
concurrent_hash_map(const concurrent_hash_map &table)
Copy constructor.
hash_map_node_base * next
Next node in chain.
base class of concurrent_hash_map
atomic< size_type > my_size
Size of container in stored items.
static node * create_node(node_allocator_type &allocator, Args &&... args)
static node * allocate_node_copy_construct(node_allocator_type &allocator, const Key &key, const T *t)
hash_map_iterator()
Construct undefined iterator.
#define __TBB_USE_OPTIONAL_RTTI
~concurrent_hash_map()
Clear table and destroy it.
bucket my_embedded_segment[embedded_buckets]
Zero segment.
const_iterator begin() const
void release()
Set to null.
void mark_rehashed_levels(hashcode_t h)
void swap(concurrent_hash_map &table)
swap two instances. Iterators are invalidated
hash_map_base::bucket bucket
Iterator::difference_type difference_type
Value & operator*() const
concurrent_hash_map(const allocator_type &a=allocator_type())
Construct empty table.
mutex_t::scoped_lock scoped_t
Scoped lock type for mutex.
bool check_mask_race(const hashcode_t h, hashcode_t &m) const
Check for mask race.
void const char const char int ITT_FORMAT __itt_group_sync p
tick_count::interval_t operator-(const tick_count &t1, const tick_count &t0)
static segment_index_t segment_base(segment_index_t k)
node * search_bucket(const key_type &key, bucket *b) const
void delete_node(node_base *n)
~enable_segment_failsafe()
T __TBB_load_with_acquire(const volatile T &location)
bool insert(const_accessor &result, value_type &&value)
Insert item by copying if there is no such key present already and acquire a read lock on the item...
friend bool is_write_access_needed(accessor_not_used const &)
segments_table_t my_table
Segment pointers table. Also prevents false sharing between my_mask and my_size.
bool is_divisible() const
True if range can be partitioned into two subranges.
const Iterator & end() const
hash_map_base::node_base node_base
static node * allocate_node_move_construct(node_allocator_type &allocator, const Key &key, const T *t)
void internal_swap(hash_map_base &table)
Swap hash_map_bases.
bool exclude(const_accessor &item_accessor)
delete item by accessor
const_pointer operator->() const
Return pointer to associated value in hash table.
static hash_map_node_base *const empty_rehashed
Rehashed empty bucket flag.
concurrent_hash_map(std::initializer_list< value_type > il, const HashCompare &compare, const allocator_type &a=allocator_type())
Fast, unfair, spinning reader-writer lock with backoff and writer-preference.
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
const_accessor()
Create empty result.
concurrent_hash_map(I first, I last, const allocator_type &a=allocator_type())
Construction with copying iteration range and given allocator instance.
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.
bucket accessor is to find, rehash, acquire a lock, and access a bucket
const value_type & const_reference
hash_map_node_base node_base
Node base type.
static void add_to_bucket(bucket *b, node_base *n)
Add node.
T itt_load_word_with_acquire(const tbb::atomic< T > &src)
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
static segment_index_t segment_index_of(size_type index)
void __TBB_EXPORTED_FUNC runtime_warning(const char *format,...)
Report a runtime warning.
hash_map_iterator & operator++()
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
void rehash_bucket(bucket *b_new, const hashcode_t h)
allocator_type get_allocator() const
return allocator object
call_clear_on_leave(concurrent_hash_map *a_ch_map)
void insert(I first, I last)
Insert range [first, last)
friend bool is_write_access_needed(const_accessor const &)
friend const_accessor * accessor_location(accessor_not_used const &)
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
bool generic_emplace(Accessor &&result, Args &&... args)
bool erase(accessor &item_accessor)
Erase item by accessor.
internal::hash_map_iterator< concurrent_hash_map, const value_type > const_iterator
const bucket * my_bucket
Pointer to bucket.
tbb::aligned_space< value_type > my_value
friend bool operator!=(const hash_map_iterator< C, T > &i, const hash_map_iterator< C, U > &j)
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
tbb::internal::allocator_rebind< Allocator, node >::type node_allocator_type
concurrent_hash_map(const HashCompare &compare, const allocator_type &a=allocator_type())
bool find(const_accessor &result, const Key &key) const
Find item and acquire a read lock on the item.
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
static size_type segment_size(segment_index_t k)