ACE  6.4.2
Public Types | Public Member Functions | Public Attributes | Protected Member Functions | Private Attributes | Friends | List of all members
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]

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 Types inherited from ACE_RB_Tree_Base
enum  RB_SearchResult { LEFT, EXACT, RIGHT }
 Search result enumeration. More...
 

Public Member Functions

 ACE_RB_Tree (ACE_Allocator *alloc=0)
 Constructor. More...
 
 ACE_RB_Tree (const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > &rbt)
 Copy constructor. More...
 
int open (ACE_Allocator *alloc=0)
 Initialize an RB Tree. More...
 
int close (void)
 
virtual ~ACE_RB_Tree (void)
 Destructor. More...
 
int bind (const EXT_ID &item, const INT_ID &int_id)
 
int bind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
 
int trybind (const EXT_ID &ext_id, INT_ID &int_id)
 
int trybind (const EXT_ID &ext_id, INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
 
int rebind (const EXT_ID &ext_id, const INT_ID &int_id)
 
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
 
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id)
 
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
 
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id)
 
int rebind (const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
 
int find (const EXT_ID &ext_id, INT_ID &int_id)
 
int find (const EXT_ID &ext_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
 
int unbind (const EXT_ID &ext_id)
 
int unbind (const EXT_ID &ext_id, INT_ID &int_id)
 
int unbind (ACE_RB_Tree_Node< EXT_ID, INT_ID > *entry)
 
size_t current_size (void) const
 Returns the current number of nodes in the tree. More...
 
void operator= (const ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > &rbt)
 Assignment operator. More...
 
ACE_LOCK & mutex (void)
 
void dump (void) const
 Dump the state of an object. More...
 
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > begin (void)
 Return forward iterator positioned at first node in tree. More...
 
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > end (void)
 Return forward iterator positioned at last node in tree. More...
 
ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > rbegin (void)
 Return reverse iterator positioned at last node in tree. More...
 
ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > rend (void)
 Return reverse iterator positioned at first node in tree. More...
 
int test_invariant (void)
 Tests the red-black invariant(s) throughout the whole tree. More...
 
INT_ID * find (const EXT_ID &k)
 
INT_ID * insert (const EXT_ID &k, const INT_ID &t)
 
int remove (const EXT_ID &k)
 
void clear (void)
 
- Public Member Functions inherited from ACE_RB_Tree_Base
ACE_Allocatorallocator (void) const
 Get the allocator;. More...
 

Public Attributes

 ACE_ALLOC_HOOK_DECLARE
 Declare the dynamic allocation hooks. More...
 

Protected Member Functions

 ACE_RB_Tree (void *location, ACE_Allocator *alloc)
 Reinitialize constructor. More...
 
int test_invariant_recurse (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x, int &expected_black_height, int measured_black_height)
 Recursive function to test the red-black invariant(s) at all nodes in a subtree. More...
 
void RB_rotate_right (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x)
 Method for right rotation of the tree about a given node. More...
 
void RB_rotate_left (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x)
 Method for left rotation of the tree about a given node. More...
 
void RB_delete_fixup (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x, ACE_RB_Tree_Node< EXT_ID, INT_ID > *parent)
 Method for restoring Red-Black properties after deletion. More...
 
ACE_RB_Tree_Node< EXT_ID, INT_ID > * RB_tree_successor (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const
 Method to find the successor node of the given node in the tree. More...
 
ACE_RB_Tree_Node< EXT_ID, INT_ID > * RB_tree_predecessor (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const
 
ACE_RB_Tree_Node< EXT_ID, INT_ID > * RB_tree_minimum (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const
 
ACE_RB_Tree_Node< EXT_ID, INT_ID > * RB_tree_maximum (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x) const
 
ACE_RB_Tree_Node< EXT_ID, INT_ID > * find_node (const EXT_ID &k, ACE_RB_Tree_Base::RB_SearchResult &result)
 
void RB_rebalance (ACE_RB_Tree_Node< EXT_ID, INT_ID > *x)
 Rebalance the tree after insertion of a node. More...
 
void delete_children_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *parent)
 
int close_i (void)
 
int find_i (const EXT_ID &ext_id, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry, int find_exact=1)
 
INT_ID * insert_i (const EXT_ID &k, const INT_ID &t)
 
int insert_i (const EXT_ID &k, const INT_ID &t, ACE_RB_Tree_Node< EXT_ID, INT_ID > *&entry)
 
int remove_i (const EXT_ID &k, INT_ID &i)
 
int remove_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *z)
 
void dump_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > *node) const
 Recursive function to dump the state of an object. More...
 
void dump_node_i (ACE_RB_Tree_Node< EXT_ID, INT_ID > &node) const
 
int lessthan (const EXT_ID &k1, const EXT_ID &k2)
 Less than comparison function for keys, using comparison functor. More...
 

Private Attributes

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 >
 

Additional Inherited Members

- Protected Attributes inherited from ACE_RB_Tree_Base
ACE_Allocatorallocator_
 Pointer to a memory allocator. More...
 

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

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

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.

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.

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.

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

Member Function Documentation

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
ACE_RB_Tree_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::begin ( void  )
inline

Return forward iterator positioned at first node in tree.

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 >::bind ( const EXT_ID &  item,
const INT_ID &  int_id 
)
inline

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.

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 >::bind ( const EXT_ID &  ext_id,
const INT_ID &  int_id,
ACE_RB_Tree_Node< EXT_ID, INT_ID > *&  entry 
)
inline

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.

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 >::clear ( void  )
inline
Deprecated:
Destroys all nodes and sets the root pointer null.
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 ( void  )
inline

Close down an RB_Tree and release dynamically allocated resources.

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.

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 ( void  ) const
inline

Returns the current number of nodes in the tree.

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.

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 ( void  ) const
inline

Dump the state of an object.

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.

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.

Function to dump node itself. Does not show parameterized node contents in its basic form, but template specialization can be used to provide definitions for various EXT_ID and INT_ID types.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
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  )
inline

Return forward iterator positioned at last node in tree.

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 ( const EXT_ID &  ext_id,
INT_ID &  int_id 
)
inline

Locate ext_id and pass out parameter via int_id. If found, return 0, returns -1 if not found.

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 ( const EXT_ID &  ext_id,
ACE_RB_Tree_Node< EXT_ID, INT_ID > *&  entry 
)
inline

Locate ext_id and pass out parameter via entry. If found, return 0, returns -1 if not found.

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 >::find ( const EXT_ID &  k)
inline

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

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.

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 ( const EXT_ID &  k,
const INT_ID &  t 
)
inline

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:
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.
template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::insert_i ( const EXT_ID &  k,
const INT_ID &  t,
ACE_RB_Tree_Node< EXT_ID, INT_ID > *&  entry 
)
protected

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

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::lessthan ( const EXT_ID &  k1,
const EXT_ID &  k2 
)
protected

Less than comparison function for keys, using comparison functor.

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 >::mutex ( void  )
inline

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!
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 >::open ( ACE_Allocator alloc = 0)
inline

Initialize an RB Tree.

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.

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.

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.

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.

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.

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.

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.

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.

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.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rbegin ( void  )
inline

Return reverse iterator positioned at last node in tree.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind ( const EXT_ID &  ext_id,
const INT_ID &  int_id 
)
inline

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.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind ( const EXT_ID &  ext_id,
const INT_ID &  int_id,
ACE_RB_Tree_Node< EXT_ID, INT_ID > *&  entry 
)
inline

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.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind ( const EXT_ID &  ext_id,
const INT_ID &  int_id,
INT_ID &  old_int_id 
)
inline

Associate ext_id with int_id. If ext_id is not in the tree then behaves just like <bind>. Otherwise, store the old value of int_id into the "out" parameter and rebind the new parameters. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind ( const EXT_ID &  ext_id,
const INT_ID &  int_id,
INT_ID &  old_int_id,
ACE_RB_Tree_Node< EXT_ID, INT_ID > *&  entry 
)
inline

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.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rebind ( const EXT_ID &  ext_id,
const INT_ID &  int_id,
EXT_ID &  old_ext_id,
INT_ID &  old_int_id 
)
inline

Associate ext_id with int_id. If ext_id is not in the tree then behaves just like <bind>. Otherwise, store the old values of ext_id and int_id into the "out" parameters and rebind the new parameters. This is very useful if you need to have an atomic way of updating <ACE_RB_Tree_Nodes> and you also need full control over memory allocation. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
int ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::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 
)
inline

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.

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 ( const EXT_ID &  k)
inline

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

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.

template<class EXT_ID , class INT_ID , class COMPARE_KEYS , class ACE_LOCK >
ACE_RB_Tree_Reverse_Iterator< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK > ACE_RB_Tree< EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK >::rend ( void  )
inline

Return reverse iterator positioned at first node in tree.

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.

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.

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 >::trybind ( const EXT_ID &  ext_id,
INT_ID &  int_id 
)
inline

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.

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 >::trybind ( const EXT_ID &  ext_id,
INT_ID &  int_id,
ACE_RB_Tree_Node< EXT_ID, INT_ID > *&  entry 
)
inline

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.

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 >::unbind ( const EXT_ID &  ext_id)
inline

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

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 >::unbind ( const EXT_ID &  ext_id,
INT_ID &  int_id 
)
inline

Break any association of ext_id. Returns the value of int_id in case the caller needs to deallocate memory.

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 >::unbind ( ACE_RB_Tree_Node< EXT_ID, INT_ID > *  entry)
inline

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.

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

Member Data 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_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

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.

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.

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.

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.


The documentation for this class was generated from the following files: