cds
2.3.2
|
Lazy ordered list. More...
#include <cds/container/impl/lazy_list.h>
Public Types | |
typedef GC | gc |
Garbage collector used. | |
typedef T | value_type |
Type of value stored in the list. | |
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_set< node_type, value_type > > | guarded_ptr |
Guarded pointer. | |
Public Member Functions | |
LazyList () | |
Default constructor. | |
~LazyList () | |
Destructor clears the list. | |
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... Args> | |
bool | emplace (Args &&... args) |
Inserts data of type value_type constructed from args . 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 Q > | |
bool | erase (Q const &key) |
Deletes 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 the key key and performs an action with it. 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 > | |
guarded_ptr | get (Q const &key) |
Finds the key key and return the item found. More... | |
template<typename Q , typename Less > | |
guarded_ptr | get_with (Q const &key, Less pred) |
Finds the key key and return the item found. 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. | |
void | clear () |
Clears the list. | |
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::LazyList< GC, T, 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 GC | gc |
Garbage collector. | |
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 | |
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< GC, T, Traits > | |
LazyList () | |
Default constructor initializes empty list. | |
~LazyList () | |
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 bAllowInsert=true) |
Updates the item. 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 (const Q &key, Func func) |
Deletes the item from the list. More... | |
template<typename Q , typename Less , typename Func > | |
bool | erase_with (const Q &key, Less pred, Func func) |
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 , typename Func > | |
bool | find (Q &key, Func f) |
Finds the key key . 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 > | |
bool | contains (Q const &key) |
Checks whether the list contains key . More... | |
template<typename Q > | |
guarded_ptr | get (Q const &key) |
template<typename Q , typename Less > | |
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... | |
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 Protected Attributes inherited from cds::intrusive::LazyList< GC, T, Traits > | |
static constexpr const size_t | c_nHazardPtrCount = 4 |
Count of hazard pointer required for the algorithm. | |
Lazy 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)
.
Source:
The lazy list is based on an optimistic locking scheme for inserts and removes, eliminating the need to use the equivalent of an atomically markable reference. It also has a novel wait-free membership find()
operation that does not need to perform cleanup operations and is more efficient.
It is non-intrusive version of cds::intrusive::LazyList
class.
Template arguments:
GC
- garbage collector: gc::HP
, gp::DHP
T
- type to be stored in the list.Traits
- 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 Unlike standard container, this implementation does not divide type T
into key and value part and may be used as main building block for hash set algorithms.
The key is a function (or a part) of type T
, and the comparing function is specified by Traits::compare
functor or Traits::less
predicate.
LazyKVList
is a key-value version of lazy non-intrusive list that is closer to the C++ std library approach.
typedef iterator_type<true> cds::container::LazyList< GC, T, Traits >::const_iterator |
Const forward iterator.
For iterator's features and requirements see iterator
typedef iterator_type<false> cds::container::LazyList< GC, T, Traits >::iterator |
Forward iterator.
The forward iterator for lazy 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 |
|
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 from args
.
Returns true
if inserting successful, false
otherwise.
|
inline |
|
inline |
Deletes key
from the list.
Since the key of LazyList's item type T
is not explicitly specified, template parameter Q
defines the key type searching in the list. The list item comparator should be able to compare the type T
of list item 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 the item. If key
is not found, the functor is not called.
The functor Func
interface:
Since the key of LazyList's item type T
is not explicitly specified, template parameter Q
defines the key type searching in the list. The list item comparator should be able to compare the type T
of list item and the type Q
.
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(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 should take 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 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, 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 key
argument is non-const since it can be used as f
functor destination i.e., the functor may modify both arguments.
The function returns true
if key
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 |
Finds the key key
and return the item found.
The function searches the item with key equal to key
and returns the item found 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 the key 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 take 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 as minimum 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 item
of user-defined functor func
is the reference to the list's item inserted. When func
is called it has exclusive access to the item. The user-defined functor is called only if the 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
functorThis 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 Traits::item_counter
type. 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
. 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
; during func
call item
is locked so it is safe to modify the item in multi-threaded environment.
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.