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