cds
2.3.2
|
Split-ordered list map (template specialization for gc::nogc) More...
#include <cds/container/split_list_map_nogc.h>
Public Types | |
typedef cds::gc::nogc | gc |
Garbage collector. | |
typedef Key | key_type |
key type | |
typedef Value | mapped_type |
type of value stored in the map | |
typedef std::pair< key_type const, mapped_type > | value_type |
Pair type. | |
typedef base_class::ordered_list | ordered_list |
Underlying ordered list class. | |
typedef base_class::key_comparator | key_comparator |
key comparison functor | |
typedef base_class::hash | hash |
Hash functor for key_type. | |
typedef base_class::item_counter | item_counter |
Item counter type. | |
typedef base_class::stat | stat |
Internal statistics. | |
Public Member Functions | |
SplitListMap () | |
Initialize split-ordered map of default capacity. More... | |
SplitListMap (size_t nItemCount, size_t nLoadFactor=1) | |
Initialize split-ordered map. More... | |
template<typename K > | |
iterator | insert (K const &key) |
Inserts new node with key and default value. More... | |
template<typename K , typename V > | |
iterator | insert (K const &key, V const &val) |
Inserts new node. 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 , typename... Args> | |
iterator | emplace (K &&key, Args &&... args) |
For key key inserts data of type mapped_type created in-place from args . More... | |
template<typename K > | |
std::pair< iterator, bool > | update (K const &key, bool bAllowInsert=true) |
Updates the item. More... | |
template<typename K > | |
iterator | contains (K const &key) |
Checks whether the map contains key . More... | |
template<typename K , typename Less > | |
iterator | contains (K const &key, Less pred) |
Checks whether the map contains key using pred predicate for searching. More... | |
void | clear () |
Clears the set (not atomic, for debugging purposes only) | |
bool | empty () const |
Checks if the map is empty. More... | |
size_t | size () const |
Returns item count in the map. | |
stat const & | statistics () const |
Returns internal statistics. | |
ordered_list::stat const & | list_statistics () const |
Returns internal statistics for ordered_list . | |
Forward iterators | |
typedef base_class::iterator | iterator |
Forward iterator. More... | |
typedef base_class::const_iterator | const_iterator |
Const forward iterator. | |
iterator | begin () |
Returns a forward iterator addressing the first element in a map. More... | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a map. More... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a map. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first element in a map. | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a map. | |
const_iterator | cend () const |
Returns an const iterator that addresses the location succeeding the last element in a map. | |
Additional Inherited Members | |
Protected Types inherited from cds::container::SplitListSet< cds::gc::nogc, std::pair< Key const, Value >, split_list::details::wrap_map_traits< Key, Value, Traits > > | |
typedef cds::gc::nogc | gc |
Garbage collector. | |
typedef std::pair< Key const, Value > | value_type |
Type of vlue to be stored in split-list. | |
typedef split_list::details::wrap_map_traits< Key, Value, Traits > | traits |
Traits template argument | |
typedef maker::ordered_list | ordered_list |
Underlying ordered list class. | |
typedef base_class::key_comparator | key_comparator |
key compare functor | |
typedef base_class::hash | hash |
Hash functor for value_type and all its derivatives that you use. | |
typedef base_class::item_counter | item_counter |
Item counter type. | |
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. | |
typedef iterator_type< false > | iterator |
Forward iterator. More... | |
typedef iterator_type< true > | const_iterator |
Const forward iterator. | |
Protected Types inherited from cds::intrusive::SplitListSet< cds::gc::nogc, split_list::details::wrap_map_traits< Key, Value, Traits > ::ordered_list, split_list::details::wrap_map_traits< Key, Value, Traits > > | |
typedef cds::gc::nogc | gc |
Garbage collector. | |
typedef split_list::details::wrap_map_traits< Key, Value, Traits > | traits |
Set traits. | |
typedef split_list::details::wrap_map_traits< Key, Value, Traits > ::ordered_list | ordered_list |
type of ordered list used as a base for split-list | |
typedef ordered_list::value_type | value_type |
type of value stored in the split-list | |
typedef ordered_list::key_comparator | key_comparator |
key comparison functor | |
typedef ordered_list::disposer | disposer |
Node disposer functor. | |
typedef cds::opt::v::hash_selector< typename traits::hash >::type | hash |
Hash functor for value_type and all its derivatives you use. | |
typedef traits::bit_reversal | bit_reversal |
Bit reversal algorithm, see split_list::traits::bit_reversal . | |
typedef traits::item_counter | item_counter |
Item counter type. | |
typedef traits::back_off | back_off |
back-off strategy for spinning | |
typedef traits::memory_model | memory_model |
Memory ordering. See cds::opt::memory_model option. | |
typedef traits::stat | stat |
Internal statistics, see spit_list::stat . | |
typedef ordered_list::guarded_ptr | 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::container::SplitListSet< cds::gc::nogc, std::pair< Key const, Value >, split_list::details::wrap_map_traits< Key, Value, Traits > > | |
SplitListSet () | |
Initializes split-ordered list of default capacity. More... | |
SplitListSet (size_t nItemCount, size_t nLoadFactor=1) | |
Initializes split-ordered list. More... | |
bool | insert (Q &&val) |
Inserts new node. More... | |
bool | insert (Q &&val, Func f) |
Inserts new node. More... | |
bool | emplace (Args &&... args) |
Inserts data of type value_type created from args . More... | |
std::pair< bool, bool > | upsert (Q &&val, bool bAllowInsert=true) |
Inserts or updates the node (only for IterableList -based set) More... | |
std::pair< bool, bool > | update (Q &&val, Func func, bool bAllowInsert=true) |
Updates the node. More... | |
bool | erase (Q const &key) |
Deletes key from the set. More... | |
bool | erase (Q const &key, Func f) |
Deletes key from the set. More... | |
bool | erase_with (Q const &key, Less pred) |
Deletes the item from the set using pred predicate for searching. More... | |
bool | erase_with (Q const &key, Less pred, Func f) |
Deletes the item from the set using pred predicate for searching. More... | |
bool | erase_at (iterator const &iter) |
Deletes the item pointed by iterator iter (only for IterableList based set) More... | |
guarded_ptr | extract (Q const &key) |
Extracts the item 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 the key key . More... | |
iterator | find (Q &key) |
Finds key and returns iterator pointed to the item found (only for IterableList -based set) More... | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the key key using pred predicate for searching. More... | |
iterator | find_with (Q &key, Less pred) |
Finds key using pred predicate and returns iterator pointed to the item found (only for IterableList -based set) More... | |
bool | contains (Q const &key) |
Checks whether the set contains key . More... | |
bool | contains (Q const &key, Less pred) |
Checks whether the map contains key using pred predicate for searching. More... | |
guarded_ptr | get (Q const &key) |
Finds the key key and return the item found. More... | |
guarded_ptr | get_with (Q const &key, Less pred) |
Finds key and return the item found. More... | |
void | clear () |
Clears the set (not atomic) | |
bool | empty () const |
Checks if the set is empty. More... | |
size_t | size () const |
Returns item count in the set. | |
stat const & | statistics () const |
Returns internal statistics. | |
ordered_list::stat const & | list_statistics () const |
Returns internal statistics for ordered_list . | |
iterator | begin () |
Returns a forward iterator addressing the first element in a set. More... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a set. | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a set. More... | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a set. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first element in a set. | |
const_iterator | cend () const |
Returns an const iterator that addresses the location succeeding the last element in a set. | |
Protected Member Functions inherited from cds::intrusive::SplitListSet< cds::gc::nogc, split_list::details::wrap_map_traits< Key, Value, Traits > ::ordered_list, split_list::details::wrap_map_traits< Key, Value, Traits > > | |
SplitListSet () | |
Initialize split-ordered list of default capacity. More... | |
SplitListSet (size_t nItemCount, size_t nLoadFactor=1) | |
Initialize split-ordered list. More... | |
~SplitListSet () | |
Destroys split-list set. | |
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 node. More... | |
std::pair< bool, bool > | upsert (value_type &val, bool bAllowInsert=true) |
Inserts or updates the node (only for IterableList ) More... | |
bool | unlink (value_type &val) |
Unlinks the item val from the set. More... | |
bool | erase (Q const &key) |
Deletes the item from the set. More... | |
bool | erase (Q const &key, Func f) |
Deletes the item from the set. More... | |
bool | erase_with (const Q &key, Less pred) |
Deletes the item from the set with comparing functor pred . More... | |
bool | erase_with (Q const &key, Less pred, Func f) |
Deletes the item from the set with comparing functor pred . More... | |
bool | erase_at (iterator const &iter) |
Deletes the item pointed by iterator iter (only for IterableList based set) More... | |
guarded_ptr | extract (Q const &key) |
Extracts the item 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 the key key . More... | |
iterator | find (Q &key) |
Finds key and returns iterator pointed to the item found (only for IterableList ) More... | |
bool | find_with (Q &key, Less pred, Func f) |
Finds the key key with pred predicate for comparing. More... | |
iterator | find_with (Q &key, Less pred) |
Finds key using pred predicate and returns iterator pointed to the item found (only for IterableList ) More... | |
bool | contains (Q const &key) |
Checks whether the set contains key . More... | |
bool | contains (Q const &key, Less pred) |
Checks whether the set contains key using pred predicate for searching. More... | |
guarded_ptr | get (Q const &key) |
Finds the key key and return the item found. More... | |
guarded_ptr | get_with (Q const &key, Less pred) |
Finds the key key and return the item found. More... | |
size_t | size () const |
Returns item count in the set. | |
bool | empty () const |
Checks if the set is empty. More... | |
void | clear () |
Clears the set (non-atomic) More... | |
stat const & | statistics () const |
Returns internal statistics. | |
split_list::details::wrap_map_traits< Key, Value, Traits > ::ordered_list ::stat const & | list_statistics () const |
Returns internal statistics for OrderedList . | |
iterator | begin () |
Returns a forward iterator addressing the first element in a split-list. More... | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a split-list. | |
iterator | end () |
Returns an iterator that addresses the location succeeding the last element in a split-list. More... | |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a split-list. | |
const_iterator | cbegin () const |
Returns a forward const iterator addressing the first element in a split-list. | |
const_iterator | cend () const |
Returns an const iterator that addresses the location succeeding the last element in a split-list. | |
Static Protected Attributes inherited from cds::container::SplitListSet< cds::gc::nogc, std::pair< Key const, Value >, split_list::details::wrap_map_traits< Key, Value, Traits > > | |
static constexpr const size_t | c_nHazardPtrCount |
Count of hazard pointer required. | |
Static Protected Attributes inherited from cds::intrusive::SplitListSet< cds::gc::nogc, split_list::details::wrap_map_traits< Key, Value, Traits > ::ordered_list, split_list::details::wrap_map_traits< Key, Value, Traits > > | |
static constexpr const size_t | c_nHazardPtrCount |
Count of hazard pointer required. | |
Split-ordered list map (template specialization for gc::nogc)
This specialization is so-called append-only. The map does not support the removal of list item.
See SplitListMap for description of template parameters.
typedef base_class::iterator cds::container::SplitListMap< cds::gc::nogc, Key, Value, Traits >::iterator |
Forward iterator.
The forward iterator for split-list is based on OrderedList
forward iterator and has some features:
The iterator interface:
|
inline |
Initialize split-ordered map of default capacity.
The default capacity is defined in bucket table constructor. See intrusive::split_list::expandable_bucket_table
, intrusive::split_list::static_ducket_table
which selects by intrusive::split_list::traits::dynamic_bucket_table
.
|
inline |
Initialize split-ordered map.
nItemCount | estimated average item count |
nLoadFactor | load factor - average item count per bucket. Small integer up to 10, default is 1. |
|
inline |
|
inline |
Checks whether the map contains key
.
The function searches the item with key equal to key
and returns an iterator pointed to item found and end() 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
. pred
must imply the same element order as the comparator used for building the map.
|
inline |
For key key
inserts data of type mapped_type
created in-place from args
.
key_type
should be constructible from type K
Returns true
if inserting successful, false
otherwise.
|
inline |
Checks if the map is empty.
Emptiness is checked by item counting: if item count is zero then the map is empty. Thus, the correct item counting feature is an important part of Michael's map implementation.
|
inline |
|
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 map.
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 an iterator pointed to inserted value, or end()
if inserting is failed
|
inline |
Inserts new node.
The function creates a node with copy of val
value and then inserts the node created into the map.
Preconditions:
key_type
should be constructible from key
of type K
.mapped_type
should be constructible from 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 map'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 map's item by concurrent threads. 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 |
Updates the item.
If key
is not in the map 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 (if inserting is not allowed and key
is not found, the iterator will be end()
),
second
is true if new item has been added or false
if the item already is in the map.