util/redblack_test.c

   1 /* Copyright (c) 2007-2014 Massachusetts Institute of Technology
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining
   4  * a copy of this software and associated documentation files (the
   5  * "Software"), to deal in the Software without restriction, including
   6  * without limitation the rights to use, copy, modify, merge, publish,
   7  * distribute, sublicense, and/or sell copies of the Software, and to
   8  * permit persons to whom the Software is furnished to do so, subject to
   9  * the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be
  12  * included in all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  15  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  16  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  17  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  18  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  19  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  20  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <math.h>
  26 #include <time.h>
  27 #include "redblack.h"
  28
  29 #include "config.h"
  30 /* workaround for Solaris + gcc 3.4.x bug (see configure.ac) */
  31 #if defined(__GNUC__) && defined(REPLACEMENT_HUGE_VAL)
  32 #  undef HUGE_VAL
  33 #  define HUGE_VAL REPLACEMENT_HUGE_VAL
  34 #endif
  35
  36 static int comp(rb_key k1, rb_key k2)
  37 {
  38      if (*k1 < *k2) return -1;
  39      if (*k1 > *k2) return +1;
  40      return 0;
  41 }
  42
  43 int main(int argc, char **argv)
  44 {
  45      int N, M;
  46      int *k;
  47      double kd;
  48      rb_tree t;
  49      rb_node *n;
  50      int i, j;
  51
  52      if (argc < 2) {
  53           fprintf(stderr, "Usage: redblack_test Ntest [rand seed]\n");
  54           return 1;
  55      }
  56
  57      N = atoi(argv[1]);
  58      k = (int *) malloc(N * sizeof(int));
  59      rb_tree_init(&t, comp);
  60
  61      srand((unsigned) (argc > 2 ? atoi(argv[2]) : time(NULL)));
  62      for (i = 0; i < N; ++i) {
  63           double *newk = (double *) malloc(sizeof(double));
  64           *newk = (k[i] = rand() % N);
  65           if (!rb_tree_insert(&t, newk)) {
  66                fprintf(stderr, "error in rb_tree_insert\n");
  67                return 1;
  68           }
  69           if (!rb_tree_check(&t)) {
  70                fprintf(stderr, "rb_tree_check_failed after insert!\n");
  71                return 1;
  72           }
  73      }
  74
  75      if (t.N != N) {
  76           fprintf(stderr, "incorrect N (%d) in tree (vs. %d)\n", t.N, N);
  77           return 1;
  78      }
  79
  80      for (i = 0; i < N; ++i) {
  81           kd = k[i];
  82           if (!rb_tree_find(&t, &kd)) {
  83                fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
  84                return 1;
  85           }
  86      }
  87
  88      n = rb_tree_min(&t);
  89      for (i = 0; i < N; ++i) {
  90           if (!n) {
  91                fprintf(stderr, "not enough successors %d\n!", i);
  92                return 1;
  93           }
  94           printf("%d: %g\n", i, n->k[0]);
  95           n = rb_tree_succ(n);
  96      }
  97      if (n) {
  98           fprintf(stderr, "too many successors!\n");
  99           return 1;
 100      }
 101
 102      n = rb_tree_max(&t);
 103      for (i = 0; i < N; ++i) {
 104           if (!n) {
 105                fprintf(stderr, "not enough predecessors %d\n!", i);
 106                return 1;
 107           }
 108           printf("%d: %g\n", i, n->k[0]);
 109           n = rb_tree_pred(n);
 110      }
 111      if (n) {
 112           fprintf(stderr, "too many predecessors!\n");
 113           return 1;
 114      }
 115
 116      for (M = N; M > 0; --M) {
 117           int knew = rand() % N; /* random new key */
 118           j = rand() % M; /* random original key to replace */
 119           for (i = 0; i < N; ++i)
 120                if (k[i] >= 0)
 121                     if (j-- == 0)
 122                          break;
 123           if (i >= N) abort();
 124           kd = k[i];
 125           if (!(n = rb_tree_find(&t, &kd))) {
 126                fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
 127                return 1;
 128           }
 129           n->k[0] = knew;
 130           if (!rb_tree_resort(&t, n)) {
 131                fprintf(stderr, "error in rb_tree_resort\n");
 132                return 1;
 133           }
 134           if (!rb_tree_check(&t)) {
 135                fprintf(stderr, "rb_tree_check_failed after change %d!\n",
 136                        N - M + 1);
 137                return 1;
 138           }
 139           k[i] = -1 - knew;
 140      }
 141
 142      if (t.N != N) {
 143           fprintf(stderr, "incorrect N (%d) in tree (vs. %d)\n", t.N, N);
 144           return 1;
 145      }
 146
 147      for (i = 0; i < N; ++i)
 148           k[i] = -1 - k[i]; /* undo negation above */
 149
 150      for (i = 0; i < N; ++i) {
 151           rb_node *le, *gt;
 152           kd = 0.01 * (rand() % (N * 150) - N*25);
 153           le = rb_tree_find_le(&t, &kd);
 154           gt = rb_tree_find_gt(&t, &kd);
 155           n = rb_tree_min(&t);
 156           double lek = le ? le->k[0] : -HUGE_VAL;
 157           double gtk = gt ? gt->k[0] : +HUGE_VAL;
 158           printf("%g <= %g < %g\n", lek, kd, gtk);
 159           if (n->k[0] > kd) {
 160                if (le) {
 161                     fprintf(stderr, "found invalid le %g for %g\n", lek, kd);
 162                     return 1;
 163                }
 164                if (gt != n) {
 165                     fprintf(stderr, "gt is not first node for k=%g\n", kd);
 166                     return 1;
 167                }
 168           }
 169           else {
 170                rb_node *succ = n;
 171                do {
 172                     n = succ;
 173                     succ = rb_tree_succ(n);
 174                } while (succ && succ->k[0] <= kd);
 175                if (n != le) {
 176                     fprintf(stderr,
 177                             "rb_tree_find_le gave wrong result for k=%g\n",kd);
 178                     return 1;
 179                }
 180                if (succ != gt) {
 181                     fprintf(stderr,
 182                             "rb_tree_find_gt gave wrong result for k=%g\n",kd);
 183                     return 1;
 184                }
 185           }
 186      }
 187
 188      for (M = N; M > 0; --M) {
 189           j = rand() % M;
 190           for (i = 0; i < N; ++i)
 191                if (k[i] >= 0)
 192                     if (j-- == 0)
 193                          break;
 194           if (i >= N) abort();
 195           kd = k[i];
 196           if (!(n = rb_tree_find(&t, &kd))) {
 197                fprintf(stderr, "rb_tree_find lost %d!\n", k[i]);
 198                return 1;
 199           }
 200           n = rb_tree_remove(&t, n);
 201           free(n->k);
 202           free(n);
 203           if (!rb_tree_check(&t)) {
 204                fprintf(stderr, "rb_tree_check_failed after remove!\n");
 205                return 1;
 206           }
 207           k[i] = -1 - k[i];
 208      }
 209
 210      if (t.N != 0) {
 211           fprintf(stderr, "nonzero N (%d) in tree at end\n", t.N);
 212           return 1;
 213      }
 214
 215      rb_tree_destroy(&t);
 216      free(k);
 217
 218      printf("SUCCESS.\n");
 219      return 0;
 220 }