cds  2.2.0
cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits > Class Template Reference

Hash map based on multi-level array. More...

#include <cds/container/feldman_hashmap_rcu.h>

Inheritance diagram for cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >:
cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, std::pair< Key const, T >, Traits >

Public Types

typedef cds::urcu::gc< RCU > gc
 RCU garbage collector.
 
typedef Key key_type
 Key type.
 
typedef T mapped_type
 Mapped type.
 
typedef std::pair< key_type const, mapped_typevalue_type
 Key-value pair to be stored in the map.
 
typedef Traits traits
 Map traits.
 
typedef traits::hash hasher
 Hash functor, see feldman_hashmap::traits::hash.
 
typedef maker::hash_type hash_type
 Hash type deduced from hasher return type.
 
typedef base_class::hash_comparator hash_comparator
 hash compare functor based on Traits::compare and Traits::less
 
typedef traits::item_counter item_counter
 Item counter type.
 
typedef traits::allocator allocator
 Element allocator.
 
typedef traits::node_allocator node_allocator
 Array node allocator.
 
typedef traits::memory_model memory_model
 Memory model.
 
typedef traits::back_off back_off
 Back-off strategy.
 
typedef traits::stat stat
 Internal statistics type.
 
typedef traits::rcu_check_deadlock rcu_check_deadlock
 Deadlock checking policy.
 
typedef gc::scoped_lock rcu_lock
 RCU scoped lock.
 
typedef feldman_hashmap::level_statistics level_statistics
 Level statistics.
 
typedef implementation_defined iterator
 bidirectional iterator type
 
typedef implementation_defined const_iterator
 bidirectional const iterator type
 
typedef implementation_defined reverse_iterator
 bidirectional reverse iterator type
 
typedef implementation_defined const_reverse_iterator
 bidirectional reverse const iterator type
 

Public Member Functions

 FeldmanHashMap (size_t head_bits=8, size_t array_bits=4)
 Creates empty map. More...
 
 ~FeldmanHashMap ()
 Destructs the map and frees all data.
 
template<typename K >
bool insert (K &&key)
 Inserts new element with key and default value. More...
 
template<typename K , typename V >
bool insert (K &&key, V &&val)
 Inserts new element. More...
 
template<typename K , typename Func >
bool insert_with (K &&key, Func func)
 Inserts new element and initialize it by a functor. More...
 
template<typename K , typename... Args>
bool emplace (K &&key, Args &&... args)
 For key key inserts data of type value_type created in-place from std::forward<Args>(args)... More...
 
template<typename K , typename Func >
std::pair< bool, bool > update (K &&key, Func func, bool bInsert=true)
 Updates data by key. More...
 
template<typename K >
bool erase (K const &key)
 Delete key from the map. More...
 
template<typename K , typename Func >
bool erase (K const &key, Func f)
 Delete key from the map. More...
 
template<typename K >
exempt_ptr extract (K const &key)
 Extracts the item from the map with specified key. More...
 
template<typename K >
bool contains (K const &key)
 Checks whether the map contains key. More...
 
template<typename K , typename Func >
bool find (K const &key, Func f)
 Find the key key. More...
 
template<typename K >
value_typeget (K const &key)
 Finds the key key and return the item found. More...
 
void clear ()
 Clears the map (non-atomic) More...
 
bool empty () const
 Checks if the map is empty. More...
 
size_t size () const
 Returns item count in the map.
 
stat const & statistics () const
 Returns const reference to internal statistics.
 
size_t head_size () const
 Returns the size of head node.
 
size_t array_node_size () const
 Returns the size of the array node.
 
void get_level_statistics (std::vector< feldman_hashmap::level_statistics > &stat) const
 Collects tree level statistics into stat. More...
 
Thread-safe iterators
iterator begin ()
 Returns an iterator to the beginning of the map. More...
 
const_iterator begin () const
 Returns an const iterator to the beginning of the map.
 
const_iterator cbegin ()
 Returns an const iterator to the beginning of the map.
 
iterator end ()
 Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
 
const_iterator end () const
 Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
 
const_iterator cend ()
 Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
 
reverse_iterator rbegin ()
 Returns a reverse iterator to the first element of the reversed map.
 
const_reverse_iterator rbegin () const
 Returns a const reverse iterator to the first element of the reversed map.
 
const_reverse_iterator crbegin ()
 Returns a const reverse iterator to the first element of the reversed map.
 
reverse_iterator rend ()
 Returns a reverse iterator to the element following the last element of the reversed map. More...
 
const_reverse_iterator rend () const
 Returns a const reverse iterator to the element following the last element of the reversed map. More...
 
const_reverse_iterator crend ()
 Returns a const reverse iterator to the element following the last element of the reversed map. More...
 

Static Public Attributes

