tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator > Class Template Reference

Unordered map from Key to T. More...

#include <concurrent_hash_map.h>

Inheritance diagram for tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >:

Collaboration diagram for tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >:

Classes
class	accessor
	Allows write access to elements and combines data access, locking, and garbage collection. More...
struct	accessor_not_used
class	bucket_accessor
	bucket accessor is to find, rehash, acquire a lock, and access a bucket More...
struct	call_clear_on_leave
class	const_accessor
	Combines data access, locking, and garbage collection. More...
struct	node

Public Types
typedef Key	key_type
typedef T	mapped_type
typedef std::pair< const Key, T >	value_type
typedef hash_map_base::size_type	size_type
typedef ptrdiff_t	difference_type
typedef value_type *	pointer
typedef const value_type *	const_pointer
typedef value_type &	reference
typedef const value_type &	const_reference
typedef internal::hash_map_iterator< concurrent_hash_map, value_type >	iterator
typedef internal::hash_map_iterator< concurrent_hash_map, const value_type >	const_iterator
typedef internal::hash_map_range< iterator >	range_type
typedef internal::hash_map_range< const_iterator >	const_range_type
typedef Allocator	allocator_type

Public Member Functions
	concurrent_hash_map (const allocator_type &a=allocator_type())
	Construct empty table. More...
	concurrent_hash_map (const HashCompare &compare, const allocator_type &a=allocator_type())
	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. More...
	concurrent_hash_map (size_type n, const HashCompare &compare, const allocator_type &a=allocator_type())
	concurrent_hash_map (const concurrent_hash_map &table, const allocator_type &a=allocator_type())
	Copy constructor. More...
	concurrent_hash_map (concurrent_hash_map &&table)
	Move constructor. More...
	concurrent_hash_map (concurrent_hash_map &&table, const allocator_type &a)
	Move constructor. More...
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. More...
template<typename I >
	concurrent_hash_map (I first, I last, const HashCompare &compare, const allocator_type &a=allocator_type())
	concurrent_hash_map (std::initializer_list< value_type > il, const allocator_type &a=allocator_type())
	Construct empty table with n preallocated buckets. This number serves also as initial concurrency level. More...
	concurrent_hash_map (std::initializer_list< value_type > il, const HashCompare &compare, const allocator_type &a=allocator_type())
concurrent_hash_map &	operator= (const concurrent_hash_map &table)
	Assignment. More...
concurrent_hash_map &	operator= (concurrent_hash_map &&table)
	Move Assignment. More...
concurrent_hash_map &	operator= (std::initializer_list< value_type > il)
	Assignment. More...
void	rehash (size_type n=0)
	Rehashes and optionally resizes the whole table. More...
void	clear ()
	Clear table. More...
	~concurrent_hash_map ()
	Clear table and destroy it. More...
range_type	range (size_type grainsize=1)
const_range_type	range (size_type grainsize=1) const
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
std::pair< iterator, iterator >	equal_range (const Key &key)
std::pair< const_iterator, const_iterator >	equal_range (const Key &key) const
size_type	size () const
	Number of items in table. More...
bool	empty () const
	True if size()==0. More...
size_type	max_size () const
	Upper bound on size. More...
size_type	bucket_count () const
	Returns the current number of buckets. More...
allocator_type	get_allocator () const
	return allocator object More...
void	swap (concurrent_hash_map &table)
	swap two instances. Iterators are invalidated More...
size_type	count (const Key &key) const
	Return count of items (0 or 1) More...
bool	find (const_accessor &result, const Key &key) const
	Find item and acquire a read lock on the item. More...
bool	find (accessor &result, const Key &key)
	Find item and acquire a write lock on the item. More...
bool	insert (const_accessor &result, const Key &key)
	Insert item (if not already present) and acquire a read lock on the item. More...
bool	insert (accessor &result, const Key &key)
	Insert item (if not already present) and acquire a write lock on the item. More...
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. More...
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. More...
bool	insert (const value_type &value)
	Insert item by copying if there is no such key present already. More...
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. More...
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. More...
bool	insert (value_type &&value)
	Insert item by copying if there is no such key present already. More...
template<typename... Args>
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. More...
template<typename... Args>
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. More...
template<typename... Args>
bool	emplace (Args &&... args)
	Insert item by copying if there is no such key present already. More...
template<typename I >
void	insert (I first, I last)
	Insert range [first, last) More...
void	insert (std::initializer_list< value_type > il)
	Insert initializer list. More...
bool	erase (const Key &key)
	Erase item. More...
bool	erase (const_accessor &item_accessor)
	Erase item by const_accessor. More...
bool	erase (accessor &item_accessor)
	Erase item by accessor. More...

Protected Types
typedef Allocator::template rebind< node >::other	node_allocator_type
Protected Types inherited from tbb::interface5::internal::hash_map_base
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...

Protected Member Functions
void	delete_node (node_base *n)
node *	search_bucket (const key_type &key, bucket *b) const
void	rehash_bucket (bucket *b_new, const hashcode_t h)
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. More...
template<typename Accessor >
bool	generic_move_insert (Accessor &&result, value_type &&value)
template<typename Accessor , typename... Args>
bool	generic_emplace (Accessor &&result, Args &&... args)
bool	exclude (const_accessor &item_accessor)
	delete item by accessor More...
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) More...
void	internal_copy (const concurrent_hash_map &source)
	Copy "source" to *this, where *this must start out empty. More...
template<typename I >
void	internal_copy (I first, I last, size_type reserve_size)
const_pointer	internal_fast_find (const Key &key) const
	Fast find when no concurrent erasure is used. For internal use inside TBB only! More...
