cds
2.3.2
|
Michael's lock-free ordered single-linked list (template specialization for RCU) More...
#include <cds/intrusive/michael_list_rcu.h>
Public Types | |
typedef T | value_type |
type of value stored in the 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 |
disposer used | |
typedef get_node_traits< value_type, node_type, hook >::type | node_traits |
node traits | |
typedef michael_list::get_link_checker< node_type, traits::link_checker >::type | link_checker |
link checker | |
typedef cds::urcu::gc< RCU > | gc |
RCU schema. | |
typedef traits::back_off | back_off |
back-off strategy | |
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::rcu_check_deadlock | rcu_check_deadlock |
Deadlock checking policy. | |
typedef traits::stat | stat |
Internal statistics. | |
typedef gc::scoped_lock | rcu_lock |
RCU scoped lock. | |
using | exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, 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 | |
MichaelList () | |
Default constructor initializes empty list. | |
~MichaelList () | |
Destroy 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 bAllowInsert=true) |
Updates the item. More... | |
bool | unlink (value_type &val) |
Unlinks the item val from the list. More... | |
template<typename Q > | |
bool | erase (Q const &key) |
Deletes the item from the list. More... | |
template<typename Q , typename Less > | |
bool | erase_with (Q const &key, Less pred) |
Deletes the item from the list using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | erase (Q const &key, Func func) |
Deletes the item from the list. More... | |
template<typename Q , typename Less , typename Func > | |
bool | erase_with (Q const &key, Less pred, Func func) |
Deletes the item from the list using pred predicate for searching. More... | |
template<typename Q > | |
exempt_ptr | extract (Q const &key) |
Extracts an item from the list. More... | |
template<typename Q , typename Less > | |
exempt_ptr | extract_with (Q const &key, Less pred) |
Extracts an item from the list using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) |
Find the key val . 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 list contains key . More... | |
template<typename Q , typename Less > | |
bool | contains (Q const &key, Less pred) |
Checks whether the map 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... | |
void | clear () |
Clears the list using default disposer. More... | |
bool | empty () const |
Check if the list is empty. | |
size_t | size () const |
Returns list's item count. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
Static Public Attributes | |
static constexpr const bool | c_bExtractLockExternal = false |
Group of extract_xxx functions do not require external locking. | |
Protected Types | |
typedef node_type::marked_ptr | marked_node_ptr |
Marked node pointer. | |
typedef node_type::atomic_marked_ptr | atomic_node_ptr |
Atomic node pointer. | |
typedef atomic_node_ptr | auxiliary_head |
Auxiliary head type (for split-list support) | |
Protected Attributes | |
atomic_node_ptr | m_pHead |
Head pointer. | |
item_counter | m_ItemCounter |
Item counter. | |
stat | m_Stat |
Internal statistics. | |
Forward iterators (thread-safe only under RCU lock) | |
typedef iterator_type< false > | iterator |
Forward iterator. More... | |
typedef iterator_type< true > | const_iterator |
Const forward iterator. | |
iterator | begin () |
Returns a forward iterator addressing the first element in a list. More... | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a list. More... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a list. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first element in a list. | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a list. | |
const_iterator | cend () const |
Returns an const iterator that addresses the location succeeding the last element in a list. | |
Michael's lock-free ordered single-linked list (template specialization for RCU)
Usually, ordered single-linked list is used as a building block for the hash table implementation. The complexity of searching is O(N)
.
Template arguments:
RCU
- one of RCU typeT
- type to be stored in the list; the type T
should be based on (or has a member of type) cds::intrusive::micheal_list::nodeTraits
- type traits. See michael_list::traits
for explanation. It is possible to declare option-based list with cds::intrusive::michael_list::make_traits
metafunction, see here for explanations.<cds/intrusive/michael_list_rcu.h>
you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files. For example, for general-purpose buffered RCU you should include: typedef iterator_type<false> cds::intrusive::MichaelList< cds::urcu::gc< RCU >, T, Traits >::iterator |
Forward iterator.
You may safely use iterators in multi-threaded environment only under RCU lock. Otherwise, a crash is possible if another thread deletes the item the iterator points to.
|
inline |
|
inline |
Clears the list using default disposer.
The function clears the list using default (provided by Traits
class template argument) disposer functor.
RCU synchronize
method can be called. Note that depending on RCU type used the disposer invocation can be deferred.
The function can throw cds::urcu::rcu_deadlock
exception if a deadlock is encountered and deadlock checking policy is opt::v::rcu_throw_deadlock
.
|
inline |
Checks whether the list 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 map contains key
using pred
predicate for searching.
The function is an analog of 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 list.
|
inline |
Returns an iterator that addresses the location succeeding the last element in a list.
Do not use the value returned by end
function to access any item. Internally, end
returning value equals to nullptr
.
The returned value can be used only to control reaching the end of the list. For empty list
|
inline |
Deletes the item from the list.
The function searches an item with key equal to key
in the list, unlinks it from the list, and returns true
. If the item with the key equal to key
is not found the function return false
.
RCU synchronize
method can be called. Note that depending on RCU type used the disposer call can be deferred.
disposer
specified in Traits
is called for deleted item.
The function can throw cds::urcu::rcu_deadlock exception if a deadlock is detected and the deadlock checking policy is opt::v::rcu_throw_deadlock
.
|
inline |
Deletes the item from the list.
The function searches an item with key equal to key
in the list, call func
functor with item found, unlinks it from the list, and returns true
. The Func
interface is
If the item with the key equal to key
is not found the function return false
.
RCU synchronize
method can be called. Note that depending on RCU type used the disposer call can be deferred.
disposer
specified in Traits
is called for deleted item.
The function can throw cds::urcu::rcu_deadlock exception if a deadlock is detected and the deadlock checking policy is opt::v::rcu_throw_deadlock
.
|
inline |
Deletes the item from the list 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
. pred
must imply the same element order as the comparator used for building the list.
disposer
specified in Traits
is called for deleted item.
|
inline |
Deletes the item from the list 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
. pred
must imply the same element order as the comparator used for building the list.
disposer
specified in Traits
is called for deleted item.
|
inline |
Extracts an item from the list.
The function searches an item with key equal to key
in the list, unlinks it from the list, and returns exempt_ptr pointer to the item found. If key
is not found the function returns an empty exempt_ptr
.
|
inline |
Extracts an item from the list using pred
predicate for searching.
This function is the analog for extract(Q const&)
The pred
is a predicate used for key comparing. Less
has the interface like std::less
. pred
must imply the same element order as key_comparator.
|
inline |
Find the key val
.
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
. The function find
does not serialize simultaneous access to the list item
. If such access is possible you must provide your own synchronization schema to exclude unsafe item modifications.
The function makes RCU lock internally.
The function returns true
if val
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
. pred
must imply the same element order as the comparator used for building the list.
|
inline |
Finds key
and return the item found.
The function searches the item with key equal to key
and returns the pointer to item found. If key
is not found it returns empty raw_ptr
object.
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 list.
|
inline |
Inserts new node.
The function inserts val
in the list if the list does not contain an item with key equal to val
.
The function makes RCU lock internally.
Returns true
if val
is linked into the list, false
otherwise.
|
inline |
Inserts new node.
This function is intended for derived non-intrusive containers.
The function allows to split new item creating 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 list's item by concurrent threads. The user-defined functor is called only if the inserting is success.
The function makes RCU lock internally.
|
inline |
Returns list's item count.
The value returned depends on item counter provided by Traits
. For atomicity::empty_item_counter
, this function always returns 0.
empty()
method.
|
inline |
Unlinks the item val
from the list.
The function searches the item val
in the list and unlink it from the list if it is found and it 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 list, i.e. the pointer to the item found is equal to &val
.
The function returns true
if success and false
otherwise.
RCU synchronize
method can be called. Note that depending on RCU type used the disposer call can be deferred.
disposer
specified in Traits
is called for unlinked item.
The function can throw cds::urcu::rcu_deadlock exception if deadlock is encountered and deadlock checking policy is opt::v::rcu_throw_deadlock.
|
inline |
Updates the item.
The operation performs inserting or changing data with lock-free manner.
If the item val
not found in the list, then val
is inserted into the list iff bAllowInsert
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 listval
- 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 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, second
is true
if new item has been added or false
if the item with key
already is in the list.
The function makes RCU lock internally.