pintos-os.org Git - pspp/blob - tests/libpspp/range-set-test.c

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