cds
2.3.2
|
Michael's hash set (template specialization for RCU) More...
#include <cds/container/michael_set_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
RCU used as garbage collector. | |
typedef OrderedList | ordered_list |
type of ordered list to be used as a bucket implementation | |
typedef Traits | traits |
Set traits. | |
typedef ordered_list::value_type | value_type |
type of value to be stored in the list | |
typedef ordered_list::key_comparator | key_comparator |
key comparing functor | |
typedef ordered_list::stat | stat |
Internal statistics. | |
typedef ordered_list::exempt_ptr | exempt_ptr |
pointer to extracted node | |
typedef ordered_list::raw_ptr | raw_ptr |
Return type of get() member function and its derivatives. | |
typedef cds::opt::v::hash_selector< typename traits::hash >::type | hash |
Hash functor for value_type and all its derivatives that you use. | |
typedef traits::item_counter | item_counter |
Item counter type. | |
typedef traits::allocator | allocator |
Bucket table allocator. | |
typedef ordered_list::rcu_lock | rcu_lock |
Public Member Functions | |
MichaelHashSet (size_t nMaxItemCount, size_t nLoadFactor) | |
Initialize hash set. More... | |
~MichaelHashSet () | |
Clears hash set and destroys it. | |
template<typename Q > | |
bool | insert (Q &&val) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
bool | insert (Q &&val, Func f) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
std::pair< bool, bool > | update (Q const &val, Func func, bool bAllowInsert=true) |
Updates the element. More... | |
template<typename... Args> | |
bool | emplace (Args &&... args) |
Inserts data of type value_type created from args . More... | |
template<typename Q > | |
bool | erase (Q const &key) |
Deletes key from the set. More... | |
template<typename Q , typename Less > | |
bool | erase_with (Q const &key, Less pred) |
Deletes the item from the set using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | erase (Q const &key, Func f) |
Deletes key from the set. More... | |
template<typename Q , typename Less , typename Func > | |
bool | erase_with (Q const &key, Less pred, Func f) |
Deletes the item from the set using pred predicate for searching. More... | |
template<typename Q > | |
exempt_ptr | extract (Q const &key) |
Extracts an item from the set. More... | |
template<typename Q , typename Less > | |
exempt_ptr | extract_with (Q const &key, Less pred) |
Extracts an item from the set using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) |
Finds the key key . More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the key key using pred predicate for searching. More... | |
template<typename Q > | |
bool | contains (Q const &key) |
Checks whether the set contains key . More... | |
template<typename Q , typename Less > | |
bool | contains (Q const &key, Less pred) |
Checks whether the set contains key using pred predicate for searching. More... | |
template<typename Q > | |
raw_ptr | get (Q const &key) |
Finds the key key and return the item found. More... | |
template<typename Q , typename Less > | |
raw_ptr | get_with (Q const &key, Less pred) |
Finds the key key and return the item found. More... | |
void | clear () |
Clears the set (not atomic) | |
bool | empty () const |
Checks if the set is empty. More... | |
size_t | size () const |
Returns item count in the set. 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 michael_set::details::iterator< internal_bucket_type, false > | iterator |
Forward iterator. More... | |
typedef michael_set::details::iterator< internal_bucket_type, true > | const_iterator |
Const forward iterator. | |
iterator | begin () |
Returns a forward iterator addressing the first element in a set. More... | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a set. More... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a set. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first element in a set. | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a set. | |
const_iterator | cend () const |
Returns an const iterator that addresses the location succeeding the last element in a set. | |
Michael's hash set (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 list implementation used as the bucket for hash set, for example, MichaelList. The ordered list implementation specifies the type T
stored in the hash-set, the comparison functor for the type T
and other features specific for the ordered list.Traits
- set traits, default is michael_set::traits. Instead of defining Traits
struct you may use option-based syntax with michael_set::make_traits metafunction.About hash functor see MichaelSet hash functor.
How to use
Suppose, we have the following type Foo
that we want to store in your MichaelHashSet
:
To use MichaelHashSet
for Foo
values, you should first choose suitable ordered list class that will be used as a bucket for the set. We will cds::urcu::general_buffered<> RCU type and MichaelList as a bucket type. You should include RCU-related header file (cds/urcu/general_buffered.h
in this example) before including cds/container/michael_set_rcu.h
. Also, for ordered list we should develop a comparator for our Foo
struct.
typedef michael_set::details::iterator< internal_bucket_type, false > cds::container::MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >::iterator |
Forward iterator.
The forward iterator for Michael's set 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:
typedef ordered_list::rcu_lock cds::container::MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >::rcu_lock |
RCU scoped lock
|
inline |
Initialize hash set.
The Michael's hash set 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)
].
The ctor defines hash table size as rounding nMaxItemCount / nLoadFactor
up to nearest power of two.
nMaxItemCount | estimation of max item count in the hash set |
nLoadFactor | load factor: estimation of max number of items in the bucket |
|
inline |
|
inline |
Returns the size of hash table.
Since MichaelHashSet
cannot dynamically extend the hash table size, the value returned is an constant depending on object initialization parameters; see MichaelHashSet::MichaelHashSet for explanation.
|
inline |
Checks whether the set contains key
.
The function searches the item with key equal to key
and returns true
if the key is found, and false
otherwise.
Note the hash functor specified for class Traits
template parameter should accept a parameter of type Q
that can be not the same as value_type
.
|
inline |
Checks whether the set 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 set.
|
inline |
Inserts data of type value_type
created from args
.
Returns true
if inserting successful, false
otherwise.
The function applies RCU lock internally.
|
inline |
Checks if the set is empty.
atomicity::empty_item_counter
in traits::item_counter
, the function always returns true
.
|
inline |
|
inline |
Deletes key
from the set.
Since the key of MichaelHashSet's item type value_type
is not explicitly specified, template parameter Q
defines the key type searching in the list. The set item comparator should be able to compare the type value_type
and the type Q
.
RCU synchronize
method can be called. RCU should not be locked.
Return true
if key is found and deleted, false
otherwise
|
inline |
Deletes key
from the set.
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:
Since the key of MichaelHashSet's value_type
is not explicitly specified, template parameter Q
defines the key type searching in the list. The list item comparator should be able to compare the type T
of list item and the type Q
.
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 set using pred
predicate for searching.
The function is an analog of erase(Q const&) 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 set.
|
inline |
Deletes the item from the set using pred
predicate for searching.
The function is an analog of erase(Q 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 set.
|
inline |
Extracts an item from the set.
The function searches an item with key equal to key
in the set, unlinks it from the set, and returns exempt_ptr pointer to the item found. If the item with the key equal to key
is not found the function return an empty exempt_ptr
.
The function just excludes the item from the set 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 set using pred
predicate for searching.
The function is an analog of extract(Q 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 set.
|
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, key
is the find
function argument.
The functor may change non-key fields of item
. 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 set's item
. If such access is possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
The key
argument is non-const since it can be used as f
functor destination i.e., the functor can modify both arguments.
Note the hash functor specified for class Traits
template parameter should accept a parameter of type Q
that may be not the same as value_type
.
The function applies RCU lock internally.
The function returns true
if key
is found, false
otherwise.
|
inline |
Finds the key key
using pred
predicate for searching.
The function is an analog of find(Q&, 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 set.
|
inline |
Finds the key 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 Q
that can be not the same as value_type
.
RCU should be locked before call of this function. Returned item is valid only while RCU is locked:
|
inline |
Finds the key key
and return the item found.
The function is an analog of get(Q const&) but pred
is used for comparing the keys.
Less
functor has the semantics like std::less
but should take arguments of type value_type and Q
in any order. pred
must imply the same element order as the comparator used for building the set.
|
inline |
Inserts new node.
The function creates a node with copy of val
value and then inserts the node created into the set.
The type Q
should contain as minimum the complete key for the node. The object of value_type should be constructible from a value of type Q
. In trivial case, Q
is equal to value_type.
The function applies RCU lock internally.
Returns true
if val
is inserted into the set, false
otherwise.
|
inline |
Inserts new node.
The function allows to split creating of new item into two part:
f
functor to initialize value-fields of val
.The functor signature is:
where val
is the item inserted. The user-defined functor is called only if the inserting is success.
The function applies RCU lock internally.
|
inline |
Returns item count in the set.
atomicity::empty_item_counter
in traits::item_counter
, the function always returns 0.
|
inline |
Updates the element.
The operation performs inserting or changing data with lock-free manner.
If the item val
not found in the set, then val
is inserted iff bAllowInsert
is true
. Otherwise, the functor func
is called with item found. The functor signature is:
with arguments:
bNew
- true
if the item has been inserted, false
otherwiseitem
- item of the setval
- argument val
passed into the update
() functionThe functor may change non-key fields of the item
.
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 is in the set.