cds
2.3.2
|
Lazy ordered list (key-value pair, template specialization for gc::nogc) More...
#include <cds/container/lazy_kvlist_nogc.h>
Public Types | |
typedef Traits | traits |
List traits. | |
typedef cds::gc::nogc | 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 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. | |
Public Member Functions | |
LazyKVList () | |
Default constructor. | |
~LazyKVList () | |
Desctructor clears the list. | |
template<typename K > | |
iterator | insert (const K &key) |
Inserts new node with key and default value. More... | |
template<typename K , typename V > | |
iterator | insert (const K &key, const V &val) |
Inserts new node with a key and a value. More... | |
template<typename K , typename Func > | |
iterator | insert_with (const K &key, Func func) |
Inserts new node and initialize it by a functor. More... | |
template<typename K > | |
std::pair< iterator, bool > | update (const K &key, bool bAllowInsert=true) |
Updates the item. More... | |
template<typename... Args> | |
iterator | emplace (Args &&... args) |
Inserts data of type mapped_type constructed with std::forward<Args>(args)... More... | |
template<typename Q > | |
iterator | contains (Q const &key) |
Checks whether the list contains key . More... | |
template<typename Q , typename Less , bool Sort = c_bSort> | |
std::enable_if< Sort, iterator >::type | contains (Q const &key, Less pred) |
Checks whether the map contains key using pred predicate for searching (ordered list version) More... | |
template<typename Q , typename Equal , bool Sort = c_bSort> | |
std::enable_if<!Sort, iterator >::type | contains (Q const &key, Equal equal) |
Finds the key val using equal predicate for searching (unordered list version) More... | |
bool | empty () const |
Check 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 bool const | c_bSort = base_class::c_bSort |
List type: ordered (true ) or unordered (false ) | |
Forward iterators | |
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::nogc, 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 gc::nogc | 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< gc::nogc, 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< gc::nogc, 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 gc::nogc)
This specialization is append-only list when no item reclamation may be performed. The class does not support deleting of list's item.
typedef iterator_type<true> cds::container::LazyKVList< gc::nogc, Key, Value, Traits >::const_iterator |
Const forward iterator.
For iterator's features and requirements see iterator
typedef iterator_type<false> cds::container::LazyKVList< gc::nogc, Key, Value, Traits >::iterator |
Forward iterator.
The forward iterator is safe: you may use it in multi-threaded enviromnent without any synchronization.
The forward iterator for lazy list based on gc::nogc
has pre- and post-increment operators.
The iterator interface to access item data:
operator ->
- returns a pointer to value_type
operator *
- returns a reference (a const reference for const_iterator
) to value_type
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 |
|
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 an iterator pointed to item found if the key is found, and end() otherwise
|
inline |
Checks whether the map contains key
using pred
predicate for searching (ordered list version)
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 |
Finds the key val
using equal
predicate for searching (unordered list version)
The function is an analog of contains( key )
but equal
is used for key comparing. Equal
functor has the interface like std::equal_to
.
|
inline |
Inserts data of type mapped_type constructed with std::forward<Args>(args)...
Returns an iterator pointed to inserted value, or end()
if inserting is failed
|
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 |
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.Returns an iterator pointed to inserted value, or end()
if inserting is failed
|
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
.Returns an iterator pointed to inserted value, or end()
if inserting is failed
|
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. The user-defined functor is called only if the 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
;f
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.
Returns an iterator pointed to inserted value, or end()
if inserting is failed
|
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 the item.
If key
is not in the list and bAllowInsert
is true
,
the function inserts a new item. Otherwise, the function returns an iterator pointing to the item found.
Returns std::pair<iterator, bool>
where first
is an iterator pointing to item found or inserted, second
is true if new item has been added or false
if the item already is in the list.