qi-hardware
/
wernermisc
mirror of git://projects.qi-hardware.com/wernermisc.git
1
0
Fork 0
Code
wernermisc/qpkg/jrb.c

564 lines
10 KiB
C
Raw Permalink Blame History

/*
Libraries for fields, doubly-linked lists and red-black trees.
Copyright (C) 2001 James S. Plank
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
---------------------------------------------------------------------------
Please see http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Libfdr/
for instruction on how to use this library.
Jim Plank
plank@cs.utk.edu
http://www.cs.utk.edu/~plank
Associate Professor
Department of Computer Science
University of Tennessee
203 Claxton Complex
1122 Volunteer Blvd.
Knoxville, TN 37996-3450
865-974-4397
Fax: 865-974-4404
*/
/* Revision 1.2. Jim Plank */
/* Original code by Jim Plank (plank@cs.utk.edu) */
/* modified for THINK C 6.0 for Macintosh by Chris Bartley */
/* Heavily edited and reformatted to K&R style 2010 by Werner Almesberger */
#include <stdio.h>
#include <stdlib.h>
#include "jrb.h"
#define isred(n) (n->red)
#define isblack(n) (!isred(n))
#define isleft(n) (n->left)
#define isright(n) (!isleft(n))
#define isint(n) (n->internal)
#define isext(n) (!isint(n))
#define ishead(n) (n->roothead & 2)
#define isroot(n) (n->roothead & 1)
#define getlext(n) ((struct jrb *) (n->key))
#define setlext(node, val) node->key = (void *) (val)
#define getrext(n) ((struct jrb *) (n->val))
#define setrext(node, value) node->val = (void *) (value)
#define setred(n) n->red = 1
#define setblack(n) n->red = 0
#define setleft(n) n->left = 1
#define setright(n) n->left = 0
#define sethead(n) (n->roothead |= 2)
#define setroot(n) (n->roothead |= 1)
#define setint(n) n->internal = 1
#define setext(n) n->internal = 0
#define setnormal(n) n->roothead = 0
#define sibling(n) (isleft(n) ? n->parent->blink : n->parent->flink)
static void insert(struct jrb *item, struct jrb *list)
/* Inserts to the end of a list */
{
struct jrb *last_node;
last_node = list->blink;
list->blink = item;
last_node->flink = item;
item->blink = last_node;
item->flink = list;
}
static void delete_item(struct jrb *item) /* Deletes an arbitrary iterm */
{
item->flink->blink = item->blink;
item->blink->flink = item->flink;
}
static void single_rotate(struct jrb *y, int l)
{
int rl = 0 /* for gcc */, ir;
struct jrb *x, *yp;
ir = isroot(y);
yp = y->parent;
if (!ir)
rl = isleft(y);
if (l) {
x = y->flink;
y->flink = x->blink;
setleft(y->flink);
y->flink->parent = y;
x->blink = y;
setright(y);
} else {
x = y->blink;
y->blink = x->flink;
setright(y->blink);
y->blink->parent = y;
x->flink = y;
setleft(y);
}
x->parent = yp;
y->parent = x;
if (ir) {
yp->parent = x;
setnormal(y);
setroot(x);
} else {
if (rl) {
yp->flink = x;
setleft(x);
} else {
yp->blink = x;
setright(x);
}
}
}
static void recolor(struct jrb *n)
{
struct jrb *p, *gp, *s;
int done = 0;
while (!done) {
if (isroot(n)) {
setblack(n);
return;
}
p = n->parent;
if (isblack(p))
return;
if (isroot(p)) {
setblack(p);
return;
}
gp = p->parent;
s = sibling(p);
if (isred(s)) {
setblack(p);
setred(gp);
setblack(s);
n = gp;
} else {
done = 1;
}
}
/* p's sibling is black, p is red, gp is black */
if ((isleft(n) == 0) == (isleft(p) == 0)) {
single_rotate(gp, isleft(n));
setblack(p);
setred(gp);
} else {
single_rotate(p, isleft(n));
single_rotate(gp, isleft(n));
setblack(n);
setred(gp);
}
}
static struct jrb *mk_new_ext(void *key, void *val)
{
struct jrb *new;
new = (struct jrb *) malloc(sizeof(struct jrb));
new->val = val;
new->key = key;
setext(new);
setblack(new);
setnormal(new);
return new;
}
static void mk_new_int(struct jrb *l, struct jrb *r, struct jrb *p, int il)
{
struct jrb *newnode;
newnode = (struct jrb *) malloc(sizeof(struct jrb));
setint(newnode);
setred(newnode);
setnormal(newnode);
newnode->flink = l;
newnode->blink = r;
newnode->parent = p;
setlext(newnode, l);
setrext(newnode, r);
l->parent = newnode;
r->parent = newnode;
setleft(l);
setright(r);
if (ishead(p)) {
p->parent = newnode;
setroot(newnode);
} else if (il) {
setleft(newnode);
p->flink = newnode;
} else {
setright(newnode);
p->blink = newnode;
}
recolor(newnode);
}
static struct jrb *lprev(struct jrb *n)
{
if (ishead(n))
return n;
while (!isroot(n)) {
if (isright(n))
return n->parent;
n = n->parent;
}
return n->parent;
}
static struct jrb *rprev(struct jrb *n)
{
if (ishead(n))
return n;
while (!isroot(n)) {
if (isleft(n))
return n->parent;
n = n->parent;
}
return n->parent;
}
struct jrb *make_jrb(void)
{
struct jrb *head;
head = (struct jrb *) malloc(sizeof(struct jrb));
head->flink = head;
head->blink = head;
head->parent = head;
head->key = NULL;
sethead(head);
return head;
}
struct jrb *jrb_find_gte(struct jrb *n, const void *key,
int (*fxn)(const void *, const void *), int *fnd)
{
int cmp;
*fnd = 0;
if (!ishead(n)) {
fprintf(stderr, "jrb_find_gte_str called on non-head %p\n", n);
exit(1);
}
if (n->parent == n)
return n;
cmp = (*fxn)(key, n->blink->key);
if (cmp == 0) {
*fnd = 1;
return n->blink;
}
if (cmp > 0)
return n;
else
n = n->parent;
while (1) {
if (isext(n))
return n;
cmp = (*fxn)(key, getlext(n)->key);
if (cmp == 0) {
*fnd = 1;
return getlext(n);
}
if (cmp < 0)
n = n->flink;
else
n = n->blink;
}
}
struct jrb *jrb_find(struct jrb *n, const void *key,
int (*fxn)(const void *a, const void *b))
{
int fnd;
struct jrb *j;
j = jrb_find_gte(n, key, fxn, &fnd);
if (fnd)
return j;
else
return NULL;
}
static struct jrb *jrb_insert_b(struct jrb *n, void *key, void *val)
{
struct jrb *newleft, *newright, *newnode, *p;
if (ishead(n)) {
if (n->parent == n) { /* Tree is empty */
newnode = mk_new_ext(key, val);
insert(newnode, n);
n->parent = newnode;
newnode->parent = n;
setroot(newnode);
return newnode;
} else {
newright = mk_new_ext(key, val);
insert(newright, n);
newleft = newright->blink;
setnormal(newleft);
mk_new_int(newleft, newright, newleft->parent,
isleft(newleft));
p = rprev(newright);
if (!ishead(p))
setlext(p, newright);
return newright;
}
} else {
newleft = mk_new_ext(key, val);
insert(newleft, n);
setnormal(n);
mk_new_int(newleft, n, n->parent, isleft(n));
p = lprev(newleft);
if (!ishead(p))
setrext(p, newleft);
return newleft;
}
}
void jrb_delete_node(struct jrb *n)
{
struct jrb *s, *p, *gp, *x, *z;
char ir, il;
if (isint(n)) {
fprintf(stderr, "Cannot delete an internal node: %p\n", n);
exit(1);
}
if (ishead(n)) {
fprintf(stderr,
"Cannot delete the head of an jrb_tree: %p\n", n);
exit(1);
}
delete_item(n); /* Delete it from the list */
p = n->parent; /* The only node */
if (isroot(n)) {
p->parent = p;
free(n);
return;
}
s = sibling(n); /* The only node after deletion */
if (isroot(p)) {
s->parent = p->parent;
s->parent->parent = s;
setroot(s);
free(p);
free(n);
return;
}
gp = p->parent; /* Set parent to sibling */
s->parent = gp;
if (isleft(p)) {
gp->flink = s;
setleft(s);
} else {
gp->blink = s;
setright(s);
}
ir = isred(p);
free(p);
free(n);
if (isext(s)) { /* Update proper rext and lext values */
p = lprev(s);
if (!ishead(p))
setrext(p, s);
p = rprev(s);
if (!ishead(p))
setlext(p, s);
} else if (isblack(s)) {
fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
exit(1);
} else {
p = lprev(s);
if (!ishead(p))
setrext(p, s->flink);
p = rprev(s);
if (!ishead(p))
setlext(p, s->blink);
setblack(s);
return;
}
if (ir)
return;
/* Recolor */
n = s;
p = n->parent;
s = sibling(n);
while (isblack(p) && isblack(s) && isint(s) &&
isblack(s->flink) && isblack(s->blink)) {
setred(s);
n = p;
if (isroot(n))
return;
p = n->parent;
s = sibling(n);
}
if (isblack(p) && isred(s)) { /* Rotation 2.3b */
single_rotate(p, isright(n));
setred(p);
setblack(s);
s = sibling(n);
}
if (isext(s)) {
fprintf(stderr, "DELETION ERROR: sibling not internal\n");
exit(1);
}
il = isleft(n);
x = il ? s->flink : s->blink;
z = sibling(x);
if (isred(z)) { /* Rotation 2.3f */
single_rotate(p, !il);
setblack(z);
if (isred(p))
setred(s);
else
setblack(s);
setblack(p);
return;
}
if (isblack(x)) { /* Recoloring only (2.3c) */
if (isred(s) || isblack(p)) {
fprintf(stderr,
"DELETION ERROR: 2.3c not quite right\n");
exit(1);
}
setblack(p);
setred(s);
return;
}
if (isred(p)) { /* 2.3d */
single_rotate(s, il);
single_rotate(p, !il);
setblack(x);
setred(s);
return;
}
/* 2.3e */
single_rotate(s, il);
single_rotate(p, !il);
setblack(x);
}
int jrb_nblack(struct jrb *n)
{
int nb;
if (ishead(n) || isint(n)) {
fprintf(stderr,
"ERROR: jrb_nblack called on a non-external node %p\n", n);
exit(1);
}
nb = 0;
while (!ishead(n)) {
if (isblack(n)) nb++;
n = n->parent;
}
return nb;
}
int jrb_plength(struct jrb *n)
{
int pl;
if (ishead(n) || isint(n)) {
fprintf(stderr,
"ERROR: jrb_plength called on a non-external node %p\n", n);
exit(1);
}
pl = 0;
while (!ishead(n)) {
pl++;
n = n->parent;
}
return pl;
}
void jrb_free_tree(struct jrb *n)
{
if (!ishead(n)) {
fprintf(stderr,
"ERROR: Rb_free_tree called on a non-head node\n");
exit(1);
}
while (jrb_first(n) != jrb_nil(n))
jrb_delete_node(jrb_first(n));
free(n);
}
void *jrb_val(struct jrb *n)
{
return n->val;
}
struct jrb *jrb_insert(struct jrb *tree, void *key, void *val,
int (*func)(const void *a, const void *b))
{
int fnd;
return jrb_insert_b(jrb_find_gte(tree, key, func, &fnd), key, val);
}
struct jrb *jrb_find_or_insert(struct jrb *tree, void *key, void *val,
int (*func)(const void *a, const void *b))
{
struct jrb *n;
int fnd;
n = jrb_find_gte(tree, key, func, &fnd);
return fnd ? n : jrb_insert_b(n, key, val);
}
View Git Blame Copy Permalink