1/* 2 * Tree search generalized from Knuth (6.2.2) Algorithm T just like 3 * the AT&T man page says. 4 * 5 * The node_t structure is for internal use only, lint doesn't grok it. 6 * 7 * Written by reading the System V Interface Definition, not the code. 8 * 9 * Totally public domain. 10 */ 11 12#include <config.h> 13 14#include "roken.h" 15#include "search.h" 16 17struct node { 18 char *string; 19 int order; 20}; 21 22extern void *rk_tdelete(const void *, void **, 23 int (*)(const void *, const void *)); 24extern void *rk_tfind(const void *, void * const *, 25 int (*)(const void *, const void *)); 26extern void *rk_tsearch(const void *, void **, int (*)(const void *, const void *)); 27extern void rk_twalk(const void *, void (*)(const void *, VISIT, int)); 28 29void *rootnode = NULL; 30int numerr = 0; 31 32/* 33 * This routine compares two nodes, based on an 34 * alphabetical ordering of the string field. 35 */ 36int 37node_compare(const void *node1, const void *node2) 38{ 39 return strcmp(((const struct node *) node1)->string, 40 ((const struct node *) node2)->string); 41} 42 43static int walkorder = -1; 44 45void 46list_node(const void *ptr, VISIT order, int level) 47{ 48 const struct node *p = *(const struct node **) ptr; 49 50 if (order == postorder || order == leaf) { 51 walkorder++; 52 if (p->order != walkorder) { 53 warnx("sort failed: expected %d next, got %d\n", walkorder, 54 p->order); 55 numerr++; 56 } 57 } 58} 59 60int 61main(int argc, char **argv) 62{ 63 int numtest = 1; 64 struct node *t, *p, tests[] = { 65 { "", 0 }, 66 { "ab", 3 }, 67 { "abc", 4 }, 68 { "abcdefg", 8 }, 69 { "abcd", 5 }, 70 { "a", 2 }, 71 { "abcdef", 7 }, 72 { "abcde", 6 }, 73 { "=", 1 }, 74 { NULL } 75 }; 76 77 for(t = tests; t->string; t++) { 78 /* Better not be there */ 79 p = (struct node *)rk_tfind((void *)t, (void **)&rootnode, 80 node_compare); 81 82 if (p) { 83 warnx("erroneous list: found %d\n", p->order); 84 numerr++; 85 } 86 87 /* Put node into the tree. */ 88 p = (struct node *) rk_tsearch((void *)t, (void **)&rootnode, 89 node_compare); 90 91 if (!p) { 92 warnx("erroneous list: missing %d\n", t->order); 93 numerr++; 94 } 95 } 96 97 rk_twalk(rootnode, list_node); 98 99 for(t = tests; t->string; t++) { 100 /* Better be there */ 101 p = (struct node *) rk_tfind((void *)t, (void **)&rootnode, 102 node_compare); 103 104 if (!p) { 105 warnx("erroneous list: missing %d\n", t->order); 106 numerr++; 107 } 108 109 /* pull out node */ 110 (void) rk_tdelete((void *)t, (void **)&rootnode, 111 node_compare); 112 113 /* Better not be there */ 114 p = (struct node *) rk_tfind((void *)t, (void **)&rootnode, 115 node_compare); 116 117 if (p) { 118 warnx("erroneous list: found %d\n", p->order); 119 numerr++; 120 } 121 122 } 123 124 return numerr; 125} 126