# HG changeset patch
# User tuomov
# Date 1078937209 -3600
# Node ID b5352976287492f647b51c0f5815579c96a1c52d
# Parent  42085c134e29505da5acdadf95cef5332c89a37d
trunk: changeset 1370
- Added red-black tree routines for direct pointer comparison.

- Made keys to red-black tree routines const.

diff -r 42085c134e29 -r b53529762874 rb.c
--- a/rb.c	Wed Mar 10 17:33:39 2004 +0100
+++ b/rb.c	Wed Mar 10 17:46:49 2004 +0100
@@ -183,13 +183,13 @@
   return rb_find_ikey_n(n, ikey, &fnd);
 }
  
-Rb_node rb_find_gkey_n(Rb_node n, void *key, Rb_compfn *fxn, int *fnd)
+Rb_node rb_find_gkey_n(Rb_node n, const void *key, Rb_compfn *fxn, int *fnd)
 {
   int cmp;
  
   *fnd = 0;
   if (!ishead(n)) {
-    fprintf(stderr, "rb_find_key_n called on non-head %p\n",
+    fprintf(stderr, "rb_find_gkey_n called on non-head %p\n",
             DONT_COMPLAIN n);
     exit(1);
   }
@@ -212,24 +212,40 @@
   }
 }
  
-Rb_node rb_find_gkey(Rb_node n, void *key, Rb_compfn *fxn)
+Rb_node rb_find_gkey(Rb_node n, const 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)
+Rb_node rb_find_key_n(Rb_node n, const char *key, int *fnd)
 {
   return rb_find_gkey_n(n, key, (Rb_compfn*)strcmp, fnd);
 }
  
-Rb_node rb_find_key(Rb_node n, char *key)
+Rb_node rb_find_key(Rb_node n, const 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)
+static int ptrcmp(const void *a, const void *b)
+{
+    return (a<b ? -1 : ((a==b) ? 0 : 1));
+}
+
+Rb_node rb_find_pkey_n(Rb_node n, const void *key, int *fnd)
+{
+  return rb_find_gkey_n(n, key, ptrcmp, fnd);
+}
+ 
+Rb_node rb_find_pkey(Rb_node n, const void *key)
+{
+  int fnd;
+  return rb_find_gkey_n(n, key, ptrcmp, &fnd);
+}
+
+Rb_node rb_insert_b(Rb_node n, const void *key, void *val)
 {
   Rb_node newleft, newright, newnode, list, p;
  
@@ -581,12 +597,12 @@
   return n->v.val;
 }
  
-Rb_node rb_insert_a(Rb_node nd, void *key, void *val)
+Rb_node rb_insert_a(Rb_node nd, const void *key, void *val)
 {
   return rb_insert_b(nd->c.list.flink, key, val);
 }
 
-Rb_node rb_insert(Rb_node tree, char *key, void *val)
+Rb_node rb_insert(Rb_node tree, const char *key, void *val)
 {
   return rb_insert_b(rb_find_key(tree, key), key, val);
 }
@@ -596,9 +612,14 @@
   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)
+Rb_node rb_insertg(Rb_node tree, const void *key, void *val, Rb_compfn *func)
 {
   return rb_insert_b(rb_find_gkey(tree, key, func), key, val);
 }
 
+Rb_node rb_insertp(Rb_node tree, const void *key, void *val)
+{
+  return rb_insertg(tree, key, val, ptrcmp);
+}
 
+
diff -r 42085c134e29 -r b53529762874 rb.h
--- a/rb.h	Wed Mar 10 17:33:39 2004 +0100
+++ b/rb.h	Wed Mar 10 17:46:49 2004 +0100
@@ -58,7 +58,7 @@
   Rb_status s;
   union {
     int ikey;
-    void *key;
+    const void *key;
     struct rb_node *lext;
   } k;
   union {
@@ -68,7 +68,7 @@
 } *Rb_node;
 
 
-typedef int Rb_compfn(void *, void *);
+typedef int Rb_compfn(const void *, const void *);
 
 
 extern Rb_node make_rb();   /* Creates a new rb-tree */
@@ -77,33 +77,38 @@
    rb_insert uses strcmp() as comparison funcion.  rb_inserti uses <>=,
    rb_insertg uses func() */
 
-extern Rb_node rb_insert(Rb_node tree, char *key, void *val);
+extern Rb_node rb_insert(Rb_node tree, const 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);
+extern Rb_node rb_insertp(Rb_node tree, const void *key, void *val);
+extern Rb_node rb_insertg(Rb_node tree, const void *key, void *val, 
+                          Rb_compfn *func);
 
 
 /* returns an external node in t whose value is equal
   k or whose value is the smallest value greater than k. */
 
-extern Rb_node rb_find_key(Rb_node root, char *key);
+extern Rb_node rb_find_key(Rb_node root, const char *key);
 extern Rb_node rb_find_ikey(Rb_node root, int ikey);
-extern Rb_node rb_find_gkey(Rb_node root, void *key, Rb_compfn *func);
+extern Rb_node rb_find_pkey(Rb_node root, const void *key);
+extern Rb_node rb_find_gkey(Rb_node root, const void *key, Rb_compfn *func);
 
 
 /* Works just like the find_key versions only it returns whether or not
    it found the key in the integer variable found */
 
-extern Rb_node rb_find_key_n(Rb_node root, char *key, int *found);
+extern Rb_node rb_find_key_n(Rb_node root, const 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, void *key, Rb_compfn *func, int *found);
+extern Rb_node rb_find_pkey_n(Rb_node root, const void *key, int *found);
+extern Rb_node rb_find_gkey_n(Rb_node root, const 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, void *key, void *val);
-extern Rb_node rb_insert_a(Rb_node nd, void *key, void *val);
+extern Rb_node rb_insert_b(Rb_node nd, const void *key, void *val);
+extern Rb_node rb_insert_a(Rb_node nd, const void *key, void *val);
 
 
 extern void rb_delete_node(Rb_node node);  /* Deletes and frees a node (but