tbb::interface5::internal::hash_map_base Class Reference

base class of concurrent_hash_map More...

#include <concurrent_hash_map.h>

Inheritance diagram for tbb::interface5::internal::hash_map_base:

Collaboration diagram for tbb::interface5::internal::hash_map_base:

Classes
struct	bucket
	Bucket type. More...
struct	enable_segment_failsafe
	Exception safety helper. More...

Public Types
typedef size_t	size_type
	Size type. More...
typedef size_t	hashcode_t
	Type of a hash code. More...
typedef size_t	segment_index_t
	Segment index type. More...
typedef hash_map_node_base	node_base
	Node base type. More...
typedef bucket *	segment_ptr_t
	Segment pointer. More...
typedef segment_ptr_t	segments_table_t[pointers_per_table]
	Segment pointers table type. More...

Public Member Functions
	hash_map_base ()
	Constructor. More...
template<typename Allocator >
void	enable_segment (segment_index_t k, const Allocator &allocator, bool is_initial=false)
	Enable segment. More...
template<typename Allocator >
void	delete_segment (segment_index_t s, const Allocator &allocator)
bucket *	get_bucket (hashcode_t h) const throw ()
	Get bucket by (masked) hashcode. More...
void	mark_rehashed_levels (hashcode_t h) throw ()
bool	check_mask_race (const hashcode_t h, hashcode_t &m) const
	Check for mask race. More...
bool	check_rehashing_collision (const hashcode_t h, hashcode_t m_old, hashcode_t m) const
	Process mask race, check for rehashing collision. More...
segment_index_t	insert_new_node (bucket *b, node_base *n, hashcode_t mask)
	Insert a node and check for load factor. More...
template<typename Allocator >
void	reserve (size_type buckets, const Allocator &allocator)
	Prepare enough segments for number of buckets. More...
void	internal_swap (hash_map_base &table)
	Swap hash_map_bases. More...
void	internal_move (hash_map_base &&other)

Static Public Member Functions
static segment_index_t	segment_index_of (size_type index)
static segment_index_t	segment_base (segment_index_t k)
static size_type	segment_size (segment_index_t k)
static bool	is_valid (void *ptr)
static void	init_buckets (segment_ptr_t ptr, size_type sz, bool is_initial)
	Initialize buckets. More...
static void	add_to_bucket (bucket *b, node_base *n)
	Add node. More...

Public Attributes
atomic< hashcode_t >	my_mask
	Hash mask = sum of allocated segment sizes - 1. More...
segments_table_t	my_table
	Segment pointers table. Also prevents false sharing between my_mask and my_size. More...
atomic< size_type >	my_size
	Size of container in stored items. More...
bucket	my_embedded_segment [embedded_buckets]
	Zero segment. More...

Static Public Attributes
static size_type const	embedded_block = 1
	Count of segments in the first block. More...
static size_type const	embedded_buckets = 1<<embedded_block
	Count of segments in the first block. More...
static size_type const	first_block = 8
	Count of segments in the first block. More...
static size_type const	pointers_per_table = sizeof(segment_index_t) * 8
	Size of a pointer / table size. More...

Detailed Description

base class of concurrent_hash_map

Definition at line 82 of file concurrent_hash_map.h.

Member Typedef Documentation

hashcode_t

typedef size_t tbb::interface5::internal::hash_map_base::hashcode_t

Type of a hash code.

Definition at line 87 of file concurrent_hash_map.h.

node_base

typedef hash_map_node_base tbb::interface5::internal::hash_map_base::node_base

Node base type.

Definition at line 91 of file concurrent_hash_map.h.

segment_index_t

typedef size_t tbb::interface5::internal::hash_map_base::segment_index_t

Segment index type.

Definition at line 89 of file concurrent_hash_map.h.

segment_ptr_t

typedef bucket* tbb::interface5::internal::hash_map_base::segment_ptr_t

Segment pointer.

Definition at line 110 of file concurrent_hash_map.h.

segments_table_t

typedef segment_ptr_t tbb::interface5::internal::hash_map_base::segments_table_t[pointers_per_table]

