diff options
author | Benny Prijono <bennylp@teluu.com> | 2005-11-01 16:42:51 +0000 |
---|---|---|
committer | Benny Prijono <bennylp@teluu.com> | 2005-11-01 16:42:51 +0000 |
commit | 81ecc233996dcddfbef707bd9a5099f5d9e5eb13 (patch) | |
tree | c735c382ff2dac0179b96505c4192ee70185372d /pjlib/include/pj/rbtree.h | |
parent | b5a1af6f999820564ead4867b1e5d5574778ee56 (diff) |
Added suppor /and fix things for SunOS port
git-svn-id: http://svn.pjsip.org/repos/pjproject/main@2 74dad513-b988-da41-8d7b-12977e46ad98
Diffstat (limited to 'pjlib/include/pj/rbtree.h')
-rw-r--r-- | pjlib/include/pj/rbtree.h | 386 |
1 files changed, 193 insertions, 193 deletions
diff --git a/pjlib/include/pj/rbtree.h b/pjlib/include/pj/rbtree.h index f94e3658..b0997680 100644 --- a/pjlib/include/pj/rbtree.h +++ b/pjlib/include/pj/rbtree.h @@ -1,193 +1,193 @@ -/* $Header: /pjproject-0.3/pjlib/include/pj/rbtree.h 5 10/14/05 12:26a Bennylp $ */
-
-#ifndef __PJ_RBTREE_H__
-#define __PJ_RBTREE_H__
-
-/**
- * @file rbtree.h
- * @brief Red/Black Tree
- */
-
-#include <pj/types.h>
-
-PJ_BEGIN_DECL
-
-/**
- * @defgroup PJ_RBTREE Red/Black Balanced Tree
- * @ingroup PJ_DS
- * @brief
- * Red/Black tree is the variant of balanced tree, where the search, insert,
- * and delete operation is \b guaranteed to take at most \a O( lg(n) ).
- * @{
- */
-/**
- * Color type for Red-Black tree.
- */
-typedef enum pj_rbcolor_t
-{
- PJ_RBCOLOR_BLACK,
- PJ_RBCOLOR_RED
-} pj_rbcolor_t;
-
-/**
- * The type of the node of the R/B Tree.
- */
-typedef struct pj_rbtree_node
-{
- /** Pointers to the node's parent, and left and right siblings. */
- struct pj_rbtree_node *parent, *left, *right;
-
- /** Key associated with the node. */
- const void *key;
-
- /** User data associated with the node. */
- void *user_data;
-
- /** The R/B Tree node color. */
- pj_rbcolor_t color;
-
-} pj_rbtree_node;
-
-
-/**
- * The type of function use to compare key value of tree node.
- * @return
- * 0 if the keys are equal
- * <0 if key1 is lower than key2
- * >0 if key1 is greater than key2.
- */
-typedef int pj_rbtree_comp(const void *key1, const void *key2);
-
-
-/**
- * Declaration of a red-black tree. All elements in the tree must have UNIQUE
- * key.
- * A red black tree always maintains the balance of the tree, so that the
- * tree height will not be greater than lg(N). Insert, search, and delete
- * operation will take lg(N) on the worst case. But for insert and delete,
- * there is additional time needed to maintain the balance of the tree.
- */
-typedef struct pj_rbtree
-{
- pj_rbtree_node null_node; /**< Constant to indicate NULL node. */
- pj_rbtree_node *null; /**< Constant to indicate NULL node. */
- pj_rbtree_node *root; /**< Root tree node. */
- unsigned size; /**< Number of elements in the tree. */
- pj_rbtree_comp *comp; /**< Key comparison function. */
-} pj_rbtree;
-
-
-/**
- * Guidance on how much memory required for each of the node.
- */
-#define PJ_RBTREE_NODE_SIZE (sizeof(pj_rbtree_node))
-
-
-/**
- * Guidance on memory required for the tree.
- */
-#define PJ_RBTREE_SIZE (sizeof(pj_rbtree))
-
-
-/**
- * Initialize the tree.
- * @param tree the tree to be initialized.
- * @param comp key comparison function to be used for this tree.
- */
-PJ_DECL(void) pj_rbtree_init( pj_rbtree *tree, pj_rbtree_comp *comp);
-
-/**
- * Get the first element in the tree.
- * The first element always has the least value for the key, according to
- * the comparison function.
- * @param tree the tree.
- * @return the tree node, or NULL if the tree has no element.
- */
-PJ_DECL(pj_rbtree_node*) pj_rbtree_first( pj_rbtree *tree );
-
-/**
- * Get the last element in the tree.
- * The last element always has the greatest key value, according to the
- * comparison function defined for the tree.
- * @param tree the tree.
- * @return the tree node, or NULL if the tree has no element.
- */
-PJ_DECL(pj_rbtree_node*) pj_rbtree_last( pj_rbtree *tree );
-
-/**
- * Get the successive element for the specified node.
- * The successive element is an element with greater key value.
- * @param tree the tree.
- * @param node the node.
- * @return the successive node, or NULL if the node has no successor.
- */
-PJ_DECL(pj_rbtree_node*) pj_rbtree_next( pj_rbtree *tree,
- pj_rbtree_node *node );
-
-/**
- * The the previous node for the specified node.
- * The previous node is an element with less key value.
- * @param tree the tree.
- * @param node the node.
- * @return the previous node, or NULL if the node has no previous node.
- */
-PJ_DECL(pj_rbtree_node*) pj_rbtree_prev( pj_rbtree *tree,
- pj_rbtree_node *node );
-
-/**
- * Insert a new node.
- * The node will be inserted at sorted location. The key of the node must
- * be UNIQUE, i.e. it hasn't existed in the tree.
- * @param tree the tree.
- * @param node the node to be inserted.
- * @return zero on success, or -1 if the key already exist.
- */
-PJ_DECL(int) pj_rbtree_insert( pj_rbtree *tree,
- pj_rbtree_node *node );
-
-/**
- * Find a node which has the specified key.
- * @param tree the tree.
- * @param key the key to search.
- * @return the tree node with the specified key, or NULL if the key can not
- * be found.
- */
-PJ_DECL(pj_rbtree_node*) pj_rbtree_find( pj_rbtree *tree,
- const void *key );
-
-/**
- * Erase a node from the tree.
- * @param tree the tree.
- * @param node the node to be erased.
- * @return the tree node itself.
- */
-PJ_DECL(pj_rbtree_node*) pj_rbtree_erase( pj_rbtree *tree,
- pj_rbtree_node *node );
-
-/**
- * Get the maximum tree height from the specified node.
- * @param tree the tree.
- * @param node the node, or NULL to get the root of the tree.
- * @return the maximum height, which should be at most lg(N)
- */
-PJ_DECL(unsigned) pj_rbtree_max_height( pj_rbtree *tree,
- pj_rbtree_node *node );
-
-/**
- * Get the minumum tree height from the specified node.
- * @param tree the tree.
- * @param node the node, or NULL to get the root of the tree.
- * @return the height
- */
-PJ_DECL(unsigned) pj_rbtree_min_height( pj_rbtree *tree,
- pj_rbtree_node *node );
-
-
-/**
- * @}
- */
-
-PJ_END_DECL
-
-#endif /* __PJ_RBTREE_H__ */
-
+/* $Header: /pjproject-0.3/pjlib/include/pj/rbtree.h 5 10/14/05 12:26a Bennylp $ */ + +#ifndef __PJ_RBTREE_H__ +#define __PJ_RBTREE_H__ + +/** + * @file rbtree.h + * @brief Red/Black Tree + */ + +#include <pj/types.h> + +PJ_BEGIN_DECL + +/** + * @defgroup PJ_RBTREE Red/Black Balanced Tree + * @ingroup PJ_DS + * @brief + * Red/Black tree is the variant of balanced tree, where the search, insert, + * and delete operation is \b guaranteed to take at most \a O( lg(n) ). + * @{ + */ +/** + * Color type for Red-Black tree. + */ +typedef enum pj_rbcolor_t +{ + PJ_RBCOLOR_BLACK, + PJ_RBCOLOR_RED +} pj_rbcolor_t; + +/** + * The type of the node of the R/B Tree. + */ +typedef struct pj_rbtree_node +{ + /** Pointers to the node's parent, and left and right siblings. */ + struct pj_rbtree_node *parent, *left, *right; + + /** Key associated with the node. */ + const void *key; + + /** User data associated with the node. */ + void *user_data; + + /** The R/B Tree node color. */ + pj_rbcolor_t color; + +} pj_rbtree_node; + + +/** + * The type of function use to compare key value of tree node. + * @return + * 0 if the keys are equal + * <0 if key1 is lower than key2 + * >0 if key1 is greater than key2. + */ +typedef int pj_rbtree_comp(const void *key1, const void *key2); + + +/** + * Declaration of a red-black tree. All elements in the tree must have UNIQUE + * key. + * A red black tree always maintains the balance of the tree, so that the + * tree height will not be greater than lg(N). Insert, search, and delete + * operation will take lg(N) on the worst case. But for insert and delete, + * there is additional time needed to maintain the balance of the tree. + */ +typedef struct pj_rbtree +{ + pj_rbtree_node null_node; /**< Constant to indicate NULL node. */ + pj_rbtree_node *null; /**< Constant to indicate NULL node. */ + pj_rbtree_node *root; /**< Root tree node. */ + unsigned size; /**< Number of elements in the tree. */ + pj_rbtree_comp *comp; /**< Key comparison function. */ +} pj_rbtree; + + +/** + * Guidance on how much memory required for each of the node. + */ +#define PJ_RBTREE_NODE_SIZE (sizeof(pj_rbtree_node)) + + +/** + * Guidance on memory required for the tree. + */ +#define PJ_RBTREE_SIZE (sizeof(pj_rbtree)) + + +/** + * Initialize the tree. + * @param tree the tree to be initialized. + * @param comp key comparison function to be used for this tree. + */ +PJ_DECL(void) pj_rbtree_init( pj_rbtree *tree, pj_rbtree_comp *comp); + +/** + * Get the first element in the tree. + * The first element always has the least value for the key, according to + * the comparison function. + * @param tree the tree. + * @return the tree node, or NULL if the tree has no element. + */ +PJ_DECL(pj_rbtree_node*) pj_rbtree_first( pj_rbtree *tree ); + +/** + * Get the last element in the tree. + * The last element always has the greatest key value, according to the + * comparison function defined for the tree. + * @param tree the tree. + * @return the tree node, or NULL if the tree has no element. + */ +PJ_DECL(pj_rbtree_node*) pj_rbtree_last( pj_rbtree *tree ); + +/** + * Get the successive element for the specified node. + * The successive element is an element with greater key value. + * @param tree the tree. + * @param node the node. + * @return the successive node, or NULL if the node has no successor. + */ +PJ_DECL(pj_rbtree_node*) pj_rbtree_next( pj_rbtree *tree, + pj_rbtree_node *node ); + +/** + * The the previous node for the specified node. + * The previous node is an element with less key value. + * @param tree the tree. + * @param node the node. + * @return the previous node, or NULL if the node has no previous node. + */ +PJ_DECL(pj_rbtree_node*) pj_rbtree_prev( pj_rbtree *tree, + pj_rbtree_node *node ); + +/** + * Insert a new node. + * The node will be inserted at sorted location. The key of the node must + * be UNIQUE, i.e. it hasn't existed in the tree. + * @param tree the tree. + * @param node the node to be inserted. + * @return zero on success, or -1 if the key already exist. + */ +PJ_DECL(int) pj_rbtree_insert( pj_rbtree *tree, + pj_rbtree_node *node ); + +/** + * Find a node which has the specified key. + * @param tree the tree. + * @param key the key to search. + * @return the tree node with the specified key, or NULL if the key can not + * be found. + */ +PJ_DECL(pj_rbtree_node*) pj_rbtree_find( pj_rbtree *tree, + const void *key ); + +/** + * Erase a node from the tree. + * @param tree the tree. + * @param node the node to be erased. + * @return the tree node itself. + */ +PJ_DECL(pj_rbtree_node*) pj_rbtree_erase( pj_rbtree *tree, + pj_rbtree_node *node ); + +/** + * Get the maximum tree height from the specified node. + * @param tree the tree. + * @param node the node, or NULL to get the root of the tree. + * @return the maximum height, which should be at most lg(N) + */ +PJ_DECL(unsigned) pj_rbtree_max_height( pj_rbtree *tree, + pj_rbtree_node *node ); + +/** + * Get the minumum tree height from the specified node. + * @param tree the tree. + * @param node the node, or NULL to get the root of the tree. + * @return the height + */ +PJ_DECL(unsigned) pj_rbtree_min_height( pj_rbtree *tree, + pj_rbtree_node *node ); + + +/** + * @} + */ + +PJ_END_DECL + +#endif /* __PJ_RBTREE_H__ */ + |