static constexpr const bool c_bExtractLockExternal = false
 Group of extract_xxx functions does not require external locking.
 

Additional Inherited Members

- Protected Types inherited from cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, std::pair< Key const, T >, Traits >
typedef cds::urcu::gc< RCU > gc
 Garbage collector.
 
typedef std::pair< Key const, T > value_type
 type of value stored in the set
 
typedef Traits traits
 Traits template parameter, see feldman_hashset::traits.
 
typedef traits::hash_accessor hash_accessor
 Hash accessor functor.
 
typedef base_class::hash_type hash_type
 Hash type deduced from hash_accessor return type.
 
typedef traits::disposer disposer
 data node disposer
 
typedef base_class::hash_comparator hash_comparator
 hash compare functor based on traits::compare and traits::less options
 
typedef traits::item_counter item_counter
 Item counter type.
 
typedef traits::node_allocator node_allocator
 Array node allocator.
 
typedef traits::memory_model memory_model
 Memory model.
 
typedef traits::back_off back_off
 Backoff strategy.
 
typedef traits::stat stat
 Internal statistics type.
 
typedef gc::template guarded_ptr< value_typeguarded_ptr
 Guarded pointer.
 
typedef feldman_hashset::level_statistics level_statistics
 Level statistics.
 
typedef implementation_defined iterator
 bidirectional iterator type
 
typedef implementation_defined const_iterator
 bidirectional const iterator type
 
typedef implementation_defined reverse_iterator
 bidirectional reverse iterator type
 
typedef implementation_defined const_reverse_iterator
 bidirectional reverse const iterator type
 
- Protected Member Functions inherited from cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, std::pair< Key const, T >, Traits >
 FeldmanHashSet (size_t head_bits=8, size_t array_bits=4)
 Creates empty set. More...
 
 ~FeldmanHashSet ()
 Destructs the set and frees all data.
 
bool insert (value_type &val)
 Inserts new node. More...
 
bool insert (value_type &val, Func f)
 Inserts new node. More...
 
std::pair< bool, bool > update (value_type &val, bool bInsert=true)
 Updates the node. More...
 
bool unlink (value_type const &val)
 Unlinks the item val from the set. More...
 
bool erase (hash_type const &hash)
 Deletes the item from the set. More...
 
bool erase (hash_type const &hash, Func f)
 Deletes the item from the set. More...
 
bool erase_at (iterator const &iter)
 Deletes the item pointed by iterator iter. More...
 
guarded_ptr extract (hash_type const &hash)
 Extracts the item with specified hash. More...
 
bool find (hash_type const &hash, Func f)
 Finds an item by it's hash. More...
 
bool contains (hash_type const &hash)
 Checks whether the set contains hash. More...
 
guarded_ptr get (hash_type const &hash)
 Finds an item by it's hash and returns the item found. More...
 
void clear ()
 Clears the set (non-atomic) More...
 
bool empty () const
 Checks if the set is empty. More...
 
size_t size () const
 Returns item count in the set.
 
stat const & statistics () const
 Returns const reference to internal statistics.
 
void get_level_statistics (std::vector< feldman_hashset::level_statistics > &stat) const
 Collects tree level statistics into stat. More...
 
iterator begin ()
 Returns an iterator to the beginning of the set. More...
 
const_iterator begin () const
 Returns an const iterator to the beginning of the set.
 
const_iterator cbegin ()
 Returns an const iterator to the beginning of the set.
 
iterator end ()
 Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 
const_iterator end () const
 Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 
const_iterator cend ()
 Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 
reverse_iterator rbegin ()
 Returns a reverse iterator to the first element of the reversed set.
 
const_reverse_iterator rbegin () const
 Returns a const reverse iterator to the first element of the reversed set.
 
const_reverse_iterator crbegin ()
 Returns a const reverse iterator to the first element of the reversed set.
 
reverse_iterator rend ()
 Returns a reverse iterator to the element following the last element of the reversed set. More...
 
const_reverse_iterator rend () const
 Returns a const reverse iterator to the element following the last element of the reversed set. More...
 
const_reverse_iterator crend ()
 Returns a const reverse iterator to the element following the last element of the reversed set. More...
 
- Static Protected Attributes inherited from cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, std::pair< Key const, T >, Traits >
static constexpr size_t const c_nHazardPtrCount
 Count of hazard pointers required.
 
static constexpr size_t const c_hash_size
 The size of hash_type in bytes, see feldman_hashset::traits::hash_size for explanation.
 

Detailed Description

template<class RCU, typename Key, typename T, class Traits = feldman_hashmap::traits>
class cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >

Hash map based on multi-level array.

