Mercurial > repos > libtu-3 / changeset

--- 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