tests/libpspp/range-set-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2010, 2011, 2012 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-set.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-set.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-set.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 #include <libpspp/pool.h>
  40
  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 /* A contiguous region. */
  68 struct region
  69   {
  70     unsigned long int start;    /* Start of region. */
  71     unsigned long int end;      /* One past the end. */
  72   };
  73
  74 /* Number of bits in an unsigned int. */
  75 #define UINT_BIT (CHAR_BIT * sizeof (unsigned int))
  76
  77 /* Returns the number of contiguous 1-bits in X starting from bit
  78    0.
  79    This implementation is designed to be obviously correct, not
  80    to be efficient. */
  81 static int
  82 count_one_bits (unsigned long int x)
  83 {
  84   int count = 0;
  85   while (x & 1)
  86     {
  87       count++;
  88       x >>= 1;
  89     }
  90   return count;
  91 }
  92
  93 /* Searches the bits in PATTERN from right to left starting from
  94    bit OFFSET for one or more 1-bits.  If any are found, sets
  95    *START to the bit index of the first and *WIDTH to the number
  96    of contiguous 1-bits and returns true.  Otherwise, returns
  97    false.
  98    This implementation is designed to be obviously correct, not
  99    to be efficient. */
 100 static bool
 101 next_region (unsigned int pattern, unsigned int offset,
 102              unsigned long int *start, unsigned long int *width)
 103 {
 104   unsigned int i;
 105
 106   assert (offset <= UINT_BIT);
 107   for (i = offset; i < UINT_BIT; i++)
 108     if (pattern & (1u << i))
 109       {
 110         *start = i;
 111         *width = count_one_bits (pattern >> i);
 112         return true;
 113       }
 114   return false;
 115 }
 116
 117 /* Searches the bits in PATTERN from left to right starting from
 118    just beyond bit OFFSET for one or more 1-bits.  If any are
 119    found, sets *START to the bit index of the first and *WIDTH to
 120    the number of contiguous 1-bits and returns true.  Otherwise,
 121    returns false.
 122    This implementation is designed to be obviously correct, not
 123    to be efficient. */
 124 static bool
 125 prev_region (unsigned int pattern, unsigned int offset,
 126              unsigned long int *start, unsigned long int *width)
 127 {
 128   unsigned int i;
 129
 130   assert (offset <= UINT_BIT);
 131   for (i = offset; i-- > 0;)
 132     if (pattern & (1u << i))
 133       {
 134         *start = i;
 135         *width = 1;
 136         while (i-- > 0 && pattern & (1u << i))
 137           {
 138             ++*width;
 139             --*start;
 140           }
 141         return true;
 142       }
 143   return false;
 144 }
 145
 146 /* Searches the bits in PATTERN from right to left starting from
 147    bit OFFSET.  Returns the bit index of the first 1-bit found,
 148    or ULONG_MAX if none is found. */
 149 static unsigned long int
 150 next_1bit (unsigned int pattern, unsigned int offset)
 151 {
 152   for (; offset < UINT_BIT; offset++)
 153     if (pattern & (1u << offset))
 154       return offset;
 155   return ULONG_MAX;
 156 }
 157
 158 /* Prints the regions in RS to stdout. */
 159 static void UNUSED
 160 print_regions (const struct range_set *rs)
 161 {
 162   const struct range_set_node *node;
 163
 164   printf ("result:");
 165   RANGE_SET_FOR_EACH (node, rs)
 166     printf (" (%lu,%lu)",
 167             range_set_node_get_start (node), range_set_node_get_end (node));
 168   printf ("\n");
 169 }
 170
 171 /* Checks that the regions in RS match the bits in PATTERN. */
 172 static void
 173 check_pattern (const struct range_set *rs, unsigned int pattern)
 174 {
 175   const struct range_set_node *node;
 176   unsigned long int start, width;
 177   unsigned long int s1, s2;
 178   int i;
 179
 180   for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL),
 181          start = width = 0;
 182        next_region (pattern, start + width, &start, &width);
 183        node = range_set_next (rs, node))
 184     {
 185       check (node != NULL);
 186       check (range_set_node_get_start (node) == start);
 187       check (range_set_node_get_end (node) == start + width);
 188       check (range_set_node_get_width (node) == width);
 189     }
 190   check (node == NULL);
 191
 192   for (node = rand () % 2 ? range_set_last (rs) : range_set_prev (rs, NULL),
 193          start = UINT_BIT;
 194        prev_region (pattern, start, &start, &width);
 195        node = range_set_prev (rs, node))
 196     {
 197       check (node != NULL);
 198       check (range_set_node_get_start (node) == start);
 199       check (range_set_node_get_end (node) == start + width);
 200       check (range_set_node_get_width (node) == width);
 201     }
 202   check (node == NULL);
 203
 204   /* Scan from all possible positions, resetting the cache each
 205      time, to ensure that we get the correct answers without
 206      caching. */
 207   for (start = 0; start <= 32; start++)
 208     {
 209       struct range_set *nonconst_rs = CONST_CAST (struct range_set *, rs);
 210       nonconst_rs->cache_end = 0;
 211       s1 = range_set_scan (rs, start);
 212       s2 = next_1bit (pattern, start);
 213       check (s1 == s2);
 214     }
 215
 216   /* Scan in forward order to exercise expected cache behavior. */
 217   for (s1 = range_set_scan (rs, 0), s2 = next_1bit (pattern, 0); ;
 218        s1 = range_set_scan (rs, s1 + 1), s2 = next_1bit (pattern, s2 + 1))
 219     {
 220       check (s1 == s2);
 221       if (s1 == ULONG_MAX)
 222         break;
 223     }
 224
 225   /* Scan in random order to frustrate cache. */
 226   for (i = 0; i < 32; i++)
 227     {
 228       start = rand () % 32;
 229       s1 = range_set_scan (rs, start);
 230       s2 = next_1bit (pattern, start);
 231       check (s1 == s2);
 232     }
 233
 234   /* Test range_set_scan() with negative cache. */
 235   check (!range_set_contains (rs, 999));
 236   check (range_set_scan (rs, 1111) == ULONG_MAX);
 237
 238   for (i = 0; i < UINT_BIT; i++)
 239     check (range_set_contains (rs, i) == ((pattern & (1u << i)) != 0));
 240   check (!range_set_contains (rs,
 241                               UINT_BIT + rand () % (ULONG_MAX - UINT_BIT)));
 242
 243   check (range_set_is_empty (rs) == (pattern == 0));
 244 }
 245
 246 /* Creates and returns a range set that contains regions for the
 247    bits set in PATTERN. */
 248 static struct range_set *
 249 make_pattern (unsigned int pattern)
 250 {
 251   unsigned long int start = 0;
 252   unsigned long int width = 0;
 253   struct range_set *rs = range_set_create_pool (NULL);
 254   while (next_region (pattern, start + width, &start, &width))
 255     range_set_set1 (rs, start, width);
 256   check_pattern (rs, pattern);
 257   return rs;
 258 }
 259
 260 /* Returns an unsigned int with bits OFS...OFS+N (exclusive)
 261    set to 1, other bits set to 0. */
 262 static unsigned int
 263 bit_range (unsigned int ofs, unsigned int n)
 264 {
 265   assert (ofs < UINT_BIT);
 266   assert (n <= UINT_BIT);
 267   assert (ofs + n <= UINT_BIT);
 268
 269   return n < UINT_BIT ? ((1u << n) - 1) << ofs : UINT_MAX;
 270 }
 271 \f
 272 /* Tests inserting all possible patterns into all possible range
 273    sets (up to a small maximum number of bits). */
 274 static void
 275 test_insert (void)
 276 {
 277   const int positions = 9;
 278   unsigned int init_pat;
 279   int i, j;
 280
 281   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 282     for (i = 0; i < positions + 1; i++)
 283       for (j = i; j <= positions + 1; j++)
 284         {
 285           struct range_set *rs, *rs2;
 286           unsigned int final_pat;
 287
 288           rs = make_pattern (init_pat);
 289           range_set_set1 (rs, i, j - i);
 290           final_pat = init_pat | bit_range (i, j - i);
 291           check_pattern (rs, final_pat);
 292           rs2 = range_set_clone (rs, NULL);
 293           check_pattern (rs2, final_pat);
 294           range_set_destroy (rs);
 295           range_set_destroy (rs2);
 296         }
 297 }
 298
 299 /* Tests deleting all possible patterns from all possible range
 300    sets (up to a small maximum number of bits). */
 301 static void
 302 test_delete (void)
 303 {
 304   const int positions = 9;
 305   unsigned int init_pat;
 306   int i, j;
 307
 308   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 309     for (i = 0; i < positions + 1; i++)
 310       for (j = i; j <= positions + 1; j++)
 311         {
 312           struct range_set *rs;
 313           unsigned int final_pat;
 314
 315           rs = make_pattern (init_pat);
 316           range_set_set0 (rs, i, j - i);
 317           final_pat = init_pat & ~bit_range (i, j - i);
 318           check_pattern (rs, final_pat);
 319           range_set_destroy (rs);
 320         }
 321 }
 322
 323 /* Tests all possible allocation in all possible range sets (up
 324    to a small maximum number of bits). */
 325 static void
 326 test_allocate (void)
 327 {
 328   const int positions = 9;
 329   unsigned int init_pat;
 330   int request;
 331
 332   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 333     for (request = 1; request <= positions + 1; request++)
 334       {
 335         struct range_set *rs;
 336         unsigned long int start, width, expect_start, expect_width;
 337         bool success, expect_success;
 338         unsigned int final_pat;
 339         int i;
 340
 341         /* Figure out expected results. */
 342         expect_success = false;
 343         expect_start = expect_width = 0;
 344         final_pat = init_pat;
 345         for (i = 0; i < positions; i++)
 346           if (init_pat & (1u << i))
 347             {
 348               expect_success = true;
 349               expect_start = i;
 350               expect_width = count_one_bits (init_pat >> i);
 351               if (expect_width > request)
 352                 expect_width = request;
 353               final_pat &= ~bit_range (expect_start, expect_width);
 354               break;
 355             }
 356
 357         /* Test. */
 358         rs = make_pattern (init_pat);
 359         success = range_set_allocate (rs, request, &start, &width);
 360         check_pattern (rs, final_pat);
 361         range_set_destroy (rs);
 362
 363         /* Check results. */
 364         check (success == expect_success);
 365         if (expect_success)
 366           {
 367             check (start == expect_start);
 368             check (width == expect_width);
 369           }
 370       }
 371 }
 372
 373 /* Tests all possible full allocations in all possible range sets
 374    (up to a small maximum number of bits). */
 375 static void
 376 test_allocate_fully (void)
 377 {
 378   const int positions = 9;
 379   unsigned int init_pat;
 380   int request;
 381
 382   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 383     for (request = 1; request <= positions + 1; request++)
 384       {
 385         struct range_set *rs;
 386         unsigned long int start, expect_start;
 387         bool success, expect_success;
 388         unsigned int final_pat;
 389         int i;
 390
 391         /* Figure out expected results. */
 392         expect_success = false;
 393         expect_start = 0;
 394         final_pat = init_pat;
 395         for (i = 0; i < positions - request + 1; i++)
 396           {
 397             int j;
 398
 399             final_pat = init_pat;
 400             for (j = i; j < i + request; j++)
 401               {
 402                 if (!(init_pat & (1u << j)))
 403                   goto next;
 404                 final_pat &= ~(1u << j);
 405               }
 406
 407             expect_success = true;
 408             expect_start = i;
 409             break;
 410           next:
 411             final_pat = init_pat;
 412           }
 413
 414         /* Test. */
 415         rs = make_pattern (init_pat);
 416         success = range_set_allocate_fully (rs, request, &start);
 417         check_pattern (rs, final_pat);
 418         range_set_destroy (rs);
 419
 420         /* Check results. */
 421         check (success == expect_success);
 422         if (expect_success)
 423           check (start == expect_start);
 424       }
 425 }
 426
 427 /* Tests freeing a range set through a pool. */
 428 static void
 429 test_pool (void)
 430 {
 431   struct pool *pool;
 432   struct range_set *rs;
 433
 434   /* Destroy the range set, then the pool.
 435      Makes sure that this doesn't cause a double-free. */
 436   pool = pool_create ();
 437   rs = range_set_create_pool (pool);
 438   range_set_set1 (rs, 1, 10);
 439   range_set_destroy (rs);
 440   pool_destroy (pool);
 441
 442   /* Just destroy the pool.
 443      Makes sure that this doesn't cause a leak. */
 444   pool = pool_create ();
 445   rs = range_set_create_pool (pool);
 446   range_set_set1 (rs, 1, 10);
 447   pool_destroy (pool);
 448 }
 449
 450 /* Tests range_set_destroy(NULL). */
 451 static void
 452 test_destroy_null (void)
 453 {
 454   range_set_destroy (NULL);
 455 }
 456 \f
 457 /* Main program. */
 458
 459 struct test
 460   {
 461     const char *name;
 462     const char *description;
 463     void (*function) (void);
 464   };
 465
 466 static const struct test tests[] =
 467   {
 468     {
 469       "insert",
 470       "insert",
 471       test_insert
 472     },
 473     {
 474       "delete",
 475       "delete",
 476       test_delete
 477     },
 478     {
 479       "allocate",
 480       "allocate",
 481       test_allocate
 482     },
 483     {
 484       "allocate-fully",
 485       "allocate_fully",
 486       test_allocate_fully
 487     },
 488     {
 489       "pool",
 490       "pool",
 491       test_pool
 492     },
 493     {
 494       "destroy-null",
 495       "destroy null",
 496       test_destroy_null
 497     },
 498   };
 499
 500 enum { N_TESTS = sizeof tests / sizeof *tests };
 501
 502 int
 503 main (int argc, char *argv[])
 504 {
 505   int i;
 506
 507   if (argc != 2)
 508     {
 509       fprintf (stderr, "exactly one argument required; use --help for help\n");
 510       return EXIT_FAILURE;
 511     }
 512   else if (!strcmp (argv[1], "--help"))
 513     {
 514       printf ("%s: test range set library\n"
 515               "usage: %s TEST-NAME\n"
 516               "where TEST-NAME is one of the following:\n",
 517               argv[0], argv[0]);
 518       for (i = 0; i < N_TESTS; i++)
 519         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 520       return 0;
 521     }
 522   else
 523     {
 524       for (i = 0; i < N_TESTS; i++)
 525         if (!strcmp (argv[1], tests[i].name))
 526           {
 527             tests[i].function ();
 528             return 0;
 529           }
 530
 531       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 532       return EXIT_FAILURE;
 533     }
 534 }