diff options
author | Benny Prijono <bennylp@teluu.com> | 2005-11-13 19:40:44 +0000 |
---|---|---|
committer | Benny Prijono <bennylp@teluu.com> | 2005-11-13 19:40:44 +0000 |
commit | a08b589d09d5197f9a76d549a189e4686bd2ca8c (patch) | |
tree | 549904e7680dfab96b3ce579b1843c5d58107100 /pjlib/src/pj/rbtree.c | |
parent | 8df70c6d5fef443506618bf31b686d53fef3f259 (diff) |
Applying license to pjproject
git-svn-id: http://svn.pjsip.org/repos/pjproject/trunk@49 74dad513-b988-da41-8d7b-12977e46ad98
Diffstat (limited to 'pjlib/src/pj/rbtree.c')
-rw-r--r-- | pjlib/src/pj/rbtree.c | 843 |
1 files changed, 432 insertions, 411 deletions
diff --git a/pjlib/src/pj/rbtree.c b/pjlib/src/pj/rbtree.c index a0babe0f..2f548c25 100644 --- a/pjlib/src/pj/rbtree.c +++ b/pjlib/src/pj/rbtree.c @@ -1,411 +1,432 @@ -/* $Id$ - */ -#include <pj/rbtree.h> -#include <pj/os.h> - -static void left_rotate( pj_rbtree *tree, pj_rbtree_node *node ) -{ - pj_rbtree_node *rnode, *parent; - - PJ_CHECK_STACK(); - - rnode = node->right; - if (rnode == tree->null) - return; - - node->right = rnode->left; - if (rnode->left != tree->null) - rnode->left->parent = node; - parent = node->parent; - rnode->parent = parent; - if (parent != tree->null) { - if (parent->left == node) - parent->left = rnode; - else - parent->right = rnode; - } else { - tree->root = rnode; - } - rnode->left = node; - node->parent = rnode; -} - -static void right_rotate( pj_rbtree *tree, pj_rbtree_node *node ) -{ - pj_rbtree_node *lnode, *parent; - - PJ_CHECK_STACK(); - - lnode = node->left; - if (lnode == tree->null) - return; - - node->left = lnode->right; - if (lnode->right != tree->null) - lnode->right->parent = node; - parent = node->parent; - lnode->parent = parent; - - if (parent != tree->null) { - if (parent->left == node) - parent->left = lnode; - else - parent->right = lnode; - } else { - tree->root = lnode; - } - lnode->right = node; - node->parent = lnode; -} - -static void insert_fixup( pj_rbtree *tree, pj_rbtree_node *node ) -{ - pj_rbtree_node *temp, *parent; - - PJ_CHECK_STACK(); - - while (node != tree->root && node->parent->color == PJ_RBCOLOR_RED) { - parent = node->parent; - if (parent == parent->parent->left) { - temp = parent->parent->right; - if (temp->color == PJ_RBCOLOR_RED) { - temp->color = PJ_RBCOLOR_BLACK; - node = parent; - node->color = PJ_RBCOLOR_BLACK; - node = node->parent; - node->color = PJ_RBCOLOR_RED; - } else { - if (node == parent->right) { - node = parent; - left_rotate(tree, node); - } - temp = node->parent; - temp->color = PJ_RBCOLOR_BLACK; - temp = temp->parent; - temp->color = PJ_RBCOLOR_RED; - right_rotate( tree, temp); - } - } else { - temp = parent->parent->left; - if (temp->color == PJ_RBCOLOR_RED) { - temp->color = PJ_RBCOLOR_BLACK; - node = parent; - node->color = PJ_RBCOLOR_BLACK; - node = node->parent; - node->color = PJ_RBCOLOR_RED; - } else { - if (node == parent->left) { - node = parent; - right_rotate(tree, node); - } - temp = node->parent; - temp->color = PJ_RBCOLOR_BLACK; - temp = temp->parent; - temp->color = PJ_RBCOLOR_RED; - left_rotate(tree, temp); - } - } - } - - tree->root->color = PJ_RBCOLOR_BLACK; -} - - -static void delete_fixup( pj_rbtree *tree, pj_rbtree_node *node ) -{ - pj_rbtree_node *temp; - - PJ_CHECK_STACK(); - - while (node != tree->root && node->color == PJ_RBCOLOR_BLACK) { - if (node->parent->left == node) { - temp = node->parent->right; - if (temp->color == PJ_RBCOLOR_RED) { - temp->color = PJ_RBCOLOR_BLACK; - node->parent->color = PJ_RBCOLOR_RED; - left_rotate(tree, node->parent); - temp = node->parent->right; - } - if (temp->left->color == PJ_RBCOLOR_BLACK && - temp->right->color == PJ_RBCOLOR_BLACK) - { - temp->color = PJ_RBCOLOR_RED; - node = node->parent; - } else { - if (temp->right->color == PJ_RBCOLOR_BLACK) { - temp->left->color = PJ_RBCOLOR_BLACK; - temp->color = PJ_RBCOLOR_RED; - right_rotate( tree, temp); - temp = node->parent->right; - } - temp->color = node->parent->color; - temp->right->color = PJ_RBCOLOR_BLACK; - node->parent->color = PJ_RBCOLOR_BLACK; - left_rotate(tree, node->parent); - node = tree->root; - } - } else { - temp = node->parent->left; - if (temp->color == PJ_RBCOLOR_RED) { - temp->color = PJ_RBCOLOR_BLACK; - node->parent->color = PJ_RBCOLOR_RED; - right_rotate( tree, node->parent); - temp = node->parent->left; - } - if (temp->right->color == PJ_RBCOLOR_BLACK && - temp->left->color == PJ_RBCOLOR_BLACK) - { - temp->color = PJ_RBCOLOR_RED; - node = node->parent; - } else { - if (temp->left->color == PJ_RBCOLOR_BLACK) { - temp->right->color = PJ_RBCOLOR_BLACK; - temp->color = PJ_RBCOLOR_RED; - left_rotate( tree, temp); - temp = node->parent->left; - } - temp->color = node->parent->color; - node->parent->color = PJ_RBCOLOR_BLACK; - temp->left->color = PJ_RBCOLOR_BLACK; - right_rotate(tree, node->parent); - node = tree->root; - } - } - } - - node->color = PJ_RBCOLOR_BLACK; -} - - -PJ_DEF(void) pj_rbtree_init( pj_rbtree *tree, pj_rbtree_comp *comp ) -{ - PJ_CHECK_STACK(); - - tree->null = tree->root = &tree->null_node; - tree->null->key = NULL; - tree->null->user_data = NULL; - tree->size = 0; - tree->null->left = tree->null->right = tree->null->parent = tree->null; - tree->null->color = PJ_RBCOLOR_BLACK; - tree->comp = comp; -} - -PJ_DEF(pj_rbtree_node*) pj_rbtree_first( pj_rbtree *tree ) -{ - register pj_rbtree_node *node = tree->root; - register pj_rbtree_node *null = tree->null; - - PJ_CHECK_STACK(); - - while (node->left != null) - node = node->left; - return node != null ? node : NULL; -} - -PJ_DEF(pj_rbtree_node*) pj_rbtree_last( pj_rbtree *tree ) -{ - register pj_rbtree_node *node = tree->root; - register pj_rbtree_node *null = tree->null; - - PJ_CHECK_STACK(); - - while (node->right != null) - node = node->right; - return node != null ? node : NULL; -} - -PJ_DEF(pj_rbtree_node*) pj_rbtree_next( pj_rbtree *tree, - register pj_rbtree_node *node ) -{ - register pj_rbtree_node *null = tree->null; - - PJ_CHECK_STACK(); - - if (node->right != null) { - for (node=node->right; node->left!=null; node = node->left) - /* void */; - } else { - register pj_rbtree_node *temp = node->parent; - while (temp!=null && temp->right==node) { - node = temp; - temp = temp->parent; - } - node = temp; - } - return node != null ? node : NULL; -} - -PJ_DEF(pj_rbtree_node*) pj_rbtree_prev( pj_rbtree *tree, - register pj_rbtree_node *node ) -{ - register pj_rbtree_node *null = tree->null; - - PJ_CHECK_STACK(); - - if (node->left != null) { - for (node=node->left; node->right!=null; node=node->right) - /* void */; - } else { - register pj_rbtree_node *temp = node->parent; - while (temp!=null && temp->left==node) { - node = temp; - temp = temp->parent; - } - node = temp; - } - return node != null ? node : NULL; -} - -PJ_DEF(int) pj_rbtree_insert( pj_rbtree *tree, - pj_rbtree_node *element ) -{ - int rv = 0; - pj_rbtree_node *node, *parent = tree->null, - *null = tree->null; - pj_rbtree_comp *comp = tree->comp; - - PJ_CHECK_STACK(); - - node = tree->root; - while (node != null) { - rv = (*comp)(element->key, node->key); - if (rv == 0) { - /* found match, i.e. entry with equal key already exist */ - return -1; - } - parent = node; - node = rv < 0 ? node->left : node->right; - } - - element->color = PJ_RBCOLOR_RED; - element->left = element->right = null; - - node = element; - if (parent != null) { - node->parent = parent; - if (rv < 0) - parent->left = node; - else - parent->right = node; - insert_fixup( tree, node); - } else { - tree->root = node; - node->parent = null; - node->color = PJ_RBCOLOR_BLACK; - } - - ++tree->size; - return 0; -} - - -PJ_DEF(pj_rbtree_node*) pj_rbtree_find( pj_rbtree *tree, - const void *key ) -{ - int rv; - pj_rbtree_node *node = tree->root; - pj_rbtree_node *null = tree->null; - pj_rbtree_comp *comp = tree->comp; - - while (node != null) { - rv = (*comp)(key, node->key); - if (rv == 0) - return node; - node = rv < 0 ? node->left : node->right; - } - return node != null ? node : NULL; -} - -PJ_DEF(pj_rbtree_node*) pj_rbtree_erase( pj_rbtree *tree, - pj_rbtree_node *node ) -{ - pj_rbtree_node *succ; - pj_rbtree_node *null = tree->null; - pj_rbtree_node *child; - pj_rbtree_node *parent; - - PJ_CHECK_STACK(); - - if (node->left == null || node->right == null) { - succ = node; - } else { - for (succ=node->right; succ->left!=null; succ=succ->left) - /* void */; - } - - child = succ->left != null ? succ->left : succ->right; - parent = succ->parent; - child->parent = parent; - - if (parent != null) { - if (parent->left == succ) - parent->left = child; - else - parent->right = child; - } else - tree->root = child; - - if (succ != node) { - succ->parent = node->parent; - succ->left = node->left; - succ->right = node->right; - succ->color = node->color; - - parent = node->parent; - if (parent != null) { - if (parent->left==node) - parent->left=succ; - else - parent->right=succ; - } - if (node->left != null) - node->left->parent = succ;; - if (node->right != null) - node->right->parent = succ; - - if (tree->root == node) - tree->root = succ; - } - - if (succ->color == PJ_RBCOLOR_BLACK) { - if (child != null) - delete_fixup(tree, child); - tree->null->color = PJ_RBCOLOR_BLACK; - } - - --tree->size; - return node; -} - - -PJ_DEF(unsigned) pj_rbtree_max_height( pj_rbtree *tree, - pj_rbtree_node *node ) -{ - unsigned l, r; - - PJ_CHECK_STACK(); - - if (node==NULL) - node = tree->root; - - l = node->left != tree->null ? pj_rbtree_max_height(tree,node->left)+1 : 0; - r = node->right != tree->null ? pj_rbtree_max_height(tree,node->right)+1 : 0; - return l > r ? l : r; -} - -PJ_DEF(unsigned) pj_rbtree_min_height( pj_rbtree *tree, - pj_rbtree_node *node ) -{ - unsigned l, r; - - PJ_CHECK_STACK(); - - if (node==NULL) - node=tree->root; - - l = (node->left != tree->null) ? pj_rbtree_max_height(tree,node->left)+1 : 0; - r = (node->right != tree->null) ? pj_rbtree_max_height(tree,node->right)+1 : 0; - return l > r ? r : l; -} - - +/* $Id$
+ */
+/*
+ * PJLIB - PJ Foundation Library
+ * (C)2003-2005 Benny Prijono <bennylp@bulukucing.org>
+ *
+ * Author:
+ * Benny Prijono <bennylp@bulukucing.org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+#include <pj/rbtree.h>
+#include <pj/os.h>
+
+static void left_rotate( pj_rbtree *tree, pj_rbtree_node *node )
+{
+ pj_rbtree_node *rnode, *parent;
+
+ PJ_CHECK_STACK();
+
+ rnode = node->right;
+ if (rnode == tree->null)
+ return;
+
+ node->right = rnode->left;
+ if (rnode->left != tree->null)
+ rnode->left->parent = node;
+ parent = node->parent;
+ rnode->parent = parent;
+ if (parent != tree->null) {
+ if (parent->left == node)
+ parent->left = rnode;
+ else
+ parent->right = rnode;
+ } else {
+ tree->root = rnode;
+ }
+ rnode->left = node;
+ node->parent = rnode;
+}
+
+static void right_rotate( pj_rbtree *tree, pj_rbtree_node *node )
+{
+ pj_rbtree_node *lnode, *parent;
+
+ PJ_CHECK_STACK();
+
+ lnode = node->left;
+ if (lnode == tree->null)
+ return;
+
+ node->left = lnode->right;
+ if (lnode->right != tree->null)
+ lnode->right->parent = node;
+ parent = node->parent;
+ lnode->parent = parent;
+
+ if (parent != tree->null) {
+ if (parent->left == node)
+ parent->left = lnode;
+ else
+ parent->right = lnode;
+ } else {
+ tree->root = lnode;
+ }
+ lnode->right = node;
+ node->parent = lnode;
+}
+
+static void insert_fixup( pj_rbtree *tree, pj_rbtree_node *node )
+{
+ pj_rbtree_node *temp, *parent;
+
+ PJ_CHECK_STACK();
+
+ while (node != tree->root && node->parent->color == PJ_RBCOLOR_RED) {
+ parent = node->parent;
+ if (parent == parent->parent->left) {
+ temp = parent->parent->right;
+ if (temp->color == PJ_RBCOLOR_RED) {
+ temp->color = PJ_RBCOLOR_BLACK;
+ node = parent;
+ node->color = PJ_RBCOLOR_BLACK;
+ node = node->parent;
+ node->color = PJ_RBCOLOR_RED;
+ } else {
+ if (node == parent->right) {
+ node = parent;
+ left_rotate(tree, node);
+ }
+ temp = node->parent;
+ temp->color = PJ_RBCOLOR_BLACK;
+ temp = temp->parent;
+ temp->color = PJ_RBCOLOR_RED;
+ right_rotate( tree, temp);
+ }
+ } else {
+ temp = parent->parent->left;
+ if (temp->color == PJ_RBCOLOR_RED) {
+ temp->color = PJ_RBCOLOR_BLACK;
+ node = parent;
+ node->color = PJ_RBCOLOR_BLACK;
+ node = node->parent;
+ node->color = PJ_RBCOLOR_RED;
+ } else {
+ if (node == parent->left) {
+ node = parent;
+ right_rotate(tree, node);
+ }
+ temp = node->parent;
+ temp->color = PJ_RBCOLOR_BLACK;
+ temp = temp->parent;
+ temp->color = PJ_RBCOLOR_RED;
+ left_rotate(tree, temp);
+ }
+ }
+ }
+
+ tree->root->color = PJ_RBCOLOR_BLACK;
+}
+
+
+static void delete_fixup( pj_rbtree *tree, pj_rbtree_node *node )
+{
+ pj_rbtree_node *temp;
+
+ PJ_CHECK_STACK();
+
+ while (node != tree->root && node->color == PJ_RBCOLOR_BLACK) {
+ if (node->parent->left == node) {
+ temp = node->parent->right;
+ if (temp->color == PJ_RBCOLOR_RED) {
+ temp->color = PJ_RBCOLOR_BLACK;
+ node->parent->color = PJ_RBCOLOR_RED;
+ left_rotate(tree, node->parent);
+ temp = node->parent->right;
+ }
+ if (temp->left->color == PJ_RBCOLOR_BLACK &&
+ temp->right->color == PJ_RBCOLOR_BLACK)
+ {
+ temp->color = PJ_RBCOLOR_RED;
+ node = node->parent;
+ } else {
+ if (temp->right->color == PJ_RBCOLOR_BLACK) {
+ temp->left->color = PJ_RBCOLOR_BLACK;
+ temp->color = PJ_RBCOLOR_RED;
+ right_rotate( tree, temp);
+ temp = node->parent->right;
+ }
+ temp->color = node->parent->color;
+ temp->right->color = PJ_RBCOLOR_BLACK;
+ node->parent->color = PJ_RBCOLOR_BLACK;
+ left_rotate(tree, node->parent);
+ node = tree->root;
+ }
+ } else {
+ temp = node->parent->left;
+ if (temp->color == PJ_RBCOLOR_RED) {
+ temp->color = PJ_RBCOLOR_BLACK;
+ node->parent->color = PJ_RBCOLOR_RED;
+ right_rotate( tree, node->parent);
+ temp = node->parent->left;
+ }
+ if (temp->right->color == PJ_RBCOLOR_BLACK &&
+ temp->left->color == PJ_RBCOLOR_BLACK)
+ {
+ temp->color = PJ_RBCOLOR_RED;
+ node = node->parent;
+ } else {
+ if (temp->left->color == PJ_RBCOLOR_BLACK) {
+ temp->right->color = PJ_RBCOLOR_BLACK;
+ temp->color = PJ_RBCOLOR_RED;
+ left_rotate( tree, temp);
+ temp = node->parent->left;
+ }
+ temp->color = node->parent->color;
+ node->parent->color = PJ_RBCOLOR_BLACK;
+ temp->left->color = PJ_RBCOLOR_BLACK;
+ right_rotate(tree, node->parent);
+ node = tree->root;
+ }
+ }
+ }
+
+ node->color = PJ_RBCOLOR_BLACK;
+}
+
+
+PJ_DEF(void) pj_rbtree_init( pj_rbtree *tree, pj_rbtree_comp *comp )
+{
+ PJ_CHECK_STACK();
+
+ tree->null = tree->root = &tree->null_node;
+ tree->null->key = NULL;
+ tree->null->user_data = NULL;
+ tree->size = 0;
+ tree->null->left = tree->null->right = tree->null->parent = tree->null;
+ tree->null->color = PJ_RBCOLOR_BLACK;
+ tree->comp = comp;
+}
+
+PJ_DEF(pj_rbtree_node*) pj_rbtree_first( pj_rbtree *tree )
+{
+ register pj_rbtree_node *node = tree->root;
+ register pj_rbtree_node *null = tree->null;
+
+ PJ_CHECK_STACK();
+
+ while (node->left != null)
+ node = node->left;
+ return node != null ? node : NULL;
+}
+
+PJ_DEF(pj_rbtree_node*) pj_rbtree_last( pj_rbtree *tree )
+{
+ register pj_rbtree_node *node = tree->root;
+ register pj_rbtree_node *null = tree->null;
+
+ PJ_CHECK_STACK();
+
+ while (node->right != null)
+ node = node->right;
+ return node != null ? node : NULL;
+}
+
+PJ_DEF(pj_rbtree_node*) pj_rbtree_next( pj_rbtree *tree,
+ register pj_rbtree_node *node )
+{
+ register pj_rbtree_node *null = tree->null;
+
+ PJ_CHECK_STACK();
+
+ if (node->right != null) {
+ for (node=node->right; node->left!=null; node = node->left)
+ /* void */;
+ } else {
+ register pj_rbtree_node *temp = node->parent;
+ while (temp!=null && temp->right==node) {
+ node = temp;
+ temp = temp->parent;
+ }
+ node = temp;
+ }
+ return node != null ? node : NULL;
+}
+
+PJ_DEF(pj_rbtree_node*) pj_rbtree_prev( pj_rbtree *tree,
+ register pj_rbtree_node *node )
+{
+ register pj_rbtree_node *null = tree->null;
+
+ PJ_CHECK_STACK();
+
+ if (node->left != null) {
+ for (node=node->left; node->right!=null; node=node->right)
+ /* void */;
+ } else {
+ register pj_rbtree_node *temp = node->parent;
+ while (temp!=null && temp->left==node) {
+ node = temp;
+ temp = temp->parent;
+ }
+ node = temp;
+ }
+ return node != null ? node : NULL;
+}
+
+PJ_DEF(int) pj_rbtree_insert( pj_rbtree *tree,
+ pj_rbtree_node *element )
+{
+ int rv = 0;
+ pj_rbtree_node *node, *parent = tree->null,
+ *null = tree->null;
+ pj_rbtree_comp *comp = tree->comp;
+
+ PJ_CHECK_STACK();
+
+ node = tree->root;
+ while (node != null) {
+ rv = (*comp)(element->key, node->key);
+ if (rv == 0) {
+ /* found match, i.e. entry with equal key already exist */
+ return -1;
+ }
+ parent = node;
+ node = rv < 0 ? node->left : node->right;
+ }
+
+ element->color = PJ_RBCOLOR_RED;
+ element->left = element->right = null;
+
+ node = element;
+ if (parent != null) {
+ node->parent = parent;
+ if (rv < 0)
+ parent->left = node;
+ else
+ parent->right = node;
+ insert_fixup( tree, node);
+ } else {
+ tree->root = node;
+ node->parent = null;
+ node->color = PJ_RBCOLOR_BLACK;
+ }
+
+ ++tree->size;
+ return 0;
+}
+
+
+PJ_DEF(pj_rbtree_node*) pj_rbtree_find( pj_rbtree *tree,
+ const void *key )
+{
+ int rv;
+ pj_rbtree_node *node = tree->root;
+ pj_rbtree_node *null = tree->null;
+ pj_rbtree_comp *comp = tree->comp;
+
+ while (node != null) {
+ rv = (*comp)(key, node->key);
+ if (rv == 0)
+ return node;
+ node = rv < 0 ? node->left : node->right;
+ }
+ return node != null ? node : NULL;
+}
+
+PJ_DEF(pj_rbtree_node*) pj_rbtree_erase( pj_rbtree *tree,
+ pj_rbtree_node *node )
+{
+ pj_rbtree_node *succ;
+ pj_rbtree_node *null = tree->null;
+ pj_rbtree_node *child;
+ pj_rbtree_node *parent;
+
+ PJ_CHECK_STACK();
+
+ if (node->left == null || node->right == null) {
+ succ = node;
+ } else {
+ for (succ=node->right; succ->left!=null; succ=succ->left)
+ /* void */;
+ }
+
+ child = succ->left != null ? succ->left : succ->right;
+ parent = succ->parent;
+ child->parent = parent;
+
+ if (parent != null) {
+ if (parent->left == succ)
+ parent->left = child;
+ else
+ parent->right = child;
+ } else
+ tree->root = child;
+
+ if (succ != node) {
+ succ->parent = node->parent;
+ succ->left = node->left;
+ succ->right = node->right;
+ succ->color = node->color;
+
+ parent = node->parent;
+ if (parent != null) {
+ if (parent->left==node)
+ parent->left=succ;
+ else
+ parent->right=succ;
+ }
+ if (node->left != null)
+ node->left->parent = succ;;
+ if (node->right != null)
+ node->right->parent = succ;
+
+ if (tree->root == node)
+ tree->root = succ;
+ }
+
+ if (succ->color == PJ_RBCOLOR_BLACK) {
+ if (child != null)
+ delete_fixup(tree, child);
+ tree->null->color = PJ_RBCOLOR_BLACK;
+ }
+
+ --tree->size;
+ return node;
+}
+
+
+PJ_DEF(unsigned) pj_rbtree_max_height( pj_rbtree *tree,
+ pj_rbtree_node *node )
+{
+ unsigned l, r;
+
+ PJ_CHECK_STACK();
+
+ if (node==NULL)
+ node = tree->root;
+
+ l = node->left != tree->null ? pj_rbtree_max_height(tree,node->left)+1 : 0;
+ r = node->right != tree->null ? pj_rbtree_max_height(tree,node->right)+1 : 0;
+ return l > r ? l : r;
+}
+
+PJ_DEF(unsigned) pj_rbtree_min_height( pj_rbtree *tree,
+ pj_rbtree_node *node )
+{
+ unsigned l, r;
+
+ PJ_CHECK_STACK();
+
+ if (node==NULL)
+ node=tree->root;
+
+ l = (node->left != tree->null) ? pj_rbtree_max_height(tree,node->left)+1 : 0;
+ r = (node->right != tree->null) ? pj_rbtree_max_height(tree,node->right)+1 : 0;
+ return l > r ? r : l;
+}
+
+
|