tests/libpspp/range-set-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 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 /* Currently running test. */
  44 static const char *test_name;
  45
  46 /* Exit with a failure code.
  47    (Place a breakpoint on this function while debugging.) */
  48 static void
  49 check_die (void)
  50 {
  51   exit (EXIT_FAILURE);
  52 }
  53
  54 /* If OK is not true, prints a message about failure on the
  55    current source file and the given LINE and terminates. */
  56 static void
  57 check_func (bool ok, int line)
  58 {
  59   if (!ok)
  60     {
  61       printf ("Check failed in %s test at %s, line %d\n",
  62               test_name, __FILE__, line);
  63       check_die ();
  64     }
  65 }
  66
  67 /* Verifies that EXPR evaluates to true.
  68    If not, prints a message citing the calling line number and
  69    terminates. */
  70 #define check(EXPR) check_func ((EXPR), __LINE__)
  71 \f
  72 /* A contiguous region. */
  73 struct region
  74   {
  75     unsigned long int start;    /* Start of region. */
  76     unsigned long int end;      /* One past the end. */
  77   };
  78
  79 /* Number of bits in an unsigned int. */
  80 #define UINT_BIT (CHAR_BIT * sizeof (unsigned int))
  81
  82 /* Returns the number of contiguous 1-bits in X starting from bit
  83    0.
  84    This implementation is designed to be obviously correct, not
  85    to be efficient. */
  86 static int
  87 count_one_bits (unsigned long int x)
  88 {
  89   int count = 0;
  90   while (x & 1)
  91     {
  92       count++;
  93       x >>= 1;
  94     }
  95   return count;
  96 }
  97
  98 /* Searches the bits in PATTERN from right to left starting from
  99    bit OFFSET for one or more 1-bits.  If any are found, sets
 100    *START to the bit index of the first and *WIDTH to the number
 101    of contiguous 1-bits and returns true.  Otherwise, returns
 102    false.
 103    This implementation is designed to be obviously correct, not
 104    to be efficient. */
 105 static bool
 106 next_region (unsigned int pattern, unsigned int offset,
 107              unsigned long int *start, unsigned long int *width)
 108 {
 109   unsigned int i;
 110
 111   assert (offset <= UINT_BIT);
 112   for (i = offset; i < UINT_BIT; i++)
 113     if (pattern & (1u << i))
 114       {
 115         *start = i;
 116         *width = count_one_bits (pattern >> i);
 117         return true;
 118       }
 119   return false;
 120 }
 121
 122 /* Searches the bits in PATTERN from right to left starting from
 123    bit OFFSET.  Returns the bit index of the first 1-bit found,
 124    or ULONG_MAX if none is found. */
 125 static unsigned long int
 126 next_1bit (unsigned int pattern, unsigned int offset)
 127 {
 128   for (; offset < UINT_BIT; offset++)
 129     if (pattern & (1u << offset))
 130       return offset;
 131   return ULONG_MAX;
 132 }
 133
 134 /* Prints the regions in RS to stdout. */
 135 static void UNUSED
 136 print_regions (const struct range_set *rs)
 137 {
 138   const struct range_set_node *node;
 139
 140   printf ("result:");
 141   for (node = range_set_first (rs); node != NULL;
 142        node = range_set_next (rs, node))
 143     printf (" (%lu,%lu)",
 144             range_set_node_get_start (node), range_set_node_get_end (node));
 145   printf ("\n");
 146 }
 147
 148 /* Checks that the regions in RS match the bits in PATTERN. */
 149 static void
 150 check_pattern (const struct range_set *rs, unsigned int pattern)
 151 {
 152   const struct range_set_node *node;
 153   unsigned long int start, width;
 154   unsigned long int s1, s2;
 155   int i;
 156
 157   for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL),
 158          start = width = 0;
 159        next_region (pattern, start + width, &start, &width);
 160        node = range_set_next (rs, node))
 161     {
 162       check (node != NULL);
 163       check (range_set_node_get_start (node) == start);
 164       check (range_set_node_get_end (node) == start + width);
 165       check (range_set_node_get_width (node) == width);
 166     }
 167   check (node == NULL);
 168
 169   /* Scan from all possible positions, resetting the cache each
 170      time, to ensure that we get the correct answers without
 171      caching. */
 172   for (start = 0; start <= 32; start++)
 173     {
 174       struct range_set *nonconst_rs = (struct range_set *) rs;
 175       nonconst_rs->cache_end = 0;
 176       s1 = range_set_scan (rs, start);
 177       s2 = next_1bit (pattern, start);
 178       check (s1 == s2);
 179     }
 180
 181   /* Scan in forward order to exercise expected cache behavior. */
 182   for (s1 = range_set_scan (rs, 0), s2 = next_1bit (pattern, 0); ;
 183        s1 = range_set_scan (rs, s1 + 1), s2 = next_1bit (pattern, s2 + 1))
 184     {
 185       check (s1 == s2);
 186       if (s1 == ULONG_MAX)
 187         break;
 188     }
 189
 190   /* Scan in random order to frustrate cache. */
 191   for (i = 0; i < 32; i++)
 192     {
 193       start = rand () % 32;
 194       s1 = range_set_scan (rs, start);
 195       s2 = next_1bit (pattern, start);
 196       check (s1 == s2);
 197     }
 198
 199   /* Test range_set_scan() with negative cache. */
 200   check (!range_set_contains (rs, 999));
 201   check (range_set_scan (rs, 1111) == ULONG_MAX);
 202
 203   for (i = 0; i < UINT_BIT; i++)
 204     check (range_set_contains (rs, i) == ((pattern & (1u << i)) != 0));
 205   check (!range_set_contains (rs,
 206                               UINT_BIT + rand () % (ULONG_MAX - UINT_BIT)));
 207
 208   check (range_set_is_empty (rs) == (pattern == 0));
 209 }
 210
 211 /* Creates and returns a range set that contains regions for the
 212    bits set in PATTERN. */
 213 static struct range_set *
 214 make_pattern (unsigned int pattern)
 215 {
 216   unsigned long int start = 0;
 217   unsigned long int width = 0;
 218   struct range_set *rs = range_set_create_pool (NULL);
 219   while (next_region (pattern, start + width, &start, &width))
 220     range_set_insert (rs, start, width);
 221   check_pattern (rs, pattern);
 222   return rs;
 223 }
 224
 225 /* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
 226    set to 1, other bits set to 0. */
 227 static unsigned int
 228 bit_range (unsigned int ofs, unsigned int cnt)
 229 {
 230   assert (ofs < UINT_BIT);
 231   assert (cnt <= UINT_BIT);
 232   assert (ofs + cnt <= UINT_BIT);
 233
 234   return cnt < UINT_BIT ? ((1u << cnt) - 1) << ofs : UINT_MAX;
 235 }
 236 \f
 237 /* Tests inserting all possible patterns into all possible range
 238    sets (up to a small maximum number of bits). */
 239 static void
 240 test_insert (void)
 241 {
 242   const int positions = 9;
 243   unsigned int init_pat;
 244   int i, j;
 245
 246   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 247     for (i = 0; i < positions + 1; i++)
 248       for (j = i; j <= positions + 1; j++)
 249         {
 250           struct range_set *rs, *rs2;
 251           unsigned int final_pat;
 252
 253           rs = make_pattern (init_pat);
 254           range_set_insert (rs, i, j - i);
 255           final_pat = init_pat | bit_range (i, j - i);
 256           check_pattern (rs, final_pat);
 257           rs2 = range_set_clone (rs, NULL);
 258           check_pattern (rs2, final_pat);
 259           range_set_destroy (rs);
 260           range_set_destroy (rs2);
 261         }
 262 }
 263
 264 /* Tests deleting all possible patterns from all possible range
 265    sets (up to a small maximum number of bits). */
 266 static void
 267 test_delete (void)
 268 {
 269   const int positions = 9;
 270   unsigned int init_pat;
 271   int i, j;
 272
 273   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 274     for (i = 0; i < positions + 1; i++)
 275       for (j = i; j <= positions + 1; j++)
 276         {
 277           struct range_set *rs;
 278           unsigned int final_pat;
 279
 280           rs = make_pattern (init_pat);
 281           range_set_delete (rs, i, j - i);
 282           final_pat = init_pat & ~bit_range (i, j - i);
 283           check_pattern (rs, final_pat);
 284           range_set_destroy (rs);
 285         }
 286 }
 287
 288 /* Tests all possible allocation in all possible range sets (up
 289    to a small maximum number of bits). */
 290 static void
 291 test_allocate (void)
 292 {
 293   const int positions = 9;
 294   unsigned int init_pat;
 295   int request;
 296
 297   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 298     for (request = 1; request <= positions + 1; request++)
 299       {
 300         struct range_set *rs;
 301         unsigned long int start, width, expect_start, expect_width;
 302         bool success, expect_success;
 303         unsigned int final_pat;
 304         int i;
 305
 306         /* Figure out expected results. */
 307         expect_success = false;
 308         expect_start = expect_width = 0;
 309         final_pat = init_pat;
 310         for (i = 0; i < positions; i++)
 311           if (init_pat & (1u << i))
 312             {
 313               expect_success = true;
 314               expect_start = i;
 315               expect_width = count_one_bits (init_pat >> i);
 316               if (expect_width > request)
 317                 expect_width = request;
 318               final_pat &= ~bit_range (expect_start, expect_width);
 319               break;
 320             }
 321
 322         /* Test. */
 323         rs = make_pattern (init_pat);
 324         success = range_set_allocate (rs, request, &start, &width);
 325         check_pattern (rs, final_pat);
 326         range_set_destroy (rs);
 327
 328         /* Check results. */
 329         check (success == expect_success);
 330         if (expect_success)
 331           {
 332             check (start == expect_start);
 333             check (width == expect_width);
 334           }
 335       }
 336 }
 337
 338 /* Tests all possible full allocations in all possible range sets
 339    (up to a small maximum number of bits). */
 340 static void
 341 test_allocate_fully (void)
 342 {
 343   const int positions = 9;
 344   unsigned int init_pat;
 345   int request;
 346
 347   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 348     for (request = 1; request <= positions + 1; request++)
 349       {
 350         struct range_set *rs;
 351         unsigned long int start, expect_start;
 352         bool success, expect_success;
 353         unsigned int final_pat;
 354         int i;
 355
 356         /* Figure out expected results. */
 357         expect_success = false;
 358         expect_start = 0;
 359         final_pat = init_pat;
 360         for (i = 0; i < positions - request + 1; i++)
 361           {
 362             int j;
 363
 364             final_pat = init_pat;
 365             for (j = i; j < i + request; j++)
 366               {
 367                 if (!(init_pat & (1u << j)))
 368                   goto next;
 369                 final_pat &= ~(1u << j);
 370               }
 371
 372             expect_success = true;
 373             expect_start = i;
 374             break;
 375           next:
 376             final_pat = init_pat;
 377           }
 378
 379         /* Test. */
 380         rs = make_pattern (init_pat);
 381         success = range_set_allocate_fully (rs, request, &start);
 382         check_pattern (rs, final_pat);
 383         range_set_destroy (rs);
 384
 385         /* Check results. */
 386         check (success == expect_success);
 387         if (expect_success)
 388           check (start == expect_start);
 389       }
 390 }
 391
 392 /* Tests freeing a range set through a pool. */
 393 static void
 394 test_pool (void)
 395 {
 396   struct pool *pool;
 397   struct range_set *rs;
 398
 399   /* Destroy the range set, then the pool.
 400      Makes sure that this doesn't cause a double-free. */
 401   pool = pool_create ();
 402   rs = range_set_create_pool (pool);
 403   range_set_insert (rs, 1, 10);
 404   range_set_destroy (rs);
 405   pool_destroy (pool);
 406
 407   /* Just destroy the pool.
 408      Makes sure that this doesn't cause a leak. */
 409   pool = pool_create ();
 410   rs = range_set_create_pool (pool);
 411   range_set_insert (rs, 1, 10);
 412   pool_destroy (pool);
 413 }
 414
 415 /* Tests range_set_destroy(NULL). */
 416 static void
 417 test_destroy_null (void)
 418 {
 419   range_set_destroy (NULL);
 420 }
 421 \f
 422 /* Main program. */
 423
 424 /* Runs TEST_FUNCTION and prints a message about NAME. */
 425 static void
 426 run_test (void (*test_function) (void), const char *name)
 427 {
 428   test_name = name;
 429   putchar ('.');
 430   fflush (stdout);
 431   test_function ();
 432 }
 433
 434 int
 435 main (void)
 436 {
 437   run_test (test_insert, "insert");
 438   run_test (test_delete, "delete");
 439   run_test (test_allocate, "allocate");
 440   run_test (test_allocate_fully, "allocate_fully");
 441   run_test (test_pool, "pool");
 442   run_test (test_destroy_null, "destroy null");
 443   putchar ('\n');
 444
 445   return 0;
 446 }