1 /* $NetBSD: tsearch-test.c,v 1.1.1.2 2014/04/24 12:45:52 pettai 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 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 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 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