2 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
3 * the AT&T man page says.
5 * The node_t structure is for internal use only, lint doesn't grok it.
7 * Written by reading the System V Interface Definition, not the code.
9 * Totally public domain.
22 extern void *rk_tdelete(const void *, void **,
23 int (*)(const void *, const void *));
24 extern void *rk_tfind(const void *, void * const *,
25 int (*)(const void *, const void *));
26 extern void *rk_tsearch(const void *, void **, int (*)(const void *, const void *));
27 extern void rk_twalk(const void *, void (*)(const void *, VISIT
, int));
29 void *rootnode
= NULL
;
33 * This routine compares two nodes, based on an
34 * alphabetical ordering of the string field.
37 node_compare(const void *node1
, const void *node2
)
39 return strcmp(((const struct node
*) node1
)->string
,
40 ((const struct node
*) node2
)->string
);
43 static int walkorder
= -1;
46 list_node(const void *ptr
, VISIT order
, int level
)
48 const struct node
*p
= *(const struct node
**) ptr
;
50 if (order
== postorder
|| order
== leaf
) {
52 if (p
->order
!= walkorder
) {
53 warnx("sort failed: expected %d next, got %d\n", walkorder
,
61 main(int argc
, char **argv
)
64 struct node
*t
, *p
, tests
[] = {
77 for(t
= tests
; t
->string
; t
++) {
78 /* Better not be there */
79 p
= (struct node
*)rk_tfind((void *)t
, (void **)&rootnode
,
83 warnx("erroneous list: found %d\n", p
->order
);
87 /* Put node into the tree. */
88 p
= (struct node
*) rk_tsearch((void *)t
, (void **)&rootnode
,
92 warnx("erroneous list: missing %d\n", t
->order
);
97 rk_twalk(rootnode
, list_node
);
99 for(t
= tests
; t
->string
; t
++) {
100 /* Better be there */
101 p
= (struct node
*) rk_tfind((void *)t
, (void **)&rootnode
,
105 warnx("erroneous list: missing %d\n", t
->order
);
110 (void) rk_tdelete((void *)t
, (void **)&rootnode
,
113 /* Better not be there */
114 p
= (struct node
*) rk_tfind((void *)t
, (void **)&rootnode
,
118 warnx("erroneous list: found %d\n", p
->order
);