Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator > Class Template Reference

Unordered map from Key to T. More...

#include <concurrent_hash_map.h>

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

Classes

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

Public Types

typedef Key key_type
 
typedef T mapped_type
 
typedef std::pair< const Key, T > value_type
 
typedef hash_map_base::size_type size_type
 
typedef ptrdiff_t difference_type
 
typedef value_typepointer
 
typedef const value_typeconst_pointer
 
typedef value_typereference
 
typedef const value_typeconst_reference
 
typedef internal::hash_map_iterator< concurrent_hash_map, value_typeiterator
 
typedef internal::hash_map_iterator< concurrent_hash_map, const value_typeconst_iterator
 
typedef internal::hash_map_range< iteratorrange_type
 
typedef internal::hash_map_range< const_iteratorconst_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_mapoperator= (const concurrent_hash_map &table)
 Assignment. More...
 
concurrent_hash_mapoperator= (concurrent_hash_map &&table)
 Move Assignment. More...
 
concurrent_hash_mapoperator= (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, iteratorequal_range (const Key &key)
 
std::pair< const_iterator, const_iteratorequal_range (const Key &key) const
 
size_type size () const
 Number of items in table. More...
 
bool empty () const
 True if size()==0. More...
 
size_type max_size () const
 Upper bound on size. More...
 
size_type bucket_count () const
 Returns the current number of buckets. More...
 
allocator_type get_allocator () const
 return allocator object More...
 
void swap (concurrent_hash_map &table)
 swap two instances. Iterators are invalidated More...
 
size_type count (const Key &key) const
 Return count of items (0 or 1) More...
 
bool find (const_accessor &result, const Key &key) const
 Find item and acquire a read lock on the item. More...
 
bool find (accessor &result, const Key &key)
 Find item and acquire a write lock on the item. More...
 
bool insert (const_accessor &result, const Key &key)
 Insert item (if not already present) and acquire a read lock on the item. More...
 
bool insert (accessor &result, const Key &key)
 Insert item (if not already present) and acquire a write lock on the item. More...
 
bool insert (const_accessor &result, const value_type &value)
 Insert item by copying if there is no such key present already and acquire a read lock on the item. More...
 
bool insert (accessor &result, const value_type &value)
 Insert item by copying if there is no such key present already and acquire a write lock on the item. More...
 
bool insert (const value_type &value)
 Insert item by copying if there is no such key present already. More...
 
bool insert (const_accessor &result, value_type &&value)
 Insert item by copying if there is no such key present already and acquire a read lock on the item. More...
 
bool insert (accessor &result, value_type &&value)
 Insert item by copying if there is no such key present already and acquire a write lock on the item. More...
 
bool insert (value_type &&value)
 Insert item by copying if there is no such key present already. More...
 
template<typename... Args>
bool emplace (const_accessor &result, Args &&... args)
 Insert item by copying if there is no such key present already and acquire a read lock on the item. More...
 
template<typename... Args>
bool emplace (accessor &result, Args &&... args)
 Insert item by copying if there is no such key present already and acquire a write lock on the item. More...
 
template<typename... Args>
bool emplace (Args &&... args)
 Insert item by copying if there is no such key present already. More...
 
template<typename I >
void insert (I first, I last)
 Insert range [first, last) More...
 
void insert (std::initializer_list< value_type > il)
 Insert initializer list. More...
 
bool erase (const Key &key)
 Erase item. More...
 
bool erase (const_accessor &item_accessor)
 Erase item by const_accessor. More...
 
bool erase (accessor &item_accessor)
 Erase item by accessor. More...
 

Protected Types

typedef tbb::internal::allocator_rebind< Allocator, node >::type node_allocator_type
 
typedef tbb::internal::allocator_traits< node_allocator_typenode_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 bucketsegment_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)
 
nodesearch_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)
 
bucketget_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 nodecreate_node (node_allocator_type &allocator, Args &&... args)
 
static nodeallocate_node_copy_construct (node_allocator_type &allocator, const Key &key, const T *t)
 
static nodeallocate_node_move_construct (node_allocator_type &allocator, const Key &key, const T *t)
 
static nodeallocate_node_default_construct (node_allocator_type &allocator, const Key &key, const T *)
 
static nodedo_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_tmy_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_typemy_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_accessoraccessor_location (accessor_not_used const &)
 
const_accessoraccessor_location (const_accessor &a)
 
bool is_write_access_needed (accessor const &)
 
bool is_write_access_needed (const_accessor const &)
 
bool is_write_access_needed (accessor_not_used const &)
 

Additional Inherited Members

- Static Protected Attributes inherited from tbb::interface5::internal::hash_map_base
static size_type const embedded_block = 1
 Count of segments in the first block. More...
 
static size_type const embedded_buckets = 1<<embedded_block
 Count of segments in the first block. More...
 
static size_type const first_block = 8
 Count of segments in the first block. More...
 
static size_type const pointers_per_table = sizeof(segment_index_t) * 8
 Size of a pointer / table size. More...
 

Detailed Description

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

Unordered map from Key to T.

concurrent_hash_map is associative container with concurrent access.

Compatibility
The class meets all Container Requirements from C++ Standard (See ISO/IEC 14882:2003(E), clause 23.1).
Exception Safety
  • Hash function is not permitted to throw an exception. User-defined types Key and T are forbidden from throwing an exception in destructors.
  • If exception happens during insert() operations, it has no effect (unless exception raised by HashCompare::hash() function during grow_segment).
  • If exception happens during operator=() operation, the container can have a part of source items, and methods size() and empty() can return wrong results.
Changes since TBB 2.1
  • Replaced internal algorithm and data structure. Patent is pending.
  • Added buckets number argument for constructor
Changes since TBB 2.0

Definition at line 55 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 594 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 591 of file concurrent_hash_map.h.

◆ const_pointer

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

Definition at line 587 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 593 of file concurrent_hash_map.h.

◆ const_reference

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

Definition at line 589 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 585 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 590 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 581 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 582 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 600 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 598 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 586 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 592 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 588 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 584 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 583 of file concurrent_hash_map.h.

Constructor & Destructor Documentation

