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 /* Prints the regions in RS to stdout. */
 123 static void UNUSED
 124 print_regions (const struct range_set *rs)
 125 {
 126   const struct range_set_node *node;
 127
 128   printf ("result:");
 129   for (node = range_set_first (rs); node != NULL;
 130        node = range_set_next (rs, node))
 131     printf (" (%lu,%lu)",
 132             range_set_node_get_start (node), range_set_node_get_end (node));
 133   printf ("\n");
 134 }
 135
 136 /* Checks that the regions in RS match the bits in PATTERN. */
 137 static void
 138 check_pattern (const struct range_set *rs, unsigned int pattern)
 139 {
 140   const struct range_set_node *node;
 141   unsigned long int start, width;
 142   int i;
 143
 144   for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL),
 145          start = width = 0;
 146        next_region (pattern, start + width, &start, &width);
 147        node = range_set_next (rs, node))
 148     {
 149       check (node != NULL);
 150       check (range_set_node_get_start (node) == start);
 151       check (range_set_node_get_end (node) == start + width);
 152       check (range_set_node_get_width (node) == width);
 153     }
 154   check (node == NULL);
 155
 156   for (i = 0; i < UINT_BIT; i++)
 157     check (range_set_contains (rs, i) == ((pattern & (1u << i)) != 0));
 158   check (!range_set_contains (rs,
 159                               UINT_BIT + rand () % (ULONG_MAX - UINT_BIT)));
 160
 161   check (range_set_is_empty (rs) == (pattern == 0));
 162 }
 163
 164 /* Creates and returns a range set that contains regions for the
 165    bits set in PATTERN. */
 166 static struct range_set *
 167 make_pattern (unsigned int pattern)
 168 {
 169   unsigned long int start = 0;
 170   unsigned long int width = 0;
 171   struct range_set *rs = range_set_create_pool (NULL);
 172   while (next_region (pattern, start + width, &start, &width))
 173     range_set_insert (rs, start, width);
 174   check_pattern (rs, pattern);
 175   return rs;
 176 }
 177
 178 /* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
 179    set to 1, other bits set to 0. */
 180 static unsigned int
 181 bit_range (unsigned int ofs, unsigned int cnt)
 182 {
 183   assert (ofs < UINT_BIT);
 184   assert (cnt <= UINT_BIT);
 185   assert (ofs + cnt <= UINT_BIT);
 186
 187   return cnt < UINT_BIT ? ((1u << cnt) - 1) << ofs : UINT_MAX;
 188 }
 189 \f
 190 /* Tests inserting all possible patterns into all possible range
 191    sets (up to a small maximum number of bits). */
 192 static void
 193 test_insert (void)
 194 {
 195   const int positions = 9;
 196   unsigned int init_pat;
 197   int i, j;
 198
 199   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 200     for (i = 0; i < positions + 1; i++)
 201       for (j = i; j <= positions + 1; j++)
 202         {
 203           struct range_set *rs, *rs2;
 204           unsigned int final_pat;
 205
 206           rs = make_pattern (init_pat);
 207           range_set_insert (rs, i, j - i);
 208           final_pat = init_pat | bit_range (i, j - i);
 209           check_pattern (rs, final_pat);
 210           rs2 = range_set_clone (rs, NULL);
 211           check_pattern (rs2, final_pat);
 212           range_set_destroy (rs);
 213           range_set_destroy (rs2);
 214         }
 215 }
 216
 217 /* Tests deleting all possible patterns from all possible range
 218    sets (up to a small maximum number of bits). */
 219 static void
 220 test_delete (void)
 221 {
 222   const int positions = 9;
 223   unsigned int init_pat;
 224   int i, j;
 225
 226   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 227     for (i = 0; i < positions + 1; i++)
 228       for (j = i; j <= positions + 1; j++)
 229         {
 230           struct range_set *rs;
 231           unsigned int final_pat;
 232
 233           rs = make_pattern (init_pat);
 234           range_set_delete (rs, i, j - i);
 235           final_pat = init_pat & ~bit_range (i, j - i);
 236           check_pattern (rs, final_pat);
 237           range_set_destroy (rs);
 238         }
 239 }
 240
 241 /* Tests all possible allocation in all possible range sets (up
 242    to a small maximum number of bits). */
 243 static void
 244 test_allocate (void)
 245 {
 246   const int positions = 9;
 247   unsigned int init_pat;
 248   int request;
 249
 250   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 251     for (request = 1; request <= positions + 1; request++)
 252       {
 253         struct range_set *rs;
 254         unsigned long int start, width, expect_start, expect_width;
 255         bool success, expect_success;
 256         unsigned int final_pat;
 257         int i;
 258
 259         /* Figure out expected results. */
 260         expect_success = false;
 261         expect_start = expect_width = 0;
 262         final_pat = init_pat;
 263         for (i = 0; i < positions; i++)
 264           if (init_pat & (1u << i))
 265             {
 266               expect_success = true;
 267               expect_start = i;
 268               expect_width = count_one_bits (init_pat >> i);
 269               if (expect_width > request)
 270                 expect_width = request;
 271               final_pat &= ~bit_range (expect_start, expect_width);
 272               break;
 273             }
 274
 275         /* Test. */
 276         rs = make_pattern (init_pat);
 277         success = range_set_allocate (rs, request, &start, &width);
 278         check_pattern (rs, final_pat);
 279         range_set_destroy (rs);
 280
 281         /* Check results. */
 282         check (success == expect_success);
 283         if (expect_success)
 284           {
 285             check (start == expect_start);
 286             check (width == expect_width);
 287           }
 288       }
 289 }
 290
 291 /* Tests all possible full allocations in all possible range sets
 292    (up to a small maximum number of bits). */
 293 static void
 294 test_allocate_fully (void)
 295 {
 296   const int positions = 9;
 297   unsigned int init_pat;
 298   int request;
 299
 300   for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 301     for (request = 1; request <= positions + 1; request++)
 302       {
 303         struct range_set *rs;
 304         unsigned long int start, expect_start;
 305         bool success, expect_success;
 306         unsigned int final_pat;
 307         int i;
 308
 309         /* Figure out expected results. */
 310         expect_success = false;
 311         expect_start = 0;
 312         final_pat = init_pat;
 313         for (i = 0; i < positions - request + 1; i++)
 314           {
 315             int j;
 316
 317             final_pat = init_pat;
 318             for (j = i; j < i + request; j++)
 319               {
 320                 if (!(init_pat & (1u << j)))
 321                   goto next;
 322                 final_pat &= ~(1u << j);
 323               }
 324
 325             expect_success = true;
 326             expect_start = i;
 327             break;
 328           next:
 329             final_pat = init_pat;
 330           }
 331
 332         /* Test. */
 333         rs = make_pattern (init_pat);
 334         success = range_set_allocate_fully (rs, request, &start);
 335         check_pattern (rs, final_pat);
 336         range_set_destroy (rs);
 337
 338         /* Check results. */
 339         check (success == expect_success);
 340         if (expect_success)
 341           check (start == expect_start);
 342       }
 343 }
 344
 345 /* Tests freeing a range set through a pool. */
 346 static void
 347 test_pool (void)
 348 {
 349   struct pool *pool;
 350   struct range_set *rs;
 351
 352   /* Destroy the range set, then the pool.
 353      Makes sure that this doesn't cause a double-free. */
 354   pool = pool_create ();
 355   rs = range_set_create_pool (pool);
 356   range_set_insert (rs, 1, 10);
 357   range_set_destroy (rs);
 358   pool_destroy (pool);
 359
 360   /* Just destroy the pool.
 361      Makes sure that this doesn't cause a leak. */
 362   pool = pool_create ();
 363   rs = range_set_create_pool (pool);
 364   range_set_insert (rs, 1, 10);
 365   pool_destroy (pool);
 366 }
 367
 368 /* Tests range_set_destroy(NULL). */
 369 static void
 370 test_destroy_null (void)
 371 {
 372   range_set_destroy (NULL);
 373 }
 374 \f
 375 /* Main program. */
 376
 377 /* Runs TEST_FUNCTION and prints a message about NAME. */
 378 static void
 379 run_test (void (*test_function) (void), const char *name)
 380 {
 381   test_name = name;
 382   putchar ('.');
 383   fflush (stdout);
 384   test_function ();
 385 }
 386
 387 int
 388 main (void)
 389 {
 390   run_test (test_insert, "insert");
 391   run_test (test_delete, "delete");
 392   run_test (test_allocate, "allocate");
 393   run_test (test_allocate_fully, "allocate_fully");
 394   run_test (test_pool, "pool");
 395   run_test (test_destroy_null, "destroy null");
 396   putchar ('\n');
 397
 398   return 0;
 399 }