Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages | Search for 

ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > 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< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >:

Inheritance graph
[legend]
Collaboration diagram for ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >:

Collaboration graph
[legend]
List of all members.

Public Types

typedef EXT_ID KEY
typedef INT_ID VALUE
typedef ACE_LOCK lock_type
typedef ACE_RB_Tree_Node<
EXT_ID, INT_ID > 		ENTRY
typedef ACE_RB_Tree_Iterator<
EXT_ID, INT_ID, COMPARE_KEYS,
ACE_LOCK > 		ITERATOR
typedef ACE_RB_Tree_Reverse_Iterator<
EXT_ID, INT_ID, COMPARE_KEYS,
ACE_LOCK > 		REVERSE_ITERATOR
typedef ACE_RB_Tree_Iterator<
EXT_ID, INT_ID, COMPARE_KEYS,
ACE_LOCK > 		iterator
typedef ACE_RB_Tree_Reverse_Iterator<
EXT_ID, INT_ID, COMPARE_KEYS,
ACE_LOCK > 		reverse_iterator

Public Member Functions

 ACE_RB_Tree (ACE_Allocator *alloc=0)
 Constructor.

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

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

int close (void)
virtual ~ACE_RB_Tree (void)
 Destructor.

int bind (const EXT_ID &item, const INT_ID &int_id)
int bind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int trybind (const EXT_ID &ext_id, INT_ID &int_id)
int trybind (const EXT_ID &ext_id, INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id)
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int find (const EXT_ID &ext_id, INT_ID &int_id)
int find (const EXT_ID &ext_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int unbind (const EXT_ID &ext_id)
int unbind (const EXT_ID &ext_id, INT_ID &int_id)
int unbind (ACE_RB_Tree_Node< EXT_ID, INT_ID > *entry)
size_t current_size (void) const
 Returns the current number of nodes in the tree.

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

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

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

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

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

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

int test_invariant (void)
 Tests the red-black invariant(s) throughout the whole tree.

INT_ID * find (const EXT_ID &k)
INT_ID * insert (const EXT_ID &k, const INT_ID &t)
int remove (const EXT_ID &k)
void clear (void)

Protected Member Functions

 ACE_RB_Tree (void *location, ACE_Allocator *alloc)
 Reinitialize constructor.

int test_invariant_recurse (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x, int &expected_black_height, int measured_black_height)
 Recursive function to test the red-black invariant(s) at all nodes in a subtree.

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

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

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

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

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

void delete_children_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *parent)
int close_i (void)
int find_i (const EXT_ID &ext_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry, int find_exact=1)
INT_ID * insert_i (const EXT_ID &k, const INT_ID &t)
int insert_i (const EXT_ID &k, const INT_ID &t, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
int remove_i (const EXT_ID &k, INT_ID &i)
int remove_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *z)
void dump_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *node) const
 Recursive function to dump the state of an object.

void dump_node_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > &node) const
int lessthan (const EXT_ID &k1, const EXT_ID &k2)
 Less than comparison function for keys, using comparison functor.


Private Attributes

ACE_LOCK lock_
 Synchronization variable for the MT_SAFE ACE_RB_Tree.

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

COMPARE_KEYS compare_keys_
 Comparison functor for comparing nodes in the tree.

size_t current_size_
 The current number of nodes in the tree.


Friends

class ACE_RB_Tree_Iterator_Base< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >
class ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >
class ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >

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 185 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< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ENTRY
 

Definition at line 196 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< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::iterator
 

Definition at line 203 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< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ITERATOR
 

Definition at line 199 of file RB_Tree.h.

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

Definition at line 193 of file RB_Tree.h.

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

Definition at line 195 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< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::reverse_iterator
 

Definition at line 204 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< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::REVERSE_ITERATOR
 

Definition at line 200 of file RB_Tree.h.

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

Definition at line 194 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 48 of file RB_Tree.cpp.

References ACE_ERROR, ACE_TEXT, ACE_TRACE, LM_ERROR, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::open(). 