◆ concurrent_hash_map() [1/12]

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

Construct empty table.

Definition at line 816 of file concurrent_hash_map.h.

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

◆ concurrent_hash_map() [2/12]

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

Definition at line 820 of file concurrent_hash_map.h.

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

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

826  : internal::hash_map_base(), my_allocator(a)
827  {
828  reserve( n, my_allocator );
829  }
void reserve(size_type buckets, const Allocator &allocator)
Prepare enough segments for number of buckets.

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

832  : internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
833  {
834  reserve( n, my_allocator );
835  }
void reserve(size_type buckets, const Allocator &allocator)
Prepare enough segments for number of buckets.

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

839  : internal::hash_map_base(),
841  {
842  call_clear_on_leave scope_guard(this);
843  internal_copy(table);
844  scope_guard.dismiss();
845  }
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.
static Alloc select_on_container_copy_construction(const Alloc &a)

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

848  : internal::hash_map_base(), my_allocator(a)
849  {
850  call_clear_on_leave scope_guard(this);
851  internal_copy(table);
852  scope_guard.dismiss();
853  }
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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

858  : internal::hash_map_base(), my_allocator(std::move(table.get_allocator()))
859  {
860  internal_move(std::move(table));
861  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305

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

865  : internal::hash_map_base(), my_allocator(a)
866  {
867  if (a == table.get_allocator()){
868  internal_move(std::move(table));
869  }else{
870  call_clear_on_leave scope_guard(this);
871  internal_copy(std::make_move_iterator(table.begin()), std::make_move_iterator(table.end()), table.size());
872  scope_guard.dismiss();
873  }
874  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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 ( first,
last,
const allocator_type a = allocator_type() 
)
inline

Construction with copying iteration range and given allocator instance.

Definition at line 879 of file concurrent_hash_map.h.

880  : internal::hash_map_base(), my_allocator(a)
881  {
882  call_clear_on_leave scope_guard(this);
883  internal_copy(first, last, std::distance(first, last));
884  scope_guard.dismiss();
885  }
auto first(Container &c) -> decltype(begin(c))
auto last(Container &c) -> decltype(begin(c))
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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 ( first,
last,
const HashCompare &  compare,
const allocator_type a = allocator_type() 
)
inline

Definition at line 888 of file concurrent_hash_map.h.

889  : internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
890  {
891  call_clear_on_leave scope_guard(this);
892  internal_copy(first, last, std::distance(first, last));
893  scope_guard.dismiss();
894  }
auto first(Container &c) -> decltype(begin(c))
auto last(Container &c) -> decltype(begin(c))
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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

899  : internal::hash_map_base(), my_allocator(a)
900  {
901  call_clear_on_leave scope_guard(this);
902  internal_copy(il.begin(), il.end(), il.size());
903  scope_guard.dismiss();
904  }
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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

907  : internal::hash_map_base(), my_allocator(a), my_hash_compare(compare)
908  {
909  call_clear_on_leave scope_guard(this);
910  internal_copy(il.begin(), il.end(), il.size());
911  scope_guard.dismiss();
912  }
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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

957 { clear(); }

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

Here is the call graph for this function:

Member Function Documentation

◆ allocate_node_copy_construct()

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

Definition at line 651 of file concurrent_hash_map.h.

651  {
652  return create_node(allocator, key, *t);
653  }
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_id __itt_string_handle * key
static node * create_node(node_allocator_type &allocator, Args &&... args)

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ allocate_node_default_construct()

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

Definition at line 661 of file concurrent_hash_map.h.

661  {
662 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT && __TBB_CPP11_TUPLE_PRESENT
663  // Emplace construct an empty T object inside the pair
664  return create_node(allocator, std::piecewise_construct,
665  std::forward_as_tuple(key), std::forward_as_tuple());
666 #else
667  T obj; // Use of temporary object in impossible, because create_node takes non-const reference
668  return create_node(allocator, key, tbb::internal::move(obj));
669 #endif
670  }
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_id __itt_string_handle * key
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
static node * create_node(node_allocator_type &allocator, Args &&... args)

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ allocate_node_move_construct()

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

Definition at line 656 of file concurrent_hash_map.h.

656  {
657  return create_node(allocator, key, std::move(*const_cast<T*>(t)));
658  }
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_id __itt_string_handle * key
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
static node * create_node(node_allocator_type &allocator, Args &&... args)

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

◆ 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

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

989 { return my_mask+1; }
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 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 1491 of file concurrent_hash_map.h.

1491  {
1492  hashcode_t m = my_mask;
1493  __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
1494 #if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1495 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1496  int current_size = int(my_size), buckets = int(m)+1, empty_buckets = 0, overpopulated_buckets = 0; // usage statistics
1497  static bool reported = false;
1498 #endif
1499  bucket *bp = 0;
1500  // check consistency
1501  for( segment_index_t b = 0; b <= m; b++ ) {
1502  if( b & (b-2) ) ++bp; // not the beginning of a segment
1503  else bp = get_bucket( b );
1504  node_base *n = bp->node_list;
1505  __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed || n == internal::rehash_req, "Broken internal structure" );
1506  __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during clear() execution" );
1507 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1508  if( n == internal::empty_rehashed ) empty_buckets++;
1509  else if( n == internal::rehash_req ) buckets--;
1510  else if( n->next ) overpopulated_buckets++;
1511 #endif
1512 #if __TBB_EXTRA_DEBUG
1513  for(; is_valid(n); n = n->next ) {
1514  hashcode_t h = my_hash_compare.hash( static_cast<node*>(n)->value().first );
1515  h &= m;
1516  __TBB_ASSERT( h == b || get_bucket(h)->node_list == internal::rehash_req, "hash() function changed for key in table or internal error" );
1517  }
1518 #endif
1519  }
1520 #if TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1521 #if __TBB_STATISTICS
1522  printf( "items=%d buckets: capacity=%d rehashed=%d empty=%d overpopulated=%d"
1523  " concurrent: resizes=%u rehashes=%u restarts=%u\n",
1524  current_size, int(m+1), buckets, empty_buckets, overpopulated_buckets,
1525  unsigned(my_info_resizes), unsigned(my_info_rehashes), unsigned(my_info_restarts) );
1526  my_info_resizes = 0; // concurrent ones
1527  my_info_restarts = 0; // race collisions
1528  my_info_rehashes = 0; // invocations of rehash_bucket
1529 #endif
1530  if( buckets > current_size) empty_buckets -= buckets - current_size;
1531  else overpopulated_buckets -= current_size - buckets; // TODO: load_factor?
1532  if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
1534  "Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
1536  typeid(*this).name(),
1537 #else
1538  "concurrent_hash_map",
1539 #endif
1540  current_size, empty_buckets, overpopulated_buckets );
1541  reported = true;
1542  }
1543 #endif
1544 #endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS || __TBB_STATISTICS
1545  my_size = 0;
1547  __TBB_ASSERT( s+1 == pointers_per_table || !my_table[s+1], "wrong mask or concurrent grow" );
1548  do {
1549  __TBB_ASSERT( is_valid( my_table[s] ), "wrong mask or concurrent grow" );
1550  segment_ptr_t buckets_ptr = my_table[s];
1551  size_type sz = segment_size( s ? s : 1 );
1552  for( segment_index_t i = 0; i < sz; i++ )
1553  for( node_base *n = buckets_ptr[i].node_list; is_valid(n); n = buckets_ptr[i].node_list ) {
1554  buckets_ptr[i].node_list = n->next;
1555  delete_node( n );
1556  }
1558  } while(s-- > 0);
1559  my_mask = embedded_buckets - 1;
1560 }
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
void __TBB_EXPORTED_FUNC runtime_warning(const char *format,...)
Report a runtime warning.
void const char const char int ITT_FORMAT __itt_group_sync s
static size_type const embedded_buckets
Count of segments in the first block.
static size_type const pointers_per_table
Size of a pointer / table size.
static hash_map_node_base *const empty_rehashed
Rehashed empty bucket flag.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
static segment_index_t segment_index_of(size_type index)
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_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
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
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
auto first(Container &c) -> decltype(begin(c))
#define __TBB_USE_OPTIONAL_RTTI
Definition: tbb_config.h:125
void delete_segment(segment_index_t s, const Allocator &allocator)
static hash_map_node_base *const rehash_req
Incompleteness flag value.
static size_type segment_size(segment_index_t k)
atomic< size_type > my_size
Size of container in stored items.
segments_table_t my_table
Segment pointers table. Also prevents false sharing between my_mask and my_size.
hash_map_node_base node_base
Node base type.
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.

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

