cds
2.3.2
|
Lazy ordered list (key-value pair), template specialization for RCU. More...
#include <cds/container/lazy_kvlist_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
Garbage collector. | |
typedef Traits | traits |
List traits. | |
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::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 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 value_type * | raw_ptr |
Type of get() member function return value. | |
Public Member Functions | |
LazyKVList () | |
Default constructor. | |
~LazyKVList () | |
Destructor clears the list. | |
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 initializes it by a functor. More... | |
template<typename... Args> | |
bool | emplace (Args &&... args) |
Inserts data of type mapped_type constructed from args . More... | |
template<typename K , typename Func > | |
std::pair< bool, bool > | update (const K &key, Func func, bool bAllowInsert=true) |
Updates data by key . 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) const |
Checks whether the list contains key . More... | |
template<typename Q , typename Less > | |
bool | contains (Q const &key, Less pred) const |
Checks whether the map contains key using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | find (Q const &key, Func f) const |
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) const |
Finds the key val using pred predicate for searching. More... | |
template<typename K > | |
value_type * | get (K const &key) const |
Finds key and return the item found. More... | |
template<typename K , typename Less > | |
value_type * | get_with (K const &key, Less pred) const |
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. | |
Static Public Attributes | |
static constexpr const bool | c_bExtractLockExternal = base_class::c_bExtractLockExternal |
Group of extract_xxx functions 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::LazyList< cds::urcu::gc< RCU >, implementation_defined, Traits > | |
typedef node_type::marked_ptr | marked_node_ptr |
Node marked pointer. | |
typedef node_type * | auxiliary_head |
Auxiliary head type (for split-list support) | |
typedef cds::urcu::gc< RCU > | gc |
Garbage collector. | |
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 | |
typedef get_node_traits< value_type, node_type, hook >::type | node_traits |
node traits | |
typedef lazy_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 |
C++ memory ordering (see lazy_list::traits::memory_model ) | |
typedef traits::stat | stat |
Internal statistics. | |
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::LazyList< cds::urcu::gc< RCU >, implementation_defined, Traits > | |
LazyList () | |
Default constructor initializes empty list. | |
~LazyList () | |
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 bAllowInsert=true) |
Updates the item. 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 (const Q &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 (const Q &key, Less pred, Func func) |
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 from the list with comparing functor pred . More... | |
bool | find (Q &key, Func f) |
Finds the key key . More... | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the key key using pred predicate for searching. More... | |
bool | contains (Q const &key) |
Checks whether the list contains key . More... | |
guarded_ptr | get (Q const &key) |
guarded_ptr | get_with (Q const &key, Less pred) |
Finds key and return the item found. More... | |
void | clear () |
Clears the list. | |
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. | |
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. | |
Static Protected Attributes inherited from cds::intrusive::LazyList< cds::urcu::gc< RCU >, implementation_defined, Traits > | |
static constexpr const size_t | c_nHazardPtrCount |
Count of hazard pointer required for the algorithm. | |
Lazy ordered list (key-value pair), template specialization for RCU.
This is key-value variation of non-intrusive LazyList
. 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 to be stored in the list. It should be copy-constructibleValue
- value type to be stored in the listTraits
- type traits, default is lazy_list::traits
It is possible to declare option-based list with lazy_list::make_traits
metafunction istead of Traits
template argument. For example, the following traits-based declaration of gc::HP
lazy list <cds/container/lazy_kvlist_rcu.h>
you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files. typedef iterator_type<false> cds::container::LazyKVList< 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 |
|
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 from args
.
Returns true
if inserting successful, false
otherwise.
The function makes 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 pointing to dummy tail node.
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.
Returns 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(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 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 applies 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 nullptr
.
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 makes 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_type
should be constructible from key
of type K
.mapped_type
should be constructible from val
of type V
.The function makes RCU lock internally.
Returns true
if inserting successful, false
otherwise.
|
inline |
Inserts new node and initializes 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. 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.
The function makes RCU lock internally.
|
inline |
Returns list's item count.
The value returned depends on opt::item_counter option. For atomicity::empty_item_counter, this function always returns 0.
|
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
; during func
call item
is locked so it is safe to modify the item in multi-threaded environment.
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.