cds
2.3.2
|
Set based on Ellen's et al binary search tree (RCU specialization) More...
#include <cds/container/ellen_bintree_set_rcu.h>
Public Types | |
typedef cds::urcu::gc< RCU > | gc |
RCU Garbage collector. | |
typedef Key | key_type |
type of a key stored in internal nodes; key is a part of value_type | |
typedef T | value_type |
type of value stored in the binary tree | |
typedef Traits | traits |
Traits template parameter. | |
typedef implementation_defined | key_comparator |
key compare functor based on Traits::compare and Traits::less | |
typedef base_class::item_counter | item_counter |
Item counting policy. | |
typedef base_class::memory_model | memory_model |
Memory ordering, see cds::opt::memory_model . | |
typedef base_class::stat | stat |
internal statistics type | |
typedef base_class::rcu_check_deadlock | rcu_check_deadlock |
Deadlock checking policy. | |
typedef traits::key_extractor | key_extractor |
key extracting functor | |
typedef traits::back_off | back_off |
Back-off strategy. | |
typedef traits::allocator | allocator_type |
Allocator for leaf nodes. | |
typedef base_class::node_allocator | node_allocator |
Internal node allocator. | |
typedef base_class::update_desc_allocator | update_desc_allocator |
Update descriptor allocator. | |
typedef gc::scoped_lock | rcu_lock |
RCU scoped lock. | |
using | exempt_ptr = cds::urcu::exempt_ptr< gc, leaf_node, value_type, typename maker::intrusive_traits::disposer, cds::urcu::details::conventional_exempt_member_cast< leaf_node, value_type > > |
pointer to extracted node | |
Public Types inherited from cds::intrusive::EllenBinTree< 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 internal nodes; key is a part of value_type | |
typedef T | value_type |
type of value stored in the binary tree | |
typedef Traits | traits |
Traits template parameter. | |
typedef traits::hook | hook |
hook type | |
typedef hook::node_type | node_type |
node type | |
typedef traits::disposer | disposer |
leaf node disposer | |
typedef traits::back_off | back_off |
back-off strategy | |
using | exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void > |
pointer to extracted node | |
typedef implementation_defined | key_comparator |
key compare functor based on Traits::compare and Traits::less | |
typedef get_node_traits< value_type, node_type, hook >::type | node_traits |
Node traits. | |
typedef traits::item_counter | item_counter |
Item counting policy used. | |
typedef traits::memory_model | memory_model |
Memory ordering. See cds::opt::memory_model option. | |
typedef traits::stat | stat |
internal statistics type | |
typedef traits::rcu_check_deadlock | rcu_check_deadlock |
Deadlock checking policy. | |
typedef traits::key_extractor | key_extractor |
key extracting functor | |
typedef traits::node_allocator | node_allocator |
Internal node allocator. | |
typedef traits::update_desc_allocator | update_desc_allocator |
Update descriptor allocator. | |
typedef gc::scoped_lock | rcu_lock |
RCU scoped lock. | |
Public Member Functions | |
EllenBinTreeSet () | |
Default constructor. | |
~EllenBinTreeSet () | |
Clears the set. | |
template<typename Q > | |
bool | insert (Q const &val) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
bool | insert (Q const &val, Func f) |
Inserts new node. More... | |
template<typename Q , typename Func > | |
std::pair< bool, bool > | update (Q const &val, Func func, bool bAllowInsert=true) |
Updates the node. More... | |
template<typename... Args> | |
bool | emplace (Args &&... args) |
Inserts data of type value_type created in-place from args . More... | |
template<typename Q > | |
bool | erase (Q const &key) |
Delete key from the set. More... | |
template<typename Q , typename Less > | |
bool | erase_with (Q const &key, Less pred) |
Deletes the item from the set using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | erase (Q const &key, Func f) |
Delete key from the set. More... | |
template<typename Q , typename Less , typename Func > | |
bool | erase_with (Q const &key, Less pred, Func f) |
Deletes the item from the set using pred predicate for searching. More... | |
exempt_ptr | extract_min () |
Extracts an item with minimal key from the set. More... | |
exempt_ptr | extract_max () |
Extracts an item with maximal key from the set. More... | |
template<typename Q > | |
exempt_ptr | extract (Q const &key) |
Extracts an item from the set. More... | |
template<typename Q , typename Less > | |
exempt_ptr | extract_with (Q const &key, Less pred) |
Extracts an item from the set using pred for searching. More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) const |
Find the key key . More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &key, Less pred, Func f) const |
Finds the key key using pred predicate for searching. More... | |
template<typename Q > | |
bool | contains (Q const &key) const |
Checks whether the set contains key . More... | |
template<typename Q , typename Less > | |
bool | contains (Q const &key, Less pred) const |
Checks whether the set contains key using pred predicate for searching. More... | |
template<typename Q > | |
value_type * | get (Q const &key) const |
Finds key and return the item found. More... | |
template<typename Q , typename Less > | |
value_type * | get_with (Q const &key, Less pred) const |
Finds key with pred predicate and return the item found. More... | |
void | clear () |
Clears the set (non-atomic) More... | |
bool | empty () const |
Checks if the set is empty. | |
size_t | size () const |
Returns item count in the set. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
bool | check_consistency () const |
Checks internal consistency (not atomic, not thread-safe) More... | |
Public Member Functions inherited from cds::intrusive::EllenBinTree< cds::urcu::gc< RCU >, Key, T, Traits > | |
EllenBinTree () | |
Default constructor. | |
~EllenBinTree () | |
Clears the tree. | |
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 node. More... | |
bool | unlink (value_type &val) |
Unlinks the item val from the tree. More... | |
template<typename Q > | |
bool | erase (const Q &key) |
Deletes the item from the tree. More... | |
template<typename Q , typename Less > | |
bool | erase_with (const Q &key, Less pred) |
Delete the item from the tree with comparing functor pred . More... | |
template<typename Q , typename Func > | |
bool | erase (Q const &key, Func f) |
Deletes the item from the tree. More... | |
template<typename Q , typename Less , typename Func > | |
bool | erase_with (Q const &key, Less pred, Func f) |
Delete the item from the tree with comparing functor pred . More... | |
exempt_ptr | extract_min () |
Extracts an item with minimal key from the tree. More... | |
exempt_ptr | extract_max () |
Extracts an item with maximal key from the tree. More... | |
template<typename Q > | |
exempt_ptr | extract (Q const &key) |
Extracts an item from the tree. More... | |
template<typename Q , typename Less > | |
exempt_ptr | extract_with (Q const &key, Less pred) |
Extracts an item from the set using pred for searching. More... | |
template<typename Q > | |
bool | contains (Q const &key) const |
Checks whether the set contains key . More... | |
template<typename Q , typename Less > | |
bool | contains (Q const &key, Less pred) const |
Checks whether the set contains key using pred predicate for searching. More... | |
template<typename Q , typename Func > | |
bool | find (Q &key, Func f) const |
Finds the key key . More... | |
template<typename Q , typename Less , typename Func > | |
bool | find_with (Q &key, Less pred, Func f) const |
Finds the key key with comparing functor pred . More... | |
template<typename Q > | |
value_type * | get (Q const &key) const |
Finds key and return the item found. More... | |
template<typename Q , typename Less > | |
value_type * | get_with (Q const &key, Less pred) const |
Finds key with pred predicate and return the item found. More... | |
bool | empty () const |
Checks if the tree is empty. | |
void | clear () |
Clears the tree (thread safe, not atomic) More... | |
void | unsafe_clear () |
Clears the tree (not thread safe) More... | |
size_t | size () const |
Returns item count in the tree. More... | |
stat const & | statistics () const |
Returns const reference to internal statistics. | |
bool | check_consistency () const |
Checks internal consistency (not atomic, not thread-safe) More... | |
Static Public Attributes | |
static constexpr const bool | c_bExtractLockExternal = base_class::c_bExtractLockExternal |
Group of extract_xxx functions do not require external locking. | |
Static Public Attributes inherited from cds::intrusive::EllenBinTree< cds::urcu::gc< RCU >, Key, T, Traits > | |
static constexpr const bool | c_bExtractLockExternal = false |
Group of extract_xxx functions do not require external locking. | |
Additional Inherited Members | |
Protected Attributes inherited from cds::intrusive::EllenBinTree< cds::urcu::gc< RCU >, Key, T, Traits > | |
item_counter | m_ItemCounter |
item counter | |
stat | m_Stat |
internal statistics | |
Set based on Ellen's et al binary search tree (RCU specialization)
EllenBinTreeSet is an unbalanced leaf-oriented binary search tree that implements the set abstract data type. Nodes maintains child pointers but not parent pointers. Every internal node has exactly two children, and all data of type T
currently in the tree are stored in the leaves. Internal nodes of the tree are used to direct find
operation along the path to the correct leaf. The keys (of Key
type) stored in internal nodes may or may not be in the set. Key
type is a subset of T
type. There should be exactly defined a key extracting functor for converting object of type T
to object of type Key
.
Due to extract_min
and extract_max
member functions the EllenBinTreeSet
can act as a priority queue. In this case you should provide unique compound key, for example, the priority value plus some uniformly distributed random value.
O(log N)
for uniformly distributed random keys, but in the worst case the complexity is O(N)
.Template arguments :
RCU
- one of RCU typeKey
- key type, a subset of T
T
- type to be stored in tree's leaf nodes.Traits
- set traits, default is ellen_bintree::traits
. It is possible to declare option-based tree with ellen_bintree::make_set_traits
metafunction instead of Traits
template argument.<cds/container/ellen_bintree_set_rcu.h>
you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files.opt::less, opt::compare and other predicates using with member fuctions should accept at least parameters of type T
and Key
in any combination. For example, for Foo
struct with std::string
key field the appropiate less
functor is:
|
inline |
Checks internal consistency (not atomic, not thread-safe)
The debugging function to check internal consistency of the tree.
|
inline |
Clears the set (non-atomic)
The function unlink all items from the tree. The function is not atomic, thus, in multi-threaded environment with parallel insertions this sequence
the assertion could be raised.
For each leaf the disposer will be called after unlinking.
RCU synchronize
method can be called. RCU should not be locked.
|
inline |
Checks whether the set 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 set 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
and should meet Predicate requirements. Less
must imply the same element order as the comparator used for building the set. pred
should accept arguments of type Q
, key_type
, value_type
in any combination.
|
inline |
Inserts data of type value_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 |
|
inline |
Delete key
from the set.
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:
Since the key of MichaelHashSet's value_type
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
.
RCU synchronize
method can be called. RCU should not be locked.
Return true
if key is found and deleted, false
otherwise
See also: erase
|
inline |
Deletes the item from the set 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
. Less
must imply the same element order as the comparator used for building the set.
|
inline |
Deletes the item from the set 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
. Less
must imply the same element order as the comparator used for building the set.
|
inline |
Extracts an item from the set.
The function searches an item with key equal to key
in the tree, unlinks it, and returns exempt_ptr pointer to an item 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 item 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 set.
Returns exempt_ptr pointer to the rightmost item. If the set is empty, returns empty 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 an item with minimal key from the set.
Returns exempt_ptr pointer to the leftmost item. If the set is empty, returns empty 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 an item from the set 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
and should meet predicate requirements. pred
must imply the same element order as the comparator used for building the set.
|
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 item
is the item found, key
is the find
function argument.
The functor may change non-key fields of item
. 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 set's item
. If such access is possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
The key
argument is non-const since it can be used as f
functor destination i.e., the functor can modify both arguments.
Note the hash functor specified for class Traits
template parameter should accept a parameter of type Q
that may be not the same as value_type
.
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(Q&, 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 set.
|
inline |
|
inline |
Finds key
with pred
predicate 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 set.
|
inline |
Inserts new node.
The function creates a node with copy of val
value and then inserts the node created into the set.
The type Q
should contain at least the complete key for the node. The object of value_type should be constructible from a value of type Q
. In trivial case, Q
is equal to value_type.
RCU synchronize()
method can be called. RCU should not be locked.
Returns true
if val
is inserted into the set, false
otherwise.
|
inline |
Inserts new node.
The function allows to split creating of new item into two part:
f
functor to initialize value-fields of val
.The functor signature is:
where val
is the item inserted. User-defined functor f
should guarantee that during changing val
no any other changes could be made on this set's item by concurrent threads. The user-defined functor is called only if the inserting is success.
RCU synchronize()
can be called. RCU should not be locked.
|
inline |
Returns item count in the set.
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
size
() always returns 0. Therefore, the function is not suitable for checking the tree emptiness, use empty()
member function for this purpose.
|
inline |
Updates the node.
The operation performs inserting or changing data with lock-free manner.
If the item val
is not found in the set, then val
is inserted into the set iff bAllowInsert
is true
. 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
- item of the setval
- argument val
passed into the update
() functionThe functor can change non-key fields of the item
; however, func
must guarantee that during changing no any other modifications could be made on this item by concurrent threads.
RCU synchronize
method can be called. RCU should not be locked.
Returns std::pair<bool, bool> where first
is true
if operation is successful, i.e. the node has been inserted or updated, second
is true
if new item has been added or false
if the item with key
already exists.