1002  {
1003  return const_cast<concurrent_hash_map*>(this)->lookup(/*insert*/false, key, NULL, NULL, /*write=*/false, &do_not_allocate_node );
1004  }
static node * do_not_allocate_node(node_allocator_type &, const Key &, const T *)
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_id __itt_string_handle * key

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

Here is the call graph for this function:

◆ create_node()

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

Definition at line 633 of file concurrent_hash_map.h.

638  {
639  node* node_ptr = node_allocator_traits::allocate(allocator, 1);
640  node_scoped_guard guard(node_ptr, allocator);
641  node_allocator_traits::construct(allocator, node_ptr);
642 #if __TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
643  node_allocator_traits::construct(allocator, node_ptr->storage(), std::forward<Args>(args)...);
644 #else
645  node_allocator_traits::construct(allocator, node_ptr->storage(), tbb::internal::forward<Arg1>(arg1), tbb::internal::forward<Arg2>(arg2));
646 #endif
647  guard.dismiss();
648  return node_ptr;
649  }
static void construct(Alloc &, PT *p)
static pointer allocate(Alloc &a, size_type n)

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ delete_node()

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

Definition at line 611 of file concurrent_hash_map.h.

611  {
612  node_allocator_traits::destroy(my_allocator, static_cast<node*>(n)->storage());
613  node_allocator_traits::destroy(my_allocator, static_cast<node*>(n));
614  node_allocator_traits::deallocate(my_allocator, static_cast<node*>(n), 1);
615  }
static void deallocate(Alloc &a, pointer p, size_type n)
static void destroy(Alloc &, T *p)

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

Here is the call graph for this function:

◆ do_not_allocate_node()

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

Definition at line 672 of file concurrent_hash_map.h.

672  {
673  __TBB_ASSERT(false,"this dummy function should not be called");
674  return NULL;
675  }
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165

References __TBB_ASSERT.

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

Here is the caller graph for this function:

◆ emplace() [1/3]

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

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

Returns true if item is new.

Definition at line 1077 of file concurrent_hash_map.h.

1077  {
1078  return generic_emplace(result, std::forward<Args>(args)...);
1079  }
bool generic_emplace(Accessor &&result, Args &&... args)

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

Here is the call graph for this function:

◆ emplace() [2/3]

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

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

Returns true if item is new.

Definition at line 1084 of file concurrent_hash_map.h.

1084  {
1085  return generic_emplace(result, std::forward<Args>(args)...);
1086  }
bool generic_emplace(Accessor &&result, Args &&... args)

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

Here is the call graph for this function:

◆ emplace() [3/3]

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

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

Returns true if item is inserted.

Definition at line 1091 of file concurrent_hash_map.h.

1091  {
1092  return generic_emplace(accessor_not_used(), std::forward<Args>(args)...);
1093  }
bool generic_emplace(Accessor &&result, 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 983 of file concurrent_hash_map.h.

983 { return my_size == 0; }
atomic< size_type > my_size
Size of container in stored items.

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

973 { return iterator( *this, 0, 0, 0 ); }
internal::hash_map_iterator< concurrent_hash_map, value_type > iterator

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

975 { return const_iterator( *this, 0, 0, 0 ); }
internal::hash_map_iterator< concurrent_hash_map, const value_type > const_iterator

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

976 { return internal_equal_range( key, end() ); }
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_id __itt_string_handle * key
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)

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

977 { return internal_equal_range( key, end() ); }
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_id __itt_string_handle * key
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)

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

Here is the call graph for this function:

◆ erase() [1/3]

template<typename Key , typename T , typename HashCompare , typename A >
bool tbb::interface5::concurrent_hash_map< Key, T, HashCompare, A >::erase ( const Key &  key)

