tests/libpspp/range-map-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* This is a test program for the routines defined in
  18    range-map.c.  This test program aims to be as comprehensive as
  19    possible.  With -DNDEBUG, "gcov -b" should report 100%
  20    coverage of lines and branches in range-map.c routines.
  21    (Without -DNDEBUG, branches caused by failed assertions will
  22    not be taken.)  "valgrind --leak-check=yes
  23    --show-reachable=yes" should give a clean report, both with
  24    and without -DNDEBUG. */
  25
  26 #ifdef HAVE_CONFIG_H
  27 #include <config.h>
  28 #endif
  29
  30 #include <libpspp/range-map.h>
  31
  32 #include <assert.h>
  33 #include <limits.h>
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37
  38 #include <libpspp/compiler.h>
  39
  40 #include "xalloc.h"
  41 \f
  42 /* Currently running test. */
  43 static const char *test_name;
  44
  45 /* Exit with a failure code.
  46    (Place a breakpoint on this function while debugging.) */
  47 static void
  48 check_die (void)
  49 {
  50   exit (EXIT_FAILURE);
  51 }
  52
  53 /* If OK is not true, prints a message about failure on the
  54    current source file and the given LINE and terminates. */
  55 static void
  56 check_func (bool ok, int line)
  57 {
  58   if (!ok)
  59     {
  60       printf ("Check failed in %s test at %s, line %d\n",
  61               test_name, __FILE__, line);
  62       check_die ();
  63     }
  64 }
  65
  66 /* Verifies that EXPR evaluates to true.
  67    If not, prints a message citing the calling line number and
  68    terminates. */
  69 #define check(EXPR) check_func ((EXPR), __LINE__)
  70 \f
  71 /* Swaps *A and *B. */
  72 static void
  73 swap (int *a, int *b)
  74 {
  75   int t = *a;
  76   *a = *b;
  77   *b = t;
  78 }
  79
  80 /* Reverses the order of the CNT integers starting at VALUES. */
  81 static void
  82 reverse (int *values, size_t cnt)
  83 {
  84   size_t i = 0;
  85   size_t j = cnt;
  86
  87   while (j > i)
  88     swap (&values[i++], &values[--j]);
  89 }
  90
  91 /* Arranges the CNT blocks in VALUES into the lexicographically
  92    next greater permutation.  Returns true if successful.
  93    If VALUES is already the lexicographically greatest
  94    permutation of its blocks (i.e. ordered from greatest to
  95    smallest), arranges them into the lexicographically least
  96    permutation (i.e. ordered from smallest to largest) and
  97    returns false. */
  98 static bool
  99 next_permutation (int *values, size_t cnt)
 100 {
 101   if (cnt > 0)
 102     {
 103       size_t i = cnt - 1;
 104       while (i != 0)
 105         {
 106           i--;
 107           if (values[i] < values[i + 1])
 108             {
 109               size_t j;
 110               for (j = cnt - 1; values[i] >= values[j]; j--)
 111                 continue;
 112               swap (values + i, values + j);
 113               reverse (values + (i + 1), cnt - (i + 1));
 114               return true;
 115             }
 116         }
 117
 118       reverse (values, cnt);
 119     }
 120
 121   return false;
 122 }
 123
 124 /* Returns N!. */
 125 static unsigned int
 126 factorial (unsigned int n)
 127 {
 128   unsigned int value = 1;
 129   /* Disallow N values that overflow on 32-bit machines. */
 130   assert (n <= 12);
 131   for (; n > 1; )
 132     value *= n--;
 133   return value;
 134 }
 135
 136 /* Tests whether PARTS is a K-part integer composition of N.
 137    Returns true if so, false otherwise. */
 138 static bool UNUSED
 139 is_k_composition (int n, int k, const int parts[])
 140 {
 141   int sum;
 142   int i;
 143
 144   sum = 0;
 145   for (i = 0; i < k; i++)
 146     {
 147       if (parts[i] < 1 || parts[i] > n)
 148         return false;
 149       sum += parts[i];
 150     }
 151   return sum == n;
 152 }
 153
 154 /* Advances the K-part integer composition of N stored in PARTS
 155    to the next lexicographically greater one.
 156    Returns true if successful, false if the composition was
 157    already the greatest K-part composition of N (in which case
 158    PARTS is unaltered). */
 159 static bool
 160 next_k_composition (int n UNUSED, int k, int parts[])
 161 {
 162   int x, i;
 163
 164   assert (is_k_composition (n, k, parts));
 165   if (k == 1)
 166     return false;
 167
 168   for (i = k - 1; i > 0; i--)
 169     if (parts[i] > 1)
 170       break;
 171   if (i == 0)
 172     return false;
 173
 174   x = parts[i] - 1;
 175   parts[i] = 1;
 176   parts[i - 1]++;
 177   parts[k - 1] = x;
 178
 179   assert (is_k_composition (n, k, parts));
 180   return true;
 181 }
 182
 183 /* Sets the K integers in PARTS to the lexicographically first
 184    K-part composition of N. */
 185 static void
 186 first_k_composition (int n, int k, int parts[])
 187 {
 188   int i;
 189
 190   assert (n >= k);
 191
 192   for (i = 0; i < k; i++)
 193     parts[i] = 1;
 194   parts[k - 1] += n - k;
 195 }
 196
 197 /* Advances *K and PARTS to the next integer composition of N.
 198    Compositions are ordered from shortest to longest and in
 199    lexicographical order within a given length.
 200    Before the first call, initialize *K to 0.
 201    After each successful call, *K contains the length of the
 202    current composition and the *K blocks in PARTS contain its
 203    parts.
 204    Returns true if successful, false if the set of compositions
 205    has been exhausted. */
 206 static bool
 207 next_composition (int n, int *k, int parts[])
 208 {
 209   if (*k >= 1 && next_k_composition (n, *k, parts))
 210     return true;
 211   else if (*k < n)
 212     {
 213       first_k_composition (n, ++*k, parts);
 214       return true;
 215     }
 216   else
 217     return false;
 218 }
 219 \f
 220 /* Test data element. */
 221 struct element
 222   {
 223     struct range_map_node node; /* Embedded tower block. */
 224     int x;                      /* Primary value. */
 225   };
 226
 227 static struct element *
 228 range_map_node_to_element (struct range_map_node *node)
 229 {
 230   return range_map_data (node, struct element, node);
 231 }
 232
 233 /* Element we expect to find. */
 234 struct expected_element
 235   {
 236     int x;                      /* Primary value. */
 237     unsigned long int start;    /* Start of region. */
 238     unsigned long int end;      /* End of region. */
 239   };
 240
 241 /* Compares expected_element A and B and returns a strcmp()-type
 242    result. */
 243 static int
 244 compare_expected_element (const void *a_, const void *b_)
 245 {
 246   const struct expected_element *a = (const struct expected_element *) a_;
 247   const struct expected_element *b = (const struct expected_element *) b_;
 248   return a->start < b->start ? -1 : a->start > b->start;
 249 }
 250
 251 /* Checks that RM contains the ELEM_CNT elements described by
 252    ELEMENTS[]. */
 253 static void
 254 check_range_map (struct range_map *rm,
 255                  struct expected_element elements[], size_t elem_cnt)
 256 {
 257   struct expected_element *sorted;
 258   struct range_map_node *node;
 259   size_t i;
 260
 261   sorted = xnmalloc (elem_cnt, sizeof *sorted);
 262   memcpy (sorted, elements, elem_cnt * sizeof *elements);
 263   qsort (sorted, elem_cnt, sizeof *sorted, compare_expected_element);
 264
 265   check (range_map_is_empty (rm) == (elem_cnt == 0));
 266
 267   for (i = 0; i < elem_cnt; i++)
 268     {
 269       struct expected_element *e = &sorted[i];
 270       unsigned long int position;
 271
 272       /* Check that range_map_lookup finds all the positions
 273          within the element. */
 274       for (position = e->start; position < e->end; position++)
 275         {
 276           struct range_map_node *found = range_map_lookup (rm, position);
 277           check (found != NULL);
 278           check (range_map_node_to_element (found)->x == e->x);
 279           check (range_map_node_get_start (found) == e->start);
 280           check (range_map_node_get_end (found) == e->end);
 281           check (range_map_node_get_width (found) == e->end - e->start);
 282         }
 283
 284       /* If there shouldn't be any elements in the positions just
 285          before or after the element, verify that
 286          range_map_lookup doesn't find any there. */
 287       if (e->start > 0 && (i == 0 || e[-1].end < e->start))
 288         check (range_map_lookup (rm, e->start - 1) == NULL);
 289       if (i == elem_cnt - 1 || e->end < e[1].start)
 290         check (range_map_lookup (rm, e->end) == NULL);
 291     }
 292
 293   for (node = (rand () % 2 ? range_map_first (rm) : range_map_next (rm, NULL)),
 294          i = 0;
 295        node != NULL;
 296        node = range_map_next (rm, node), i++)
 297     {
 298       struct expected_element *e = &sorted[i];
 299       check (range_map_node_to_element (node)->x == e->x);
 300     }
 301   check (i == elem_cnt);
 302
 303   free (sorted);
 304 }
 305 \f
 306 /* Tests inserting all possible sets of ranges into a range map
 307    in all possible orders, up to a specified maximum overall
 308    range. */
 309 static void
 310 test_insert (void)
 311 {
 312   const int max_range = 7;
 313   int cnt;
 314
 315   for (cnt = 1; cnt <= max_range; cnt++)
 316     {
 317       unsigned int composition_cnt;
 318       struct expected_element *expected;
 319       int *widths;
 320       int elem_cnt;
 321       int *order;
 322       struct element *elements;
 323
 324       expected = xnmalloc (cnt, sizeof *expected);
 325       widths = xnmalloc (cnt, sizeof *widths);
 326       order = xnmalloc (cnt, sizeof *order);
 327       elements = xnmalloc (cnt, sizeof *elements);
 328
 329       elem_cnt = 0;
 330       composition_cnt = 0;
 331       while (next_composition (cnt, &elem_cnt, widths))
 332         {
 333           int i, j;
 334           unsigned int permutation_cnt;
 335
 336           for (i = 0; i < elem_cnt; i++)
 337             order[i] = i;
 338
 339           permutation_cnt = 0;
 340           while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
 341             {
 342               struct range_map rm;
 343
 344               /* Inserts the elem_cnt elements with the given
 345                  widths[] into T in the order given by order[]. */
 346               range_map_init (&rm);
 347               for (i = 0; i < elem_cnt; i++)
 348                 {
 349                   unsigned long int start, end;
 350                   int idx;
 351
 352                   idx = order[i];
 353                   elements[idx].x = idx;
 354
 355                   /* Find start and end of element. */
 356                   start = 0;
 357                   for (j = 0; j < idx; j++)
 358                     start += widths[j];
 359                   end = start + widths[j];
 360
 361                   /* Insert. */
 362                   range_map_insert (&rm, start, end - start,
 363                                     &elements[idx].node);
 364
 365                   /* Check map contents. */
 366                   expected[i].x = idx;
 367                   expected[i].start = start;
 368                   expected[i].end = end;
 369                   check_range_map (&rm, expected, i + 1);
 370                 }
 371               permutation_cnt++;
 372             }
 373           check (permutation_cnt == factorial (elem_cnt));
 374
 375           composition_cnt++;
 376         }
 377       check (composition_cnt == 1 << (cnt - 1));
 378
 379       free (expected);
 380       free (widths);
 381       free (order);
 382       free (elements);
 383     }
 384 }
 385
 386 /* Tests deleting ranges from a range map in all possible orders,
 387    up to a specified maximum overall range. */
 388 static void
 389 test_delete (int gap)
 390 {
 391   const int max_range = 7;
 392   int cnt;
 393
 394   for (cnt = 1; cnt <= max_range; cnt++)
 395     {
 396       unsigned int composition_cnt;
 397       struct expected_element *expected;
 398       int *widths;
 399       int elem_cnt;
 400       int *order;
 401       struct element *elements;
 402
 403       expected = xnmalloc (cnt, sizeof *expected);
 404       widths = xnmalloc (cnt, sizeof *widths);
 405       order = xnmalloc (cnt, sizeof *order);
 406       elements = xnmalloc (cnt, sizeof *elements);
 407
 408       elem_cnt = 0;
 409       composition_cnt = 0;
 410       while (next_composition (cnt, &elem_cnt, widths))
 411         {
 412           int i, j;
 413           unsigned int permutation_cnt;
 414
 415           for (i = 0; i < elem_cnt; i++)
 416             order[i] = i;
 417
 418           permutation_cnt = 0;
 419           while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
 420             {
 421               struct range_map rm;
 422               unsigned long int start;
 423
 424               /* Insert all the elements. */
 425               range_map_init (&rm);
 426               start = 0;
 427               for (i = 0; i < elem_cnt; i++)
 428                 {
 429                   int width = widths[i] > gap ? widths[i] - gap : widths[i];
 430                   unsigned long int end = start + width;
 431
 432                   elements[i].x = i;
 433                   range_map_insert (&rm, start, end - start,
 434                                     &elements[i].node);
 435
 436                   for (j = 0; ; j++)
 437                     {
 438                       assert (j < elem_cnt);
 439                       if (order[j] == i)
 440                         {
 441                           expected[j].x = i;
 442                           expected[j].start = start;
 443                           expected[j].end = end;
 444                           break;
 445                         }
 446                     }
 447
 448                   start += widths[i];
 449                 }
 450               check_range_map (&rm, expected, elem_cnt);
 451
 452               /* Delete the elements in the specified order. */
 453               for (i = 0; i < elem_cnt; i++)
 454                 {
 455                   range_map_delete (&rm, &elements[order[i]].node);
 456                   check_range_map (&rm, expected + i + 1, elem_cnt - i - 1);
 457                 }
 458
 459               permutation_cnt++;
 460             }
 461           check (permutation_cnt == factorial (elem_cnt));
 462
 463           composition_cnt++;
 464         }
 465       check (composition_cnt == 1 << (cnt - 1));
 466
 467       free (expected);
 468       free (widths);
 469       free (order);
 470       free (elements);
 471     }
 472 }
 473
 474 /* Tests deleting ranges from a range map filled with contiguous
 475    ranges in all possible orders, up to a specified maximum
 476    overall range. */
 477 static void
 478 test_delete_contiguous (void)
 479 {
 480   test_delete (0);
 481 }
 482
 483 /* Tests deleting ranges from a range map filled with ranges
 484    sometimes separated by gaps in all possible orders, up to a
 485    specified maximum overall range. */
 486 static void
 487 test_delete_gaps (void)
 488 {
 489   test_delete (1);
 490 }
 491 \f
 492 /* Main program. */
 493
 494 /* Runs TEST_FUNCTION and prints a message about NAME. */
 495 static void
 496 run_test (void (*test_function) (void), const char *name)
 497 {
 498   test_name = name;
 499   putchar ('.');
 500   fflush (stdout);
 501   test_function ();
 502 }
 503
 504 int
 505 main (void)
 506 {
 507   run_test (test_insert, "insert");
 508   run_test (test_delete_contiguous, "delete from contiguous ranges");
 509   run_test (test_delete_gaps, "delete from ranges separated by gaps");
 510   putchar ('\n');
 511
 512   return 0;
 513 }