From 432bbb4e4a356c932af22f146e3ba2fb763059e4 Mon Sep 17 00:00:00 2001 From: Not Zed Date: Sun, 10 May 2020 08:21:14 +0930 Subject: [PATCH] Made the interface a bit more sane. init takes and saves the comparator scan_init renamed to scan_init_key and takes scan direction scan_init simpler default interface for full scans scan_next goes in the natural scan direction scan_prev added to go in the opposite --- ez-tree.c | 112 ++++++++++++++++++++++++++++++---------------------- ez-tree.h | 69 ++++++++++++++++++++++---------- test-tree.c | 70 +++++++++++++++++--------------- 3 files changed, 152 insertions(+), 99 deletions(-) diff --git a/ez-tree.c b/ez-tree.c index 6b2482a..ee6d390 100644 --- a/ez-tree.c +++ b/ez-tree.c @@ -111,7 +111,7 @@ static __inline__ void node_set_link(struct ez_node *n, int i, struct ez_node *l static struct ez_node *node_rotate_single(struct ez_node * __restrict s, struct ez_node * __restrict r, int ai, int a) { node_set_link(s, ai, node_link(r, ai ^ 1)); node_set_link(r, ai ^ 1, s); - + node_set_balance(s, -a); node_set_balance(r, +a); @@ -132,7 +132,7 @@ static struct ez_node *node_rotate_single(struct ez_node * __restrict s, struct static struct ez_node *node_rotate_double(struct ez_node *s, struct ez_node *r, int ai, int a) { struct ez_node *p = node_link(r, ai ^ 1); int pb = node_balance(p); - + node_set_link(r, ai ^ 1, node_link(p, ai)); node_set_link(p, ai, r); node_set_link(s, ai, node_link(p, ai ^ 1)); @@ -225,7 +225,7 @@ static void node_remove(struct ez_tree_scan_info *stack, struct ez_tree_scan_inf if (xb == 0) break; } - + si -= 1; } @@ -250,19 +250,22 @@ static void tree_free(ez_tree *tree, struct ez_node *n, ez_free_fn node_free) { /* ********************************************************************** */ -void ez_tree_init(struct ez_tree *t) { - t->root.u.tree.link[0] = 0; - t->root.u.tree.link[1] = 0; +void ez_tree_init(struct ez_tree *tree, ez_cmp_fn node_cmp) { + tree->root.u.tree.link[0] = 0; + tree->root.u.tree.link[1] = 0; + tree->node_cmp = node_cmp; } void ez_tree_clear(ez_tree *tree, ez_free_fn node_free) { tree_free(tree, ez_tree_root(tree), node_free); - ez_tree_init(tree); + tree->root.u.tree.link[0] = 0; + tree->root.u.tree.link[1] = 0; } -void *ez_tree_get(ez_tree *tree, ez_cmp_fn node_cmp, const void *node) { +void *ez_tree_get(ez_tree *tree, const void *node) { const struct ez_node *k = node; struct ez_node *p = ez_tree_root(tree); + ez_cmp_fn node_cmp = tree->node_cmp; while (p) { int cmp = node_cmp(k, p); @@ -276,10 +279,11 @@ void *ez_tree_get(ez_tree *tree, ez_cmp_fn node_cmp, const void *node) { return p; } -void *ez_tree_put(ez_tree *tree, ez_cmp_fn node_cmp, void *node) { +void *ez_tree_put(ez_tree *tree, void *node) { struct ez_node *k = node; struct ez_tree_scan_info stack[EZ_TREE_MAX_DEPTH]; struct ez_tree_scan_info *sp = stack, *se = sp + EZ_TREE_MAX_DEPTH - 1; + ez_cmp_fn node_cmp = tree->node_cmp; k->u.tree.link[0] = BALANCE0; // balance=0 node_set_link(k, 1, 0); @@ -311,7 +315,7 @@ void *ez_tree_put(ez_tree *tree, ez_cmp_fn node_cmp, void *node) { // Matched, replace and return old node if (cmp == 0) { node_set_link(sp[-2].node, sp[-2].link, k); - *k = *p; + *k = *p; return p; } @@ -323,21 +327,21 @@ void *ez_tree_put(ez_tree *tree, ez_cmp_fn node_cmp, void *node) { // Fix balance factors between s and q for (struct ez_tree_scan_info *pi = si+1;pi != sp; pi+=1) node_set_balance(pi->node, pi->link * 2 - 1); - + // Balance struct ez_node *s = si[0].node; struct ez_node *r = si[1].node; int ai = si->link; int a = ai * 2 - 1; // map 0,1 to -1,+1 int balance = node_balance(s); - + if (balance == 0) { node_set_balance(s, a); } else if (balance == -a) { node_set_balance(s, 0); } else { struct ez_node *q; - + if (node_balance(r) == a) q = node_rotate_single(s, r, ai, 0); else @@ -349,11 +353,12 @@ void *ez_tree_put(ez_tree *tree, ez_cmp_fn node_cmp, void *node) { return NULL; } -void *ez_tree_remove(ez_tree *tree, ez_cmp_fn node_cmp, const void *key) { +void *ez_tree_remove(ez_tree *tree, const void *key) { struct ez_node *p = ez_node_right(&tree->root); struct ez_node *n = p; struct ez_tree_scan_info stack[EZ_TREE_MAX_DEPTH]; struct ez_tree_scan_info *sp = stack, *se = sp + EZ_TREE_MAX_DEPTH; + ez_cmp_fn node_cmp = tree->node_cmp; int cmp = 1; *sp++ = (struct ez_tree_scan_info) { &tree->root, 1 }; @@ -372,13 +377,40 @@ void *ez_tree_remove(ez_tree *tree, ez_cmp_fn node_cmp, const void *key) { return p; } -void *ez_tree_scan_init(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t dir, ez_cmp_fn node_cmp, void *key) { +static void *ez_tree_scan_dir(ez_tree_scan *scan, enum ez_node_link_t dir) { + int l = scan->level; + int nir = dir ^ 1; + struct ez_node *p = scan->stack[l-1].node; + struct ez_node *r = node_link(p, dir); + + if (r) { + scan->stack[l-1].link = dir; + do { + if (l >= EZ_TREE_MAX_DEPTH) + return fail_depth(); + scan->stack[l++] = (struct ez_tree_scan_info) { r, nir }; + r = node_link(r, nir); + } while (r); + scan->level = l; + return scan->stack[l-1].node; + } else { + while (l > 2 && scan->stack[l-2].link == dir) + l--; + scan->level = l - 1; + if (l > 2) + return scan->stack[l-2].node; + return NULL; + } +} + +void *ez_tree_scan_init_key(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t scan_dir, enum ez_node_link_t key_dir, void *key) { struct ez_node *p = ez_node_right(&tree->root); + ez_cmp_fn node_cmp = tree->node_cmp; int l = 0; int cmp = 1; scan->tree = tree; - scan->node_cmp = node_cmp; + scan->scan_dir = scan_dir; scan->stack[l++] = (struct ez_tree_scan_info) { &tree->root, 1 }; if (key) { @@ -393,8 +425,8 @@ void *ez_tree_scan_init(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t d while (p) { if (l >= EZ_TREE_MAX_DEPTH) return fail_depth(); - scan->stack[l++] = (struct ez_tree_scan_info) { p, dir }; - p = ez_node_link(p, dir); + scan->stack[l++] = (struct ez_tree_scan_info) { p, 1 - scan_dir }; + p = ez_node_link(p, 1 - scan_dir); } } scan->level = l; @@ -402,61 +434,47 @@ void *ez_tree_scan_init(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t d if (l > 1) { if (key) { int c = (cmp > 0) - (cmp < 0); // -1 0 1 from compare - int a = dir * 2 - 1; // -1 x 1 from direction + int a = key_dir * 2 - 1; // -1 x 1 from direction if (c == a) - return ez_tree_scan_next(scan, dir); + return ez_tree_scan_dir(scan, key_dir); // same as: //if ((cmp < 0 && dir == EZ_LINK_LEFT) // || (cmp > 0 && dir == EZ_LINK_RIGHT)) // return ez_tree_scan_next(scan, dir); } - + return scan->stack[l-1].node; } else return NULL; } -void *ez_tree_scan_next(ez_tree_scan *scan, enum ez_node_link_t dir) { - int l = scan->level; - int nir = dir ^ 1; - struct ez_node *p = scan->stack[l-1].node; - struct ez_node *r = node_link(p, dir); +void *ez_tree_scan_init(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t scan_dir) { + return ez_tree_scan_init_key(tree, scan, scan_dir, 1 - scan_dir, NULL); +} - if (r) { - scan->stack[l-1].link = dir; - do { - if (l >= EZ_TREE_MAX_DEPTH) - return fail_depth(); - scan->stack[l++] = (struct ez_tree_scan_info) { r, nir }; - r = node_link(r, nir); - } while (r); - scan->level = l; - return scan->stack[l-1].node; - } else { - while (l > 2 && scan->stack[l-2].link == dir) - l--; - scan->level = l - 1; - if (l > 2) - return scan->stack[l-2].node; - return NULL; - } +void *ez_tree_scan_next(ez_tree_scan *scan) { + return ez_tree_scan_dir(scan, scan->scan_dir); +} + +void *ez_tree_scan_prev(ez_tree_scan *scan) { + return ez_tree_scan_dir(scan, 1 - scan->scan_dir); } void *ez_tree_scan_remove(ez_tree_scan *scan, enum ez_node_link_t dir) { int l = scan->level; struct ez_tree_scan_info *sp = scan->stack + l; - + if (l > 1) { struct ez_node *last = sp[-1].node; - + node_remove(scan->stack, sp); // If node_remove could maintain the stack or indicate when it // is still valid this could be avoided, but its messy. if (dir != -1) - return ez_tree_scan_init(scan->tree, scan, dir, scan->node_cmp, last); + return ez_tree_scan_init_key(scan->tree, scan, scan->scan_dir, dir, last); } return NULL; } diff --git a/ez-tree.h b/ez-tree.h index 327d65f..dbe51d3 100644 --- a/ez-tree.h +++ b/ez-tree.h @@ -32,14 +32,15 @@ typedef struct ez_tree ez_tree; */ struct ez_tree { ez_node root; + ez_cmp_fn node_cmp; }; /** * Static initialiser for a tree. * - * struct ez_tree tree = EZ_INIT_TREE(tree); + * struct ez_tree tree = EZ_INIT_TREE(tree, cmp); */ -#define EZ_INIT_TREE(t) { .root.u.tree.link[0] = 0, .root.u.tree.link[1] = 0 } +#define EZ_INIT_TREE(t, cmp) { .root.u.tree.link[0] = 0, .root.u.tree.link[1] = 0, .node_cmp = cmp } typedef struct ez_tree_scan ez_tree_scan; @@ -63,8 +64,8 @@ struct ez_tree_scan_info { */ struct ez_tree_scan { ez_tree *tree; - ez_cmp_fn node_cmp; int level; + int scan_dir; struct ez_tree_scan_info stack[EZ_TREE_MAX_DEPTH]; }; @@ -75,8 +76,9 @@ struct ez_tree_scan { * member. * * @param tree tree to initialise. + * @param cmp node comparison function for this tree. */ -void ez_tree_init(struct ez_tree *tree); +void ez_tree_init(struct ez_tree *tree, ez_cmp_fn cmp); /** * Number of nodes in tree. @@ -93,11 +95,19 @@ static __inline__ void *ez_tree_root(ez_tree *tree) { return (void *)tree->root.u.tree.link[1]; } +/** + * Determine if the tree is empty. + */ +static __inline__ int ez_tree_empty(ez_tree *tree) { + return !tree->root.u.tree.link[1]; +} + /** * Remove all nodes from a tree. * * This will be substantially quicker than removing all nodes - * as there is no need to maintain the tree balance incrementally. + * individually as there is no need to maintain the tree balance + * incrementally. * * Any nodes are freed using the node_free function. * @@ -110,23 +120,21 @@ void ez_tree_clear(ez_tree *tree, ez_free_fn node_free); * Retrieve an item by key. * * @param tree - * @param node_cmp node compare function. * @param key_node is of the same type as the entires in the tree but * only needs to contain enough valid fields for node_cmp to function. * @return an exact match for the key or NULL if no such key exists. */ -void *ez_tree_get(ez_tree *tree, ez_cmp_fn node_cmp, const void *key_node); +void *ez_tree_get(ez_tree *tree, const void *key_node); /** * Put a new item into the tree. This will replace any existing * item which matches. * * @param tree - * @param node_cmp node compare function. * @param node a data node. The type must start with an ez_node. * @return the previous node which matches the same key. */ -void *ez_tree_put(ez_tree *tree, ez_cmp_fn node_cmp, void *node); +void *ez_tree_put(ez_tree *tree, void *node); /** * Remove an item from the tree by key. @@ -136,7 +144,7 @@ void *ez_tree_put(ez_tree *tree, ez_cmp_fn node_cmp, void *node); * @param key_node node who's quality indicates a match. * @return a node matching key_node, or NULL if no such node exists. */ -void *ez_tree_remove(ez_tree *tree, ez_cmp_fn node_cmp, const void *key_node); +void *ez_tree_remove(ez_tree *tree, const void *key_node); /** * Initialise tree scanner for walking the tree in order. @@ -158,23 +166,41 @@ void *ez_tree_remove(ez_tree *tree, ez_cmp_fn node_cmp, const void *key_node); * is being used outside of the scanner functions. * * @param tree initialised tree. - * @param scan (un)initialised scan state. - * @param dir Direction to initialise in. - * @param node_cmp Node compare function. Must be supplised if - * key_node is supplied, or if ez_tree_scan_remove() is called with a - * valid direction. - * @param key_node optional key node. + * @param scan (un)initialised scan state. This function will initialise it. + * @param scan_dir Direction of scan. + * @param key_dir Direction to initialise in. + * @param key_node optional key node for starting point. * @return The found node if any is returned. */ -void *ez_tree_scan_init(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t dir, ez_cmp_fn node_cmp, void *key_node); +void *ez_tree_scan_init_key(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t scan_dir, enum ez_node_link_t key_dir, void *key_node); + + +/** + * Initialise tree scanner for walking tree in order from an end. + * + * This is equivalent of: + * ez_tree_scan_init_key(tree, scan, dir, 1-dir, NULL); + * @param tree initialised tree. + * @param scan (un)initialised scan state. This function will initialise it. + * @param scan_dir Direction of scan. + */ +void *ez_tree_scan_init(ez_tree *tree, ez_tree_scan *scan, enum ez_node_link_t scan_dir); + +/** + * Move to the next node in the tree in scan order. + * + * @param scan initialsied scan state. + * @return the next node, or NULL if the boundaries have been reached. + */ +void *ez_tree_scan_next(ez_tree_scan *scan); /** - * Move to the next node in the tree. + * Move to the previous node in the tree in scan order. * - * @param dir The direction to move in. + * @param scan initialsied scan state. * @return the next node, or NULL if the boundaries have been reached. */ -void *ez_tree_scan_next(ez_tree_scan *scan, enum ez_node_link_t dir); +void *ez_tree_scan_prev(ez_tree_scan *scan); /** * Remove the current node. @@ -187,6 +213,7 @@ void *ez_tree_scan_next(ez_tree_scan *scan, enum ez_node_link_t dir); * Nodes must not be freed until after they have been removed. * * @param dir The direction to move in next, or -1 to finish the scan. + * @return the next node in the specified direction or NULL if none exist. */ void *ez_tree_scan_remove(ez_tree_scan *scan, enum ez_node_link_t dir); @@ -201,7 +228,9 @@ void *ez_tree_scan_remove(ez_tree_scan *scan, enum ez_node_link_t dir); */ void *ez_tree_scan_put(ez_tree_scan *scan, void *node); +static int ez_tree_empty(ez_tree *tree) __attribute__((always_inline)); static int ez_tree_size(struct ez_tree *tree) __attribute__((always_inline)); static void *ez_tree_root(struct ez_tree *tree) __attribute__((always_inline)); + #endif diff --git a/test-tree.c b/test-tree.c index 768cd44..030937b 100644 --- a/test-tree.c +++ b/test-tree.c @@ -58,24 +58,24 @@ static int count_nodes(struct ez_node *n) { } static void get_none(ez_tree *t, int i) { - struct node k = { .value = i }; - assert(ez_tree_get(t, node_cmp, &k) == NULL); + struct node k = { .value = i }; + assert(ez_tree_get(t, &k) == NULL); } static void get_exists(ez_tree *t, int i) { - struct node k = { .value = i }; + struct node k = { .value = i }; struct node *n; - n = ez_tree_get(t, node_cmp, &k); + n = ez_tree_get(t, &k); assert(n != NULL); assert(n->value == i ); } static void del_exists(ez_tree *t, int i) { - struct node k = { .value = i }; + struct node k = { .value = i }; struct node *n; - n = ez_tree_remove(t, node_cmp, &k); + n = ez_tree_remove(t, &k); assert(n != NULL); assert(n->value == i ); free(n); @@ -86,7 +86,7 @@ static void put_new(ez_tree *t, int i) { n->value =i; - assert(ez_tree_put(t, node_cmp, n) == NULL); + assert(ez_tree_put(t, n) == NULL); } struct word { @@ -114,13 +114,19 @@ static ez_tree *read_words(struct word ***array, int *asize) { int count = 0; ez_tree *tree = malloc(sizeof(*tree)); - ez_tree_init(tree); + ez_tree_init(tree, word_cmp); if (array) { *asize = 16384; *array = malloc((*asize) * sizeof(void *)); } - + + if (!fp) + fp = fopen("words", "r"); + if (!fp) { + printf("test skipped: cannot open /usr/share/dict/words or ./words\n"); + return 0; + } while (fgets(word, 256, fp)) { size_t len = strlen(word); if (len > 0) { @@ -137,8 +143,8 @@ static ez_tree *read_words(struct word ***array, int *asize) { e->index = count; (*array)[count] = e; } - - e = ez_tree_put(tree, word_cmp, e); + + e = ez_tree_put(tree, e); if (e) { printf("duplicate! %s\n", e->word); word_free(e); @@ -160,7 +166,7 @@ void words(void) { assert(count_nodes(ez_tree_root(tree)) == count); assert(count_nodes(ez_tree_root(tree)) == ez_tree_size(tree)); check_balance(ez_tree_root(tree)); - + ez_tree_clear(tree, word_free); free(tree); } @@ -174,12 +180,12 @@ void words2(void) { int seen =0; ez_tree_scan scan; struct word key = { .word = "bullshit" }; - - for (struct word *n = ez_tree_scan_init(t, &scan, EZ_LINK_RIGHT, word_cmp, &key); n && seen < limit; seen++) { + + for (struct word *n = ez_tree_scan_init_key(t, &scan, EZ_LINK_LEFT, EZ_LINK_RIGHT, &key); n && seen < limit; seen++) { struct word *w = n; n = ez_tree_scan_remove(&scan, EZ_LINK_LEFT); - + words[w->index] = NULL; word_free(w); } @@ -193,7 +199,7 @@ void words2(void) { } int main(int argc, char **argv) { - ez_tree tree = EZ_INIT_TREE(tree); + ez_tree tree = EZ_INIT_TREE(tree, node_cmp); ez_tree *t = &tree; get_none(t, 0); @@ -206,7 +212,7 @@ int main(int argc, char **argv) { assert(ez_tree_root(t) != NULL); assert(ez_tree_size(t) == 7); assert(count_nodes(ez_tree_root(t)) == ez_tree_size(t)); - + check_balance(ez_tree_root(t)); for (int i=-10;i<10;i++) { if (i >= 0 && i < 7) @@ -225,7 +231,7 @@ int main(int argc, char **argv) { assert(ez_tree_root(t) != NULL); assert(ez_tree_size(t) == 1027); check_balance(ez_tree_root(t)); - + for (int i=-10;i<1030;i++) { if (i >= 0 && i < 1027) get_exists(t, i); @@ -238,7 +244,7 @@ int main(int argc, char **argv) { int count, c; count = 0; - ez_tree_init(&tree); + ez_tree_init(&tree, node_cmp); for (int i=0;i<1027;i++) { put_new(t, i); count++; @@ -257,7 +263,7 @@ int main(int argc, char **argv) { int j; j = 0; c = 0; - for (struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_LEFT, NULL, NULL); n ; n = ez_tree_scan_next(&scan, EZ_LINK_RIGHT)) { + for (struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_RIGHT); n ; n = ez_tree_scan_next(&scan)) { assert(j == n->value); if (j == 36) j = 301; @@ -269,7 +275,7 @@ int main(int argc, char **argv) { j = 1026; c = 0; - for (struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_RIGHT, NULL, NULL); n ; n = ez_tree_scan_next(&scan, EZ_LINK_LEFT)) { + for (struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_LEFT); n ; n = ez_tree_scan_next(&scan)) { assert(j == n->value); if (j == 301) j = 36; @@ -286,26 +292,26 @@ int main(int argc, char **argv) { } for (int i=0;i<100;i++) { struct node k = { .value = i }; - struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_RIGHT, node_cmp, &k); + struct node *n = ez_tree_scan_init_key(t, &scan, EZ_LINK_LEFT, EZ_LINK_RIGHT, &k); assert(n != NULL); assert(n->value >= i); assert(n->value < i + 7); - } + } for (int i=0;i<100;i++) { struct node k = { .value = i }; - struct node *n = ez_tree_scan_init(t, &scan, EZ_LINK_LEFT, node_cmp, &k); + struct node *n = ez_tree_scan_init_key(t, &scan, EZ_LINK_RIGHT, EZ_LINK_LEFT, &k); assert(n != NULL); assert(n->value <= i); assert(n->value > i - 7); - } + } ez_tree_clear(t, free); // words(); words2(); - + return 0; } @@ -354,7 +360,7 @@ void *ez_tree_removex(ez_tree *tree, const void *key) { #endif // Binary tree remove and adjust balance factors ez_tree_node *r = ez_node_right(p); - + if (!r) { node_set_link(sp[-2].node, sp[-2].link, ez_node_left(p)); sp -= 1; @@ -397,7 +403,7 @@ void *ez_tree_removex(ez_tree *tree, const void *key) { //printf("tree\n"); //dump(tree->root.link[1], 1); #endif - + // Rebalance tree // basic code from libavl but paramterised as in Knuth si = sp-1; @@ -432,7 +438,7 @@ void *ez_tree_removex(ez_tree *tree, const void *key) { #ifdef SPEW printf("w %p [%p %p] balance=%d\n", w, ez_node_left(w), ez_node_right(w), node_balance(w)); fflush(stdout); -#endif +#endif x->link[ai] = node_link(w, aj); w->link[aj] = (intptr_t)x; y->link[aj] = node_link(w, ai); @@ -441,7 +447,7 @@ void *ez_tree_removex(ez_tree *tree, const void *key) { node_set_balance(y, wb == -a ? +a : 0); node_set_balance(x, wb == +a ? -a : 0); node_set_balance(w, 0); - + node_set_link(si[-1].node, si[-1].link, w); } else { // single rotate @@ -458,7 +464,7 @@ void *ez_tree_removex(ez_tree *tree, const void *key) { } } } - + si -= 1; } @@ -470,7 +476,7 @@ void *ez_tree_removex(ez_tree *tree, const void *key) { //} //printf("tree\n"); //dump(tree->root.link[1], 1); - + return p; } -- 2.39.2