cds
2.3.2
|
Michael's ordered list for key-value pair. More...
#include <cds/container/impl/michael_kvlist.h>
Public Types | |
typedef Key | key_type |
Key type. | |
typedef Value | mapped_type |
Type of value stored in the list. | |
typedef std::pair< key_type const, mapped_type > | value_type |
key/value pair stored in the list | |
typedef base_class::gc | gc |
Garbage collector used. | |
typedef Traits | traits |
List traits. | |
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_map< node_type, value_type > > | guarded_ptr |
Guarded pointer. | |
typedef iterator_type< false > | iterator |
Forward iterator. More... | |
typedef iterator_type< true > | const_iterator |
Const forward iterator. More... | |
Public Member Functions | |
MichaelKVList () | |
Default constructor. More... | |
~MichaelKVList () | |
List destructor. More... | |
template<typename K > | |
bool | insert (K &&key) |
Inserts new node with key and default value. More... | |
template<typename K , typename V > | |
bool | insert (K &&key, V &&val) |
Inserts new node with a key and a value. More... | |
template<typename K , typename Func > | |
bool | insert_with (K &&key, Func func) |
Inserts new node and initialize it by a functor. More... | |
template<typename K , typename Func > | |
std::pair< bool, bool > | update (K &&key, Func f, bool bAllowInsert=true) |
Updates data by key . More... | |
template<typename K , typename... Args> | |
bool | emplace (K &&key, Args &&... args) |
Inserts a new node using move semantics. More... | |
template<typename K > | |
bool | erase (K const &key) |
Deletes key from the list. More... | |
template<typename K , typename Less > | |
bool | erase_with (K const &key, Less pred) |
Deletes the item from the list using pred predicate for searching. More... | |
template<typename K , typename Func > | |
bool | erase (K const &key, Func f) |
Deletes key from the list. More... | |
template<typename K , typename Less , typename Func > | |
bool | erase_with (K const &key, Less pred, Func f) |
Deletes the item from the list using pred predicate for searching. More... | |
template<typename K > | |
guarded_ptr | extract (K const &key) |
Extracts the item from the list with specified key . More... | |
template<typename K , typename Less > | |
guarded_ptr | extract_with (K 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 map contains key using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | find (Q const &key, Func f) |
Finds the key key and performs an action with it. More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q const &key, Less pred, Func f) |
Finds the key val using pred predicate for searching. More... | |
template<typename K > | |
guarded_ptr | get (K const &key) |
Finds the key and return the item found. More... | |
template<typename K , typename Less > | |
guarded_ptr | get_with (K const &key, Less pred) |
Finds the key and return the item found. More... | |
bool | empty () const |
Checks 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. | |
Forward iterators (only for debugging purpose) | |
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. | |
Static Public Attributes | |
static constexpr const size_t | c_nHazardPtrCount = base_class::c_nHazardPtrCount |
Count of hazard pointer required for the algorithm. | |
Additional Inherited Members | |
Protected Types inherited from cds::intrusive::MichaelList< GC, implementation_defined, 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 implementation_defined | 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, implementation_defined, Traits > | |
MichaelList () | |
Default constructor initializes empty list. | |
~MichaelList () | |
Destroys the list object. | |
bool | insert (value_type &val) |
Inserts new node. More... | |
bool | insert (value_type &val, Func f) |
Inserts new node. More... | |
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... | |
bool | erase (Q const &key) |
Deletes the item from the list. More... | |
bool | erase (Q const &key, Func func) |
Deletes the item from the list. More... | |
bool | erase_with (Q const &key, Less pred) |
Deletes the item from the list using pred predicate for searching. More... | |
bool | erase_with (Q const &key, Less pred, Func f) |
Deletes the item from the list using pred predicate for searching. More... | |
guarded_ptr | extract (Q const &key) |
Extracts the item from the list with specified key . More... | |
guarded_ptr | extract_with (Q const &key, Less pred) |
Extracts the item using compare functor pred . More... | |
bool | find (Q &key, Func f) |
Finds key in the list. More... | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the key using pred predicate for searching. More... | |
bool | contains (Q const &key) |
Checks whether the list contains key . More... | |
bool | contains (Q const &key, Less pred) |
Checks whether the list contains key using pred predicate for searching. More... | |
guarded_ptr | get (Q const &key) |
Finds the key and return the item found. More... | |
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... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a list. | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a list. More... | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a list. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first 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, implementation_defined, 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, implementation_defined, Traits > | |
static constexpr const size_t | c_nHazardPtrCount |
Count of hazard pointer required for the algorithm. | |
Michael's ordered list for key-value pair.
This is key-value variation of non-intrusive MichaelList. Like standard container, this implementation split a value stored into two part - constant key and alterable value.
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.
Template arguments:
GC
- garbage collector usedKey
- key type of an item stored in the list. It should be copy-constructibleValue
- value type stored in a listTraits
- type traits, default is michael_list::traits
It is possible to declare option-based list with cds::container::michael_list::make_traits
metafunction instead 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::MichaelKVList< GC, Key, Value, Traits >::const_iterator |
Const forward iterator.
For iterator's features and requirements see iterator
typedef iterator_type<false> cds::container::MichaelKVList< GC, Key, Value, 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.The iterator interface to access item data:
operator ->
- returns a pointer to value_type for iterator operator *
- returns a reference (a const reference for const_iterator
) to value_type for iterator const key_type& key()
- returns a key reference for iterator mapped_type& val()
- retuns a value reference for iterator (const reference for const_iterator
)For both functions the iterator should not be equal to end()
|
inline |
Default constructor.
Initializes 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 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 |
Inserts a new node using move semantics.
key_type
field of new item is constructed from key
argument, mapped_type
field is done from 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 |
|
inline |
Deletes key
from the list.
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:
Return true
if key is found and deleted, false
otherwise
See also: erase
|
inline |
Deletes the item from the list using pred
predicate for searching.
The function is an analog of erase(K 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(K 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 K
that can be not the same as key_type
.
The disposer
specified in Traits
class template parameter is called automatically by garbage collector GC
specified in class' template parameters 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 list with comparing functor pred
.
The function is an analog of extract(K const&) but pred
predicate is used for key comparing.
Less
functor has the semantics like std::less
but should take arguments of type key_type and K
in any order. pred
must imply the same element order as the comparator used for building the list.
|
inline |
Finds the key key
and performs 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.
The functor may change item.second
that is reference to value of node. 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 the key val
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 the 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 K
that can be not the same as key_type
.
|
inline |
Finds the key
and return the item found.
The function is an analog of get( guarded_ptr& ptr, K const&) but pred
is used for comparing the keys.
Less
functor has the semantics like std::less
but should take arguments of type key_type and K
in any order. pred
must imply the same element order as the comparator used for building the list.
|
inline |
Inserts new node with key and default value.
The function creates a node with key
and default value, and then inserts the node created into the list.
Preconditions:
key_type
should be constructible from value of type K
. In trivial case, K
is equal to key_type
.mapped_type
should be default-constructible.Returns true
if inserting successful, false
otherwise.
|
inline |
Inserts new node with a key and a value.
The function creates a node with key
and value val
, and then inserts the node created into the list.
Preconditions:
key_type
should be constructible from key
of type K
.mapped_type
should be constructible from val
of type V
.Returns true
if inserting successful, false
otherwise.
|
inline |
Inserts new node and initialize it by a functor.
This function inserts new node with key key
and if inserting is successful then it calls func
functor with signature
The argument item
of user-defined functor func
is the reference to the item inserted. item.second
is a reference to item's value that may be changed. 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 successful.
The key_type
should be constructible from value of type K
.
The function allows to split creating of new item into two part:
key
;func
functorThis can be useful if complete initialization of object of mapped_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
. (note that in this case the key_type should be constructible from type K
). 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
- the item found or insertedThe functor may change any fields of the item.second
of mapped_type
; 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.