cds
2.3.2
|
Lock-free skip-list set (template specialization for RCU) More...
#include <cds/container/skip_list_set_rcu.h>
Public Types | |
typedef base_class::gc | gc |
Garbage collector used. | |
typedef T | value_type |
Value type stored in the set. | |
typedef Traits | traits |
Options specified. | |
typedef base_class::back_off | back_off |
Back-off strategy used. | |
typedef traits::allocator | allocator_type |
Allocator type used for allocate/deallocate the skip-list nodes. | |
typedef base_class::item_counter | item_counter |
Item counting policy used. | |
typedef maker::key_comparator | key_comparator |
key compare functor | |
typedef base_class::memory_model | memory_model |
Memory ordering. See cds::opt::memory_model option. | |
typedef traits::random_level_generator | random_level_generator |
random level generator | |
typedef traits::stat | stat |
internal statistics type | |
typedef traits::rcu_check_deadlock | rcu_check_deadlock |
Deadlock checking policy. | |
typedef base_class::rcu_lock | rcu_lock |
using | exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer > |
pointer to extracted node | |
typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > | raw_ptr |
Result of get() , get_with() functions - pointer to the node found. | |
Public Member Functions | |
SkipListSet () | |
Default ctor. | |
~SkipListSet () | |
Destructor destroys the set object. | |
template<typename Q > | |
bool | insert (Q const &val) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
bool | insert (Q const &val, Func f) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
std::pair< bool, bool > | update (const Q &val, Func func, bool bInsert=true) |
Updates the item. More... | |
template<typename... Args> | |
bool | emplace (Args &&... args) |
Inserts data of type value_type constructed with std::forward<Args>(args)... More... | |
template<typename Q > | |
bool | erase (Q const &key) |
Delete 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) |
Delete 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 the item from the set with specified key . More... | |
template<typename Q , typename Less > | |
exempt_ptr | extract_with (Q const &key, Less pred) |
Extracts the item from the set with comparing functor pred . More... | |
exempt_ptr | extract_min () |
Extracts an item with minimal key from the set. More... | |
exempt_ptr | extract_max () |
Extracts an item with maximal key from the set. More... | |
template<typename Q , typename Func > | |
bool | find (Q &val, Func f) |
Find the key val . More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &val, Less pred, Func f) |
Finds the key val 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 key and return the item found. More... | |
template<typename Q , typename Less > | |
raw_ptr | get_with (Q const &val, Less pred) |
Finds the key val and return the item found. More... | |
void | clear () |
Clears the set (non-atomic). More... | |
bool | empty () const |
Checks if the set is empty. | |
size_t | size () const |
Returns item count in the set. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
Static Public Attributes | |
static constexpr const bool | c_bExtractLockExternal = base_class::c_bExtractLockExternal |
Group of extract_xxx functions do not require external locking. | |
Forward ordered iterators (thread-safe under RCU lock) | |
typedef skip_list::details::iterator< typename base_class::iterator > | iterator |
Forward iterator. More... | |
typedef skip_list::details::iterator< typename base_class::const_iterator > | const_iterator |
Const iterator type. | |
iterator | begin () |
Returns a forward iterator addressing the first element in a set. | |
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. | |
iterator | end () |
Returns a forward iterator that addresses the location succeeding the last element in a set. | |
const_iterator | end () const |
Returns a forward const iterator that addresses the location succeeding the last element in a set. | |
const_iterator | cend () const |
Returns a forward const iterator that addresses the location succeeding the last element in a set. | |
Additional Inherited Members | |
Protected Types inherited from cds::intrusive::SkipListSet< cds::urcu::gc< RCU >, T, Traits > | |
typedef node_type::atomic_marked_ptr | atomic_node_ptr |
Atomic marked node pointer. | |
typedef node_type::marked_ptr | marked_node_ptr |
Node marked pointer. | |
typedef cds::urcu::gc< RCU > | gc |
Garbage collector. | |
typedef T | value_type |
type of value stored in the skip-list | |
typedef Traits | traits |
Traits template parameter. | |
typedef traits::hook | hook |
hook type | |
typedef hook::node_type | node_type |
node type | |
typedef implementation_defined | key_comparator |
key comparison functor based on Traits::compare and Traits::less | |
typedef traits::disposer | disposer |
disposer | |
typedef get_node_traits< value_type, node_type, hook >::type | node_traits |
node traits | |
typedef traits::item_counter | item_counter |
Item counting policy used. | |
typedef traits::memory_model | memory_model |
Memory ordering, see cds::opt::memory_model option. | |
typedef traits::random_level_generator | random_level_generator |
random level generator | |
typedef traits::allocator | allocator_type |
allocator for maintaining array of next pointers of the node | |
typedef traits::back_off | back_off |
Back-off strategy. | |
typedef traits::stat | stat |
internal statistics type | |
typedef traits::rcu_check_deadlock | rcu_check_deadlock |
Deadlock checking policy. | |
typedef gc::scoped_lock | rcu_lock |
RCU scoped lock. | |
using | exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, node_disposer, void > |
pointer to extracted node | |
typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > | raw_ptr |
Result of get() , get_with() functions - pointer to the node found. | |
typedef skip_list::details::iterator< gc, node_traits, back_off, false > | iterator |
Forward iterator. More... | |
typedef skip_list::details::iterator< gc, node_traits, back_off, true > | const_iterator |
Const iterator type. | |
Protected Member Functions inherited from cds::intrusive::SkipListSet< cds::urcu::gc< RCU >, T, Traits > | |
SkipListSet () | |
Default constructor. | |
~SkipListSet () | |
Clears and destructs the skip-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 bInsert=true) |
Updates the node. More... | |
bool | unlink (value_type &val) |
Unlinks the item val from the set. More... | |
template<typename Q > | |
exempt_ptr | extract (Q const &key) |
Extracts the item from the set with specified key . More... | |
template<typename Q , typename Less > | |
exempt_ptr | extract_with (Q const &key, Less pred) |
Extracts the item from the set with comparing functor pred . More... | |
exempt_ptr | extract_min () |
Extracts an item with minimal key from the list. More... | |
exempt_ptr | extract_max () |
Extracts an item with maximal key from the list. More... | |
template<typename Q > | |
bool | erase (const Q &key) |
Deletes the item from the set. More... | |
template<typename Q , typename Less > | |
bool | erase_with (const Q &key, Less pred) |
Delete the item from the set with comparing functor pred . 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) |
Delete the item from the set with comparing functor pred . More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) |
Finds key . More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the key key with comparing functor pred . 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 key and return the item found. More... | |
template<typename Q , typename Less > | |
raw_ptr | get_with (Q const &key, Less pred) |
Finds key and return the item found. More... | |
size_t | size () const |
Returns item count in the set. More... | |
bool | empty () const |
Checks if the set is empty. | |
void | clear () |
Clears the set (not atomic) More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
iterator | begin () |
Returns a forward iterator addressing the first element in a set. | |
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. | |
iterator | end () |
Returns a forward iterator that addresses the location succeeding the last element in a set. | |
const_iterator | end () const |
Returns a forward const iterator that addresses the location succeeding the last element in a set. | |
const_iterator | cend () const |
Returns a forward const iterator that addresses the location succeeding the last element in a set. | |
Static Protected Member Functions inherited from cds::intrusive::SkipListSet< cds::urcu::gc< RCU >, T, Traits > | |
static constexpr unsigned int | max_height () noexcept |
Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32. | |
Protected Attributes inherited from cds::intrusive::SkipListSet< cds::urcu::gc< RCU >, T, Traits > | |
skip_list::details::head_node< node_type > | m_Head |
head tower (max height) | |
random_level_generator | m_RandomLevelGen |
random level generator instance | |
atomics::atomic< unsigned int > | m_nHeight |
estimated high level | |
atomics::atomic< node_type * > | m_pDeferredDelChain |
Deferred deleted node chain. | |
item_counter | m_ItemCounter |
item counter | |
stat | m_Stat |
internal statistics | |
Static Protected Attributes inherited from cds::intrusive::SkipListSet< cds::urcu::gc< RCU >, T, Traits > | |
static constexpr const bool | c_bExtractLockExternal = false |
Group of extract_xxx functions does not require external locking. | |
static unsigned int const | c_nMaxHeight |
Max node height. The actual node height should be in range [0 .. c_nMaxHeight) More... | |
Lock-free skip-list set (template specialization for RCU)
The implementation of well-known probabilistic data structure called skip-list invented by W.Pugh in his papers:
A skip-list is a probabilistic data structure that provides expected logarithmic time search without the need of rebalance. The skip-list is a collection of sorted linked list. Nodes are ordered by key. Each node is linked into a subset of the lists. Each list has a level, ranging from 0 to 32. The bottom-level list contains all the nodes, and each higher-level list is a sublist of the lower-level lists. Each node is created with a random top level (with a random height), and belongs to all lists up to that level. The probability that a node has the height 1 is 1/2. The probability that a node has the height N is 1/2 ** N (more precisely, the distribution depends on an random generator provided, but our generators have this property).
The lock-free variant of skip-list is implemented according to book
Template arguments:
RCU
- one of RCU type.T
- type to be stored in the list.Traits
- set traits, default is skip_list::traits for explanation.It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of Traits
template argument. Template argument list Options
of cds::container::skip_list::make_traits metafunction are:
std::less<T>
.skip_list::xor_shift
, skip_list::turbo
or user-provided one. See skip_list::random_level_generator
option description for explanation. Default is skip_list::turbo32
.<cds/container/skip_list_set_rcu.h>
you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files.Iterators
The class supports a forward iterator (iterator and const_iterator). The iteration is ordered.
You may iterate over skip-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 requirement of RCU lock during iterating means that deletion of the elements (i.e. erase) is not possible.
Example how to use skip-list set iterators:
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.
typedef skip_list::details::iterator< typename base_class::iterator > cds::container::SkipListSet< cds::urcu::gc< RCU >, T, Traits >::iterator |
Forward iterator.
The forward iterator 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 base_class::rcu_lock cds::container::SkipListSet< cds::urcu::gc< RCU >, T, Traits >::rcu_lock |
RCU scoped lock
|
inline |
Clears the set (non-atomic).
The function deletes all items from the set. The function is not atomic, thus, in multi-threaded environment with parallel insertions this sequence
the assertion could be raised.
For each item the disposer provided by Traits
template parameter will be called.
|
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.
The function applies RCU lock internally.
|
inline |
Checks whether the set 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 set.
|
inline |
Inserts data of type value_type constructed with std::forward<Args>(args)...
Returns true
if inserting successful, false
otherwise.
RCU synchronize
method can be called. RCU should not be locked.
|
inline |
|
inline |
Delete 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
See also: erase
|
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 the item from the set with specified key
.
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 is not found the function returns an empty exempt_ptr
Note the compare functor from Traits
class' template argument should accept a parameter of type Q
that can be not the same as value_type
.
RCU synchronize
method can be called. RCU should NOT be locked.
The function does not free the item found. The item will be implicitly freed when the returned object is destroyed or when its release()
member function is called.
|
inline |
Extracts an item with maximal key from the set.
The function searches an item with maximal key, unlinks it from the set, and returns exempt_ptr pointer to the item. If the skip-list is empty the function returns an empty exempt_ptr
.
RCU synchronize
method can be called. RCU should NOT be locked.
The function does not free the item found. The item will be implicitly freed when the returned object is destroyed or when its release()
member function is called.
|
inline |
Extracts an item with minimal key from the set.
The function searches an item with minimal key, unlinks it, and returns exempt_ptr pointer to the item. If the skip-list is empty the function returns an empty exempt_ptr
.
RCU synchronize
method can be called. RCU should NOT be locked.
The function does not free the item found. The item will be implicitly freed when the returned object is destroyed or when its release()
member function is called.
|
inline |
Extracts the item from the set with comparing functor pred
.
The function is an analog of extract(Q const&)
but pred
predicate is used for key comparing. Less
has the semantics like std::less
. pred
must imply the same element order as the comparator used for building the set.
|
inline |
Find the key val
.
The function searches the item with key equal to val
and calls the functor f
for item found. The interface of Func
functor is:
where item
is the item found, val
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 val
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 val
is found, false
otherwise.
|
inline |
Finds the key val
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 key
and return the item found.
The function searches the item with key equal to key
and returns a raw_ptr
object pointed to item found. If key
is not found it returns empty raw_ptr
.
Note the compare functor in Traits
class' template argument 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 val
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.
RCU synchronize
method can be called. RCU should not be locked.
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. 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.
RCU synchronize
method can be called. RCU should not be locked.
|
inline |
Returns item count in the set.
The value returned depends on item counter type provided by Traits
template parameter. If it is atomicity::empty_item_counter this function always returns 0. Therefore, the function is not suitable for checking the set emptiness, use empty member function for this purpose.
|
inline |
Updates the item.
The operation performs inserting or changing data with lock-free manner.
If val
not found in the set, then the new item created from val
is inserted into the set iff bInsert
is true
. Otherwise, the functor func
is called with the item found. The functor Func
signature:
where:
bNew
- true
if the item has been inserted, false
otherwiseitem
- an item of the setval
- argument val
passed into the update
() 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.
RCU synchronize
method can be called. RCU should not be locked.
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.