Erase item.

Return true if item was erased by particularly this call.

Definition at line 1372 of file concurrent_hash_map.h.

1372  {
1373  node_base *n;
1374  hashcode_t const h = my_hash_compare.hash( key );
1376 restart:
1377  {//lock scope
1378  // get bucket
1379  bucket_accessor b( this, h & m );
1380  search:
1381  node_base **p = &b()->node_list;
1382  n = *p;
1383  while( is_valid(n) && !my_hash_compare.equal(key, static_cast<node*>(n)->value().first ) ) {
1384  p = &n->next;
1385  n = *p;
1386  }
1387  if( !n ) { // not found, but mask could be changed
1388  if( check_mask_race( h, m ) )
1389  goto restart;
1390  return false;
1391  }
1392  else if( !b.is_writer() && !b.upgrade_to_writer() ) {
1393  if( check_mask_race( h, m ) ) // contended upgrade, check mask
1394  goto restart;
1395  goto search;
1396  }
1397  *p = n->next;
1398  my_size--;
1399  }
1400  {
1401  typename node::scoped_t item_locker( n->mutex, /*write=*/true );
1402  }
1403  // note: there should be no threads pretending to acquire this mutex again, do not try to upgrade const_accessor!
1404  delete_node( n ); // Only one thread can delete it due to write lock on the bucket
1405  return true;
1406 }
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_id __itt_string_handle * key
bool check_mask_race(const hashcode_t h, hashcode_t &m) const
Check for mask race.
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
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
void const char const char int ITT_FORMAT __itt_group_sync p
T itt_load_word_with_acquire(const tbb::atomic< T > &src)
atomic< size_type > my_size
Size of container in stored items.
hash_map_node_base node_base
Node base type.

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

Here is the call graph for this function:

◆ erase() [2/3]

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

Erase item by const_accessor.

Return true if item was erased by particularly this call.

Definition at line 1117 of file concurrent_hash_map.h.

1117  {
1118  return exclude( item_accessor );
1119  }
bool exclude(const_accessor &item_accessor)
delete item by accessor

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

Here is the call graph for this function:

◆ erase() [3/3]

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

Erase item by accessor.

Return true if item was erased by particularly this call.

Definition at line 1123 of file concurrent_hash_map.h.

1123  {
1124  return exclude( item_accessor );
1125  }
bool exclude(const_accessor &item_accessor)
delete item by 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 1342 of file concurrent_hash_map.h.

1342  {
1343  __TBB_ASSERT( item_accessor.my_node, NULL );
1344  node_base *const n = item_accessor.my_node;
1345  hashcode_t const h = item_accessor.my_hash;
1347  do {
1348  // get bucket
1349  bucket_accessor b( this, h & m, /*writer=*/true );
1350  node_base **p = &b()->node_list;
1351  while( *p && *p != n )
1352  p = &(*p)->next;
1353  if( !*p ) { // someone else was first
1354  if( check_mask_race( h, m ) )
1355  continue;
1356  item_accessor.release();
1357  return false;
1358  }
1359  __TBB_ASSERT( *p == n, NULL );
1360  *p = n->next; // remove from container
1361  my_size--;
1362  break;
1363  } while(true);
1364  if( !item_accessor.is_writer() ) // need to get exclusive lock
1365  item_accessor.upgrade_to_writer(); // return value means nothing here
1366  item_accessor.release();
1367  delete_node( n ); // Only one thread can delete it
1368  return true;
1369 }
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
bool check_mask_race(const hashcode_t h, hashcode_t &m) const
Check for mask race.
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
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
void const char const char int ITT_FORMAT __itt_group_sync p
T itt_load_word_with_acquire(const tbb::atomic< T > &src)
atomic< size_type > my_size
Size of container in stored items.
hash_map_node_base node_base
Node base type.

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ find() [1/2]

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

Find item and acquire a read lock on the item.

Return true if item is found, false otherwise.

Definition at line 1008 of file concurrent_hash_map.h.

1008  {
1009  result.release();
1010  return const_cast<concurrent_hash_map*>(this)->lookup(/*insert*/false, key, NULL, &result, /*write=*/false, &do_not_allocate_node );
1011  }
static node * do_not_allocate_node(node_allocator_type &, const Key &, const T *)
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_id __itt_string_handle * key

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

Here is the call graph for this function:

◆ find() [2/2]

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

Find item and acquire a write lock on the item.

Return true if item is found, false otherwise.

Definition at line 1015 of file concurrent_hash_map.h.

1015  {
1016  result.release();
1017  return lookup(/*insert*/false, key, NULL, &result, /*write=*/true, &do_not_allocate_node );
1018  }
static node * do_not_allocate_node(node_allocator_type &, const Key &, const T *)
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_id __itt_string_handle * key
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.

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

Here is the call graph for this function:

◆ generic_emplace()

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

Definition at line 1148 of file concurrent_hash_map.h.

1148  {
1149  result.release();
1150  node * node_ptr = create_node(my_allocator, std::forward<Args>(args)...);
1151  return lookup(/*insert*/true, node_ptr->value().first, NULL, accessor_location(result), is_write_access_needed(result), &do_not_allocate_node, node_ptr );
1152  }
friend const_accessor * accessor_location(accessor_not_used const &)
static node * do_not_allocate_node(node_allocator_type &, const Key &, const T *)
friend bool is_write_access_needed(accessor const &)
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.
static node * create_node(node_allocator_type &allocator, Args &&... args)

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ generic_move_insert()

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

Definition at line 1141 of file concurrent_hash_map.h.

1141  {
1142  result.release();
1143  return lookup(/*insert*/true, value.first, &value.second, accessor_location(result), is_write_access_needed(result), &allocate_node_move_construct );
1144  }
friend const_accessor * accessor_location(accessor_not_used const &)
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
friend bool is_write_access_needed(accessor const &)
static node * allocate_node_move_construct(node_allocator_type &allocator, const Key &key, const T *t)
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.

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

992 { return this->my_allocator; }

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

◆ insert() [1/10]

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

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

Returns true if item is new.

Definition at line 1022 of file concurrent_hash_map.h.

