cds
2.3.2
|
Michael's hash set, RCU specialization. More...
#include <cds/intrusive/michael_set_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
RCU schema. | |
typedef OrderedList | ordered_list |
type of ordered list used as a bucket implementation | |
typedef Traits | traits |
Set traits. | |
typedef ordered_list::value_type | value_type |
type of value stored in the list | |
typedef ordered_list::key_comparator | key_comparator |
key comparing functor | |
typedef ordered_list::disposer | disposer |
Node disposer functor. | |
typedef ordered_list::stat | stat |
Internal statistics. | |
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 |
typedef internal_bucket_type::exempt_ptr | exempt_ptr |
pointer to extracted node | |
typedef internal_bucket_type::raw_ptr | raw_ptr |
Return type of get() member function and its derivatives. | |
Public Member Functions | |
MichaelHashSet (size_t nMaxItemCount, size_t nLoadFactor) | |
Initialize hash set. More... | |
~MichaelHashSet () | |
Clear hash set and destroy it. | |
bool | insert (value_type &val) |
Inserts new node. More... | |
template<typename Func > | |
bool | insert (value_type &val, Func f) |
Inserts new node. More... | |
template<typename Func > | |
std::pair< bool, bool > | update (value_type &val, Func func, bool bAllowInsert=true) |
Updates the element. More... | |
bool | unlink (value_type &val) |
Unlinks the item val from the set. More... | |
template<typename Q > | |
bool | erase (Q const &key) |
Deletes the item 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 (const Q &key, Func f) |
Deletes the item from the set. More... | |
template<typename Q , typename Less , typename Func > | |
bool | erase_with (const Q &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 > | |
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 , typename Func > | |
bool | find (Q &key, Func f) |
Find 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 > | |
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 (non-atomic) More... | |
bool | empty () const |
Checks if the set is empty. More... | |
size_t | size () const |
Returns item count in the set. More... | |
size_t | bucket_count () const |
Returns the size of hash table. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
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. More... | |
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, RCU specialization.
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 bucket for hash set, for example, MichaelList, LazyList. The intrusive ordered list implementation specifies the type T
stored in the hash-set, the reclamation schema GC
used by hash-set, the comparison functor for the type T
and other features specific for the ordered list.Traits
- type traits, default is michael_set::traits
. Instead of defining Traits
struct you can use option-based syntax with michael_set::make_traits
metafunction.<cds/intrusive/michael_set_rcu.h>
you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files. For example, for general-purpose buffered RCU you should include: typedef michael_set::details::iterator< internal_bucket_type, true > cds::intrusive::MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >::const_iterator |
Const forward iterator.
For iterator's features and requirements see iterator
typedef michael_set::details::iterator< internal_bucket_type, false > cds::intrusive::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::intrusive::MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >::rcu_lock |
RCU scoped lock
|
inline |
Initialize hash set.
The Michael's hash set is an unbounded container, but its hash table is non-expandable. At construction time you should pass estimated maximum item count and a load factor. The load factor is average size of one bucket - a small number between 1 and 10. The bucket is an ordered single-linked list, the complexity of searching in the bucket is linear O(nLoadFactor)
. The constructor 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: average size of 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 for explanation.
|
inline |
Clears the set (non-atomic)
The function unlink all items from the set. 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 set may contain item(s). Therefore, clear
may be used only for debugging purposes.
For each item the disposer
is called after unlinking.
|
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 |
Checks if the set is empty.
atomicity::empty_item_counter
in traits::item_counter
, the function always returns true
.
|
inline |
|
inline |
Deletes the item from the set.
The function searches an item with key equal to key
in the set, unlinks it from the set, and returns true
. If the item with key equal to key
is not found the function return false
.
Note the hash functor should accept a parameter of type Q
that may be not the same as value_type
.
|
inline |
Deletes the item from the set.
The function searches an item with key equal to key
in the set, call f
functor with item found, and unlinks it from the set. The disposer specified in OrderedList
class template parameter is called by garbage collector GC
asynchronously.
The Func
interface is
If the item with key equal to key
is not found the function return false
.
Note the hash functor should accept a parameter of type Q
that can be not the same as value_type
.
|
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
. pred
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&) 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 |
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 returns an empty exempt_ptr
.
Depends on ordered_list
you should or should not lock RCU before calling of this function:
See ordered list implementation for details.
|
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 |
Find 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 can change non-key fields of item
. The functor does not serialize simultaneous access to the set 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 can be not the same as value_type
.
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
. pred
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 inserts val
in the set if it does not contain an item with key equal to val
.
Returns true
if val
is placed into the set, false
otherwise.
|
inline |
Inserts new node.
This function is intended for derived non-intrusive containers.
The function allows to split creating of new item into two part:
f
functor to initialize value-field of val
.The functor signature is:
where val
is the item inserted. The user-defined functor is called only if the inserting is success.
|
inline |
Returns item count in the set.
If you use atomicity::empty_item_counter
in traits::item_counter
, the function always returns 0.
|
inline |
Unlinks the item val
from the set.
The function searches the item val
in the set and unlink it from the set if it is found and is equal to val
.
The function returns true
if success and false
otherwise.
|
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
() function If new item has been inserted (i.e. bNew
is true
) then item
and val
arguments refers to the same thing.The functor may change non-key fields of the item
.
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.