21 #ifndef __TBB_concurrent_hash_map_H 22 #define __TBB_concurrent_hash_map_H 28 #include __TBB_STD_SWAP_HEADER 39 #if __TBB_INITIALIZER_LISTS_PRESENT 40 #include <initializer_list> 42 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 48 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_TUPLE_PRESENT 56 namespace interface5 {
58 template<
typename Key,
typename T,
typename HashCompare = tbb_hash_compare<Key>,
typename A = tbb_allocator<std::pair<const Key, T> > >
105 static size_type const embedded_buckets = 1<<embedded_block;
121 bucket my_embedded_segment[embedded_buckets];
129 std::memset(
this, 0, pointers_per_table*
sizeof(
segment_ptr_t)
130 +
sizeof(my_size) +
sizeof(my_mask)
131 + embedded_buckets*
sizeof(
bucket) );
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;
160 return reinterpret_cast<uintptr_t>(ptr) > uintptr_t(63);
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>
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);
217 template<
typename Allocator>
221 bucket_allocator_type bucket_allocator(allocator);
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;
236 h -= segment_base(
s);
238 __TBB_ASSERT( is_valid(seg),
"hashcode must be cut by valid mask for allocated segments" );
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;
287 add_to_bucket( b, n );
291 __TBB_ASSERT( is_valid(my_table[new_seg-1]),
"new allocations must not publish new mask until segment has allocated");
294 &&
as_atomic(my_table[new_seg]).compare_and_swap(is_allocating, NULL) == NULL )
301 template<
typename 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++)
320 template<
typename Iterator>
326 template<
typename Container,
typename Value>
328 :
public std::iterator<std::forward_iterator_tag,Value>
331 typedef typename Container::node
node;
335 template<
typename C,
typename T,
typename U>
338 template<
typename C,
typename T,
typename U>
341 template<
typename C,
typename T,
typename U>
344 template<
typename C,
typename U>
351 size_t k = my_index+1;
352 __TBB_ASSERT( my_bucket,
"advancing an invalid iterator?");
353 while( k <= my_map->my_mask ) {
357 else my_bucket = my_map->get_bucket( k );
358 my_node = static_cast<node*>( my_bucket->node_list );
360 my_index = k;
return;
364 my_bucket = 0; my_node = 0; my_index = k;
366 #if !defined(_MSC_VER) || defined(__INTEL_COMPILER) 367 template<
typename Key,
typename T,
typename HashCompare,
typename A>
372 const Container *my_map;
390 my_map(other.my_map),
391 my_index(other.my_index),
392 my_bucket(other.my_bucket),
393 my_node(other.my_node)
397 return my_node->value();
410 template<
typename Container,
typename Value>
415 my_node( static_cast<
node*>(n) )
421 template<
typename Container,
typename Value>
423 my_node = static_cast<node*>( my_node->next );
424 if( !my_node ) advance_to_next_bucket();
428 template<
typename Container,
typename T,
typename U>
433 template<
typename Container,
typename T,
typename U>
440 template<
typename Iterator>
441 class hash_map_range {
470 r.my_end =
my_begin = r.my_midpoint;
472 __TBB_ASSERT( !r.empty(),
"Splitting despite the range is not divisible" );
486 my_begin( Iterator( map, 0, map.my_embedded_segment, map.my_embedded_segment->node_list ) ),
487 my_end( Iterator( map, map.my_mask + 1, 0, 0 ) ),
490 __TBB_ASSERT( grainsize_>0,
"grainsize must be positive" );
499 template<
typename Iterator>
502 size_t m = my_end.my_index-my_begin.my_index;
503 if( m > my_grainsize ) {
504 m = my_begin.my_index + m/2u;
506 my_midpoint = Iterator(*my_begin.my_map,m,b,b->
node_list);
508 my_midpoint = my_end;
510 __TBB_ASSERT( my_begin.my_index <= my_midpoint.my_index,
511 "my_begin is after my_midpoint" );
513 "my_midpoint is after my_end" );
514 __TBB_ASSERT( my_begin != my_midpoint || my_begin == my_end,
515 "[my_begin, my_midpoint) range should not be empty" );
521 #if _MSC_VER && !defined(__INTEL_COMPILER) 523 #pragma warning( push ) 524 #pragma warning( disable: 4127 ) 557 template<
typename Key,
typename T,
typename HashCompare,
typename Allocator>
559 template<
typename Container,
typename Value>
575 typedef internal::hash_map_iterator<concurrent_hash_map,value_type>
iterator;
576 typedef internal::hash_map_iterator<concurrent_hash_map,const value_type>
const_iterator;
616 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 617 template<
typename... Args>
620 template<
typename Arg1,
typename Arg2>
627 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 640 #if __TBB_CPP11_RVALUE_REF_PRESENT 647 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_TUPLE_PRESENT 649 return create_node(allocator, std::piecewise_construct,
650 std::forward_as_tuple(
key), std::forward_as_tuple());
658 __TBB_ASSERT(
false,
"this dummy function should not be called");
665 n = static_cast<node*>( n->next );
680 && try_acquire(
my_b->mutex,
true ) )
688 bool is_writer() {
return bucket::scoped_t::is_writer; }
696 __TBB_ASSERT(
h > 1,
"The lowermost buckets can't be rehashed" );
712 bmask = bmask==0? 1 : ( 1u<<(
__TBB_Log2( bmask )+1 ) ) - 1;
713 __TBB_ASSERT( (c & bmask) == (
h & bmask),
"hash() function changed for key in table" );
715 if( (c &
mask) ==
h ) {
717 if( !b_old.upgrade_to_writer() ) {
831 #if __TBB_CPP11_RVALUE_REF_PRESENT 851 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 872 #if __TBB_INITIALIZER_LISTS_PRESENT 877 call_clear_on_leave scope_guard(
this);
879 scope_guard.dismiss();
890 #endif //__TBB_INITIALIZER_LISTS_PRESENT 901 #if __TBB_CPP11_RVALUE_REF_PRESENT 913 this->
swap(moved_copy);
918 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 920 #if __TBB_INITIALIZER_LISTS_PRESENT 927 #endif //__TBB_INITIALIZER_LISTS_PRESENT 992 return const_cast<concurrent_hash_map*>(
this)->lookup(
false,
key, NULL, &result,
false, &
do_not_allocate_node );
1036 #if __TBB_CPP11_RVALUE_REF_PRESENT 1055 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 1058 template<
typename... Args>
1065 template<
typename... Args>
1072 template<
typename... Args>
1076 #endif //__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 1077 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 1080 template<
typename I>
1086 #if __TBB_INITIALIZER_LISTS_PRESENT 1087 void insert( std::initializer_list<value_type> il ) {
1089 insert( il.begin(), il.end() );
1091 #endif //__TBB_INITIALIZER_LISTS_PRESENT 1100 return exclude( item_accessor );
1106 return exclude( item_accessor );
1121 #if __TBB_CPP11_RVALUE_REF_PRESENT 1122 template<
typename Accessor>
1128 #if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 1129 template<
typename Accessor,
typename... Args>
1135 #endif //__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT 1136 #endif //__TBB_CPP11_RVALUE_REF_PRESENT 1142 template<
typename I>
1148 template<
typename I>
1159 __TBB_ASSERT((m&(m+1))==0,
"data structure is invalid");
1165 if(
lock.try_acquire( b->
mutex,
true ) ) {
1167 const_cast<concurrent_hash_map*>(
this)->rehash_bucket( b,
h & m );
1181 #if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT 1182 namespace internal {
1185 template<
template<
typename...>
typename Map,
typename Key,
typename T,
typename... Args>
1186 using hash_map_t = Map<
1188 std::conditional_t< (
sizeof...(Args)>0) && !is_allocator_v< pack_element_t<0, Args...> >,
1190 std::conditional_t< (
sizeof...(Args)>0) && is_allocator_v< pack_element_t<
sizeof...(Args)-1, Args...> >,
1196 template<
typename I,
typename... Args>
1197 concurrent_hash_map(I, I, Args...)
1198 -> internal::hash_map_t<concurrent_hash_map, internal::iterator_key_t<I>,internal::iterator_mapped_t<I>, Args...>;
1202 template<
typename Key,
typename T,
typename CompareOrAllocator>
1203 concurrent_hash_map(std::initializer_list<std::pair<const Key, T>>, CompareOrAllocator)
1204 -> internal::hash_map_t<concurrent_hash_map, Key, T, CompareOrAllocator>;
1208 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1209 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 ) {
1218 __TBB_ASSERT((m&(m+1))==0,
"data structure is invalid");
1219 return_value =
false;
1224 n = search_bucket(
key, b() );
1229 tmp_n = allocate_node(my_allocator,
key, t);
1231 if( !b.
is_writer() && !b.upgrade_to_writer() ) {
1233 n = search_bucket(
key, b() );
1235 b.downgrade_to_reader();
1239 if( check_mask_race(
h, m) )
1242 grow_segment = insert_new_node( b(), n = tmp_n, m );
1244 return_value =
true;
1248 if( check_mask_race(
h, m ) )
1252 return_value =
true;
1255 if( !result )
goto check_growth;
1258 if( !result->try_acquire( n->mutex, write ) ) {
1260 if( result->try_acquire( n->mutex, write ) )
break;
1261 if( !backoff.bounded_pause() ) {
1264 __TBB_ASSERT( !op_insert || !return_value,
"Can't acquire new item in locked bucket?" );
1276 if( grow_segment ) {
1277 #if __TBB_STATISTICS 1280 enable_segment( grow_segment, my_allocator );
1283 delete_node( tmp_n );
1284 return return_value;
1287 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1288 template<
typename I>
1292 __TBB_ASSERT((m&(m+1))==0,
"data structure is invalid");
1297 b = get_bucket(
h &= m );
1299 node *n = search_bucket(
key, b );
1301 return std::make_pair(end_, end_);
1302 iterator lower(*
this,
h, b, n), upper(lower);
1303 return std::make_pair(lower, ++upper);
1306 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1316 while( *
p && *
p != n )
1319 if( check_mask_race(
h, m ) )
1330 item_accessor.upgrade_to_writer();
1336 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1348 while( is_valid(n) && !my_hash_compare.equal(
key, static_cast<node*>(n)->value().first ) ) {
1353 if( check_mask_race(
h, m ) )
1357 else if( !b.
is_writer() && !b.upgrade_to_writer() ) {
1358 if( check_mask_race(
h, m ) )
1366 typename node::scoped_t item_locker( n->
mutex,
true );
1373 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1379 internal_swap(table);
1382 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1384 reserve( sz, my_allocator );
1388 bucket *bp = get_bucket( b );
1389 for(; b <=
mask; b++, bp++ ) {
1392 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->
mutex) == 0,
"concurrent or unexpectedly terminated operation during rehash() execution" );
1396 __TBB_ASSERT(
h > 1,
"The lowermost buckets can't be rehashed" );
1398 b_old = get_bucket(
h &= m );
1401 mark_rehashed_levels(
h );
1404 if( (c &
mask) !=
h ) {
1408 add_to_bucket( b_new, q );
1409 }
else p = &q->next;
1413 #if TBB_USE_PERFORMANCE_WARNINGS 1414 int current_size =
int(my_size), buckets =
int(
mask)+1, empty_buckets = 0, overpopulated_buckets = 0;
1415 static bool reported =
false;
1417 #if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS 1418 for( b = 0; b <=
mask; b++ ) {
1419 if( b & (b-2) ) ++bp;
1420 else bp = get_bucket( b );
1422 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->
mutex) == 0,
"concurrent or unexpectedly terminated operation during rehash() execution" );
1424 #if TBB_USE_PERFORMANCE_WARNINGS 1426 else if( n->
next ) overpopulated_buckets++;
1429 for( ; is_valid(n); n = n->
next ) {
1431 __TBB_ASSERT(
h == b,
"hash() function changed for key in table or internal error" );
1435 #endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS 1436 #if TBB_USE_PERFORMANCE_WARNINGS 1437 if( buckets > current_size) empty_buckets -= buckets - current_size;
1438 else overpopulated_buckets -= current_size - buckets;
1439 if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
1441 "Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
1443 typeid(*this).name(),
1445 "concurrent_hash_map",
1447 current_size, empty_buckets, overpopulated_buckets );
1453 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1456 __TBB_ASSERT((m&(m+1))==0,
"data structure is invalid");
1457 #if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1458 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1459 int current_size =
int(my_size), buckets =
int(m)+1, empty_buckets = 0, overpopulated_buckets = 0;
1460 static bool reported =
false;
1465 if( b & (b-2) ) ++bp;
1466 else bp = get_bucket( b );
1469 __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->
mutex) == 0,
"concurrent or unexpectedly terminated operation during clear() execution" );
1470 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1473 else if( n->
next ) overpopulated_buckets++;
1475 #if __TBB_EXTRA_DEBUG 1476 for(; is_valid(n); n = n->
next ) {
1483 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1484 #if __TBB_STATISTICS 1485 printf(
"items=%d buckets: capacity=%d rehashed=%d empty=%d overpopulated=%d" 1486 " concurrent: resizes=%u rehashes=%u restarts=%u\n",
1487 current_size,
int(m+1), buckets, empty_buckets, overpopulated_buckets,
1488 unsigned(my_info_resizes),
unsigned(my_info_rehashes),
unsigned(my_info_restarts) );
1489 my_info_resizes = 0;
1490 my_info_restarts = 0;
1491 my_info_rehashes = 0;
1493 if( buckets > current_size) empty_buckets -= buckets - current_size;
1494 else overpopulated_buckets -= current_size - buckets;
1495 if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
1497 "Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
1499 typeid(*this).name(),
1501 "concurrent_hash_map",
1503 current_size, empty_buckets, overpopulated_buckets );
1507 #endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS 1510 __TBB_ASSERT(
s+1 == pointers_per_table || !my_table[
s+1],
"wrong mask or concurrent grow" );
1512 __TBB_ASSERT( is_valid( my_table[
s] ),
"wrong mask or concurrent grow" );
1516 for(
node_base *n = buckets_ptr[i].node_list; is_valid(n); n = buckets_ptr[i].
node_list ) {
1520 delete_segment(
s, my_allocator);
1522 my_mask = embedded_buckets - 1;
1525 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1528 if( my_mask ==
mask ) {
1529 reserve( source.
my_size, my_allocator );
1530 bucket *dst = 0, *src = 0;
1531 bool rehash_required =
false;
1533 if( k & (k-2) ) ++dst,src++;
1534 else { dst = get_bucket( k ); src = source.
get_bucket( k ); }
1536 node *n = static_cast<node*>( src->node_list );
1538 rehash_required =
true;
1540 }
else for(; n; n = static_cast<node*>( n->next ) ) {
1541 node* node_ptr = create_node(my_allocator, n->
value().first, n->
value().second);
1542 add_to_bucket( dst, node_ptr);
1546 if( rehash_required ) rehash();
1550 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1551 template<
typename I>
1553 reserve( reserve_size, my_allocator );
1556 hashcode_t h = my_hash_compare.hash( (*first).first );
1557 bucket *b = get_bucket(
h & m );
1559 node* node_ptr = create_node(my_allocator, (*first).first, (*first).second);
1560 add_to_bucket( b, node_ptr );
1570 template<
typename Key,
typename T,
typename HashCompare,
typename A1,
typename A2>
1572 if(a.
size() != b.
size())
return false;
1575 for(; i != i_end; ++i) {
1577 if( j == j_end || !(i->second == j->second) )
return false;
1582 template<
typename Key,
typename T,
typename HashCompare,
typename A1,
typename A2>
1584 {
return !(a == b); }
1586 template<
typename Key,
typename T,
typename HashCompare,
typename A>
1590 #if _MSC_VER && !defined(__INTEL_COMPILER) 1591 #pragma warning( pop ) 1592 #endif // warning 4127 is back Meets requirements of a forward iterator for STL */.
~const_accessor()
Destroy result after releasing the underlying reference.
T itt_hide_load_word(const T &src)
void __TBB_EXPORTED_FUNC runtime_warning(const char *format,...)
Report a runtime warning.
hash_map_base::bucket bucket
Fast, unfair, spinning reader-writer lock with backoff and writer-preference.
Allows write access to elements and combines data access, locking, and garbage collection.
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 operator==(const cache_aligned_allocator< T > &, const cache_aligned_allocator< U > &)
internal::hash_map_range< const_iterator > const_range_type
node * my_node
Pointer to node that has current item.
size_t size_type
Size type.
bucket accessor is to find, rehash, acquire a lock, and access a bucket
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
concurrent_hash_map(size_type n, const HashCompare &compare, const allocator_type &a=allocator_type())
allocator_type get_allocator() const
return allocator object
friend bool is_write_access_needed(const_accessor const &)
size_t hashcode_t
Type of a hash code.
bool check_rehashing_collision(const hashcode_t h, hashcode_t m_old, hashcode_t m) const
Process mask race, check for rehashing collision.
void delete_node(node_base *n)
const Container * my_map
concurrent_hash_map over which we are iterating.
size_type size() const
Number of items in table.
friend bool is_write_access_needed(accessor_not_used const &)
T __TBB_load_with_acquire(const volatile T &location)
static node * allocate_node_move_construct(node_allocator_type &allocator, const Key &key, const T *t)
const concurrent_hash_map::value_type value_type
Type of value.
const Iterator & begin() const
const_pointer operator->() const
Return pointer to associated value in hash table.
T * begin() const
Pointer to beginning of array.
bool emplace(Args &&... args)
Insert item by copying if there is no such key present already.
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
void set_midpoint() const
Set my_midpoint to point approximately half way between my_begin and my_end.
friend class internal::hash_map_range
bool is_writer()
check whether bucket is locked for write
bool generic_move_insert(Accessor &&result, value_type &&value)
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
tbb::aligned_space< value_type > my_value
const_pointer internal_fast_find(const Key &key) const
Fast find when no concurrent erasure is used. For internal use inside TBB only!
size_type count(const Key &key) const
Return count of items (0 or 1)
concurrent_hash_map(I first, I last, const allocator_type &a=allocator_type())
Construction with copying iteration range and given allocator instance.
std::pair< iterator, iterator > equal_range(const Key &key)
tick_count::interval_t operator-(const tick_count &t1, const tick_count &t0)
size_type grainsize() const
The grain size for this range.
pointer operator->() const
Return pointer to associated value in hash table.
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
Iterator::map_type map_type
auto first(Container &c) -> decltype(begin(c))
Unordered map from Key to T.
bool empty() const
True if result is empty.
hash_map_range(hash_map_range &r, split)
Split range.
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
concurrent_hash_map * my_ch_map
Iterator::reference reference
bool erase(const_accessor &item_accessor)
Erase item by const_accessor.
allocator_traits< Alloc >::template rebind_alloc< T >::other type
ptrdiff_t difference_type
size_t segment_index_t
Segment index type.
void insert(I first, I last)
Insert range [first, last)
Base class for types that should not be copied or assigned.
static bool is_valid(void *ptr)
const_iterator end() const
friend const_accessor * accessor_location(const_accessor &a)
T itt_load_word_with_acquire(const tbb::atomic< T > &src)
Range class used with concurrent_hash_map.
static void add_to_bucket(bucket *b, node_base *n)
Add node.
bool generic_emplace(Accessor &&result, Args &&... args)
size_t my_index
Index in hash table for current item.
base class of concurrent_hash_map
spin_rw_mutex mutex_t
Mutex type.
tbb::internal::allocator_rebind< Allocator, node >::type node_allocator_type
bool find(const_accessor &result, const Key &key) const
Find item and acquire a read lock on the item.
~concurrent_hash_map()
Clear table and destroy it.
~enable_segment_failsafe()
static pointer allocate(Alloc &a, size_type n)
hash_map_range(const map_type &map, size_type grainsize_=1)
Init range with container and grainsize specified.
hash_compare that is default argument for concurrent_hash_map
hash_map_base()
Constructor.
void const char const char int ITT_FORMAT __itt_group_sync p
Iterator::difference_type difference_type
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.
static void deallocate(Alloc &a, pointer p, size_type n)
const_range_type range(size_type grainsize=1) const
static void construct(Alloc &, PT *p)
Value & operator*() const
void delete_segment(segment_index_t s, const Allocator &allocator)
node * search_bucket(const key_type &key, bucket *b) const
atomic< size_type > my_size
Size of container in stored items.
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.
concurrent_hash_map(concurrent_hash_map &&table, const allocator_type &a)
Move constructor.
auto last(Container &c) -> decltype(begin(c))
concurrent_hash_map(const concurrent_hash_map &table, const allocator_type &a=allocator_type())
Copy constructor.
void internal_swap(hash_map_base &table)
Swap hash_map_bases.
intptr_t __TBB_Log2(uintptr_t x)
hash_map_base::node_base node_base
void mark_rehashed_levels(hashcode_t h)
bool find(accessor &result, const Key &key)
Find item and acquire a write lock on the item.
bool exclude(const_accessor &item_accessor)
delete item by accessor
bool empty() const
True if size()==0.
internal::hash_map_range< iterator > range_type
const bucket * my_bucket
Pointer to bucket.
concurrent_hash_map(const allocator_type &a=allocator_type())
Construct empty table.
static hash_map_node_base *const empty_rehashed
Rehashed empty bucket flag.
void advance_to_next_bucket()
concurrent_hash_map & operator=(const concurrent_hash_map &table)
Assignment.
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
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...
reference operator*() const
Return reference to associated value in hash table.
mutex_t::scoped_lock scoped_t
Scoped lock type for mutex.
const_accessor()
Create empty result.
#define __TBB_FORWARDING_REF(A)
bool insert(const_accessor &result, const Key &key)
Insert item (if not already present) and acquire a read lock on the item.
hash_map_range(hash_map_range< U > &r)
type conversion
tbb::internal::allocator_traits< node_allocator_type > node_allocator_traits
bucket my_embedded_segment[embedded_buckets]
Zero segment.
const_reference operator*() const
Return reference to associated value in hash table.
friend class const_accessor
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
static node * allocate_node_default_construct(node_allocator_type &allocator, const Key &key, const T *)
const value_type * const_pointer
mutex_t::scoped_lock scoped_t
Scoped lock type for mutex.
bool erase(const Key &key)
Erase item.
static void init_buckets(segment_ptr_t ptr, size_type sz, bool is_initial)
Initialize buckets.
bool operator==(const hash_map_iterator< Container, T > &i, const hash_map_iterator< Container, U > &j)
segments_table_t my_table
Segment pointers table. Also prevents false sharing between my_mask and my_size.
friend const_accessor * accessor_location(accessor_not_used const &)
Combines data access, locking, and garbage collection.
Dummy type that distinguishes splitting constructor from copy constructor.
const_iterator begin() const
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
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.
friend bool is_write_access_needed(accessor const &)
bool erase(accessor &item_accessor)
Erase item by accessor.
void swap(concurrent_hash_map &table)
swap two instances. Iterators are invalidated
bool insert(value_type &&value)
Insert item by copying if there is no such key present already.
spin_rw_mutex mutex_t
Mutex type for buckets.
static node * do_not_allocate_node(node_allocator_type &, const Key &, const T *)
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
bool check_mask_race(const hashcode_t h, hashcode_t &m) const
Check for mask race.
bool operator!=(const hash_map_iterator< Container, T > &i, const hash_map_iterator< Container, U > &j)
void rehash_bucket(bucket *b_new, const hashcode_t h)
static hash_map_node_base *const rehash_req
Incompleteness flag value.
Class that implements exponential backoff.
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.
call_clear_on_leave(concurrent_hash_map *a_ch_map)
hash_map_node_base * next
Next node in chain.
void move(tbb_thread &t1, tbb_thread &t2)
bool operator!=(const cache_aligned_allocator< T > &, const cache_aligned_allocator< U > &)
bucket * segment_ptr_t
Segment pointer.
Iterator::value_type value_type
void release()
Set to null.
void const char const char int ITT_FORMAT __itt_group_sync s
void itt_hide_store_word(T &dst, T src)
#define __TBB_USE_OPTIONAL_RTTI
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
hash_map_iterator & operator++()
bool insert(accessor &result, const Key &key)
Insert item (if not already present) and acquire a write lock on the item.
hash_map_iterator(const hash_map_iterator< Container, typename Container::value_type > &other)
segment_index_t insert_new_node(bucket *b, node_base *n, hashcode_t mask)
Insert a node and check for load factor.
std::pair< const Key, T > value_type
static segment_index_t segment_base(segment_index_t k)
HashCompare my_hash_compare
const value_type & const_reference
hash_map_iterator()
Construct undefined iterator.
node_allocator_type & my_alloc
range_type range(size_type grainsize=1)
bucket * operator()()
get bucket pointer
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.
bool is_divisible() const
True if range can be partitioned into two subranges.
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
concurrent_hash_map::value_type value_type
Type of value.
internal::hash_map_iterator< concurrent_hash_map, const value_type > const_iterator
static segment_index_t segment_index_of(size_type index)
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.
hash_map_base::size_type size_type
concurrent_hash_map(const HashCompare &compare, const allocator_type &a=allocator_type())
concurrent_hash_map(I first, I last, const HashCompare &compare, const allocator_type &a=allocator_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
static void destroy(Alloc &, T *p)
size_type bucket_count() const
Returns the current number of buckets.
void enable_segment(segment_index_t k, const Allocator &allocator, bool is_initial=false)
Enable segment.
node_scoped_guard(node *n, node_allocator_type &alloc)
bool empty() const
True if range is empty.
enable_segment_failsafe(segments_table_t &table, segment_index_t k)
std::size_t size_type
Type for size of a range.
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)
The scoped locking pattern.
void reserve(size_type buckets, const Allocator &allocator)
Prepare enough segments for number of buckets.
Class for determining type of std::allocator<T>::value_type.
hash_map_iterator operator++(int)
Post increment.
static node * allocate_node_copy_construct(node_allocator_type &allocator, const Key &key, const T *t)
node_allocator_type my_allocator
Identifiers declared inside namespace internal should never be used directly by client code.
hash_map_node_base node_base
Node base type.
const Iterator & end() const
bool insert(const value_type &value)
Insert item by copying if there is no such key present already.
friend class internal::hash_map_iterator
internal::hash_map_iterator< concurrent_hash_map, value_type > iterator
static size_type segment_size(segment_index_t k)
void __TBB_store_with_release(volatile T &location, V value)
atomic< T > & as_atomic(T &t)
size_type max_size() const
Upper bound on size.
Value * operator->() const
bucket_accessor(concurrent_hash_map *base, const hashcode_t h, bool writer=false)
concurrent_hash_map(std::initializer_list< value_type > il, const HashCompare &compare, const allocator_type &a=allocator_type())
size_t hashcode_t
Type of a hash code.
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.
void rehash(size_type n=0)
Rehashes and optionally resizes the whole table.
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.
static node * create_node(node_allocator_type &allocator, Args &&... args)
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.
segment_ptr_t * my_segment_ptr