1022  {
1023  result.release();
1024  return lookup(/*insert*/true, key, NULL, &result, /*write=*/false, &allocate_node_default_construct );
1025  }
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_id __itt_string_handle * key
static node * allocate_node_default_construct(node_allocator_type &allocator, const Key &key, const T *)
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.

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ insert() [2/10]

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

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

Returns true if item is new.

Definition at line 1029 of file concurrent_hash_map.h.

1029  {
1030  result.release();
1031  return lookup(/*insert*/true, key, NULL, &result, /*write=*/true, &allocate_node_default_construct );
1032  }
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_id __itt_string_handle * key
static node * allocate_node_default_construct(node_allocator_type &allocator, const Key &key, const T *)
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.

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

Here is the call graph for this function:

◆ insert() [3/10]

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

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

Returns true if item is new.

Definition at line 1036 of file concurrent_hash_map.h.

1036  {
1037  result.release();
1038  return lookup(/*insert*/true, value.first, &value.second, &result, /*write=*/false, &allocate_node_copy_construct );
1039  }
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
static node * allocate_node_copy_construct(node_allocator_type &allocator, const Key &key, const T *t)
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.

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

Here is the call graph for this function:

◆ insert() [4/10]

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

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

Returns true if item is new.

Definition at line 1043 of file concurrent_hash_map.h.

1043  {
1044  result.release();
1045  return lookup(/*insert*/true, value.first, &value.second, &result, /*write=*/true, &allocate_node_copy_construct );
1046  }
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
static node * allocate_node_copy_construct(node_allocator_type &allocator, const Key &key, const T *t)
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.

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

Here is the call graph for this function:

◆ insert() [5/10]

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

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

Returns true if item is inserted.

Definition at line 1050 of file concurrent_hash_map.h.

1050  {
1051  return lookup(/*insert*/true, value.first, &value.second, NULL, /*write=*/false, &allocate_node_copy_construct );
1052  }
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
static node * allocate_node_copy_construct(node_allocator_type &allocator, const Key &key, const T *t)
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.

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

Here is the call graph for this function:

◆ insert() [6/10]

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

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

Returns true if item is new.

Definition at line 1057 of file concurrent_hash_map.h.

1057  {
1058  return generic_move_insert(result, std::move(value));
1059  }
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
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
bool generic_move_insert(Accessor &&result, value_type &&value)

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

Here is the call graph for this function:

◆ insert() [7/10]

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

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

Returns true if item is new.

Definition at line 1063 of file concurrent_hash_map.h.

1063  {
1064  return generic_move_insert(result, std::move(value));
1065  }
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
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
bool generic_move_insert(Accessor &&result, value_type &&value)

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

Here is the call graph for this function:

◆ insert() [8/10]

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

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

Returns true if item is inserted.

Definition at line 1069 of file concurrent_hash_map.h.

1069  {
1070  return generic_move_insert(accessor_not_used(), std::move(value));
1071  }
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
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
bool generic_move_insert(Accessor &&result, value_type &&value)

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

Here is the call graph for this function:

◆ insert() [9/10]

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

Insert range [first, last)

Definition at line 1099 of file concurrent_hash_map.h.

1099  {
1100  for ( ; first != last; ++first )
1101  insert( *first );
1102  }
auto first(Container &c) -> decltype(begin(c))
bool insert(const_accessor &result, const Key &key)
Insert item (if not already present) and acquire a read lock on the item.
auto last(Container &c) -> decltype(begin(c))

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

Here is the call graph for this function:

◆ insert() [10/10]

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

Insert initializer list.

Definition at line 1106 of file concurrent_hash_map.h.

1106  {
1107  insert( il.begin(), il.end() );
1108  }
bool insert(const_accessor &result, const Key &key)
Insert item (if not already present) and acquire a read lock on the item.

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

1563  {
1564  hashcode_t mask = source.my_mask;
1565  if( my_mask == mask ) { // optimized version
1566  reserve( source.my_size, my_allocator ); // TODO: load_factor?
1567  bucket *dst = 0, *src = 0;
1568  bool rehash_required = false;
1569  for( hashcode_t k = 0; k <= mask; k++ ) {
1570  if( k & (k-2) ) ++dst,src++; // not the beginning of a segment
1571  else { dst = get_bucket( k ); src = source.get_bucket( k ); }
1572  __TBB_ASSERT( dst->node_list != internal::rehash_req, "Invalid bucket in destination table");
1573  node *n = static_cast<node*>( src->node_list );
1574  if( n == internal::rehash_req ) { // source is not rehashed, items are in previous buckets
1575  rehash_required = true;
1576  dst->node_list = internal::rehash_req;
1577  } else for(; n; n = static_cast<node*>( n->next ) ) {
1578  node* node_ptr = create_node(my_allocator, n->value().first, n->value().second);
1579  add_to_bucket( dst, node_ptr);
1580  ++my_size; // TODO: replace by non-atomic op
1581  }
1582  }
1583  if( rehash_required ) rehash();
1584  } else internal_copy( source.begin(), source.end(), source.my_size );
1585 }
void reserve(size_type buckets, const Allocator &allocator)
Prepare enough segments for number of buckets.
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
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
static void add_to_bucket(bucket *b, node_base *n)
Add node.
void rehash(size_type n=0)
Rehashes and optionally resizes the whole table.
static node * create_node(node_allocator_type &allocator, Args &&... args)
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.
static hash_map_node_base *const rehash_req
Incompleteness flag value.
atomic< size_type > my_size
Size of container in stored items.
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.

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 ( first,
last,
size_type  reserve_size 
)
protected

Definition at line 1589 of file concurrent_hash_map.h.