00049   : root_ (0),
00050     current_size_ (0)
00051 {
00052   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::"
00053              "ACE_RB_Tree (ACE_Allocator *alloc)");
00054   allocator_ = alloc;
00055   if (this->open (alloc) == -1)
00056     ACE_ERROR ((LM_ERROR,
00057                 ACE_TEXT ("ACE_RB_Tree::ACE_RB_Tree\n")));
00058 }

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

References ACE_TRACE, ACE_WRITE_GUARD, ACE_RB_Tree_Base::allocator_, ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::first(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::is_done(), ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::item(), ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::key(), and ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::next(). 

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

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

References ACE_TRACE, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close(). 

00100 {
00101   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::~ACE_RB_Tree");
00102 
00103   // Use the locked public method, to be totally safe, as the class
00104   // can be used with an allocator and placement new.
00105   this->close ();
00106 }

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 *  location,
ACE_Allocator *  alloc
)  [protected]
 

Reinitialize constructor.

This constructor is used to provide a valid vtable and allocator if the tree is reconstructed from shared memory. Constructor used by the derived class that has an allocator

Definition at line 83 of file RB_Tree.cpp. 

00087 {
00088   if (location != this)
00089     {
00090       this->root_ = 0;
00091       this->current_size_ = 0;
00092     }
00093 
00094   this->allocator_ = alloc;
00095 }

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 594 of file RB_Tree.inl.

References ACE_TRACE. 

00595 {
00596   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::begin");
00597 
00598   return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this);
00599 }

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 193 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(). 

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

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 is not changed. Returns 0 if a new entry is bound successfully, returns 1 if an attempt is made to bind an existing entry, and returns -1 if failures occur.

Definition at line 176 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(). 

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

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 707 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close_i(). 

00708 {
00709   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear");
00710   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
00711 
00712   this->close_i ();
00713 }

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 160 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close_i().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::~ACE_RB_Tree(). 

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

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

