Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

ACE_RB_Tree Class Template Reference

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>

Inheritance diagram for ACE_RB_Tree:

Inheritance graph
[legend]
Collaboration diagram for ACE_RB_Tree:

Collaboration graph
[legend]
List of all members.

Public Types

typedef EXT_ID KEY
typedef INT_ID VALUE
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 Methods

 ACE_RB_Tree (ACE_Allocator *alloc=0)
 Constructor. More...

 ACE_RB_Tree (const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > &rbt)
 Copy constructor. More...

int open (ACE_Allocator *alloc=0)
 Initialize an RB Tree. More...

int close (void)
 Close down an RB_Tree and release dynamically allocated resources. More...

virtual ~ACE_RB_Tree (void)
 Destructor. More...

int bind (const EXT_ID &item, const INT_ID &int_id)
int bind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int trybind (const EXT_ID &ext_id, INT_ID &int_id)
int trybind (const EXT_ID &ext_id, INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int find (const EXT_ID &ext_id, INT_ID &int_id)
 Locate <ext_id> and pass out parameter via <int_id>. If found, return 0, returns -1 if not found. More...

int 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. More...

int unbind (const EXT_ID &ext_id)
int 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. More...

int unbind (ACE_RB_Tree_Node< EXT_ID, INT_ID > *entry)
size_t current_size (void) const
 Returns the current number of nodes in the tree. More...

void operator= (const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > &rbt)
 Assignment operator. More...

virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2)
 Less than comparison function for keys, using comparison functor. More...

ACE_LOCK & mutex (void)
void dump (void) const
 Dump the state of an object. More...

ACE_RB_Tree_Iterator< EXT_ID,
INT_ID, COMPARE_KEYS, ACE_LOCK > 		begin (void)
 Return forward iterator positioned at first node in tree. More...

ACE_RB_Tree_Iterator< EXT_ID,
INT_ID, COMPARE_KEYS, ACE_LOCK > 		end (void)
 Return forward iterator positioned at last node in tree. More...

ACE_RB_Tree_Reverse_Iterator<
EXT_ID, INT_ID, COMPARE_KEYS,
ACE_LOCK > 		rbegin (void)
 Return reverse iterator positioned at last node in tree. More...

ACE_RB_Tree_Reverse_Iterator<
EXT_ID, INT_ID, COMPARE_KEYS,
ACE_LOCK > 		rend (void)
 Return reverse iterator positioned at first node in tree. More...

int test_invariant (void)
 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. More...

INT_ID * find (const EXT_ID &k)
INT_ID * insert (const EXT_ID &k, const INT_ID &t)
int remove (const EXT_ID &k)
void clear (void)
 
Deprecated:
Destroys all nodes and sets the root pointer null.
 More...


Protected Methods

int test_invariant_recurse (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x, int &expected_black_height, int measured_black_height)
 Recursively tests the invariant red-black properties at each node of the tree. Returns 0 if invariant holds, else -1. More...

void RB_rotate_right (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x)
 Method for right rotation of the tree about a given node. More...

void RB_rotate_left (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x)
 Method for left rotation of the tree about a given node. More...

void RB_delete_fixup (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x, ACE_RB_Tree_Node< EXT_ID, INT_ID > *parent)
 Method for restoring Red-Black properties after deletion. More...

ACE_RB_Tree_Node< EXT_ID,
INT_ID > * 		RB_tree_successor (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const
 Method to find the successor node of the given node in the tree. More...

ACE_RB_Tree_Node< EXT_ID,
INT_ID > * 		RB_tree_predecessor (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const
 Method to find the predecessor node of the given node in the tree. More...

ACE_RB_Tree_Node< EXT_ID,
INT_ID > * 		RB_tree_minimum (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const
 Method to find the minimum node of the subtree rooted at the given node. More...

ACE_RB_Tree_Node< EXT_ID,
INT_ID > * 		RB_tree_maximum (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const
 Method to find the maximum node of the subtree rooted at the given node. More...

ACE_RB_Tree_Node< EXT_ID,
INT_ID > * 		find_node (const EXT_ID &k, ACE_RB_Tree_Base::RB_SearchResult &result)
void RB_rebalance (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x)
 Rebalance the tree after insertion of a node. More...

int close_i (void)
 Close down an RB_Tree. this method should only be called with locks already held. More...

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)
 Removes the item associated with the given key from the tree and destroys it. More...

void dump_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *node) const
 Recursive function to dump the state of an object. More...

void dump_node_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > &node) const
 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. More...


Private Attributes

ACE_Allocator * allocator_
 Pointer to a memory allocator. More...

ACE_LOCK lock_
 Synchronization variable for the MT_SAFE <ACE_RB_Tree>. More...

ACE_RB_Tree_Node< EXT_ID,
INT_ID > * 		root_
 The root of the tree. More...

COMPARE_KEYS compare_keys_
 Comparison functor for comparing nodes in the tree. More...

size_t current_size_
 The current number of nodes in the tree. More...


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 >

Detailed Description

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
class ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >

Implements a Red-Black Tree ADT, according to T. H. Corman, C. E. Leiserson, and R. L. Rivest, "Introduction to Algorithms" 1990, MIT, chapter 14.

A number of Changes have been made to this class template in order to conform to the ACE_Hash_Map_Manager_Ex interface. All previously supported public methods are still part of this class. However, these are marked as DEPRECATED and will be removed from this class in a future version of ACE. Please migrate your code to the appropriate public methods indicated in the method deprecation comments. This class uses an <ACE_Allocator> to allocate memory. The user can make this a persistent class by providing an <ACE_Allocator> with a persistable memory pool.

Requirements and Performance Characteristics

Definition at line 165 of file RB_Tree.h.

Member Typedef Documentation

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
typedef ACE_RB_Tree_Node<EXT_ID, INT_ID> ACE_RB_Tree::ENTRY
 

Definition at line 175 of file RB_Tree.h.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ACE_RB_Tree::iterator
 

Definition at line 182 of file RB_Tree.h.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ACE_RB_Tree::ITERATOR
 

Definition at line 178 of file RB_Tree.h.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
typedef EXT_ID ACE_RB_Tree::KEY
 

Definition at line 173 of file RB_Tree.h.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ACE_RB_Tree::reverse_iterator
 

Definition at line 183 of file RB_Tree.h.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ACE_RB_Tree::REVERSE_ITERATOR
 

Definition at line 179 of file RB_Tree.h.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
typedef INT_ID ACE_RB_Tree::VALUE
 

Definition at line 174 of file RB_Tree.h.

Constructor & Destructor Documentation

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 = 0 ) 
 

