crypto/external/bsd/heimdal/dist/lib/roken/tsearch-test.c

   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 }