1 /* $NetBSD: tsearch-test.c,v 1.1.1.2 2014/04/24 12:45:52 pettai Exp $ */
4 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
5 * the AT&T man page says.
7 * The node_t structure is for internal use only, lint doesn't grok it.
9 * Written by reading the System V Interface Definition, not the code.
11 * Totally public domain.
16 #include <krb5/roken.h>
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));
31 void *rootnode
= NULL
;
35 * This routine compares two nodes, based on an
36 * alphabetical ordering of the string field.
39 node_compare(const void *node1
, const void *node2
)
41 return strcmp(((const struct node
*) node1
)->string
,
42 ((const struct node
*) node2
)->string
);
45 static int walkorder
= -1;
48 list_node(const void *ptr
, VISIT order
, int level
)
50 const struct node
*p
= *(const struct node
**) ptr
;
52 if (order
== postorder
|| order
== leaf
) {
54 if (p
->order
!= walkorder
) {
55 warnx("sort failed: expected %d next, got %d\n", walkorder
,
63 main(int argc
, char **argv
)
66 struct node
*t
, *p
, tests
[] = {
79 for(t
= tests
; t
->string
; t
++) {
80 /* Better not be there */
81 p
= (struct node
*)rk_tfind((void *)t
, (void **)&rootnode
,
85 warnx("erroneous list: found %d\n", p
->order
);
89 /* Put node into the tree. */
90 p
= (struct node
*) rk_tsearch((void *)t
, (void **)&rootnode
,
94 warnx("erroneous list: missing %d\n", t
->order
);
99 rk_twalk(rootnode
, list_node
);
101 for(t
= tests
; t
->string
; t
++) {
102 /* Better be there */
103 p
= (struct node
*) rk_tfind((void *)t
, (void **)&rootnode
,
107 warnx("erroneous list: missing %d\n", t
->order
);
112 (void) rk_tdelete((void *)t
, (void **)&rootnode
,
115 /* Better not be there */
116 p
= (struct node
*) rk_tfind((void *)t
, (void **)&rootnode
,
120 warnx("erroneous list: found %d\n", p
->order
);