Segment pointers table type.

Definition at line 112 of file concurrent_hash_map.h.

size_type

typedef size_t tbb::interface5::internal::hash_map_base::size_type

Size type.

Definition at line 85 of file concurrent_hash_map.h.

Constructor & Destructor Documentation

hash_map_base()

tbb::interface5::internal::hash_map_base::hash_map_base ( )

inline

Constructor.

Definition at line 127 of file concurrent_hash_map.h.

                        {
            std::memset(my_table, 0, sizeof(my_table));
            my_mask = 0;
            my_size = 0;
            std::memset(my_embedded_segment, 0, sizeof(my_embedded_segment));
            for( size_type i = 0; i < embedded_block; i++ ) // fill the table
                my_table[i] = my_embedded_segment + segment_base(i);
            my_mask = embedded_buckets - 1;
            __TBB_ASSERT( embedded_block <= first_block, "The first block number must include embedded blocks");
#if __TBB_STATISTICS
            my_info_resizes = 0; // concurrent ones
            my_info_restarts = 0; // race collisions
            my_info_rehashes = 0;  // invocations of rehash_bucket
#endif
        }

Member Function Documentation

add_to_bucket()

static void tbb::interface5::internal::hash_map_base::add_to_bucket ( bucket *  b, node_base *  n  )

inlinestatic

Add node.

• n to bucket
• b

Definition at line 173 of file concurrent_hash_map.h.

                                                             {
            __TBB_ASSERT(b->node_list != rehash_req, NULL);
            n->next = b->node_list;
            b->node_list = n; // its under lock and flag is set
        }

References __TBB_ASSERT, tbb::interface5::internal::hash_map_node_base::next, tbb::interface5::internal::hash_map_base::bucket::node_list, and tbb::interface5::internal::rehash_req.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::rehash_bucket().

Here is the caller graph for this function:

check_mask_race()

bool tbb::interface5::internal::hash_map_base::check_mask_race ( const hashcode_t  h, hashcode_t &  m  ) const

inline

Check for mask race.

Definition at line 254 of file concurrent_hash_map.h.

                                                                               {
            hashcode_t m_now, m_old = m;
            m_now = (hashcode_t) itt_load_word_with_acquire( my_mask );
            if( m_old != m_now )
                return check_rehashing_collision( h, m_old, m = m_now );
            return false;
        }

References h, and tbb::internal::itt_load_word_with_acquire().

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_fast_find().

Here is the call graph for this function:

Here is the caller graph for this function:

check_rehashing_collision()

bool tbb::interface5::internal::hash_map_base::check_rehashing_collision ( const hashcode_t  h, hashcode_t  m_old, hashcode_t  m  ) const

inline

Process mask race, check for rehashing collision.

Definition at line 263 of file concurrent_hash_map.h.

                                                                                                   {
            __TBB_ASSERT(m_old != m, NULL); // TODO?: m arg could be optimized out by passing h = h&m
            if( (h & m_old) != (h & m) ) { // mask changed for this hashcode, rare event
                // condition above proves that 'h' has some other bits set beside 'm_old'
                // find next applicable mask after m_old    //TODO: look at bsl instruction
                for( ++m_old; !(h & m_old); m_old <<= 1 ) // at maximum few rounds depending on the first block size
                    ;
                m_old = (m_old<<1) - 1; // get full mask from a bit
                __TBB_ASSERT((m_old&(m_old+1))==0 && m_old <= m, NULL);
                // check whether it is rehashing/ed
                if( itt_load_word_with_acquire(get_bucket(h & m_old)->node_list) != rehash_req )
                {
#if __TBB_STATISTICS
                    my_info_restarts++; // race collisions
#endif
                    return true;
                }
            }
            return false;
        }

References __TBB_ASSERT, h, tbb::internal::itt_load_word_with_acquire(), and tbb::interface5::internal::rehash_req.

Here is the call graph for this function:

delete_segment()

template<typename Allocator >

void tbb::interface5::internal::hash_map_base::delete_segment ( segment_index_t  s, const Allocator &  allocator  )

inline

Definition at line 218 of file concurrent_hash_map.h.

                                                                           {
            typedef typename tbb::internal::allocator_rebind<Allocator, bucket>::type bucket_allocator_type;
            typedef tbb::internal::allocator_traits<bucket_allocator_type> bucket_allocator_traits;
            bucket_allocator_type bucket_allocator(allocator);
            segment_ptr_t buckets_ptr = my_table[s];
            size_type sz = segment_size( s ? s : 1 );

            if( s >= first_block) // the first segment or the next
                bucket_allocator_traits::deallocate(bucket_allocator, buckets_ptr, sz);
            else if( s == embedded_block && embedded_block != first_block )
                bucket_allocator_traits::deallocate(bucket_allocator, buckets_ptr,
                                                    segment_size(first_block) - embedded_buckets);
            if( s >= embedded_block ) my_table[s] = 0;
        }

References s.

enable_segment()

template<typename Allocator >

void tbb::interface5::internal::hash_map_base::enable_segment ( segment_index_t  k, const Allocator &  allocator, bool  is_initial = false  )

inline

Enable segment.

Definition at line 190 of file concurrent_hash_map.h.

                                                                                                      {
            typedef typename tbb::internal::allocator_rebind<Allocator, bucket>::type bucket_allocator_type;
            typedef tbb::internal::allocator_traits<bucket_allocator_type> bucket_allocator_traits;
            bucket_allocator_type bucket_allocator(allocator);
            __TBB_ASSERT( k, "Zero segment must be embedded" );
            enable_segment_failsafe watchdog( my_table, k );
            size_type sz;
            __TBB_ASSERT( !is_valid(my_table[k]), "Wrong concurrent assignment");
            if( k >= first_block ) {
                sz = segment_size( k );
                segment_ptr_t ptr = bucket_allocator_traits::allocate(bucket_allocator, sz);
                init_buckets( ptr, sz, is_initial );
                itt_hide_store_word( my_table[k], ptr );
                sz <<= 1;// double it to get entire capacity of the container
            } else { // the first block
                __TBB_ASSERT( k == embedded_block, "Wrong segment index" );
                sz = segment_size( first_block );
                segment_ptr_t ptr = bucket_allocator_traits::allocate(bucket_allocator, sz - embedded_buckets);
                init_buckets( ptr, sz - embedded_buckets, is_initial );
                ptr -= segment_base(embedded_block);
                for(segment_index_t i = embedded_block; i < first_block; i++) // calc the offsets
                    itt_hide_store_word( my_table[i], ptr + segment_base(i) );
            }
            itt_store_word_with_release( my_mask, sz-1 );
            watchdog.my_segment_ptr = 0;
        }

References __TBB_ASSERT, tbb::internal::itt_hide_store_word(), tbb::internal::itt_store_word_with_release(), and tbb::interface5::internal::hash_map_base::enable_segment_failsafe::my_segment_ptr.

Here is the call graph for this function:

get_bucket()

bucket* tbb::interface5::internal::hash_map_base::get_bucket ( hashcode_t  h ) const throw ( )

inline

Get bucket by (masked) hashcode.

Definition at line 234 of file concurrent_hash_map.h.

                                                         { // TODO: add throw() everywhere?
            segment_index_t s = segment_index_of( h );
            h -= segment_base(s);
            segment_ptr_t seg = my_table[s];
            __TBB_ASSERT( is_valid(seg), "hashcode must be cut by valid mask for allocated segments" );
            return &seg[h];
        }

