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 a = i/10, b = i%10, j = a*10 + (b + a) % 10;
 179                 int res UNUSED = my_delete(&t, j);
 180                 ASSERT(res);
 181                 my_dump(dump_fb, &t);
 182         }
 183         my_cleanup(&t);
 184         if (verbose > 0)
 185                 bputs(fb, "Sequential adding and deleting passed\n");
 186
 187         my_init(&t);
 188         for (i=0; i<997; i++)
 189         {
 190                 my_new(&t, i*238 % 997)->x = i;
 191                 my_dump(NULL, &t);
 192         }
 193         my_dump(dump_fb, &t);
 194         i = 0;
 195         TREE_FOR_ALL(my, &t, n)
 196         {
 197                 ASSERT(n->key == i);
 198                 i++;
 199         }
 200         TREE_END_FOR;
 201         ASSERT(i == 997);
 202         for (i=0; i<997; i++)
 203         {
 204                 int res UNUSED = my_delete(&t, i*111 % 997);
 205                 ASSERT(res);
 206                 my_dump(NULL, &t);
 207         }
 208         my_dump(dump_fb, &t);
 209         my_cleanup(&t);
 210         if (verbose > 0)
 211                 bputs(fb, "Complete tree passed\n");
 212
 213         my2_init(&t2);
 214         for (i=0; i<number; i++)
 215         {
 216                 char txt[30];
 217                 random_string(txt, 30);
 218                 my2_new(&t2, txt);
 219         }
 220         my2_dump(dump_fb, &t2);
 221         TREE_FOR_ALL(my2, &t2, n)
 222         {
 223                 my2_node *tmp;
 224                 int count = 0;
 225                 for (tmp=n; tmp; tmp = my2_find_next(tmp))
 226                         count++;
 227                 if (dump_fb)
 228                 {
 229                         char txt[20];
 230                         bputs(dump_fb, n->key);
 231                         sprintf(txt, ": %d\n", count);
 232                         bputs(dump_fb, txt);
 233                 }
 234         }
 235         TREE_END_FOR;
 236         while (t2.count > 0)
 237         {
 238                 char txt[30];
 239                 my2_node *n;
 240                 random_string(txt, 30);
 241                 n = my2_search(&t2, txt);
 242                 ASSERT(n);
 243                 my2_remove(&t2, n);
 244         }
 245         my2_dump(dump_fb, &t2);
 246         my2_cleanup(&t2);
 247         if (verbose > 0)
 248                 bputs(fb, "String test passed\n");
 249
 250         bclose(fb);
 251         return 0;
 252 }