Constructor.

Definition at line 53 of file RB_Tree.cpp.

References ACE_ERROR, ACE_LIB_TEXT, ACE_TRACE, LM_ERROR, and open. 

00054   : allocator_ (alloc),
00055     root_ (0),
00056     current_size_ (0)
00057 {
00058   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
00059              "ACE_RB_Tree (ACE_Allocator *alloc)");
00060   if (this->open (alloc) == -1)
00061     ACE_ERROR ((LM_ERROR,
00062                 ACE_LIB_TEXT ("ACE_RB_Tree::ACE_RB_Tree\n")));
00063 }

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 ) 
 

Copy constructor.

Definition at line 68 of file RB_Tree.cpp.

References ACE_TRACE, ACE_WRITE_GUARD, ACE_RB_Tree_Iterator::first, insert_i, ACE_RB_Tree_Iterator::is_done, ACE_RB_Tree_Iterator::item, ACE_RB_Tree_Iterator::key, and ACE_RB_Tree_Iterator::next. 

00069   : allocator_ (rbt.allocator_),
00070     root_ (0),
00071     current_size_ (0)
00072 {
00073   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
00074              "ACE_RB_Tree (const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt)");
00075   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
00076 
00077   // Make a deep copy of the passed tree.
00078   ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
00079 
00080   for (iter.first ();
00081 
00082        iter.is_done () == 0; iter.next ())
00083     insert_i (*(iter.key ()),
00084               *(iter.item ()));
00085 }

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 (  void    )  [virtual]
 

Destructor.

Definition at line 90 of file RB_Tree.cpp.

References ACE_TRACE, and close. 

00091 {
00092   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree");
00093 
00094   // Use the locked public method, to be totally safe, as the class
00095   // can be used with an allocator and placement new.
00096   this->close ();
00097 }

Member Function Documentation

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 589 of file RB_Tree.i.

References ACE_TRACE. 

00590 {
00591   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::begin");
00592 
00593   return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this);
00594 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 190 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and insert_i. 

