--- a/rb.c Wed Mar 10 17:08:26 2004 +0100
+++ b/rb.c Wed Mar 10 17:33:39 2004 +0100
@@ -35,6 +35,8 @@
static void rb_print_tree(Rb_node t, int level);
static void rb_iprint_tree(Rb_node t, int level);
+/* Gcc complains if non-char* pointer is passed to printf %p */
+#define DONT_COMPLAIN (char*)
#define isred(n) (n->s.red)
#define isblack(n) (!isred(n))
@@ -76,6 +78,7 @@
#define mk_new_ext(new, kkkey, vvval) {\
new = (Rb_node) malloc(sizeof(struct rb_node));\
+ if(new==NULL) return NULL;\
new->v.val = vvval;\
new->k.key = kkkey;\
setext(new);\
@@ -139,53 +142,22 @@
Rb_node head;
head = (Rb_node) malloc (sizeof(struct rb_node));
- head->c.list.flink = head;
- head->c.list.blink = head;
- head->p.root = head;
- head->k.key = "";
- sethead(head);
- return head;
-}
-
-Rb_node rb_find_key_n(Rb_node n, char *key, int *fnd)
-{
- int cmp;
-
- *fnd = 0;
- if (!ishead(n)) {
- fprintf(stderr, "rb_find_key_n called on non-head 0x%x\n", n);
- exit(1);
+ if(head!=NULL){
+ head->c.list.flink = head;
+ head->c.list.blink = head;
+ head->p.root = head;
+ head->k.key = "";
+ sethead(head);
}
- if (n->p.root == n) return n;
- cmp = strcmp(key, n->c.list.blink->k.key);
- if (cmp == 0) {
- *fnd = 1;
- return n->c.list.blink;
- }
- if (cmp > 0) return n;
- else n = n->p.root;
- while (1) {
- if (isext(n)) return n;
- cmp = strcmp(key, n->k.lext->k.key);
- if (cmp == 0) {
- *fnd = 1;
- return n->k.lext;
- }
- if (cmp < 0) n = n->c.child.left ; else n = n->c.child.right;
- }
-}
-
-Rb_node rb_find_key(Rb_node n, char *key)
-{
- int fnd;
- return rb_find_key_n(n, key, &fnd);
+ return head;
}
Rb_node rb_find_ikey_n(Rb_node n, int ikey, int *fnd)
{
*fnd = 0;
if (!ishead(n)) {
- fprintf(stderr, "rb_find_ikey_n called on non-head 0x%x\n", n);
+ fprintf(stderr, "rb_find_ikey_n called on non-head %p\n",
+ DONT_COMPLAIN n);
exit(1);
}
if (n->p.root == n) return n;
@@ -211,13 +183,14 @@
return rb_find_ikey_n(n, ikey, &fnd);
}
-Rb_node rb_find_gkey_n(Rb_node n, char *key,int (*fxn)(char *, char *), int *fnd)
+Rb_node rb_find_gkey_n(Rb_node n, void *key, Rb_compfn *fxn, int *fnd)
{
int cmp;
*fnd = 0;
if (!ishead(n)) {
- fprintf(stderr, "rb_find_key_n called on non-head 0x%x\n", n);
+ fprintf(stderr, "rb_find_key_n called on non-head %p\n",
+ DONT_COMPLAIN n);
exit(1);
}
if (n->p.root == n) return n;
@@ -239,13 +212,24 @@
}
}
-Rb_node rb_find_gkey(Rb_node n, char *key, int (*fxn)(char *, char *))
+Rb_node rb_find_gkey(Rb_node n, void *key, Rb_compfn *fxn)
{
int fnd;
return rb_find_gkey_n(n, key, fxn, &fnd);
}
+
+Rb_node rb_find_key_n(Rb_node n, char *key, int *fnd)
+{
+ return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, fnd);
+}
-Rb_node rb_insert_b(Rb_node n, char *key, char *val)
+Rb_node rb_find_key(Rb_node n, char *key)
+{
+ int fnd;
+ return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, &fnd);
+}
+
+Rb_node rb_insert_b(Rb_node n, void *key, void *val)
{
Rb_node newleft, newright, newnode, list, p;
@@ -325,9 +309,9 @@
static void single_rotate(Rb_node y, int l)
{
- int rl, ir;
- Rb_node x, yp;
- char *tmp;
+ int rl=0, ir=0;
+ Rb_node x=NULL, yp=NULL;
+ void *tmp=NULL;
ir = isroot(y);
yp = y->p.parent;
@@ -374,11 +358,11 @@
char ir;
if (isint(n)) {
- fprintf(stderr, "Cannot delete an internal node: 0x%x\n", n);
+ fprintf(stderr, "Cannot delete an internal node: %p\n", DONT_COMPLAIN n);
exit(1);
}
if (ishead(n)) {
- fprintf(stderr, "Cannot delete the head of an rb_tree: 0x%x\n", n);
+ fprintf(stderr, "Cannot delete the head of an rb_tree: %p\n", DONT_COMPLAIN n);
exit(1);
}
delete_item(n); /* Delete it from the list */
@@ -494,23 +478,25 @@
{
int i;
if (ishead(t) && t->p.parent == t) {
- printf("tree 0x%x is empty\n", t);
+ printf("tree %p is empty\n", DONT_COMPLAIN t);
} else if (ishead(t)) {
- printf("Head: 0x%x. Root = 0x%x\n", t, t->p.root);
+ printf("Head: %p. Root = %p\n", DONT_COMPLAIN t, DONT_COMPLAIN t->p.root);
rb_print_tree(t->p.root, 0);
} else {
if (isext(t)) {
for (i = 0; i < level; i++) putchar(' ');
- printf("Ext node 0x%x: %c,%c: p=0x%x, k=%s\n",
- t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent, t->k.key);
+ printf("Ext node %p: %c,%c: p=%p, k=%s\n",
+ DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
+ DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->k.key);
} else {
rb_print_tree(t->c.child.left, level+2);
rb_print_tree(t->c.child.right, level+2);
for (i = 0; i < level; i++) putchar(' ');
- printf("Int node 0x%x: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%s,%s)\n",
- t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left,
- t->c.child.right,
- t->p.parent, t->k.lext->k.key, t->v.rext->k.key);
+ printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%s,%s)\n",
+ DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
+ DONT_COMPLAIN t->c.child.left, DONT_COMPLAIN t->c.child.right,
+ DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->k.lext->k.key,
+ DONT_COMPLAIN t->v.rext->k.key);
}
}
}
@@ -519,25 +505,28 @@
{
int i;
if (ishead(t) && t->p.parent == t) {
- printf("tree 0x%x is empty\n", t);
+ printf("tree %p is empty\n", DONT_COMPLAIN t);
} else if (ishead(t)) {
- printf("Head: 0x%x. Root = 0x%x, < = 0x%x, > = 0x%x\n",
- t, t->p.root, t->c.list.blink, t->c.list.flink);
+ printf("Head: %p. Root = %p, < = %p, > = %p\n",
+ DONT_COMPLAIN t, DONT_COMPLAIN t->p.root,
+ DONT_COMPLAIN t->c.list.blink,
+ DONT_COMPLAIN t->c.list.flink);
rb_iprint_tree(t->p.root, 0);
} else {
if (isext(t)) {
for (i = 0; i < level; i++) putchar(' ');
- printf("Ext node 0x%x: %c,%c: p=0x%x, <=0x%x, >=0x%x k=%d\n",
- t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent,
- t->c.list.blink, t->c.list.flink, t->k.ikey);
+ printf("Ext node %p: %c,%c: p=%p, <=%p, >=%p k=%d\n",
+ DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
+ DONT_COMPLAIN t->p.parent, DONT_COMPLAIN t->c.list.blink,
+ DONT_COMPLAIN t->c.list.flink, t->k.ikey);
} else {
rb_iprint_tree(t->c.child.left, level+2);
rb_iprint_tree(t->c.child.right, level+2);
for (i = 0; i < level; i++) putchar(' ');
- printf("Int node 0x%x: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%d,%d)\n",
- t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left,
- t->c.child.right,
- t->p.parent, t->k.lext->k.ikey, t->v.rext->k.ikey);
+ printf("Int node %p: %c,%c: l=%p, r=%p, p=%p, lr=(%d,%d)\n",
+ DONT_COMPLAIN t, isred(t)?'R':'B', isleft(t)?'l':'r',
+ DONT_COMPLAIN t->c.child.left, DONT_COMPLAIN t->c.child.right,
+ DONT_COMPLAIN t->p.parent, t->k.lext->k.ikey, t->v.rext->k.ikey);
}
}
}
@@ -546,8 +535,8 @@
{
int nb;
if (ishead(n) || isint(n)) {
- fprintf(stderr, "ERROR: rb_nblack called on a non-external node 0x%x\n",
- n);
+ fprintf(stderr, "ERROR: rb_nblack called on a non-external node %p\n",
+ DONT_COMPLAIN n);
exit(1);
}
nb = 0;
@@ -562,8 +551,8 @@
{
int pl;
if (ishead(n) || isint(n)) {
- fprintf(stderr, "ERROR: rb_plength called on a non-external node 0x%x\n",
- n);
+ fprintf(stderr, "ERROR: rb_plength called on a non-external node %p\n",
+ DONT_COMPLAIN n);
exit(1);
}
pl = 0;
@@ -587,30 +576,29 @@
free(n);
}
-char *rb_val(Rb_node n)
+void *rb_val(Rb_node n)
{
return n->v.val;
}
-Rb_node rb_insert_a(Rb_node nd, char *key, char *val)
+Rb_node rb_insert_a(Rb_node nd, void *key, void *val)
{
- rb_insert_b(nd->c.list.flink, key, val);
-}
-
-Rb_node rb_insert(Rb_node tree, char *key, char *val)
-{
- rb_insert_b(rb_find_key(tree, key), key, val);
+ return rb_insert_b(nd->c.list.flink, key, val);
}
-Rb_node rb_inserti(Rb_node tree, int ikey, char *val)
+Rb_node rb_insert(Rb_node tree, char *key, void *val)
{
- rb_insert_b(rb_find_ikey(tree, ikey), (char *) ikey, val);
+ return rb_insert_b(rb_find_key(tree, key), key, val);
}
-Rb_node rb_insertg(Rb_node tree, char *key, char *val,
- int (*func)(char *, char *))
+Rb_node rb_inserti(Rb_node tree, int ikey, void *val)
{
- rb_insert_b(rb_find_gkey(tree, key, func), key, val);
+ return rb_insert_b(rb_find_ikey(tree, ikey), (void *) ikey, val);
+}
+
+Rb_node rb_insertg(Rb_node tree, void *key, void *val, Rb_compfn *func)
+{
+ return rb_insert_b(rb_find_gkey(tree, key, func), key, val);
}
