cds
2.3.2
|
Split-ordered list map (template specialization for RCU) More...
#include <cds/container/split_list_map_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 to be stored in the map | |
typedef Traits | traits |
Map traits. | |
typedef std::pair< key_type const, mapped_type > | value_type |
key-value 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. | |
typedef base_class::rcu_lock | rcu_lock |
RCU scoped lock. | |
typedef base_class::exempt_ptr | exempt_ptr |
typedef base_class::raw_ptr | raw_ptr |
type of get() return value | |
typedef base_class::iterator | iterator |
Forward iterator. | |
typedef base_class::const_iterator | const_iterator |
Const forward iterator. | |
Public Member Functions | |
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... | |
SplitListMap () | |
Initializes split-ordered map of default capacity. More... | |
SplitListMap (size_t nItemCount, size_t nLoadFactor=1) | |
Initializes split-ordered map. More... | |
template<typename K > | |
bool | insert (K const &key) |
Inserts new node with key and default value. More... | |
template<typename K , typename V > | |
bool | insert (K const &key, V const &val) |
Inserts new node. More... | |
template<typename K , typename Func > | |
bool | insert_with (K const &key, Func func) |
Inserts new node and initialize it by a functor. More... | |
template<typename K , typename... Args> | |
bool | emplace (K &&key, Args &&... args) |
For key key inserts data of type mapped_type created in-place from args . More... | |
template<typename K , typename Func > | |
std::pair< bool, bool > | update (K const &key, Func func, bool bAllowInsert=true) |
Updates data by key . More... | |
template<typename K > | |
bool | erase (K const &key) |
Deletes key from the map. More... | |
template<typename K , typename Less > | |
bool | erase_with (K const &key, Less pred) |
Deletes the item from the map using pred predicate for searching. More... | |
template<typename K , typename Func > | |
bool | erase (K const &key, Func f) |
Deletes key from the map. More... | |
template<typename K , typename Less , typename Func > | |
bool | erase_with (K const &key, Less pred, Func f) |
Deletes the item from the map using pred predicate for searching. More... | |
template<typename K > | |
exempt_ptr | extract (K const &key) |
Extracts an item from the map. More... | |
template<typename K , typename Less > | |
exempt_ptr | extract_with (K const &key, Less pred) |
Extracts an item from the map using pred predicate for searching. More... | |
template<typename K , typename Func > | |
bool | find (K const &key, Func f) |
Finds the key key . More... | |
template<typename K , typename Less , typename Func > | |
bool | find_with (K const &key, Less pred, Func f) |
Finds the key key using pred predicate for searching. More... | |
template<typename K > | |
bool | contains (K const &key) |
Checks whether the map contains key . More... | |
template<typename K , typename Less > | |
bool | contains (K const &key, Less pred) |
Checks whether the map contains key 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 with predicate specified and return the item found. More... | |
void | clear () |
Clears the map (not atomic) | |
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 . | |
const_iterator | begin () const |
Returns a forward const iterator addressing the first element in a map. | |
const_iterator | cbegin () const |
const_iterator | end () const |
Returns an const iterator that addresses the location succeeding the last element in a map. | |
const_iterator | cend () const |
Static Public Attributes | |
static constexpr const bool | c_bExtractLockExternal = base_class::c_bExtractLockExternal |
Group of extract_xxx functions require external locking if underlying ordered list requires that. | |
Additional Inherited Members | |
Protected Types inherited from cds::container::SplitListSet< cds::urcu::gc< RCU >, std::pair< Key const, Value >, split_list::details::wrap_map_traits< Key, Value, Traits > > | |
typedef cds::urcu::gc< RCU > | 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::urcu::gc< RCU >, split_list::details::wrap_map_traits< Key, Value, Traits > ::ordered_list, split_list::details::wrap_map_traits< Key, Value, Traits > > | |
typedef cds::urcu::gc< RCU > | 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::urcu::gc< RCU >, 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::urcu::gc< RCU >, 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::urcu::gc< RCU >, 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::urcu::gc< RCU >, 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 RCU)
Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
See intrusive::SplitListSet for a brief description of the split-list algorithm.
Template parameters:
RCU
- one of RCU typeKey
- key type to be stored in the mapValue
- value type to be stored in the mapTraits
- type traits, default is split_list::traits
. Instead of declaring split_list::traits
-based struct you may apply option-based notation with split_list::make_traits
metafunction.Iterators
The class supports a forward unordered iterator (iterator and const_iterator). You may iterate over split-list map items only under RCU lock. Only in this case the iterator is thread-safe since while RCU is locked any map's item cannot be reclaimed. The requirement of RCU lock during iterating means that deletion of the elements is not possible.
The iterator class supports the following minimalistic interface:
Note, the iterator object returned by end, cend
member functions points to nullptr
and should not be dereferenced.
You should decide what garbage collector you want, and what ordered list you want to use. Split-ordered list is original data structure based on an ordered list. Suppose, you want construct split-list map based on cds::urcu::general_buffered<>
GC and MichaelList
as ordered list implementation. Your map should map int
key to std::string
value. So, you beginning your program with following include:
The inclusion order is important:
cds/urcu/general_buffered.h
in our case)cds/container/michael_list_rcu.h
),cds/container/split_list_map_rcu.h
.Now, you should declare traits for split-list map. The main parts of traits are a hash functor for the map key and a comparing functor for ordered list. We use std::hash<int>
and std::less<int>
.
The second attention: instead of using MichaelList
in SplitListMap
traits we use a tag ds::contaner::michael_list_tag
for the Michael's list. The split-list requires significant support from underlying ordered list class and it is not good idea to dive you into deep implementation details of split-list and ordered list interrelations. The tag paradigm simplifies split-list interface.
Now you are ready to declare our map class based on SplitListMap
:
You may use the modern option-based declaration instead of classic traits-based one:
In case of option-based declaration using split_list::make_traits
metafunction the struct foo_set_traits
is not required.
Now, the map of type int_string_map
is ready to use in your program.
Note that in this example we show only mandatory traits
parts, optional ones is the default and they are inherited from cds::container::split_list::traits. There are many other useful options for deep tuning the split-list and ordered-list containers.
typedef base_class::exempt_ptr cds::container::SplitListMap< cds::urcu::gc< RCU >, Key, Value, Traits >::exempt_ptr |
pointer to extracted node
|
inline |
Initializes 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_bucket_table
which selects by split_list::dynamic_bucket_table
option.
|
inline |
Initializes 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 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 map.
|
inline |
For key key
inserts data of type mapped_type
created in-place from args
.
key_type
should be constructible from type K
The function applies RCU lock internally.
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 is an important part of the map implementation.
|
inline |
|
inline |
|
inline |
Deletes key
from the map.
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 is:
RCU synchronize
method can be called. RCU should not be locked.
Return true
if key is found and deleted, false
otherwise
|
inline |
Deletes the item from the map 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
. Less
must imply the same element order as the comparator used for building the map.
|
inline |
Deletes the item from the map 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
. Less
must imply the same element order as the comparator used for building the map.
|
inline |
Extracts an item from the map.
The function searches an item with key equal to key
in the map, unlinks it from the map, and returns exempt_ptr pointer to the item found. If the item with the key equal to key
is not found the function returns an empty exempt_ptr
.
Depends on ordered list you should or should not lock RCU before calling of this function:
|
inline |
Extracts an item from the map using pred
predicate for searching.
The function is an analog of extract(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 map.
|
inline |
Finds the key key
.
The function searches the item with key equal to key
and calls the functor f
for item found. The interface of Func
functor is:
where item
is the item found.
The functor may change item.second
. Note that the functor is only guarantee that item
cannot be disposed during functor is executing. The functor does not serialize simultaneous access to the map's item
. If such access is possible you must provide your own synchronization schema on item level 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 key
using pred
predicate for searching.
The function is an analog of find(K const&, Func) 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 map.
|
inline |
Finds key
and return the item found.
The function searches the item with key equal to key
and returns the pointer to item found. If key
is not found it returns empty raw_ptr
.
Note the compare functor should accept a parameter of type K
that can be not the same as value_type
.
RCU should be locked before call of this function. Returned item is valid only while RCU is locked:
|
inline |
Finds key
with predicate specified 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 value_type and K
in any order. pred
must imply the same element order as the comparator used for building the map.
|
inline |
Inserts new node with key and default value.
The function creates a node with key
and the default value, and then inserts the node created into the map.
Preconditions:
key_type
should be constructible from value of type K
.mapped_type
should be default-constructible.The function applies RCU lock internally.
Returns true
if inserting successful, false
otherwise.
|
inline |
Inserts new node.
The function creates a node with copy of val
value and then inserts the node into the map.
Preconditions:
key_type
should be constructible from key
of type K
.mapped_type
should be constructible from val
of type V
.The function applies RCU lock internally.
Returns true
if val
is inserted into the map, 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 map's item inserted:
item.first
is a const reference to item's key that cannot be changed.item.second
is a reference to item's value that may be changed.It should be keep in mind that concurrent modifications of
in item.second
func
body should be careful. You shouldf guarantee that during changing item's value in func
no any other changes could be made on this item
by concurrent threads.
func
is called only if inserting is successful.
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 |
Updates data by key
.
The operation performs inserting or replacing the element with lock-free manner.
If the key
not found in the map, then the new item created from key
will be inserted into the map 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
.
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.