Source:

  • [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: Wait-free Extensible Hash Maps"

See algorithm short description here

Note
Two important things you should keep in mind when you're using FeldmanHashMap:
  • all keys is converted to fixed-size bit-string by hash functor provided. You can use variable-length keys, for example, std::string as a key for FeldmanHashMap, but real key in the map will be fixed-size hash values of your keys. For the strings you may use well-known hashing algorithms like SHA1, SHA2, MurmurHash, CityHash or its successor FarmHash and so on, which converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in FeldmanHashMap. If your key is fixed-sized the hash functor is optional, see feldman_hashmap::traits::hash for explanation and examples.
  • FeldmanHashMap uses a perfect hashing. It means that if two different keys, for example, of type std::string, have identical hash then you cannot insert both that keys in the map. FeldmanHashMap does not maintain the key, it maintains its fixed-size hash value.

The map supports bidirectional thread-safe iterators.

Template parameters:

Note
Before including <cds/intrusive/feldman_hashset_rcu.h> you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files.

Constructor & Destructor Documentation

§ FeldmanHashMap()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::FeldmanHashMap ( size_t  head_bits = 8,
size_t  array_bits = 4 
)
inline

Creates empty map.

Parameters
head_bits2head_bits specifies the size of head array, minimum is 4.
array_bits2array_bits specifies the size of array node, minimum is 2.

Equation for head_bits and array_bits:

sizeof(hash_type) * 8 == head_bits + N * array_bits

where N is multi-level array depth.

Member Function Documentation

§ begin()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
iterator cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::begin ( )
inline

Returns an iterator to the beginning of the map.

The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment under explicit RCU lock. RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the map since erasing under RCU lock can lead to a deadlock. However, another thread can call erase() safely while your thread is iterating.

A typical example is:

struct foo {
// ... other fields
uint32_t payload; // only for example
};
typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
map_type m;
// ...
// iterate over the map
{
// lock the RCU.
typename set_type::rcu_lock l; // scoped RCU lock
// traverse the map
for ( auto i = m.begin(); i != s.end(); ++i ) {
// deal with i. Remember, erasing is prohibited here!
i->second.payload++;
}
} // at this point RCU lock is released

Each iterator object supports the common interface:

  • dereference operators:
    value_type [const] * operator ->() noexcept
    value_type [const] & operator *() noexcept
  • pre-increment and pre-decrement. Post-operators is not supported
  • equality operators == and !=. Iterators are equal iff they point to the same cell of the same array node. Note that for two iterators it1 and it2 the condition it1 == it2 does not entail &(*it1) == &(*it2) : welcome to concurrent containers
Note
It is possible the item can be iterated more that once, for example, if an iterator points to the item in an array node that is being splitted.

§ clear()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
void cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::clear ( )
inline

Clears the map (non-atomic)

The function unlink all data node from the map. The function is not atomic but is thread-safe. After clear() the map may not be empty because another threads may insert items.

§ contains()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K >
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::contains ( K const &  key)
inline

Checks whether the map contains key.

The function searches the item by its hash that is equal to hash( key_type( key )) and returns true if it is found, or false otherwise.

§ crend()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
const_reverse_iterator cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::crend ( )
inline

Returns a const reverse iterator to the element following the last element of the reversed map.

It corresponds to the element preceding the first element of the non-reversed container. This element acts as a placeholder, attempting to access it results in undefined behavior.

§ emplace()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K , typename... Args>
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::emplace ( K &&  key,
Args &&...  args 
)
inline

For key key inserts data of type value_type created in-place from std::forward<Args>(args)...

Returns true if inserting successful, false otherwise.

The function locks RCU internally.

§ empty()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::empty ( ) const
inline

Checks if the map is empty.

Emptiness is checked by item counting: if item count is zero then the map is empty. Thus, the correct item counting feature is an important part of the map implementation.

§ erase() [1/2]

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K >
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::erase ( K const &  key)
inline

Delete key from the map.

key_type must be constructible from value of type K. The function deletes the element with hash value equal to hash( key_type( key ))

Return true if key is found and deleted, false otherwise.

RCU should not be locked. The function locks RCU internally.

§ erase() [2/2]

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K , typename Func >
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::erase ( K const &  key,
Func  f 
)
inline

Delete key from the map.

The function searches an item with hash value equal to hash( key_type( key )), calls f functor and deletes the item. If key is not found, the functor is not called.

The functor Func interface:

struct extractor {
void operator()(value_type& item) { ... }
};

where item is the element found.

key_type must be constructible from value of type K.

Return true if key is found and deleted, false otherwise

RCU should not be locked. The function locks RCU internally.

§ extract()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K >
exempt_ptr cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::extract ( K const &  key)
inline

Extracts the item from the map with specified key.

The function searches an item with key equal to hash( key_type( key )) in the map, unlinks it from the map, and returns a guarded pointer to the item found. If key is not found the function returns an empty guarded pointer.

RCU synchronize method can be called. RCU should NOT be locked. The function does not call the disposer for the item found. The disposer will be implicitly invoked when the returned object is destroyed or when its release() member function is called. Example:

map_type theMap;
// ...
typename map_type::exempt_ptr ep( theMap.extract( 5 ));
if ( ep ) {
// Deal with ep
//...
// Dispose returned item.
ep.release();
}

§ find()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K , typename Func >
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::find ( K const &  key,
Func  f 
)
inline

Find the key key.

The function searches the item by its hash that is equal to hash( key_type( key )) and calls the functor f for item found. The interface of Func functor is:

struct functor {
void operator()( value_type& item );
};

where item is the item found.

The functor may change item.second.

The function returns true if key is found, false otherwise.

§ get()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K >
value_type* cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::get ( K const &  key)
inline

Finds the key key and return the item found.

The function searches the item by its hash and returns the pointer to the item found. If hash is not found the function returns nullptr.

RCU should be locked before the function invocation. Returned pointer is valid only while RCU is locked.

Usage:

my_map theMap;
// ...
{
// lock RCU
my_map::rcu_lock;
foo * p = theMap.get( 5 );
if ( p ) {
// Deal with p
//...
}
}

§ get_level_statistics()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
void cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::get_level_statistics ( std::vector< feldman_hashmap::level_statistics > &  stat) const
inline

Collects tree level statistics into stat.

The function traverses the set and collects statistics for each level of the tree into feldman_hashset::level_statistics struct. The element of stat[i] represents statistics for level i, level 0 is head array. The function is thread-safe and may be called in multi-threaded environment.

Result can be useful for estimating efficiency of hash functor you use.

§ insert() [1/2]

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K >
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::insert ( K &&  key)
inline

Inserts new element with key and default value.

The function creates an element with key and default value, and then inserts the node created into the map.

Preconditions:

  • The key_type should be constructible from a value of type K. In trivial case, K is equal to key_type.
  • The mapped_type should be default-constructible.

Returns true if inserting successful, false otherwise.

The function locks RCU internally.

§ insert() [2/2]

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K , typename V >
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::insert ( K &&  key,
V &&  val 
)
inline

Inserts new element.

The function creates a node with copy of val value and then inserts the node created into the map.

Preconditions:

  • The key_type should be constructible from key of type K.
  • The value_type should be constructible from val of type V.

Returns true if val is inserted into the map, false otherwise.

The function locks RCU internally.

§ insert_with()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K , typename Func >
bool cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::insert_with ( K &&  key,
Func  func 
)
inline

Inserts new element and initialize it by a functor.

This function inserts new element with key key and if inserting is successful then it calls func functor with signature

struct functor {
void operator()( value_type& item );
};

The argument item of user-defined functor func is the reference to the map's item inserted:

  • item.first is a const reference to item's key that cannot be changed.
  • item.second is a reference to item's value that may be changed.

key_type should be constructible from value of type K.

The function allows to split creating of new item into two part:

  • create item from key;
  • insert new item into the map;
  • if inserting is successful, initialize the value of item by calling func functor

This can be useful if complete initialization of object of value_type is heavyweight and it is preferable that the initialization should be completed only if inserting is successful.

The function locks RCU internally.

§ rend() [1/2]

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
reverse_iterator cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::rend ( )
inline

Returns a reverse iterator to the element following the last element of the reversed map.

It corresponds to the element preceding the first element of the non-reversed container. This element acts as a placeholder, attempting to access it results in undefined behavior.

§ rend() [2/2]

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
const_reverse_iterator cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::rend ( ) const
inline

Returns a const reverse iterator to the element following the last element of the reversed map.

It corresponds to the element preceding the first element of the non-reversed container. This element acts as a placeholder, attempting to access it results in undefined behavior.

§ update()

template<class RCU , typename Key , typename T , class Traits = feldman_hashmap::traits>
template<typename K , typename Func >
std::pair<bool, bool> cds::container::FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >::update ( K &&  key,
Func  func,
bool  bInsert = true 
)
inline

Updates data by key.

The operation performs inserting or replacing the element with lock-free manner.

If the key not found in the map, then the new item created from key will be inserted into the map iff bInsert is true (note that in this case the key_type should be constructible from type K). Otherwise, if key is found, it is replaced with a new item created from key. The functor Func signature:

struct my_functor {
void operator()( value_type& item, value_type * old );
};

where:

  • item - item of the map
  • old - old item of the map, if nullptr - the new item was inserted

The functor may change any fields of the item.second.

Returns std::pair<bool, bool> where first is true if operation is successful, second is true if new item has been added or false if key already exists.

The function locks RCU internally.

Warning
See insert item troubleshooting

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

cds 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:49:35 by Doxygen 1.8.12