Protected Member Functions inherited from tbb::interface5::internal::hash_map_base
	hash_map_base ()
	Constructor. More...
void	enable_segment (segment_index_t k, bool is_initial=false)
	Enable segment. More...
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...
void	reserve (size_type buckets)
	Prepare enough segments for number of buckets. More...
void	internal_swap (hash_map_base &table)
	Swap hash_map_bases. More...

Static Protected Member Functions
static node *	allocate_node_copy_construct (node_allocator_type &allocator, const Key &key, const T *t)
static node *	allocate_node_move_construct (node_allocator_type &allocator, const Key &key, const T *t)
template<typename... Args>
static node *	allocate_node_emplace_construct (node_allocator_type &allocator, Args &&... args)
static node *	allocate_node_default_construct (node_allocator_type &allocator, const Key &key, const T *)
static node *	do_not_allocate_node (node_allocator_type &, const Key &, const T *)
Static Protected Member Functions inherited from tbb::interface5::internal::hash_map_base
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...

Protected Attributes
node_allocator_type	my_allocator
HashCompare	my_hash_compare
Protected Attributes inherited from tbb::interface5::internal::hash_map_base
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...

Friends
template<typename Container , typename Value >
class	internal::hash_map_iterator
template<typename I >
class	internal::hash_map_range
class	const_accessor
const_accessor *	accessor_location (accessor_not_used const &)
const_accessor *	accessor_location (const_accessor &a)
bool	is_write_access_needed (accessor const &)
bool	is_write_access_needed (const_accessor const &)
bool	is_write_access_needed (accessor_not_used const &)

Additional Inherited Members
Static Protected Attributes inherited from tbb::interface5::internal::hash_map_base
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

template<typename Key, typename T, typename HashCompare, typename Allocator>
class tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >

Unordered map from Key to T.

concurrent_hash_map is associative container with concurrent access.

Compatibility

The class meets all Container Requirements from C++ Standard (See ISO/IEC 14882:2003(E), clause 23.1).

Exception Safety

• Hash function is not permitted to throw an exception. User-defined types Key and T are forbidden from throwing an exception in destructors.
• If exception happens during insert() operations, it has no effect (unless exception raised by HashCompare::hash() function during grow_segment).
• If exception happens during operator=() operation, the container can have a part of source items, and methods size() and empty() can return wrong results.

Changes since TBB 2.1

• Replaced internal algorithm and data structure. Patent is pending.
• Added buckets number argument for constructor

Changes since TBB 2.0

• Fixed exception-safety
• Added template argument for allocator
• Added allocator argument in constructors
• Added constructor from a range of iterators
• Added several new overloaded insert() methods
• Added get_allocator()
• Added swap()
• Added count()
• Added overloaded erase(accessor &) and erase(const_accessor&)
• Added equal_range() [const]
• Added [const_]pointer, [const_]reference, and allocator_type types
• Added global functions: operator==(), operator!=(), and swap()

Definition at line 52 of file concurrent_hash_map.h.

Member Typedef Documentation

allocator_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef Allocator tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocator_type

Definition at line 552 of file concurrent_hash_map.h.

const_iterator

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef internal::hash_map_iterator<concurrent_hash_map,const value_type> tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_iterator

Definition at line 549 of file concurrent_hash_map.h.

const_pointer

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef const value_type* tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_pointer

Definition at line 545 of file concurrent_hash_map.h.

const_range_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef internal::hash_map_range<const_iterator> tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_range_type

Definition at line 551 of file concurrent_hash_map.h.

const_reference

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef const value_type& tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_reference

Definition at line 547 of file concurrent_hash_map.h.

difference_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef ptrdiff_t tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::difference_type

Definition at line 543 of file concurrent_hash_map.h.

iterator

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef internal::hash_map_iterator<concurrent_hash_map,value_type> tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::iterator

Definition at line 548 of file concurrent_hash_map.h.

key_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef Key tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::key_type

Definition at line 539 of file concurrent_hash_map.h.

mapped_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef T tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::mapped_type

Definition at line 540 of file concurrent_hash_map.h.

node_allocator_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef Allocator::template rebind<node>::other tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node_allocator_type

protected

Definition at line 556 of file concurrent_hash_map.h.

pointer

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef value_type* tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::pointer

Definition at line 544 of file concurrent_hash_map.h.

range_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef internal::hash_map_range<iterator> tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::range_type

Definition at line 550 of file concurrent_hash_map.h.

reference

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef value_type& tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::reference

Definition at line 546 of file concurrent_hash_map.h.

size_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef hash_map_base::size_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::size_type

Definition at line 542 of file concurrent_hash_map.h.

value_type

template<typename Key, typename T, typename HashCompare, typename Allocator>

typedef std::pair<const Key,T> tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::value_type

Definition at line 541 of file concurrent_hash_map.h.

Constructor & Destructor Documentation

concurrent_hash_map() [1/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( const allocator_type &  a = allocator_type() )

inlineexplicit

Construct empty table.

Definition at line 758 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a)
    {}

