cds
2.3.2
|
Michael's ordered list. More...
#include <cds/container/impl/michael_list.h>
Public Types | |
typedef T | value_type |
Type of value stored in the list. | |
typedef Traits | traits |
List traits. | |
typedef base_class::gc | gc |
Garbage collector used. | |
typedef base_class::back_off | back_off |
Back-off strategy used. | |
typedef maker::allocator_type | allocator_type |
Allocator type used for allocate/deallocate the 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 base_class::stat | stat |
Internal statistics. | |
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 | |
MichaelList () | |
Default constructor. More... | |
~MichaelList () | |
List destructor. More... | |
template<typename Q > | |
bool | insert (Q &&val) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
bool | insert (Q &&key, Func func) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
std::pair< bool, bool > | update (Q const &key, Func func, bool bAllowInsert=true) |
Updates data by key . More... | |
template<typename... Args> | |
bool | emplace (Args &&... args) |
Inserts data of type value_type constructed with std::forward<Args>(args)... More... | |
template<typename Q > | |
bool | erase (Q const &key) |
Delete key 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 f) |
Deletes key from the list. More... | |
template<typename Q , typename Less , typename Func > | |
bool | erase_with (Q const &key, Less pred, Func f) |
Deletes the item from the list using pred predicate for searching. More... | |
template<typename Q > | |
guarded_ptr | extract (Q const &key) |
Extracts the item from the list with specified key . More... | |
template<typename Q , typename Less > | |
guarded_ptr | extract_with (Q const &key, Less pred) |
Extracts the item from the list with comparing functor pred . 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 list contains key using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) |
Finds key and perform an action with it. 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 > | |
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... | |
bool | empty () const |
Check if the list is empty. | |
size_t | size () const |
Returns list's item count. More... | |
void | clear () |
Clears the list. | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
Static Public Attributes | |
static constexpr const size_t | c_nHazardPtrCount = base_class::c_nHazardPtrCount |
Count of hazard pointer required for the algorithm. | |
Forward iterators (only for debugging purpose) | |
typedef iterator_type< false > | iterator |
Forward iterator. More... | |
typedef iterator_type< true > | const_iterator |
Const forward iterator. More... | |
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. | |
Additional Inherited Members | |
Protected Types inherited from cds::intrusive::MichaelList< GC, T, Traits > | |
typedef node_type::atomic_marked_ptr | atomic_node_ptr |
Atomic node pointer. | |
typedef node_type::marked_ptr | marked_node_ptr |
Node marked pointer. | |
typedef atomic_node_ptr | auxiliary_head |
Auxiliary head type (for split-list support) | |
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 traits::stat | stat |
Internal statistics. | |
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 GC | gc |
Garbage collector. | |
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 gc::template guarded_ptr< value_type > | guarded_ptr |
Guarded pointer. | |
typedef iterator_type< false > | iterator |
Forward iterator. More... | |
typedef iterator_type< true > | const_iterator |
Const forward iterator. More... | |
Protected Member Functions inherited from cds::intrusive::MichaelList< GC, T, Traits > | |
MichaelList () | |
Default constructor initializes empty list. | |
~MichaelList () | |
Destroys the list object. | |
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 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 f) |
Deletes the item from the list using pred predicate for searching. More... | |
template<typename Q > | |
guarded_ptr | extract (Q const &key) |
Extracts the item from the list with specified key . More... | |
template<typename Q , typename Less > | |
guarded_ptr | extract_with (Q const &key, Less pred) |
Extracts the item using compare functor pred . More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) |
Finds key in the list. More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the 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 list contains key using pred predicate for searching. More... | |
template<typename Q > | |
guarded_ptr | get (Q const &key) |
Finds the key and return the item found. More... | |
template<typename Q , typename Less > | |
guarded_ptr | get_with (Q const &key, Less pred) |
Finds the key and return the item found. More... | |
void | clear () |
Clears the list. More... | |
bool | empty () const |
Checks whether the list is empty. | |
size_t | size () const |
Returns list's item count. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
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 | cbegin () const |
Returns a forward const iterator addressing the first element in a list. | |
const_iterator | begin () 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. | |
Protected Attributes inherited from cds::intrusive::MichaelList< GC, T, Traits > | |
atomic_node_ptr | m_pHead |
Head pointer. | |
item_counter | m_ItemCounter |
Item counter. | |
stat | m_Stat |
Internal statistics. | |
Static Protected Attributes inherited from cds::intrusive::MichaelList< GC, T, Traits > | |
static constexpr const size_t | c_nHazardPtrCount = 4 |
Count of hazard pointer required for the algorithm. | |
Michael's ordered list.
Usually, ordered single-linked list is used as a building block for the hash table implementation. The complexity of searching is O(N)
, where N
is the item count in the list, not in the hash table.
Source:
This class is non-intrusive version of cds::intrusive::MichaelList class
Template arguments:
GC
- garbage collector usedT
- type stored in the list. The type must be default- and copy-constructible.Traits
- type traits, default is michael_list::traits
Unlike standard container, this implementation does not divide type T
into key and value part and may be used as a main building block for hash set algorithms. The key is a function (or a part) of type T
, and this function is specified by Traits::compare
functor or Traits::less
predicate
MichaelKVList is a key-value version of Michael's non-intrusive list that is closer to the C++ std library approach.
It is possible to declare option-based list with cds::container::michael_list::make_traits metafunction istead of Traits
template argument. For example, the following traits-based declaration of gc::HP Michael's list
is equivalent for the following option-based list
typedef iterator_type<true> cds::container::MichaelList< GC, T, Traits >::const_iterator |
Const forward iterator.
For iterator's features and requirements see iterator
typedef iterator_type<false> cds::container::MichaelList< GC, T, Traits >::iterator |
Forward iterator.
The forward iterator for Michael's list has some features:
gc::HP
), a guard is limited resource per thread, so an exception (or assertion) "no free guard" may be thrown if a limit of guard count per thread is exceeded.
|
inline |
Default constructor.
Initialize empty list
|
inline |
List destructor.
Clears the list
|
inline |
|
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 list 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
. pred
must imply the same element order as the comparator used for building the list.
|
inline |
Inserts data of type value_type
constructed with std::forward<Args>(args)...
Returns true
if inserting successful, false
otherwise.
|
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 |
Delete key
from the list.
Since the key of MichaelList's item type value_type
is not explicitly specified, template parameter Q
sould contain the complete key to search in the list. The list item comparator should be able to compare the type value_type
and the type Q
.
Return true
if key is found and deleted, false
otherwise
|
inline |
Deletes key
from the list.
The function searches an item with key key
, calls f
functor with item found and deletes it. If key
is not found, the functor is not called.
The functor Func
interface:
Since the key of MichaelList's item type value_type
is not explicitly specified, template parameter Q
should contain the complete key to search in the list. The list item comparator should be able to compare the type value_type
of list item and the type Q
.
Return true
if key is found and deleted, false
otherwise
|
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.
|
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.
|
inline |
Extracts the item from the list with specified key
.
The function searches an item with key equal to key
, unlinks it from the list, 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
.
guarded_ptr
object uses the GC's guard that can be limited resource.Usage:
|
inline |
Extracts the item from the list 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 it should accept 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 |
Finds key
and perform an action with it.
The function searches an item with key equal to key
and calls the functor f
for the 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 function is only guarantee that item
cannot be deleted during functor is executing. The function 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 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
. 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 it as guarded_ptr
. If key
is not found the function returns an empty guarded pointer.
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 accept 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 creates a node with copy of val
value and then inserts the node created into the list.
The type Q
should contain least the complete key of the node. The object of value_type should be constructible from val
of type Q
. In trivial case, Q
is equal to value_type.
Returns true
if inserting successful, false
otherwise.
|
inline |
Inserts new node.
This function inserts new node with default-constructed value and then it calls func
functor with signature
The argument itemValue
of user-defined functor func
is the reference to the list's item inserted. User-defined functor func
should guarantee that during changing item's value no any other changes could be made on this list's item by concurrent threads. The user-defined functor is called only if inserting is success.
The type Q
should contain the complete key of the node. The object of value_type
should be constructible from key
of type Q
.
The function allows to split creating of new item into two part:
key
with initializing key-fields only;func
functorThe method can be useful if complete initialization of object of value_type
is heavyweight and it is preferable that the initialization should be completed only if inserting is successful.
|
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 data by key
.
The operation performs inserting or replacing the element with lock-free manner.
If the key
not found in the list, then the new item created from key
will be inserted iff bAllowInsert
is true
. Otherwise, if key
is found, 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 listkey
- 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, second
is true if new item has been added or false
if the item with key
already exists.