2) Fixed bug in constructbindings method.
-static char rcsid[]="$Id: redblack.c,v 1.1 2004/10/28 19:29:04 bdemsky Exp $";
+static char rcsid[]="$Id: redblack.c,v 1.2 2004/11/10 05:44:37 bdemsky Exp $";
/*
Redblack balanced tree algorithm
/*
Redblack balanced tree algorithm
struct rbtree * rbinit() {
struct rbtree *retval;
char c;
struct rbtree * rbinit() {
struct rbtree *retval;
char c;
c=rcsid[0]; /* This does nothing but shutup the -Wall */
c=rcsid[0]; /* This does nothing but shutup the -Wall */
if ((retval=(struct rbtree *) malloc(sizeof(struct rbtree)))==NULL)
return(NULL);
if ((retval=(struct rbtree *) malloc(sizeof(struct rbtree)))==NULL)
return(NULL);
void rbdestroy(struct rbtree *rbinfo, void (*free_function)(void *)) {
if (rbinfo==NULL)
return;
void rbdestroy(struct rbtree *rbinfo, void (*free_function)(void *)) {
if (rbinfo==NULL)
return;
if (rbinfo->rb_root!=RBNULL)
rb_destroy(rbinfo->rb_root,free_function);
if (rbinfo->rb_root!=RBNULL)
rb_destroy(rbinfo->rb_root,free_function);
free(rbinfo);
}
const void * rbdelete(const void *key, struct rbtree *rbinfo) {
struct rbnode *x;
const void *y;
free(rbinfo);
}
const void * rbdelete(const void *key, struct rbtree *rbinfo) {
struct rbnode *x;
const void *y;
if (rbinfo==NULL)
return(NULL);
if (rbinfo==NULL)
return(NULL);
x=rb_traverse(key, rbinfo);
x=rb_traverse(key, rbinfo);
+
+ if (x==NULL||x==RBNULL) {
return(NULL);
} else {
y=x->key;
rb_delete(&rbinfo->rb_root, x);
return(NULL);
} else {
y=x->key;
rb_delete(&rbinfo->rb_root, x);
/* If we have a NULL root (empty tree) then just return NULL */
if (rbinfo==NULL || rbinfo->rb_root==NULL)
return(NULL);
/* If we have a NULL root (empty tree) then just return NULL */
if (rbinfo==NULL || rbinfo->rb_root==NULL)
return(NULL);
x=rb_lookup(low, high, rbinfo);
x=rb_lookup(low, high, rbinfo);
return((x==RBNULL) ? NULL : x->object);
}
return((x==RBNULL) ? NULL : x->object);
}
p.high=NULL;
if (rbinfo==NULL || rbinfo->rb_root==NULL)
return p;
p.high=NULL;
if (rbinfo==NULL || rbinfo->rb_root==NULL)
return p;
x=rb_lookup(low, high, rbinfo);
if (x!=NULL) {
p.low=x->key;
x=rb_lookup(low, high, rbinfo);
if (x!=NULL) {
p.low=x->key;
struct rbnode *x,*y,*z, *tmp;
const void *max;
int found=0;
struct rbnode *x,*y,*z, *tmp;
const void *max;
int found=0;
y=RBNULL; /* points to the parent of x */
x=rbinfo->rb_root;
y=RBNULL; /* points to the parent of x */
x=rbinfo->rb_root;
/* walk x down the tree */
while(x!=RBNULL && found==0) {
y=x;
/* walk x down the tree */
while(x!=RBNULL && found==0) {
y=x;
if (found)
return RB_FALSE;
if (found)
return RB_FALSE;
if ((z=rb_alloc())==NULL) {
/* Whoops, no memory */
return RB_FALSE;
}
if ((z=rb_alloc())==NULL) {
/* Whoops, no memory */
return RB_FALSE;
}
z->object=object;
z->high=high;
z->key=key;
z->object=object;
z->high=high;
z->key=key;
z->left=RBNULL;
z->right=RBNULL;
z->left=RBNULL;
z->right=RBNULL;
/* colour this new node red */
z->colour=RED;
/* colour this new node red */
z->colour=RED;
** it, by a series of rotations and changing of colours
*/
x=z;
** it, by a series of rotations and changing of colours
*/
x=z;
/* While we are not at the top and our parent node is red
** N.B. Since the root node is garanteed black, then we
** are also going to stop if we are the child of the root
*/
/* While we are not at the top and our parent node is red
** N.B. Since the root node is garanteed black, then we
** are also going to stop if we are the child of the root
*/
while(x != rbinfo->rb_root && (x->up->colour == RED)) {
/* if our parent is on the left side of our grandparent */
if (x->up == x->up->up->left) {
while(x != rbinfo->rb_root && (x->up->colour == RED)) {
/* if our parent is on the left side of our grandparent */
if (x->up == x->up->up->left) {
y->colour = BLACK;
/* make our grandparent red */
x->up->up->colour = RED;
y->colour = BLACK;
/* make our grandparent red */
x->up->up->colour = RED;
/* now consider our grandparent */
x=x->up->up;
} else {
/* now consider our grandparent */
x=x->up->up;
} else {
x=x->up;
rb_left_rotate(&rbinfo->rb_root, x);
}
x=x->up;
rb_left_rotate(&rbinfo->rb_root, x);
}
/* make our parent black */
x->up->colour = BLACK;
/* make our grandparent red */
/* make our parent black */
x->up->colour = BLACK;
/* make our grandparent red */
x->up->colour = BLACK;
y->colour = BLACK;
x->up->up->colour = RED;
x->up->colour = BLACK;
y->colour = BLACK;
x->up->up->colour = RED;
x=x->up->up;
} else {
if (x == x->up->left) {
x=x->up;
rb_right_rotate(&rbinfo->rb_root, x);
}
x=x->up->up;
} else {
if (x == x->up->left) {
x=x->up;
rb_right_rotate(&rbinfo->rb_root, x);
}
x->up->colour = BLACK;
x->up->up->colour = RED;
rb_left_rotate(&rbinfo->rb_root, x->up->up);
x->up->colour = BLACK;
x->up->up->colour = RED;
rb_left_rotate(&rbinfo->rb_root, x->up->up);
static struct rbnode * rb_traverse(const void *key, struct rbtree *rbinfo) {
struct rbnode *x,*y,*z;
int found=0;
static struct rbnode * rb_traverse(const void *key, struct rbtree *rbinfo) {
struct rbnode *x,*y,*z;
int found=0;
y=RBNULL; /* points to the parent of x */
x=rbinfo->rb_root;
y=RBNULL; /* points to the parent of x */
x=rbinfo->rb_root;
/* walk x down the tree */
while(x!=RBNULL && found==0) {
y=x;
/* walk x down the tree */
while(x!=RBNULL && found==0) {
y=x;
if (found)
return(x);
return NULL;
if (found)
return(x);
return NULL;
*/
static struct rbnode * rb_lookup(const void *low, const void *high, struct rbtree *rbinfo) {
struct rbnode *x;
*/
static struct rbnode * rb_lookup(const void *low, const void *high, struct rbtree *rbinfo) {
struct rbnode *x;
/* walk x down the tree */
while(x!=RBNULL) {
if (low<x->high &&
/* walk x down the tree */
while(x!=RBNULL) {
if (low<x->high &&
return RB_FALSE;
x=rbinfo->rb_root;
return RB_FALSE;
x=rbinfo->rb_root;
/* walk x down the tree */
while(x!=RBNULL) {
if (low<x->high &&
/* walk x down the tree */
while(x!=RBNULL) {
if (low<x->high &&
const void *max;
assert(x!=RBNULL);
assert(x->right!=RBNULL);
const void *max;
assert(x!=RBNULL);
assert(x->right!=RBNULL);
/* Turn Y's left subtree into X's right subtree (move B)*/
x->right = y->left;
/* Turn Y's left subtree into X's right subtree (move B)*/
x->right = y->left;
/* If B is not null, set it's parent to be X */
if (y->left != RBNULL)
y->left->up = x;
/* If B is not null, set it's parent to be X */
if (y->left != RBNULL)
y->left->up = x;
/* Set Y's parent to be what X's parent was */
y->up = x->up;
/* Set Y's parent to be what X's parent was */
y->up = x->up;
/* if X was the root */
if (x->up == RBNULL) {
*rootp=y;
/* if X was the root */
if (x->up == RBNULL) {
*rootp=y;
/* Put X on Y's left */
y->left=x;
/* Put X on Y's left */
y->left=x;
/* Set X's parent to be Y */
x->up = y;
/* Set X's parent to be Y */
x->up = y;
y->max=x->max; /* compute Y's max */
max=NULL;
y->max=x->max; /* compute Y's max */
max=NULL;
if (x->left!=RBNULL)
max=x->left->max;
if (x->left!=RBNULL)
max=x->left->max;
if (x->right!=RBNULL&&
x->right->max>max)
max=x->right->max;
if (x->right!=RBNULL&&
x->right->max>max)
max=x->right->max;
static void rb_right_rotate(struct rbnode **rootp, struct rbnode *y) {
struct rbnode *x;
const void *max;
static void rb_right_rotate(struct rbnode **rootp, struct rbnode *y) {
struct rbnode *x;
const void *max;
assert(y!=RBNULL);
assert(y->left!=RBNULL);
assert(y!=RBNULL);
assert(y->left!=RBNULL);
x=y->left; /* set X */
/* Turn X's right subtree into Y's left subtree (move B) */
y->left = x->right;
x=y->left; /* set X */
/* Turn X's right subtree into Y's left subtree (move B) */
y->left = x->right;
/* If B is not null, set it's parent to be Y */
if (x->right != RBNULL)
x->right->up = y;
/* If B is not null, set it's parent to be Y */
if (x->right != RBNULL)
x->right->up = y;
/* Put Y on X's right */
x->right=y;
/* Put Y on X's right */
x->right=y;
/* Set Y's parent to be X */
y->up = x;
/* Set Y's parent to be X */
y->up = x;
if (y->left!=RBNULL)
max=y->left->max;
if (y->left!=RBNULL)
max=y->left->max;
if (y->right!=RBNULL&&
y->right->max>max)
max=y->right->max;
if (y->right!=RBNULL&&
y->right->max>max)
max=y->right->max;
static void rb_delete(struct rbnode **rootp, struct rbnode *z) {
struct rbnode *x, *y, *tmp;
const void *max;
static void rb_delete(struct rbnode **rootp, struct rbnode *z) {
struct rbnode *x, *y, *tmp;
const void *max;
if (z->left == RBNULL || z->right == RBNULL)
y=z;
else
y=rb_successor(z);
if (z->left == RBNULL || z->right == RBNULL)
y=z;
else
y=rb_successor(z);
if (y->left != RBNULL)
x=y->left;
else
x=y->right;
if (y->left != RBNULL)
x=y->left;
else
x=y->right;
if (y->up == RBNULL) {
*rootp=x;
} else {
if (y->up == RBNULL) {
*rootp=x;
} else {
if (y!=z) {
z->key = y->key;
z->high=y->high;
if (y!=z) {
z->key = y->key;
z->high=y->high;
}
if (y->colour == BLACK)
rb_delete_fix(rootp, x);
}
if (y->colour == BLACK)
rb_delete_fix(rootp, x);
rb_free(y);
}
/* Restore the reb-black properties after a delete */
static void rb_delete_fix(struct rbnode **rootp, struct rbnode *x) {
struct rbnode *w;
rb_free(y);
}
/* Restore the reb-black properties after a delete */
static void rb_delete_fix(struct rbnode **rootp, struct rbnode *x) {
struct rbnode *w;
while (x!=*rootp && x->colour==BLACK) {
if (x==x->up->left) {
w=x->up->right;
while (x!=*rootp && x->colour==BLACK) {
if (x==x->up->left) {
w=x->up->right;
rb_walk(const struct rbnode *x, void (*action)(const void *, const VISIT, const int, void *), void *arg, int level) {
if (x==RBNULL)
return;
rb_walk(const struct rbnode *x, void (*action)(const void *, const VISIT, const int, void *), void *arg, int level) {
if (x==RBNULL)
return;
if (x->left==RBNULL && x->right==RBNULL) {
/* leaf */
(*action)(x->key, leaf, level, arg);
} else {
(*action)(x->key, preorder, level, arg);
if (x->left==RBNULL && x->right==RBNULL) {
/* leaf */
(*action)(x->key, leaf, level, arg);
} else {
(*action)(x->key, preorder, level, arg);
rb_walk(x->left, action, arg, level+1);
rb_walk(x->left, action, arg, level+1);
(*action)(x->key, postorder, level, arg);
rb_walk(x->right, action, arg, level+1);
(*action)(x->key, postorder, level, arg);
rb_walk(x->right, action, arg, level+1);
static RBLIST * rb_openlist(const struct rbnode *rootp) {
RBLIST *rblistp;
static RBLIST * rb_openlist(const struct rbnode *rootp) {
RBLIST *rblistp;
rblistp=(RBLIST *) malloc(sizeof(RBLIST));
if (!rblistp)
return(NULL);
rblistp=(RBLIST *) malloc(sizeof(RBLIST));
if (!rblistp)
return(NULL);
rblistp->rootp=rootp;
rblistp->nextp=rootp;
rblistp->rootp=rootp;
rblistp->nextp=rootp;
if (rootp!=RBNULL) {
while(rblistp->nextp->left!=RBNULL) {
rblistp->nextp=rblistp->nextp->left;
if (rootp!=RBNULL) {
while(rblistp->nextp->left!=RBNULL) {
rblistp->nextp=rblistp->nextp->left;
int rb_check(struct rbnode *rootp) {
if (rootp==NULL || rootp==RBNULL)
return(0);
int rb_check(struct rbnode *rootp) {
if (rootp==NULL || rootp==RBNULL)
return(0);
if (rootp->up!=RBNULL) {
fprintf(stderr, "Root up pointer not RBNULL");
dumptree(rootp, 0);
return(1);
}
if (rootp->up!=RBNULL) {
fprintf(stderr, "Root up pointer not RBNULL");
dumptree(rootp, 0);
return(1);
}
if (rb_check1(rootp)) {
dumptree(rootp, 0);
return(1);
if (rb_check1(rootp)) {
dumptree(rootp, 0);
return(1);
dumptree(rootp, 0);
return(-1);
}
dumptree(rootp, 0);
return(-1);
}
fprintf(stderr, "Left or right is NULL");
return(1);
}
fprintf(stderr, "Left or right is NULL");
return(1);
}
if (x->colour==RED)
{
if (x->left->colour!=BLACK && x->right->colour!=BLACK)
if (x->colour==RED)
{
if (x->left->colour!=BLACK && x->right->colour!=BLACK)
if (x->left != RBNULL)
{
if (x->left->up != x)
if (x->left != RBNULL)
{
if (x->left->up != x)
fprintf(stderr, "x->left->up != x, x=%ld", x);
return(1);
}
fprintf(stderr, "x->left->up != x, x=%ld", x);
return(1);
}
if (rb_check1(x->left))
return(1);
if (rb_check1(x->left))
return(1);
if (x->right != RBNULL)
{
if (x->right->up != x)
if (x->right != RBNULL)
{
if (x->right->up != x)
fprintf(stderr, "x->right->up != x, x=%ld", x);
return(1);
}
fprintf(stderr, "x->right->up != x, x=%ld", x);
return(1);
}
if (rb_check1(x->right))
return(1);
if (rb_check1(x->right))
return(1);
return(0);
}
count_black(struct rbnode *x)
{
int nleft, nright;
return(0);
}
count_black(struct rbnode *x)
{
int nleft, nright;
if (x==RBNULL)
return(1);
if (x==RBNULL)
return(1);
nleft=count_black(x->left);
nright=count_black(x->right);
nleft=count_black(x->left);
nright=count_black(x->right);
if (nleft==-1 || nright==-1)
return(-1);
if (nleft==-1 || nright==-1)
return(-1);
if (nleft != nright)
{
fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
return(-1);
}
if (nleft != nright)
{
fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
return(-1);
}
if (x->colour == BLACK)
{
nleft++;
}
if (x->colour == BLACK)
{
nleft++;
}
return(nleft);
}
dumptree(struct rbnode *x, int n)
{
char *prkey();
return(nleft);
}
dumptree(struct rbnode *x, int n)
{
char *prkey();
if (x!=NULL && x!=RBNULL)
{
n++;
if (x!=NULL && x!=RBNULL)
{
n++;
x->right,
(x->colour==BLACK) ? "BLACK" : "RED",
prkey(x->key));
x->right,
(x->colour==BLACK) ? "BLACK" : "RED",
prkey(x->key));
dumptree(x->left, n);
dumptree(x->right, n);
dumptree(x->left, n);
dumptree(x->right, n);
}
#endif
/*
* $Log: redblack.c,v $
}
#endif
/*
* $Log: redblack.c,v $
+ * Revision 1.2 2004/11/10 05:44:37 bdemsky
+ *
+ *
+ * 1) Fixed some bugs in the redblack tree implementation...removing a non-present node resulted in a segfault.
+ *
+ * 2) Fixed bug in constructbindings method.
+ *
* Revision 1.1 2004/10/28 19:29:04 bdemsky
* Checking in C runtime.
*
* Revision 1.1 2004/10/28 19:29:04 bdemsky
* Checking in C runtime.
*
* Initial import of files. Versions are now all over the place. Oh well
*
*/
* Initial import of files. Versions are now all over the place. Oh well
*
*/
-static char rcsid[]="$Id: redblack.c,v 1.1 2004/10/28 19:28:59 bdemsky Exp $";
+static char rcsid[]="$Id: redblack.c,v 1.2 2004/11/10 05:44:00 bdemsky Exp $";
/*
Redblack balanced tree algorithm
/*
Redblack balanced tree algorithm
struct rbtree * rbinit() {
struct rbtree *retval;
char c;
struct rbtree * rbinit() {
struct rbtree *retval;
char c;
c=rcsid[0]; /* This does nothing but shutup the -Wall */
c=rcsid[0]; /* This does nothing but shutup the -Wall */
if ((retval=(struct rbtree *) malloc(sizeof(struct rbtree)))==NULL)
return(NULL);
if ((retval=(struct rbtree *) malloc(sizeof(struct rbtree)))==NULL)
return(NULL);
void rbdestroy(struct rbtree *rbinfo, void (*free_function)(void *)) {
if (rbinfo==NULL)
return;
void rbdestroy(struct rbtree *rbinfo, void (*free_function)(void *)) {
if (rbinfo==NULL)
return;
if (rbinfo->rb_root!=RBNULL)
rb_destroy(rbinfo->rb_root,free_function);
if (rbinfo->rb_root!=RBNULL)
rb_destroy(rbinfo->rb_root,free_function);
free(rbinfo);
}
const void * rbdelete(const void *key, struct rbtree *rbinfo) {
struct rbnode *x;
const void *y;
free(rbinfo);
}
const void * rbdelete(const void *key, struct rbtree *rbinfo) {
struct rbnode *x;
const void *y;
if (rbinfo==NULL)
return(NULL);
if (rbinfo==NULL)
return(NULL);
x=rb_traverse(key, rbinfo);
x=rb_traverse(key, rbinfo);
+
+ if (x==NULL||x==RBNULL) {
return(NULL);
} else {
y=x->key;
rb_delete(&rbinfo->rb_root, x);
return(NULL);
} else {
y=x->key;
rb_delete(&rbinfo->rb_root, x);
/* If we have a NULL root (empty tree) then just return NULL */
if (rbinfo==NULL || rbinfo->rb_root==NULL)
return(NULL);
/* If we have a NULL root (empty tree) then just return NULL */
if (rbinfo==NULL || rbinfo->rb_root==NULL)
return(NULL);
x=rb_lookup(low, high, rbinfo);
x=rb_lookup(low, high, rbinfo);
return((x==RBNULL) ? NULL : x->object);
}
return((x==RBNULL) ? NULL : x->object);
}
p.high=NULL;
if (rbinfo==NULL || rbinfo->rb_root==NULL)
return p;
p.high=NULL;
if (rbinfo==NULL || rbinfo->rb_root==NULL)
return p;
x=rb_lookup(low, high, rbinfo);
if (x!=NULL) {
p.low=x->key;
x=rb_lookup(low, high, rbinfo);
if (x!=NULL) {
p.low=x->key;
struct rbnode *x,*y,*z, *tmp;
const void *max;
int found=0;
struct rbnode *x,*y,*z, *tmp;
const void *max;
int found=0;
y=RBNULL; /* points to the parent of x */
x=rbinfo->rb_root;
y=RBNULL; /* points to the parent of x */
x=rbinfo->rb_root;
/* walk x down the tree */
while(x!=RBNULL && found==0) {
y=x;
/* walk x down the tree */
while(x!=RBNULL && found==0) {
y=x;
if (found)
return RB_FALSE;
if (found)
return RB_FALSE;
if ((z=rb_alloc())==NULL) {
/* Whoops, no memory */
return RB_FALSE;
}
if ((z=rb_alloc())==NULL) {
/* Whoops, no memory */
return RB_FALSE;
}
z->object=object;
z->high=high;
z->key=key;
z->object=object;
z->high=high;
z->key=key;
z->left=RBNULL;
z->right=RBNULL;
z->left=RBNULL;
z->right=RBNULL;
/* colour this new node red */
z->colour=RED;
/* colour this new node red */
z->colour=RED;
** it, by a series of rotations and changing of colours
*/
x=z;
** it, by a series of rotations and changing of colours
*/
x=z;
/* While we are not at the top and our parent node is red
** N.B. Since the root node is garanteed black, then we
** are also going to stop if we are the child of the root
*/
/* While we are not at the top and our parent node is red
** N.B. Since the root node is garanteed black, then we
** are also going to stop if we are the child of the root
*/
while(x != rbinfo->rb_root && (x->up->colour == RED)) {
/* if our parent is on the left side of our grandparent */
if (x->up == x->up->up->left) {
while(x != rbinfo->rb_root && (x->up->colour == RED)) {
/* if our parent is on the left side of our grandparent */
if (x->up == x->up->up->left) {
y->colour = BLACK;
/* make our grandparent red */
x->up->up->colour = RED;
y->colour = BLACK;
/* make our grandparent red */
x->up->up->colour = RED;
/* now consider our grandparent */
x=x->up->up;
} else {
/* now consider our grandparent */
x=x->up->up;
} else {
x=x->up;
rb_left_rotate(&rbinfo->rb_root, x);
}
x=x->up;
rb_left_rotate(&rbinfo->rb_root, x);
}
/* make our parent black */
x->up->colour = BLACK;
/* make our grandparent red */
/* make our parent black */
x->up->colour = BLACK;
/* make our grandparent red */
x->up->colour = BLACK;
y->colour = BLACK;
x->up->up->colour = RED;
x->up->colour = BLACK;
y->colour = BLACK;
x->up->up->colour = RED;
x=x->up->up;
} else {
if (x == x->up->left) {
x=x->up;
rb_right_rotate(&rbinfo->rb_root, x);
}
x=x->up->up;
} else {
if (x == x->up->left) {
x=x->up;
rb_right_rotate(&rbinfo->rb_root, x);
}
x->up->colour = BLACK;
x->up->up->colour = RED;
rb_left_rotate(&rbinfo->rb_root, x->up->up);
x->up->colour = BLACK;
x->up->up->colour = RED;
rb_left_rotate(&rbinfo->rb_root, x->up->up);
static struct rbnode * rb_traverse(const void *key, struct rbtree *rbinfo) {
struct rbnode *x,*y,*z;
int found=0;
static struct rbnode * rb_traverse(const void *key, struct rbtree *rbinfo) {
struct rbnode *x,*y,*z;
int found=0;
y=RBNULL; /* points to the parent of x */
x=rbinfo->rb_root;
y=RBNULL; /* points to the parent of x */
x=rbinfo->rb_root;
/* walk x down the tree */
while(x!=RBNULL && found==0) {
y=x;
/* walk x down the tree */
while(x!=RBNULL && found==0) {
y=x;
if (found)
return(x);
return NULL;
if (found)
return(x);
return NULL;
*/
static struct rbnode * rb_lookup(const void *low, const void *high, struct rbtree *rbinfo) {
struct rbnode *x;
*/
static struct rbnode * rb_lookup(const void *low, const void *high, struct rbtree *rbinfo) {
struct rbnode *x;
/* walk x down the tree */
while(x!=RBNULL) {
if (low<x->high&&
/* walk x down the tree */
while(x!=RBNULL) {
if (low<x->high&&
return RB_FALSE;
x=rbinfo->rb_root;
return RB_FALSE;
x=rbinfo->rb_root;
/* walk x down the tree */
while(x!=RBNULL) {
if (low<x->high &&
/* walk x down the tree */
while(x!=RBNULL) {
if (low<x->high &&
const void *max;
assert(x!=RBNULL);
assert(x->right!=RBNULL);
const void *max;
assert(x!=RBNULL);
assert(x->right!=RBNULL);
/* Turn Y's left subtree into X's right subtree (move B)*/
x->right = y->left;
/* Turn Y's left subtree into X's right subtree (move B)*/
x->right = y->left;
/* If B is not null, set it's parent to be X */
if (y->left != RBNULL)
y->left->up = x;
/* If B is not null, set it's parent to be X */
if (y->left != RBNULL)
y->left->up = x;
/* Set Y's parent to be what X's parent was */
y->up = x->up;
/* Set Y's parent to be what X's parent was */
y->up = x->up;
/* if X was the root */
if (x->up == RBNULL) {
*rootp=y;
/* if X was the root */
if (x->up == RBNULL) {
*rootp=y;
/* Put X on Y's left */
y->left=x;
/* Put X on Y's left */
y->left=x;
/* Set X's parent to be Y */
x->up = y;
/* Set X's parent to be Y */
x->up = y;
y->max=x->max; /* compute Y's max */
max=NULL;
y->max=x->max; /* compute Y's max */
max=NULL;
if (x->left!=RBNULL)
max=x->left->max;
if (x->left!=RBNULL)
max=x->left->max;
if (x->right!=RBNULL&&
x->right->max>max)
max=x->right->max;
if (x->right!=RBNULL&&
x->right->max>max)
max=x->right->max;
static void rb_right_rotate(struct rbnode **rootp, struct rbnode *y) {
struct rbnode *x;
const void *max;
static void rb_right_rotate(struct rbnode **rootp, struct rbnode *y) {
struct rbnode *x;
const void *max;
assert(y!=RBNULL);
assert(y->left!=RBNULL);
assert(y!=RBNULL);
assert(y->left!=RBNULL);
x=y->left; /* set X */
/* Turn X's right subtree into Y's left subtree (move B) */
y->left = x->right;
x=y->left; /* set X */
/* Turn X's right subtree into Y's left subtree (move B) */
y->left = x->right;
/* If B is not null, set it's parent to be Y */
if (x->right != RBNULL)
x->right->up = y;
/* If B is not null, set it's parent to be Y */
if (x->right != RBNULL)
x->right->up = y;
/* Put Y on X's right */
x->right=y;
/* Put Y on X's right */
x->right=y;
/* Set Y's parent to be X */
y->up = x;
/* Set Y's parent to be X */
y->up = x;
if (y->left!=RBNULL)
max=y->left->max;
if (y->left!=RBNULL)
max=y->left->max;
if (y->right!=RBNULL&&
y->right->max>max)
max=y->right->max;
if (y->right!=RBNULL&&
y->right->max>max)
max=y->right->max;
static void rb_delete(struct rbnode **rootp, struct rbnode *z) {
struct rbnode *x, *y, *tmp;
const void *max;
static void rb_delete(struct rbnode **rootp, struct rbnode *z) {
struct rbnode *x, *y, *tmp;
const void *max;
if (z->left == RBNULL || z->right == RBNULL)
y=z;
else
y=rb_successor(z);
if (z->left == RBNULL || z->right == RBNULL)
y=z;
else
y=rb_successor(z);
if (y->left != RBNULL)
x=y->left;
else
x=y->right;
if (y->left != RBNULL)
x=y->left;
else
x=y->right;
if (y->up == RBNULL) {
*rootp=x;
} else {
if (y->up == RBNULL) {
*rootp=x;
} else {
if (y!=z) {
z->key = y->key;
z->high=y->high;
if (y!=z) {
z->key = y->key;
z->high=y->high;
}
if (y->colour == BLACK)
rb_delete_fix(rootp, x);
}
if (y->colour == BLACK)
rb_delete_fix(rootp, x);
rb_free(y);
}
/* Restore the reb-black properties after a delete */
static void rb_delete_fix(struct rbnode **rootp, struct rbnode *x) {
struct rbnode *w;
rb_free(y);
}
/* Restore the reb-black properties after a delete */
static void rb_delete_fix(struct rbnode **rootp, struct rbnode *x) {
struct rbnode *w;
while (x!=*rootp && x->colour==BLACK) {
if (x==x->up->left) {
w=x->up->right;
while (x!=*rootp && x->colour==BLACK) {
if (x==x->up->left) {
w=x->up->right;
rb_walk(const struct rbnode *x, void (*action)(const void *, const VISIT, const int, void *), void *arg, int level) {
if (x==RBNULL)
return;
rb_walk(const struct rbnode *x, void (*action)(const void *, const VISIT, const int, void *), void *arg, int level) {
if (x==RBNULL)
return;
if (x->left==RBNULL && x->right==RBNULL) {
/* leaf */
(*action)(x->key, leaf, level, arg);
} else {
(*action)(x->key, preorder, level, arg);
if (x->left==RBNULL && x->right==RBNULL) {
/* leaf */
(*action)(x->key, leaf, level, arg);
} else {
(*action)(x->key, preorder, level, arg);
rb_walk(x->left, action, arg, level+1);
rb_walk(x->left, action, arg, level+1);
(*action)(x->key, postorder, level, arg);
rb_walk(x->right, action, arg, level+1);
(*action)(x->key, postorder, level, arg);
rb_walk(x->right, action, arg, level+1);
static RBLIST * rb_openlist(const struct rbnode *rootp) {
RBLIST *rblistp;
static RBLIST * rb_openlist(const struct rbnode *rootp) {
RBLIST *rblistp;
rblistp=(RBLIST *) malloc(sizeof(RBLIST));
if (!rblistp)
return(NULL);
rblistp=(RBLIST *) malloc(sizeof(RBLIST));
if (!rblistp)
return(NULL);
rblistp->rootp=rootp;
rblistp->nextp=rootp;
rblistp->rootp=rootp;
rblistp->nextp=rootp;
if (rootp!=RBNULL) {
while(rblistp->nextp->left!=RBNULL) {
rblistp->nextp=rblistp->nextp->left;
if (rootp!=RBNULL) {
while(rblistp->nextp->left!=RBNULL) {
rblistp->nextp=rblistp->nextp->left;
int rb_check(struct rbnode *rootp) {
if (rootp==NULL || rootp==RBNULL)
return(0);
int rb_check(struct rbnode *rootp) {
if (rootp==NULL || rootp==RBNULL)
return(0);
if (rootp->up!=RBNULL) {
fprintf(stderr, "Root up pointer not RBNULL");
dumptree(rootp, 0);
return(1);
}
if (rootp->up!=RBNULL) {
fprintf(stderr, "Root up pointer not RBNULL");
dumptree(rootp, 0);
return(1);
}
if (rb_check1(rootp)) {
dumptree(rootp, 0);
return(1);
if (rb_check1(rootp)) {
dumptree(rootp, 0);
return(1);
dumptree(rootp, 0);
return(-1);
}
dumptree(rootp, 0);
return(-1);
}
fprintf(stderr, "Left or right is NULL");
return(1);
}
fprintf(stderr, "Left or right is NULL");
return(1);
}
if (x->colour==RED)
{
if (x->left->colour!=BLACK && x->right->colour!=BLACK)
if (x->colour==RED)
{
if (x->left->colour!=BLACK && x->right->colour!=BLACK)
if (x->left != RBNULL)
{
if (x->left->up != x)
if (x->left != RBNULL)
{
if (x->left->up != x)
fprintf(stderr, "x->left->up != x, x=%ld", x);
return(1);
}
fprintf(stderr, "x->left->up != x, x=%ld", x);
return(1);
}
if (rb_check1(x->left))
return(1);
if (rb_check1(x->left))
return(1);
if (x->right != RBNULL)
{
if (x->right->up != x)
if (x->right != RBNULL)
{
if (x->right->up != x)
fprintf(stderr, "x->right->up != x, x=%ld", x);
return(1);
}
fprintf(stderr, "x->right->up != x, x=%ld", x);
return(1);
}
if (rb_check1(x->right))
return(1);
if (rb_check1(x->right))
return(1);
return(0);
}
count_black(struct rbnode *x)
{
int nleft, nright;
return(0);
}
count_black(struct rbnode *x)
{
int nleft, nright;
if (x==RBNULL)
return(1);
if (x==RBNULL)
return(1);
nleft=count_black(x->left);
nright=count_black(x->right);
nleft=count_black(x->left);
nright=count_black(x->right);
if (nleft==-1 || nright==-1)
return(-1);
if (nleft==-1 || nright==-1)
return(-1);
if (nleft != nright)
{
fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
return(-1);
}
if (nleft != nright)
{
fprintf(stderr, "Black count not equal on left & right, x=%ld", x);
return(-1);
}
if (x->colour == BLACK)
{
nleft++;
}
if (x->colour == BLACK)
{
nleft++;
}
return(nleft);
}
dumptree(struct rbnode *x, int n)
{
char *prkey();
return(nleft);
}
dumptree(struct rbnode *x, int n)
{
char *prkey();
if (x!=NULL && x!=RBNULL)
{
n++;
if (x!=NULL && x!=RBNULL)
{
n++;
x->right,
(x->colour==BLACK) ? "BLACK" : "RED",
prkey(x->key));
x->right,
(x->colour==BLACK) ? "BLACK" : "RED",
prkey(x->key));
dumptree(x->left, n);
dumptree(x->right, n);
dumptree(x->left, n);
dumptree(x->right, n);
}
#endif
/*
* $Log: redblack.c,v $
}
#endif
/*
* $Log: redblack.c,v $
+ * Revision 1.2 2004/11/10 05:44:00 bdemsky
+ *
+ *
+ * 1) Fixed some bugs in the redblack tree implementation...removing a non-present node resulted in a segfault.
+ *
+ * 2) Fixed bug in constructbindings method.
+ *
* Revision 1.1 2004/10/28 19:28:59 bdemsky
* Checking in C runtime.
*
* Revision 1.1 2004/10/28 19:28:59 bdemsky
* Checking in C runtime.
*
* Initial import of files. Versions are now all over the place. Oh well
*
*/
* Initial import of files. Versions are now all over the place. Oh well
*
*/
if ((e instanceof VarExpr)&&
(((VarExpr)e).getVar()==vd)) {
/* Can solve for v */
if ((e instanceof VarExpr)&&
(((VarExpr)e).getVar()==vd)) {
/* Can solve for v */
- if (!si.getSet().getType().isSubtypeOf(set.getType()))
+ if (set==null||!si.getSet().getType().isSubtypeOf(set.getType()))
return false;
Binding binding=new Binding(vd,0);
bindings.add(binding);
return false;
Binding binding=new Binding(vd,0);
bindings.add(binding);