References __TBB_ASSERT, h, and s.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_accessor::acquire(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_fast_find().

Here is the caller graph for this function:

init_buckets()

static void tbb::interface5::internal::hash_map_base::init_buckets ( segment_ptr_t  ptr, size_type  sz, bool  is_initial  )

inlinestatic

Initialize buckets.

Definition at line 164 of file concurrent_hash_map.h.

                                                                                     {
            if( is_initial ) std::memset( static_cast<void*>(ptr), 0, sz*sizeof(bucket) );
            else for(size_type i = 0; i < sz; i++, ptr++) {
                *reinterpret_cast<intptr_t*>(&ptr->mutex) = 0;
                ptr->node_list = rehash_req;
            }
        }

References tbb::interface5::internal::hash_map_base::bucket::mutex, tbb::interface5::internal::hash_map_base::bucket::node_list, and tbb::interface5::internal::rehash_req.

insert_new_node()

segment_index_t tbb::interface5::internal::hash_map_base::insert_new_node ( bucket *  b, node_base *  n, hashcode_t  mask  )

inline

Insert a node and check for load factor.

Returns

segment index to enable.

Definition at line 285 of file concurrent_hash_map.h.

                                                                                    {
            size_type sz = ++my_size; // prefix form is to enforce allocation after the first item inserted
            add_to_bucket( b, n );
            // check load factor
            if( sz >= mask ) { // TODO: add custom load_factor
                segment_index_t new_seg = __TBB_Log2( mask+1 ); //optimized segment_index_of
                __TBB_ASSERT( is_valid(my_table[new_seg-1]), "new allocations must not publish new mask until segment has allocated");
                static const segment_ptr_t is_allocating = (segment_ptr_t)2;
                if( !itt_hide_load_word(my_table[new_seg])
                  && as_atomic(my_table[new_seg]).compare_and_swap(is_allocating, NULL) == NULL )
                    return new_seg; // The value must be processed
            }
            return 0;
        }

References __TBB_ASSERT, __TBB_Log2(), tbb::internal::as_atomic(), tbb::internal::itt_hide_load_word(), and mask.

Here is the call graph for this function:

internal_move()

void tbb::interface5::internal::hash_map_base::internal_move ( hash_map_base &&  other )

inline

Definition at line 320 of file concurrent_hash_map.h.

                                                  {
            my_mask = other.my_mask;
            other.my_mask = embedded_buckets - 1;
            my_size = other.my_size;
            other.my_size = 0;

            for(size_type i = 0; i < embedded_buckets; ++i) {
                my_embedded_segment[i].node_list = other.my_embedded_segment[i].node_list;
                other.my_embedded_segment[i].node_list = NULL;
            }

            for(size_type i = embedded_block; i < pointers_per_table; ++i) {
                my_table[i] = other.my_table[i];
                other.my_table[i] = NULL;
            }
        }

References tbb::interface5::internal::hash_map_base::bucket::node_list.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_move_assign().

Here is the caller graph for this function:

internal_swap()

void tbb::interface5::internal::hash_map_base::internal_swap ( hash_map_base &  table )

inline

Swap hash_map_bases.

Definition at line 309 of file concurrent_hash_map.h.

                                                 {
            using std::swap;
            swap(this->my_mask, table.my_mask);
            swap(this->my_size, table.my_size);
            for(size_type i = 0; i < embedded_buckets; i++)
                swap(this->my_embedded_segment[i].node_list, table.my_embedded_segment[i].node_list);
            for(size_type i = embedded_block; i < pointers_per_table; i++)
                swap(this->my_table[i], table.my_table[i]);
        }

References my_embedded_segment, my_mask, my_size, my_table, tbb::interface5::internal::hash_map_base::bucket::node_list, and tbb::swap().

Here is the call graph for this function:

is_valid()

static bool tbb::interface5::internal::hash_map_base::is_valid ( void *  ptr )

inlinestatic

Returns

true if

• ptr is valid pointer

Definition at line 159 of file concurrent_hash_map.h.

                                          {
            return reinterpret_cast<uintptr_t>(ptr) > uintptr_t(63);
        }

Referenced by tbb::interface5::internal::hash_map_iterator< Container, Value >::advance_to_next_bucket(), tbb::interface5::internal::hash_map_iterator< Container, Value >::hash_map_iterator(), tbb::interface5::internal::hash_map_iterator< Container, Value >::operator *(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::rehash_bucket(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::search_bucket().

Here is the caller graph for this function:

mark_rehashed_levels()

void tbb::interface5::internal::hash_map_base::mark_rehashed_levels ( hashcode_t  h ) throw ( )

inline

Definition at line 243 of file concurrent_hash_map.h.

                                                           {
            segment_index_t s = segment_index_of( h );
            while( segment_ptr_t seg = my_table[++s] )
                if( seg[h].node_list == rehash_req ) {
                    seg[h].node_list = empty_rehashed;
                    mark_rehashed_levels( h + ((hashcode_t)1<<s) ); // optimized segment_base(s)
                }
        }

References tbb::interface5::internal::empty_rehashed, h, tbb::interface5::internal::rehash_req, and s.

reserve()

template<typename Allocator >

void tbb::interface5::internal::hash_map_base::reserve ( size_type  buckets, const Allocator &  allocator  )

inline

Prepare enough segments for number of buckets.

Definition at line 302 of file concurrent_hash_map.h.

                                                                    {
            if( !buckets-- ) return;
            bool is_initial = !my_size;
            for( size_type m = my_mask; buckets > m; m = my_mask )
                enable_segment( segment_index_of( m+1 ), allocator, is_initial );
        }

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map().

Here is the caller graph for this function:

segment_base()

static segment_index_t tbb::interface5::internal::hash_map_base::segment_base ( segment_index_t  k )

inlinestatic

Returns

the first array index of given segment

Definition at line 149 of file concurrent_hash_map.h.

                                                                 {
            return (segment_index_t(1)<<k & ~segment_index_t(1));
        }

segment_index_of()

static segment_index_t tbb::interface5::internal::hash_map_base::segment_index_of ( size_type  index )

inlinestatic

Returns

segment index of given index in the array

Definition at line 144 of file concurrent_hash_map.h.

                                                                   {
            return segment_index_t( __TBB_Log2( index|1 ) );
        }

References __TBB_Log2().

Here is the call graph for this function:

segment_size()

static size_type tbb::interface5::internal::hash_map_base::segment_size ( segment_index_t  k )

inlinestatic

Returns

segment size except for

• k == 0

Definition at line 154 of file concurrent_hash_map.h.

                                                           {
            return size_type(1)<<k; // fake value for k==0
        }

Member Data Documentation

embedded_block

size_type const tbb::interface5::internal::hash_map_base::embedded_block = 1

static

Count of segments in the first block.

Definition at line 102 of file concurrent_hash_map.h.

embedded_buckets

size_type const tbb::interface5::internal::hash_map_base::embedded_buckets = 1<<embedded_block

static

Count of segments in the first block.

Definition at line 104 of file concurrent_hash_map.h.

first_block

size_type const tbb::interface5::internal::hash_map_base::first_block = 8

static

Count of segments in the first block.

Definition at line 106 of file concurrent_hash_map.h.

my_embedded_segment

bucket tbb::interface5::internal::hash_map_base::my_embedded_segment[embedded_buckets]

Zero segment.

Definition at line 120 of file concurrent_hash_map.h.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::begin(), and internal_swap().

my_mask

atomic<hashcode_t> tbb::interface5::internal::hash_map_base::my_mask

Hash mask = sum of allocated segment sizes - 1.

Definition at line 114 of file concurrent_hash_map.h.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_count(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_fast_find(), and internal_swap().

my_size

atomic<size_type> tbb::interface5::internal::hash_map_base::my_size

Size of container in stored items.

Definition at line 118 of file concurrent_hash_map.h.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::empty(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), internal_swap(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::size().

my_table

segments_table_t tbb::interface5::internal::hash_map_base::my_table

Segment pointers table. Also prevents false sharing between my_mask and my_size.

Definition at line 116 of file concurrent_hash_map.h.

Referenced by internal_swap().

pointers_per_table

size_type const tbb::interface5::internal::hash_map_base::pointers_per_table = sizeof(segment_index_t) * 8

static

Size of a pointer / table size.

Definition at line 108 of file concurrent_hash_map.h.

---

The documentation for this class was generated from the following file:

• concurrent_hash_map.h