diff options
Diffstat (limited to 'ace/RB_Tree.cpp')
| -rw-r--r-- | ace/RB_Tree.cpp | 950 |
1 files changed, 313 insertions, 637 deletions
diff --git a/ace/RB_Tree.cpp b/ace/RB_Tree.cpp index 251f5c563e3..5b619313e6d 100644 --- a/ace/RB_Tree.cpp +++ b/ace/RB_Tree.cpp @@ -17,15 +17,15 @@ ACE_RCSID(ace, RB_Tree, "$Id$") -///////////////////////////////////////////////////// -// template class ACE_RB_Tree_Node<EXT_ID, INT_ID> // -///////////////////////////////////////////////////// +///////////////////////////////////////////// +// template class ACE_RB_Tree_Node<KEY, T> // +///////////////////////////////////////////// // Constructor. -template <class EXT_ID, class INT_ID> -ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t) +template <class KEY, class T> +ACE_RB_Tree_Node<KEY, T>::ACE_RB_Tree_Node (const KEY &k, const T &t) : k_ (k) , t_ (t) , color_ (RED) @@ -33,17 +33,14 @@ ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_I , left_ (0) , right_ (0) { - ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::ACE_RB_Tree_Node (const EXT_ID &k, const INT_ID &t)"); } // Destructor. -template <class EXT_ID, class INT_ID> -ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node () +template <class KEY, class T> +ACE_RB_Tree_Node<KEY, T>::~ACE_RB_Tree_Node () { - ACE_TRACE ("ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node"); - // Delete left sub-tree. delete left_; @@ -53,113 +50,309 @@ ACE_RB_Tree_Node<EXT_ID, INT_ID>::~ACE_RB_Tree_Node () -//////////////////////////////////////////////// -// template class ACE_RB_Tree<EXT_ID, INT_ID> // -//////////////////////////////////////////////// +//////////////////////////////////////// +// template class ACE_RB_Tree<KEY, T> // +//////////////////////////////////////// // Constructor. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (ACE_Allocator *alloc) - : allocator_ (alloc), - root_ (0), - current_size_ (0) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree () + : root_ (0) { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::" - "ACE_RB_Tree (ACE_Allocator *alloc)"); - if (this->open (alloc) == -1) - ACE_ERROR ((LM_ERROR, ASYS_TEXT ("ACE_RB_Tree::ACE_RB_Tree\n"))); } // Copy constructor. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -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) - : allocator_ (rbt.allocator_), - root_ (0), - current_size_ (0) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &rbt) + : root_ (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_); - // Make a deep copy of the passed tree. - ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt); + ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> iter(rbt); for (iter.first (); iter.is_done () == 0; iter.next ()) { - insert_i (*(iter.key ()), *(iter.item ())); + insert (*(iter.key ()), *(iter.item ())); } } + // Destructor. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree () +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree () { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree"); - - // Use the locked public method, to be totally safe, as the - // class can be used with an allocator and placement new. - this->close (); + // Clear away all nodes in the tree. + clear (); } // Assignment operator. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 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) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::operator = (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &rbt) { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator ="); - ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_); - // Clear out the existing tree. - close_i (); + clear (); // Make a deep copy of the passed tree. - ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt); + ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> iter(rbt); for (iter.first (); iter.is_done () == 0; iter.next ()) { - insert_i (*(iter.key ()), *(iter.item ())); + insert (*(iter.key ()), *(iter.item ())); } - - // Use the same allocator as the rhs. - allocator_ = rbt.allocator_; } // Less than comparison function for keys, default // functor implementation returns 1 if k1 < k2, 0 otherwise. -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>::lessthan (const EXT_ID &k1, const EXT_ID &k2) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> int +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::lessthan (const KEY &k1, const KEY &k2) { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan"); - return this->compare_keys_ (k1, k2); + return this->compare_keys_ (k1, k2); } -// Method for right rotation of the tree about a given node. +// Returns a pointer to the item corresponding to the +// given key, or 0 if it cannot find the key in the tree. + +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> T* +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::find (const KEY &k) +{ + // Find the closest matching node, if there is one. + ACE_RB_Tree_Node<KEY, T> *current = find_node (k); + + if (current) + { + // If a nearest matching node was returned. + if (this->lessthan (current->key (), k) + || this->lessthan (k, current->key ())) + { + // If the keys differ, there is no match: return 0. + return 0; + } + else + { + // The keys match: return a pointer to the node's item. + return &(current->item ()); + } + } + else + { + // The tree is empty: return 0. + return 0; + } +} + + + +// Inserts a *copy* of the key and the item into the tree: +// both the key type KEY and the item type T must have well +// defined semantics for copy construction and < comparison. +// This method returns a pointer to the inserted item copy, +// or 0 if an error occurred. NOTE: if an identical key +// already exists in the tree, no new item is created, and +// the returned pointer addresses the existing item +// associated with the existing key. + +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> T* +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::insert (const KEY &k, const T &t) +{ + // Find the closest matching node, if there is one. + ACE_RB_Tree_Node<KEY, T> *current = find_node (k); + if (current) + { + if (this->lessthan (current->key (), k)) + { + // If a nearest matching node has a key less than the insertion key. + if (current->right ()) + { + // If there is already a right subtree, complain. + ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), + ASYS_TEXT ("\nright subtree already present in " + "ACE_RB_Tree<KEY, T>::insert\n")), 0); + } + else + { + // The right subtree is empty: insert new node there. + current->right (new ACE_RB_Tree_Node<KEY, T> (k, t)); + if (current->right ()) + { + // If the node was successfully inserted, set its parent, rebalance + // the tree, color the root black, and return a pointer to the + // inserted item. + T *item = &(current->right ()->item ()); + current->right ()->parent (current); + RB_rebalance (current->right ()); + root_->color (ACE_RB_Tree_Node_Base::BLACK); + return item; + } + else + { + // Memory allocation failed. + ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), + ASYS_TEXT ("\nmemory allocation to current->right_ failed " + "in ACE_RB_Tree<KEY, T>::insert\n")), 0); + } + } + } + else if (this->lessthan (k, current->key ())) + { + // If a nearest matching node has a key greater than the insertion key. + if (current->left ()) + { + // If there is already a left subtree, complain. + ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), + ASYS_TEXT ("\nleft subtree already present in " + "ACE_RB_Tree<KEY, T>::insert\n")), 0); + } + else + { + // The right subtree is empty: insert new node there. + current->left (new ACE_RB_Tree_Node<KEY, T> (k, t)); + if (current->left ()) + { + // If the node was successfully inserted, set its parent, rebalance + // the tree, color the root black, and return a pointer to the + // inserted item. + T *item = &(current->left ()->item ()); + current->left ()->parent (current); + RB_rebalance (current->left ()); + root_->color (ACE_RB_Tree_Node_Base::BLACK); + return item; + } + else + { + // Memory allocation failed. + ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), + ASYS_TEXT ("\nmemory allocation to current->left_ failed in " + "ACE_RB_Tree<KEY, T>::insert\n")), 0); + } + } + } + else + { + // The keys match: return a pointer to the node's item. + return &(current->item ()); + } + } + else + { + // The tree is empty: insert at the root and color the root black. + root_ = new ACE_RB_Tree_Node<KEY, T> (k, t); + if (root_) + { + root_->color (ACE_RB_Tree_Node_Base::BLACK); + return &(root_->item ()); + } + else + { + ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), + ASYS_TEXT ("\nmemory allocation to root_ failed in " + "ACE_RB_Tree<KEY, T>::insert\n")), 0); + } + } +} + -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void -ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x) +// 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. + +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> int +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::remove (const KEY &k) { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right"); + // Find a matching node, if there is one. + ACE_RB_Tree_Node<KEY, T> *x, *z; + + z = find_node (k); + if ((z) && (! this->lessthan (z->key (), k)) + && (! this->lessthan (k, z->key ()))) + { + // There is a matching node: remove and destroy it. + ACE_RB_Tree_Node<KEY, T> *y; + if ((z->left ()) && (z->right ())) + { + y = RB_tree_successor (z); + } + else + { + y = z; + } + if (y->left ()) + { + x = y->left (); + } + else + { + x = y->right (); + } + if (x) + { + x->parent (y->parent ()); + } + if (y->parent ()) + { + if (y == y->parent ()->left ()) + { + y->parent ()->left (x); + } + else + { + y->parent ()->right (x); + } + } + else + { + root_ = x; + } + if (y != z) + { + // Copy the elements of y into z. + z->key () = y->key (); + z->item () = y->item (); + } + if (y->color () == ACE_RB_Tree_Node_Base::BLACK) + { + RB_delete_fixup (x); + } + y->parent (0); + y->right (0); + y->left (0); + delete y; + return 1; + } + else + { + // No matching node was found: return 0. + return 0; + } +} + + +// Method for right rotation of the tree about a given node. + +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right (ACE_RB_Tree_Node<KEY, T> * x) +{ if (! x) { ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"), ASYS_TEXT ("\nerror: x is a null pointer in " - "ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n"))); + "ACE_RB_Tree<KEY, T>::RB_rotate_right\n"))); } else if (! (x->left())) { ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"), ASYS_TEXT ("\nerror: x->left () is a null pointer in " - "ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n"))); + "ACE_RB_Tree<KEY, T>::RB_rotate_right\n"))); } else { - ACE_RB_Tree_Node<EXT_ID, INT_ID> * y; + ACE_RB_Tree_Node<KEY, T> * y; y = x->left (); x->left (y->right ()); if (y->right ()) @@ -190,26 +383,24 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right (ACE_RB_Tre // Method for left rotation of the tree about a given node. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void -ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree_Node<KEY, T> * x) { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left"); - if (! x) { ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"), ASYS_TEXT ("\nerror: x is a null pointer in " - "ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n"))); + "ACE_RB_Tree<KEY, T>::RB_rotate_left\n"))); } else if (! (x->right())) { ACE_ERROR ((LM_ERROR, ASYS_TEXT ("%p\n"), ASYS_TEXT ("\nerror: x->right () is a null pointer " - "in ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n"))); + "in ACE_RB_Tree<KEY, T>::RB_rotate_left\n"))); } else { - ACE_RB_Tree_Node<EXT_ID, INT_ID> * y; + ACE_RB_Tree_Node<KEY, T> * y; y = x->right (); x->right (y->left ()); if (y->left ()) @@ -240,107 +431,71 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left (ACE_RB_Tree // Method for restoring Red-Black properties after deletion. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void -ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x) { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup"); - - while (x && - x->parent () && - x->color () == ACE_RB_Tree_Node_Base::BLACK) + while ((x) && (x->parent ()) && (x->color () == ACE_RB_Tree_Node_Base::BLACK)) { if (x == x->parent ()->left ()) { - ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = x->parent ()->right (); - if (w && w->color () == ACE_RB_Tree_Node_Base::RED) + ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->right (); + if (w->color () == ACE_RB_Tree_Node_Base::RED) { w->color (ACE_RB_Tree_Node_Base::BLACK); x->parent ()->color (ACE_RB_Tree_Node_Base::RED); RB_rotate_left (x->parent ()); w = x->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)) + if ((w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) && + (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK)) { w->color (ACE_RB_Tree_Node_Base::RED); x = 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->right ()->color () == ACE_RB_Tree_Node_Base::BLACK) { - if (w->left ()) - { - w->left ()->color (ACE_RB_Tree_Node_Base::BLACK); - } + w->left ()->color (ACE_RB_Tree_Node_Base::BLACK); w->color (ACE_RB_Tree_Node_Base::RED); RB_rotate_right (w); w = x->parent ()->right (); } - if (w) - { - w->color (x->parent ()->color ()); - if (w->right ()) - { - w->right ()->color (ACE_RB_Tree_Node_Base::BLACK); - } - } + w->color (x->parent ()->color ()); x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK); + w->right ()->color (ACE_RB_Tree_Node_Base::BLACK); RB_rotate_left (x->parent ()); x = root_; } } else { - ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = x->parent ()->left (); - if (w && w->color () == ACE_RB_Tree_Node_Base::RED) + ACE_RB_Tree_Node<KEY, T> *w = x->parent ()->left (); + if (w->color () == ACE_RB_Tree_Node_Base::RED) { w->color (ACE_RB_Tree_Node_Base::BLACK); x->parent ()->color (ACE_RB_Tree_Node_Base::RED); RB_rotate_right (x->parent ()); w = x->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)) + if ((w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) && + (w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK)) { w->color (ACE_RB_Tree_Node_Base::RED); x = 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)) + if (w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK) { + w->right ()->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 = x->parent ()->left (); } - if (w) - { - w->color (x->parent ()->color ()); - if (w->left ()) - { - w->left ()->color (ACE_RB_Tree_Node_Base::BLACK); - } - } + w->color (x->parent ()->color ()); x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK); + w->left ()->color (ACE_RB_Tree_Node_Base::BLACK); RB_rotate_right (x->parent ()); x = root_; } @@ -360,13 +515,10 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup (ACE_RB_Tre // if the tree is not empty and there is no such match, // or 0 if the tree is empty. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 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) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> * +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::find_node (const KEY &k) { - 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_; + ACE_RB_Tree_Node<KEY, T> *current = root_; while (current) { @@ -381,9 +533,7 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node (const EXT_ID &k, } else { - // If the right subtree is empty, we're done searching, - // and are positioned to the left of the insertion point. - result = LEFT; + // If the right subtree is empty, we're done. break; } } @@ -397,16 +547,13 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node (const EXT_ID &k, } else { - // If the left subtree is empty, we're done searching, - // and are positioned to the right of the insertion point. - result = RIGHT; + // If the left subtree is empty, we're done. break; } } else { - // If the keys match exactly, we're done as well. - result = EXACT; + // If the keys match, we're done. break; } } @@ -417,30 +564,27 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node (const EXT_ID &k, // Rebalance the tree after insertion of a node. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void -ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> void +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_Node<KEY, T> * x) { - 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; + ACE_RB_Tree_Node<KEY, T> *y = 0; - while (x && - x->parent () && - x->parent ()->color () == ACE_RB_Tree_Node_Base::RED) + 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, ASYS_TEXT ("%p\n"), ASYS_TEXT ("\nerror: parent's parent is null in " - "ACE_RB_Tree<EXT_ID, INT_ID>::RB_rebalance\n"))); + "ACE_RB_Tree<KEY, T>::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) + 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); @@ -466,7 +610,7 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_N else { y = x->parent ()->parent ()->left (); - if (y && y->color () == ACE_RB_Tree_Node_Base::RED) + 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); @@ -495,17 +639,15 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance (ACE_RB_Tree_N // Method to find the successor node of the given node in the tree. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 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 +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> * +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor (ACE_RB_Tree_Node<KEY, T> *x) const { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor"); - if (x->right ()) { return RB_tree_minimum (x->right ()); } - ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent (); + ACE_RB_Tree_Node<KEY, T> *y = x->parent (); while ((y) && (x == y->right ())) { x = y; @@ -518,17 +660,15 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor (ACE_RB_T // Method to find the predecessor node of the given node in the tree. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 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 +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> * +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor (ACE_RB_Tree_Node<KEY, T> *x) const { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor"); - if (x->left ()) { return RB_tree_maximum (x->left ()); } - ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent (); + ACE_RB_Tree_Node<KEY, T> *y = x->parent (); while ((y) && (x == y->left ())) { x = y; @@ -541,11 +681,9 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor (ACE_RB // Method to find the minimum node of the subtree rooted at the given node. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 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 +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> * +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum (ACE_RB_Tree_Node<KEY, T> *x) const { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum"); - while ((x) && (x->left ())) { x = x->left (); @@ -557,11 +695,9 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum (ACE_RB_Tre // Method to find the maximum node of the subtree rooted at the given node. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> 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 +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> ACE_RB_Tree_Node<KEY, T> * +ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum (ACE_RB_Tree_Node<KEY, T> *x) const { - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum"); - while ((x) && (x->right ())) { x = x->right (); @@ -570,490 +706,30 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum (ACE_RB_Tre return x; } -// Close down an RB_Tree. this method should -// only be called with locks already held. - -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>::close_i () -{ - ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i"); - - delete root_; - current_size_ = 0; - root_ = 0; - - return 0; -} - -// Returns a pointer to the item corresponding to the given key, -// or 0 if it cannot find the key in the tree. This method should -// only be called with locks already held. - -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>::find_i (const EXT_ID &k, - ACE_RB_Tree_Node<EXT_ID, INT_ID>* &entry) -{ - 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 && result == EXACT) - { - // Found an exact match: return a pointer to the node. - entry = current; - return 0; - } - else - { - // The node is not there. - return -1; - } -} - - -// 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 and < comparison. -// This method returns a pointer to the inserted item copy, -// or 0 if an error occurred. NOTE: if an identical key -// already exists in the tree, no new item is created, and -// the returned pointer addresses the existing item -// associated with the existing key. This method should -// only be called with locks already held. - -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> INT_ID* -ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t) -{ - 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 &(current->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, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nright subtree already present in " - "ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), 0); - } - else - { - // The right subtree is empty: insert new node there. - current->right (new ACE_RB_Tree_Node<EXT_ID, INT_ID> (k, t)); - if (current->right ()) - { - // 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; - } - else - { - // Memory allocation failed. - ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nmemory allocation to current->right_ failed " - "in ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), 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, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nleft subtree already present in " - "ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), 0); - } - else - { - // The left subtree is empty: insert new node there. - current->left (new ACE_RB_Tree_Node<EXT_ID, INT_ID> (k, t)); - if (current->left ()) - { - // 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->left ()->item ()); - current->left ()->parent (current); - RB_rebalance (current->left ()); - root_->color (ACE_RB_Tree_Node_Base::BLACK); - ++current_size_; - return item; - } - else - { - // Memory allocation failed. - ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nmemory allocation to current->left_ failed in " - "ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), 0); - } - } - } - } - else - { - // The tree is empty: insert at the root and color the root black. - root_ = new ACE_RB_Tree_Node<EXT_ID, INT_ID> (k, t); - if (root_) - { - root_->color (ACE_RB_Tree_Node_Base::BLACK); - ++current_size_; - return &(root_->item ()); - } - else - { - ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nmemory allocation to root_ failed in " - "ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), 0); - } - } -} - - -// 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>::insert_i (const EXT_ID &k, const INT_ID &t, - ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry) -{ - 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, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nright subtree already present in " - "ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), -1); - } - else - { - // The right subtree is empty: insert new node there. - current->right (new ACE_RB_Tree_Node<EXT_ID, INT_ID> (k, t)); - if (current->right ()) - { - // 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 ()); - root_->color (ACE_RB_Tree_Node_Base::BLACK); - ++current_size_; - return 0; - } - else - { - // Memory allocation failed. - ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nmemory allocation to current->right_ failed " - "in ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), -1); - } - } - } - // 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, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nleft subtree already present in " - "ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), -1); - } - else - { - // The left subtree is empty: insert new node there. - current->left (new ACE_RB_Tree_Node<EXT_ID, INT_ID> (k, t)); - if (current->left ()) - { - // 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 ()); - root_->color (ACE_RB_Tree_Node_Base::BLACK); - ++current_size_; - return 0; - } - else - { - // Memory allocation failed. - ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nmemory allocation to current->left_ failed in " - "ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), -1); - } - } - } - } - else - { - // The tree is empty: insert at the root and color the root black. - root_ = new ACE_RB_Tree_Node<EXT_ID, INT_ID> (k, t); - if (root_) - { - root_->color (ACE_RB_Tree_Node_Base::BLACK); - ++current_size_; - entry = root_; - return 0; - } - else - { - ACE_ERROR_RETURN ((LM_ERROR, ASYS_TEXT ("%p\n"), - ASYS_TEXT ("\nmemory allocation to root_ failed in " - "ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")), -1); - } - } -} - - -// 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. This method should -// only be called with locks already held. - -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>::remove_i (const EXT_ID &k, INT_ID &i) -{ - 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; - } - else - { - // No matching node was found: return 0. - return 0; - } -} - -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>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z) -{ - 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, *y; - - if ((z->left ()) && (z->right ())) - { - y = RB_tree_successor (z); - } - else - { - y = z; - } - if (y->left ()) - { - x = y->left (); - } - else - { - x = y->right (); - } - if (x) - { - x->parent (y->parent ()); - } - if (y->parent ()) - { - if (y == y->parent ()->left ()) - { - y->parent ()->left (x); - } - else - { - y->parent ()->right (x); - } - } - else - { - root_ = x; - } - if (y != z) - { - // Copy the elements of y into z. - z->key () = y->key (); - z->item () = y->item (); - } - // 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); - } - y->parent (0); - y->right (0); - y->left (0); - delete y; - --current_size_; - - return 0; -} - - - -/////////////////////////////////////////////////////////////////////// -// template class // -// ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> // -/////////////////////////////////////////////////////////////////////// - -ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Iterator_Base) - -// Constructor. - -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, int set_first) - : tree_ (&tree), node_ (0) -{ - ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (ACE_RB_Tree, int)"); - - // Position the iterator at the first (or last) node in the tree. - if (set_first) - { - node_ = tree_->RB_tree_minimum (tree_->root_); - } - else - { - node_ = tree_->RB_tree_maximum (tree_->root_); - } -} - -// Copy constructor. - -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &iter) - : tree_ (iter.tree_), - node_ (iter.node_) -{ - ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator_Base (ACE_RB_Tree_Iterator_Base)"); -} - -// Assignment operator. - -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> void -ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator= (const ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &iter) -{ - ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator="); - tree_ = iter.tree_; - node_ = iter.node_; -} - - -// Destructor. - -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator_Base () -{ - ACE_TRACE ("ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator_Base"); -} - - -////////////////////////////////////////////////////////////////// -// template class // -// ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> // -////////////////////////////////////////////////////////////////// - -ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Iterator) - -// Constructor. - -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, - int set_first) - : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree, set_first) -{ - ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator"); -} - - -// Destructor. - -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator () -{ - ACE_TRACE ("ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator"); -} -////////////////////////////////////////////////////////////////////////// -// template class // -// ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> // -////////////////////////////////////////////////////////////////////////// +////////////////////////////////////////////////////////// +// template class ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> // +////////////////////////////////////////////////////////// -ACE_ALLOC_HOOK_DEFINE(ACE_RB_Tree_Reverse_Iterator) // Constructor. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &tree, int set_last) - : ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (tree, set_last ? 0 : 1) +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> +ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Iterator (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &tree) + : tree_ (tree), node_ (0) { - ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::ACE_RB_Tree_Reverse_Iterator"); + // Position the iterator at the first node in the tree. + first (); } // Destructor. -template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> -ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Reverse_Iterator () +template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK> +ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Iterator () { - ACE_TRACE ("ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree_Reverse_Iterator"); } |