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...
class	node
struct	node_scoped_guard

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)
	Copy constructor. More...
	concurrent_hash_map (const concurrent_hash_map &table, const allocator_type &a)
	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 tbb::internal::allocator_rebind< Allocator, node >::type	node_allocator_type
typedef tbb::internal::allocator_traits< node_allocator_type >	node_allocator_traits
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)
void	internal_move_assign (concurrent_hash_map &&other, tbb::internal::traits_true_type)
void	internal_move_assign (concurrent_hash_map &&other, tbb::internal::traits_false_type)
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...
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 Protected Member Functions
template<typename... Args>
static node *	create_node (node_allocator_type &allocator, Args &&... args)
static node *	allocate_node_copy_construct (node_allocator_type &allocator, const Key &key, const T *t)
static node *	allocate_node_move_construct (node_allocator_type &allocator, const Key &key, const T *t)
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 58 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 606 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 603 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 599 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 605 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 601 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 597 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 602 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 593 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 594 of file concurrent_hash_map.h.

node_allocator_traits

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

typedef tbb::internal::allocator_traits<node_allocator_type> tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node_allocator_traits

protected

Definition at line 612 of file concurrent_hash_map.h.

node_allocator_type

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

typedef tbb::internal::allocator_rebind<Allocator, node>::type tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node_allocator_type

protected

Definition at line 610 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 598 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 604 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 600 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 596 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 595 of file concurrent_hash_map.h.

Constructor & Destructor Documentation

concurrent_hash_map() [1/12]

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

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

concurrent_hash_map() [2/12]

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

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

concurrent_hash_map() [3/12]

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

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

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator, and tbb::interface5::internal::hash_map_base::reserve().

Here is the call graph for this function:

concurrent_hash_map() [4/12]

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

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

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator, and tbb::interface5::internal::hash_map_base::reserve().

Here is the call graph for this function:

concurrent_hash_map() [5/12]

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 )

inline

Copy constructor.

Definition at line 852 of file concurrent_hash_map.h.

        : internal::hash_map_base(),
          my_allocator(node_allocator_traits::select_on_container_copy_construction(table.get_allocator()))
    {
        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/12]

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  )

inline

Definition at line 861 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() [7/12]

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

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

concurrent_hash_map() [8/12]

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

        : internal::hash_map_base(), my_allocator(a)
    {
        if (a == table.get_allocator()){
            internal_move(std::move(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 >::call_clear_on_leave::dismiss(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), tbb::interface5::internal::hash_map_base::internal_move(), and tbb::move().

Here is the call graph for this function:

concurrent_hash_map() [9/12]

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 893 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() [10/12]

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 902 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() [11/12]

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 912 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() [12/12]

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 920 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 971 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 663 of file concurrent_hash_map.h.

                                                                                                          {
        return create_node(allocator, key, *t);
    }

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

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:

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

                                                                                                            {
#if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_TUPLE_PRESENT
        // Emplace construct an empty T object inside the pair
        return create_node(allocator, std::piecewise_construct,
                           std::forward_as_tuple(key), std::forward_as_tuple());
#else
        // Use of a temporary object is impossible, because create_node takes a non-const reference.
        // copy-initialization is possible because T is already required to be CopyConstructible.
        T obj = T();
        return create_node(allocator, key, tbb::internal::move(obj));
#endif
    }

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

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:

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

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

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::create_node(), 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 986 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 >::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 988 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 1003 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 1505 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)->value().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" );
    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 );
            }
        delete_segment(s, my_allocator);
    } while(s-- > 0);
    my_mask = embedded_buckets - 1;
}

References __TBB_ASSERT, __TBB_USE_OPTIONAL_RTTI, tbb::interface5::internal::empty_rehashed, tbb::internal::first(), 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(), s, and value.

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 1016 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:

create_node()

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

template<typename... Args>

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

inlinestaticprotected

Definition at line 645 of file concurrent_hash_map.h.

    {
        node* node_ptr = node_allocator_traits::allocate(allocator, 1);
        node_scoped_guard guard(node_ptr, allocator);
        node_allocator_traits::construct(allocator, node_ptr);
#if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
        node_allocator_traits::construct(allocator, node_ptr->storage(), std::forward<Args>(args)...);
#else
        node_allocator_traits::construct(allocator, node_ptr->storage(), tbb::internal::forward<Arg1>(arg1), tbb::internal::forward<Arg2>(arg2));
#endif
        guard.dismiss();
        return node_ptr;
    }

