lib/redblack-test.c

   1 /*
   2  *      Test of red-black trees
   3  *
   4  *      (c) 2002, Robert Spalek <robert@ucw.cz>
   5  */
   6
   7 #include "lib/lib.h"
   8 #include "lib/conf.h"
   9 #include "lib/fastbuf.h"
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12
  13 struct my1_node
  14 {
  15         int key;
  16         int x;
  17 };
  18
  19 static void my_dump_key(struct fastbuf *fb, struct my1_node *n)
  20 {
  21         char tmp[20];
  22         sprintf(tmp, "key=%d ", n->key);
  23         bputs(fb, tmp);
  24 }
  25
  26 static void my_dump_data(struct fastbuf *fb, struct my1_node *n)
  27 {
  28         char tmp[20];
  29         sprintf(tmp, "x=%d ", n->x);
  30         bputs(fb, tmp);
  31 }
  32
  33 #define TREE_NODE struct my1_node
  34 #define TREE_PREFIX(x) my_##x
  35 #define TREE_KEY_ATOMIC key
  36 #define TREE_WANT_CLEANUP
  37 #define TREE_WANT_LOOKUP
  38 #define TREE_WANT_DELETE
  39 #define TREE_WANT_ITERATOR
  40 #define TREE_WANT_DUMP
  41 #define TREE_CONSERVE_SPACE
  42 #include "redblack.h"
  43
  44 static void my_check_order(struct fastbuf *fb, struct my_tree *t)
  45 {
  46         int last_key = 0x80000000;
  47         TREE_FOR_ALL(my, t, n)
  48         {
  49                 ASSERT(n->key >= last_key);
  50                 last_key = n->key;
  51                 if (fb)
  52                 {
  53                         char tmp[30];
  54                         sprintf(tmp, "%d -> %d\n", n->key, n->x);
  55                         bputs(fb, tmp);
  56                 }
  57         }
  58         TREE_END_FOR;
  59         if (fb)
  60                 bflush(fb);
  61 }
  62
  63 struct my2_node
  64 {
  65         char key[1];
  66 };
  67
  68 static void my2_dump_key(struct fastbuf *fb, struct my2_node *n)
  69 {
  70         bputs(fb, "key=");
  71         bputs(fb, n->key);
  72         bputc(fb, ' ');
  73 }
  74
  75 static void my2_dump_data(struct fastbuf *fb UNUSED, struct my2_node *n UNUSED)
  76 {
  77 }
  78
  79 #define TREE_NODE struct my2_node
  80 #define TREE_PREFIX(x) my2_##x
  81 #define TREE_KEY_ENDSTRING key
  82 #define TREE_NOCASE
  83 #define TREE_WANT_CLEANUP
  84 #define TREE_WANT_NEW
  85 #define TREE_WANT_SEARCH
  86 #define TREE_WANT_REMOVE
  87 #define TREE_WANT_FIND_NEXT
  88 #define TREE_WANT_ITERATOR
  89 #define TREE_WANT_DUMP
  90 #define TREE_STATIC
  91 #define TREE_CONSERVE_SPACE
  92 #include "redblack.h"
  93
  94 static void random_string(char *txt, uns max_len)
  95 {
  96         uns len = random() % max_len;
  97         uns j;
  98         for (j=0; j<len; j++)
  99                 txt[j] = random() % 96 + 32;
 100         txt[len] = 0;
 101 }
 102
 103 static char *options = CF_SHORT_OPTS "vn:a";
 104
 105 static char *help = "\
 106 Usage: test1.bin <options>\n\
 107 Options:\n"
 108 CF_USAGE
 109 "-v\tSet verbose mode\n\
 110 -n num\tNumber of inserted nodes\n\
 111 -a\tProbe some ASSERTs\n\
 112 ";
 113
 114 static void NONRET
 115 usage(void)
 116 {
 117         fputs(help, stderr);
 118         exit(1);
 119 }
 120
 121 int
 122 main(int argc, char **argv)
 123 {
 124         int verbose = 0, number = 1000, asserts = 0;
 125         int opt;
 126         struct fastbuf *fb, *dump_fb;
 127         struct my_tree t;
 128         struct my2_tree t2;
 129         int i;
 130         cfdeffile = NULL;
 131         log_init(argv[0]);
 132         while ((opt = cf_getopt(argc, argv, options, CF_NO_LONG_OPTS, NULL)) >= 0)
 133                 switch (opt)
 134                 {
 135                         case 'v':
 136                                 verbose++;
 137                                 break;
 138                         case 'n':
 139                                 number = atoi(optarg);
 140                                 break;
 141                         case 'a':
 142                                 asserts++;
 143                                 break;
 144                         default:
 145                                 usage();
 146                                 break;
 147                 }
 148         if (optind < argc)
 149                 usage();
 150         fb = bfdopen(1, 4096);
 151         if (verbose > 1)
 152                 dump_fb = fb;
 153         else
 154                 dump_fb = NULL;
 155
 156         my_init(&t);
 157         for (i=0; i<number; i++)
 158                 my_lookup(&t, random() % 1000000)->x = i;
 159         my_dump(dump_fb, &t);
 160         my_check_order(dump_fb, &t);
 161         if (asserts)
 162         {
 163                 my_new(&t, 1);
 164                 my_new(&t, 1);
 165         }
 166         my_cleanup(&t);
 167         if (verbose > 0)
 168                 bputs(fb, "Load test passed\n");
 169
 170         my_init(&t);
 171         for (i=0; i<100; i++)
 172         {
 173                 my_new(&t, i)->x = i;
 174                 my_dump(dump_fb, &t);
 175         }
 176         for (i=0; i<100; i++)
 177         {
 178                 int res UNUSED = my_delete(&t, i);
 179                 ASSERT(res);
 180                 my_dump(dump_fb, &t);
 181         }
 182         my_cleanup(&t);
 183         if (verbose > 0)
 184                 bputs(fb, "Sequential adding and deleting passed\n");
 185
 186         my_init(&t);
 187         for (i=0; i<997; i++)
 188         {
 189                 my_new(&t, i*238 % 997)->x = i;
 190                 my_dump(NULL, &t);
 191         }
 192         my_dump(dump_fb, &t);
 193         for (i=0; i<997; i++)
 194         {
 195                 int res UNUSED = my_delete(&t, i*111 % 997);
 196                 ASSERT(res);
 197                 my_dump(NULL, &t);
 198         }
 199         my_dump(dump_fb, &t);
 200         i = 0;
 201         TREE_FOR_ALL(my, &t, n)
 202         {
 203                 ASSERT(n->key == i);
 204                 i++;
 205         }
 206         TREE_END_FOR;
 207         my_cleanup(&t);
 208         if (verbose > 0)
 209                 bputs(fb, "Complete tree passed\n");
 210
 211         my2_init(&t2);
 212         for (i=0; i<number; i++)
 213         {
 214                 char txt[30];
 215                 random_string(txt, 30);
 216                 my2_new(&t2, txt);
 217         }
 218         my2_dump(dump_fb, &t2);
 219         TREE_FOR_ALL(my2, &t2, n)
 220         {
 221                 my2_node *tmp;
 222                 int count = 0;
 223                 for (tmp=n; tmp; tmp = my2_find_next(tmp))
 224                         count++;
 225                 if (dump_fb)
 226                 {
 227                         char txt[20];
 228                         bputs(dump_fb, n->key);
 229                         sprintf(txt, ": %d\n", count);
 230                         bputs(dump_fb, txt);
 231                 }
 232         }
 233         TREE_END_FOR;
 234         while (t2.count > 0)
 235         {
 236                 char txt[30];
 237                 my2_node *n;
 238                 random_string(txt, 30);
 239                 n = my2_search(&t2, txt);
 240                 ASSERT(n);
 241                 my2_remove(&t2, n);
 242         }
 243         my2_dump(dump_fb, &t2);
 244         my2_cleanup(&t2);
 245         if (verbose > 0)
 246                 bputs(fb, "String test passed\n");
 247
 248         bclose(fb);
 249         return 0;
 250 }