lib/redblack-test.c

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