cds
2.3.2
|
Bronson et al AVL-tree (RCU specialization) More...
#include <cds/container/bronson_avltree_map_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
RCU Garbage collector. | |
typedef Key | key_type |
type of a key stored in the map | |
typedef T | mapped_type |
type of value stored in the map | |
typedef Traits | traits |
Traits template parameter. | |
typedef base_class::key_comparator | key_comparator |
key compare functor based on Traits::compare and Traits::less | |
typedef traits::item_counter | item_counter |
Item counting policy. | |
typedef traits::memory_model | memory_model |
Memory ordering, see cds::opt::memory_model option. | |
typedef traits::allocator | allocator_type |
allocator for value | |
typedef traits::node_allocator | node_allocator_type |
allocator for maintaining internal nodes | |
typedef traits::stat | stat |
internal statistics | |
typedef traits::rcu_check_deadlock | rcu_check_deadlock |
Deadlock checking policy. | |
typedef traits::back_off | back_off |
Back-off strategy. | |
typedef traits::sync_monitor | sync_monitor |
Synchronization monitor type for node-level locking | |
typedef base_class::rcu_lock | rcu_lock |
RCU scoped lock. | |
typedef base_class::exempt_ptr | exempt_ptr |
Returned pointer to mapped_type of extracted node. | |
Public Member Functions | |
BronsonAVLTreeMap () | |
Creates empty map. | |
~BronsonAVLTreeMap () | |
Destroys the map. | |
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 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 the value for key . More... | |
template<typename K > | |
bool | erase (K const &key) |
Delete 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) |
Delete 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... | |
exempt_ptr | extract_min () |
Extracts a value with minimal key from the map. More... | |
template<typename Func > | |
exempt_ptr | extract_min (Func f) |
Extracts minimal key and corresponding value. More... | |
std::enable_if< std::is_copy_assignable< key_type >::value, exempt_ptr >::type | extract_min_key (key_type &min_key) |
Extracts minimal key and corresponding value. More... | |
exempt_ptr | extract_max () |
Extracts an item with maximal key from the map. More... | |
template<typename Func > | |
exempt_ptr | extract_max (Func f) |
Extracts the maximal key and corresponding value. More... | |
std::enable_if< std::is_copy_assignable< key_type >::value, exempt_ptr >::type | extract_max_key (key_type &max_key) |
Extracts the maximal key and corresponding value. More... | |
template<typename Q > | |
exempt_ptr | extract (Q const &key) |
Extracts an item from the map. More... | |
template<typename Q , typename Less > | |
exempt_ptr | extract_with (Q const &key, Less pred) |
Extracts an item from the map using pred for searching. More... | |
template<typename K , typename Func > | |
bool | find (K const &key, Func f) |
Find the key key . More... | |
template<typename K , typename Less , typename Func > | |
bool | find_with (K const &key, Less pred, Func f) |
Finds the key val 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... | |
void | clear () |
Clears the map. | |
bool | empty () const |
Checks if the map is empty. | |
size_t | size () const |
Returns item count in the map. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
sync_monitor & | monitor () |
Returns reference to sync_monitor object. | |
bool | check_consistency () const |
Checks internal consistency (not atomic, not thread-safe) More... | |
template<typename Func > | |
bool | check_consistency (Func f) const |
Checks internal consistency (not atomic, not thread-safe) More... | |
Static Public Attributes | |
static bool const | c_bRelaxedInsert = traits::relaxed_insert |
Enabled or disabled relaxed insertion. | |
static constexpr const bool | c_bExtractLockExternal = base_class::c_bExtractLockExternal |
Group of extract_xxx functions does not require external locking. | |
Additional Inherited Members | |
Private Types inherited from cds::container::BronsonAVLTreeMap< cds::urcu::gc< RCU >, Key, T *, Traits > | |
typedef cds::urcu::gc< RCU > | gc |
RCU Garbage collector. | |
typedef Key | key_type |
type of a key stored in the map | |
typedef T * | mapped_type |
type of value stored in the map | |
typedef Traits | traits |
Traits template parameter. | |
typedef implementation_defined | key_comparator |
key compare functor based on Traits::compare and Traits::less | |
typedef traits::item_counter | item_counter |
Item counting policy. | |
typedef traits::memory_model | memory_model |
Memory ordering, see cds::opt::memory_model option. | |
typedef traits::node_allocator | node_allocator_type |
allocator for maintaining internal nodes | |
typedef traits::stat | stat |
internal statistics | |
typedef traits::rcu_check_deadlock | rcu_check_deadlock |
Deadlock checking policy. | |
typedef traits::back_off | back_off |
Back-off strategy. | |
typedef traits::disposer | disposer |
Value disposer. | |
typedef traits::sync_monitor | sync_monitor |
Synchronization monitor type for node-level locking | |
typedef cds::urcu::exempt_ptr< gc, T, T, disposer, void > | exempt_ptr |
Returned pointer to mapped_type of extracted node. | |
typedef gc::scoped_lock | rcu_lock |
RCU scoped lock. | |
Private Member Functions inherited from cds::container::BronsonAVLTreeMap< cds::urcu::gc< RCU >, Key, T *, Traits > | |
BronsonAVLTreeMap () | |
Creates empty map. | |
~BronsonAVLTreeMap () | |
Destroys the map. | |
template<typename K > | |
bool | insert (K const &key, mapped_type pVal) |
Inserts new node. More... | |
template<typename K > | |
std::pair< bool, bool > | update (K const &key, mapped_type pVal, bool bInsert=true) |
Updates the value for key . More... | |
template<typename K > | |
bool | erase (K const &key) |
Delete 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) |
Delete 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... | |
exempt_ptr | extract_min () |
Extracts a value with minimal key from the map. More... | |
template<typename Func > | |
exempt_ptr | extract_min (Func f) |
Extracts minimal key and corresponding value. More... | |
std::enable_if< std::is_copy_assignable< key_type >::value, exempt_ptr >::type | extract_min_key (key_type &min_key) |
Extracts minimal key and corresponding value. More... | |
exempt_ptr | extract_max () |
Extracts a value with maximal key from the tree. More... | |
template<typename Func > | |
exempt_ptr | extract_max (Func f) |
Extracts the maximal key and corresponding value. More... | |
std::enable_if< std::is_copy_assignable< key_type >::value, exempt_ptr >::type | extract_max_key (key_type &max_key) |
Extracts the maximal key and corresponding value. More... | |
template<typename Q > | |
exempt_ptr | extract (Q const &key) |
Extracts an item from the map. More... | |
template<typename Q , typename Less > | |
exempt_ptr | extract_with (Q const &key, Less pred) |
Extracts an item from the map using pred for searching. More... | |
template<typename K , typename Func > | |
bool | find (K const &key, Func f) |
Find the key key . More... | |
template<typename K , typename Less , typename Func > | |
bool | find_with (K const &key, Less pred, Func f) |
Finds the key val 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... | |
void | clear () |
Clears the tree (thread safe, not atomic) More... | |
void | unsafe_clear () |
Clears the tree (not thread safe) More... | |
bool | empty () const |
Checks if the map is empty. | |
size_t | size () const |
Returns item count in the map. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
sync_monitor & | monitor () |
Returns reference to sync_monitor object. | |
bool | check_consistency () const |
Checks internal consistency (not atomic, not thread-safe) More... | |
template<typename Func > | |
bool | check_consistency (Func f) const |
Checks internal consistency (not atomic, not thread-safe) More... | |
Static Private Attributes inherited from cds::container::BronsonAVLTreeMap< cds::urcu::gc< RCU >, Key, T *, Traits > | |
static constexpr bool const | c_bRelaxedInsert = traits::relaxed_insert |
Enabled or disabled relaxed insertion. | |
static constexpr const bool | c_bExtractLockExternal = false |
Group of extract_xxx functions does not require external locking. | |
Bronson et al AVL-tree (RCU specialization)
This is a concurrent AVL tree algorithm that uses hand-over-hand optimistic validation, a concurrency control mechanism for searching and navigating a binary search tree. This mechanism minimizes spurious retries when concurrent structural changes cannot affect the correctness of the search or navigation result. The algorithm is based on partially external trees, a simple scheme that simplifies deletions by leaving a routing node in the tree when deleting a node that has two children, then opportunistically unlinking routing nodes during rebalancing. As in external trees, which store values only in leaf nodes, deletions can be performed locally while holding a fixed number of locks. Partially external trees, however, require far fewer routing nodes than an external tree for most sequences of insertions and deletions. The algorithm uses optimistic concurrency control, but carefully manage the tree in such a way that all atomic regions have fixed read and write sets that are known ahead of time. This allows to reduce practical overheads by embedding the concurrency control directly. To perform tree operations using only fixed sized atomic regions the algo uses the following mechanisms: search operations overlap atomic blocks as in the hand-over-hand locking technique; mutations perform rebalancing separately; and deletions occasionally leave a routing node in the tree.
Template arguments:
RCU
- one of RCU typeKey
- key typeT
- value type to be stored in tree's nodes.Traits
- tree traits, default is bronson_avltree::traits
It is possible to declare option-based tree with bronson_avltree::make_traits
metafunction instead of Traits
template argument.There is a specialization for "key -> value pointer" map.
<cds/container/bronson_avltree_map_rcu.h>
you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files.
|
inline |
Checks internal consistency (not atomic, not thread-safe)
The debugging function to check internal consistency of the tree.
|
inline |
Checks internal consistency (not atomic, not thread-safe)
The debugging function to check internal consistency of the tree. The functor Func
is called if a violation of internal tree structure is found:
where
nLevel
- the level where the violation is foundhLeft
- the height of left subtreehRight
- the height of right subtreeThe functor is called for each violation found.
|
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 similar to 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 set.
|
inline |
For key
inserts data of type mapped_type
created in-place from args
.
Returns true
if inserting successful, false
otherwise.
RCU synchronize()
method can be called. RCU should not be locked.
|
inline |
Delete key
from the map.
RCU synchronize()
method can be called. RCU should not be locked.
Return true
if key
is found and deleted, false
otherwise
|
inline |
Delete 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:
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 tree, unlinks it, and returns exempt_ptr
pointer to a value found. If key
is not found the function returns an empty exempt_ptr
.
RCU synchronize
method can be called. RCU should NOT be locked. The function does not destroy the value found. The dealloctor will be implicitly invoked when the returned object is destroyed or when its release()
member function is called.
|
inline |
Extracts an item with maximal key from the map.
Returns exempt_ptr
pointer to the rightmost item. If the set is empty, returns empty exempt_ptr
.
Note that the function returns only the value for maximal key. To retrieve its key use extract_max( Func )
or extract_max_key(key_type&)
member function.
RCU synchronize
method can be called. RCU should NOT be locked. The function does not free the item. The deallocator will be implicitly invoked when the returned object is destroyed or when its release()
is called.
|
inline |
Extracts the maximal key and corresponding value.
Returns exempt_ptr
pointer to the rightmost item. If the set is empty, returns empty exempt_ptr
.
Func
functor is used to store maximal key. Func
has the following signature:
If the tree is empty, f
is not called. Otherwise, is it called with maximal key, the pointer to corresponding value is returned as exempt_ptr
.
RCU synchronize
method can be called. RCU should NOT be locked. The function does not free the item. The deallocator will be implicitly invoked when the returned object is destroyed or when its release()
is called.
|
inline |
Extracts the maximal key and corresponding value.
This function is a shortcut for the following call:
key_type
should be copy-assignable. The copy of maximal key is returned in max_key
argument.
|
inline |
Extracts a value with minimal key from the map.
Returns exempt_ptr
pointer to the leftmost item. If the set is empty, returns empty exempt_ptr
.
Note that the function returns only the value for minimal key. To retrieve its key use extract_min( Func )
member function.
RCU synchronize
method can be called. RCU should NOT be locked. The function does not free the item. The deallocator will be implicitly invoked when the returned object is destroyed or when its release()
member function is called.
|
inline |
Extracts minimal key and corresponding value.
Returns exempt_ptr
to the leftmost item. If the tree is empty, returns empty exempt_ptr
.
Func
functor is used to store minimal key. Func
has the following signature:
If the tree is empty, f
is not called. Otherwise, is it called with minimal key, the pointer to corresponding value is returned as exempt_ptr
.
RCU synchronize
method can be called. RCU should NOT be locked. The function does not free the item. The deallocator will be implicitly invoked when the returned object is destroyed or when its release()
member function is called.
|
inline |
Extracts minimal key and corresponding value.
This function is a shortcut for the following call:
key_type
should be copy-assignable. The copy of minimal key is returned in min_key
argument.
|
inline |
Extracts an item from the map using pred
for searching.
The function is an analog of extract(Q const&)
but pred
is used for key compare. Less
has the interface like std::less
. pred
must imply the same element order as the comparator used for building the map.
|
inline |
Find 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 val
is the item found for key
The functor is called under node-level lock.
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(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 |
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 a value of type K
.mapped_type
should be default-constructible.RCU synchronize()
can be called. RCU should not be locked.
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 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
.RCU synchronize()
method can be called. RCU should not be locked.
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 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 value_type
is heavyweight and it is preferable that the initialization should be completed only if inserting is successful. The functor is called under the node lock.
RCU synchronize()
method can be called. RCU should not be locked.
|
inline |
Returns item count in the map.
Only leaf nodes containing user data are counted.
The value returned depends on item counter type provided by Traits
template parameter. If it is atomicity::empty_item_counter
this function always returns 0.
The function is not suitable for checking the tree emptiness, use empty()
member function for this purpose.
|
inline |
Updates the value for key
.
The operation performs inserting or changing data 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, 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
- valueThe functor may change any fields of the item
. The functor is called under the node lock, the caller can change any field of item
.
RCU synchronize()
method can be called. RCU should not be locked.
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.