References tbb::internal::allocator_traits< Alloc >::allocate(), tbb::internal::allocator_traits< Alloc >::construct(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node_scoped_guard::dismiss(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::storage().

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

Here is the call graph for this function:

Here is the caller 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 623 of file concurrent_hash_map.h.

                                     {
        node_allocator_traits::destroy(my_allocator, static_cast<node*>(n)->storage());
        node_allocator_traits::destroy(my_allocator, static_cast<node*>(n));
        node_allocator_traits::deallocate(my_allocator, static_cast<node*>(n), 1);
    }

References tbb::internal::allocator_traits< Alloc >::deallocate(), tbb::internal::allocator_traits< Alloc >::destroy(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator.

Here is the call graph for this function:

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 686 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 1091 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 1098 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 1105 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 997 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 987 of file concurrent_hash_map.h.

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

Referenced by 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 989 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 990 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 991 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 1386 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)->value().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 1131 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 1137 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 1356 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 1022 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 1029 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 1162 of file concurrent_hash_map.h.

                                                                {
        result.release();
        node * node_ptr = create_node(my_allocator, std::forward<Args>(args)...);
        return lookup(/*insert*/true, node_ptr->value().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 >::create_node(), 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 >::lookup(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator, and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::value().

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

{ return this->my_allocator; }

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

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 1036 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 1043 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 1050 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 1057 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 1064 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 1071 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 1077 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 1083 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 1113 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 1120 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 1577 of file concurrent_hash_map.h.

                                                                                                {
    hashcode_t mask = source.my_mask;
    if( my_mask == mask ) { // optimized version
        reserve( source.my_size, my_allocator ); // 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 ) ) {
                node* node_ptr = create_node(my_allocator, n->value().first, n->value().second);
                add_to_bucket( dst, node_ptr);
                ++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(), 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, tbb::interface5::internal::rehash_req, and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::value().

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_move_assign(), 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 1603 of file concurrent_hash_map.h.

                                                                                                    {
    reserve( reserve_size, my_allocator ); // 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* node_ptr = create_node(my_allocator, (*first).first, (*first).second);
        add_to_bucket( b, node_ptr );
        ++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 1338 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 1203 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->storage();
        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::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, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::search_bucket(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::storage().

Here is the call graph for this function:

internal_move_assign() [1/2]

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

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_move_assign ( concurrent_hash_map< Key, T, HashCompare, Allocator > &&  other, tbb::internal::traits_true_type    )

inlineprotected

Definition at line 1185 of file concurrent_hash_map.h.

                                                                                        {
        tbb::internal::allocator_move_assignment(my_allocator, other.my_allocator, tbb::internal::traits_true_type());
        internal_move(std::move(other));
    }

References tbb::internal::allocator_move_assignment(), tbb::interface5::internal::hash_map_base::internal_move(), tbb::move(), and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_allocator.

Here is the call graph for this function:

internal_move_assign() [2/2]

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

void tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_move_assign ( concurrent_hash_map< Key, T, HashCompare, Allocator > &&  other, tbb::internal::traits_false_type    )

inlineprotected

Definition at line 1190 of file concurrent_hash_map.h.

                                                                                         {
        if (this->my_allocator == other.my_allocator) {
            internal_move(std::move(other));
        } else {
            //do per element move
            internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()), other.size());
        }
    }

References tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_copy(), tbb::interface5::internal::hash_map_base::internal_move(), and tbb::move().

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 1258 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, my_allocator );
    }
    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 1000 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 931 of file concurrent_hash_map.h.

                                                                       {
        if( this!=&table ) {
            typedef typename node_allocator_traits::propagate_on_container_copy_assignment pocca_type;
            clear();
            tbb::internal::allocator_copy_assignment(my_allocator, table.my_allocator, pocca_type());
            internal_copy(table);
        }
        return *this;
    }

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

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

                                                                  {
        if(this != &table) {
            typedef typename node_allocator_traits::propagate_on_container_move_assignment pocma_type;
            internal_move_assign(std::move(table), pocma_type());
        }
        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 954 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 976 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 979 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 1434 of file concurrent_hash_map.h.

                                                                  {
    reserve( sz, my_allocator ); // 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)->value().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)->value().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, tbb::internal::first(), 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, tbb::internal::runtime_warning(), and value.

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 723 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)->value().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, tbb::internal::first(), 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, p, and value.

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

                                                                {
        node *n = static_cast<node*>( b->node_list );
        while( is_valid(n) && !my_hash_compare.equal(key, n->value().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(), key, tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::my_hash_compare, tbb::interface5::internal::hash_map_base::bucket::node_list, tbb::interface5::internal::rehash_req, and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::node::value().

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

{ return my_size; }

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

Referenced by 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 1423 of file concurrent_hash_map.h.

                                                                                                   {
    typedef typename node_allocator_traits::propagate_on_container_swap pocs_type;
    if (this != &table && (pocs_type::value || my_allocator == table.my_allocator)) {
        using std::swap;
        tbb::internal::allocator_swap(this->my_allocator, table.my_allocator, pocs_type());
        swap(this->my_hash_compare, table.my_hash_compare);
        internal_swap(table);
    }
}

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

Referenced by 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 1146 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 1147 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 609 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 587 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 590 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 1149 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 1150 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 1151 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 613 of file concurrent_hash_map.h.

Referenced by tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::concurrent_hash_map(), 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(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::internal_move_assign(), tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::operator=(), 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 614 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