source4/heimdal/lib/roken/tsearch-test.c

   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
  17 struct node {
  18     char *string;
  19     int order;
  20 };
  21
  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));
  28
  29 void *rootnode = NULL;
  30 int numerr = 0;
  31
  32 /*
  33  *  This routine compares two nodes, based on an
  34  *  alphabetical ordering of the string field.
  35  */
  36 int
  37 node_compare(const void *node1, const void *node2)
  38 {
  39     return strcmp(((const struct node *) node1)->string,
  40                   ((const struct node *) node2)->string);
  41 }
  42
  43 static int walkorder = -1;
  44
  45 void
  46 list_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
  60 int
  61 main(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 }