1 /* $NetBSD: tsearch-test.c,v 1.2 2017/01/28 21:31:50 christos Exp $ */
2
3 /*
4 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
5 * the AT&T man page says.
6 *
7 * The node_t structure is for internal use only, lint doesn't grok it.
8 *
9 * Written by reading the System V Interface Definition, not the code.
10 *
11 * Totally public domain.
12 */
13
14 #include <config.h>
15
16 #include <krb5/roken.h>
17 #include "search.h"
18
19 struct node {
20 char *string;
21 int order;
22 };
23
24 extern void *rk_tdelete(const void *, void **,
25 int (*)(const void *, const void *));
26 extern void *rk_tfind(const void *, void * const *,
27 int (*)(const void *, const void *));
28 extern void *rk_tsearch(const void *, void **, int (*)(const void *, const void *));
29 extern void rk_twalk(const void *, void (*)(const void *, VISIT, int));
30
31 void *rootnode = NULL;
32 int numerr = 0;
33
34 /*
35 * This routine compares two nodes, based on an
36 * alphabetical ordering of the string field.
37 */
38 int
node_compare(const void * node1,const void * node2)39 node_compare(const void *node1, const void *node2)
40 {
41 return strcmp(((const struct node *) node1)->string,
42 ((const struct node *) node2)->string);
43 }
44
45 static int walkorder = -1;
46
47 void
list_node(const void * ptr,VISIT order,int level)48 list_node(const void *ptr, VISIT order, int level)
49 {
50 const struct node *p = *(const struct node **) ptr;
51
52 if (order == postorder || order == leaf) {
53 walkorder++;
54 if (p->order != walkorder) {
55 warnx("sort failed: expected %d next, got %d\n", walkorder,
56 p->order);
57 numerr++;
58 }
59 }
60 }
61
62 int
main(int argc,char ** argv)63 main(int argc, char **argv)
64 {
65 int numtest = 1;
66 struct node *t, *p, tests[] = {
67 { "", 0 },
68 { "ab", 3 },
69 { "abc", 4 },
70 { "abcdefg", 8 },
71 { "abcd", 5 },
72 { "a", 2 },
73 { "abcdef", 7 },
74 { "abcde", 6 },
75 { "=", 1 },
76 { NULL }
77 };
78
79 for(t = tests; t->string; t++) {
80 /* Better not be there */
81 p = (struct node *)rk_tfind((void *)t, (void **)&rootnode,
82 node_compare);
83
84 if (p) {
85 warnx("erroneous list: found %d\n", p->order);
86 numerr++;
87 }
88
89 /* Put node into the tree. */
90 p = (struct node *) rk_tsearch((void *)t, (void **)&rootnode,
91 node_compare);
92
93 if (!p) {
94 warnx("erroneous list: missing %d\n", t->order);
95 numerr++;
96 }
97 }
98
99 rk_twalk(rootnode, list_node);
100
101 for(t = tests; t->string; t++) {
102 /* Better be there */
103 p = (struct node *) rk_tfind((void *)t, (void **)&rootnode,
104 node_compare);
105
106 if (!p) {
107 warnx("erroneous list: missing %d\n", t->order);
108 numerr++;
109 }
110
111 /* pull out node */
112 (void) rk_tdelete((void *)t, (void **)&rootnode,
113 node_compare);
114
115 /* Better not be there */
116 p = (struct node *) rk_tfind((void *)t, (void **)&rootnode,
117 node_compare);
118
119 if (p) {
120 warnx("erroneous list: found %d\n", p->order);
121 numerr++;
122 }
123
124 }
125
126 return numerr;
127 }
128