--- name: "ACE_RB_Tree" section: "3" platform: "linux" package: "libace-doc" version: "5.0.7-4" release: "Debian 2.2 (Potato)" platforms: ["linux"] url: "https://new.carta.tech/ACE_RB_Tree" --- # ACE\_RB\_Tree(3) 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. ## NAME ACE\_RB\_Tree - 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. ## SYNOPSIS ``` #include template class ACE_RB_Tree : public ACE_RB_Tree_Base { public: friend class ACE_RB_Tree_Iterator_Base; friend class ACE_RB_Tree_Iterator; friend class ACE_RB_Tree_Reverse_Iterator; typedef EXT_ID KEY; typedef INT_ID VALUE; typedef ACE_RB_Tree_Node ENTRY; typedef ACE_RB_Tree_Iterator ITERATOR; typedef ACE_RB_Tree_Reverse_Iterator REVERSE_ITERATOR; typedef ACE_RB_Tree_Iterator iterator; typedef ACE_RB_Tree_Reverse_Iterator reverse_iterator; ACE_RB_Tree (ACE_Allocator *alloc = 0); ACE_RB_Tree ( const ACE_RB_Tree &rbt ); int open (ACE_Allocator *alloc = 0); int close (void); virtual ~ACE_RB_Tree (void); 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 *&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 *&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 *&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 *&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 *&entry ); int find (const EXT_ID &ext_id, INT_ID &int_id); int find ( const EXT_ID &ext_id, ACE_RB_Tree_Node *&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 *entry); size_t current_size (void); void operator= ( const ACE_RB_Tree &rbt ); virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2); ACE_LOCK &mutex (void); void dump (void) const; ACE_RB_Tree_Iterator begin ( void ); ACE_RB_Tree_Iterator end ( void ); ACE_RB_Tree_Reverse_Iterator rbegin ( void ); ACE_RB_Tree_Reverse_Iterator rend ( void ); 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: void RB_rotate_right (ACE_RB_Tree_Node * x); void RB_rotate_left (ACE_RB_Tree_Node * x); void RB_delete_fixup (ACE_RB_Tree_Node * x); RB_tree_successor (ACE_RB_Tree_Node *x) const; RB_tree_predecessor (ACE_RB_Tree_Node *x) const; RB_tree_minimum (ACE_RB_Tree_Node *x) const; RB_tree_maximum (ACE_RB_Tree_Node *x) const; find_node (const EXT_ID &k, RB_SearchResult &result); void RB_rebalance (ACE_RB_Tree_Node * x); int close_i (void); int find_i ( const EXT_ID &ext_id, ACE_RB_Tree_Node* &entry ); 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 *&entry ); int remove_i (const EXT_ID &k, INT_ID &i); int remove_i (ACE_RB_Tree_Node *z); private: ACE_Allocator *allocator_; ACE_LOCK lock_; ACE_RB_Tree_Node *root_; COMPARE_KEYS compare_keys_; size_t current_size_; }; ``` ## ACE-style iterator typedefs. ``` typedef ACE_RB_Tree_Iterator ITERATOR; ``` ``` typedef ACE_RB_Tree_Reverse_Iterator REVERSE_ITERATOR; ``` ## STL-style iterator typedefs. ``` typedef ACE_RB_Tree_Iterator iterator; ``` ``` typedef ACE_RB_Tree_Reverse_Iterator reverse_iterator; ``` ## Initialization and termination methods. ``` ACE_RB_Tree (ACE_Allocator *alloc = 0); ``` Constructor. ``` ACE_RB_Tree ( const ACE_RB_Tree &rbt ); ``` Copy constructor. ``` int open (ACE_Allocator *alloc = 0); ``` Initialize an RB Tree. ``` int close (void); ``` Close down an RB\_Tree and release dynamically allocated resources. ``` virtual ~ACE_RB_Tree (void); ``` Destructor. ## insertion, removal, and search methods. ``` int bind (const EXT_ID &item, const INT_ID &int_id); ``` Associate ext\_id with int\_id. If ext\_id is already in the tree then the ACE\_RB\_Tree\_Node is not changed. Returns 0 if a new entry is bound successfully, returns 1 if an attempt is made to bind an existing entry, and returns -1 if failures occur. ``` int bind ( const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node *&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. ``` int 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. ``` int trybind ( const EXT_ID &ext_id, INT_ID &int_id, ACE_RB_Tree_Node *&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. ``` int rebind (const EXT_ID &ext_id, const INT_ID &int_id); ``` Reassociate ext\_id with int\_id. If ext\_id is not in the tree then behaves just like bind. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur. ``` int rebind ( const EXT_ID &ext_id, const INT_ID &int_id, ACE_RB_Tree_Node *&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. ``` int rebind ( const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id ); ``` Associate ext\_id with int\_id. If ext\_id is not in the tree then behaves just like bind. Otherwise, store the old value of int\_id into the "out" parameter and rebind the new parameters. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur. ``` int rebind ( const EXT_ID &ext_id, const INT_ID &int_id, INT_ID &old_int_id, ACE_RB_Tree_Node *&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. ``` int rebind ( const EXT_ID &ext_id, const INT_ID &int_id, EXT_ID &old_ext_id, INT_ID &old_int_id ); ``` Associate ext\_id with int\_id. If ext\_id is not in the tree then behaves just like bind. Otherwise, store the old values of ext\_id and int\_id into the "out" parameters and rebind the new parameters. This is very useful if you need to have an atomic way of updating ACE\_RB\_Tree\_Nodes and you also need full control over memory allocation. Returns 0 if a new entry is bound successfully, returns 1 if an existing entry was rebound, and returns -1 if failures occur. ``` 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 *&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. ``` int find (const EXT_ID &ext_id, INT_ID &int_id); ``` Locate ext\_id and pass out parameter via int\_id. If found, return 0, returns -1 if not found. ``` int find ( const EXT_ID &ext_id, ACE_RB_Tree_Node *&entry ); ``` Locate ext\_id and pass out parameter via entry. If found, return 0, returns -1 if not found. ``` int 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...) ``` int unbind (const EXT_ID &ext_id, INT_ID &int_id); ``` Break any association of ext\_id. Returns the value of int\_id in case the caller needs to deallocate memory. ``` int unbind (ACE_RB_Tree_Node *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. ## Public helper methods. ``` size_t current_size (void); ``` Returns the current number of nodes in the tree. ``` void operator= ( const ACE_RB_Tree &rbt ); ``` Assignment operator. ``` virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2); ``` Less than comparison function for keys, using comparison functor. ``` ACE_LOCK &mutex (void); ``` Returns a reference to the underlying ACE\_LOCK. This makes it possible to acquire the lock explicitly, which can be useful in some cases if you instantiate the ACE\_Atomic\_Op with an ACE\_Recursive\_Mutex or ACE\_Process\_Mutex, or if you need to guard the state of an iterator. NOTE: the right name would be lock, but HP/C++ will choke on that! ``` void dump (void) const; ``` Dump the state of an object. ## STL styled iterator factory functions. ``` ACE_RB_Tree_Iterator begin ( void ); ``` Return forward iterator positioned at first node in tree. ``` ACE_RB_Tree_Iterator end ( void ); ``` Return forward iterator positioned at last node in tree. ``` ACE_RB_Tree_Reverse_Iterator rbegin ( void ); ``` Return reverse iterator positioned at last node in tree. ``` ACE_RB_Tree_Reverse_Iterator rend ( void ); ``` Return reverse iterator positioned at first node in tree. ## DEPRECATED methods. Please migrate your code to use the new methods instead ``` INT_ID* 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. ``` INT_ID* 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 ``` int 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 ``` void clear (void); ``` Destroys all nodes and sets the root pointer null. DEPRECATED ## Protected methods. These should only be called with locks held. ``` void RB_rotate_right (ACE_RB_Tree_Node * x); ``` Method for right rotation of the tree about a given node. ``` void RB_rotate_left (ACE_RB_Tree_Node * x); ``` Method for left rotation of the tree about a given node. ``` void RB_delete_fixup (ACE_RB_Tree_Node * x); ``` Method for restoring Red-Black properties after deletion. ``` RB_tree_successor (ACE_RB_Tree_Node *x) const; ``` Method to find the successor node of the given node in the tree. ``` RB_tree_predecessor (ACE_RB_Tree_Node *x) const; ``` Method to find the predecessor node of the given node in the tree. ``` RB_tree_minimum (ACE_RB_Tree_Node *x) const; ``` Method to find the minimum node of the subtree rooted at the given node. ``` RB_tree_maximum (ACE_RB_Tree_Node *x) const; ``` Method to find the maximum node of the subtree rooted at the given node. ``` find_node (const EXT_ID &k, RB_SearchResult &result); ``` 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. ``` void RB_rebalance (ACE_RB_Tree_Node * x); ``` Rebalance the tree after insertion of a node. ``` int close_i (void); ``` Close down an RB\_Tree. this method should only be called with locks already held. ``` int find_i ( const EXT_ID &ext_id, ACE_RB_Tree_Node* &entry ); ``` Retrieves a pointer to the item corresponding to the given key. Returns 0 for success, or -1 if it cannot find the key in the tree. ``` INT_ID* insert_i (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. ``` int insert_i ( const EXT_ID &k, const INT_ID &t, ACE_RB_Tree_Node *&entry ); ``` 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. ``` int remove_i (const EXT_ID &k, INT_ID &i); ``` 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. ``` int remove_i (ACE_RB_Tree_Node *z); ``` Removes the item associated with the given key from the tree and destroys it. ## Private members. ``` ACE_Allocator *allocator_; ``` Pointer to a memory allocator. ``` ACE_LOCK lock_; ``` Synchronization variable for the MT\_SAFE ACE\_RB\_Tree. ``` ACE_RB_Tree_Node *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. ## AUTHOR Chris Gill ## Description 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. ## LIBRARY ace