#include <concurrent_hash_map.h>
Classes | |
| class | accessor |
| Allows write access to elements and combines data access, locking, and garbage collection. More... | |
| class | bucket_accessor |
| bucket accessor is to find, rehash, acquire a lock, and access a bucket More... | |
| class | const_accessor |
| Combines data access, locking, and garbage collection. More... | |
| struct | node |
Public Types | |
| typedef Allocator | allocator_type |
| typedef internal::hash_map_iterator < concurrent_hash_map, const value_type > | const_iterator |
| typedef const value_type * | const_pointer |
| typedef internal::hash_map_range < const_iterator > | const_range_type |
| typedef const value_type & | const_reference |
| typedef ptrdiff_t | difference_type |
| typedef internal::hash_map_iterator < concurrent_hash_map, value_type > | iterator |
| typedef Key | key_type |
| typedef T | mapped_type |
| typedef value_type * | pointer |
| typedef internal::hash_map_range < iterator > | range_type |
| typedef value_type & | reference |
| typedef hash_map_base::size_type | size_type |
| typedef std::pair< const Key, T > | value_type |
Public Member Functions | |
| iterator | begin () |
| const_iterator | begin () const |
| size_type | bucket_count () const |
| Returns the current number of buckets. | |
| void | clear () |
| Clear table. | |
| template<typename I > | |
| concurrent_hash_map (I first, I last, const allocator_type &a=allocator_type()) | |
| Construction with copying iteration range and given allocator instance. | |
| 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 level. | |
| concurrent_hash_map (const allocator_type &a=allocator_type()) | |
| Construct empty table. | |
| concurrent_hash_map (const concurrent_hash_map &table, const allocator_type &a=allocator_type()) | |
| Copy constructor. | |
| size_type | count (const Key &key) const |
| Return count of items (0 or 1). | |
| bool | empty () const |
| True if size()==0. | |
| iterator | end () |
| const_iterator | end () const |
| std::pair< const_iterator, const_iterator > | equal_range (const Key &key) const |
| std::pair< iterator, iterator > | equal_range (const Key &key) |
| bool | erase (const Key &key) |
| Erase item. | |
| bool | erase (accessor &item_accessor) |
| Erase item by accessor. | |
| bool | erase (const_accessor &item_accessor) |
| Erase item by const_accessor. | |
| bool | find (const_accessor &result, const Key &key) const |
| Find item and acquire a read lock on the item. | |
| bool | find (accessor &result, const Key &key) |
| Find item and acquire a write lock on the item. | |
| allocator_type | get_allocator () const |
| return allocator object | |
| 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. | |
| bool | insert (const value_type &value) |
| Insert item by copying if there is no such key present already. | |
| bool | insert (accessor &result, const Key &key) |
| Insert item (if not already present) and acquire a write lock on the item. | |
| template<typename I > | |
| void | insert (I first, I last) |
| Insert range [first, last). | |
| bool | insert (const_accessor &result, const Key &key) |
| Insert item (if not already present) and acquire a read lock on the item. | |
| 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. | |
| size_type | max_size () const |
| Upper bound on size. | |
| concurrent_hash_map & | operator= (const concurrent_hash_map &table) |
| Assignment. | |
| const_range_type | range (size_type grainsize=1) const |
| range_type | range (size_type grainsize=1) |
| void | rehash (size_type n=0) |
| Rehashes and optionally resizes the whole table. | |
| size_type | size () const |
| Number of items in table. | |
| void | swap (concurrent_hash_map &table) |
| swap two instances. Iterators are invalidated | |
| ~concurrent_hash_map () | |
| Clear table and destroy it. | |
Protected Types | |
| typedef Allocator::template rebind< node >::other | node_allocator_type |
Protected Member Functions | |
| void | delete_node (node_base *n) |
| bool | exclude (const_accessor &item_accessor, bool readonly) |
| delete item by accessor | |
| template<typename I > | |
| void | internal_copy (I first, I last) |
| void | internal_copy (const concurrent_hash_map &source) |
| Copy "source" to *this, where *this must start out empty. | |
| template<typename I > | |
| 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). | |
| const_pointer | internal_fast_find (const Key &key) const |
| Fast find when no concurrent erasure is used. For internal use inside TBB only! | |
| bool | lookup (bool op_insert, const Key &key, const T *t, const_accessor *result, bool write) |
| Insert or find item and optionally acquire a lock on the item. | |
| void | rehash_bucket (bucket *b_new, const hashcode_t h) |
| node * | search_bucket (const key_type &key, bucket *b) const |
Protected Attributes | |
| node_allocator_type | my_allocator |
| HashCompare | my_hash_compare |
Friends | |
| class | const_accessor |
| class | internal::hash_map_iterator |
| class | internal::hash_map_range |
Unordered map from Key to T. concurrent_hash_map is associative container with concurrent access.
Definition at line 571 of file concurrent_hash_map.h.
| typedef Allocator tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocator_type |
Definition at line 592 of file concurrent_hash_map.h.
| typedef internal::hash_map_iterator<concurrent_hash_map,const value_type> tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_iterator |
Definition at line 589 of file concurrent_hash_map.h.
| typedef const value_type* tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_pointer |
Definition at line 585 of file concurrent_hash_map.h.
| typedef internal::hash_map_range<const_iterator> tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_range_type |
Definition at line 591 of file concurrent_hash_map.h.
| typedef const value_type& tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_reference |
Definition at line 587 of file concurrent_hash_map.h.
| typedef ptrdiff_t tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::difference_type |
Definition at line 583 of file concurrent_hash_map.h.
| typedef internal::hash_map_iterator<concurrent_hash_map,value_type> tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::iterator |
Definition at line 588 of file concurrent_hash_map.h.
| typedef Key tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::key_type |
Definition at line 579 of file concurrent_hash_map.h.
| typedef T tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::mapped_type |
Definition at line 580 of file concurrent_hash_map.h.
typedef Allocator::template rebind<node>::other tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::node_allocator_type [protected] |
Definition at line 596 of file concurrent_hash_map.h.
| typedef value_type* tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::pointer |
Definition at line 584 of file concurrent_hash_map.h.
| typedef internal::hash_map_range<iterator> tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::range_type |
Definition at line 590 of file concurrent_hash_map.h.
| typedef value_type& tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::reference |
Definition at line 586 of file concurrent_hash_map.h.
| typedef hash_map_base::size_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::size_type |
Definition at line 582 of file concurrent_hash_map.h.
| typedef std::pair<const Key,T> tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::value_type |
Definition at line 581 of file concurrent_hash_map.h.
| tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map | ( | const allocator_type & | a = allocator_type() |
) | [inline] |
Definition at line 757 of file concurrent_hash_map.h.
: internal::hash_map_base(), my_allocator(a)
| tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map | ( | size_type | n, | |
| const allocator_type & | a = allocator_type() | |||
| ) | [inline] |
Definition at line 762 of file concurrent_hash_map.h.
: internal::hash_map_base(), my_allocator(a) {} concurrent_hash_map(size_type n, const allocator_type &a = allocator_type())
| tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map | ( | const concurrent_hash_map< Key, T, HashCompare, Allocator > & | table, | |
| const allocator_type & | a = allocator_type() | |||
| ) | [inline] |
Definition at line 769 of file concurrent_hash_map.h.
: internal::hash_map_base(), my_allocator(a)
| tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map | ( | I | first, | |
| I | last, | |||
| const allocator_type & | a = allocator_type() | |||
| ) | [inline] |
Definition at line 777 of file concurrent_hash_map.h.
: my_allocator(a)
| tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::~concurrent_hash_map | ( | ) | [inline] |
Definition at line 803 of file concurrent_hash_map.h.
{ clear(); }
| iterator tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::begin | ( | ) | [inline] |
Definition at line 818 of file concurrent_hash_map.h.
{return iterator(*this,0,my_embedded_segment,my_embedded_segment->node_list);}
| const_iterator tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::begin | ( | ) | const [inline] |
Definition at line 820 of file concurrent_hash_map.h.
{return iterator(*this,0,my_embedded_segment,my_embedded_segment->node_list);}
| size_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_count | ( | ) | const [inline] |
Definition at line 835 of file concurrent_hash_map.h.
{return (~size_type(0))/sizeof(node);}
| void tbb::interface4::concurrent_hash_map< Key, T, HashCompare, A >::clear | ( | ) |
Definition at line 1240 of file concurrent_hash_map.h.
{
hashcode_t m = my_mask;
__TBB_ASSERT((m&(m+1))==0, NULL);
#if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS
#if TBB_USE_PERFORMANCE_WARNINGS
int current_size = int(my_size), buckets = int(m)+1, empty_buckets = 0, overpopulated_buckets = 0; // usage statistics
static bool reported = false;
#endif
bucket *bp = 0;
// check consistency
for( segment_index_t b = 0; b <= m; b++ ) {
if( b & (b-2) ) ++bp; // not the beginning of a segment
else bp = get_bucket( b );
node_base *n = bp->node_list;
__TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed || n == internal::rehash_req, "Broken internal structure" );
__TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during clear() execution" );
#if TBB_USE_PERFORMANCE_WARNINGS
if( n == internal::empty_rehashed ) empty_buckets++;
else if( n == internal::rehash_req ) buckets--;
else if( n->next ) overpopulated_buckets++;
#endif
#if __TBB_EXTRA_DEBUG
for(; is_valid(n); n = n->next ) {
hashcode_t h = my_hash_compare.hash( static_cast<node*>(n)->item.first );
h &= m;
__TBB_ASSERT( h == b || get_bucket(h)->node_list == internal::rehash_req, "hash() function changed for key in table or internal error" );
}
#endif
}
#if TBB_USE_PERFORMANCE_WARNINGS
if( buckets > current_size) empty_buckets -= buckets - current_size;
else overpopulated_buckets -= current_size - buckets; // TODO: load_factor?
if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
tbb::internal::runtime_warning(
"Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
typeid(*this).name(), current_size, empty_buckets, overpopulated_buckets );
reported = true;
}
#endif
#endif//TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS
my_size = 0;
segment_index_t s = segment_index_of( m );
__TBB_ASSERT( s+1 == pointers_per_table || !my_table[s+1], "wrong mask or concurrent grow" );
cache_aligned_allocator<bucket> alloc;
do {
__TBB_ASSERT( is_valid( my_table[s] ), "wrong mask or concurrent grow" );
segment_ptr_t buckets_ptr = my_table[s];
size_type sz = segment_size( s ? s : 1 );
for( segment_index_t i = 0; i < sz; i++ )
for( node_base *n = buckets_ptr[i].node_list; is_valid(n); n = buckets_ptr[i].node_list ) {
buckets_ptr[i].node_list = n->next;
delete_node( n );
}
if( s >= first_block) // the first segment or the next
alloc.deallocate( buckets_ptr, sz );
else if( s == embedded_block && embedded_block != first_block )
alloc.deallocate( buckets_ptr, segment_size(first_block)-embedded_buckets );
| size_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::count | ( | const Key & | key | ) | const [inline] |
Definition at line 848 of file concurrent_hash_map.h.
{
| void tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::delete_node | ( | node_base * | n | ) | [inline, protected] |
Definition at line 616 of file concurrent_hash_map.h.
Referenced by tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup().
{return a.deallocate(static_cast<node*>(ptr),1); }
};
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::empty | ( | ) | const [inline] |
Definition at line 829 of file concurrent_hash_map.h.
{ return my_size; }
| iterator tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::end | ( | ) | [inline] |
Definition at line 819 of file concurrent_hash_map.h.
{return iterator(*this,0,my_embedded_segment,my_embedded_segment->node_list);}
| const_iterator tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::end | ( | ) | const [inline] |
Definition at line 821 of file concurrent_hash_map.h.
{return iterator(*this,0,my_embedded_segment,my_embedded_segment->node_list);}
| std::pair<iterator, iterator> tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::equal_range | ( | const Key & | key | ) | [inline] |
Definition at line 822 of file concurrent_hash_map.h.
{return iterator(*this,0,my_embedded_segment,my_embedded_segment->node_list);}
| std::pair<const_iterator, const_iterator> tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::equal_range | ( | const Key & | key | ) | const [inline] |
Definition at line 823 of file concurrent_hash_map.h.
{return iterator(*this,0,0,0);}
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::erase | ( | accessor & | item_accessor | ) | [inline] |
Return true if item was erased by particularly this call.
Definition at line 919 of file concurrent_hash_map.h.
{
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::erase | ( | const_accessor & | item_accessor | ) | [inline] |
Return true if item was erased by particularly this call.
Definition at line 913 of file concurrent_hash_map.h.
{
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, A >::erase | ( | const Key & | key | ) |
Return true if item was erased by particularly this call.
Definition at line 1126 of file concurrent_hash_map.h.
{
node_base *n;
hashcode_t const h = my_hash_compare.hash( key );
#if TBB_USE_THREADING_TOOLS
hashcode_t m = (hashcode_t) itt_load_pointer_with_acquire_v3( &my_mask );
#else
hashcode_t m = my_mask;
#endif
restart:
{//lock scope
// get bucket
bucket_accessor b( this, h & m );
search:
node_base **p = &b()->node_list;
n = *p;
while( is_valid(n) && !my_hash_compare.equal(key, static_cast<node*>(n)->item.first ) ) {
p = &n->next;
n = *p;
}
if( !n ) { // not found, but mask could be changed
if( check_mask_race( h, m ) )
goto restart;
return false;
}
else if( !b.is_writer() && !b.upgrade_to_writer() ) {
if( check_mask_race( h, m ) ) // contended upgrade, check mask
goto restart;
goto search;
}
*p = n->next;
my_size--;
}
{
typename node::scoped_t item_locker( n->mutex, /*write=*/true );
}
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, A >::exclude | ( | const_accessor & | item_accessor, | |
| bool | readonly | |||
| ) | [protected] |
Definition at line 1091 of file concurrent_hash_map.h.
{
__TBB_ASSERT( item_accessor.my_node, NULL );
node_base *const n = item_accessor.my_node;
item_accessor.my_node = NULL; // we ought release accessor anyway
hashcode_t const h = item_accessor.my_hash;
#if TBB_USE_THREADING_TOOLS
hashcode_t m = (hashcode_t) itt_load_pointer_with_acquire_v3( &my_mask );
#else
hashcode_t m = my_mask;
#endif
do {
// get bucket
bucket_accessor b( this, h & m, /*writer=*/true );
node_base **p = &b()->node_list;
while( *p && *p != n )
p = &(*p)->next;
if( !*p ) { // someone else was the first
if( check_mask_race( h, m ) )
continue;
item_accessor.my_lock.release();
return false;
}
__TBB_ASSERT( *p == n, NULL );
*p = n->next; // remove from container
my_size--;
break;
} while(true);
if( readonly ) // need to get exclusive lock
item_accessor.my_lock.upgrade_to_writer(); // return value means nothing here
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::find | ( | const_accessor & | result, | |
| const Key & | key | |||
| ) | const [inline] |
Return true if item is found, false otherwise.
Definition at line 854 of file concurrent_hash_map.h.
{
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::find | ( | accessor & | result, | |
| const Key & | key | |||
| ) | [inline] |
Return true if item is found, false otherwise.
Definition at line 861 of file concurrent_hash_map.h.
{
| allocator_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::get_allocator | ( | ) | const [inline] |
Definition at line 838 of file concurrent_hash_map.h.
{ return my_mask+1; }
| void tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert | ( | I | first, | |
| I | last | |||
| ) | [inline] |
Definition at line 902 of file concurrent_hash_map.h.
{
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert | ( | const_accessor & | result, | |
| const Key & | key | |||
| ) | [inline] |
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert | ( | accessor & | result, | |
| const Key & | key | |||
| ) | [inline] |
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert | ( | const_accessor & | result, | |
| const value_type & | value | |||
| ) | [inline] |
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert | ( | accessor & | result, | |
| const value_type & | value | |||
| ) | [inline] |
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert | ( | const value_type & | value | ) | [inline] |
| void tbb::interface4::concurrent_hash_map< Key, T, HashCompare, A >::internal_copy | ( | const concurrent_hash_map< Key, T, HashCompare, Allocator > & | source | ) | [protected] |
Definition at line 1303 of file concurrent_hash_map.h.
{
reserve( source.my_size ); // TODO: load_factor?
hashcode_t mask = source.my_mask;
if( my_mask == mask ) { // optimized version
bucket *dst = 0, *src = 0;
bool rehash_required = false;
for( hashcode_t k = 0; k <= mask; k++ ) {
if( k & (k-2) ) ++dst,src++; // not the beginning of a segment
else { dst = get_bucket( k ); src = source.get_bucket( k ); }
__TBB_ASSERT( dst->node_list != internal::rehash_req, "Invalid bucket in destination table");
node *n = static_cast<node*>( src->node_list );
if( n == internal::rehash_req ) { // source is not rehashed, items are in previous buckets
rehash_required = true;
dst->node_list = internal::rehash_req;
} else for(; n; n = static_cast<node*>( n->next ) ) {
add_to_bucket( dst, new( my_allocator ) node(n->item.first, n->item.second) );
++my_size; // TODO: replace by non-atomic op
}
| void tbb::interface4::concurrent_hash_map< Key, T, HashCompare, A >::internal_copy | ( | I | first, | |
| I | last | |||
| ) | [protected] |
Definition at line 1328 of file concurrent_hash_map.h.
{
hashcode_t m = my_mask;
for(; first != last; ++first) {
hashcode_t h = my_hash_compare.hash( first->first );
bucket *b = get_bucket( h & m );
__TBB_ASSERT( b->node_list != internal::rehash_req, "Invalid bucket in destination table");
node *n = new( my_allocator ) node(first->first, first->second);
| std::pair< I, I > tbb::interface4::concurrent_hash_map< Key, T, HashCompare, A >::internal_equal_range | ( | const Key & | key, | |
| I | end | |||
| ) | const [protected] |
Definition at line 1073 of file concurrent_hash_map.h.
{
hashcode_t h = my_hash_compare.hash( key );
hashcode_t m = my_mask;
__TBB_ASSERT((m&(m+1))==0, NULL);
h &= m;
bucket *b = get_bucket( h );
while( b->node_list == internal::rehash_req ) {
m = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
b = get_bucket( h &= m );
}
node *n = search_bucket( key, b );
if( !n )
| const_pointer tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_fast_find | ( | const Key & | key | ) | const [inline, protected] |
Return pointer to item with given key, or NULL if no such item exists. Must not be called concurrently with erasure operations.
Definition at line 943 of file concurrent_hash_map.h.
References __TBB_load_with_acquire(), and tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::item.
{
hashcode_t h = my_hash_compare.hash( key );
#if TBB_USE_THREADING_TOOLS
hashcode_t m = (hashcode_t) itt_load_pointer_with_acquire_v3( &my_mask );
#else
hashcode_t m = my_mask;
#endif
node *n;
restart:
__TBB_ASSERT((m&(m+1))==0, NULL);
bucket *b = get_bucket( h & m );
#if TBB_USE_THREADING_TOOLS
// TODO: actually, notification is unnecessary here, just hiding double-check
if( itt_load_pointer_with_acquire_v3(&b->node_list) == internal::rehash_req )
#else
if( __TBB_load_with_acquire(b->node_list) == internal::rehash_req )
#endif
{
bucket::scoped_t lock;
if( lock.try_acquire( b->mutex, /*write=*/true ) ) {
if( b->node_list == internal::rehash_req)
const_cast<concurrent_hash_map*>(this)->rehash_bucket( b, h & m ); //recursive rehashing
}
else lock.acquire( b->mutex, /*write=*/false );
__TBB_ASSERT(b->node_list!=internal::rehash_req,NULL);
}
n = search_bucket( key, b );
if( n )
return &n->item;
| bool tbb::interface4::concurrent_hash_map< Key, T, HashCompare, A >::lookup | ( | bool | op_insert, | |
| const Key & | key, | |||
| const T * | t, | |||
| const_accessor * | result, | |||
| bool | write | |||
| ) | [protected] |
Definition at line 985 of file concurrent_hash_map.h.
References tbb::internal::atomic_backoff::bounded_pause(), tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::delete_node(), tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_accessor::is_writer(), tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator, tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_hash_compare, tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::search_bucket(), and tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_accessor::upgrade_to_writer().
: 4127 ) #endif template<typename Key, typename T, typename HashCompare, typename A> bool concurrent_hash_map<Key,T,HashCompare,A>::lookup( bool op_insert, const Key &key, const T *t, const_accessor *result, bool write ) { __TBB_ASSERT( !result || !result->my_node, NULL ); segment_index_t grow_segment; bool return_value; node *n, *tmp_n = 0; hashcode_t const h = my_hash_compare.hash( key ); #if TBB_USE_THREADING_TOOLS hashcode_t m = (hashcode_t) itt_load_pointer_with_acquire_v3( &my_mask ); #else hashcode_t m = my_mask; #endif restart: {//lock scope __TBB_ASSERT((m&(m+1))==0, NULL); return_value = false; // get bucket bucket_accessor b( this, h & m ); // find a node n = search_bucket( key, b() ); if( op_insert ) { // [opt] insert a key if( !n ) { if( !tmp_n ) { if(t) tmp_n = new( my_allocator ) node(key, *t); else tmp_n = new( my_allocator ) node(key); } if( !b.is_writer() && !b.upgrade_to_writer() ) { // TODO: improved insertion // Rerun search_list, in case another thread inserted the item during the upgrade. n = search_bucket( key, b() ); if( is_valid(n) ) { // unfortunately, it did b.downgrade_to_reader(); goto exists; } } if( check_mask_race(h, m) ) goto restart; // b.release() is done in ~b(). // insert and set flag to grow the container grow_segment = insert_new_node( b(), n = tmp_n, m ); tmp_n = 0; return_value = true; } else { exists: grow_segment = 0; } } else { // find or count if( !n ) { if( check_mask_race( h, m ) ) goto restart; // b.release() is done in ~b(). TODO: replace by continue return false; } return_value = true; grow_segment = 0; } if( !result ) goto check_growth; // TODO: the following seems as generic/regular operation // acquire the item if( !result->my_lock.try_acquire( n->mutex, write ) ) { // we are unlucky, prepare for longer wait tbb::internal::atomic_backoff trials; do { if( !trials.bounded_pause() ) { // the wait takes really long, restart the operation b.release(); __TBB_ASSERT( !op_insert || !return_value, "Can't acquire new item in locked bucket?" ); __TBB_Yield(); #if TBB_USE_THREADING_TOOLS m = (hashcode_t) itt_load_pointer_with_acquire_v3( &my_mask ); #else m = my_mask; #endif goto restart; } } while( !result->my_lock.try_acquire( n->mutex, write ) ); } }//lock scope result->my_node = n; result->my_hash = h; check_growth: // [opt] grow the container if( grow_segment ) enable_segment( grow_segment );
| size_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::max_size | ( | ) | const [inline] |
Definition at line 832 of file concurrent_hash_map.h.
{ return my_size == 0; }
| concurrent_hash_map& tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::operator= | ( | const concurrent_hash_map< Key, T, HashCompare, Allocator > & | table | ) | [inline] |
Definition at line 785 of file concurrent_hash_map.h.
{
if( this!=&table ) {
clear();
| const_range_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::range | ( | size_type | grainsize = 1 |
) | const [inline] |
Definition at line 811 of file concurrent_hash_map.h.
{
return range_type( *this, grainsize );
| range_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::range | ( | size_type | grainsize = 1 |
) | [inline] |
Definition at line 808 of file concurrent_hash_map.h.
{
| void tbb::interface4::concurrent_hash_map< Key, T, HashCompare, A >::rehash | ( | size_type | n = 0 |
) |
Useful to optimize performance before or after concurrent operations. Also enables using of find() and count() concurrent methods in serial context.
Definition at line 1174 of file concurrent_hash_map.h.
{
reserve( sz ); // TODO: add reduction of number of buckets as well
hashcode_t mask = my_mask;
hashcode_t b = (mask+1)>>1; // size or first index of the last segment
__TBB_ASSERT((b&(b-1))==0, NULL);
bucket *bp = get_bucket( b ); // only the last segment should be scanned for rehashing
for(; b <= mask; b++, bp++ ) {
node_base *n = bp->node_list;
__TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed || n == internal::rehash_req, "Broken internal structure" );
__TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during rehash() execution" );
if( n == internal::rehash_req ) { // rehash bucket, conditional because rehashing of a previous bucket may affect this one
hashcode_t h = b; bucket *b_old = bp;
do {
__TBB_ASSERT( h > 1, "The lowermost buckets can't be rehashed" );
hashcode_t m = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
b_old = get_bucket( h &= m );
} while( b_old->node_list == internal::rehash_req );
// now h - is index of the root rehashed bucket b_old
mark_rehashed_levels( h ); // mark all non-rehashed children recursively across all segments
for( node_base **p = &b_old->node_list, *q = *p; is_valid(q); q = *p ) {
hashcode_t c = my_hash_compare.hash( static_cast<node*>(q)->item.first );
if( (c & mask) != h ) { // should be rehashed
*p = q->next; // exclude from b_old
bucket *b_new = get_bucket( c & mask );
__TBB_ASSERT( b_new->node_list != internal::rehash_req, "hash() function changed for key in table or internal error" );
add_to_bucket( b_new, q );
} else p = &q->next; // iterate to next item
}
}
}
#if TBB_USE_PERFORMANCE_WARNINGS
int current_size = int(my_size), buckets = int(mask)+1, empty_buckets = 0, overpopulated_buckets = 0; // usage statistics
static bool reported = false;
#endif
#if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS
for( b = 0; b <= mask; b++ ) {// only last segment should be scanned for rehashing
if( b & (b-2) ) ++bp; // not the beginning of a segment
else bp = get_bucket( b );
node_base *n = bp->node_list;
__TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during rehash() execution" );
__TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed, "Broken internal structure" );
#if TBB_USE_PERFORMANCE_WARNINGS
if( n == internal::empty_rehashed ) empty_buckets++;
else if( n->next ) overpopulated_buckets++;
#endif
#if TBB_USE_ASSERT
for( ; is_valid(n); n = n->next ) {
hashcode_t h = my_hash_compare.hash( static_cast<node*>(n)->item.first ) & mask;
__TBB_ASSERT( h == b, "hash() function changed for key in table or internal error" );
}
#endif
}
#endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS
#if TBB_USE_PERFORMANCE_WARNINGS
if( buckets > current_size) empty_buckets -= buckets - current_size;
else overpopulated_buckets -= current_size - buckets; // TODO: load_factor?
if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
tbb::internal::runtime_warning(
"Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
typeid(*this).name(), current_size, empty_buckets, overpopulated_buckets );
| void tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::rehash_bucket | ( | bucket * | b_new, | |
| const hashcode_t | h | |||
| ) | [inline, protected] |
Definition at line 661 of file concurrent_hash_map.h.
{ my_is_writer = true; return bucket::scoped_t::upgrade_to_writer(); }
};
// TODO refactor to hash_base
void rehash_bucket( bucket *b_new, const hashcode_t h ) {
__TBB_ASSERT( *(intptr_t*)(&b_new->mutex), "b_new must be locked (for write)");
__TBB_ASSERT( h > 1, "The lowermost buckets can't be rehashed" );
__TBB_store_with_release(b_new->node_list, internal::empty_rehashed); // mark rehashed
hashcode_t mask = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
bucket_accessor b_old( this, h & mask );
mask = (mask<<1) | 1; // get full mask for new bucket
__TBB_ASSERT( (mask&(mask+1))==0 && (h & mask) == h, NULL );
restart:
for( node_base **p = &b_old()->node_list, *n = __TBB_load_with_acquire(*p); is_valid(n); n = *p ) {
hashcode_t c = my_hash_compare.hash( static_cast<node*>(n)->item.first );
#if TBB_USE_ASSERT
hashcode_t bmask = h & (mask>>1);
bmask = bmask==0? 1 : ( 1u<<(__TBB_Log2( bmask )+1 ) ) - 1; // minimal mask of parent bucket
__TBB_ASSERT( (c & bmask) == (h & bmask), "hash() function changed for key in table" );
#endif
if( (c & mask) == h ) {
if( !b_old.is_writer() )
if( !b_old.upgrade_to_writer() ) {
goto restart; // node ptr can be invalid due to concurrent erase
}
*p = n->next; // exclude from b_old
| node* tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::search_bucket | ( | const key_type & | key, | |
| bucket * | b | |||
| ) | const [inline, protected] |
Definition at line 621 of file concurrent_hash_map.h.
Referenced by tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup().
{
node *n = static_cast<node*>( b->node_list );
while( is_valid(n) && !my_hash_compare.equal(key, n->item.first) )
| size_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::size | ( | ) | const [inline] |
Definition at line 826 of file concurrent_hash_map.h.
{ return internal_equal_range(key, end()); }
| void tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::swap | ( | concurrent_hash_map< Key, T, HashCompare, Allocator > & | table | ) |
friend class const_accessor [friend] |
Definition at line 595 of file concurrent_hash_map.h.
friend class internal::hash_map_iterator [friend] |
Definition at line 573 of file concurrent_hash_map.h.
friend class internal::hash_map_range [friend] |
Definition at line 576 of file concurrent_hash_map.h.
node_allocator_type tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator [protected] |
Definition at line 598 of file concurrent_hash_map.h.
Referenced by tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup().
HashCompare tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_hash_compare [protected] |
Definition at line 599 of file concurrent_hash_map.h.
Referenced by tbb::interface4::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup().
Copyright © 2005-2010 Intel Corporation. All Rights Reserved.
Licensed under the GNU General Public License 2 with the runtime exception.
Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.
* Other names and brands may be claimed as the property of others.