| #ifndef _XOPEN_SOURCE |
| #define _XOPEN_SOURCE 700 |
| #endif |
| #include <stdlib.h> |
| #include <string.h> |
| #include <search.h> |
| #include "test.h" |
| |
| struct e { |
| char *k; |
| int v; |
| }; |
| |
| static int count; |
| static void *root; |
| static struct e tab[100]; |
| static struct e *cur = tab; |
| |
| static int cmp(const void *a, const void *b) |
| { |
| return strcmp(((struct e*)a)->k, ((struct e*)b)->k); |
| } |
| |
| static int wantc = 'a'; |
| static void act(const void *node, VISIT v, int d) |
| { |
| struct e *e = *(void**)node; |
| |
| if (v == preorder) |
| if (e->k[0] < wantc) |
| t_error("preorder visited node \"%s\" before \"%c\"\n", e->k, wantc); |
| if (v == endorder) |
| if (e->k[0] > wantc) |
| t_error("endorder visited node \"%s\" after \"%c\"\n", e->k, wantc); |
| if (v == postorder) |
| if (e->k[0] != wantc) |
| t_error("postorder visited node \"%s\", wanted \"%c\"\n", e->k, wantc); |
| if (v == leaf) |
| if (e->k[0] != wantc) |
| t_error("visited leaf node \"%s\", wanted \"%c\"\n", e->k, wantc); |
| if (v == postorder || v == leaf) |
| wantc++; |
| } |
| |
| static const void *parent; |
| static char *searchkey; |
| static void getparent(const void *node, VISIT v, int d) |
| { |
| static const void *p; |
| struct e *e = *(void**)node; |
| |
| if (v == preorder || v == leaf) |
| if (strcmp(searchkey, e->k) == 0) |
| parent = p; |
| if (v == preorder || v == postorder) |
| p = node; |
| } |
| |
| struct e *get(char *k) |
| { |
| void **p = tfind(&(struct e){.k = k}, &root, cmp); |
| if (!p) return 0; |
| return *p; |
| } |
| |
| struct e *set(char *k, int v) |
| { |
| void **p; |
| cur->k = k; |
| cur->v = v; |
| if (!get(k)) |
| count++; |
| p = tsearch(cur++, &root, cmp); |
| if (!p || strcmp(((struct e*)*p)->k, k) != 0) |
| t_error("tsearch %s %d failed\n", k, v); |
| if (!p) { |
| count--; |
| return 0; |
| } |
| return *p; |
| } |
| |
| void *del(char *k) |
| { |
| void *p = tdelete(&(struct e){.k = k}, &root, cmp); |
| if (p) |
| count--; |
| return p; |
| } |
| |
| int main() { |
| struct e *e; |
| void *p; |
| |
| set("f", 6); |
| set("b", 2); |
| set("c", 3); |
| set("e", 5); |
| set("h", 8); |
| set("g", 7); |
| set("a", 1); |
| set("d", 4); |
| |
| e = get("a"); |
| if (!e || e->v != 1) |
| t_error("tfind a failed\n"); |
| if (get("z")) |
| t_error("tfind z should fail\n"); |
| e = set("g", 9); |
| if (e && e->v != 7) |
| t_error("tsearch g 9 returned data %d, wanted 7\n", e->v); |
| e = set("g", 9); |
| if (e && e->v != 7) |
| t_error("tsearch g 9 returned data %d, wanted 7\n", e->v); |
| e = set("i", 9); |
| if (e && e->v != 9) |
| t_error("tsearch i 9 returned data %d, wanted 9\n", e->v); |
| if (del("foobar")) |
| t_error("tdelete foobar should fail\n"); |
| |
| twalk(root, act); |
| if (wantc!='j') |
| t_error("twalk did not visit all nodes (wanted 'j' got '%c')\n", wantc); |
| searchkey = "h"; |
| twalk(root, getparent); |
| if (parent == 0) |
| t_error("twalk search for key \"%s\" failed\n", searchkey); |
| p = del("h"); |
| if (p != parent) |
| t_error("tdelete h failed to return parent (got %p wanted %p)\n", p, parent); |
| |
| e = *(void**)root; |
| if (!del(e->k)) |
| t_error("tdelete root \"%s\" failed (returned 0)\n", e->k); |
| |
| for (; count; count--) { |
| e = *(void**)root; |
| if (!tdelete(e, &root, cmp)) |
| t_error("tdelete k=%s failed during destruction\n", e->k); |
| } |
| if (root) |
| t_error("tree destruction failed: root is nonzero %p\n", root); |
| |
| return t_status; |
| } |