1589  {
1590  reserve( reserve_size, my_allocator ); // TODO: load_factor?
1591  hashcode_t m = my_mask;
1592  for(; first != last; ++first) {
1593  hashcode_t h = my_hash_compare.hash( (*first).first );
1594  bucket *b = get_bucket( h & m );
1595  __TBB_ASSERT( b->node_list != internal::rehash_req, "Invalid bucket in destination table");
1596  node* node_ptr = create_node(my_allocator, (*first).first, (*first).second);
1597  add_to_bucket( b, node_ptr );
1598  ++my_size; // TODO: replace by non-atomic op
1599  }
1600 }
void reserve(size_type buckets, const Allocator &allocator)
Prepare enough segments for number of buckets.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
static void add_to_bucket(bucket *b, node_base *n)
Add node.
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
auto first(Container &c) -> decltype(begin(c))
static node * create_node(node_allocator_type &allocator, Args &&... args)
auto last(Container &c) -> decltype(begin(c))
static hash_map_node_base *const rehash_req
Incompleteness flag value.
atomic< size_type > my_size
Size of container in stored items.
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.

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

1324  {
1325  hashcode_t h = my_hash_compare.hash( key );
1326  hashcode_t m = my_mask;
1327  __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
1328  h &= m;
1329  bucket *b = get_bucket( h );
1330  while( b->node_list == internal::rehash_req ) {
1331  m = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
1332  b = get_bucket( h &= m );
1333  }
1334  node *n = search_bucket( key, b );
1335  if( !n )
1336  return std::make_pair(end_, end_);
1337  iterator lower(*this, h, b, n), upper(lower);
1338  return std::make_pair(lower, ++upper);
1339 }
intptr_t __TBB_Log2(uintptr_t x)
Definition: tbb_machine.h:860
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_id __itt_string_handle * key
internal::hash_map_iterator< concurrent_hash_map, value_type > iterator
node * search_bucket(const key_type &key, bucket *b) const
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
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
static hash_map_node_base *const rehash_req
Incompleteness flag value.
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ internal_fast_find()

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

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

Return pointer to item with given key, or NULL if no such item exists. Must not be called concurrently with erasure operations.

Definition at line 1189 of file concurrent_hash_map.h.

1189  {
1190  hashcode_t h = my_hash_compare.hash( key );
1192  node *n;
1193  restart:
1194  __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
1195  bucket *b = get_bucket( h & m );
1196  // TODO: actually, notification is unnecessary here, just hiding double-check
1197  if( itt_load_word_with_acquire(b->node_list) == internal::rehash_req )
1198  {
1200  if( lock.try_acquire( b->mutex, /*write=*/true ) ) {
1201  if( b->node_list == internal::rehash_req)
1202  const_cast<concurrent_hash_map*>(this)->rehash_bucket( b, h & m ); //recursive rehashing
1203  }
1204  else lock.acquire( b->mutex, /*write=*/false );
1205  __TBB_ASSERT(b->node_list!=internal::rehash_req,NULL);
1206  }
1207  n = search_bucket( key, b );
1208  if( n )
1209  return &n->item;
1210  else if( check_mask_race( h, m ) )
1211  goto restart;
1212  return 0;
1213  }
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_id __itt_string_handle * key
node * search_bucket(const key_type &key, bucket *b) const
mutex_t::scoped_lock scoped_t
Scoped lock type for mutex.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
bool check_mask_race(const hashcode_t h, hashcode_t &m) const
Check for mask race.
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
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
static hash_map_node_base *const rehash_req
Incompleteness flag value.
T itt_load_word_with_acquire(const tbb::atomic< T > &src)
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
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.

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, and tbb::interface5::concurrent_hash_map< Key, T, HashCompare, Allocator >::search_bucket().

Here is the call graph for this function:

◆ internal_move_assign() [1/2]

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

Definition at line 1171 of file concurrent_hash_map.h.

1171  {
1173  internal_move(std::move(other));
1174  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)

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

Here is the call graph for this function:

◆ internal_move_assign() [2/2]

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

Definition at line 1176 of file concurrent_hash_map.h.

1176  {
1177  if (this->my_allocator == other.my_allocator) {
1178  internal_move(std::move(other));
1179  } else {
1180  //do per element move
1181  internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()), other.size());
1182  }
1183  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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

Here is the call graph for this function:

◆ lookup()

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

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

Definition at line 1244 of file concurrent_hash_map.h.

1244  {
1245  __TBB_ASSERT( !result || !result->my_node, NULL );
1246  bool return_value;
1247  hashcode_t const h = my_hash_compare.hash( key );
1249  segment_index_t grow_segment = 0;
1250  node *n;
1251  restart:
1252  {//lock scope
1253  __TBB_ASSERT((m&(m+1))==0, "data structure is invalid");
1254  return_value = false;
1255  // get bucket
1256  bucket_accessor b( this, h & m );
1257 
1258  // find a node
1259  n = search_bucket( key, b() );
1260  if( op_insert ) {
1261  // [opt] insert a key
1262  if( !n ) {
1263  if( !tmp_n ) {
1264  tmp_n = allocate_node(my_allocator, key, t);
1265  }
1266  if( !b.is_writer() && !b.upgrade_to_writer() ) { // TODO: improved insertion
1267  // Rerun search_list, in case another thread inserted the item during the upgrade.
1268  n = search_bucket( key, b() );
1269  if( is_valid(n) ) { // unfortunately, it did
1270  b.downgrade_to_reader();
1271  goto exists;
1272  }
1273  }
1274  if( check_mask_race(h, m) )
1275  goto restart; // b.release() is done in ~b().
1276  // insert and set flag to grow the container
1277  grow_segment = insert_new_node( b(), n = tmp_n, m );
1278  tmp_n = 0;
1279  return_value = true;
1280  }
1281  } else { // find or count
1282  if( !n ) {
1283  if( check_mask_race( h, m ) )
1284  goto restart; // b.release() is done in ~b(). TODO: replace by continue
1285  return false;
1286  }
1287  return_value = true;
1288  }
1289  exists:
1290  if( !result ) goto check_growth;
1291  // TODO: the following seems as generic/regular operation
1292  // acquire the item
1293  if( !result->try_acquire( n->mutex, write ) ) {
1294  for( tbb::internal::atomic_backoff backoff(true);; ) {
1295  if( result->try_acquire( n->mutex, write ) ) break;
1296  if( !backoff.bounded_pause() ) {
1297  // the wait takes really long, restart the operation
1298  b.release();
1299  __TBB_ASSERT( !op_insert || !return_value, "Can't acquire new item in locked bucket?" );
1300  __TBB_Yield();
1302  goto restart;
1303  }
1304  }
1305  }
1306  }//lock scope
1307  result->my_node = n;
1308  result->my_hash = h;
1309 check_growth:
1310  // [opt] grow the container
1311  if( grow_segment ) {
1312 #if __TBB_STATISTICS
1313  my_info_resizes++; // concurrent ones
1314 #endif
1315  enable_segment( grow_segment, my_allocator );
1316  }
1317  if( tmp_n ) // if op_insert only
1318  delete_node( tmp_n );
1319  return return_value;
1320 }
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_id __itt_string_handle * key
node * search_bucket(const key_type &key, bucket *b) const
Class that implements exponential backoff.
Definition: tbb_machine.h:345
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
bool check_mask_race(const hashcode_t h, hashcode_t &m) const
Check for mask race.
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
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
void enable_segment(segment_index_t k, const Allocator &allocator, bool is_initial=false)
Enable segment.
#define __TBB_Yield()
Definition: ibm_aix51.h:44
T itt_load_word_with_acquire(const tbb::atomic< T > &src)
segment_index_t insert_new_node(bucket *b, node_base *n, hashcode_t mask)
Insert a node and check for load factor.

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

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

