cds
2.3.2
|
Michael's lock-free ordered single-linked list (template specialization for gc::nogc) More...
#include <cds/intrusive/michael_list_nogc.h>
Public Types | |
typedef gc::nogc | gc |
Garbage collector. | |
typedef T | value_type |
type of value to be stored in the queue | |
typedef Traits | traits |
List traits. | |
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 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::stat | stat |
Internal statistics. | |
typedef iterator_type< false > | iterator |
Forward iterator. | |
typedef iterator_type< true > | const_iterator |
Const forward iterator. | |
Public Member Functions | |
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. | |
MichaelList () | |
Default constructor initializes empty list. | |
~MichaelList () | |
Destroys the list objects. | |
bool | insert (value_type &val) |
Inserts new node. More... | |
template<typename Func > | |
std::pair< bool, bool > | update (value_type &val, Func func, bool bAllowInsert=true) |
Updates the item. More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) |
Finds the key val . More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the key key using pred predicate for searching. More... | |
template<typename Q > | |
value_type * | contains (Q const &key) |
Checks whether the list contains key . More... | |
template<typename Q , typename Less > | |
value_type * | contains (Q const &key, Less pred) |
Checks whether the map contains key using pred predicate for searching. More... | |
template<typename Disposer > | |
void | clear (Disposer disp) |
Clears the list. More... | |
void | clear () |
Clears the list using default disposer. More... | |
bool | empty () const |
Checks 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. | |
Protected Types | |
typedef node_type::atomic_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. | |
Michael's lock-free ordered single-linked list (template specialization for gc::nogc)
This specialization is intended for so-called append-only usage when no item reclamation may be performed. The class does not support item removal.
See MichaelList for description of template parameters.
|
inline |
|
inline |
Clears the list.
The function unlink all items from the list.
For each unlinked item the item disposer disp
is called after unlinking.
|
inline |
Clears the list using default disposer.
The function clears the list using default (provided in class template) disposer functor.
|
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 |
Finds 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 returns true
if val
is found, false
otherwise.
|
inline |
Finds the key 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 |
Inserts new node.
The function inserts val
in the list if the list does not contain an item with key equal to val
.
Returns true
if val
is linked into the list, false
otherwise.
|
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 |
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.