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