/* $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 | |
*/ | |
#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; | |
} | |