cds
2.3.2
|
Michael's hash map (template specialization for RCU) More...
#include <cds/container/michael_map_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
RCU used as garbage collector. | |
typedef OrderedList | ordered_list |
type of ordered list used as a bucket implementation | |
typedef Traits | traits |
Map traits. | |
typedef ordered_list::key_type | key_type |
key type | |
typedef ordered_list::mapped_type | mapped_type |
value type | |
typedef ordered_list::value_type | value_type |
key/value pair stored in the list | |
typedef ordered_list::key_comparator | key_comparator |
key comparison functor | |
typedef ordered_list::stat | stat |
Internal statistics. | |
typedef ordered_list::exempt_ptr | exempt_ptr |
typedef ordered_list::raw_ptr | raw_ptr |
Type of get() member function return value. | |
typedef ordered_list::rcu_lock | rcu_lock |
RCU scoped lock. | |
typedef cds::opt::v::hash_selector< typename traits::hash >::type | hash |
Hash functor for key_type and all its derivatives that you use. | |
typedef traits::item_counter | item_counter |
Item counter type. | |
typedef traits::allocator | allocator |
Bucket table allocator. | |
Public Member Functions | |
MichaelHashMap (size_t nMaxItemCount, size_t nLoadFactor) | |
Initializes the map. More... | |
~MichaelHashMap () | |
Clears hash map and destroys it. | |
template<typename K > | |
bool | insert (const K &key) |
Inserts new node with key and default value. More... | |
template<typename K , typename V > | |
bool | insert (K const &key, V const &val) |
Inserts new node. More... | |
template<typename K , typename Func > | |
bool | insert_with (const K &key, Func func) |
Inserts new node and initialize it by a functor. More... | |
template<typename K , typename Func > | |
std::pair< bool, bool > | update (K const &key, Func func, bool bAllowInsert=true) |
Updates data by key . More... | |
template<typename K , typename... Args> | |
bool | emplace (K &&key, Args &&... args) |
For key key inserts data of type mapped_type created from args . More... | |
template<typename K > | |
bool | erase (const K &key) |
Deletes key from the map. More... | |
template<typename K , typename Less > | |
bool | erase_with (const K &key, Less pred) |
Deletes the item from the map using pred predicate for searching. More... | |
template<typename K , typename Func > | |
bool | erase (const K &key, Func f) |
Deletes key from the map. More... | |
template<typename K , typename Less , typename Func > | |
bool | erase_with (const K &key, Less pred, Func f) |
Deletes the item from the map using pred predicate for searching. More... | |
template<typename K > | |
exempt_ptr | extract (K const &key) |
Extracts an item from the map. More... | |
template<typename K , typename Less > | |
exempt_ptr | extract_with (K const &key, Less pred) |
Extracts an item from the map using pred predicate for searching. More... | |
template<typename K , typename Func > | |
bool | find (K const &key, Func f) |
Finds the key key . More... | |
template<typename K , typename Less , typename Func > | |
bool | find_with (K const &key, Less pred, Func f) |
Finds the key val using pred predicate for searching. More... | |
template<typename K > | |
bool | contains (K const &key) |
Checks whether the map contains key . More... | |
template<typename K , typename Less > | |
bool | contains (K const &key, Less pred) |
Checks whether the map contains key using pred predicate for searching. More... | |
template<typename K > | |
raw_ptr | get (K const &key) |
Finds key and return the item found. More... | |
template<typename K , typename Less > | |
raw_ptr | get_with (K const &key, Less pred) |
Finds key and return the item found. More... | |
void | clear () |
Clears the map (not atomic) More... | |
bool | empty () const |
Checks if the map is empty. More... | |
size_t | size () const |
Returns item count in the map. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
size_t | bucket_count () const |
Returns the size of hash table. More... | |
Static Public Attributes | |
static constexpr const bool | c_bExtractLockExternal = ordered_list::c_bExtractLockExternal |
Group of extract_xxx functions require external locking if underlying ordered list requires that. | |
Forward iterators (thread-safe under RCU lock) | |
typedef iterator_type< false > | iterator |
Forward iterator. More... | |
typedef iterator_type< true > | const_iterator |
Const forward iterator. | |
iterator | begin () |
Returns a forward iterator addressing the first element in a map. More... | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a map. More... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a map. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first element in a map. | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a map. | |
const_iterator | cend () const |
Returns an const iterator that addresses the location succeeding the last element in a map. | |
Michael's hash map (template specialization for RCU)
Michael's hash table algorithm is based on lock-free ordered list and it is very simple. The main structure is an array T
of size M
. Each element in T
is basically a pointer to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded. However, each bucket may contain unbounded number of items.
Template parameters are:
RCU
- one of RCU typeOrderedList
- ordered key-value list implementation used as bucket for hash map, for example, MichaelKVList
. The ordered list implementation specifies the Key
and Value
types stored in the hash-map, the reclamation schema GC
used by hash-map, the comparison functor for the type Key
and other features specific for the ordered list.Traits
- map traits, default is michael_map::traits
. Instead of defining Traits
struct you may use option-based syntax with michael_map::make_traits
metafunctionMany of the class function take a key argument of type K
that in general is not key_type
. key_type
and an argument of template type K
must meet the following requirements:
key_type
should be constructible from value of type K
;key
of type K:
hash( key_type(key)) == hash( key )
key_type
and K
should be comparableHow to use
The tips about how to use Michael's map see MichaelHashMap. Remember, that you should include RCU-related header file (for example, cds/urcu/general_buffered.h
) before including cds/container/michael_map_rcu.h
.
typedef ordered_list::exempt_ptr cds::container::MichaelHashMap< cds::urcu::gc< RCU >, OrderedList, Traits >::exempt_ptr |
pointer to extracted node
typedef iterator_type< false > cds::container::MichaelHashMap< cds::urcu::gc< RCU >, OrderedList, Traits >::iterator |
Forward iterator.
The forward iterator for Michael's map is based on OrderedList
forward iterator and has some features:
You may safely use iterators in multi-threaded environment only under RCU lock. Otherwise, a crash is possible if another thread deletes the element the iterator points to.
The iterator interface:
|
inline |
Initializes the map.
The Michael's hash map is non-expandable container. You should point the average count of items nMaxItemCount
when you create an object. nLoadFactor
parameter defines average count of items per bucket and it should be small number between 1 and 10. Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [O(nLoadFactor)
]. Note, that many popular STL hash map implementation uses load factor 1.
The ctor defines hash table size as rounding nMacItemCount / nLoadFactor
up to nearest power of two.
nMaxItemCount | estimation of max item count in the hash map |
nLoadFactor | load factor: estimation of max number of items in the bucket |
|
inline |
|
inline |
Returns the size of hash table.
Since MichaelHashMap
cannot dynamically extend the hash table size, the value returned is an constant depending on object initialization parameters; see MichaelHashMap::MichaelHashMap
for explanation.
|
inline |
Clears the map (not atomic)
The function erases all items from the map.
The function is not atomic. It cleans up each bucket and then resets the item counter to zero. If there are a thread that performs insertion while clear
is working the result is undefined in general case: empty()
may return true
but the map may contain item(s). Therefore, clear
may be used only for debugging purposes.
RCU synchronize
method can be called. RCU should not be locked.
|
inline |
Checks whether the map contains key
.
The function searches the item with key equal to key
and returns true
if it is found, and false
otherwise.
The function applies RCU lock internally.
|
inline |
Checks whether the map contains key
using pred
predicate for searching.
The function is an analog of contains( key )
but pred
is used for key comparing. Less
functor has the interface like std::less
. Less
must imply the same element order as the comparator used for building the map.
|
inline |
For key key
inserts data of type mapped_type
created from args
.
key_type
should be constructible from type K
Returns true
if inserting successful, false
otherwise.
|
inline |
Checks if the map is empty.
atomicity::empty_item_counter
in traits::item_counter
, the function always returns true
.
|
inline |
|
inline |
|
inline |
Deletes key
from the map.
The function searches an item with key key
, calls f
functor and deletes the item. If key
is not found, the functor is not called.
The functor Func
interface:
RCU synchronize
method can be called. RCU should not be locked.
Return true
if key is found and deleted, false
otherwise
|
inline |
Deletes the item from the map using pred
predicate for searching.
The function is an analog of erase(K const&) but pred
is used for key comparing. Less
predicate has the interface like std::less
. Less
must imply the same element order as the comparator used for building the map.
|
inline |
Deletes the item from the map using pred
predicate for searching.
The function is an analog of erase(K const&, Func) but pred
is used for key comparing. Less
functor has the interface like std::less
. Less
must imply the same element order as the comparator used for building the map.
|
inline |
Extracts an item from the map.
The function searches an item with key equal to key
, unlinks it from the map, and returns exempt_ptr pointer to the item found. If the item is not found the function return an empty exempt_ptr
.
The function just excludes the key from the map and returns a pointer to item found. Depends on ordered_list
you should or should not lock RCU before calling of this function:
|
inline |
Extracts an item from the map using pred
predicate for searching.
The function is an analog of extract(K const&)
but pred
is used for key comparing. Less
functor has the interface like std::less
. pred
must imply the same element order as the comparator used for building the map.
|
inline |
Finds the key key
.
The function searches the item with key equal to key
and calls the functor f
for item found. The interface of Func
functor is:
where item
is the item found.
The functor may change item.second
. Note that the functor is only guarantee that item
cannot be disposed during functor is executing. The functor does not serialize simultaneous access to the map's item
. If such access is possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
The function applies RCU lock internally.
The function returns true
if key
is found, false
otherwise.
|
inline |
Finds the key val
using pred
predicate for searching.
The function is an analog of find(K const&, Func) but pred
is used for key comparing. Less
functor has the interface like std::less
. Less
must imply the same element order as the comparator used for building the map.
|
inline |
Finds key
and return the item found.
The function searches the item with key equal to key
and returns the pointer to item found. If key
is not found it returns nullptr
. Note the type of returned value depends on underlying ordered_list
. For details, see documentation of ordered list you use.
Note the compare functor should accept a parameter of type K
that can be not the same as key_type
.
RCU should be locked before call of this function. Returned item is valid only while RCU is locked:
|
inline |
Finds key
and return the item found.
The function is an analog of get(K const&) but pred
is used for comparing the keys.
Less
functor has the semantics like std::less
but should take arguments of type key_type and K
in any order. pred
must imply the same element order as the comparator used for building the map.
|
inline |
Inserts new node with key and default value.
The function creates a node with key
and default value, and then inserts the node created into the map.
Preconditions:
key_type
should be constructible from value of type K
. In trivial case, K
is equal to key_type.mapped_type
should be default-constructible.The function applies RCU lock internally.
Returns true
if inserting successful, false
otherwise.
|
inline |
Inserts new node.
The function creates a node with copy of val
value and then inserts the node created into the map.
Preconditions:
key_type
should be constructible from key
of type K
.mapped_type
should be constructible from val
of type V
.The function applies RCU lock internally.
Returns true
if val
is inserted into the map, false
otherwise.
|
inline |
Inserts new node and initialize it by a functor.
This function inserts new node with key key
and if inserting is successful then it calls func
functor with signature
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.The user-defined functor is called only if inserting is successful.
The key_type should be constructible from value of type K
.
The function allows to split creating of new item into two part:
key
;func
functorThis can be useful if complete initialization of object of mapped_type
is heavyweight and it is preferable that the initialization should be completed only if inserting is successful.
The function applies RCU lock internally.
|
inline |
Returns item count in the map.
atomicity::empty_item_counter
in traits::item_counter
, the function always returns 0.
|
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 bAllowInsert
is true
. (note that in this case the key_type should be constructible from type K
). Otherwise, if key
is found, the functor func
is called with item found.
The functor Func
signature is:
with arguments:
bNew
- true
if the item has been inserted, false
otherwiseitem
- the item found or insertedThe functor may change any fields of the item.second
that is mapped_type
.
The function applies RCU lock internally.
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 the item with key
already exists.