cds
2.3.2
|
Split-ordered list set (template specialization for RCU) More...
#include <cds/container/split_list_set_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
RCU-based garbage collector. | |
typedef T | value_type |
Type of value to be storedin the set. | |
typedef Traits | traits |
Traits template argument | |
typedef maker::ordered_list | ordered_list |
Underlying ordered list class. | |
typedef base_class::key_comparator | key_comparator |
key compare functor | |
typedef base_class::hash | hash |
Hash functor for value_type and all its derivatives that you use. | |
typedef base_class::item_counter | item_counter |
Item counter type. | |
typedef base_class::stat | stat |
Internal statistics. | |
typedef base_class::rcu_lock | rcu_lock |
using | exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::ordered_list_traits::disposer > |
pointer to extracted node | |
typedef implementation_defined | raw_ptr |
pointer to the node for get() function More... | |
Public Member Functions | |
SplitListSet () | |
Initializes split-ordered list of default capacity. More... | |
SplitListSet (size_t nItemCount, size_t nLoadFactor=1) | |
Initializes split-ordered list. More... | |
template<typename Q > | |
bool | insert (Q const &val) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
bool | insert (Q const &key, Func f) |
Inserts new node. More... | |
template<typename... Args> | |
bool | emplace (Args &&... args) |
Inserts data of type value_type created from args . More... | |
template<typename Q , typename Func > | |
std::pair< bool, bool > | update (Q const &val, Func func, bool bAllowInsert=true) |
Updates an element with given val . 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 map 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. | |
stat const & | statistics () const |
Returns internal statistics. | |
ordered_list::stat const & | list_statistics () const |
Returns internal statistics for ordered_list . | |
Static Public Attributes | |
static constexpr const bool | c_bExtractLockExternal = base_class::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 |
Forward const 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. | |
Additional Inherited Members | |
Protected Types inherited from cds::intrusive::SplitListSet< cds::urcu::gc< RCU >, T, Traits::ordered_list, Traits > | |
typedef cds::urcu::gc< RCU > | gc |
Garbage collector. | |
typedef Traits | traits |
Set traits. | |
typedef T | ordered_list |
type of ordered list used as a 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 comparison functor | |
typedef ordered_list::disposer | disposer |
Node disposer functor. | |
typedef cds::opt::v::hash_selector< typename traits::hash >::type | hash |
Hash functor for value_type and all its derivatives you use. | |
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, see spit_list::stat . | |
typedef ordered_list::guarded_ptr | guarded_ptr |
Guarded pointer. | |
typedef iterator_type< false > | iterator |
Forward iterator. More... | |
typedef iterator_type< true > | const_iterator |
Const forward iterator. More... | |
Protected Member Functions inherited from cds::intrusive::SplitListSet< cds::urcu::gc< RCU >, T, Traits::ordered_list, Traits > | |
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 set. | |
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, Func func, bool bAllowInsert=true) |
Updates the node. More... | |
std::pair< bool, bool > | upsert (value_type &val, bool bAllowInsert=true) |
Inserts or updates the node (only for IterableList ) More... | |
bool | unlink (value_type &val) |
Unlinks the item val from the set. More... | |
bool | erase (Q const &key) |
Deletes the item from the set. More... | |
bool | erase (Q const &key, Func f) |
Deletes the item from the set. More... | |
bool | erase_with (const Q &key, Less pred) |
Deletes the item from the set with comparing functor pred . More... | |
bool | erase_with (Q const &key, Less pred, Func f) |
Deletes the item from the set with comparing functor pred . More... | |
bool | erase_at (iterator const &iter) |
Deletes the item pointed by iterator iter (only for IterableList based set) More... | |
guarded_ptr | extract (Q const &key) |
Extracts the item with specified key . More... | |
guarded_ptr | extract_with (Q const &key, Less pred) |
Extracts the item using compare functor pred . More... | |
bool | find (Q &key, Func f) |
Finds the key key . More... | |
iterator | find (Q &key) |
Finds key and returns iterator pointed to the item found (only for IterableList ) More... | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the key key with pred predicate for comparing. More... | |
iterator | find_with (Q &key, Less pred) |
Finds key using pred predicate and returns iterator pointed to the item found (only for IterableList ) More... | |
bool | contains (Q const &key) |
Checks whether the set contains key . More... | |
bool | contains (Q const &key, Less pred) |
Checks whether the set contains key using pred predicate for searching. More... | |
guarded_ptr | get (Q const &key) |
Finds the key key and return the item found. More... | |
guarded_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 (non-atomic) More... | |
stat const & | statistics () const |
Returns internal statistics. | |
T ::stat const & | list_statistics () const |
Returns internal statistics for OrderedList . | |
iterator | begin () |
Returns a forward iterator addressing the first element in a split-list. More... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a split-list. | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a split-list. More... | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a split-list. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first 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. | |
Static Protected Attributes inherited from cds::intrusive::SplitListSet< cds::urcu::gc< RCU >, T, Traits::ordered_list, Traits > | |
static constexpr const size_t | c_nHazardPtrCount |
Count of hazard pointer required. | |
Split-ordered list set (template specialization for RCU)
Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
See intrusive::SplitListSet
for a brief description of the split-list algorithm.
Template parameters:
RCU
- one of RCU typeT
- type of the value to be stored in the split-list.Traits
- type traits, default is split_list::traits
. Instead of declaring split_list::traits
-based struct you can apply option-based notation with split_list::make_traits
metafunction.Iterators
The class supports a forward iterator (iterator and const_iterator). The iteration is unordered.
You may iterate over split-list set items only under RCU lock. Only in this case the iterator is thread-safe since while RCU is locked any set's item cannot be reclaimed.
The iterator class supports the following minimalistic interface:
Note, the iterator object returned by end()
, cend()
member functions points to nullptr
and should not be dereferenced.
You should decide what garbage collector you want, and what ordered list you want to use. Split-ordered list is an original data structure based on an ordered list. Suppose, you want construct split-list set based on cds::urcu::general_buffered<>
GC and LazyList
as ordered list implementation. So, you beginning your program with following include:
The inclusion order is important:
cds/urcu/general_buffered.h
in our case)cds/container/lazy_list_rcu.h
),cds/container/split_list_set_rcu.h
.Now, you should declare traits for split-list set. The main parts of traits are a hash functor for the set and a comparing functor for ordered list. Note that we define several function in foo_hash
and foo_less
functors for different argument types since we want call our SplitListSet
object by the key of type int
and by the value of type foo
.
The second attention: instead of using LazyList
in SplitListSet
traits we use cds::contaner::lazy_list_tag
tag for the lazy list. The split-list requires significant support from underlying ordered list class and it is not good idea to dive you into deep implementation details of split-list and ordered list interrelations. The tag paradigm simplifies split-list interface.
Now you are ready to declare our set class based on SplitListSet
:
You may use the modern option-based declaration instead of classic type-traits-based one:
In case of option-based declaration using split_list::make_traits
metafunction the struct foo_set_traits
is not required.
Now, the set of type foo_set
is ready to use in your program.
Note that in this example we show only mandatory traits
parts, optional ones is the default and they are inherited from container::split_list::traits
. There are many other options for deep tuning of the split-list and ordered-list containers.
typedef iterator_type<false> cds::container::SplitListSet< cds::urcu::gc< RCU >, T, 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 implementation_defined cds::container::SplitListSet< cds::urcu::gc< RCU >, T, Traits >::raw_ptr |
pointer to the node for get()
function
For LazyList
, raw_ptr
is just pointer to value_type
.
For MichaelList
, raw_ptr
is cds::urcu::raw_ptr
object giving access to value_type
.
typedef base_class::rcu_lock cds::container::SplitListSet< cds::urcu::gc< RCU >, T, Traits >::rcu_lock |
RCU scoped lock
|
inline |
Initializes split-ordered list of default capacity.
The default capacity is defined in bucket table constructor. See intrusive::split_list::expandable_bucket_table
, intrusive::split_list::static_bucket_table
which selects by container::split_list::dynamic_bucket_table
option.
|
inline |
Initializes split-ordered list.
nItemCount | estimated 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.
The function applies RCU lock internally.
|
inline |
Checks whether the map contains key
using pred
predicate for searching.
The function is similar to 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 |
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.
Emptiness is checked by item counting: if item count is zero then assume that the set is empty. Thus, the correct item counting feature is an important part of split-list set implementation.
|
inline |
|
inline |
Deletes key
from the set.
Template parameter of type Q
defines the key type searching in the list. The set item comparator should be able to compare the values of 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:
Template parameter of type Q
defines the key type searching in the list. The list item comparator should be able to compare the values of 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 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 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
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.
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 makes 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 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-field of val
.The functor signature is:
where val
is the item inserted. User-defined functor f
should guarantee that during changing val
no any other changes could be made on this set's item by concurrent threads. The user-defined functor is called only if the inserting is success.
The function applies RCU lock internally.
|
inline |
Updates an element with given val
.
The operation performs inserting or changing data with lock-free manner.
If the val
key not found in the set, then the new item created from val
is inserted into the set. Otherwise, the functor func
is called with the item found. The functor Func
signature is:
with arguments:
bNew
- true
if the item has been inserted, false
otherwiseitem
- item of the setval
- argument val
passed into the ensure
() functionThe functor may change non-key fields of the item
; however, func
must guarantee that during changing no any other modifications could be made on this item by concurrent threads.
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.Updates the node The operation performs inserting or changing data with lock-free manner.
If key
is not found in the set, then key
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 map.