concurrent_hash_map() [2/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( const HashCompare &  compare, const allocator_type &  a = allocator_type()  )

inlineexplicit

Definition at line 762 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
    {}

concurrent_hash_map() [3/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( size_type  n, const allocator_type &  a = allocator_type()  )

inline

Construct empty table with n preallocated buckets. This number serves also as initial concurrency level.

Definition at line 767 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a)
    {
        reserve( n );
    }

References tbb::interface5::internal::hash_map_base::reserve().

Here is the call graph for this function:

concurrent_hash_map() [4/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( size_type  n, const HashCompare &  compare, const allocator_type &  a = allocator_type()  )

inline

Definition at line 773 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
    {
        reserve( n );
    }

References tbb::interface5::internal::hash_map_base::reserve().

Here is the call graph for this function:

concurrent_hash_map() [5/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::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

Copy constructor.

Definition at line 780 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a)
    {
        call_clear_on_leave scope_guard(this);
        internal_copy(table);
        scope_guard.dismiss();
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::call_clear_on_leave::dismiss(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy().

Here is the call graph for this function:

concurrent_hash_map() [6/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( concurrent_hash_map< Key, T, HashCompare, Allocator > &&  table )

inline

Move constructor.

Definition at line 790 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(std::move(table.get_allocator()))
    {
        swap(table);
    }

concurrent_hash_map() [7/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( concurrent_hash_map< Key, T, HashCompare, Allocator > &&  table, const allocator_type &  a  )

inline

Move constructor.

Definition at line 797 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a)
    {
        if (a == table.get_allocator()){
            this->swap(table);
        }else{
            call_clear_on_leave scope_guard(this);
            internal_copy(std::make_move_iterator(table.begin()), std::make_move_iterator(table.end()), table.size());
            scope_guard.dismiss();
        }
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::begin(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::call_clear_on_leave::dismiss(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::end(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::get_allocator(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::size(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::swap().

Here is the call graph for this function:

concurrent_hash_map() [8/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename I >

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( I  first, I  last, const allocator_type &  a = allocator_type()  )

inline

Construction with copying iteration range and given allocator instance.

Definition at line 812 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a)
    {
        call_clear_on_leave scope_guard(this);
        internal_copy(first, last, std::distance(first, last));
        scope_guard.dismiss();
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::call_clear_on_leave::dismiss(), tbb::internal::first(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), and tbb::internal::last().

Here is the call graph for this function:

concurrent_hash_map() [9/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename I >

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( I  first, I  last, const HashCompare &  compare, const allocator_type &  a = allocator_type()  )

inline

Definition at line 821 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
    {
        call_clear_on_leave scope_guard(this);
        internal_copy(first, last, std::distance(first, last));
        scope_guard.dismiss();
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::call_clear_on_leave::dismiss(), tbb::internal::first(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), and tbb::internal::last().

Here is the call graph for this function:

concurrent_hash_map() [10/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( std::initializer_list< value_type >  il, const allocator_type &  a = allocator_type()  )

inline

Construct empty table with n preallocated buckets. This number serves also as initial concurrency level.

Definition at line 831 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a)
    {
        call_clear_on_leave scope_guard(this);
        internal_copy(il.begin(), il.end(), il.size());
        scope_guard.dismiss();
    }

concurrent_hash_map() [11/11]

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map ( std::initializer_list< value_type >  il, const HashCompare &  compare, const allocator_type &  a = allocator_type()  )

inline

Definition at line 839 of file concurrent_hash_map.h.

        : internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
    {
        call_clear_on_leave scope_guard(this);
        internal_copy(il.begin(), il.end(), il.size());
        scope_guard.dismiss();
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::call_clear_on_leave::dismiss(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy().

Here is the call graph for this function:

~concurrent_hash_map()

template<typename Key, typename T, typename HashCompare, typename Allocator>

tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::~concurrent_hash_map ( )

inline

Clear table and destroy it.

Definition at line 896 of file concurrent_hash_map.h.

{ clear(); }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::clear().

Here is the call graph for this function:

Member Function Documentation

allocate_node_copy_construct()

template<typename Key, typename T, typename HashCompare, typename Allocator>

static node* tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_copy_construct ( node_allocator_type &  allocator, const Key &  key, const T *  t  )

inlinestaticprotected

Definition at line 594 of file concurrent_hash_map.h.

                                                                                                          {
        return  new( allocator ) node(key, *t);
    }

References key.

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

Here is the caller graph for this function:

allocate_node_default_construct()

template<typename Key, typename T, typename HashCompare, typename Allocator>

static node* tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_default_construct ( node_allocator_type &  allocator, const Key &  key, const T *    )

inlinestaticprotected

Definition at line 610 of file concurrent_hash_map.h.

                                                                                                            {
        return  new( allocator ) node(key);
    }

References key.

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

Here is the caller graph for this function:

allocate_node_emplace_construct()

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename... Args>

static node* tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_emplace_construct ( node_allocator_type &  allocator, Args &&...  args  )

inlinestaticprotected

Definition at line 604 of file concurrent_hash_map.h.

                                                                                                {
        return  new( allocator ) node(std::forward<Args>(args)...);
    }

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

Here is the caller graph for this function:

allocate_node_move_construct()

template<typename Key, typename T, typename HashCompare, typename Allocator>

static node* tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_move_construct ( node_allocator_type &  allocator, const Key &  key, const T *  t  )

inlinestaticprotected

Definition at line 599 of file concurrent_hash_map.h.

                                                                                                          {
        return  new( allocator ) node(key, std::move(*const_cast<T*>(t)));
    }

References key, and tbb::move().

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

Here is the call graph for this function:

Here is the caller graph for this function:

begin() [1/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

iterator tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::begin ( )

inline

Definition at line 911 of file concurrent_hash_map.h.

{ return iterator( *this, 0, my_embedded_segment, my_embedded_segment->node_list ); }

References tbb::interface5::internal::hash_map_base::my_embedded_segment, and tbb::interface5::internal::hash_map_base::bucket::node_list.

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

Here is the caller graph for this function:

begin() [2/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

const_iterator tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::begin ( ) const

inline

Definition at line 913 of file concurrent_hash_map.h.

{ return const_iterator( *this, 0, my_embedded_segment, my_embedded_segment->node_list ); }

References tbb::interface5::internal::hash_map_base::my_embedded_segment, and tbb::interface5::internal::hash_map_base::bucket::node_list.

bucket_count()

template<typename Key, typename T, typename HashCompare, typename Allocator>

size_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_count ( ) const

inline

Returns the current number of buckets.

Definition at line 928 of file concurrent_hash_map.h.

{ return my_mask+1; }

References tbb::interface5::internal::hash_map_base::my_mask.

clear()

template<typename Key , typename T , typename HashCompare , typename A >

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::clear

(

)

Clear table.

Definition at line 1384 of file concurrent_hash_map.h.

                                                     {
    hashcode_t m = my_mask;
    __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
#if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
#if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
    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 || __TBB_STATISTICS
        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 || __TBB_STATISTICS
#if __TBB_STATISTICS
    printf( "items=%d buckets: capacity=%d rehashed=%d empty=%d overpopulated=%d"
        " concurrent: resizes=%u rehashes=%u restarts=%u\n",
        current_size, int(m+1), buckets, empty_buckets, overpopulated_buckets,
        unsigned(my_info_resizes), unsigned(my_info_rehashes), unsigned(my_info_restarts) );
    my_info_resizes = 0; // concurrent ones
    my_info_restarts = 0; // race collisions
    my_info_rehashes = 0;  // invocations of rehash_bucket
#endif
    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",
#if __TBB_USE_OPTIONAL_RTTI
            typeid(*this).name(),
#else
            "concurrent_hash_map",
#endif
            current_size, empty_buckets, overpopulated_buckets );
        reported = true;
    }
#endif
#endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
    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 );
        if( s >= embedded_block ) my_table[s] = 0;
    } while(s-- > 0);
    my_mask = embedded_buckets - 1;
}

References __TBB_ASSERT, __TBB_USE_OPTIONAL_RTTI, tbb::cache_aligned_allocator< T >::deallocate(), tbb::interface5::internal::empty_rehashed, h, int, tbb::interface5::internal::hash_map_base::bucket::mutex, tbb::interface5::internal::hash_map_node_base::next, tbb::interface5::internal::hash_map_base::bucket::node_list, tbb::interface5::internal::rehash_req, tbb::internal::runtime_warning(), and s.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::operator=(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::call_clear_on_leave::~call_clear_on_leave(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::~concurrent_hash_map().

Here is the call graph for this function:

Here is the caller graph for this function:

count()

template<typename Key, typename T, typename HashCompare, typename Allocator>

size_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::count ( const Key &  key ) const

inline

Return count of items (0 or 1)

Definition at line 941 of file concurrent_hash_map.h.

                                            {
        return const_cast<concurrent_hash_map*>(this)->lookup(/*insert*/false, key, NULL, NULL, /*write=*/false, &do_not_allocate_node );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::do_not_allocate_node(), and key.

Here is the call graph for this function:

delete_node()

template<typename Key, typename T, typename HashCompare, typename Allocator>

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::delete_node ( node_base *  n )

inlineprotected

Definition at line 589 of file concurrent_hash_map.h.

                                     {
        my_allocator.destroy( static_cast<node*>(n) );
        my_allocator.deallocate( static_cast<node*>(n), 1);
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator.

do_not_allocate_node()

template<typename Key, typename T, typename HashCompare, typename Allocator>

static node* tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::do_not_allocate_node ( node_allocator_type &  , const Key &  , const T *    )

inlinestaticprotected

Definition at line 614 of file concurrent_hash_map.h.

                                                                                     {
        __TBB_ASSERT(false,"this dummy function should not be called");
        return NULL;
    }

References __TBB_ASSERT.

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

Here is the caller graph for this function:

emplace() [1/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename... Args>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::emplace ( const_accessor &  result, Args &&...  args  )

inline

Insert item by copying if there is no such key present already and acquire a read lock on the item.

Returns true if item is new.

Definition at line 1016 of file concurrent_hash_map.h.

                                                           {
        return generic_emplace(result, std::forward<Args>(args)...);
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_emplace().

Here is the call graph for this function:

emplace() [2/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename... Args>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::emplace ( accessor &  result, Args &&...  args  )

inline

Insert item by copying if there is no such key present already and acquire a write lock on the item.

Returns true if item is new.

Definition at line 1023 of file concurrent_hash_map.h.

                                                     {
        return generic_emplace(result, std::forward<Args>(args)...);
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_emplace().

Here is the call graph for this function:

emplace() [3/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename... Args>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::emplace ( Args &&...  args )

inline

Insert item by copying if there is no such key present already.

Returns true if item is inserted.

Definition at line 1030 of file concurrent_hash_map.h.

                                   {
        return generic_emplace(accessor_not_used(), std::forward<Args>(args)...);
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_emplace().

Here is the call graph for this function:

empty()

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::empty ( ) const

inline

True if size()==0.

Definition at line 922 of file concurrent_hash_map.h.

{ return my_size == 0; }

References tbb::interface5::internal::hash_map_base::my_size.

end() [1/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

iterator tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::end ( )

inline

Definition at line 912 of file concurrent_hash_map.h.

{ return iterator( *this, 0, 0, 0 ); }

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::equal_range(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), and tbb::operator==().

Here is the caller graph for this function:

end() [2/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

const_iterator tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::end ( ) const

inline

Definition at line 914 of file concurrent_hash_map.h.

{ return const_iterator( *this, 0, 0, 0 ); }

equal_range() [1/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

std::pair<iterator, iterator> tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::equal_range ( const Key &  key )

inline

Definition at line 915 of file concurrent_hash_map.h.

{ return internal_equal_range( key, end() ); }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::end(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_equal_range(), and key.

Referenced by tbb::operator==().

Here is the call graph for this function:

Here is the caller graph for this function:

equal_range() [2/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

std::pair<const_iterator, const_iterator> tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::equal_range ( const Key &  key ) const

inline

Definition at line 916 of file concurrent_hash_map.h.

{ return internal_equal_range( key, end() ); }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::end(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_equal_range(), and key.

Here is the call graph for this function:

erase() [1/3]

template<typename Key , typename T , typename HashCompare , typename A >

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::erase

(

const Key &

key

)

Erase item.

Return true if item was erased by particularly this call.

Definition at line 1267 of file concurrent_hash_map.h.

                                                                     {
    node_base *n;
    hashcode_t const h = my_hash_compare.hash( key );
    hashcode_t m = (hashcode_t) itt_load_word_with_acquire( my_mask );
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 );
    }
    // note: there should be no threads pretending to acquire this mutex again, do not try to upgrade const_accessor!
    delete_node( n ); // Only one thread can delete it due to write lock on the bucket
    return true;
}

References h, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_accessor::is_writer(), tbb::internal::itt_load_word_with_acquire(), key, tbb::interface5::internal::hash_map_node_base::mutex, tbb::interface5::internal::hash_map_node_base::next, and p.

Here is the call graph for this function:

erase() [2/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::erase ( const_accessor &  item_accessor )

inline

Erase item by const_accessor.

Return true if item was erased by particularly this call.

Definition at line 1056 of file concurrent_hash_map.h.

                                                {
        return exclude( item_accessor );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::exclude().

Here is the call graph for this function:

erase() [3/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::erase ( accessor &  item_accessor )

inline

Erase item by accessor.

Return true if item was erased by particularly this call.

Definition at line 1062 of file concurrent_hash_map.h.

                                          {
        return exclude( item_accessor );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::exclude().

Here is the call graph for this function:

exclude()

template<typename Key , typename T , typename HashCompare , typename A >

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::exclude ( const_accessor &  item_accessor )

protected

delete item by accessor

Definition at line 1237 of file concurrent_hash_map.h.

                                                                                      {
    __TBB_ASSERT( item_accessor.my_node, NULL );
    node_base *const n = item_accessor.my_node;
    hashcode_t const h = item_accessor.my_hash;
    hashcode_t m = (hashcode_t) itt_load_word_with_acquire( my_mask );
    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 first
            if( check_mask_race( h, m ) )
                continue;
            item_accessor.release();
            return false;
        }
        __TBB_ASSERT( *p == n, NULL );
        *p = n->next; // remove from container
        my_size--;
        break;
    } while(true);
    if( !item_accessor.is_writer() ) // need to get exclusive lock
        item_accessor.upgrade_to_writer(); // return value means nothing here
    item_accessor.release();
    delete_node( n ); // Only one thread can delete it
    return true;
}

References __TBB_ASSERT, h, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::is_writer(), tbb::internal::itt_load_word_with_acquire(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::my_hash, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::my_node, tbb::interface5::internal::hash_map_node_base::next, p, and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::release().

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

Here is the call graph for this function:

Here is the caller graph for this function:

find() [1/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::find ( const_accessor &  result, const Key &  key  ) const

inline

Find item and acquire a read lock on the item.

Return true if item is found, false otherwise.

Definition at line 947 of file concurrent_hash_map.h.

                                                              {
        result.release();
        return const_cast<concurrent_hash_map*>(this)->lookup(/*insert*/false, key, NULL, &result, /*write=*/false, &do_not_allocate_node );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::do_not_allocate_node(), key, and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::release().

Here is the call graph for this function:

find() [2/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::find ( accessor &  result, const Key &  key  )

inline

Find item and acquire a write lock on the item.

Return true if item is found, false otherwise.

Definition at line 954 of file concurrent_hash_map.h.

                                                  {
        result.release();
        return lookup(/*insert*/false, key, NULL, &result, /*write=*/true, &do_not_allocate_node );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::do_not_allocate_node(), key, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::release().

Here is the call graph for this function:

generic_emplace()

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename Accessor , typename... Args>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_emplace ( Accessor &&  result, Args &&...  args  )

inlineprotected

Definition at line 1087 of file concurrent_hash_map.h.

                                                                {
        result.release();
        node * node_ptr = allocate_node_emplace_construct(my_allocator, std::forward<Args>(args)...);
        return lookup(/*insert*/true, node_ptr->item.first, NULL, accessor_location(result), is_write_access_needed(result), &do_not_allocate_node, node_ptr );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::accessor_location, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_emplace_construct(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::do_not_allocate_node(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::is_write_access_needed, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::item, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator.

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

Here is the call graph for this function:

Here is the caller graph for this function:

generic_move_insert()

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename Accessor >

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_move_insert ( Accessor &&  result, value_type &&  value  )

inlineprotected

Definition at line 1080 of file concurrent_hash_map.h.

                                                                        {
        result.release();
        return lookup(/*insert*/true, value.first, &value.second, accessor_location(result), is_write_access_needed(result), &allocate_node_move_construct );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::accessor_location, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_move_construct(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::is_write_access_needed, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup(), and value.

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

Here is the call graph for this function:

Here is the caller graph for this function:

get_allocator()

template<typename Key, typename T, typename HashCompare, typename Allocator>

allocator_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::get_allocator ( ) const

inline

return allocator object

Definition at line 931 of file concurrent_hash_map.h.

{ return this->my_allocator; }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator.

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

Here is the caller graph for this function:

insert() [1/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( const_accessor &  result, const Key &  key  )

inline

Insert item (if not already present) and acquire a read lock on the item.

Returns true if item is new.

Definition at line 961 of file concurrent_hash_map.h.

                                                          {
        result.release();
        return lookup(/*insert*/true, key, NULL, &result, /*write=*/false, &allocate_node_default_construct );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_default_construct(), key, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::release().

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

Here is the call graph for this function:

Here is the caller graph for this function:

insert() [2/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( accessor &  result, const Key &  key  )

inline

Insert item (if not already present) and acquire a write lock on the item.

Returns true if item is new.

Definition at line 968 of file concurrent_hash_map.h.

                                                    {
        result.release();
        return lookup(/*insert*/true, key, NULL, &result, /*write=*/true, &allocate_node_default_construct );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_default_construct(), key, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::release().

Here is the call graph for this function:

insert() [3/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( const_accessor &  result, const value_type &  value  )

inline

Insert item by copying if there is no such key present already and acquire a read lock on the item.

Returns true if item is new.

Definition at line 975 of file concurrent_hash_map.h.

                                                                   {
        result.release();
        return lookup(/*insert*/true, value.first, &value.second, &result, /*write=*/false, &allocate_node_copy_construct );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_copy_construct(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::release(), and value.

Here is the call graph for this function:

insert() [4/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( accessor &  result, const value_type &  value  )

inline

Insert item by copying if there is no such key present already and acquire a write lock on the item.

Returns true if item is new.

Definition at line 982 of file concurrent_hash_map.h.

                                                             {
        result.release();
        return lookup(/*insert*/true, value.first, &value.second, &result, /*write=*/true, &allocate_node_copy_construct );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_copy_construct(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::release(), and value.

Here is the call graph for this function:

insert() [5/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( const value_type &  value )

inline

Insert item by copying if there is no such key present already.

Returns true if item is inserted.

Definition at line 989 of file concurrent_hash_map.h.

                                           {
        return lookup(/*insert*/true, value.first, &value.second, NULL, /*write=*/false, &allocate_node_copy_construct );
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::allocate_node_copy_construct(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::lookup(), and value.

Here is the call graph for this function:

insert() [6/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( const_accessor &  result, value_type &&  value  )

inline

Insert item by copying if there is no such key present already and acquire a read lock on the item.

Returns true if item is new.

Definition at line 996 of file concurrent_hash_map.h.

                                                               {
        return generic_move_insert(result, std::move(value));
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_move_insert(), tbb::move(), and value.

Here is the call graph for this function:

insert() [7/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( accessor &  result, value_type &&  value  )

inline

Insert item by copying if there is no such key present already and acquire a write lock on the item.

Returns true if item is new.

Definition at line 1002 of file concurrent_hash_map.h.

                                                         {
        return generic_move_insert(result, std::move(value));
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_move_insert(), tbb::move(), and value.

Here is the call graph for this function:

insert() [8/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( value_type &&  value )

inline

Insert item by copying if there is no such key present already.

Returns true if item is inserted.

Definition at line 1008 of file concurrent_hash_map.h.

                                       {
        return generic_move_insert(accessor_not_used(), std::move(value));
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_move_insert(), tbb::move(), and value.

Here is the call graph for this function:

insert() [9/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename I >

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( I  first, I  last  )

inline

Insert range [first, last)

Definition at line 1038 of file concurrent_hash_map.h.

                                   {
        for ( ; first != last; ++first )
            insert( *first );
    }

References tbb::internal::first(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert(), and tbb::internal::last().

Here is the call graph for this function:

insert() [10/10]

template<typename Key, typename T, typename HashCompare, typename Allocator>

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert ( std::initializer_list< value_type >  il )

inline

Insert initializer list.

Definition at line 1045 of file concurrent_hash_map.h.

                                                      {
        insert( il.begin(), il.end() );
    }

internal_copy() [1/2]

template<typename Key , typename T , typename HashCompare , typename A >

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::internal_copy ( const concurrent_hash_map< Key, T, HashCompare, Allocator > &  source )

protected

Copy "source" to *this, where *this must start out empty.

Definition at line 1461 of file concurrent_hash_map.h.

                                                                                                {
    hashcode_t mask = source.my_mask;
    if( my_mask == mask ) { // optimized version
        reserve( source.my_size ); // TODO: load_factor?
        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
            }
        }
        if( rehash_required ) rehash();
    } else internal_copy( source.begin(), source.end(), source.my_size );
}

References __TBB_ASSERT, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::begin(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::end(), tbb::interface5::internal::hash_map_base::get_bucket(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::item, mask, tbb::interface5::internal::hash_map_base::my_mask, tbb::interface5::internal::hash_map_base::my_size, 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 >::concurrent_hash_map(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

internal_copy() [2/2]

template<typename Key , typename T , typename HashCompare , typename A >

template<typename I >

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::internal_copy ( I  first, I  last, size_type  reserve_size  )

protected

Definition at line 1486 of file concurrent_hash_map.h.

                                                                                                    {
    reserve( reserve_size ); // TODO: load_factor?
    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);
        add_to_bucket( b, n );
        ++my_size; // TODO: replace by non-atomic op
    }
}

References __TBB_ASSERT, tbb::internal::first(), h, tbb::internal::last(), tbb::interface5::internal::hash_map_base::bucket::node_list, and tbb::interface5::internal::rehash_req.

Here is the call graph for this function:

internal_equal_range()

template<typename Key , typename T , typename HashCompare , typename A >

template<typename I >

std::pair< I, I > tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::internal_equal_range ( const Key &  key, I  end  ) const

protected

Returns an iterator for an item defined by the key, or for the next item after it (if upper==true)

Definition at line 1219 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, "data structure is invalid");
    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 )
        return std::make_pair(end_, end_);
    iterator lower(*this, h, b, n), upper(lower);
    return std::make_pair(lower, ++upper);
}

References __TBB_ASSERT, __TBB_Log2(), h, key, 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 >::equal_range().

Here is the call graph for this function:

Here is the caller graph for this function:

internal_fast_find()

template<typename Key, typename T, typename HashCompare, typename Allocator>

const_pointer tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_fast_find ( const Key &  key ) const

inlineprotected

Fast find when no concurrent erasure is used. For internal use inside TBB only!

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 1111 of file concurrent_hash_map.h.

                                                             {
        hashcode_t h = my_hash_compare.hash( key );
        hashcode_t m = (hashcode_t) itt_load_word_with_acquire( my_mask );
        node *n;
    restart:
        __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
        bucket *b = get_bucket( h & m );
        // TODO: actually, notification is unnecessary here, just hiding double-check
        if( itt_load_word_with_acquire(b->node_list) == internal::rehash_req )
        {
            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;
        else if( check_mask_race( h, m ) )
            goto restart;
        return 0;
    }

References __TBB_ASSERT, tbb::interface5::internal::hash_map_base::check_mask_race(), tbb::interface5::internal::hash_map_base::get_bucket(), h, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::item, tbb::internal::itt_load_word_with_acquire(), key, lock, tbb::interface5::internal::hash_map_base::bucket::mutex, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_hash_compare, tbb::interface5::internal::hash_map_base::my_mask, tbb::interface5::internal::hash_map_base::bucket::node_list, tbb::interface5::internal::rehash_req, and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::search_bucket().

Here is the call graph for this function:

lookup()

template<typename Key , typename T , typename HashCompare , typename A >

bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::lookup ( bool  op_insert, const Key &  key, const T *  t, const_accessor *  result, bool  write, node *(*)(node_allocator_type &, const Key &, const T *)  allocate_node, node *  tmp_n = 0  )

protected

Insert or find item and optionally acquire a lock on the item.

Definition at line 1139 of file concurrent_hash_map.h.

                                                                                                                                                                                                                        {
    __TBB_ASSERT( !result || !result->my_node, NULL );
    bool return_value;
    hashcode_t const h = my_hash_compare.hash( key );
    hashcode_t m = (hashcode_t) itt_load_word_with_acquire( my_mask );
    segment_index_t grow_segment = 0;
    node *n;
    restart:
    {//lock scope
        __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
        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 ) {
                    tmp_n = allocate_node(my_allocator, key, t);
                }
                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 { // 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;
        }
    exists:
        if( !result ) goto check_growth;
        // TODO: the following seems as generic/regular operation
        // acquire the item
        if( !result->try_acquire( n->mutex, write ) ) {
            for( tbb::internal::atomic_backoff backoff(true);; ) {
                if( result->try_acquire( n->mutex, write ) ) break;
                if( !backoff.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();
                    m = (hashcode_t) itt_load_word_with_acquire( my_mask );
                    goto restart;
                }
            }
        }
    }//lock scope
    result->my_node = n;
    result->my_hash = h;
check_growth:
    // [opt] grow the container
    if( grow_segment ) {
#if __TBB_STATISTICS
        my_info_resizes++; // concurrent ones
#endif
        enable_segment( grow_segment );
    }
    if( tmp_n ) // if op_insert only
        delete_node( tmp_n );
    return return_value;
}

References __TBB_ASSERT, __TBB_Yield, h, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_accessor::is_writer(), tbb::internal::itt_load_word_with_acquire(), key, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::my_hash, and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::const_accessor::my_node.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::find(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_emplace(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_move_insert(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::insert().

Here is the call graph for this function:

Here is the caller graph for this function:

max_size()

template<typename Key, typename T, typename HashCompare, typename Allocator>

size_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::max_size ( ) const

inline

Upper bound on size.

Definition at line 925 of file concurrent_hash_map.h.

{return (~size_type(0))/sizeof(node);}

operator=() [1/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

concurrent_hash_map& tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::operator= ( const concurrent_hash_map< Key, T, HashCompare, Allocator > &  table )

inline

Assignment.

Definition at line 850 of file concurrent_hash_map.h.

                                                                       {
        if( this!=&table ) {
            clear();
            internal_copy(table);
        }
        return *this;
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::clear(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy().

Here is the call graph for this function:

operator=() [2/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

concurrent_hash_map& tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::operator= ( concurrent_hash_map< Key, T, HashCompare, Allocator > &&  table )

inline

Move Assignment.

Definition at line 860 of file concurrent_hash_map.h.

                                                                  {
        if(this != &table){
            typedef typename tbb::internal::allocator_traits<allocator_type>::propagate_on_container_move_assignment pocma_t;
            if(pocma_t::value || this->my_allocator == table.my_allocator) {
                concurrent_hash_map trash (std::move(*this));
                //TODO: swapping allocators here may be a problem, replace with single direction moving iff pocma is set
                this->swap(table);
            } else {
                //do per element move
                concurrent_hash_map moved_copy(std::move(table), this->my_allocator);
                this->swap(moved_copy);
            }
        }
        return *this;
    }

operator=() [3/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

concurrent_hash_map& tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::operator= ( std::initializer_list< value_type >  il )

inline

Assignment.

Definition at line 879 of file concurrent_hash_map.h.

                                                                         {
        clear();
        internal_copy(il.begin(), il.end(), il.size());
        return *this;
    }

range() [1/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

range_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::range ( size_type  grainsize = 1 )

inline

Definition at line 901 of file concurrent_hash_map.h.

                                              {
        return range_type( *this, grainsize );
    }

range() [2/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

const_range_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::range ( size_type  grainsize = 1 ) const

inline

Definition at line 904 of file concurrent_hash_map.h.

                                                          {
        return const_range_type( *this, grainsize );
    }

rehash()

template<typename Key , typename T , typename HashCompare , typename A >

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::rehash

(

size_type

n = 0

)

Rehashes and optionally resizes the whole table.

Useful to optimize performance before or after concurrent operations. Also enables using of find() and count() concurrent methods in serial context.

Definition at line 1313 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); // zero or power of 2
    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",
#if __TBB_USE_OPTIONAL_RTTI
            typeid(*this).name(),
#else
            "concurrent_hash_map",
#endif
            current_size, empty_buckets, overpopulated_buckets );
        reported = true;
    }
#endif
}

References __TBB_ASSERT, __TBB_Log2(), __TBB_USE_OPTIONAL_RTTI, tbb::interface5::internal::empty_rehashed, h, int, mask, tbb::interface5::internal::hash_map_base::bucket::mutex, tbb::interface5::internal::hash_map_node_base::next, tbb::interface5::internal::hash_map_base::bucket::node_list, p, tbb::interface5::internal::rehash_req, and tbb::internal::runtime_warning().

Here is the call graph for this function:

rehash_bucket()

template<typename Key, typename T, typename HashCompare, typename Allocator>

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::rehash_bucket ( bucket *  b_new, const hashcode_t  h  )

inlineprotected

Definition at line 651 of file concurrent_hash_map.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
#if __TBB_STATISTICS
        my_info_rehashes++; // invocations of rehash_bucket
#endif

        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
                add_to_bucket( b_new, n );
            } else p = &n->next; // iterate to next item
        }
    }

References __TBB_ASSERT, tbb::internal::__TBB_load_with_acquire(), __TBB_Log2(), tbb::internal::__TBB_store_with_release(), tbb::interface5::internal::hash_map_base::add_to_bucket(), tbb::interface5::internal::empty_rehashed, h, tbb::interface5::internal::hash_map_base::is_valid(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::bucket_accessor::is_writer(), mask, tbb::interface5::internal::hash_map_base::bucket::mutex, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_hash_compare, tbb::interface5::internal::hash_map_base::bucket::node_list, and p.

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

Here is the call graph for this function:

Here is the caller graph for this function:

search_bucket()

template<typename Key, typename T, typename HashCompare, typename Allocator>

node* tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::search_bucket ( const key_type &  key, bucket *  b  ) const

inlineprotected

Definition at line 619 of file concurrent_hash_map.h.

                                                                {
        node *n = static_cast<node*>( b->node_list );
        while( is_valid(n) && !my_hash_compare.equal(key, n->item.first) )
            n = static_cast<node*>( n->next );
        __TBB_ASSERT(n != internal::rehash_req, "Search can be executed only for rehashed bucket");
        return n;
    }

References __TBB_ASSERT, tbb::interface5::internal::hash_map_base::is_valid(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::item, key, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_hash_compare, 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 >::internal_fast_find().

Here is the call graph for this function:

Here is the caller graph for this function:

size()

template<typename Key, typename T, typename HashCompare, typename Allocator>

size_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::size ( ) const

inline

Number of items in table.

Definition at line 919 of file concurrent_hash_map.h.

{ return my_size; }

References tbb::interface5::internal::hash_map_base::my_size.

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

Here is the caller graph for this function:

swap()

template<typename Key, typename T, typename HashCompare, typename Allocator>

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::swap

(

concurrent_hash_map< Key, T, HashCompare, Allocator > &

table

)

swap two instances. Iterators are invalidated

Definition at line 1304 of file concurrent_hash_map.h.

                                                                                                   {
    //TODO: respect C++11 allocator_traits<A>::propogate_on_constainer_swap
    using std::swap;
    swap(this->my_allocator, table.my_allocator);
    swap(this->my_hash_compare, table.my_hash_compare);
    internal_swap(table);
}

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_hash_compare, and tbb::swap().

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

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

accessor_location [1/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

const_accessor* accessor_location ( accessor_not_used const &  )

friend

Definition at line 1071 of file concurrent_hash_map.h.

{ return NULL;}

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

accessor_location [2/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>

const_accessor* accessor_location ( const_accessor &  a )

friend

Definition at line 1072 of file concurrent_hash_map.h.

{ return &a;}

const_accessor

template<typename Key, typename T, typename HashCompare, typename Allocator>

friend class const_accessor

friend

Definition at line 555 of file concurrent_hash_map.h.

internal::hash_map_iterator

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename Container , typename Value >

friend class internal::hash_map_iterator

friend

Definition at line 533 of file concurrent_hash_map.h.

internal::hash_map_range

template<typename Key, typename T, typename HashCompare, typename Allocator>

template<typename I >

friend class internal::hash_map_range

friend

Definition at line 536 of file concurrent_hash_map.h.

is_write_access_needed [1/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool is_write_access_needed ( accessor const &  )

friend

Definition at line 1074 of file concurrent_hash_map.h.

{ return true;}

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

is_write_access_needed [2/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool is_write_access_needed ( const_accessor const &  )

friend

Definition at line 1075 of file concurrent_hash_map.h.

{ return false;}

is_write_access_needed [3/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>

bool is_write_access_needed ( accessor_not_used const &  )

friend

Definition at line 1076 of file concurrent_hash_map.h.

{ return false;}

Member Data Documentation

my_allocator

template<typename Key, typename T, typename HashCompare, typename Allocator>

node_allocator_type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator

protected

Definition at line 558 of file concurrent_hash_map.h.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::delete_node(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::generic_emplace(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::get_allocator(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::swap().

my_hash_compare

template<typename Key, typename T, typename HashCompare, typename Allocator>

HashCompare tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_hash_compare

protected

Definition at line 559 of file concurrent_hash_map.h.

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

---

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

• concurrent_hash_map.h