cds
2.3.2
|
Michael's ordered list (key-value pair), template specialization for RCU. More...
#include <cds/container/michael_kvlist_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
Garbage collector. | |
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 Traits | traits |
List traits. | |
typedef base_class::back_off | back_off |
Back-off strategy. | |
typedef maker::allocator_type | allocator_type |
Allocator type used for allocate/deallocate the nodes. | |
typedef base_class::item_counter | item_counter |
Item counting policy. | |
typedef maker::key_comparator | key_comparator |
key comparison functor | |
typedef base_class::memory_model | memory_model |
Memory ordering. See michael_list::traits::memory_model . | |
typedef base_class::stat | stat |
Internal statistics. | |
typedef base_class::rcu_check_deadlock | rcu_check_deadlock |
RCU deadlock checking policy. | |
typedef gc::scoped_lock | rcu_lock |
RCU scoped lock. | |
using | exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer, cds::urcu::details::conventional_exempt_pair_cast< node_type, value_type > > |
pointer to extracted node | |
typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > | raw_ptr |
Result of get() , get_with() functions - pointer to the node found. | |
Public Member Functions | |
MichaelKVList () | |
Default constructor. More... | |
~MichaelKVList () | |
List destructor. More... | |
template<typename K > | |
bool | insert (const K &key) |
Inserts new node with key and default value. More... | |
template<typename K , typename V > | |
bool | insert (const K &key, const V &val) |
Inserts new node with a key and a value. More... | |
template<typename K , typename Func > | |
bool | insert_with (const K &key, Func func) |
Inserts new node and initialize it by a functor. More... | |
template<typename K , typename Func > | |
std::pair< bool, bool > | update (const K &key, Func func, bool bAllowInsert=true) |
Updates an element with given key . More... | |
template<typename K , typename... Args> | |
bool | emplace (K &&key, Args &&... args) |
Inserts data of type mapped_type constructed with std::forward<Args>(args)... 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 > | |
exempt_ptr | extract (K const &key) |
Extracts an item from the list. More... | |
template<typename K , typename Less > | |
exempt_ptr | extract_with (K const &key, Less pred) |
Extracts an item from the list 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 , typename Func > | |
bool | find (Q const &key, Func f) |
Finds 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 > | |
raw_ptr | get (K const &key) |
Finds key and return the item found. More... | |
template<typename K , typename Less > | |
raw_ptr | get_with (K const &key, Less pred) |
Finds 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... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
void | clear () |
Clears the list. More... | |
Static Public Attributes | |
static constexpr const bool | c_bExtractLockExternal = base_class::c_bExtractLockExternal |
Group of extract_xxx functions do not require external locking. | |
Forward iterators | |
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. | |
Additional Inherited Members | |
Protected Types inherited from cds::intrusive::MichaelList< cds::urcu::gc< RCU >, 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 cds::urcu::gc< RCU > | 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< cds::urcu::gc< RCU >, 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< cds::urcu::gc< RCU >, 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< cds::urcu::gc< RCU >, implementation_defined, Traits > | |
static constexpr const size_t | c_nHazardPtrCount |
Count of hazard pointer required for the algorithm. | |
Michael's ordered list (key-value pair), template specialization for RCU.
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)
.
Template arguments:
RCU
- one of RCU typeKey
- 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
<cds/container/michael_kvlist_rcu.h>
you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files.It is possible to declare option-based list using cds::container::michael_list::make_traits
metafunction istead of Traits
template argument. For example, the following traits-based declaration of Michael's list
is equivalent for the following option-based list
typedef iterator_type<false> cds::container::MichaelKVList< cds::urcu::gc< RCU >, Key, Value, Traits >::iterator |
Forward iterator.
You may safely use iterators in multi-threaded environment only under external RCU lock. Otherwise, a program crash is possible if another thread deletes the item the iterator points to.
|
inline |
Default constructor.
Initializes empty list
|
inline |
List destructor.
Clears the list
|
inline |
|
inline |
Clears the list.
Post-condition: the list is empty
|
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.
The function applies RCU lock internally.
|
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.
The function applies RCU lock internally.
|
inline |
Inserts data of type mapped_type constructed with std::forward<Args>(args)...
Returns true
if inserting successful, false
otherwise.
The function applies RCU lock internally.
|
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:
RCU synchronize
method can be called. RCU should not be locked.
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 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(K 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 |
Finds 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 makes RCU lock internally.
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 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 |
Finds key
and return the item found.
The function searches the item with key
and returns the pointer to item found. If key
is not found it returns an empty raw_ptr
object.
Note the compare functor should accept a parameter of type K
that can be not the same as key_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(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:
K
. In trivial case, K
is equal to key_type.The function applies RCU lock internally.
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
of type K
.val
of type V
.The function applies RCU lock internally.
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 list's 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 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.
The function applies 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 |
Updates an element with given key
.
The operation performs inserting or changing data with lock-free manner.
If the key
not found in the list, then the new item created from key
is inserted into the list (note that in this case the key_type should be copy-constructible from type K
). Otherwise, the functor func
is called with item found. The functor Func
may be a function with signature:
or a functor:
with arguments:
bNew
- true
if the item has been inserted, false
otherwiseitem
- item of the listThe functor may change any fields of the item.second
that is mapped_type; however, func
must guarantee that during changing no any other modifications could be made on this item by concurrent threads.
The function applies RCU lock internally.
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.
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
that is mapped_type; however, func
must guarantee that during changing no any other modifications could be made on this item by concurrent threads.
The function applies RCU lock internally.
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.