References ACE_DES_FREE_TEMPLATE2, ACE_TRACE, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::delete_children_i().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::clear(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::open(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::operator=(). 

00566 {
00567   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::close_i");
00568 
00569   this->delete_children_i (this->root_);
00570   ACE_DES_FREE_TEMPLATE2 (this->root_,
00571                           this->allocator()->free,
00572                           ACE_RB_Tree_Node,
00573                           EXT_ID, INT_ID);
00574   this->current_size_ = 0;
00575   this->root_ = 0;
00576   return 0;
00577 }

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 719 of file RB_Tree.inl.

References ACE_TRACE. 

00720 {
00721   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::current_size");
00722   return current_size_;
00723 }

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

Delete children (left and right) of the node. Must be called with lock held.

Definition at line 539 of file RB_Tree.cpp.

References ACE_DES_FREE_TEMPLATE2.

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close_i(). 

00540 {
00541   if (parent)
00542     {
00543       this->delete_children_i (parent->left ());
00544       this->delete_children_i (parent->right ());
00545       ACE_DES_FREE_TEMPLATE2
00546         (parent->left (),
00547          this->allocator_->free,
00548          ACE_RB_Tree_Node,
00549          EXT_ID, INT_ID);
00550       ACE_DES_FREE_TEMPLATE2
00551         (parent->right (),
00552          this->allocator_->free,
00553          ACE_RB_Tree_Node,
00554          EXT_ID, INT_ID);
00555       parent->left (0);
00556       parent->right (0);
00557     }
00558   return;
00559 }

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 575 of file RB_Tree.inl.

References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_TEXT, ACE_TRACE, ACE_Allocator::dump(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::dump_i(), and LM_DEBUG. 

00576 {
00577 #if defined (ACE_HAS_DUMP)
00578   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::dump");
00579   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
00580   ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ncurrent_size_ = %d\n"), this->current_size_));
00581   this->allocator_->dump ();
00582   this->lock_.dump ();
00583   ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nDumping nodes from root\n")));
00584   this->dump_i (this->root_);
00585   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
00586 #endif /* ACE_HAS_DUMP */
00587 }

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

References ACE_DEBUG, ACE_TEXT, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::dump_node_i(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), LM_DEBUG, and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::dump(). 

00863 {
00864 #if defined (ACE_HAS_DUMP)
00865   if (node)
00866     {
00867       dump_node_i (*node);
00868 
00869       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ndown left\n")));
00870       this->dump_i (node->left ());
00871       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nup left\n")));
00872 
00873       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ndown right\n")));
00874       this->dump_i (node->right ());
00875       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nup right\n")));
00876     }
00877   else
00878     {
00879       ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nNULL POINTER (BLACK)\n")));
00880     }
00881 #else /* !ACE_HAS_DUMP */
00882   ACE_UNUSED_ARG (node);
00883 #endif /* ACE_HAS_DUMP */
00884 }

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

References ACE_DEBUG, ACE_TEXT, ACE_RB_Tree_Node< EXT_ID, INT_ID >::color(), and LM_DEBUG.

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::dump_i(). 

00893 {
00894 #if defined (ACE_HAS_DUMP)
00895   const char * color_str = (node.color () == ACE_RB_Tree_Node_Base::RED)
00896                            ? "RED" : "BLACK";
00897 
00898   ACE_DEBUG ((LM_DEBUG,  ACE_TEXT (" color=[%s]\n"), color_str));
00899 #else /* !ACE_HAS_DUMP */
00900   ACE_UNUSED_ARG (node);
00901 #endif /* ACE_HAS_DUMP */
00902 }

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 606 of file RB_Tree.inl.

References ACE_TRACE. 

00607 {
00608   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::end");
00609 
00610   return ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ();
00611 }

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 643 of file RB_Tree.inl.

References ACE_READ_GUARD_RETURN, ACE_TRACE, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_i(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(). 

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

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 . If found, return 0, returns -1 if not found.

Definition at line 460 of file RB_Tree.inl.

References ACE_READ_GUARD_RETURN, ACE_TRACE, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_i(). 

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

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 438 of file RB_Tree.inl.

References ACE_READ_GUARD_RETURN, ACE_TRACE, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_i(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(). 

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

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

References ACE_TRACE, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_node().

Referenced by ACE_RB_Tree_Iterator_Base< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ACE_RB_Tree_Iterator_Base(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find(). 

00586 {
00587   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::find_i");
00588 
00589   // Try to find a match.
00590   RB_SearchResult result = LEFT;
00591   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00592 
00593   if (current)
00594     {
00595       // Found a match
00596       if (!find_exact || result == EXACT)
00597         entry = current;  // Assign the entry for any match.
00598       return (result == EXACT ? 0 : -1);
00599     }
00600   else
00601     // The node is not there.
00602     return -1;
00603 }

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

References ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::key(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::lessthan(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_i(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i(). 

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

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 674 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(). 

00675 {
00676   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert");
00677   ACE_WRITE_GUARD_RETURN (ACE_LOCK,
00678                           ace_mon,
00679                           this->lock_,
00680                           reinterpret_cast<INT_ID*> (0L));
00681 
00682   return this->insert_i (k, t);
00683 }

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

References ACE_ERROR_RETURN, ACE_NEW_MALLOC_RETURN, ACE_TEXT, ACE_TRACE, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_node(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), LM_ERROR, ACE_Allocator::malloc(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rebalance(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right(). 

00730 {
00731   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t, "
00732              "ACE_RB_Tree_Node<EXT_ID, INT_ID> *&entry)");
00733 
00734   // Find the closest matching node, if there is one.
00735   RB_SearchResult result = LEFT;
00736   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00737   if (current)
00738     {
00739       // If the keys match, just return a pointer to the node's item.
00740       if (result == EXACT)
00741         {
00742           entry = current;
00743           return 1;
00744         }
00745       // Otherwise if we're to the left of the insertion
00746       // point, insert into the right subtree.
00747       else if (result == LEFT)
00748         {
00749           if (current->right ())
00750             {
00751               // If there is already a right subtree, complain.
00752               ACE_ERROR_RETURN ((LM_ERROR,
00753                                  ACE_TEXT ("%p\n"),
00754                                  ACE_TEXT ("\nright subtree already present in ")
00755                                  ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00756                                 -1);
00757             }
00758           else
00759             {
00760               // The right subtree is empty: insert new node there.
00761               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00762               ACE_NEW_MALLOC_RETURN
00763                 (tmp,
00764                  (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
00765                    (this->allocator_->malloc (sizeof (*tmp)))),
00766                  (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00767                  -1);
00768               current->right (tmp);
00769 
00770               // If the node was successfully inserted, set its parent, rebalance
00771               // the tree, color the root black, and return a pointer to the
00772               // inserted item.
00773               entry = current->right ();
00774               current->right ()->parent (current);
00775               RB_rebalance (current->right ());
00776               this->root_->color (ACE_RB_Tree_Node_Base::BLACK);
00777               ++this->current_size_;
00778               return 0;
00779             }
00780         }
00781       // Otherwise, we're to the right of the insertion point, so
00782       // insert into the left subtree.
00783       else // (result == RIGHT)
00784         {
00785           if (current->left ())
00786             // If there is already a left subtree, complain.
00787             ACE_ERROR_RETURN ((LM_ERROR,
00788                                ACE_TEXT ("%p\n"),
00789                                ACE_TEXT ("\nleft subtree already present in ")
00790                                ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00791                               -1);
00792           else
00793             {
00794               // The left subtree is empty: insert new node there.
00795               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00796               ACE_NEW_MALLOC_RETURN
00797                 (tmp,
00798                  (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
00799                    (this->allocator_->malloc (sizeof (*tmp)))),
00800                  (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00801                  -1);
00802               current->left (tmp);
00803               // If the node was successfully inserted, set its
00804               // parent, rebalance the tree, color the root black, and
00805               // return a pointer to the inserted item.
00806               entry = current->left ();
00807               current->left ()->parent (current);
00808               RB_rebalance (current->left ());
00809               this->root_->color (ACE_RB_Tree_Node_Base::BLACK);
00810               ++this->current_size_;
00811               return 0;
00812             }
00813         }
00814     }
00815   else
00816     {
00817       // The tree is empty: insert at the root and color the root black.
00818       ACE_NEW_MALLOC_RETURN
00819         (this->root_,
00820          (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
00821            (this->allocator_->malloc (sizeof (ACE_RB_Tree_Node<EXT_ID, INT_ID>)))),
00822          (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00823          -1);
00824       this->root_->color (ACE_RB_Tree_Node_Base::BLACK);
00825       ++this->current_size_;
00826       entry = this->root_;
00827       return 0;
00828     }
00829 }

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

References ACE_ERROR_RETURN, ACE_NEW_MALLOC_RETURN, ACE_TEXT, ACE_TRACE, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_node(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), LM_ERROR, ACE_Allocator::malloc(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rebalance(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ACE_RB_Tree(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::bind(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::operator=(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::trybind(). 

00616 {
00617   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::insert_i (const EXT_ID &k, const INT_ID &t)");
00618 
00619   // Find the closest matching node, if there is one.
00620   RB_SearchResult result = LEFT;
00621   ACE_RB_Tree_Node<EXT_ID, INT_ID> *current = find_node (k, result);
00622   if (current)
00623     {
00624       // If the keys match, just return a pointer to the node's item.
00625       if (result == EXACT)
00626         return &current->item ();
00627 
00628       // Otherwise if we're to the left of the insertion point, insert
00629       // into the right subtree.
00630       else if (result == LEFT)
00631         {
00632           if (current->right ())
00633             {
00634               // If there is already a right subtree, complain.
00635               ACE_ERROR_RETURN ((LM_ERROR,
00636                                  ACE_TEXT ("%p\n"),
00637                                  ACE_TEXT ("\nright subtree already present in ")
00638                                  ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00639                                 0);
00640             }
00641           else
00642             {
00643               // The right subtree is empty: insert new node there.
00644               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00645 
00646               ACE_NEW_MALLOC_RETURN
00647                 (tmp,
00648                  (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
00649                    (this->allocator_->malloc (sizeof (*tmp)))),
00650                  (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00651                  0);
00652               current->right (tmp);
00653 
00654               // If the node was successfully inserted, set its
00655               // parent, rebalance the tree, color the root black, and
00656               // return a pointer to the inserted item.
00657               INT_ID *item = &(current->right ()->item ());
00658               current->right ()->parent (current);
00659               RB_rebalance (current->right ());
00660               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00661               ++current_size_;
00662               return item;
00663             }
00664         }
00665       // Otherwise, we're to the right of the insertion point, so
00666       // insert into the left subtree.
00667       else // (result == RIGHT)
00668         {
00669           if (current->left ())
00670             // If there is already a left subtree, complain.
00671             ACE_ERROR_RETURN ((LM_ERROR,
00672                                ACE_TEXT ("%p\n"),
00673                                ACE_TEXT ("\nleft subtree already present in ")
00674                                ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::insert_i\n")),
00675                               0);
00676           else
00677             {
00678               // The left subtree is empty: insert new node there.
00679               ACE_RB_Tree_Node<EXT_ID, INT_ID> *tmp = 0;
00680               ACE_NEW_MALLOC_RETURN
00681                 (tmp,
00682                  (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
00683                    (this->allocator_->malloc (sizeof (*tmp)))),
00684                  (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00685                  0);
00686               current->left (tmp);
00687 
00688               // If the node was successfully inserted, set its
00689               // parent, rebalance the tree, color the root black, and
00690               // return a pointer to the inserted item.
00691               INT_ID *item = &current->left ()->item ();
00692               current->left ()->parent (current);
00693               RB_rebalance (current->left ());
00694               root_->color (ACE_RB_Tree_Node_Base::BLACK);
00695               ++current_size_;
00696               return item;
00697             }
00698         }
00699     }
00700   else
00701     {
00702       // The tree is empty: insert at the root and color the root
00703       // black.
00704       ACE_NEW_MALLOC_RETURN
00705         (this->root_,
00706          (reinterpret_cast<ACE_RB_Tree_Node<EXT_ID, INT_ID>*>
00707            (this->allocator_->malloc (sizeof (ACE_RB_Tree_Node<EXT_ID, INT_ID>)))),
00708          (ACE_RB_Tree_Node<EXT_ID, INT_ID>) (k, t),
00709          0);
00710       this->root_->color (ACE_RB_Tree_Node_Base::BLACK);
00711       ++current_size_;
00712       return &this->root_->item ();
00713     }
00714 }

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

Less than comparison function for keys, using comparison functor.

Definition at line 138 of file RB_Tree.cpp.

References ACE_TRACE, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::compare_keys_.

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_node(). 

00139 {
00140   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::lessthan");
00141   return this->compare_keys_ (k1, k2);
00142 }

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 . 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 , but HP/C++ will choke on that!

Definition at line 564 of file RB_Tree.inl.

References ACE_TRACE. 

00565 {
00566   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::mutex");
00567   return this->lock_;
00568 }

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 135 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close_i(), and ACE_Allocator::instance().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::ACE_RB_Tree(). 

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

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

References ACE_TRACE, ACE_WRITE_GUARD, ACE_RB_Tree_Base::allocator_, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::close_i(), ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::first(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::is_done(), ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::item(), ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::key(), and ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::next(). 

00112 {
00113   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::operator =");
00114   ACE_WRITE_GUARD (ACE_LOCK, ace_mon, this->lock_);
00115 
00116   if (this != &rbt)
00117     {
00118       // Clear out the existing tree.
00119       close_i ();
00120 
00121       // Make a deep copy of the passed tree.
00122       ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iter(rbt);
00123 
00124       for (iter.first ();
00125            iter.is_done () == 0;
00126            iter.next ())
00127         insert_i (*(iter.key ()),
00128                   *(iter.item ()));
00129 
00130       // Use the same allocator as the rhs.
00131       allocator_ = rbt.allocator_;
00132     }
00133 }

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

References ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::color(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::parent(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rotate_left(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rotate_right(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i(). 

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

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

References ACE_ERROR, ACE_TEXT, ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::color(), LM_ERROR, ACE_RB_Tree_Node< EXT_ID, INT_ID >::parent(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rotate_left(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rotate_right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(). 

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

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

References ACE_ERROR, ACE_TEXT, ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), LM_ERROR, ACE_RB_Tree_Node< EXT_ID, INT_ID >::parent(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_delete_fixup(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rebalance(). 

00187 {
00188   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_left");
00189 
00190   if (! x)
00191     ACE_ERROR ((LM_ERROR,
00192                 ACE_TEXT ("%p\n"),
00193                 ACE_TEXT ("\nerror: x is a null pointer in ")
00194                 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
00195   else if (! (x->right()))
00196     ACE_ERROR ((LM_ERROR,
00197                 ACE_TEXT ("%p\n"),
00198                 ACE_TEXT ("\nerror: x->right () is a null pointer ")
00199                 ACE_TEXT ("in ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_left\n")));
00200   else
00201     {
00202       ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
00203       y = x->right ();
00204       x->right (y->left ());
00205       if (y->left ())
00206         y->left ()->parent (x);
00207       y->parent (x->parent ());
00208       if (x->parent ())
00209         {
00210           if (x == x->parent ()->left ())
00211             x->parent ()->left (y);
00212           else
00213             x->parent ()->right (y);
00214         }
00215       else
00216         root_ = y;
00217       y->left (x);
00218       x->parent (y);
00219     }
00220 }

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

References ACE_ERROR, ACE_TEXT, ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), LM_ERROR, ACE_RB_Tree_Node< EXT_ID, INT_ID >::parent(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_delete_fixup(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_rebalance(). 

00148 {
00149   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_rotate_right");
00150 
00151   if (!x)
00152     ACE_ERROR ((LM_ERROR,
00153                 ACE_TEXT ("%p\n"),
00154                 ACE_TEXT ("\nerror: x is a null pointer in ")
00155                 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
00156   else if (! (x->left()))
00157     ACE_ERROR ((LM_ERROR,
00158                 ACE_TEXT ("%p\n"),
00159                 ACE_TEXT ("\nerror: x->left () is a null pointer in ")
00160                 ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::RB_rotate_right\n")));
00161   else
00162     {
00163       ACE_RB_Tree_Node<EXT_ID, INT_ID> * y;
00164       y = x->left ();
00165       x->left (y->right ());
00166       if (y->right ())
00167         y->right ()->parent (x);
00168       y->parent (x->parent ());
00169       if (x->parent ())
00170         {
00171           if (x == x->parent ()->right ())
00172             x->parent ()->right (y);
00173           else
00174             x->parent ()->left (y);
00175         }
00176       else
00177         root_ = y;
00178       y->right (x);
00179       x->parent (y);
00180     }
00181 }

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

References ACE_TRACE, and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_predecessor(). 

00526 {
00527   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_maximum");
00528 
00529   while ((x) && (x->right ()))
00530     x = x->right ();
00531 
00532   return x;
00533 }

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

References ACE_TRACE, and ACE_RB_Tree_Node< EXT_ID, INT_ID >::left().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_successor(). 

00513 {
00514   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_minimum");
00515 
00516   while ((x) && (x->left ()))
00517     x = x->left ();
00518 
00519   return x;
00520 }

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

References ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::parent(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_maximum(). 

00490 {
00491   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_predecessor");
00492   if (x == 0)
00493     return 0;
00494 
00495   if (x->left ())
00496     return RB_tree_maximum (x->left ());
00497 
00498   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
00499 
00500   while ((y) && (x == y->left ()))
00501     {
00502       x = y;
00503       y = y->parent ();
00504     }
00505 
00506   return y;
00507 }

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

References ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::parent(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_minimum(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i(). 

00467 {
00468   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::RB_tree_successor");
00469 
00470   if (x == 0)
00471     return 0;
00472 
00473   if (x->right ())
00474     return RB_tree_minimum (x->right ());
00475 
00476   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y = x->parent ();
00477   while ((y) && (x == y->right ()))
00478     {
00479       x = y;
00480       y = y->parent ();
00481     }
00482 
00483   return y;
00484 }

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 618 of file RB_Tree.inl.

References ACE_TRACE. 

00619 {
00620   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rbegin");
00621 
00622   return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> (*this);
00623 }

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 408 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::key(). 

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

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 . 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 and you also need full control over memory allocation. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur.

Definition at line 378 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::key(). 

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

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 345 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::key(). 

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

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 . Otherwise, store the old value of int_id into the "out" parameter and rebind the new parameters. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur.

Definition at line 317 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::key(). 

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

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 289 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::key(). 

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

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 . Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur.

Definition at line 264 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::key(). 

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

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 693 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i(). 

00694 {
00695   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove");
00696   ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00697 
00698   INT_ID i;
00699   return this->remove_i (k, i);
00700 }

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

References ACE_DES_FREE_TEMPLATE2, ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::color(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::key(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::parent(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_delete_fixup(), ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::RB_tree_successor(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right(). 

00992 {
00993   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (ACE_RB_Tree_Node<EXT_ID, INT_ID> *z)");
00994 
00995   // Delete the node and reorganize the tree to satisfy the Red-Black
00996   // properties.
00997 
00998   ACE_RB_Tree_Node<EXT_ID, INT_ID> *x;
00999   ACE_RB_Tree_Node<EXT_ID, INT_ID> *y;
01000   ACE_RB_Tree_Node<EXT_ID, INT_ID> *parent;
01001 
01002   if (z->left () && z->right ())
01003     y = RB_tree_successor (z);
01004   else
01005     y = z;
01006 
01007   if (!y)
01008     return -1;
01009 
01010   if (y->left ())
01011     x = y->left ();
01012   else
01013     x = y->right ();
01014 
01015   parent = y->parent ();
01016   if (x)
01017     {
01018       x->parent (parent);
01019     }
01020 
01021   if (parent)
01022     {
01023       if (y == parent->left ())
01024         parent->left (x);
01025       else
01026         parent->right (x);
01027     }
01028   else
01029     this->root_ = x;
01030 
01031   if (y != z)
01032     {
01033       // Copy the elements of y into z.
01034       z->key () = y->key ();
01035       z->item () = y->item ();
01036     }
01037 
01038   // CLR pp. 263 says that nil nodes are implicitly colored BLACK
01039   if (!y || y->color () == ACE_RB_Tree_Node_Base::BLACK)
01040     RB_delete_fixup (x, parent);
01041 
01042   y->parent (0);
01043   y->right (0);
01044   y->left (0);
01045   ACE_DES_FREE_TEMPLATE2 (y,
01046                           this->allocator_->free,
01047                           ACE_RB_Tree_Node,
01048                           EXT_ID, INT_ID);
01049   --this->current_size_;
01050 
01051   return 0;
01052 }

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

References ACE_TRACE, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::find_node(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::item().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove(), and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::unbind(). 

00839 {
00840   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::remove_i (const EXT_ID &k, INT_ID &i)");
00841 
00842   // Find a matching node, if there is one.
00843   ACE_RB_Tree_Node<EXT_ID, INT_ID> *z;
00844   RB_SearchResult result = LEFT;
00845   z = find_node (k, result);
00846 
00847   // If there is a matching node: remove and destroy it.
00848   if (z && result == EXACT)
00849     {
00850       // Return the internal id stored in the deleted node.
00851       i = z->item ();
00852       return -1 == this->remove_i (z) ? -1 : 1;
00853     }
00854 
00855   // No matching node was found: return 0.
00856   return 0;
00857 }

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 630 of file RB_Tree.inl.

References ACE_TRACE. 

00631 {
00632   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::rend");
00633 
00634   return ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ();
00635 }

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

Tests the red-black invariant(s) throughout the whole tree.

Recursively tests the invariant red-black properties at each node of the tree. Returns 0 if invariant holds, else -1. This method is computationally expensive, and should only be called for testing purposes, and not in code that depends on the algorithmic complexity bounds provided by the other methods.

Definition at line 907 of file RB_Tree.cpp.

References ACE_DEBUG, ACE_READ_GUARD_RETURN, ACE_TEXT, ACE_TRACE, LM_DEBUG, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::test_invariant_recurse(). 

00908 {
00909   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant");
00910   ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1);
00911 
00912   // Recurse from the root, starting with the measured black height at
00913   // 0, and the expected black height at -1, which will cause the
00914   // count from first measured path to a leaf to be used as the
00915   // expected one from that point onward (the key is to check
00916   // consistency).
00917   int expected_black_height = -1;
00918   if (this->test_invariant_recurse (this->root_, expected_black_height, 0) == 0)
00919     {
00920       ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("invariant holds\n")));
00921       return 0;
00922     }
00923 
00924   return -1;
00925 }

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]
 

Recursive function to test the red-black invariant(s) at all nodes in a subtree.

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

Definition at line 930 of file RB_Tree.cpp.

References ACE_ERROR_RETURN, ACE_TEXT, ACE_TRACE, ACE_RB_Tree_Node< EXT_ID, INT_ID >::color(), ACE_RB_Tree_Node< EXT_ID, INT_ID >::left(), LM_ERROR, and ACE_RB_Tree_Node< EXT_ID, INT_ID >::right().

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::test_invariant(). 

00933 {
00934   ACE_TRACE ("ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::test_invariant_recurse");
00935 
00936   if (!x)
00937     {
00938       // Count each leaf (zero pointer) as a black node (per CLR algorithm description).
00939       ++measured_black_height;
00940 
00941       if (expected_black_height == -1)
00942         {
00943           expected_black_height = measured_black_height;
00944         }
00945       else if (expected_black_height != measured_black_height)
00946         {
00947           ACE_ERROR_RETURN ((LM_ERROR,
00948                              ACE_TEXT ("\nexpected_black_height = %d but ")
00949                              ACE_TEXT ("\nmeasured_black_height = %d in ")
00950                              ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n"),
00951                              expected_black_height, measured_black_height),
00952                             -1);
00953         }
00954 
00955       return 0;
00956     }
00957 
00958   // Check the invariant that a red node cannot have a red child.
00959   if (x->color () == ACE_RB_Tree_Node_Base::RED)
00960     {
00961       if (x->left () && x->left ()->color () == ACE_RB_Tree_Node_Base::RED)
00962         {
00963           ACE_ERROR_RETURN ((LM_ERROR,
00964                              ACE_TEXT ("%p\n"),
00965                              ACE_TEXT ("\nRED parent has RED left child in ")
00966                              ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
00967                             -1);
00968         }
00969 
00970       if (x->right () && x->right ()->color () == ACE_RB_Tree_Node_Base::RED)
00971         {
00972           ACE_ERROR_RETURN ((LM_ERROR,
00973                              ACE_TEXT ("%p\n"),
00974                              ACE_TEXT ("\nRED parent has RED right child in ")
00975                              ACE_TEXT ("ACE_RB_Tree<EXT_ID, INT_ID>::test_invariant_recurse\n")),
00976                             -1);
00977         }
00978     }
00979   else
00980     {
00981       // Count each black node traversed.
00982       ++measured_black_height;
00983     }
00984 
00985   return (test_invariant_recurse (x->left (), expected_black_height, measured_black_height) == 0)
00986           ? test_invariant_recurse (x->right (), expected_black_height, measured_black_height)
00987           : -1;
00988 }

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 237 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(). 

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

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 213 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i(), and ACE_RB_Tree_Node< EXT_ID, INT_ID >::item(). 

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

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

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i(). 

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

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 511 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i(). 

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

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_ids are *not* dynamically allocated...)

Definition at line 476 of file RB_Tree.inl.

References ACE_TRACE, ACE_WRITE_GUARD_RETURN, and ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::remove_i(). 

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

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 190 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 189 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 191 of file RB_Tree.h.

Member Data Documentation

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

Comparison functor for comparing nodes in the tree.

Definition at line 580 of file RB_Tree.h.

Referenced by ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::lessthan().

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

The current number of nodes in the tree.

Definition at line 583 of file RB_Tree.h.

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

Synchronization variable for the MT_SAFE ACE_RB_Tree.

Definition at line 574 of file RB_Tree.h.

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 >::root_ [private]
 

The root of the tree.

Definition at line 577 of file RB_Tree.h.

The documentation for this class was generated from the following files:
Generated on Sun Jan 27 12:56:34 2008 for ACE by doxygen 1.3.6