cds
2.3.2
|
Split-ordered list RCU specialization. More...
#include <cds/intrusive/split_list_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
RCU garbage collector. | |
typedef Traits | traits |
Traits template parameters. | |
typedef cds::opt::v::hash_selector< typename traits::hash >::type | hash |
Hash functor for value_type and all its derivatives that you use. | |
typedef OrderedList | ordered_list |
type of ordered list used as base for split-list | |
typedef ordered_list::value_type | value_type |
type of value stored in the split-list | |
typedef ordered_list::key_comparator | key_comparator |
key compare functor | |
typedef ordered_list::disposer | disposer |
Node disposer functor. | |
typedef ordered_list::rcu_lock | rcu_lock |
RCU scoped lock. | |
typedef ordered_list::exempt_ptr | exempt_ptr |
pointer to extracted node | |
typedef ordered_list::raw_ptr | raw_ptr |
typedef traits::bit_reversal | bit_reversal |
Bit reversal algorithm, see split_list::traits::bit_reversal . | |
typedef traits::item_counter | item_counter |
Item counter type. | |
typedef traits::back_off | back_off |
back-off strategy for spinning | |
typedef traits::memory_model | memory_model |
Memory ordering. See cds::opt::memory_model option. | |
typedef traits::stat | stat |
Internal statistics. | |
Public Member Functions | |
SplitListSet () | |
Initialize split-ordered list of default capacity. More... | |
SplitListSet (size_t nItemCount, size_t nLoadFactor=1) | |
Initialize split-ordered list. More... | |
~SplitListSet () | |
Destroys split-list. | |
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 node. 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 for searching. More... | |
template<typename Q , typename Func > | |
bool | erase (Q const &key, Func f) |
Deletes the item 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 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 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 with pred predicate for comparing. 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... | |
size_t | size () const |
Returns item count in the set. | |
bool | empty () const |
Checks if the set is empty. More... | |
void | clear () |
Clears the set (not atomic) | |
stat const & | statistics () const |
Returns internal statistics. | |
OrderedList::stat const & | list_statistics () const |
Returns internal statistics for OrderedList . | |
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. More... | |
iterator | begin () |
Returns a forward iterator addressing the first element in a split-list. More... | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a split-list. More... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a split-list. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first element in a split-list. | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a split-list. | |
const_iterator | cend () const |
Returns an const iterator that addresses the location succeeding the last element in a split-list. | |
Split-ordered list RCU specialization.
Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
The split-ordered list is a lock-free implementation of an extensible unbounded hash table. It uses original recursive split-ordering algorithm discovered by Ori Shalev and Nir Shavit that allows to split buckets without moving an item on resizing, see short algo description.
Implementation
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 comparing functor for the type T
and other features specific for the ordered list.Traits
- set traits, default isd split_list::traits
. Instead of defining Traits
struct you can use option-based syntax provided by split_list::make_traits
metafunction.<cds/intrusive/split_list_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 and MichaelList-based split-list you should include: typedef iterator_type<true> cds::intrusive::SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >::const_iterator |
Const forward iterator.
For iterator's features and requirements see iterator
typedef iterator_type<false> cds::intrusive::SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >::iterator |
Forward iterator.
The forward iterator for a split-list has some features:
OrderedList
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.
typedef ordered_list::raw_ptr cds::intrusive::SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >::raw_ptr |
pointer to the node for get()
function
|
inline |
Initialize split-ordered list of default capacity.
The default capacity is defined in bucket table constructor. See split_list::expandable_bucket_table, split_list::static_ducket_table which selects by split_list::dynamic_bucket_table option.
|
inline |
Initialize split-ordered list.
nItemCount | estimate average of item count |
nLoadFactor | load factor - average item count per bucket. Small integer up to 8, default is 1. |
|
inline |
|
inline |
Checks whether the set contains key
.
The function searches the item with key equal to key
and returns true
if it 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
. Otherwise, you may use contains( Q const&, Less pred )
functions with explicit predicate for key comparing.
|
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 list.
|
inline |
Checks if the set is empty.
Emptiness is checked by item counting: if item count is zero then the set is empty. Thus, the correct item counting feature is an important part of split-list set implementation.
|
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
.
Difference between erase and unlink
functions: erase
finds a key and deletes the item found. unlink
finds an item by key and deletes it only if key
is an item of that set, i.e. the pointer to item found is equal to &key
.
RCU synchronize
method can be called, therefore, RCU should not be locked.
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.
The function searches an item with key equal to key
in the set, call f
functor with item found, unlinks it from the set, and returns true
. The disposer specified by 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
.
RCU synchronize
method can be called, therefore, RCU should not be locked.
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
for searching.
The function is an analog of erase(Q const&) but cmp
is used for key compare. Less
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
for searching.
The function is an analog of erase(Q const&, Func) but cmp
is used for key compare. Less
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, 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 bucket_type
you should or should not lock RCU before calling of this function:
|
inline |
Extracts an item from the set using pred
for searching.
The function is an analog of extract(Q const&)
but pred
is used for key compare. 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 can 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 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 applies RCU lock internally.
The function returns true
if key
is found, false
otherwise.
|
inline |
Finds the key key
with pred
predicate for comparing.
The function is an analog of find(Q&, Func) but cmp
is used for key compare. Less
has the interface like std::less
. cmp
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 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
.
The function makes RCU lock internally.
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 function makes RCU lock internally.
|
inline |
Unlinks the item val
from the set.
The function searches the item val
in the set and unlinks it from the set if it is found and is equal to val
.
Difference between erase and unlink
functions: erase
finds a key and deletes the item found. unlink
finds an item by key and deletes it only if val
is an item of that set, i.e. the pointer to item found is equal to &val
.
RCU synchronize
method can be called, therefore, RCU should not be locked.
The function returns true
if success and false
otherwise.
|
inline |
Updates the node.
The operation performs inserting or changing data with lock-free manner.
If the item val
is 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 stuff.The 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 list.