cds
2.3.2
|
Lock-free skip-list set. More...
#include <cds/container/impl/skip_list_set.h>
Public Types | |
typedef GC | gc |
Garbage collector used. | |
typedef T | value_type |
typedef Traits | traits |
Options specified. | |
typedef base_class::back_off | back_off |
Back-off strategy. | |
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 comparison 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 gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set< node_type, value_type > > | guarded_ptr |
Guarded pointer. | |
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 created in-place from 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 > | |
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 set. More... | |
guarded_ptr | extract_max () |
Extracts an item with maximal key from the set. More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) |
Find the key . More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &key, Less pred, Func f) |
Finds 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 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... | |
void | clear () |
Clears the set (not 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 size_t const | c_nHazardPtrCount = base_class::c_nHazardPtrCount |
Count of hazard pointer required for the skip-list. | |
Forward iterators (only for debugging purpose) | |
typedef skip_list::details::iterator< typename base_class::iterator > | iterator |
Iterator type. 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< GC, 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 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. | |
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. | |
Protected Member Functions inherited from cds::intrusive::SkipListSet< GC, T, Traits > | |
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. | |
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< GC, 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. | |
Static Protected Attributes inherited from cds::intrusive::SkipListSet< GC, T, Traits > | |
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. | |
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.T
- type to be stored in the list.Traits
- set traits, default is skip_list::traits
. It is possible to declare option-based list with cds::container::skip_list::make_traits
metafunction istead of Traits
template argument.gc::HP
). Those GCs should be explicitly initialized with hazard pointer enough:SkipListSet
for each GC
. You should include:<cds/container/skip_list_set_hp.h>
for gc::HP
garbage collector<cds/container/skip_list_set_dhp.h>
for gc::DHP
garbage collector<cds/container/skip_list_set_rcu.h>
for RCU type<cds/container/skip_list_set_nogc.h>
for non-deletable SkipListSetIterators
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 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.
typedef skip_list::details::iterator< typename base_class::iterator > cds::container::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:
typedef T cds::container::SkipListSet< GC, T, Traits >::value_type |
|
inline |
Clears the set (not 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.
|
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
created in-place from std::forward<Args>(args)...
Returns true
if inserting successful, false
otherwise.
|
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 value_type
is not explicitly specified, template parameter Q
defines the key type to search in the list. The list item comparator should be able to compare the type T
of list item and the type Q
.
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 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
. 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 item extracted is freed automatically by garbage collector GC
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 set.
The function searches an item with maximal key, unlinks it, and returns the pointer to item found as guarded_ptr
. If the skip-list is empty the function returns an empty guarded pointer.
The item found is freed 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 an item with minimal key from the set.
The function searches an item with minimal key, unlinks it, and returns pointer to the item found as guarded_ptr
. If the skip-list is empty the function returns an empty guarded pointer.
The item extracted is freed automatically by garbage collector GC
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 |
Find the 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 may be not the same as value_type
.
The function returns true
if key
is found, false
otherwise.
|
inline |
Finds 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 key
and return the item found.
The function searches the item with key equal to key
and returns a guarded pointer to the item found. If key
is not found the function returns an empty guarded pointer.
It is safe when a concurrent thread erases the item returned in result
guarded pointer. In this case the item will be freed later by garbage collector GC
automatically when 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 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.
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.
|
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 the val
key not found in the set, then the new item created from val
will be inserted into the set iff bInsert
is true
. Otherwise, if val
is found, the functor func
will be called with the item found.
The functor Func
signature:
where:
bNew
- true
if the item has been inserted, false
otherwiseitem
- item of the setval
- argument key
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.
Returns std::pair<bool, bool>
where first
is true
if operation is successful, i.e. the item has been inserted or updated, second
is true
if new item has been added or false
if the item with key equal to val
already exists.