Wed, 10 Mar 2004 17:46:49 +0100
trunk: changeset 1370
- Added red-black tree routines for direct pointer comparison.
- Made keys to red-black tree routines const.
rb.c | file | annotate | diff | comparison | revisions | |
rb.h | file | annotate | diff | comparison | revisions |
--- 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); +} +
--- 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