00193 {
00194   ACE_TRACE ("ACE_RB_Tree::bind (const EXT_ID &ext_id, const INT_ID &int_id, "
00195              "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00196   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00197 
00198   return this->insert_i (ext_id, int_id, entry);
00199 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 173 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and insert_i. 

00175 {
00176   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::bind (const EXT_ID &item, const INT_ID &int_id)");
00177   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00178 
00179   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
00180   return this->insert_i (ext_id, int_id, entry);
00181 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::clear (  void    ) 
 

Deprecated:
Destroys all nodes and sets the root pointer null.

Definition at line 694 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD, and close_i. 

00695 {
00696   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear");
00697   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
00698 
00699   this->close_i ();
00700 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 157 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and close_i.

Referenced by ~ACE_RB_Tree. 

00158 {
00159   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close");
00160   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00161 
00162   return this->close_i ();
00163 }

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 (  void    )  [protected]
 

Close down an RB_Tree. this method should only be called with locks already held.

Definition at line 530 of file RB_Tree.cpp.

References ACE_TRACE, current_size_, and root_.

Referenced by clear, close, open, and operator=. 

00531 {
00532   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i");
00533 
00534   delete root_;
00535   current_size_ = 0;
00536   root_ = 0;
00537 
00538   return 0;
00539 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 706 of file RB_Tree.i.

References ACE_TRACE, and current_size_. 

00707 {
00708   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::current_size");
00709   return current_size_;
00710 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE void ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::dump (  void    )  const
 

Dump the state of an object.

Definition at line 572 of file RB_Tree.i.

References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_LIB_TEXT, ACE_TRACE, allocator_, ACE_Allocator::dump, dump_i, LM_DEBUG, and lock_. 

00573 {
00574   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump");
00575   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
00576   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\ncurrent_size_ = %d\n"), this->current_size_));
00577   this->allocator_->dump ();
00578   this->lock_.dump ();
00579   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nDumping nodes from root\n")));
00580   this->dump_i (this->root_);
00581   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
00582 }

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 >::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 812 of file RB_Tree.cpp.

References ACE_DEBUG, ACE_LIB_TEXT, dump_node_i, ACE_RB_Tree_Node::left, LM_DEBUG, and ACE_RB_Tree_Node::right.

Referenced by dump. 

00813 {
00814   if (node)
00815     {
00816       dump_node_i (*node);
00817 
00818       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\ndown left\n")));
00819       this->dump_i (node->left ());
00820       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nup left\n")));
00821 
00822       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\ndown right\n")));
00823       this->dump_i (node->right ());
00824       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nup right\n")));
00825     }
00826   else
00827     {
00828       ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT ("\nNULL POINTER (BLACK)\n")));
00829     }
00830 }

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 >::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.

Definition at line 839 of file RB_Tree.cpp.

References ACE_DEBUG, ACE_LIB_TEXT, ACE_RB_Tree_Node::color, LM_DEBUG, and ACE_RB_Tree_Node_Base::RED.

Referenced by dump_i. 

00840 {
00841   const char * color_str = (node.color () == ACE_RB_Tree_Node_Base::RED)
00842                            ? "RED" : "BLACK";
00843 
00844   ACE_DEBUG ((LM_DEBUG,  ACE_LIB_TEXT (" color=[%s]\n"), color_str));
00845 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 601 of file RB_Tree.i.

References ACE_TRACE. 

00602 {
00603   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::end");
00604 
00605   return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ();
00606 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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.

Deprecated:
signature will change to become int find (const EXT_ID &ext_id); which will return 0 if the <ext_id> is in the tree, otherwise -1.

Definition at line 638 of file RB_Tree.i.

References ACE_READ_GUARD_RETURN, ACE_TRACE, find_i, and ACE_RB_Tree_Node::item. 

00639 {
00640   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find (const EXT_ID &k)");
00641 
00642   // The reinterpret cast is to ensure that when this deprecated method is removed, and
00643   // is replaced (as planned) by a find method that takes the same argument signature
00644   // but returns an int, that the compiler will cough if this return macro is not
00645   // changed to just return an int (whose value will be -1).  Please leave this as is.
00646   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, ACE_reinterpret_cast(INT_ID*, 0L));
00647 
00648   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
00649   int result = this->find_i (k, entry);
00650   return (result == 0) ? &(entry->item ()) : 0;
00651 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 457 of file RB_Tree.i.

References ACE_READ_GUARD_RETURN, ACE_TRACE, and find_i. 

00459 {
00460   ACE_TRACE ("ACE_RB_Tree::find (const EXT_ID &ext_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00461   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00462 
00463   return this->find_i (ext_id, entry);
00464 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 435 of file RB_Tree.i.

References ACE_READ_GUARD_RETURN, ACE_TRACE, find_i, and ACE_RB_Tree_Node::item. 

00437 {
00438   ACE_TRACE ("ACE_RB_Tree::find (const EXT_ID &ext_id, INT_ID &int_id)");
00439   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00440 
00441   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry = 0;
00442 
00443   int result = this->find_i (ext_id, entry);
00444   if (result == 0)
00445     {
00446       int_id = entry->item ();
00447     }
00448 
00449   return result;
00450 }

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 &    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 546 of file RB_Tree.cpp.

References ACE_TRACE, ACE_RB_Tree_Base::EXACT, find_node, ACE_RB_Tree_Base::LEFT, and ACE_RB_Tree_Base::RB_SearchResult.

Referenced by find. 

00548 {
00549   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_i");
00550 
00551   // Try to find a match.
00552   RB_SearchResult result = LEFT;
00553   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00554 
00555   if (current)
00556     {
00557       // Found a match
00558       if (!find_exact || result == EXACT)
00559         entry = current;  // Assign the entry for any match.
00560       return (result == EXACT ? 0 : -1);
00561     }
00562   else
00563     // The node is not there.
00564     return -1;
00565 }

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
)  [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 327 of file RB_Tree.cpp.

References ACE_TRACE, ACE_RB_Tree_Base::EXACT, ACE_RB_Tree_Node::key, ACE_RB_Tree_Node::left, ACE_RB_Tree_Base::LEFT, lessthan, ACE_RB_Tree_Base::RB_SearchResult, ACE_RB_Tree_Base::RIGHT, ACE_RB_Tree_Node::right, and root_.

Referenced by find_i, insert_i, and remove_i. 

00328 {
00329   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_node");
00330 
00331   // Start at the root.
00332   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = root_;
00333 
00334   while (current)
00335     {
00336       // While there are more nodes to examine.
00337       if (this->lessthan (current->key (), k))
00338         {
00339           // If the search key is greater than the current node's key.
00340           if (current->right ())
00341             // If the right subtree is not empty, search to the right.
00342             current = current->right ();
00343           else
00344             {
00345               // If the right subtree is empty, we're done searching,
00346               // and are positioned to the left of the insertion point.
00347               result = LEFT;
00348               break;
00349             }
00350         }
00351       else if (this->lessthan (k, current->key ()))
00352         {
00353           // Else if the search key is less than the current node's key.
00354           if (current->left ())
00355             // If the left subtree is not empty, search to the left.
00356             current = current->left ();
00357           else
00358             {
00359               // If the left subtree is empty, we're done searching,
00360               // and are positioned to the right of the insertion point.
00361               result = RIGHT;
00362               break;
00363             }
00364         }
00365       else
00366         {
00367           // If the keys match exactly, we're done as well.
00368           result = EXACT;
00369           break;
00370         }
00371     }
00372 
00373   return current;
00374 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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. 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.

Deprecated:

Definition at line 664 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and insert_i. 

00665 {
00666   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert");
00667   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, ACE_reinterpret_cast(INT_ID*, 0L));
00668 
00669   return this->insert_i (k, t);
00670 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i (  const EXT_ID &    k,
const INT_ID &    t,
ACE_RB_Tree_Node< EXT_ID, INT_ID > *&    entry
)  [protected]
 

Inserts a *copy* of the key and the item into the tree: both the key type EXT_ID and the item type INT_ID must have well defined semantics for copy construction. The default implementation also requires that the key type support well defined < semantics. This method passes back a pointer to the inserted (or existing) node, and the search status. If the node already exists, the method returns 1. If the node does not exist, and a new one is successfully created, and the method returns 0. If there was an error, the method returns -1.

Definition at line 684 of file RB_Tree.cpp.

References ACE_ERROR_RETURN, ACE_LIB_TEXT, ACE_NEW_RETURN, ACE_TRACE, ACE_RB_Tree_Node_Base::BLACK, current_size_, ACE_RB_Tree_Base::EXACT, find_node, ACE_RB_Tree_Node::left, ACE_RB_Tree_Base::LEFT, LM_ERROR, RB_rebalance, ACE_RB_Tree_Base::RB_SearchResult, ACE_RB_Tree_Node::right, and root_. 

00687 {
00688   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t, "
00689              "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00690 
00691   // Find the closest matching node, if there is one.
00692   RB_SearchResult result = LEFT;
00693   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00694   if (current)
00695     {
00696       // If the keys match, just return a pointer to the node's item.
00697       if (result == EXACT)
00698         {
00699           entry = current;
00700           return 1;
00701         }
00702       // Otherwise if we're to the left of the insertion
00703       // point, insert into the right subtree.
00704       else if (result == LEFT)
00705         {
00706           if (current->right ())
00707             {
00708               // If there is already a right subtree, complain.
00709               ACE_ERROR_RETURN ((LM_ERROR,
00710                                  ACE_LIB_TEXT ("%p\n"),
00711                                  ACE_LIB_TEXT ("\nright subtree already present in ")
00712                                  ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00713                                 -1);
00714             }
00715           else
00716             {
00717               // The right subtree is empty: insert new node there.
00718               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00719               ACE_NEW_RETURN (tmp,
00720                               (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00721                               -1);
00722               current->right (tmp);
00723 
00724               // If the node was successfully inserted, set its parent, rebalance
00725               // the tree, color the root black, and return a pointer to the
00726               // inserted item.
00727               entry = current->right ();
00728               current->right ()->parent (current);
00729               RB_rebalance (current->right ());
00730               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00731               ++current_size_;
00732               return 0;
00733             }
00734         }
00735       // Otherwise, we're to the right of the insertion point, so
00736       // insert into the left subtree.
00737       else // (result == RIGHT)
00738         {
00739           if (current->left ())
00740             // If there is already a left subtree, complain.
00741             ACE_ERROR_RETURN ((LM_ERROR,
00742                                ACE_LIB_TEXT ("%p\n"),
00743                                ACE_LIB_TEXT ("\nleft subtree already present in ")
00744                                ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00745                               -1);
00746           else
00747             {
00748               // The left subtree is empty: insert new node there.
00749               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00750               ACE_NEW_RETURN (tmp,
00751                               (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00752                               -1);
00753               current->left (tmp);
00754               // If the node was successfully inserted, set its
00755               // parent, rebalance the tree, color the root black, and
00756               // return a pointer to the inserted item.
00757               entry = current->left ();
00758               current->left ()->parent (current);
00759               RB_rebalance (current->left ());
00760               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00761               ++current_size_;
00762               return 0;
00763             }
00764         }
00765     }
00766   else
00767     {
00768       // The tree is empty: insert at the root and color the root black.
00769       ACE_NEW_RETURN (root_,
00770                       (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00771                       -1);
00772       root_->color (ACE_RB_Tree_Node_Base::BLACK);
00773       ++current_size_;
00774       entry = root_;
00775       return 0;
00776     }
00777 }

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
)  [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. 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.

Definition at line 577 of file RB_Tree.cpp.

References ACE_ERROR_RETURN, ACE_LIB_TEXT, ACE_NEW_RETURN, ACE_TRACE, ACE_RB_Tree_Node_Base::BLACK, current_size_, ACE_RB_Tree_Base::EXACT, find_node, ACE_RB_Tree_Node::item, ACE_RB_Tree_Node::left, ACE_RB_Tree_Base::LEFT, LM_ERROR, RB_rebalance, ACE_RB_Tree_Base::RB_SearchResult, ACE_RB_Tree_Node::right, and root_.

Referenced by ACE_RB_Tree, bind, insert, operator=, rebind, and trybind. 

00578 {
00579   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t)");
00580 
00581   // Find the closest matching node, if there is one.
00582   RB_SearchResult result = LEFT;
00583   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00584   if (current)
00585     {
00586       // If the keys match, just return a pointer to the node's item.
00587       if (result == EXACT)
00588         return &current->item ();
00589 
00590       // Otherwise if we're to the left of the insertion point, insert
00591       // into the right subtree.
00592       else if (result == LEFT)
00593         {
00594           if (current->right ())
00595             {
00596               // If there is already a right subtree, complain.
00597               ACE_ERROR_RETURN ((LM_ERROR,
00598                                  ACE_LIB_TEXT ("%p\n"),
00599                                  ACE_LIB_TEXT ("\nright subtree already present in ")
00600                                  ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00601                                 0);
00602             }
00603           else
00604             {
00605               // The right subtree is empty: insert new node there.
00606               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00607 
00608               ACE_NEW_RETURN (tmp,
00609                               (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00610                               0);
00611               current->right (tmp);
00612 
00613               // If the node was successfully inserted, set its
00614               // parent, rebalance the tree, color the root black, and
00615               // return a pointer to the inserted item.
00616               INT_ID *item = &(current->right ()->item ());
00617               current->right ()->parent (current);
00618               RB_rebalance (current->right ());
00619               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00620               ++current_size_;
00621               return item;
00622             }
00623         }
00624       // Otherwise, we're to the right of the insertion point, so
00625       // insert into the left subtree.
00626       else // (result == RIGHT)
00627         {
00628           if (current->left ())
00629             // If there is already a left subtree, complain.
00630             ACE_ERROR_RETURN ((LM_ERROR,
00631                                ACE_LIB_TEXT ("%p\n"),
00632                                ACE_LIB_TEXT ("\nleft subtree already present in ")
00633                                ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00634                               0);
00635           else
00636             {
00637               // The left subtree is empty: insert new node there.
00638               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00639               ACE_NEW_RETURN (tmp,
00640                               (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00641                               0);
00642               current->left (tmp);
00643 
00644               // If the node was successfully inserted, set its
00645               // parent, rebalance the tree, color the root black, and
00646               // return a pointer to the inserted item.
00647               INT_ID *item = &current->left ()->item ();
00648               current->left ()->parent (current);
00649               RB_rebalance (current->left ());
00650               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00651               ++current_size_;
00652               return item;
00653             }
00654         }
00655     }
00656   else
00657     {
00658       // The tree is empty: insert at the root and color the root
00659       // black.
00660       ACE_NEW_RETURN (root_,
00661                       (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00662                       0);
00663       if (root_)
00664         {
00665           root_->color (ACE_RB_Tree_Node_Base::BLACK);
00666           ++current_size_;
00667           return &root_->item ();
00668         }
00669     }
00670   return 0;
00671 }

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
)  [virtual]
 

Less than comparison function for keys, using comparison functor.

Definition at line 129 of file RB_Tree.cpp.

References ACE_TRACE, and compare_keys_.

Referenced by find_node. 

00130 {
00131   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan");
00132   return this->compare_keys_ (k1, k2);
00133 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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. NOTE: the right name would be <lock>, but HP/C++ will choke on that!

Definition at line 561 of file RB_Tree.i.

References ACE_TRACE, and lock_. 

00562 {
00563   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::mutex");
00564   return this->lock_;
00565 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::open (  ACE_Allocator *    alloc = 0 ) 
 

Initialize an RB Tree.

Definition at line 132 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, allocator_, close_i, and ACE_Allocator::instance.

Referenced by ACE_RB_Tree. 

00133 {
00134   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::open");
00135   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00136 
00137   // Calling this->close_i () ensures we release previously allocated
00138   // memory before allocating new memory.
00139   this->close_i ();
00140 
00141   // If we were passed an allocator use it,
00142   // otherwise use the default instance.
00143 
00144   if (alloc == 0)
00145     alloc = ACE_Allocator::instance ();
00146 
00147   this->allocator_ = alloc;
00148 
00149   return 0;
00150 }

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 ) 
 

Assignment operator.

Definition at line 102 of file RB_Tree.cpp.

References ACE_TRACE, ACE_WRITE_GUARD, allocator_, close_i, ACE_RB_Tree_Iterator::first, insert_i, ACE_RB_Tree_Iterator::is_done, ACE_RB_Tree_Iterator::item, ACE_RB_Tree_Iterator::key, and ACE_RB_Tree_Iterator::next. 

00103 {
00104   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator =");
00105   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
00106 
00107   if (this != &rbt)
00108     {
00109       // Clear out the existing tree.
00110       close_i ();
00111 
00112       // Make a deep copy of the passed tree.
00113       ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
00114 
00115       for (iter.first ();
00116            iter.is_done () == 0;
00117            iter.next ())
00118         insert_i (*(iter.key ()),
00119                   *(iter.item ()));
00120 
00121       // Use the same allocator as the rhs.
00122       allocator_ = rbt.allocator_;
00123     }
00124 }

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,
ACE_RB_Tree_Node< EXT_ID, INT_ID > *    parent
)  [protected]
 

Method for restoring Red-Black properties after deletion.

Definition at line 217 of file RB_Tree.cpp.

References ACE_TRACE, ACE_RB_Tree_Node_Base::BLACK, ACE_RB_Tree_Node::color, ACE_RB_Tree_Node::left, ACE_RB_Tree_Node::parent, RB_rotate_left, RB_rotate_right, ACE_RB_Tree_Node_Base::RED, ACE_RB_Tree_Node::right, and root_.

Referenced by remove_i. 

00219 {
00220   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_delete_fixup");
00221 
00222   while (x != this->root_
00223          && (!x
00224              || x->color () == ACE_RB_Tree_Node_Base::BLACK))
00225     {
00226       if (x == parent->left ())
00227         {
00228           ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = parent->right ();
00229           if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
00230             {
00231               w->color (ACE_RB_Tree_Node_Base::BLACK);
00232               parent->color (ACE_RB_Tree_Node_Base::RED);
00233               RB_rotate_left (parent);
00234               w = parent->right ();
00235             }
00236           // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00237           if (w
00238               && (!w->left ()
00239                   || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
00240               && (!w->right ()
00241                   || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
00242             {
00243               w->color (ACE_RB_Tree_Node_Base::RED);
00244               x = parent;
00245               parent = x->parent ();
00246             }
00247           else
00248             {
00249               // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00250               if (w
00251                   && (!w->right ()
00252                       || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
00253                 {
00254                   if (w->left ())
00255                     w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
00256                   w->color (ACE_RB_Tree_Node_Base::RED);
00257                   RB_rotate_right (w);
00258                   w = parent->right ();
00259                 }
00260               if (w)
00261                 {
00262                   w->color (parent->color ());
00263                   if (w->right ())
00264                     w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
00265                 }
00266               parent->color (ACE_RB_Tree_Node_Base::BLACK);
00267               RB_rotate_left (parent);
00268               x = root_;
00269             }
00270         }
00271       else
00272         {
00273           ACE_RB_Tree_Node<EXT_ID, INT_ID> *w = parent->left ();
00274           if (w && w->color () == ACE_RB_Tree_Node_Base::RED)
00275             {
00276               w->color (ACE_RB_Tree_Node_Base::BLACK);
00277               parent->color (ACE_RB_Tree_Node_Base::RED);
00278               RB_rotate_right (parent);
00279               w = parent->left ();
00280             }
00281           // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00282           if (w
00283               && (!w->left ()
00284                   || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK)
00285               && (!w->right ()
00286                   || w->right ()->color () == ACE_RB_Tree_Node_Base::BLACK))
00287             {
00288               w->color (ACE_RB_Tree_Node_Base::RED);
00289               x = parent;
00290               parent = x->parent ();
00291             }
00292           else
00293             {
00294               // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00295               if (w
00296                   && (!w->left ()
00297                       || w->left ()->color () == ACE_RB_Tree_Node_Base::BLACK))
00298                 {
00299                   w->color (ACE_RB_Tree_Node_Base::RED);
00300                   if (w->right ())
00301                     w->right ()->color (ACE_RB_Tree_Node_Base::BLACK);
00302                   RB_rotate_left (w);
00303                   w = parent->left ();
00304                 }
00305               if (w)
00306                 {
00307                   w->color (parent->color ());
00308                   if (w->left ())
00309                     w->left ()->color (ACE_RB_Tree_Node_Base::BLACK);
00310                 }
00311               parent->color (ACE_RB_Tree_Node_Base::BLACK);
00312               RB_rotate_right (parent);
00313               x = root_;
00314             }
00315         }
00316     }
00317 
00318   if (x)
00319     x->color (ACE_RB_Tree_Node_Base::BLACK);
00320 }

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 )  [protected]
 

Rebalance the tree after insertion of a node.

Definition at line 379 of file RB_Tree.cpp.

References ACE_ERROR, ACE_LIB_TEXT, ACE_TRACE, ACE_RB_Tree_Node_Base::BLACK, ACE_RB_Tree_Node::color, LM_ERROR, ACE_RB_Tree_Node::parent, RB_rotate_left, RB_rotate_right, and ACE_RB_Tree_Node_Base::RED.

Referenced by insert_i. 

00380 {
00381   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rebalance");
00382 
00383   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = 0;
00384 
00385   while (x &&
00386          x->parent ()
00387          && x->parent ()->color () == ACE_RB_Tree_Node_Base::RED)
00388     {
00389       if (! x->parent ()->parent ())
00390         {
00391           // If we got here, something is drastically wrong!
00392           ACE_ERROR ((LM_ERROR,
00393                       ACE_LIB_TEXT ("%p\n"),
00394                       ACE_LIB_TEXT ("\nerror: parent's parent is null in ")
00395                       ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rebalance\n")));
00396           return;
00397         }
00398 
00399       if (x->parent () == x->parent ()->parent ()->left ())
00400         {
00401           y = x->parent ()->parent ()->right ();
00402           if (y && y->color () == ACE_RB_Tree_Node_Base::RED)
00403             {
00404               // Handle case 1 (see CLR book, pp. 269).
00405               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
00406               y->color (ACE_RB_Tree_Node_Base::BLACK);
00407               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
00408               x = x->parent ()->parent ();
00409             }
00410           else
00411             {
00412               if (x == x->parent ()->right ())
00413                 {
00414                   // Transform case 2 into case 3 (see CLR book, pp. 269).
00415                   x = x->parent ();
00416                   RB_rotate_left (x);
00417                 }
00418 
00419               // Handle case 3 (see CLR book, pp. 269).
00420               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
00421               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
00422               RB_rotate_right (x->parent ()->parent ());
00423             }
00424         }
00425       else
00426         {
00427           y = x->parent ()->parent ()->left ();
00428           if (y && y->color () == ACE_RB_Tree_Node_Base::RED)
00429             {
00430               // Handle case 1 (see CLR book, pp. 269).
00431               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
00432               y->color (ACE_RB_Tree_Node_Base::BLACK);
00433               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
00434               x = x->parent ()->parent ();
00435             }
00436           else
00437             {
00438               if (x == x->parent ()->left ())
00439                 {
00440                   // Transform case 2 into case 3 (see CLR book, pp. 269).
00441                   x = x->parent ();
00442                   RB_rotate_right (x);
00443                 }
00444 
00445               // Handle case 3 (see CLR book, pp. 269).
00446               x->parent ()->color (ACE_RB_Tree_Node_Base::BLACK);
00447               x->parent ()->parent ()->color (ACE_RB_Tree_Node_Base::RED);
00448               RB_rotate_left (x->parent ()->parent ());
00449             }
00450         }
00451     }
00452 }

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 )  [protected]
 

Method for left rotation of the tree about a given node.

Definition at line 177 of file RB_Tree.cpp.

References ACE_ERROR, ACE_LIB_TEXT, ACE_TRACE, ACE_RB_Tree_Node::left, LM_ERROR, ACE_RB_Tree_Node::parent, ACE_RB_Tree_Node::right, and root_.

Referenced by RB_delete_fixup, and RB_rebalance. 

00178 {
00179   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left");
00180 
00181   if (! x)
00182     ACE_ERROR ((LM_ERROR,
00183                 ACE_LIB_TEXT ("%p\n"),
00184                 ACE_LIB_TEXT ("\nerror: x is a null pointer in ")
00185                 ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
00186   else if (! (x->right()))
00187     ACE_ERROR ((LM_ERROR,
00188                 ACE_LIB_TEXT ("%p\n"),
00189                 ACE_LIB_TEXT ("\nerror: x->right () is a null pointer ")
00190                 ACE_LIB_TEXT ("in ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
00191   else
00192     {
00193       ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
00194       y = x->right ();
00195       x->right (y->left ());
00196       if (y->left ())
00197         y->left ()->parent (x);
00198       y->parent (x->parent ());
00199       if (x->parent ())
00200         {
00201           if (x == x->parent ()->left ())
00202             x->parent ()->left (y);
00203           else
00204             x->parent ()->right (y);
00205         }
00206       else
00207         root_ = y;
00208       y->left (x);
00209       x->parent (y);
00210     }
00211 }

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 )  [protected]
 

Method for right rotation of the tree about a given node.

Definition at line 138 of file RB_Tree.cpp.

References ACE_ERROR, ACE_LIB_TEXT, ACE_TRACE, ACE_RB_Tree_Node::left, LM_ERROR, ACE_RB_Tree_Node::parent, ACE_RB_Tree_Node::right, and root_.

Referenced by RB_delete_fixup, and RB_rebalance. 

00139 {
00140   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right");
00141 
00142   if (!x)
00143     ACE_ERROR ((LM_ERROR,
00144                 ACE_LIB_TEXT ("%p\n"),
00145                 ACE_LIB_TEXT ("\nerror: x is a null pointer in ")
00146                 ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
00147   else if (! (x->left()))
00148     ACE_ERROR ((LM_ERROR,
00149                 ACE_LIB_TEXT ("%p\n"),
00150                 ACE_LIB_TEXT ("\nerror: x->left () is a null pointer in ")
00151                 ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
00152   else
00153     {
00154       ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
00155       y = x->left ();
00156       x->left (y->right ());
00157       if (y->right ())
00158         y->right ()->parent (x);
00159       y->parent (x->parent ());
00160       if (x->parent ())
00161         {
00162           if (x == x->parent ()->right ())
00163             x->parent ()->right (y);
00164           else
00165             x->parent ()->left (y);
00166         }
00167       else
00168         root_ = y;
00169       y->right (x);
00170       x->parent (y);
00171     }
00172 }

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 [protected]
 

Method to find the maximum node of the subtree rooted at the given node.

Definition at line 516 of file RB_Tree.cpp.

References ACE_TRACE, and ACE_RB_Tree_Node::right.

Referenced by RB_tree_predecessor. 

00517 {
00518   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum");
00519 
00520   while ((x) && (x->right ()))
00521     x = x->right ();
00522 
00523   return x;
00524 }

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 [protected]
 

Method to find the minimum node of the subtree rooted at the given node.

Definition at line 503 of file RB_Tree.cpp.

References ACE_TRACE, and ACE_RB_Tree_Node::left.

Referenced by RB_tree_successor. 

00504 {
00505   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum");
00506 
00507   while ((x) && (x->left ()))
00508     x = x->left ();
00509 
00510   return x;
00511 }

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 [protected]
 

Method to find the predecessor node of the given node in the tree.

Definition at line 480 of file RB_Tree.cpp.

References ACE_TRACE, ACE_RB_Tree_Node::left, ACE_RB_Tree_Node::parent, and RB_tree_maximum. 

00481 {
00482   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor");
00483   if (x == 0)
00484     return 0;
00485 
00486   if (x->left ())
00487     return RB_tree_maximum (x->left ());
00488 
00489   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
00490 
00491   while ((y) && (x == y->left ()))
00492     {
00493       x = y;
00494       y = y->parent ();
00495     }
00496 
00497   return y;
00498 }

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 [protected]
 

Method to find the successor node of the given node in the tree.

Definition at line 457 of file RB_Tree.cpp.

References ACE_TRACE, ACE_RB_Tree_Node::parent, RB_tree_minimum, and ACE_RB_Tree_Node::right.

Referenced by remove_i. 

00458 {
00459   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor");
00460 
00461   if (x == 0)
00462     return 0;
00463 
00464   if (x->right ())
00465     return RB_tree_minimum (x->right ());
00466 
00467   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
00468   while ((y) && (x == y->right ()))
00469     {
00470       x = y;
00471       y = y->parent ();
00472     }
00473 
00474   return y;
00475 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 613 of file RB_Tree.i.

References ACE_TRACE. 

00614 {
00615   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rbegin");
00616 
00617   return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this);
00618 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 405 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, insert_i, ACE_RB_Tree_Node::item, and ACE_RB_Tree_Node::key. 

00410 {
00411   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id, "
00412              "EXT_ID &old_ext_id, INT_ID &old_int_id, "
00413              "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00414   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00415 
00416   int result = this->insert_i (ext_id, int_id, entry);
00417 
00418   if (result == 1)
00419     {
00420       old_ext_id = entry->key ();
00421       old_int_id = entry->item ();
00422       entry->key () = ext_id;
00423       entry->item () = int_id;
00424     }
00425 
00426   return result;
00427 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 375 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, insert_i, ACE_RB_Tree_Node::item, and ACE_RB_Tree_Node::key. 

00379 {
00380   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id,"
00381              "EXT_ID &old_ext_id, INT_ID &old_int_id)");
00382   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00383 
00384   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
00385   int result = this->insert_i (ext_id, int_id, entry);
00386 
00387   if (result == 1)
00388     {
00389       old_ext_id = entry->key ();
00390       old_int_id = entry->item ();
00391       entry->key () = ext_id;
00392       entry->item () = int_id;
00393     }
00394 
00395   return result;
00396 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 342 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, insert_i, ACE_RB_Tree_Node::item, and ACE_RB_Tree_Node::key. 

00346 {
00347   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id,"
00348              "INT_ID &old_int_id, ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00349   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00350 
00351   int result = this->insert_i (ext_id, int_id, entry);
00352 
00353   if (result == 1)
00354     {
00355       old_int_id = entry->item ();
00356       entry->key () = ext_id;
00357       entry->item () = int_id;
00358     }
00359 
00360   return result;
00361 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 314 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, insert_i, ACE_RB_Tree_Node::item, and ACE_RB_Tree_Node::key. 

00317 {
00318   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, "
00319              "const INT_ID &int_id, INT_ID &old_int_id)");
00320   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00321 
00322   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
00323   int result = this->insert_i (ext_id, int_id, entry);
00324 
00325   if (result == 1)
00326     {
00327       old_int_id = entry->item ();
00328       entry->key () = ext_id;
00329       entry->item () = int_id;
00330     }
00331 
00332   return result;
00333 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 286 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, insert_i, ACE_RB_Tree_Node::item, and ACE_RB_Tree_Node::key. 

00289 {
00290   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id, "
00291              "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00292   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00293 
00294   int result = this->insert_i (ext_id, int_id, entry);
00295 
00296   if (result == 1)
00297     {
00298       entry->key () = ext_id;
00299       entry->item () = int_id;
00300     }
00301 
00302   return result;
00303 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 261 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, insert_i, ACE_RB_Tree_Node::item, and ACE_RB_Tree_Node::key. 

00263 {
00264   ACE_TRACE ("ACE_RB_Tree::rebind (const EXT_ID &ext_id, const INT_ID &int_id)");
00265   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00266 
00267   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
00268   int result = this->insert_i (ext_id, int_id, entry);
00269 
00270   if (result == 1)
00271     {
00272       entry->key () = ext_id;
00273       entry->item () = int_id;
00274     }
00275 
00276   return result;
00277 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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.

Deprecated:

Definition at line 680 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and remove_i. 

00681 {
00682   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove");
00683   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00684 
00685   INT_ID i;
00686   return this->remove_i (k, i);
00687 }

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 )  [protected]
 

Removes the item associated with the given key from the tree and destroys it.

Definition at line 934 of file RB_Tree.cpp.

References ACE_TRACE, ACE_RB_Tree_Node_Base::BLACK, ACE_RB_Tree_Node::color, current_size_, ACE_RB_Tree_Node::item, ACE_RB_Tree_Node::key, ACE_RB_Tree_Node::left, ACE_RB_Tree_Node::parent, RB_delete_fixup, RB_tree_successor, ACE_RB_Tree_Node::right, and root_. 

00935 {
00936   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z)");
00937 
00938   // Delete the node and reorganize the tree to satisfy the Red-Black
00939   // properties.
00940 
00941   ACE_RB_Tree_Node<EXT_ID, INT_ID> *x;
00942   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y;
00943   ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent;
00944 
00945   if (z->left () && z->right ())
00946     y = RB_tree_successor (z);
00947   else
00948     y = z;
00949 
00950   if (y->left ())
00951     x = y->left ();
00952   else
00953     x = y->right ();
00954 
00955   parent = y->parent ();
00956   if (x)
00957     {
00958       x->parent (parent);
00959     }
00960 
00961   if (parent)
00962     {
00963       if (y == parent->left ())
00964         parent->left (x);
00965       else
00966         parent->right (x);
00967     }
00968   else
00969     this->root_ = x;
00970 
00971   if (y != z)
00972     {
00973       // Copy the elements of y into z.
00974       z->key () = y->key ();
00975       z->item () = y->item ();
00976     }
00977 
00978   // CLR pp. 263 says that nil nodes are implicitly colored BLACK
00979   if (!y || y->color () == ACE_RB_Tree_Node_Base::BLACK)
00980     RB_delete_fixup (x, parent);
00981 
00982   y->parent (0);
00983   y->right (0);
00984   y->left (0);
00985   delete y;
00986   --current_size_;
00987 
00988   return 0;
00989 }

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
)  [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 786 of file RB_Tree.cpp.

References ACE_TRACE, ACE_RB_Tree_Base::EXACT, find_node, ACE_RB_Tree_Node::item, ACE_RB_Tree_Base::LEFT, and ACE_RB_Tree_Base::RB_SearchResult.

Referenced by remove, and unbind. 

00787 {
00788   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (const EXT_ID &k, INT_ID &i)");
00789 
00790   // Find a matching node, if there is one.
00791   ACE_RB_Tree_Node<EXT_ID, INT_ID> *z;
00792   RB_SearchResult result = LEFT;
00793   z = find_node (k, result);
00794 
00795   // If there is a matching node: remove and destroy it.
00796   if (z && result == EXACT)
00797     {
00798       // Return the internal id stored in the deleted node.
00799       i = z->item ();
00800       return -1 == this->remove_i (z) ? -1 : 1;
00801     }
00802   else
00803   {
00804     // No matching node was found: return 0.
00805     return 0;
00806   }
00807 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 625 of file RB_Tree.i.

References ACE_TRACE. 

00626 {
00627   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rend");
00628 
00629   return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ();
00630 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::test_invariant (  void    ) 
 

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 850 of file RB_Tree.cpp.

References ACE_DEBUG, ACE_LIB_TEXT, ACE_READ_GUARD_RETURN, ACE_TRACE, LM_DEBUG, and test_invariant_recurse. 

00851 {
00852   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant");
00853   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00854 
00855   // Recurse from the root, starting with the measured black height at
00856   // 0, and the expected black height at -1, which will cause the
00857   // count from first measured path to a leaf to be used as the
00858   // expected one from that point onward (the key is to check
00859   // consistency).
00860   int expected_black_height = -1;
00861   if (this->test_invariant_recurse (this->root_, expected_black_height, 0) == 0)
00862     {
00863       ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("invariant holds\n")));
00864       return 0;
00865     }
00866 
00867   return -1;
00868 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::test_invariant_recurse (  ACE_RB_Tree_Node< EXT_ID, INT_ID > *    x,
int &    expected_black_height,
int    measured_black_height
)  [protected]
 

Recursively tests the invariant red-black properties at each node of the tree. Returns 0 if invariant holds, else -1.

Definition at line 873 of file RB_Tree.cpp.

References ACE_ERROR_RETURN, ACE_LIB_TEXT, ACE_TRACE, ACE_RB_Tree_Node::color, ACE_RB_Tree_Node::left, LM_ERROR, ACE_RB_Tree_Node_Base::RED, and ACE_RB_Tree_Node::right.

Referenced by test_invariant. 

00876 {
00877   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant_recurse");
00878 
00879   if (!x)
00880     {
00881       // Count each leaf (zero pointer) as a black node (per CLR algorithm description).
00882       ++measured_black_height;
00883 
00884       if (expected_black_height == -1)
00885         {
00886           expected_black_height = measured_black_height;
00887         }
00888       else if (expected_black_height != measured_black_height)
00889         {
00890           ACE_ERROR_RETURN ((LM_ERROR,
00891                              ACE_LIB_TEXT ("\nexpected_black_height = %d but ")
00892                              ACE_LIB_TEXT ("\nmeasured_black_height = %d in ")
00893                              ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n"),
00894                              expected_black_height, measured_black_height),
00895                             -1);
00896         }
00897 
00898       return 0;
00899     }
00900 
00901   // Check the invariant that a red node cannot have a red child.
00902   if (x->color () == ACE_RB_Tree_Node_Base::RED)
00903     {
00904       if (x->left () && x->left ()->color () == ACE_RB_Tree_Node_Base::RED)
00905         {
00906           ACE_ERROR_RETURN ((LM_ERROR,
00907                              ACE_LIB_TEXT ("%p\n"),
00908                              ACE_LIB_TEXT ("\nRED parent has RED left child in ")
00909                              ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
00910                             -1);
00911         }
00912 
00913       if (x->right () && x->right ()->color () == ACE_RB_Tree_Node_Base::RED)
00914         {
00915           ACE_ERROR_RETURN ((LM_ERROR,
00916                              ACE_LIB_TEXT ("%p\n"),
00917                              ACE_LIB_TEXT ("\nRED parent has RED right child in ")
00918                              ACE_LIB_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
00919                             -1);
00920         }
00921     }
00922   else
00923     {
00924       // Count each black node traversed.
00925       ++measured_black_height;
00926     }
00927 
00928   return (test_invariant_recurse (x->left (), expected_black_height, measured_black_height) == 0)
00929           ? test_invariant_recurse (x->right (), expected_black_height, measured_black_height)
00930           : -1;
00931 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 234 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, insert_i, and ACE_RB_Tree_Node::item. 

00237 {
00238   ACE_TRACE ("ACE_RB_Tree::trybind (const EXT_ID &ext_id, INT_ID &int_id, "
00239              "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00240   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00241 
00242   int result = this->insert_i (ext_id, int_id, entry);
00243 
00244   if (result == 1)
00245     {
00246       int_id = entry->item ();
00247     }
00248 
00249 
00250   return result;
00251 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 210 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, insert_i, and ACE_RB_Tree_Node::item. 

00212 {
00213   ACE_TRACE ("ACE_RB_Tree::trybind (const EXT_ID &ext_id, INT_ID &int_id)");
00214   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00215 
00216   ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry;
00217   int result = this->insert_i (ext_id, int_id, entry);
00218 
00219   if (result == 1)
00220     {
00221       int_id = entry->item ();
00222     }
00223 
00224   return result;
00225 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 543 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and remove_i. 

00544 {
00545   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (ACE_RB_Tree_Node<EXT_ID, INT_ID> *entry)");
00546   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00547 
00548   return this->remove_i (entry);
00549 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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 508 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and remove_i. 

00510 {
00511   ACE_TRACE ("ACE_RB_Tree::unbind (const EXT_ID &ext_id, INT_ID &int_id)");
00512   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00513 
00514   int result = this->remove_i (ext_id, int_id);
00515 
00516   // Remap the return codes from the internal method: this
00517   // is maintained this way in support of deprecated methods,
00518   // and will be cleaned up when these methods are removed.
00519   switch (result)
00520     {
00521       case 1:
00522         // If the node was found and deleted, return success.
00523         return 0;
00524       case 0:
00525         // If nothing was found, set errno and break.
00526         errno = ENOENT;
00527         break;
00528       case -1:
00529         // If an error happened, just break.
00530         break;
00531     }
00532 
00533   // Return an error if we didn't already return success.
00534   return -1;
00535 }

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_INLINE 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_id>s are *not* dynamically allocated...)

Definition at line 473 of file RB_Tree.i.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and remove_i. 

00474 {
00475   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::unbind (const EXT_ID &ext_id)");
00476   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00477 
00478   INT_ID int_id;
00479   int result = this->remove_i (ext_id, int_id);
00480 
00481   // Remap the return codes from the internal method: this
00482   // is maintained this way in support of deprecated methods,
00483   // and will be cleaned up when these methods are removed.
00484   switch (result)
00485     {
00486       case 1:
00487         // If the node was found and deleted, return success.
00488         return 0;
00489       case 0:
00490         // If nothing was found, set errno and break.
00491         errno = ENOENT;
00492         break;
00493       case -1:
00494         // If an error happened, just break.
00495         break;
00496     }
00497 
00498   // Return an error if we didn't already return success.
00499   return -1;
00500 }

Friends And Related Function Documentation

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
friend class ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > [friend]
 

Definition at line 170 of file RB_Tree.h.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
friend class ACE_RB_Tree_Iterator_Base< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > [friend]
 

Definition at line 169 of file RB_Tree.h.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
friend class ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > [friend]
 

Definition at line 171 of file RB_Tree.h.

Member Data Documentation

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_Allocator* ACE_RB_Tree::allocator_ [private]
 

Pointer to a memory allocator.

Definition at line 536 of file RB_Tree.h.

Referenced by dump, open, and operator=.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
COMPARE_KEYS ACE_RB_Tree::compare_keys_ [private]
 

Comparison functor for comparing nodes in the tree.

Definition at line 545 of file RB_Tree.h.

Referenced by lessthan.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
size_t ACE_RB_Tree::current_size_ [private]
 

The current number of nodes in the tree.

Definition at line 548 of file RB_Tree.h.

Referenced by close_i, current_size, insert_i, and remove_i.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_LOCK ACE_RB_Tree::lock_ [private]
 

Synchronization variable for the MT_SAFE <ACE_RB_Tree>.

Definition at line 539 of file RB_Tree.h.

Referenced by dump, and mutex.

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
ACE_RB_Tree_Node<EXT_ID, INT_ID>* ACE_RB_Tree::root_ [private]
 

The root of the tree.

Definition at line 542 of file RB_Tree.h.

Referenced by close_i, find_node, insert_i, RB_delete_fixup, RB_rotate_left, RB_rotate_right, and remove_i.

The documentation for this class was generated from the following files:
Generated on Mon Jun 16 12:54:40 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002