◆ operator=() [1/3]

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

Assignment.

Definition at line 917 of file concurrent_hash_map.h.

917  {
918  if( this!=&table ) {
920  clear();
921  tbb::internal::allocator_copy_assignment(my_allocator, table.my_allocator, pocca_type());
922  internal_copy(table);
923  }
924  return *this;
925  }
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
tbb::internal::false_type propagate_on_container_copy_assignment
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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

Here is the call graph for this function:

◆ operator=() [2/3]

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

Move Assignment.

Definition at line 929 of file concurrent_hash_map.h.

929  {
930  if(this != &table) {
932  internal_move_assign(std::move(table), pocma_type());
933  }
934  return *this;
935  }
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:305
tbb::internal::false_type propagate_on_container_move_assignment
void internal_move_assign(concurrent_hash_map &&other, tbb::internal::traits_true_type)

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

940  {
941  clear();
942  internal_copy(il.begin(), il.end(), il.size());
943  return *this;
944  }
void internal_copy(const concurrent_hash_map &source)
Copy "source" to *this, where *this must start out empty.

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

962  {
963  return range_type( *this, grainsize );
964  }
internal::hash_map_range< iterator > range_type

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

965  {
966  return const_range_type( *this, grainsize );
967  }
internal::hash_map_range< const_iterator > const_range_type

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

1420  {
1421  reserve( sz, my_allocator ); // TODO: add reduction of number of buckets as well
1423  hashcode_t b = (mask+1)>>1; // size or first index of the last segment
1424  __TBB_ASSERT((b&(b-1))==0, NULL); // zero or power of 2
1425  bucket *bp = get_bucket( b ); // only the last segment should be scanned for rehashing
1426  for(; b <= mask; b++, bp++ ) {
1427  node_base *n = bp->node_list;
1428  __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed || n == internal::rehash_req, "Broken internal structure" );
1429  __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during rehash() execution" );
1430  if( n == internal::rehash_req ) { // rehash bucket, conditional because rehashing of a previous bucket may affect this one
1431  hashcode_t h = b; bucket *b_old = bp;
1432  do {
1433  __TBB_ASSERT( h > 1, "The lowermost buckets can't be rehashed" );
1434  hashcode_t m = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
1435  b_old = get_bucket( h &= m );
1436  } while( b_old->node_list == internal::rehash_req );
1437  // now h - is index of the root rehashed bucket b_old
1438  mark_rehashed_levels( h ); // mark all non-rehashed children recursively across all segments
1439  for( node_base **p = &b_old->node_list, *q = *p; is_valid(q); q = *p ) {
1440  hashcode_t c = my_hash_compare.hash( static_cast<node*>(q)->value().first );
1441  if( (c & mask) != h ) { // should be rehashed
1442  *p = q->next; // exclude from b_old
1443  bucket *b_new = get_bucket( c & mask );
1444  __TBB_ASSERT( b_new->node_list != internal::rehash_req, "hash() function changed for key in table or internal error" );
1445  add_to_bucket( b_new, q );
1446  } else p = &q->next; // iterate to next item
1447  }
1448  }
1449  }
1450 #if TBB_USE_PERFORMANCE_WARNINGS
1451  int current_size = int(my_size), buckets = int(mask)+1, empty_buckets = 0, overpopulated_buckets = 0; // usage statistics
1452  static bool reported = false;
1453 #endif
1454 #if TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS
1455  for( b = 0; b <= mask; b++ ) {// only last segment should be scanned for rehashing
1456  if( b & (b-2) ) ++bp; // not the beginning of a segment
1457  else bp = get_bucket( b );
1458  node_base *n = bp->node_list;
1459  __TBB_ASSERT( *reinterpret_cast<intptr_t*>(&bp->mutex) == 0, "concurrent or unexpectedly terminated operation during rehash() execution" );
1460  __TBB_ASSERT( is_valid(n) || n == internal::empty_rehashed, "Broken internal structure" );
1461 #if TBB_USE_PERFORMANCE_WARNINGS
1462  if( n == internal::empty_rehashed ) empty_buckets++;
1463  else if( n->next ) overpopulated_buckets++;
1464 #endif
1465 #if TBB_USE_ASSERT
1466  for( ; is_valid(n); n = n->next ) {
1467  hashcode_t h = my_hash_compare.hash( static_cast<node*>(n)->value().first ) & mask;
1468  __TBB_ASSERT( h == b, "hash() function changed for key in table or internal error" );
1469  }
1470 #endif
1471  }
1472 #endif // TBB_USE_ASSERT || TBB_USE_PERFORMANCE_WARNINGS
1473 #if TBB_USE_PERFORMANCE_WARNINGS
1474  if( buckets > current_size) empty_buckets -= buckets - current_size;
1475  else overpopulated_buckets -= current_size - buckets; // TODO: load_factor?
1476  if( !reported && buckets >= 512 && ( 2*empty_buckets > current_size || 2*overpopulated_buckets > current_size ) ) {
1478  "Performance is not optimal because the hash function produces bad randomness in lower bits in %s.\nSize: %d Empties: %d Overlaps: %d",
1480  typeid(*this).name(),
1481 #else
1482  "concurrent_hash_map",
1483 #endif
1484  current_size, empty_buckets, overpopulated_buckets );
1485  reported = true;
1486  }
1487 #endif
1488 }
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
intptr_t __TBB_Log2(uintptr_t x)
Definition: tbb_machine.h:860
void __TBB_EXPORTED_FUNC runtime_warning(const char *format,...)
Report a runtime warning.
void reserve(size_type buckets, const Allocator &allocator)
Prepare enough segments for number of buckets.
static hash_map_node_base *const empty_rehashed
Rehashed empty bucket flag.
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
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
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_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
atomic< hashcode_t > my_mask
Hash mask = sum of allocated segment sizes - 1.
static void add_to_bucket(bucket *b, node_base *n)
Add node.
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
auto first(Container &c) -> decltype(begin(c))
#define __TBB_USE_OPTIONAL_RTTI
Definition: tbb_config.h:125
void const char const char int ITT_FORMAT __itt_group_sync p
static hash_map_node_base *const rehash_req
Incompleteness flag value.
atomic< size_type > my_size
Size of container in stored items.
hash_map_node_base node_base
Node base type.
bucket * get_bucket(hashcode_t h) const
Get bucket by (masked) hashcode.

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

