tests/libpspp/range-map-test.c

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