[For complete, up-to-date TBB information visit: http://www.ThreadingBuildingBlocks.org]
Summary
Template class for associative container with concurrent access.
Syntax
template<typename Key, typename T, typename HashCompare> class concurrent_hash_map;
Header
#include "tbb/concurrent_hash_map.h"
Description
A concurrent_hash_map maps keys to values in a way that permits multiple threads to concurrently access values. The keys are unordered. The interface resembles typical STL associative containers, but with some differences critical to supporting concurrent access.
Types Key and T must model the CopyConstructible concept ( 2.2.3 ).
Type HashCompare specifies how keys are hashed and compared for equality. It must model the HashCompare concept in Table 13.
Table 13: HashCompare Concept
Pseudo-Signature
Semantics
HashCompare::HashCompare( const HashCompare & )
Copy constructor
HashCompare::~HashCompare ()
Destructor
bool HashCompare::equal( const Key& j, const Key& k ) const
True if keys are equal
size_t HashCompare::hash( const Key& k )
Hashcode for key
CAUTION: As for most hash tables, if two keys are equal, they must hash to the same hash code. That is for a given HashCompare h and any two keys j and k, the following assertion must hold: “!h.equal(j,k) || h.hash(j)==h.hash(k)”. The importance of this property is the reason that concurrent_hash_map makes key equality and hashing travel together in a single object instead of being separate objects.
Members
namespace tbb {
template<typename Key, typename T, typename HashCompare>
class concurrent_hash_map {
public:
// types
typedef Key key_type;
typedef T mapped_type;
typedef std::pair<const Key,T> value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
// whole-table operations
concurrent_hash_map();
concurrent_hash_map( const concurrent_hash_map& );
~concurrent_hash_map();
concurrent_hash_map operator=( const concurrent_hash_map& );
void clear();
// concurrent access
class const_accessor;
class accessor;
// concurrent operations on a table
bool find( const_accessor& result, const Key& key ) const;
bool find( accessor& result, const Key& key );
bool insert( const_accessor& result, const Key& key );
bool insert( accessor& result, const Key& key );
bool erase( const Key& key );
// parallel iteration
typedef implementation defined range_type;
typedef implementation defined const_range_type;
range_type range( size_t grainsize );
const_range_type range( size_t grainsize ) const;
// Capacity
size_type size() const;
bool empty() const;
size_type max_size() const;
// Iterators
typedef implementation defined iterator;
typedef implementation defined const_iterator;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
};
}
These operations affect an entire table. Do not concurrently invoke them on the same table.
4.1.1.1 concurrent_hash_map()
Effects
Construct empty table.
4.1.1.2 concurrent_hash_map( const concurrent_hash_map& table )
Effects
Copy a table. The table being copied may have map operations running on it concurrently.
4.1.1.3 ~concurrent_hash_map()
Effects
Remove all items from the table and destroy it. This method is not safe to execute concurrently with other methods on the same concurrent_hash_map.
4.1.1.4 concurrent_hash_map& operator= ( concurrent_hash_map& source )
Effects
If source and destination (this) table are distinct, clear the destination table and copy all key-value pairs from the source table to the destination table. Otherwise, do nothing.
Returns
Reference to the destination table.
4.1.1.5 void clear()
Effects
Erase all key-value pairs from the table.
Member classes const_accessor and accessor are called accessors. Accessors allow multiple threads to concurrently access pairs in a shared concurrent_hash_map. An accessor acts as a smart pointer to a pair in a concurrent_hash_map. It holds an implicit lock on a pair until the instance is destroyed or method release is called on the accessor.
Classes const_accessor and accessor differ in the kind of access that they permit.
Table 14: Differences Between const_accessor and accessor
Class
value_type
Implied Lock on pair
const_accessor
const std::pair<const Key,T>
Reader lock – permits shared access with other readers
accessor
std::pair<const Key,T>
Writer lock – blocks access by other threads
Accessors cannot be assigned or copy-constructed, because allowing such would greatly complicate the locking semantics.
4.1.2.1 const_accessor
Summary
Provides read-only access to a pair in a concurrent_hash_map.
Syntax
template<typename Key, typename T, typename HashCompare> class concurrent_hash_map<Key,T,HashCompare>::const_accessor;
Header
#include "tbb/concurrent_hash_map.h"
Description
A const_accessor permits read-only access to a key-value pair in a concurrent_hash_map.
Members
namespace tbb {
template<typename Key, typename T, typename HashCompare>
class concurrent_hash_map<Key,T,HashCompare>::const_accessor {
public:
// types
typedef const std::pair<const Key,T> value_type;
// construction and destruction
const_accessor();
~const_accessor();
// inspection
bool empty() const;
const value_type& operator*() const;
const value_type* operator->() const;
// early release
void release();
};
}
4.1.2.1.1 bool empty() const
Returns
True if instance points to nothing; false if instance points to a key-value pair.
4.1.2.1.2 void release()
Effects
If !empty(), release the implied lock on the pair, and set instance to point to nothing. Otherwise do nothing.
4.1.2.1.3 const value_type& operator*() const
Effects
Raise assertion failure if empty() and TBB_DO_ASSERT ( 2.6.1) is defined as nonzero.
Returns
Const reference to key-value pair.
4.1.2.1.4 const value_type* operator->() const
Returns
&operator*()
4.1.2.1.5 const_accessor()
Effects
Construct const_accessor that points to nothing.
4.1.2.1.6 ~const_accessor
Effects
If pointing to key-value pair, release the implied lock on the pair.
4.1.2.2 accessor
Summary
Class that provides read and write access to a pair in a concurrent_hash_map.
Syntax
template<typename Key, typename T, typename HashCompare>
class concurrent_hash_map<Key,T,HashCompare>::accessor;
Header
#include "tbb/concurrent_hash_map.h"
Description
An accessor permits read and write access to a key-value pair in a concurrent_hash_map. It is derived from a const_accessor, and thus can be implicitly cast to a const_accessor.
Members
namespace tbb {
template<typename Key, typename T, typename HashCompare>
class concurrent_hash_map<Key,T,HashCompare>::accessor:
concurrent_hash_map<Key,T,HashCompare>::const_accessor {
public:
typedef std::pair<const Key,T> value_type;
value_type& operator*() const;
value_type* operator->() const;
};
}
4.1.2.2.1 value_type& operator*() const
Effects
Raise assertion failure if empty() and TBB_DO_ASSERT ( 2.6.1) is defined as nonzero.
Returns
Reference to key-value pair.
4.1.2.2.2 value_type* operator->() const
Returns
&operator*()
The operations find, insert, and erase are the only operations that may be concurrently invoked on the same concurrent_hash_map. These operations search the table for a key-value pair that matches a given key. The find and insert methods each have two variants. One takes a const_accessor argument and provides read-only access to the desired key-value pair. The other takes an accessor argument and provides write access.
TIP: If the nonconst variant succeeds in finding the key, the consequent write access blocks any other thread from accessing the key until the accessor object is destroyed. Where possible, use the const variant to improve concurrency.
The result of the map operations is true if the operation succeeds.
4.1.3.1 bool find( const_accessor& result, const Key& key ) const
Effects
Search table for pair with given key. If key is found, set result to provide read-only access to the matching pair.
Returns
True if key was found; false if key was not found.
4.1.3.2 bool find( accessor& result, const Key& key )
Effects
Search table for pair with given key. If key is found, set result to provide write access to the matching pair
Returns
True if key was found; false if key was not found.
4.1.3.3 bool insert( const_accessor& result, const Key& key )
Effects
Search table for pair with given key. If not present, insert new pair into table. The new pair is initialized with pair(key,T()). Set result to provide read-only access to the matching pair.
Returns
True if new pair was inserted; false if key is already in the map.
4.1.3.4 bool insert( accessor& result, const Key& key )
Effects
Search table for pair with given key. If not present, insert new pair into table. The new pair is initialized with pair(key,T()). Set result to provide write access to the matching pair.
Returns
True if new pair was inserted; false if key is already in the map.
4.1.3.5 bool erase(const Key& key )
Effects
Search table for pair with given key. Remove the matching pair if it exists.
Returns
True if pair was removed; false if key was not in the map.
Types const_range_type and range_type model the Range concept ( 3.2 ) and provide methods to access the bounds of the range as shown in Table 15 . The types differ only in that the bounds for a const_range_type are of type const_iterator, whereas the bounds for a range_type are of type iterator.
Use the range types in conjunction with parallel_for ( 3.4 ), parallel_reduce ( 3.5 3.6 ), and parallel_scan () to iterate over pairs in a concurrent_hash_map.
Table 15: Concept for concurrent_hash_map Range R (In Addition to Table 4)
Pseudo-Signature
Semantics
R::iterator R::begin() const
First item in range
R::iterator R::end() const
One past last item in range
4.1.4.1 const_range_type range( size_t grainsize ) const
Effects
Construct a const_range_type representing all keys in the table. The parameter grainsize is in units of hash table slots. Each slot typically has on average about one key-value pair.
Returns
const_range_type object for the table.
4.1.4.2 range_type range( size_t grainsize )
Returns
range_type object for the table.
4.1.5.1 size_type size() const
Returns
Number of key-value pairs in the table.
NOTE: This method takes constant time, but is slower than for most STL containers.
4.1.5.2 bool empty() const
Returns
size()==0.
NOTE: This method takes constant time, but is slower than for most STL containers.
4.1.5.3 size_type max_size() const
Returns
Inclusive upper bound on number of key-value pairs that the table can hold.
Template class concurrent_hash_map supports forward iterators; that is, iterators that can advance only forwards across the table. Reverse iterators are not supported.
4.1.6.1 iterator begin()
Returns
iterator pointing to beginning of key-value sequence.
4.1.6.2 iterator end()
Returns
iterator pointing to end of key-value sequence.
4.1.6.3 const_iterator begin() const
Returns
const_iterator with pointing to beginning of key-value sequence.
4.1.6.4 const_iterator end() const
Returns
const_iterator pointing to end of key-value sequence.
[For complete, up-to-date TBB information visit: http://www.ThreadingBuildingBlocks.org]