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

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 value_type & | 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...

## Public Attributes

const typedef value_type * | const_pointer
const typedef value_type & | const_reference

## 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 const size_type | embedded_block = 1
| Count of segments in the first block. More...
static const size_type | embedded_buckets = 1<<embedded_block
| Count of segments in the first block. More...
static const size_type | first_block = 8
| Count of segments in the first block. More...
static const size_type | 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_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.

## 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()` | ) |

inline explicit

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()`
| ) |  |

inline explicit

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
| ) |  |

inline static protected

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 * |
| ) |  |

inline static protected

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
| ) |  |

inline static protected

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
| ) |  |

inline static protected

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 | ) |

inline protected

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 * |
| ) |  |

inline static protected

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 | ( | 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() [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 | ( | 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:

## 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 | ( | 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:

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

## erase() [2/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() [3/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:

## 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 | ( | 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:

## find() [2/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:

## 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
| ) |  |

inline protected

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
| ) |  |

inline protected

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 | ( | 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() [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 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() [3/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() [4/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() [5/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() [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,
|  | 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() [7/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() [8/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() [9/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() );
}

## insert() [10/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:

## 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

inline protected

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_false_type |
| ) |  |

inline protected

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:

## 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_true_type |
| ) |  |

inline protected

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:

## 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= | ( | 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=() [2/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=() [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
| ) |  |

inline protected

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

inline protected

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 | ( | accessor_not_used const & |  | ) |

friend

Definition at line 1151 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 | ( | const_accessor const & |  | ) |

friend

Definition at line 1150 of file concurrent_hash_map.h.

{ return false;}

## Member Data Documentation

## const_pointer

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

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

Definition at line 599 of file concurrent_hash_map.h.

## const_reference

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

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

Definition at line 601 of file concurrent_hash_map.h.

## 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

tbb::interface5::internal::hash_map_base::delete_segment
void delete_segment(segment_index_t s, const Allocator &allocator)
Definition: concurrent_hash_map.h:218
tbb::interface5::internal::hash_map_base::my_size
atomic< size_type > my_size
Size of container in stored items.
Definition: concurrent_hash_map.h:118
tbb::interface5::internal::hash_map_base::my_table
segments_table_t my_table
Segment pointers table. Also prevents false sharing between my_mask and my_size.
Definition: concurrent_hash_map.h:116
tbb::interface5::concurrent_hash_map::lookup
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.
Definition: concurrent_hash_map.h:1258
tbb::internal::allocator_traits::allocate
static pointer allocate(Alloc &a, size_type n)
Definition: _allocator_traits.h:102
tbb::interface5::internal::hash_map_base::bucket::scoped_t
mutex_t::scoped_lock scoped_t
Scoped lock type for mutex.
Definition: concurrent_hash_map.h:97
tbb::internal::__TBB_load_with_acquire
T __TBB_load_with_acquire(const volatile T &location)
Definition: tbb_machine.h:712
tbb::interface5::internal::hash_map_base::internal_swap
void internal_swap(hash_map_base &table)
Swap hash_map_bases.
Definition: concurrent_hash_map.h:309
tbb::interface5::internal::hash_map_base::mark_rehashed_levels
void mark_rehashed_levels(hashcode_t h)
Definition: concurrent_hash_map.h:243
tbb::interface5::concurrent_hash_map::clear
void clear()
Clear table.
Definition: concurrent_hash_map.h:1505
tbb::interface5::concurrent_hash_map::do_not_allocate_node
static node * do_not_allocate_node(node_allocator_type &, const Key &, const T *)
Definition: concurrent_hash_map.h:686
tbb::interface5::internal::hash_map_base::check_mask_race
bool check_mask_race(const hashcode_t h, hashcode_t &m) const
Check for mask race.
Definition: concurrent_hash_map.h:254
tbb::interface5::concurrent_hash_map::allocate_node_copy_construct
static node * allocate_node_copy_construct(node_allocator_type &allocator, const Key &key, const T *t)
Definition: concurrent_hash_map.h:663
tbb::internal::allocator_copy_assignment
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
Definition: _allocator_traits.h:49
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::interface5::internal::hash_map_base::segment_ptr_t
bucket * segment_ptr_t
Segment pointer.
Definition: concurrent_hash_map.h:110
tbb::interface5::internal::hash_map_base::my_embedded_segment
bucket my_embedded_segment[embedded_buckets]
Zero segment.
Definition: concurrent_hash_map.h:120
tbb::internal::allocator_traits::destroy
static void destroy(Alloc &, T *p)
Definition: _allocator_traits.h:133
tbb::internal::itt_load_word_with_acquire
T itt_load_word_with_acquire(const tbb::atomic< T > &src)
Definition: tbb_profiling.h:168
tbb::internal::allocator_move_assignment
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
Definition: _allocator_traits.h:59
tbb::interface5::concurrent_hash_map::iterator
internal::hash_map_iterator< concurrent_hash_map, value_type > iterator
Definition: concurrent_hash_map.h:602
tbb::internal::atomic_backoff
Class that implements exponential backoff.
Definition: tbb_machine.h:348
tbb::interface5::concurrent_hash_map::my_hash_compare
HashCompare my_hash_compare
Definition: concurrent_hash_map.h:614
tbb::interface5::internal::hash_map_base::insert_new_node
segment_index_t insert_new_node(bucket *b, node_base *n, hashcode_t mask)
Insert a node and check for load factor.
Definition: concurrent_hash_map.h:285
tbb::interface5::concurrent_hash_map::rehash
void rehash(size_type n=0)
Rehashes and optionally resizes the whole table.
Definition: concurrent_hash_map.h:1434
tbb::interface5::concurrent_hash_map::search_bucket
node * search_bucket(const key_type &key, bucket *b) const
Definition: concurrent_hash_map.h:691
tbb::interface5::concurrent_hash_map::create_node
static node * create_node(node_allocator_type &allocator, Args &&... args)
Definition: concurrent_hash_map.h:645
tbb::interface5::internal::hash_map_base::internal_move
void internal_move(hash_map_base &&other)
Definition: concurrent_hash_map.h:320
tbb::internal::allocator_swap
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
Definition: _allocator_traits.h:69
tbb::interface5::concurrent_hash_map::exclude
bool exclude(const_accessor &item_accessor)
delete item by accessor
Definition: concurrent_hash_map.h:1356
tbb::interface5::internal::empty_rehashed
static hash_map_node_base *const empty_rehashed
Rehashed empty bucket flag.
Definition: concurrent_hash_map.h:80
tbb::internal::runtime_warning
void __TBB_EXPORTED_FUNC runtime_warning(const char *format,...)
Report a runtime warning.
Definition: tbb_assert_impl.h:85
tbb::interface5::internal::hash_map_base::get_bucket
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.
Definition: concurrent_hash_map.h:234
tbb::interface5::concurrent_hash_map::swap
void swap(concurrent_hash_map &table)
swap two instances. Iterators are invalidated
Definition: concurrent_hash_map.h:1423
tbb::internal::bool_constant
Definition: tbb_stddef.h:486
tbb::internal::allocator_traits::propagate_on_container_copy_assignment
tbb::internal::false_type propagate_on_container_copy_assignment
Definition: _allocator_traits.h:87
tbb::interface5::internal::hash_map_base::enable_segment
void enable_segment(segment_index_t k, const Allocator &allocator, bool is_initial=false)
Enable segment.
Definition: concurrent_hash_map.h:190
tbb::interface5::internal::hash_map_base::bucket::node_list
node_base * node_list
Definition: concurrent_hash_map.h:99
tbb::interface5::internal::hash_map_base::reserve
void reserve(size_type buckets, const Allocator &allocator)
Prepare enough segments for number of buckets.
Definition: concurrent_hash_map.h:302
tbb::interface5::concurrent_hash_map::delete_node
void delete_node(node_base *n)
Definition: concurrent_hash_map.h:623
tbb::interface5::concurrent_hash_map::allocate_node_move_construct
static node * allocate_node_move_construct(node_allocator_type &allocator, const Key &key, const T *t)
Definition: concurrent_hash_map.h:668
tbb::interface5::concurrent_hash_map::end
iterator end()
Definition: concurrent_hash_map.h:987
tbb::interface5::internal::hash_map_base::my_mask
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
Definition: concurrent_hash_map.h:114
tbb::interface5::internal::hash_map_base::embedded_buckets
static const size_type embedded_buckets
Count of segments in the first block.
Definition: concurrent_hash_map.h:104
tbb::interface5::internal::hash_map_base::segment_size
static size_type segment_size(segment_index_t k)
Definition: concurrent_hash_map.h:154
tbb::internal::allocator_traits::construct
static void construct(Alloc &, PT *p)
Definition: _allocator_traits.h:111
tbb::interface5::concurrent_hash_map::internal_copy
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.
Definition: concurrent_hash_map.h:1577
tbb::interface5::concurrent_hash_map::accessor_location
friend const_accessor * accessor_location(accessor_not_used const &)
Definition: concurrent_hash_map.h:1146
tbb::interface5::internal::hash_map_base::segment_index_of
static segment_index_t segment_index_of(size_type index)
Definition: concurrent_hash_map.h:144
tbb::interface5::concurrent_hash_map::const_iterator
internal::hash_map_iterator< concurrent_hash_map, const value_type > const_iterator
Definition: concurrent_hash_map.h:603
tbb::internal::allocator_traits::propagate_on_container_move_assignment
tbb::internal::false_type propagate_on_container_move_assignment
Definition: _allocator_traits.h:86
tbb::interface5::concurrent_hash_map::internal_equal_range
std::pair< I, I > internal_equal_range(const Key &key, I end) const
Returns an iterator for an item defined by the key, or for the next item after it (if upper==true)
Definition: concurrent_hash_map.h:1338
tbb::interface5::internal::hash_map_base::node_base
hash_map_node_base node_base
Node base type.
Definition: concurrent_hash_map.h:91
tbb::interface5::concurrent_hash_map::my_allocator
node_allocator_type my_allocator
Definition: concurrent_hash_map.h:613
int
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void ITT_FORMAT p const __itt_domain __itt_id __itt_string_handle const wchar_t size_t ITT_FORMAT lu const __itt_domain __itt_id __itt_relation __itt_id ITT_FORMAT p const wchar_t int ITT_FORMAT __itt_group_mark d int
Definition: ittnotify_static.h:217
tbb::move
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
tbb::internal::allocator_traits::select_on_container_copy_construction
static Alloc select_on_container_copy_construction(const Alloc &a)
Definition: _allocator_traits.h:138
tbb::interface5::concurrent_hash_map::generic_emplace
bool generic_emplace(Accessor &&result, Args &&... args)
Definition: concurrent_hash_map.h:1162
tbb::internal::allocator_traits::deallocate
static void deallocate(Alloc &a, pointer p, size_type n)
Definition: _allocator_traits.h:106
tbb::interface5::concurrent_hash_map::generic_move_insert
bool generic_move_insert(Accessor &&result, value_type &&value)
Definition: concurrent_hash_map.h:1155
key
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
Definition: ittnotify_static.h:198
tbb::interface5::internal::rehash_req
static hash_map_node_base *const rehash_req
Incompleteness flag value.
Definition: concurrent_hash_map.h:78
tbb::internal::__TBB_store_with_release
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:716
lock
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void * lock
Definition: ittnotify_static.h:121
__TBB_Yield
#define __TBB_Yield()
Definition: ibm_aix51.h:44
__TBB_USE_OPTIONAL_RTTI
#define __TBB_USE_OPTIONAL_RTTI
Definition: tbb_config.h:125
tbb::interface5::concurrent_hash_map::size_type
hash_map_base::size_type size_type
Definition: concurrent_hash_map.h:596
tbb::interface5::concurrent_hash_map::const_range_type
internal::hash_map_range< const_iterator > const_range_type
Definition: concurrent_hash_map.h:605
tbb::internal::allocator_traits::propagate_on_container_swap
tbb::internal::false_type propagate_on_container_swap
Definition: _allocator_traits.h:88
tbb::internal::first
auto first(Container &c) -> decltype(begin(c))
Definition: _range_iterator.h:34
tbb::interface5::internal::hash_map_base::segment_index_t
size_t segment_index_t
Segment index type.
Definition: concurrent_hash_map.h:89
tbb::interface5::internal::hash_map_base::hashcode_t
size_t hashcode_t
Type of a hash code.
Definition: concurrent_hash_map.h:87
tbb::interface5::internal::hash_map_base::is_valid
static bool is_valid(void *ptr)
Definition: concurrent_hash_map.h:159
s
void const char const char int ITT_FORMAT __itt_group_sync s
Definition: ittnotify_static.h:91
tbb::interface5::internal::hash_map_base::add_to_bucket
static void add_to_bucket(bucket *b, node_base *n)
Add node.
Definition: concurrent_hash_map.h:173
__TBB_Log2
intptr_t __TBB_Log2(uintptr_t x)
Definition: tbb_machine.h:863
tbb::interface5::concurrent_hash_map::insert
bool insert(const_accessor &result, const Key &key)
Insert item (if not already present) and acquire a read lock on the item.
Definition: concurrent_hash_map.h:1036
tbb::interface5::concurrent_hash_map::internal_move_assign
void internal_move_assign(concurrent_hash_map &&other, tbb::internal::traits_true_type)
Definition: concurrent_hash_map.h:1185
tbb::interface5::internal::hash_map_base::pointers_per_table
static const size_type pointers_per_table
Size of a pointer / table size.
Definition: concurrent_hash_map.h:108
value
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
Definition: ittnotify_static.h:192
tbb::interface5::concurrent_hash_map::is_write_access_needed
friend bool is_write_access_needed(accessor const &)
Definition: concurrent_hash_map.h:1149
tbb::internal::last
auto last(Container &c) -> decltype(begin(c))
Definition: _range_iterator.h:40
tbb::interface5::concurrent_hash_map::range_type
internal::hash_map_range< iterator > range_type
Definition: concurrent_hash_map.h:604
p
void const char const char int ITT_FORMAT __itt_group_sync p
Definition: ittnotify_static.h:91
tbb::swap
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
Definition: concurrent_hash_map.h:1638
mask
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int mask
Definition: ittnotify_static.h:109
tbb::interface5::concurrent_hash_map::allocate_node_default_construct
static node * allocate_node_default_construct(node_allocator_type &allocator, const Key &key, const T *)
Definition: concurrent_hash_map.h:673
h
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function h
Definition: ittnotify_static.h:159

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.