cds
2.3.2
|
Lock-free skip-list set (template specialization for gc::nogc) More...
#include <cds/intrusive/skip_list_nogc.h>
Public Types | |
typedef cds::gc::nogc | gc |
No garbage collector is used. | |
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 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 traits::disposer | disposer |
disposer | |
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 > | |
std::pair< bool, bool > | update (value_type &val, Func func, bool bInsert=true) |
Updates the node. More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) const |
Finds key . More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &key, Less pred, Func f) const |
Finds the key key using pred predicate for comparing. More... | |
template<typename Q > | |
value_type * | contains (Q const &key) const |
Checks whether the set contains key . More... | |
template<typename Q , typename Less > | |
value_type * | contains (Q const &key, Less pred) const |
Checks whether the set contains key using pred predicate for searching. More... | |
value_type * | get_min () const |
Gets minimum key from the set. More... | |
value_type * | get_max () const |
Gets maximum key from the set. More... | |
void | clear () |
Clears the set (non-atomic) More... | |
size_t | size () const |
Returns item count in the set. More... | |
bool | empty () const |
Checks if the set is empty. | |
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... | |
Protected Types | |
typedef node_type::atomic_ptr | atomic_node_ptr |
Atomic node pointer. | |
Protected Attributes | |
head_node | m_Head |
head tower (max height) | |
random_level_generator | m_RandomLevelGen |
random level generator instance | |
atomics::atomic< unsigned int > | m_nHeight |
estimated high level | |
item_counter | m_ItemCounter |
item counter | |
stat | m_Stat |
internal statistics | |
Forward iterators | |
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 gc::nogc)
This specialization is so-called append-only when no item reclamation may be performed. The class does not support deleting of list item.
See SkipListSet for description of skip-list.
Template arguments :
T
- type to be stored in the set. 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
- type 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.Iterators
The class supports a forward iterator (iterator and const_iterator). The iteration is ordered.
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 base hook:
Equivalent option-based code:
typedef skip_list::details::iterator< gc, node_traits, back_off, false > cds::intrusive::SkipListSet< cds::gc::nogc, T, Traits >::iterator |
Forward iterator.
The forward iterator for a split-list has some features:
OrderedList
|
inline |
Default constructor.
The constructor checks whether the count of guards is enough for skip-list and may raise an exception if not.
|
inline |
Clears the set (non-atomic)
The function is not atomic. Finding and/or inserting is prohibited while clearing. Otherwise an unpredictable result may be encountered. Thus, clear()
may be used only for debugging purposes.
|
inline |
Checks whether the set contains key
.
The function searches the item with key equal to key
and returns pointer to item found or nullptr
.
|
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 |
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.
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 returns true
if key
is found, false
otherwise.
|
inline |
Finds the key key
using pred
predicate for comparing.
The function is an analog of find(Q&, Func) but pred
predicate is used for key compare. Less
has the interface like std::less
. pred
must imply the same element order as the comparator used for building the set.
|
inline |
Gets maximum key from the set.
The function returns nullptr
if the set is empty
|
inline |
Gets minimum key from the set.
If the set is empty the function returns nullptr
|
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 |
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. The function is not suitable for checking the set emptiness, use empty()
.
|
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.
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.
|
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
).