ucw/redblack-test.c

   1 /*
   2  *      Test of red-black trees
   3  *
   4  *      (c) 2002, Robert Spalek <robert@ucw.cz>
   5  */
   6
   7 #include <ucw/lib.h>
   8 #include <ucw/getopt.h>
   9 #include <ucw/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_CONSERVE_SPACE
  91 #include "redblack.h"
  92
  93 static void random_string(char *txt, uint max_len)
  94 {
  95         uint len = random() % max_len;
  96         uint j;
  97         for (j=0; j<len; j++)
  98                 txt[j] = random() % 96 + 32;
  99         txt[len] = 0;
 100 }
 101
 102 static char *options = CF_SHORT_OPTS "vn:a";
 103
 104 static char *help = "\
 105 Usage: test1.bin <options>\n\
 106 Options:\n"
 107 CF_USAGE
 108 "-v\tSet verbose mode\n\
 109 -n num\tNumber of inserted nodes\n\
 110 -a\tProbe some ASSERTs\n\
 111 ";
 112
 113 static void NONRET
 114 usage(void)
 115 {
 116         fputs(help, stderr);
 117         exit(1);
 118 }
 119
 120 int
 121 main(int argc, char **argv)
 122 {
 123         int verbose = 0, number = 1000, asserts = 0;
 124         int opt;
 125         struct fastbuf *fb, *dump_fb;
 126         struct my_tree t;
 127         struct my2_tree t2;
 128         int i;
 129         cf_def_file = NULL;
 130         log_init(argv[0]);
 131         while ((opt = cf_getopt(argc, argv, options, CF_NO_LONG_OPTS, NULL)) >= 0)
 132                 switch (opt)
 133                 {
 134                         case 'v':
 135                                 verbose++;
 136                                 break;
 137                         case 'n':
 138                                 number = atoi(optarg);
 139                                 break;
 140                         case 'a':
 141                                 asserts++;
 142                                 break;
 143                         default:
 144                                 usage();
 145                                 break;
 146                 }
 147         if (optind < argc)
 148                 usage();
 149         fb = bfdopen(1, 4096);
 150         if (verbose > 1)
 151                 dump_fb = fb;
 152         else
 153                 dump_fb = NULL;
 154
 155         my_init(&t);
 156         for (i=0; i<number; i++)
 157                 my_lookup(&t, random() % 1000000)->x = i;
 158         my_dump(dump_fb, &t);
 159         my_check_order(dump_fb, &t);
 160         if (asserts)
 161         {
 162                 my_new(&t, 1);
 163                 my_new(&t, 1);
 164         }
 165         my_cleanup(&t);
 166         if (verbose > 0)
 167                 bputs(fb, "Load test passed\n");
 168
 169         my_init(&t);
 170         for (i=0; i<100; i++)
 171         {
 172                 my_new(&t, i)->x = i;
 173                 my_dump(dump_fb, &t);
 174         }
 175         for (i=0; i<100; i++)
 176         {
 177                 int a = i/10, b = i%10, j = a*10 + (b + a) % 10;
 178                 int res UNUSED = my_delete(&t, j);
 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         i = 0;
 194         TREE_FOR_ALL(my, &t, n)
 195         {
 196                 ASSERT(n->key == i);
 197                 i++;
 198         }
 199         TREE_END_FOR;
 200         ASSERT(i == 997);
 201         for (i=0; i<997; i++)
 202         {
 203                 int res UNUSED = my_delete(&t, i*111 % 997);
 204                 ASSERT(res);
 205                 my_dump(NULL, &t);
 206         }
 207         my_dump(dump_fb, &t);
 208         my_cleanup(&t);
 209         if (verbose > 0)
 210                 bputs(fb, "Complete tree passed\n");
 211
 212         my2_init(&t2);
 213         for (i=0; i<number; i++)
 214         {
 215                 char txt[30];
 216                 random_string(txt, 30);
 217                 my2_new(&t2, txt);
 218         }
 219         my2_dump(dump_fb, &t2);
 220         TREE_FOR_ALL(my2, &t2, n)
 221         {
 222                 my2_node *tmp;
 223                 int count = 0;
 224                 for (tmp=n; tmp; tmp = my2_find_next(tmp))
 225                         count++;
 226                 if (dump_fb)
 227                 {
 228                         char txt[20];
 229                         bputs(dump_fb, n->key);
 230                         sprintf(txt, ": %d\n", count);
 231                         bputs(dump_fb, txt);
 232                 }
 233         }
 234         TREE_END_FOR;
 235         while (t2.count > 0)
 236         {
 237                 char txt[30];
 238                 my2_node *n;
 239                 random_string(txt, 30);
 240                 n = my2_search(&t2, txt);
 241                 ASSERT(n);
 242                 my2_remove(&t2, n);
 243         }
 244         my2_dump(dump_fb, &t2);
 245         my2_cleanup(&t2);
 246         if (verbose > 0)
 247                 bputs(fb, "String test passed\n");
 248
 249         bclose(fb);
 250         return 0;
 251 }