cds
2.3.2
|
Ellen's et al binary search tree (RCU specialization) More...
#include <cds/intrusive/ellen_bintree_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 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 | |
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 = false |
Group of extract_xxx functions do not require external locking. | |
Protected Attributes | |
item_counter | m_ItemCounter |
item counter | |
stat | m_Stat |
internal statistics | |
Ellen's et al binary search tree (RCU specialization)
EllenBinTree 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 EllenBinTree
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. The type must be based on ellen_bintree::node
(for ellen_bintree::base_hook
) or it must have a member of type ellen_bintree::node
(for ellen_bintree::member_hook
).Traits
- tree traits, default is ellen_bintree::traits
It is possible to declare option-based tree with ellen_bintree::make_traits
metafunction instead of Traits
template argument.<cds/intrusive/ellen_bintree_rcu.h>
you should include appropriate RCU header file, see RCU type for list of existing RCU class and corresponding header files.Traits::less
, Traits::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:
Suppose we have the following Foo struct with string key type:
We want to utilize RCU-based cds::intrusive::EllenBinTree
set for Foo
data. We may use base hook or member hook. Consider base hook variant. First, we need deriving Foo
struct from cds::intrusive::ellen_bintree::node
:
Second, we need to implement auxiliary structures and functors:
Foo
object. Such functor is necessary because the tree internal nodes store the keys.less
predicate. We want our set should accept std::string
and char const *
parameters for searching, so our less
predicate will not be trivial, see below.size()
member function returns actual item count.Now we declare EllenBinTree
set and use it:
Instead of declaring set_traits
type traits we can use option-based syntax with ellen_bintree::make_traits
metafunction, for example:
Functionally, set_type
and set_type2
are equivalent.
Member-hooked tree
Sometimes, we cannot use base hook, for example, when the Foo
structure is external. In such case we can use member hook feature.
Multiple containers
Sometimes we need that our Foo
struct should be used in several different containers. Suppose, Foo
struct has two key fields:
We want to build two intrusive EllenBinTree
sets: one indexed on Foo::m_strKey
field, another indexed on Foo::m_nKey
field. To decide such case we should use a tag option for tree's hook:
|
inline |
Checks internal consistency (not atomic, not thread-safe)
The debugging function to check internal consistency of the tree.
|
inline |
Clears the tree (thread safe, not atomic)
The function unlink all items from the tree. The function is thread safe but not atomic: 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 |
Deletes the item from the tree.
The function searches an item with key equal to key
in the tree, unlinks it from the tree, and returns true
. If the item with key equal to key
is not found the function return false
.
Note the Traits::less
and/or Traits::compare
predicate should accept a parameter of type Q
that can be not the same as value_type
.
RCU synchronize
method can be called. RCU should not be locked.
|
inline |
Deletes the item from the tree.
The function searches an item with key equal to key
in the tree, call f
functor with item found, unlinks it from the tree, and returns true
. The disposer specified in Traits
class template parameter is called by garbage collector GC
asynchronously.
The Func
interface is
If the item with key equal to key
is not found the function return false
.
Note the Traits::less
and/or Traits::compare
predicate should accept a parameter of type Q
that can be not the same as value_type
.
RCU synchronize
method can be called. RCU should not be locked.
|
inline |
Delete the item from the tree with comparing functor pred
.
The function is an analog of erase(Q const&) but pred
predicate is used for key comparing. 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 tree.
|
inline |
Delete the item from the tree with comparing functor pred
.
The function is an analog of erase(Q const&, Func) but pred
predicate is used for key comparing. 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 tree.
|
inline |
Extracts an item from the tree.
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 the item with the key equal to key
is not found the function returns empty exempt_ptr
.
RCU synchronize
method can be called. RCU should NOT be locked. The function does not call the disposer for the item found. The disposer 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 tree.
The function searches an item with maximal key, unlinks it, and returns exempt_ptr pointer to the rightmost item. If the tree is empty the function returns empty exempt_ptr
.
RCU synchronize
method can be called. RCU should NOT be locked. The function does not call the disposer for the item found. The disposer 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 tree.
The function searches an item with minimal key, unlinks it, and returns exempt_ptr pointer to the leftmost item. If the tree is empty the function returns empty exempt_ptr
.
RCU synchronize
method can be called. RCU should NOT be locked. The function does not call the disposer for the item found. The disposer 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 tree.
|
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, key
is the find
function argument.
The functor can 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 tree 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
with comparing functor pred
.
The function is an analog of find(Q&, Func) but pred
is used for key comparison. Less
functor 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 tree.
|
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 tree.
|
inline |
Inserts new node.
The function inserts val
in the tree if it does not contain an item with key equal to val
.
The function applies RCU lock internally.
Returns true
if val
is placed into the set, false
otherwise.
|
inline |
Inserts new node.
This function is intended for derived non-intrusive containers.
The function allows to split creating of new item into two part:
f
functor to initialize value-field 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 tree's item by concurrent threads. The user-defined functor is called only if the inserting is success.
RCU synchronize
method can be called. RCU should not be locked.
|
inline |
Returns item count in the tree.
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 that.
|
inline |
Unlinks the item val
from the tree.
The function searches the item val
in the tree and unlink it from the tree if it is found and is equal to val
.
Difference between erase()
and unlink
() functions: erase
() finds a key and deletes the item found. unlink
() finds an item by key and deletes it only if val
is an item of the tree, i.e. the pointer to item found is equal to &val
.
RCU synchronize
method can be called. RCU should not be locked.
The disposer specified in Traits
class template parameter is called by garbage collector GC
asynchronously.
The function returns true
if success and false
otherwise.
|
inline |
Clears the tree (not thread safe)
This function is not thread safe and may be called only when no other thread deals with the tree. The function is used in the tree destructor.
|
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
() function If new item has been inserted (i.e. bNew
is true
) then item
and val
arguments refer to the same thing.The 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.