Here is the call graph for this function:

◆ rehash_bucket()

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

Definition at line 709 of file concurrent_hash_map.h.

709  {
710  __TBB_ASSERT( *(intptr_t*)(&b_new->mutex), "b_new must be locked (for write)");
711  __TBB_ASSERT( h > 1, "The lowermost buckets can't be rehashed" );
712  __TBB_store_with_release(b_new->node_list, internal::empty_rehashed); // mark rehashed
713  hashcode_t mask = ( 1u<<__TBB_Log2( h ) ) - 1; // get parent mask from the topmost bit
714 #if __TBB_STATISTICS
715  my_info_rehashes++; // invocations of rehash_bucket
716 #endif
717 
718  bucket_accessor b_old( this, h & mask );
719 
720  mask = (mask<<1) | 1; // get full mask for new bucket
721  __TBB_ASSERT( (mask&(mask+1))==0 && (h & mask) == h, NULL );
722  restart:
723  for( node_base **p = &b_old()->node_list, *n = __TBB_load_with_acquire(*p); is_valid(n); n = *p ) {
724  hashcode_t c = my_hash_compare.hash( static_cast<node*>(n)->value().first );
725 #if TBB_USE_ASSERT
726  hashcode_t bmask = h & (mask>>1);
727  bmask = bmask==0? 1 : ( 1u<<(__TBB_Log2( bmask )+1 ) ) - 1; // minimal mask of parent bucket
728  __TBB_ASSERT( (c & bmask) == (h & bmask), "hash() function changed for key in table" );
729 #endif
730  if( (c & mask) == h ) {
731  if( !b_old.is_writer() )
732  if( !b_old.upgrade_to_writer() ) {
733  goto restart; // node ptr can be invalid due to concurrent erase
734  }
735  *p = n->next; // exclude from b_old
736  add_to_bucket( b_new, n );
737  } else p = &n->next; // iterate to next item
738  }
739  }
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
intptr_t __TBB_Log2(uintptr_t x)
Definition: tbb_machine.h:860
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:713
static hash_map_node_base *const empty_rehashed
Rehashed empty bucket flag.
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
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
static void add_to_bucket(bucket *b, node_base *n)
Add node.
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
auto first(Container &c) -> decltype(begin(c))
void const char const char int ITT_FORMAT __itt_group_sync p
T __TBB_load_with_acquire(const volatile T &location)
Definition: tbb_machine.h:709
hash_map_node_base node_base
Node base type.

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

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ search_bucket()

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

Definition at line 677 of file concurrent_hash_map.h.

677  {
678  node *n = static_cast<node*>( b->node_list );
679  while( is_valid(n) && !my_hash_compare.equal(key, n->value().first) )
680  n = static_cast<node*>( n->next );
681  __TBB_ASSERT(n != internal::rehash_req, "Search can be executed only for rehashed bucket");
682  return n;
683  }
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_id __itt_string_handle * key
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
static hash_map_node_base *const rehash_req
Incompleteness flag value.

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

980 { return my_size; }
atomic< size_type > my_size
Size of container in stored items.

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

1409  {
1410  typedef typename node_allocator_traits::propagate_on_container_swap pocs_type;
1411  if (this != &table && (pocs_type::value || my_allocator == table.my_allocator)) {
1412  using std::swap;
1413  tbb::internal::allocator_swap(this->my_allocator, table.my_allocator, pocs_type());
1414  swap(this->my_hash_compare, table.my_hash_compare);
1415  internal_swap(table);
1416  }
1417 }
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
tbb::internal::false_type propagate_on_container_swap
void swap(concurrent_hash_map &table)
swap two instances. Iterators are invalidated
void internal_swap(hash_map_base &table)
Swap hash_map_bases.
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)

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

◆ accessor_location [2/2]

template<typename Key, typename T, typename HashCompare, typename Allocator>
const_accessor* accessor_location ( const_accessor a)
friend

Definition at line 1133 of file concurrent_hash_map.h.

1133 { return &a;}

◆ const_accessor

template<typename Key, typename T, typename HashCompare, typename Allocator>
friend class const_accessor
friend

Definition at line 597 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 575 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 578 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

◆ is_write_access_needed [2/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>
bool is_write_access_needed ( const_accessor const &  )
friend

Definition at line 1136 of file concurrent_hash_map.h.

1136 { return false;}

◆ is_write_access_needed [3/3]

template<typename Key, typename T, typename HashCompare, typename Allocator>
bool is_write_access_needed ( accessor_not_used const &  )
friend

Definition at line 1137 of file concurrent_hash_map.h.

1137 { return false;}

Member Data Documentation

◆ my_allocator

◆ my_hash_compare


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

Copyright © 2005-2019 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.