Wed, 10 Mar 2004 17:33:39 +0100
trunk: changeset 1369
Fixed some issues with the ripped red-black tree code (compiler printf
warnings, type safety, check of malloc result).
rb.c | file | annotate | diff | comparison | revisions | |
rb.h | file | annotate | diff | comparison | revisions |
--- 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); }
--- a/rb.h Wed Mar 10 17:08:26 2004 +0100 +++ b/rb.h Wed Mar 10 17:33:39 2004 +0100 @@ -22,13 +22,13 @@ /* Original code by Jim Plank (plank@cs.utk.edu) */ /* modified for THINK C 6.0 for Macintosh by Chris Bartley */ -typedef struct { +typedef struct rb_status { unsigned red : 1 ; unsigned internal : 1 ; unsigned left : 1 ; unsigned root : 1 ; unsigned head : 1 ; -} status; +} Rb_status; /* Main rb_node. You only ever use the fields @@ -55,31 +55,31 @@ struct rb_node *parent; struct rb_node *root; } p; - status s; + Rb_status s; union { int ikey; - char *key; + void *key; struct rb_node *lext; } k; union { - char *val; + void *val; struct rb_node *rext; } v; } *Rb_node; -extern Rb_node make_rb(); /* Creates a new rb-tree */ +typedef int Rb_compfn(void *, void *); +extern Rb_node make_rb(); /* Creates a new rb-tree */ /* Creates a node with key key and val val and inserts it into the tree. rb_insert uses strcmp() as comparison funcion. rb_inserti uses <>=, rb_insertg uses func() */ -extern Rb_node rb_insert(Rb_node tree, char *key, char *val); -extern Rb_node rb_inserti(Rb_node tree, int ikey, char *val); -extern Rb_node rb_insertg(Rb_node tree, char *key, char *val, - int (*func)(char *, char *)); +extern Rb_node rb_insert(Rb_node tree, char *key, void *val); +extern Rb_node rb_inserti(Rb_node tree, int ikey, void *val); +extern Rb_node rb_insertg(Rb_node tree, void *key, void *val, Rb_compfn *func); /* returns an external node in t whose value is equal @@ -87,8 +87,7 @@ extern Rb_node rb_find_key(Rb_node root, char *key); extern Rb_node rb_find_ikey(Rb_node root, int ikey); -extern Rb_node rb_find_gkey(Rb_node root, char *key, - int (*func)(char *, char *)); +extern Rb_node rb_find_gkey(Rb_node root, void *key, Rb_compfn *func); /* Works just like the find_key versions only it returns whether or not @@ -96,23 +95,22 @@ extern Rb_node rb_find_key_n(Rb_node root, char *key, int *found); extern Rb_node rb_find_ikey_n(Rb_node root, int ikey, int *found); -extern Rb_node rb_find_gkey_n(Rb_node root, char *key, - int (*func)(char *, char *), int *found); +extern Rb_node rb_find_gkey_n(Rb_node root, void *key, Rb_compfn *func, int *found); /* Creates a node with key key and val val and inserts it into the tree before/after node nd. Does not check to ensure that you are keeping the correct order */ -extern Rb_node rb_insert_b(Rb_node nd, char *key, char *val); -extern Rb_node rb_insert_a(Rb_node nd, char *key, char *val); +extern Rb_node rb_insert_b(Rb_node nd, void *key, void *val); +extern Rb_node rb_insert_a(Rb_node nd, void *key, void *val); extern void rb_delete_node(Rb_node node); /* Deletes and frees a node (but not the key or val) */ extern void rb_free_tree(Rb_node root); /* Deletes and frees an entire tree */ -extern char *rb_val(Rb_node node); /* Returns node->v.val -- this is to shut +extern void *rb_val(Rb_node node); /* Returns node->v.val -- this is to shut lint up */ extern int rb_nblack(Rb_node n); /* returns # of black nodes in path from