cds
2.3.2
|
Lock-free skip-list set. More...
#include <cds/intrusive/impl/skip_list.h>
Public Types | |
typedef GC | 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 opt::compare and opt::less option setter. | |
typedef traits::disposer | disposer |
item disposer | |
typedef get_node_traits< value_type, node_type, hook >::type | node_traits |
node traits | |
typedef traits::item_counter | item_counter |
Item counting policy. | |
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 gc::template guarded_ptr< value_type > | guarded_ptr |
Guarded pointer. | |
Public Member Functions | |
SkipListSet () | |
Default constructor. More... | |
~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 > | |
guarded_ptr | extract (Q const &key) |
Extracts the item from the set with specified key . More... | |
template<typename Q , typename Less > | |
guarded_ptr | extract_with (Q const &key, Less pred) |
Extracts the item from the set with comparing functor pred . More... | |
guarded_ptr | extract_min () |
Extracts an item with minimal key from the list. More... | |
guarded_ptr | extract_max () |
Extracts an item with maximal key from the list. 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 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) |
Deletes 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 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 > | |
guarded_ptr | get (Q const &key) |
Finds key and return the item found. More... | |
template<typename Q , typename Less > | |
guarded_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 unsigned int const | c_nMaxHeight |
Max node height. The actual node height should be in range [0 .. c_nMaxHeight) More... | |
static size_t const | c_nHazardPtrCount = c_nMaxHeight * 2 + 3 |
Count of hazard pointer required for the skip-list. | |
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. | |
Forward iterators (only for debugging purpose) | |
typedef skip_list::details::iterator< gc, node_traits, back_off, false > | iterator |
Iterator type. 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.
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:
GC
- Garbage collector used. Note the GC
must be the same as the GC used for item type T
, see skip_list::node
.T
- 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
- skip-list traits, default is skip_list::traits
. It is possible to declare option-based list with cds::intrusive::skip_list::make_traits
metafunction istead of Traits
template argument.gc::HP
). Those GCs should be explicitly initialized with hazard pointer enough:There are several specializations of SkipListSet
for each GC
. You should include:
<cds/intrusive/skip_list_hp.h>
for gc::HP
garbage collector<cds/intrusive/skip_list_dhp.h>
for gc::DHP
garbage collector<cds/intrusive/skip_list_nogc.h>
for cds_intrusive_SkipListSet_nogc for append-only set<cds/intrusive/skip_list_rcu.h>
for RCU typeIterators
The class supports a forward iterator (iterator and const_iterator). The iteration is ordered. The iterator object is thread-safe: the element pointed by the iterator object is guarded, so, the element cannot be reclaimed while the iterator object is alive. However, passing an iterator object between threads is dangerous.
Remember, each iterator object requires 2 additional hazard pointers, that may be a limited resource for GC
like as gc::HP
(for gc::DHP
the count of guards is unlimited).
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 gc::HP
and base hook:
Equivalent option-based code:
typedef skip_list::details::iterator< gc, node_traits, back_off, false > cds::intrusive::SkipListSet< GC, T, Traits >::iterator |
Iterator type.
The forward iterator has some features:
gc::HP
), a guard is a limited resource per thread, so an exception (or assertion) "no free guard" may be thrown if the limit of guard count per thread is exceeded.The iterator interface:
|
inline |
Default constructor.
The constructor checks whether the count of guards is enough for skip-list and may raise an exception if not.
|
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.
|
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 compare 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 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 compare functor should accept a parameter of type Q
that can be not the same as value_type
.
|
inline |
Deletes 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
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 |
Deletes 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
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 |
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 it as guarded_ptr
object. If key
is not found the function returns an empty guarded pointer.
Note the compare functor should accept a parameter of type Q
that can be not the same as value_type
.
The disposer
specified in Traits
class template parameter is called automatically by garbage collector GC
specified in class' template parameters when returned guarded_ptr
object will be destroyed or released.
guarded_ptr
object uses the GC's guard that can be limited resource.Usage:
|
inline |
Extracts an item with maximal key from the list.
The function searches an item with maximal key, unlinks it, and returns the pointer to item as guarded_ptr
object. If the skip-list is empty the function returns an empty guarded_ptr
.
The disposer
specified in Traits
class template parameter is called by garbage collector GC
asynchronously when returned guarded_ptr object will be destroyed or released.
guarded_ptr
object uses the GC's guard that can be limited resource.Usage:
|
inline |
Extracts an item with minimal key from the list.
The function searches an item with minimal key, unlinks it, and returns it as guarded_ptr
object. If the skip-list is empty the function returns an empty guarded pointer.
The disposer
specified in Traits
class template parameter is called by garbage collector GC
automatically when returned guarded_ptr
object will be destroyed or released.
guarded_ptr
object uses the GC's guard that can be limited resource.Usage:
|
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
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 |
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 on item level to exclude unsafe item modifications.
Note the compare 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
with pred
predicate for comparing.
The function is an analog of find(Q&, Func) but pred
is used for key compare.
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 |
Finds key
and return the item found.
The function searches the item with key equal to key
and returns the pointer to the item found as guarded_ptr
. If key
is not found the function returns an empt guarded pointer.
The disposer
specified in Traits
class template parameter is called by garbage collector GC
asynchronously when returned guarded_ptr object will be destroyed or released.
guarded_ptr
object uses one GC's guard which can be limited resource.Usage:
Note the compare functor specified for class Traits
template parameter should accept a parameter of type Q
that can be not the same as value_type
.
|
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
.
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.
|
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()
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
() 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
.
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 func
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.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
).