1/*	$NetBSD$	*/
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
19struct node {
20    char *string;
21    int order;
22};
23
24extern void *rk_tdelete(const void * __restrict, void ** __restrict,
25		 int (*)(const void *, const void *));
26extern void *rk_tfind(const void *, void * const *,
27	       int (*)(const void *, const void *));
28extern void *rk_tsearch(const void *, void **, int (*)(const void *, const void *));
29extern void rk_twalk(const void *, void (*)(const void *, VISIT, int));
30
31void *rootnode = NULL;
32int numerr = 0;
33
34/*
35 *  This routine compares two nodes, based on an
36 *  alphabetical ordering of the string field.
37 */
38int
39node_compare(const void *node1, const void *node2)
40{
41    return strcmp(((const struct node *) node1)->string,
42		  ((const struct node *) node2)->string);
43}
44
45static int walkorder = -1;
46
47void
48list_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
62int
63main(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