Implements a Red-Black Tree ADT, according to T. H. Corman, C. E. Leiserson, and R. L. Rivest, "Introduction to Algorithms" 1990, MIT, chapter 14.
More...
|
| ACE_RB_Tree (ACE_Allocator *alloc=0) |
| Constructor. More...
|
|
| ACE_RB_Tree (const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > &rbt) |
| Copy constructor. More...
|
|
int | open (ACE_Allocator *alloc=0) |
| Initialize an RB Tree. More...
|
|
int | close (void) |
|
virtual | ~ACE_RB_Tree (void) |
| Destructor. More...
|
|
int | bind (const EXT_ID &item, const INT_ID &int_id) |
|
int | bind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry) |
|
int | trybind (const EXT_ID &ext_id, INT_ID &int_id) |
|
int | trybind (const EXT_ID &ext_id, INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry) |
|
int | rebind (const EXT_ID &ext_id, const INT_ID &int_id) |
|
int | rebind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry) |
|
int | rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id) |
|
int | rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry) |
|
int | rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id) |
|
int | rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry) |
|
int | find (const EXT_ID &ext_id, INT_ID &int_id) |
|
int | find (const EXT_ID &ext_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry) |
|
int | unbind (const EXT_ID &ext_id) |
|
int | unbind (const EXT_ID &ext_id, INT_ID &int_id) |
|
int | unbind (ACE_RB_Tree_Node< EXT_ID, INT_ID > *entry) |
|
size_t | current_size (void) const |
| Returns the current number of nodes in the tree. More...
|
|
void | operator= (const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > &rbt) |
| Assignment operator. More...
|
|
ACE_LOCK & | mutex (void) |
|
void | dump (void) const |
| Dump the state of an object. More...
|
|
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | begin (void) |
| Return forward iterator positioned at first node in tree. More...
|
|
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | end (void) |
| Return forward iterator positioned at last node in tree. More...
|
|
ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | rbegin (void) |
| Return reverse iterator positioned at last node in tree. More...
|
|
ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | rend (void) |
| Return reverse iterator positioned at first node in tree. More...
|
|
int | test_invariant (void) |
| Tests the red-black invariant(s) throughout the whole tree. More...
|
|
INT_ID * | find (const EXT_ID &k) |
|
INT_ID * | insert (const EXT_ID &k, const INT_ID &t) |
|
int | remove (const EXT_ID &k) |
|
void | clear (void) |
|
ACE_Allocator * | allocator (void) const |
| Get the allocator;. More...
|
|
|
| ACE_RB_Tree (void *location, ACE_Allocator *alloc) |
| Reinitialize constructor. More...
|
|
int | test_invariant_recurse (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x, int &expected_black_height, int measured_black_height) |
| Recursive function to test the red-black invariant(s) at all nodes in a subtree. More...
|
|
void | RB_rotate_right (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) |
| Method for right rotation of the tree about a given node. More...
|
|
void | RB_rotate_left (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) |
| Method for left rotation of the tree about a given node. More...
|
|
void | RB_delete_fixup (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x, ACE_RB_Tree_Node< EXT_ID, INT_ID > *parent) |
| Method for restoring Red-Black properties after deletion. More...
|
|
ACE_RB_Tree_Node< EXT_ID, INT_ID > * | RB_tree_successor (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const |
| Method to find the successor node of the given node in the tree. More...
|
|
ACE_RB_Tree_Node< EXT_ID, INT_ID > * | RB_tree_predecessor (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const |
|
ACE_RB_Tree_Node< EXT_ID, INT_ID > * | RB_tree_minimum (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const |
|
ACE_RB_Tree_Node< EXT_ID, INT_ID > * | RB_tree_maximum (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const |
|
ACE_RB_Tree_Node< EXT_ID, INT_ID > * | find_node (const EXT_ID &k, ACE_RB_Tree_Base::RB_SearchResult &result) |
|
void | RB_rebalance (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) |
| Rebalance the tree after insertion of a node. More...
|
|
void | delete_children_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *parent) |
|
int | close_i (void) |
|
int | find_i (const EXT_ID &ext_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry, int find_exact=1) |
|
INT_ID * | insert_i (const EXT_ID &k, const INT_ID &t) |
|
int | insert_i (const EXT_ID &k, const INT_ID &t, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry) |
|
int | remove_i (const EXT_ID &k, INT_ID &i) |
|
int | remove_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *z) |
|
void | dump_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *node) const |
| Recursive function to dump the state of an object. More...
|
|
void | dump_node_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > &node) const |
|
int | lessthan (const EXT_ID &k1, const EXT_ID &k2) |
| Less than comparison function for keys, using comparison functor. More...
|
|
template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
class ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >
Implements a Red-Black Tree ADT, according to T. H. Corman, C. E. Leiserson, and R. L. Rivest, "Introduction to Algorithms" 1990, MIT, chapter 14.
A number of Changes have been made to this class template in order to conform to the ACE_Hash_Map_Manager_Ex interface. All previously supported public methods are still part of this class. However, these are marked as DEPRECATED and will be removed from this class in a future version of ACE. Please migrate your code to the appropriate public methods indicated in the method deprecation comments. This class uses an ACE_Allocator to allocate memory. The user can make this a persistent class by providing an ACE_Allocator with a persistable memory pool.
Requirements and Performance Characteristics
- Internal Structure: Binary tree
- Duplicates allowed? No
- Random access allowed? No
- Search speed: Log(n)
- Insert/replace speed: Log(n)
- Iterator still valid after change to container? Yes, except if the iterated-over element is removed.
- Frees memory for removed elements? Yes
- Items inserted by: Value
- Requirements for contained type
- Default constructor
- Copy constructor
- operator=
- operator==
- operator<
template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
Function to dump node contents. Does nothing in its basic form, but template specialization can be used to provide definitions for various EXT_ID and INT_ID types.
Function to dump node itself. Does not show parameterized node contents in its basic form, but template specialization can be used to provide definitions for various EXT_ID and INT_ID types.
template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
Returns a pointer to a matching node if there is one, a pointer to the node under which to insert the item if the tree is not empty and there is no such match, or 0 if the tree is empty. It stores the result of the search in the result argument: LEFT if the node is to the left of the node to be inserted, RIGHT if the node is to the right of the node to be inserted, or EXACT if an exactly matching node already exists.
template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i |
( |
const EXT_ID & |
k, |
|
|
const INT_ID & |
t, |
|
|
ACE_RB_Tree_Node< EXT_ID, INT_ID > *& |
entry |
|
) |
| |
|
protected |
Inserts a copy of the key and the item into the tree: both the key type EXT_ID and the item type INT_ID must have well defined semantics for copy construction. The default implementation also requires that the key type support well defined < semantics. This method passes back a pointer to the inserted (or existing) node, and the search status. If the node already exists, the method returns 1. If the node does not exist, and a new one is successfully created, and the method returns 0. If there was an error, the method returns -1.
template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind |
( |
const EXT_ID & |
ext_id, |
|
|
const INT_ID & |
int_id, |
|
|
INT_ID & |
old_int_id |
|
) |
| |
|
inline |
Associate ext_id with int_id. If ext_id is not in the tree then behaves just like <bind>. Otherwise, store the old value of int_id into the "out" parameter and rebind the new parameters. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur.
template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind |
( |
const EXT_ID & |
ext_id, |
|
|
const INT_ID & |
int_id, |
|
|
EXT_ID & |
old_ext_id, |
|
|
INT_ID & |
old_int_id |
|
) |
| |
|
inline |
Associate ext_id with int_id. If ext_id is not in the tree then behaves just like <bind>. Otherwise, store the old values of ext_id and int_id into the "out" parameters and rebind the new parameters. This is very useful if you need to have an atomic way of updating <ACE_RB_Tree_Nodes> and you also need full control over memory allocation. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur.
template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::test_invariant |
( |
void |
| ) |
|
Tests the red-black invariant(s) throughout the whole tree.
Recursively tests the invariant red-black properties at each node of the tree. Returns 0 if invariant holds, else -1. This method is computationally expensive, and should only be called for testing purposes, and not in code that depends on the algorithmic complexity bounds provided by the other methods.