Set svn:eol-style for all files

git-svn-id: http://svn.pjsip.org/repos/pjproject/trunk@66 74dad513-b988-da41-8d7b-12977e46ad98

1 files changed, 209 insertions, 209 deletions

diff --git a/pjlib/include/pj/rbtree.h b/pjlib/include/pj/rbtree.h
index 1d4df0be..ed6607fd 100644
--- a/pjlib/include/pj/rbtree.h
+++ b/pjlib/include/pj/rbtree.h
@@ -1,209 +1,209 @@
-/* $Id$ */

-/* 

- * Copyright (C)2003-2006 Benny Prijono <benny@prijono.org>

- *

- * This program is free software; you can redistribute it and/or modify

- * it under the terms of the GNU General Public License as published by

- * the Free Software Foundation; either version 2 of the License, or

- * (at your option) any later version.

- *

- * This program is distributed in the hope that it will be useful,

- * but WITHOUT ANY WARRANTY; without even the implied warranty of

- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

- * GNU General Public License for more details.

- *

- * You should have received a copy of the GNU General Public License

- * along with this program; if not, write to the Free Software

- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 

- */

-#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__ */

-

+/* $Id$ */
+/* 
+ * Copyright (C)2003-2006 Benny Prijono <benny@prijono.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
+ */
+#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__ */
+