1 #ifndef _XOPEN_SOURCE
2 #define _XOPEN_SOURCE 700
3 #endif
4 #include <stdlib.h>
5 #include <string.h>
6 #include <search.h>
7 #include "test.h"
8
9 struct e {
10 char *k;
11 int v;
12 };
13
14 static int count;
15 static void *root;
16 static struct e tab[100];
17 static struct e *cur = tab;
18
cmp(const void * a,const void * b)19 static int cmp(const void *a, const void *b)
20 {
21 return strcmp(((struct e*)a)->k, ((struct e*)b)->k);
22 }
23
24 static int wantc = 'a';
act(const void * node,VISIT v,int d)25 static void act(const void *node, VISIT v, int d)
26 {
27 struct e *e = *(void**)node;
28
29 if (v == preorder)
30 if (e->k[0] < wantc)
31 t_error("preorder visited node \"%s\" before \"%c\"\n", e->k, wantc);
32 if (v == endorder)
33 if (e->k[0] > wantc)
34 t_error("endorder visited node \"%s\" after \"%c\"\n", e->k, wantc);
35 if (v == postorder)
36 if (e->k[0] != wantc)
37 t_error("postorder visited node \"%s\", wanted \"%c\"\n", e->k, wantc);
38 if (v == leaf)
39 if (e->k[0] != wantc)
40 t_error("visited leaf node \"%s\", wanted \"%c\"\n", e->k, wantc);
41 if (v == postorder || v == leaf)
42 wantc++;
43 }
44
45 static const void *parent;
46 static char *searchkey;
getparent(const void * node,VISIT v,int d)47 static void getparent(const void *node, VISIT v, int d)
48 {
49 static const void *p;
50 struct e *e = *(void**)node;
51
52 if (v == preorder || v == leaf)
53 if (strcmp(searchkey, e->k) == 0)
54 parent = p;
55 if (v == preorder || v == postorder)
56 p = node;
57 }
58
get(char * k)59 struct e *get(char *k)
60 {
61 void **p = tfind(&(struct e){.k = k}, &root, cmp);
62 if (!p) return 0;
63 return *p;
64 }
65
set(char * k,int v)66 struct e *set(char *k, int v)
67 {
68 void **p;
69 cur->k = k;
70 cur->v = v;
71 if (!get(k))
72 count++;
73 p = tsearch(cur++, &root, cmp);
74 if (!p || strcmp(((struct e*)*p)->k, k) != 0)
75 t_error("tsearch %s %d failed\n", k, v);
76 if (!p) {
77 count--;
78 return 0;
79 }
80 return *p;
81 }
82
del(char * k)83 void *del(char *k)
84 {
85 void *p = tdelete(&(struct e){.k = k}, &root, cmp);
86 if (p)
87 count--;
88 return p;
89 }
90
main()91 int main() {
92 struct e *e;
93 void *p;
94
95 set("f", 6);
96 set("b", 2);
97 set("c", 3);
98 set("e", 5);
99 set("h", 8);
100 set("g", 7);
101 set("a", 1);
102 set("d", 4);
103
104 e = get("a");
105 if (!e || e->v != 1)
106 t_error("tfind a failed\n");
107 if (get("z"))
108 t_error("tfind z should fail\n");
109 e = set("g", 9);
110 if (e && e->v != 7)
111 t_error("tsearch g 9 returned data %d, wanted 7\n", e->v);
112 e = set("g", 9);
113 if (e && e->v != 7)
114 t_error("tsearch g 9 returned data %d, wanted 7\n", e->v);
115 e = set("i", 9);
116 if (e && e->v != 9)
117 t_error("tsearch i 9 returned data %d, wanted 9\n", e->v);
118 if (del("foobar"))
119 t_error("tdelete foobar should fail\n");
120
121 twalk(root, act);
122 if (wantc!='j')
123 t_error("twalk did not visit all nodes (wanted 'j' got '%c')\n", wantc);
124 searchkey = "h";
125 twalk(root, getparent);
126 if (parent == 0)
127 t_error("twalk search for key \"%s\" failed\n", searchkey);
128 p = del("h");
129 if (p != parent)
130 t_error("tdelete h failed to return parent (got %p wanted %p)\n", p, parent);
131
132 e = *(void**)root;
133 if (!del(e->k))
134 t_error("tdelete root \"%s\" failed (returned 0)\n", e->k);
135
136 for (; count; count--) {
137 e = *(void**)root;
138 if (!tdelete(e, &root, cmp))
139 t_error("tdelete k=%s failed during destruction\n", e->k);
140 }
141 if (root)
142 t_error("tree destruction failed: root is nonzero %p\n", root);
143
144 return t_status;
145 }
146