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...
#include <RB_Tree.h>
Public Types | |
typedef EXT_ID | KEY |
typedef INT_ID | VALUE |
typedef ACE_LOCK | lock_type |
typedef ACE_RB_Tree_Node < EXT_ID, INT_ID > | ENTRY |
typedef ACE_RB_Tree_Iterator < EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | ITERATOR |
typedef ACE_RB_Tree_Reverse_Iterator < EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | REVERSE_ITERATOR |
typedef ACE_RB_Tree_Iterator < EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | iterator |
typedef ACE_RB_Tree_Reverse_Iterator < EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | reverse_iterator |
Public Member Functions | |
ACE_RB_Tree (ACE_Allocator *alloc=0) | |
Constructor. | |
ACE_RB_Tree (const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > &rbt) | |
Copy constructor. | |
int | open (ACE_Allocator *alloc=0) |
Initialize an RB Tree. | |
int | close (void) |
virtual | ~ACE_RB_Tree (void) |
Destructor. | |
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. | |
void | operator= (const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > &rbt) |
Assignment operator. | |
ACE_LOCK & | mutex (void) |
void | dump (void) const |
Dump the state of an object. | |
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | begin (void) |
Return forward iterator positioned at first node in tree. | |
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | end (void) |
Return forward iterator positioned at last node in tree. | |
ACE_RB_Tree_Reverse_Iterator < EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | rbegin (void) |
Return reverse iterator positioned at last node in tree. | |
ACE_RB_Tree_Reverse_Iterator < EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > | rend (void) |
Return reverse iterator positioned at first node in tree. | |
int | test_invariant (void) |
Tests the red-black invariant(s) throughout the whole tree. | |
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) |
Protected Member Functions | |
ACE_RB_Tree (void *location, ACE_Allocator *alloc) | |
Reinitialize constructor. | |
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. | |
void | RB_rotate_right (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) |
Method for right rotation of the tree about a given node. | |
void | RB_rotate_left (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) |
Method for left rotation of the tree about a given node. | |
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. | |
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. | |
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. | |
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. | |
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. | |
Private Attributes | |
ACE_LOCK | lock_ |
Synchronization variable for the MT_SAFE ACE_RB_Tree. | |
ACE_RB_Tree_Node< EXT_ID, INT_ID > * | root_ |
The root of the tree. | |
COMPARE_KEYS | compare_keys_ |
Comparison functor for comparing nodes in the tree. | |
size_t | current_size_ |
The current number of nodes in the tree. | |
Friends | |
class | ACE_RB_Tree_Iterator_Base< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > |
class | ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > |
class | ACE_RB_Tree_Reverse_Iterator< 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
Definition at line 185 of file RB_Tree.h.
typedef ACE_RB_Tree_Node<EXT_ID, INT_ID> ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ENTRY |
typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ITERATOR |
typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::iterator |
typedef EXT_ID ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::KEY |
typedef ACE_LOCK ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::lock_type |
typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::reverse_iterator |
typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::REVERSE_ITERATOR |
typedef INT_ID ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::VALUE |
ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ACE_RB_Tree | ( | ACE_Allocator * | alloc = 0 |
) |
Constructor.
Definition at line 48 of file RB_Tree.cpp.
: root_ (0), current_size_ (0) { ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::" "ACE_RB_Tree (ACE_Allocator *alloc)"); allocator_ = alloc; if (this->open (alloc) == -1) ACE_ERROR ((LM_ERROR, ACE_TEXT ("ACE_RB_Tree::ACE_RB_Tree\n"))); }
ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ACE_RB_Tree | ( | const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > & | rbt | ) |
Copy constructor.
Definition at line 63 of file RB_Tree.cpp.
: root_ (0), current_size_ (0) { ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::" "ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)"); ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_); allocator_ = rbt.allocator_; // Make a deep copy of the passed tree. ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt); for (iter.first (); iter.is_done () == 0; iter.next ()) insert_i (*(iter.key ()), *(iter.item ())); }
ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::~ACE_RB_Tree | ( | void | ) | [virtual] |
Destructor.
Definition at line 99 of file RB_Tree.cpp.
ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ACE_RB_Tree | ( | void * | location, | |
ACE_Allocator * | alloc | |||
) | [protected] |
Reinitialize constructor.
This constructor is used to provide a valid vtable and allocator if the tree is reconstructed from shared memory. Constructor used by the derived class that has an allocator
Definition at line 83 of file RB_Tree.cpp.
{ if (location != this) { this->root_ = 0; this->current_size_ = 0; } this->allocator_ = alloc; }
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::begin | ( | void | ) |
Return forward iterator positioned at first node in tree.
Definition at line 594 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::begin"); return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this); }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::bind | ( | const EXT_ID & | item, | |
const INT_ID & | int_id | |||
) |
Associate ext_id with int_id. If ext_id is already in the tree then the <ACE_RB_Tree_Node> is not changed. Returns 0 if a new entry is bound successfully, returns 1 if an attempt is made to bind an existing entry, and returns -1 if failures occur.
Definition at line 176 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::bind (const EXT_ID &item, const INT_ID &int_id)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry; return this->insert_i (ext_id, int_id, entry); }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::bind | ( | const EXT_ID & | ext_id, | |
const INT_ID & | int_id, | |||
ACE_RB_Tree_Node< EXT_ID, INT_ID > *& | entry | |||
) |
Same as a normal bind, except the tree entry is also passed back to the caller. The entry in this case will either be the newly created entry, or the existing one.
Definition at line 193 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::bind (const EXT_ID &ext_id, const INT_ID &int_id, " "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); return this->insert_i (ext_id, int_id, entry); }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::clear | ( | void | ) |
Definition at line 707 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear"); ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_); this->close_i (); }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close | ( | void | ) |
Close down an RB_Tree and release dynamically allocated resources.
Definition at line 160 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); return this->close_i (); }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close_i | ( | void | ) | [protected] |
Close down an RB_Tree. this method should only be called with locks already held.
Definition at line 565 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i"); this->delete_children_i (this->root_); ACE_DES_FREE_TEMPLATE2 (this->root_, this->allocator()->free, ACE_RB_Tree_Node, EXT_ID, INT_ID); this->current_size_ = 0; this->root_ = 0; return 0; }
size_t ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::current_size | ( | void | ) | const |
Returns the current number of nodes in the tree.
Definition at line 719 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::current_size"); return current_size_; }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::delete_children_i | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | parent | ) | [protected] |
Delete children (left and right) of the node. Must be called with lock held.
Definition at line 539 of file RB_Tree.cpp.
{ if (parent) { this->delete_children_i (parent->left ()); this->delete_children_i (parent->right ()); ACE_DES_FREE_TEMPLATE2 (parent->left (), this->allocator_->free, ACE_RB_Tree_Node, EXT_ID, INT_ID); ACE_DES_FREE_TEMPLATE2 (parent->right (), this->allocator_->free, ACE_RB_Tree_Node, EXT_ID, INT_ID); parent->left (0); parent->right (0); } return; }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::dump | ( | void | ) | const |
Dump the state of an object.
Definition at line 575 of file RB_Tree.inl.
{ #if defined (ACE_HAS_DUMP) ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump"); ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\ncurrent_size_ = %d\n"), this->current_size_)); this->allocator_->dump (); this->lock_.dump (); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nDumping nodes from root\n"))); this->dump_i (this->root_); ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); #endif /* ACE_HAS_DUMP */ }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::dump_i | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | node | ) | const [protected] |
Recursive function to dump the state of an object.
Definition at line 862 of file RB_Tree.cpp.
{ #if defined (ACE_HAS_DUMP) if (node) { dump_node_i (*node); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\ndown left\n"))); this->dump_i (node->left ()); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nup left\n"))); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\ndown right\n"))); this->dump_i (node->right ()); ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nup right\n"))); } else { ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nNULL POINTER (BLACK)\n"))); } #else /* !ACE_HAS_DUMP */ ACE_UNUSED_ARG (node); #endif /* ACE_HAS_DUMP */ }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::dump_node_i | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > & | node | ) | const [protected] |
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.
Definition at line 892 of file RB_Tree.cpp.
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::end | ( | void | ) |
Return forward iterator positioned at last node in tree.
Definition at line 606 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::end"); return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (); }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find | ( | const EXT_ID & | ext_id, | |
INT_ID & | int_id | |||
) |
Locate ext_id and pass out parameter via int_id. If found, return 0, returns -1 if not found.
Definition at line 438 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::find (const EXT_ID &ext_id, INT_ID &int_id)"); ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry = 0; int result = this->find_i (ext_id, entry); if (result == 0) { int_id = entry->item (); } return result; }
INT_ID * ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find | ( | const EXT_ID & | k | ) |
Returns a pointer to the item corresponding to the given key, or 0 if it cannot find the key in the tree.
Definition at line 643 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &k)"); // The reinterpret cast is to ensure that when this deprecated // method is removed, and is replaced (as planned) by a find method // that takes the same argument signature but returns an int, that // the compiler will cough if this return macro is not changed to // just return an int (whose value will be -1). Please leave this // as is. ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, reinterpret_cast<INT_ID*> (0L)); ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry = 0; int result = this->find_i (k, entry); return (result == 0) ? &(entry->item ()) : 0; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find | ( | const EXT_ID & | ext_id, | |
ACE_RB_Tree_Node< EXT_ID, INT_ID > *& | entry | |||
) |
Locate ext_id and pass out parameter via entry. If found, return 0, returns -1 if not found.
Definition at line 460 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::find (const EXT_ID &ext_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)"); ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); return this->find_i (ext_id, entry); }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_i | ( | const EXT_ID & | ext_id, | |
ACE_RB_Tree_Node< EXT_ID, INT_ID > *& | entry, | |||
int | find_exact = 1 | |||
) | [protected] |
Retrieves a pointer to the item corresponding to the given key. If find_exact==1, find the exact match node, otherwise just find a match node Returns 0 for success, or -1 if it cannot find the key in the tree.
Definition at line 584 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_i"); // Try to find a match. RB_SearchResult result = LEFT; ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result); if (current) { // Found a match if (!find_exact || result == EXACT) entry = current; // Assign the entry for any match. return (result == EXACT ? 0 : -1); } else // The node is not there. return -1; }
ACE_RB_Tree_Node< EXT_ID, INT_ID > * ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_node | ( | const EXT_ID & | k, | |
ACE_RB_Tree_Base::RB_SearchResult & | result | |||
) | [protected] |
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.
Definition at line 336 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node"); // Start at the root. ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = root_; while (current) { // While there are more nodes to examine. if (this->lessthan (current->key (), k)) { // If the search key is greater than the current node's key. if (current->right ()) // If the right subtree is not empty, search to the right. current = current->right (); else { // If the right subtree is empty, we're done searching, // and are positioned to the left of the insertion point. result = LEFT; break; } } else if (this->lessthan (k, current->key ())) { // Else if the search key is less than the current node's key. if (current->left ()) // If the left subtree is not empty, search to the left. current = current->left (); else { // If the left subtree is empty, we're done searching, // and are positioned to the right of the insertion point. result = RIGHT; break; } } else { // If the keys match exactly, we're done as well. result = EXACT; break; } } return current; }
INT_ID * ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert | ( | const EXT_ID & | k, | |
const INT_ID & | t | |||
) |
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 returns a pointer to the inserted item copy, or 0 if an error occurred.
Definition at line 674 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, reinterpret_cast<INT_ID*> (0L)); return this->insert_i (k, t); }
INT_ID * ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i | ( | const EXT_ID & | k, | |
const INT_ID & | t | |||
) | [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 returns a pointer to the inserted item copy, or 0 if an error occurred.
Definition at line 615 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t)"); // Find the closest matching node, if there is one. RB_SearchResult result = LEFT; ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result); if (current) { // If the keys match, just return a pointer to the node's item. if (result == EXACT) return ¤t->item (); // Otherwise if we're to the left of the insertion point, insert // into the right subtree. else if (result == LEFT) { if (current->right ()) { // If there is already a right subtree, complain. ACE_ERROR_RETURN ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nright subtree already present in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), 0); } else { // The right subtree is empty: insert new node there. ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0; ACE_NEW_MALLOC_RETURN (tmp, (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*> (this->allocator_->malloc (sizeof (*tmp)))), (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t), 0); current->right (tmp); // If the node was successfully inserted, set its // parent, rebalance the tree, color the root black, and // return a pointer to the inserted item. INT_ID *item = &(current->right ()->item ()); current->right ()->parent (current); RB_rebalance (current->right ()); root_->color (ACE_RB_Tree_Node_Base::BLACK); ++current_size_; return item; } } // Otherwise, we're to the right of the insertion point, so // insert into the left subtree. else // (result == RIGHT) { if (current->left ()) // If there is already a left subtree, complain. ACE_ERROR_RETURN ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nleft subtree already present in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), 0); else { // The left subtree is empty: insert new node there. ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0; ACE_NEW_MALLOC_RETURN (tmp, (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*> (this->allocator_->malloc (sizeof (*tmp)))), (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t), 0); current->left (tmp); // If the node was successfully inserted, set its // parent, rebalance the tree, color the root black, and // return a pointer to the inserted item. INT_ID *item = ¤t->left ()->item (); current->left ()->parent (current); RB_rebalance (current->left ()); root_->color (ACE_RB_Tree_Node_Base::BLACK); ++current_size_; return item; } } } else { // The tree is empty: insert at the root and color the root // black. ACE_NEW_MALLOC_RETURN (this->root_, (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*> (this->allocator_->malloc (sizeof (ACE_RB_Tree_Node<EXT_ID, INT_ID>)))), (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t), 0); this->root_->color (ACE_RB_Tree_Node_Base::BLACK); ++current_size_; return &this->root_->item (); } }
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.
Definition at line 727 of file RB_Tree.cpp.
{ ACE_TRACE ("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)"); // Find the closest matching node, if there is one. RB_SearchResult result = LEFT; ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result); if (current) { // If the keys match, just return a pointer to the node's item. if (result == EXACT) { entry = current; return 1; } // Otherwise if we're to the left of the insertion // point, insert into the right subtree. else if (result == LEFT) { if (current->right ()) { // If there is already a right subtree, complain. ACE_ERROR_RETURN ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nright subtree already present in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), -1); } else { // The right subtree is empty: insert new node there. ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0; ACE_NEW_MALLOC_RETURN (tmp, (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*> (this->allocator_->malloc (sizeof (*tmp)))), (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t), -1); current->right (tmp); // If the node was successfully inserted, set its parent, rebalance // the tree, color the root black, and return a pointer to the // inserted item. entry = current->right (); current->right ()->parent (current); RB_rebalance (current->right ()); this->root_->color (ACE_RB_Tree_Node_Base::BLACK); ++this->current_size_; return 0; } } // Otherwise, we're to the right of the insertion point, so // insert into the left subtree. else // (result == RIGHT) { if (current->left ()) // If there is already a left subtree, complain. ACE_ERROR_RETURN ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nleft subtree already present in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), -1); else { // The left subtree is empty: insert new node there. ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0; ACE_NEW_MALLOC_RETURN (tmp, (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*> (this->allocator_->malloc (sizeof (*tmp)))), (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t), -1); current->left (tmp); // If the node was successfully inserted, set its // parent, rebalance the tree, color the root black, and // return a pointer to the inserted item. entry = current->left (); current->left ()->parent (current); RB_rebalance (current->left ()); this->root_->color (ACE_RB_Tree_Node_Base::BLACK); ++this->current_size_; return 0; } } } else { // The tree is empty: insert at the root and color the root black. ACE_NEW_MALLOC_RETURN (this->root_, (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*> (this->allocator_->malloc (sizeof (ACE_RB_Tree_Node<EXT_ID, INT_ID>)))), (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t), -1); this->root_->color (ACE_RB_Tree_Node_Base::BLACK); ++this->current_size_; entry = this->root_; return 0; } }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::lessthan | ( | const EXT_ID & | k1, | |
const EXT_ID & | k2 | |||
) | [protected] |
Less than comparison function for keys, using comparison functor.
Definition at line 138 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan"); return this->compare_keys_ (k1, k2); }
ACE_LOCK & ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::mutex | ( | void | ) |
Returns a reference to the underlying <ACE_LOCK>. This makes it possible to acquire the lock explicitly, which can be useful in some cases if you instantiate the ACE_Atomic_Op with an ACE_Recursive_Mutex or ACE_Process_Mutex, or if you need to guard the state of an iterator.
Definition at line 564 of file RB_Tree.inl.
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::open | ( | ACE_Allocator * | alloc = 0 |
) |
Initialize an RB Tree.
Definition at line 135 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::open"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); // Calling this->close_i () ensures we release previously allocated // memory before allocating new memory. this->close_i (); // If we were passed an allocator use it, // otherwise use the default instance. if (alloc == 0) alloc = ACE_Allocator::instance (); this->allocator_ = alloc; return 0; }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::operator= | ( | const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > & | rbt | ) |
Assignment operator.
Definition at line 111 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator ="); ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_); if (this != &rbt) { // Clear out the existing tree. close_i (); // Make a deep copy of the passed tree. ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt); for (iter.first (); iter.is_done () == 0; iter.next ()) insert_i (*(iter.key ()), *(iter.item ())); // Use the same allocator as the rhs. allocator_ = rbt.allocator_; } }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_delete_fixup | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x, | |
ACE_RB_Tree_Node< EXT_ID, INT_ID > * | parent | |||
) | [protected] |
Method for restoring Red-Black properties after deletion.
Definition at line 226 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup"); while (x != this->root_ && (!x || x->color () == ACE_RB_Tree_Node_Base::BLACK)) { if (x == parent->left ()) { ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = parent->right (); if (w && w->color () == ACE_RB_Tree_Node_Base::RED) { w->color (ACE_RB_Tree_Node_Base::BLACK); parent->color (ACE_RB_Tree_Node_Base::RED); RB_rotate_left (parent); w = parent->right (); } // CLR pp. 263 says that nil nodes are implicitly colored BLACK if (w && (!w->left () || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) && (!w->right () || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK)) { w->color (ACE_RB_Tree_Node_Base::RED); x = parent; parent = x->parent (); } else { // CLR pp. 263 says that nil nodes are implicitly colored BLACK if (w && (!w->right () || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK)) { if (w->left ()) w->left ()->color (ACE_RB_Tree_Node_Base::BLACK); w->color (ACE_RB_Tree_Node_Base::RED); RB_rotate_right (w); w = parent->right (); } if (w) { w->color (parent->color ()); if (w->right ()) w->right ()->color (ACE_RB_Tree_Node_Base::BLACK); } parent->color (ACE_RB_Tree_Node_Base::BLACK); RB_rotate_left (parent); x = root_; } } else { ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = parent->left (); if (w && w->color () == ACE_RB_Tree_Node_Base::RED) { w->color (ACE_RB_Tree_Node_Base::BLACK); parent->color (ACE_RB_Tree_Node_Base::RED); RB_rotate_right (parent); w = parent->left (); } // CLR pp. 263 says that nil nodes are implicitly colored BLACK if (w && (!w->left () || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) && (!w->right () || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK)) { w->color (ACE_RB_Tree_Node_Base::RED); x = parent; parent = x->parent (); } else { // CLR pp. 263 says that nil nodes are implicitly colored BLACK if (w && (!w->left () || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)) { w->color (ACE_RB_Tree_Node_Base::RED); if (w->right ()) w->right ()->color (ACE_RB_Tree_Node_Base::BLACK); RB_rotate_left (w); w = parent->left (); } if (w) { w->color (parent->color ()); if (w->left ()) w->left ()->color (ACE_RB_Tree_Node_Base::BLACK); } parent->color (ACE_RB_Tree_Node_Base::BLACK); RB_rotate_right (parent); x = root_; } } } if (x) x->color (ACE_RB_Tree_Node_Base::BLACK); }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rebalance | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x | ) | [protected] |
Rebalance the tree after insertion of a node.
Definition at line 388 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance"); ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = 0; while (x && x->parent () && x->parent ()->color () == ACE_RB_Tree_Node_Base::RED) { if (! x->parent ()->parent ()) { // If we got here, something is drastically wrong! ACE_ERROR ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nerror: parent's parent is null in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rebalance\n"))); return; } if (x->parent () == x->parent ()->parent ()->left ()) { y = x->parent ()->parent ()->right (); if (y && y->color () == ACE_RB_Tree_Node_Base::RED) { // Handle case 1 (see CLR book, pp. 269). x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK); y->color (ACE_RB_Tree_Node_Base::BLACK); x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED); x = x->parent ()->parent (); } else { if (x == x->parent ()->right ()) { // Transform case 2 into case 3 (see CLR book, pp. 269). x = x->parent (); RB_rotate_left (x); } // Handle case 3 (see CLR book, pp. 269). x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK); x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED); RB_rotate_right (x->parent ()->parent ()); } } else { y = x->parent ()->parent ()->left (); if (y && y->color () == ACE_RB_Tree_Node_Base::RED) { // Handle case 1 (see CLR book, pp. 269). x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK); y->color (ACE_RB_Tree_Node_Base::BLACK); x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED); x = x->parent ()->parent (); } else { if (x == x->parent ()->left ()) { // Transform case 2 into case 3 (see CLR book, pp. 269). x = x->parent (); RB_rotate_right (x); } // Handle case 3 (see CLR book, pp. 269). x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK); x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED); RB_rotate_left (x->parent ()->parent ()); } } } }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rotate_left | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x | ) | [protected] |
Method for left rotation of the tree about a given node.
Definition at line 186 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left"); if (! x) ACE_ERROR ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nerror: x is a null pointer in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n"))); else if (! (x->right())) ACE_ERROR ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nerror: x->right () is a null pointer ") ACE_TEXT ("in ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n"))); else { ACE_RB_Tree_Node<EXT_ID, INT_ID> * y; y = x->right (); x->right (y->left ()); if (y->left ()) y->left ()->parent (x); y->parent (x->parent ()); if (x->parent ()) { if (x == x->parent ()->left ()) x->parent ()->left (y); else x->parent ()->right (y); } else root_ = y; y->left (x); x->parent (y); } }
void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rotate_right | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x | ) | [protected] |
Method for right rotation of the tree about a given node.
Definition at line 147 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right"); if (!x) ACE_ERROR ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nerror: x is a null pointer in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n"))); else if (! (x->left())) ACE_ERROR ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nerror: x->left () is a null pointer in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n"))); else { ACE_RB_Tree_Node<EXT_ID, INT_ID> * y; y = x->left (); x->left (y->right ()); if (y->right ()) y->right ()->parent (x); y->parent (x->parent ()); if (x->parent ()) { if (x == x->parent ()->right ()) x->parent ()->right (y); else x->parent ()->left (y); } else root_ = y; y->right (x); x->parent (y); } }
ACE_RB_Tree_Node< EXT_ID, INT_ID > * ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_maximum | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x | ) | const [protected] |
Method to find the maximum node of the subtree rooted at the given node.
Definition at line 525 of file RB_Tree.cpp.
ACE_RB_Tree_Node< EXT_ID, INT_ID > * ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_minimum | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x | ) | const [protected] |
Method to find the minimum node of the subtree rooted at the given node.
Definition at line 512 of file RB_Tree.cpp.
ACE_RB_Tree_Node< EXT_ID, INT_ID > * ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_predecessor | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x | ) | const [protected] |
Method to find the predecessor node of the given node in the tree.
Definition at line 489 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor"); if (x == 0) return 0; if (x->left ()) return RB_tree_maximum (x->left ()); ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent (); while ((y) && (x == y->left ())) { x = y; y = y->parent (); } return y; }
ACE_RB_Tree_Node< EXT_ID, INT_ID > * ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_successor | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x | ) | const [protected] |
Method to find the successor node of the given node in the tree.
Definition at line 466 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor"); if (x == 0) return 0; if (x->right ()) return RB_tree_minimum (x->right ()); ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent (); while ((y) && (x == y->right ())) { x = y; y = y->parent (); } return y; }
ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rbegin | ( | void | ) |
Return reverse iterator positioned at last node in tree.
Definition at line 618 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rbegin"); return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this); }
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 | |||
) |
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.
Definition at line 317 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, " "const INT_ID &int_id, INT_ID &old_int_id)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry; int result = this->insert_i (ext_id, int_id, entry); if (result == 1) { old_int_id = entry->item (); entry->key () = ext_id; entry->item () = int_id; } return result; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind | ( | const EXT_ID & | ext_id, | |
const INT_ID & | int_id, | |||
ACE_RB_Tree_Node< EXT_ID, INT_ID > *& | entry | |||
) |
Same as a normal rebind, except the tree entry is also passed back to the caller. The entry in this case will either be the newly created entry, or the existing one.
Definition at line 289 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id, " "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); int result = this->insert_i (ext_id, int_id, entry); if (result == 1) { entry->key () = ext_id; entry->item () = int_id; } return result; }
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 | |||
) |
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.
Definition at line 378 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id," "EXT_ID &old_ext_id, INT_ID &old_int_id)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry; int result = this->insert_i (ext_id, int_id, entry); if (result == 1) { old_ext_id = entry->key (); old_int_id = entry->item (); entry->key () = ext_id; entry->item () = int_id; } return result; }
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, | |||
ACE_RB_Tree_Node< EXT_ID, INT_ID > *& | entry | |||
) |
Same as a normal rebind, except the tree entry is also passed back to the caller. The entry in this case will either be the newly created entry, or the existing one.
Definition at line 345 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::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)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); int result = this->insert_i (ext_id, int_id, entry); if (result == 1) { old_int_id = entry->item (); entry->key () = ext_id; entry->item () = int_id; } return result; }
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, | |||
ACE_RB_Tree_Node< EXT_ID, INT_ID > *& | entry | |||
) |
Same as a normal rebind, except the tree entry is also passed back to the caller. The entry in this case will either be the newly created entry, or the existing one.
Definition at line 408 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::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)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); int result = this->insert_i (ext_id, int_id, entry); if (result == 1) { old_ext_id = entry->key (); old_int_id = entry->item (); entry->key () = ext_id; entry->item () = int_id; } return result; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind | ( | const EXT_ID & | ext_id, | |
const INT_ID & | int_id | |||
) |
Reassociate ext_id with int_id. If ext_id is not in the tree then behaves just like <bind>. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur.
Definition at line 264 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry; int result = this->insert_i (ext_id, int_id, entry); if (result == 1) { entry->key () = ext_id; entry->item () = int_id; } return result; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove | ( | const EXT_ID & | k | ) |
Removes the item associated with the given key from the tree and destroys it. Returns 1 if it found the item and successfully destroyed it, 0 if it did not find the item, or -1 if an error occurred.
Definition at line 693 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); INT_ID i; return this->remove_i (k, i); }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i | ( | const EXT_ID & | k, | |
INT_ID & | i | |||
) | [protected] |
Removes the item associated with the given key from the tree and destroys it. Returns 1 if it found the item and successfully destroyed it, 0 if it did not find the item, or -1 if an error occurred. Returns the stored internal id in the second argument.
Definition at line 838 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (const EXT_ID &k, INT_ID &i)"); // Find a matching node, if there is one. ACE_RB_Tree_Node<EXT_ID, INT_ID> *z; RB_SearchResult result = LEFT; z = find_node (k, result); // If there is a matching node: remove and destroy it. if (z && result == EXACT) { // Return the internal id stored in the deleted node. i = z->item (); return -1 == this->remove_i (z) ? -1 : 1; } // No matching node was found: return 0. return 0; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | z | ) | [protected] |
Removes the item associated with the given key from the tree and destroys it.
Definition at line 991 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z)"); // Delete the node and reorganize the tree to satisfy the Red-Black // properties. ACE_RB_Tree_Node<EXT_ID, INT_ID> *x; ACE_RB_Tree_Node<EXT_ID, INT_ID> *y; ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent; if (z->left () && z->right ()) y = RB_tree_successor (z); else y = z; if (!y) return -1; if (y->left ()) x = y->left (); else x = y->right (); parent = y->parent (); if (x) { x->parent (parent); } if (parent) { if (y == parent->left ()) parent->left (x); else parent->right (x); } else this->root_ = x; if (y != z) { // Replace node z with node y, since y's pointer may well be // held externally, and be linked with y's key and item. // We will end up deleting the old unlinked, node z. ACE_RB_Tree_Node<EXT_ID, INT_ID> *zParent = z->parent (); ACE_RB_Tree_Node<EXT_ID, INT_ID> *zLeftChild = z->left (); ACE_RB_Tree_Node<EXT_ID, INT_ID> *zRightChild = z->right (); if (zParent) { if (z == zParent->left ()) { zParent->left (y); } else { zParent->right (y); } } else { this->root_ = y; } y->parent (zParent); if (zLeftChild) { zLeftChild->parent (y); } y->left (zLeftChild); if (zRightChild) { zRightChild->parent (y); } y->right (zRightChild); if (parent == z) { parent = y; } ACE_RB_Tree_Node_Base::RB_Tree_Node_Color yColor = y->color (); y->color (z->color ()); z->color (yColor); //Reassign the y pointer to z because the node that y points to will be //deleted y = z; } // CLR pp. 263 says that nil nodes are implicitly colored BLACK if (!y || y->color () == ACE_RB_Tree_Node_Base::BLACK) RB_delete_fixup (x, parent); y->parent (0); y->right (0); y->left (0); ACE_DES_FREE_TEMPLATE2 (y, this->allocator_->free, ACE_RB_Tree_Node, EXT_ID, INT_ID); --this->current_size_; return 0; }
ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rend | ( | void | ) |
Return reverse iterator positioned at first node in tree.
Definition at line 630 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rend"); return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, 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.
Definition at line 907 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant"); ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); // Recurse from the root, starting with the measured black height at // 0, and the expected black height at -1, which will cause the // count from first measured path to a leaf to be used as the // expected one from that point onward (the key is to check // consistency). int expected_black_height = -1; if (this->test_invariant_recurse (this->root_, expected_black_height, 0) == 0) { ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("invariant holds\n"))); return 0; } return -1; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::test_invariant_recurse | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | x, | |
int & | expected_black_height, | |||
int | measured_black_height | |||
) | [protected] |
Recursive function to test the red-black invariant(s) at all nodes in a subtree.
Recursively tests the invariant red-black properties at each node of the tree. Returns 0 if invariant holds, else -1.
Definition at line 930 of file RB_Tree.cpp.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant_recurse"); if (!x) { // Count each leaf (zero pointer) as a black node (per CLR algorithm description). ++measured_black_height; if (expected_black_height == -1) { expected_black_height = measured_black_height; } else if (expected_black_height != measured_black_height) { ACE_ERROR_RETURN ((LM_ERROR, ACE_TEXT ("\nexpected_black_height = %d but ") ACE_TEXT ("\nmeasured_black_height = %d in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n"), expected_black_height, measured_black_height), -1); } return 0; } // Check the invariant that a red node cannot have a red child. if (x->color () == ACE_RB_Tree_Node_Base::RED) { if (x->left () && x->left ()->color () == ACE_RB_Tree_Node_Base::RED) { ACE_ERROR_RETURN ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nRED parent has RED left child in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")), -1); } if (x->right () && x->right ()->color () == ACE_RB_Tree_Node_Base::RED) { ACE_ERROR_RETURN ((LM_ERROR, ACE_TEXT ("%p\n"), ACE_TEXT ("\nRED parent has RED right child in ") ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")), -1); } } else { // Count each black node traversed. ++measured_black_height; } return (test_invariant_recurse (x->left (), expected_black_height, measured_black_height) == 0) ? test_invariant_recurse (x->right (), expected_black_height, measured_black_height) : -1; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::trybind | ( | const EXT_ID & | ext_id, | |
INT_ID & | int_id, | |||
ACE_RB_Tree_Node< EXT_ID, INT_ID > *& | entry | |||
) |
Same as a normal trybind, except the tree entry is also passed back to the caller. The entry in this case will either be the newly created entry, or the existing one.
Definition at line 237 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::trybind (const EXT_ID &ext_id, INT_ID &int_id, " "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); int result = this->insert_i (ext_id, int_id, entry); if (result == 1) { int_id = entry->item (); } return result; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::trybind | ( | const EXT_ID & | ext_id, | |
INT_ID & | int_id | |||
) |
Associate ext_id with int_id if and only if ext_id is not in the tree. If ext_id is already in the tree then the int_id parameter is assigned the existing value in the tree. Returns 0 if a new entry is bound successfully, returns 1 if an attempt is made to bind an existing entry, and returns -1 if failures occur.
Definition at line 213 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::trybind (const EXT_ID &ext_id, INT_ID &int_id)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry; int result = this->insert_i (ext_id, int_id, entry); if (result == 1) { int_id = entry->item (); } return result; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::unbind | ( | const EXT_ID & | ext_id, | |
INT_ID & | int_id | |||
) |
Break any association of ext_id. Returns the value of int_id in case the caller needs to deallocate memory.
Definition at line 511 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree::unbind (const EXT_ID &ext_id, INT_ID &int_id)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); int result = this->remove_i (ext_id, int_id); // Remap the return codes from the internal method: this // is maintained this way in support of deprecated methods, // and will be cleaned up when these methods are removed. switch (result) { case 1: // If the node was found and deleted, return success. return 0; case 0: // If nothing was found, set errno and break. errno = ENOENT; break; case -1: // If an error happened, just break. break; } // Return an error if we didn't already return success. return -1; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::unbind | ( | const EXT_ID & | ext_id | ) |
Unbind (remove) the ext_id from the tree. Don't return the int_id to the caller (this is useful for collections where the int_ids
are *not* dynamically allocated...)
Definition at line 476 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (const EXT_ID &ext_id)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); INT_ID int_id; int result = this->remove_i (ext_id, int_id); // Remap the return codes from the internal method: this // is maintained this way in support of deprecated methods, // and will be cleaned up when these methods are removed. switch (result) { case 1: // If the node was found and deleted, return success. return 0; case 0: // If nothing was found, set errno and break. errno = ENOENT; break; case -1: // If an error happened, just break. break; } // Return an error if we didn't already return success. return -1; }
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::unbind | ( | ACE_RB_Tree_Node< EXT_ID, INT_ID > * | entry | ) |
Remove entry from tree. This method should be used with *extreme* caution, and only for optimization purposes. The node being passed in had better have been allocated by the tree that is unbinding it.
Definition at line 546 of file RB_Tree.inl.
{ ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry)"); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); return this->remove_i (entry); }
friend class ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > [friend] |
friend class ACE_RB_Tree_Iterator_Base< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > [friend] |
friend class ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > [friend] |
COMPARE_KEYS ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::compare_keys_ [private] |
size_t ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::current_size_ [private] |
ACE_LOCK ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::lock_ [private] |
Synchronization variable for the MT_SAFE ACE_RB_Tree.
ACE_RB_Tree_Node<EXT_ID, INT_ID>* ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::root_ [private] |