cds
2.3.2
|
Lock-free skip-list set (template specialization for RCU) More...
#include <cds/intrusive/skip_list_rcu.h>
Public Types | |
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. | |
Public Member Functions | |
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. | |
Static Public Member Functions | |
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. | |
Static Public Attributes | |
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... | |
Protected Types | |
typedef node_type::atomic_marked_ptr | atomic_node_ptr |
Atomic marked node pointer. | |
typedef node_type::marked_ptr | marked_node_ptr |
Node marked pointer. | |
Protected Attributes | |
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 | |
Forward iterators (thread-safe under RCU lock) | |
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. | |
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. | |
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 typeT
- type to be stored in the list. The type must be based on skip_list::node
(for skip_list::base_hook
) or it must have a member of type skip_list::node
(for skip_list::member_hook
).Traits
- set traits, default is skip_list::traits
It is possible to declare option-based list with cds::intrusive::skip_list::make_traits
metafunction instead of Traits
template argument.<cds/intrusive/skip_list_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.
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.
How to use
You should incorporate skip_list::node into your struct T
and provide appropriate skip_list::traits::hook in your Traits
template parameters. Usually, for Traits
you define a struct based on skip_list::traits
.
Example for cds::urcu::general_buffered<>
RCU and base hook:
Equivalent option-based code:
typedef skip_list::details::iterator< gc, node_traits, back_off, false > cds::intrusive::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.
|
inline |
Clears the set (not atomic)
The function unlink 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
will be called automatically after unlinking.
|
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 |
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 can be not the same as value_type
.
RCU synchronize
method can be called. RCU should not be locked.
|
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 in Traits
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
.
RCU synchronize
method can be called. RCU should not be locked.
|
inline |
Delete the item from the set with comparing functor pred
.
The function is an analog of erase(Q const&) but pred
predicate is used for key comparing. Less
has the interface like std::less
. pred
must imply the same element order as the comparator used for building the set.
|
inline |
Delete the item from the set with comparing functor pred
.
The function is an analog of erase(Q const&, Func) but pred
predicate is used for key comparing. Less
has the interface like std::less
. pred
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 with key equal to key
is not found the function returns an empty exempt_ptr
.
Note the compare functor 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 call the disposer for the item found. The disposer will be implicitly invoked when the returned object is destroyed or when its release()
member function is called. Example:
|
inline |
Extracts an item with maximal key from the list.
The function searches an item with maximal 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 call the disposer for the item found. The disposer will be implicitly invoked when the returned object is destroyed or when its release()
member function is manually called. Example:
|
inline |
Extracts an item with minimal key from the list.
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 call the disposer for the item found. The disposer will be implicitly invoked when the returned object is destroyed or when its release()
member function is manually called. Example:
|
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 interface like std::less
. pred
must imply the same element order as the comparator used for building the set.
|
inline |
Finds 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.
The function applies RCU lock internally.
The function returns true
if key
is found, false
otherwise.
|
inline |
Finds the key key
with comparing functor pred
.
The function is an analog of find(Q&, Func) but cmp
is used for key comparison. Less
functor has the interface like std::less
. cmp
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 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 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 applies 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. 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. For atomicity::empty_item_counter
the function always returns 0. Therefore, the function is not suitable for checking the set emptiness, use empty()
member function for this purpose.
|
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
.
Difference between erase()
and unlink
() functions: erase()
finds a key and deletes the item found. unlink
() searches 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. RCU should not be locked.
The disposer specified in Traits
class template parameter is called by garbage collector GC
asynchronously.
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 into the set iff bInsert
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 refer to the same thing.The functor can 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, i.e. the node has been inserted or updated, second
is true
if new item has been added or false
if the item with key
already exists.
|
static |
Max node height. The actual node height should be in range [0 .. c_nMaxHeight)
The max height is specified by random level generator constant m_nUpperBound
but it should be no more than 32 (skip_list::c_nHeightLimit).