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