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