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 <ace/RB_Tree.h>

template<class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK> class ACE_RB_Tree : public ACE_RB_Tree_Base { public: friend class ACE_RB_Tree_Iterator_Base<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>; friend class ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>; friend class ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>; typedef EXT_ID KEY; typedef INT_ID VALUE; typedef ACE_RB_Tree_Node<EXT_ID, INT_ID> ENTRY; typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> ITERATOR; typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> REVERSE_ITERATOR; typedef ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> iterator; typedef ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> reverse_iterator; ACE_RB_Tree (ACE_Allocator *alloc = 0); ACE_RB_Tree ( const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &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<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; void operator= ( const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt ); virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2); ACE_LOCK &mutex (void); void dump (void) const; ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> begin ( void ); ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> end ( void ); ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rbegin ( void ); ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> 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<EXT_ID, INT_ID> * x); void RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x); void RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x); RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const; RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const; RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const; RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const; find_node (const EXT_ID &k, RB_SearchResult &result); void RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x); int close_i (void); int find_i ( const EXT_ID &ext_id, ACE_RB_Tree_Node<EXT_ID, INT_ID>* &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<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); private: ACE_Allocator *allocator_; ACE_LOCK lock_; ACE_RB_Tree_Node<EXT_ID, INT_ID> *root_; COMPARE_KEYS compare_keys_; size_t current_size_; };

ACE-style iterator typedefs.

    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;
    

STL-style iterator typedefs.

    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;
    

Initialization and termination methods.

ACE_RB_Tree (ACE_Allocator *alloc = 0);

ACE_RB_Tree (
    const ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> &rbt
    );

int open (ACE_Allocator *alloc = 0);

int close (void);

virtual ~ACE_RB_Tree (void);

insertion, removal, and search methods.

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

Public helper methods.

size_t current_size (void) const;

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

virtual int lessthan (const EXT_ID &k1, const EXT_ID &k2);

ACE_LOCK &mutex (void);

void dump (void) const;

STL styled iterator factory functions.

ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> begin (
    void
    );

ACE_RB_Tree_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> end (
    void
    );

ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rbegin (
    void
    );

ACE_RB_Tree_Reverse_Iterator<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK> rend (
    void
    );

DEPRECATED methods. Please migrate your code to use the new methods instead

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 methods. These should only be called with locks held.

void RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);

void RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);

void RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);

RB_tree_successor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;

RB_tree_predecessor (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;

RB_tree_minimum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;

RB_tree_maximum (ACE_RB_Tree_Node<EXT_ID, INT_ID> *x) const;

find_node (const EXT_ID &k, RB_SearchResult &result);

void RB_rebalance (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);

int close_i (void);

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

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<EXT_ID, INT_ID> *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<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.

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