tests/libpspp/range-map-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2010 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 /* Exit with a failure code.
  43    (Place a breakpoint on this function while debugging.) */
  44 static void
  45 check_die (void)
  46 {
  47   exit (EXIT_FAILURE);
  48 }
  49
  50 /* If OK is not true, prints a message about failure on the
  51    current source file and the given LINE and terminates. */
  52 static void
  53 check_func (bool ok, int line)
  54 {
  55   if (!ok)
  56     {
  57       fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
  58       check_die ();
  59     }
  60 }
  61
  62 /* Verifies that EXPR evaluates to true.
  63    If not, prints a message citing the calling line number and
  64    terminates. */
  65 #define check(EXPR) check_func ((EXPR), __LINE__)
  66 \f
  67 /* Swaps *A and *B. */
  68 static void
  69 swap (int *a, int *b)
  70 {
  71   int t = *a;
  72   *a = *b;
  73   *b = t;
  74 }
  75
  76 /* Reverses the order of the CNT integers starting at VALUES. */
  77 static void
  78 reverse (int *values, size_t cnt)
  79 {
  80   size_t i = 0;
  81   size_t j = cnt;
  82
  83   while (j > i)
  84     swap (&values[i++], &values[--j]);
  85 }
  86
  87 /* Arranges the CNT blocks in VALUES into the lexicographically
  88    next greater permutation.  Returns true if successful.
  89    If VALUES is already the lexicographically greatest
  90    permutation of its blocks (i.e. ordered from greatest to
  91    smallest), arranges them into the lexicographically least
  92    permutation (i.e. ordered from smallest to largest) and
  93    returns false. */
  94 static bool
  95 next_permutation (int *values, size_t cnt)
  96 {
  97   if (cnt > 0)
  98     {
  99       size_t i = cnt - 1;
 100       while (i != 0)
 101         {
 102           i--;
 103           if (values[i] < values[i + 1])
 104             {
 105               size_t j;
 106               for (j = cnt - 1; values[i] >= values[j]; j--)
 107                 continue;
 108               swap (values + i, values + j);
 109               reverse (values + (i + 1), cnt - (i + 1));
 110               return true;
 111             }
 112         }
 113
 114       reverse (values, cnt);
 115     }
 116
 117   return false;
 118 }
 119
 120 /* Returns N!. */
 121 static unsigned int
 122 factorial (unsigned int n)
 123 {
 124   unsigned int value = 1;
 125   /* Disallow N values that overflow on 32-bit machines. */
 126   assert (n <= 12);
 127   for (; n > 1;)
 128     value *= n--;
 129   return value;
 130 }
 131
 132 /* Tests whether PARTS is a K-part integer composition of N.
 133    Returns true if so, false otherwise. */
 134 static bool UNUSED
 135 is_k_composition (int n, int k, const int parts[])
 136 {
 137   int sum;
 138   int i;
 139
 140   sum = 0;
 141   for (i = 0; i < k; i++)
 142     {
 143       if (parts[i] < 1 || parts[i] > n)
 144         return false;
 145       sum += parts[i];
 146     }
 147   return sum == n;
 148 }
 149
 150 /* Advances the K-part integer composition of N stored in PARTS
 151    to the next lexicographically greater one.
 152    Returns true if successful, false if the composition was
 153    already the greatest K-part composition of N (in which case
 154    PARTS is unaltered). */
 155 static bool
 156 next_k_composition (int n UNUSED, int k, int parts[])
 157 {
 158   int x, i;
 159
 160   assert (is_k_composition (n, k, parts));
 161   if (k == 1)
 162     return false;
 163
 164   for (i = k - 1; i > 0; i--)
 165     if (parts[i] > 1)
 166       break;
 167   if (i == 0)
 168     return false;
 169
 170   x = parts[i] - 1;
 171   parts[i] = 1;
 172   parts[i - 1]++;
 173   parts[k - 1] = x;
 174
 175   assert (is_k_composition (n, k, parts));
 176   return true;
 177 }
 178
 179 /* Sets the K integers in PARTS to the lexicographically first
 180    K-part composition of N. */
 181 static void
 182 first_k_composition (int n, int k, int parts[])
 183 {
 184   int i;
 185
 186   assert (n >= k);
 187
 188   for (i = 0; i < k; i++)
 189     parts[i] = 1;
 190   parts[k - 1] += n - k;
 191 }
 192
 193 /* Advances *K and PARTS to the next integer composition of N.
 194    Compositions are ordered from shortest to longest and in
 195    lexicographical order within a given length.
 196    Before the first call, initialize *K to 0.
 197    After each successful call, *K contains the length of the
 198    current composition and the *K blocks in PARTS contain its
 199    parts.
 200    Returns true if successful, false if the set of compositions
 201    has been exhausted. */
 202 static bool
 203 next_composition (int n, int *k, int parts[])
 204 {
 205   if (*k >= 1 && next_k_composition (n, *k, parts))
 206     return true;
 207   else if (*k < n)
 208     {
 209       first_k_composition (n, ++*k, parts);
 210       return true;
 211     }
 212   else
 213     return false;
 214 }
 215 \f
 216 /* Test data element. */
 217 struct element
 218   {
 219     struct range_map_node node; /* Embedded tower block. */
 220     int x;                      /* Primary value. */
 221   };
 222
 223 static struct element *
 224 range_map_node_to_element (struct range_map_node *node)
 225 {
 226   return range_map_data (node, struct element, node);
 227 }
 228
 229 /* Element we expect to find. */
 230 struct expected_element
 231   {
 232     int x;                      /* Primary value. */
 233     unsigned long int start;    /* Start of region. */
 234     unsigned long int end;      /* End of region. */
 235   };
 236
 237 /* Compares expected_element A and B and returns a strcmp()-type
 238    result. */
 239 static int
 240 compare_expected_element (const void *a_, const void *b_)
 241 {
 242   const struct expected_element *a = (const struct expected_element *) a_;
 243   const struct expected_element *b = (const struct expected_element *) b_;
 244   return a->start < b->start ? -1 : a->start > b->start;
 245 }
 246
 247 /* Checks that RM contains the ELEM_CNT elements described by
 248    ELEMENTS[]. */
 249 static void
 250 check_range_map (struct range_map *rm,
 251                  struct expected_element elements[], size_t n_elems)
 252 {
 253   struct expected_element *sorted;
 254   struct range_map_node *node;
 255   size_t i;
 256
 257   sorted = xnmalloc (n_elems, sizeof *sorted);
 258   memcpy (sorted, elements, n_elems * sizeof *elements);
 259   qsort (sorted, n_elems, sizeof *sorted, compare_expected_element);
 260
 261   check (range_map_is_empty (rm) == (n_elems == 0));
 262
 263   for (i = 0; i < n_elems; i++)
 264     {
 265       struct expected_element *e = &sorted[i];
 266       unsigned long int position;
 267
 268       /* Check that range_map_lookup finds all the positions
 269          within the element. */
 270       for (position = e->start; position < e->end; position++)
 271         {
 272           struct range_map_node *found = range_map_lookup (rm, position);
 273           check (found != NULL);
 274           check (range_map_node_to_element (found)->x == e->x);
 275           check (range_map_node_get_start (found) == e->start);
 276           check (range_map_node_get_end (found) == e->end);
 277           check (range_map_node_get_width (found) == e->end - e->start);
 278         }
 279
 280       /* If there shouldn't be any elements in the positions just
 281          before or after the element, verify that
 282          range_map_lookup doesn't find any there. */
 283       if (e->start > 0 && (i == 0 || e[-1].end < e->start))
 284         check (range_map_lookup (rm, e->start - 1) == NULL);
 285       if (i == n_elems - 1 || e->end < e[1].start)
 286         check (range_map_lookup (rm, e->end) == NULL);
 287     }
 288
 289   for (node = (rand () % 2 ? range_map_first (rm) : range_map_next (rm, NULL)),
 290          i = 0;
 291        node != NULL;
 292        node = range_map_next (rm, node), i++)
 293     {
 294       struct expected_element *e = &sorted[i];
 295       check (range_map_node_to_element (node)->x == e->x);
 296     }
 297   check (i == n_elems);
 298
 299   free (sorted);
 300 }
 301 \f
 302 /* Tests inserting all possible sets of ranges into a range map
 303    in all possible orders, up to a specified maximum overall
 304    range. */
 305 static void
 306 test_insert (void)
 307 {
 308   const int max_range = 7;
 309   int cnt;
 310
 311   for (cnt = 1; cnt <= max_range; cnt++)
 312     {
 313       unsigned int n_compositions;
 314       struct expected_element *expected;
 315       int *widths;
 316       int n_elems;
 317       int *order;
 318       struct element *elements;
 319
 320       expected = xnmalloc (cnt, sizeof *expected);
 321       widths = xnmalloc (cnt, sizeof *widths);
 322       order = xnmalloc (cnt, sizeof *order);
 323       elements = xnmalloc (cnt, sizeof *elements);
 324
 325       n_elems = 0;
 326       n_compositions = 0;
 327       while (next_composition (cnt, &n_elems, widths))
 328         {
 329           int i, j;
 330           unsigned int n_permutations;
 331
 332           for (i = 0; i < n_elems; i++)
 333             order[i] = i;
 334
 335           n_permutations = 0;
 336           while (n_permutations == 0 || next_permutation (order, n_elems))
 337             {
 338               struct range_map rm;
 339
 340               /* Inserts the n_elems elements with the given
 341                  widths[] into T in the order given by order[]. */
 342               range_map_init (&rm);
 343               for (i = 0; i < n_elems; i++)
 344                 {
 345                   unsigned long int start, end;
 346                   int idx;
 347
 348                   idx = order[i];
 349                   elements[idx].x = idx;
 350
 351                   /* Find start and end of element. */
 352                   start = 0;
 353                   for (j = 0; j < idx; j++)
 354                     start += widths[j];
 355                   end = start + widths[j];
 356
 357                   /* Insert. */
 358                   range_map_insert (&rm, start, end - start,
 359                                     &elements[idx].node);
 360
 361                   /* Check map contents. */
 362                   expected[i].x = idx;
 363                   expected[i].start = start;
 364                   expected[i].end = end;
 365                   check_range_map (&rm, expected, i + 1);
 366                 }
 367               n_permutations++;
 368             }
 369           check (n_permutations == factorial (n_elems));
 370
 371           n_compositions++;
 372         }
 373       check (n_compositions == 1 << (cnt - 1));
 374
 375       free (expected);
 376       free (widths);
 377       free (order);
 378       free (elements);
 379     }
 380 }
 381
 382 /* Tests deleting ranges from a range map in all possible orders,
 383    up to a specified maximum overall range. */
 384 static void
 385 test_delete (int gap)
 386 {
 387   const int max_range = 7;
 388   int cnt;
 389
 390   for (cnt = 1; cnt <= max_range; cnt++)
 391     {
 392       unsigned int n_compositions;
 393       struct expected_element *expected;
 394       int *widths;
 395       int n_elems;
 396       int *order;
 397       struct element *elements;
 398
 399       expected = xnmalloc (cnt, sizeof *expected);
 400       widths = xnmalloc (cnt, sizeof *widths);
 401       order = xnmalloc (cnt, sizeof *order);
 402       elements = xnmalloc (cnt, sizeof *elements);
 403
 404       n_elems = 0;
 405       n_compositions = 0;
 406       while (next_composition (cnt, &n_elems, widths))
 407         {
 408           int i, j;
 409           unsigned int n_permutations;
 410
 411           for (i = 0; i < n_elems; i++)
 412             order[i] = i;
 413
 414           n_permutations = 0;
 415           while (n_permutations == 0 || next_permutation (order, n_elems))
 416             {
 417               struct range_map rm;
 418               unsigned long int start;
 419
 420               /* Insert all the elements. */
 421               range_map_init (&rm);
 422               start = 0;
 423               for (i = 0; i < n_elems; i++)
 424                 {
 425                   int width = widths[i] > gap ? widths[i] - gap : widths[i];
 426                   unsigned long int end = start + width;
 427
 428                   elements[i].x = i;
 429                   range_map_insert (&rm, start, end - start,
 430                                     &elements[i].node);
 431
 432                   for (j = 0; ; j++)
 433                     {
 434                       assert (j < n_elems);
 435                       if (order[j] == i)
 436                         {
 437                           expected[j].x = i;
 438                           expected[j].start = start;
 439                           expected[j].end = end;
 440                           break;
 441                         }
 442                     }
 443
 444                   start += widths[i];
 445                 }
 446               check_range_map (&rm, expected, n_elems);
 447
 448               /* Delete the elements in the specified order. */
 449               for (i = 0; i < n_elems; i++)
 450                 {
 451                   range_map_delete (&rm, &elements[order[i]].node);
 452                   check_range_map (&rm, expected + i + 1, n_elems - i - 1);
 453                 }
 454
 455               n_permutations++;
 456             }
 457           check (n_permutations == factorial (n_elems));
 458
 459           n_compositions++;
 460         }
 461       check (n_compositions == 1 << (cnt - 1));
 462
 463       free (expected);
 464       free (widths);
 465       free (order);
 466       free (elements);
 467     }
 468 }
 469
 470 /* Tests deleting ranges from a range map filled with contiguous
 471    ranges in all possible orders, up to a specified maximum
 472    overall range. */
 473 static void
 474 test_delete_contiguous (void)
 475 {
 476   test_delete (0);
 477 }
 478
 479 /* Tests deleting ranges from a range map filled with ranges
 480    sometimes separated by gaps in all possible orders, up to a
 481    specified maximum overall range. */
 482 static void
 483 test_delete_gaps (void)
 484 {
 485   test_delete (1);
 486 }
 487 \f
 488 /* Main program. */
 489
 490 struct test
 491   {
 492     const char *name;
 493     const char *description;
 494     void (*function) (void);
 495   };
 496
 497 static const struct test tests[] =
 498   {
 499     {
 500       "insert",
 501       "insert",
 502       test_insert
 503     },
 504     {
 505       "delete-contiguous",
 506       "delete from contiguous ranges",
 507       test_delete_contiguous
 508     },
 509     {
 510       "delete-gaps",
 511       "delete from ranges separated by gaps",
 512       test_delete_gaps
 513     },
 514   };
 515
 516 enum { N_TESTS = sizeof tests / sizeof *tests };
 517
 518 int
 519 main (int argc, char *argv[])
 520 {
 521   int i;
 522
 523   if (argc != 2)
 524     {
 525       fprintf (stderr, "exactly one argument required; use --help for help\n");
 526       return EXIT_FAILURE;
 527     }
 528   else if (!strcmp (argv[1], "--help"))
 529     {
 530       printf ("%s: test range map library\n"
 531               "usage: %s TEST-NAME\n"
 532               "where TEST-NAME is one of the following:\n",
 533               argv[0], argv[0]);
 534       for (i = 0; i < N_TESTS; i++)
 535         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 536       return 0;
 537     }
 538   else
 539     {
 540       for (i = 0; i < N_TESTS; i++)
 541         if (!strcmp (argv[1], tests[i].name))
 542           {
 543             tests[i].function ();
 544             return 0;
 545           }
 546
 547       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 548       return EXIT_FAILURE;
 549     }
 550 }