pintos-os.org Git - pspp/blob - tests/libpspp/range-tower-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-tower.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-tower.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-tower.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 "gl/minmax.h"
  42 #include "gl/xalloc.h"
  43 \f
  44 /* Exit with a failure code.
  45    (Place a breakpoint on this function while debugging.) */
  46 static void
  47 check_die (void)
  48 {
  49   abort ();
  50 }
  51
  52 /* If OK is not true, prints a message about failure on the
  53    current source file and the given LINE and terminates. */
  54 static void
  55 check_func (bool ok, int line)
  56 {
  57   if (!ok)
  58     {
  59       fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
  60       check_die ();
  61     }
  62 }
  63
  64 /* Verifies that EXPR evaluates to true.
  65    If not, prints a message citing the calling line number and
  66    terminates. */
  67 #define check(EXPR) check_func ((EXPR), __LINE__)
  68 \f
  69 /* A contiguous region. */
  70 struct region
  71   {
  72     unsigned long int start;    /* Start of region. */
  73     unsigned long int end;      /* One past the end. */
  74   };
  75
  76 /* Number of bits in an unsigned int. */
  77 #define UINT_BIT (CHAR_BIT * sizeof (unsigned int))
  78
  79 /* Returns the number of contiguous 1-bits in X starting from bit
  80    0.
  81    This implementation is designed to be obviously correct, not
  82    to be efficient. */
  83 static int
  84 count_one_bits (unsigned long int x)
  85 {
  86   int count = 0;
  87   while (x & 1)
  88     {
  89       count++;
  90       x >>= 1;
  91     }
  92   return count;
  93 }
  94
  95 /* Searches the bits in PATTERN from right to left starting from
  96    bit OFFSET for one or more 1-bits.  If any are found, sets
  97    *START to the bit index of the first and *WIDTH to the number
  98    of contiguous 1-bits and returns true.  Otherwise, returns
  99    false.
 100    This implementation is designed to be obviously correct, not
 101    to be efficient. */
 102 static bool
 103 next_region (unsigned int pattern, unsigned int offset,
 104              unsigned long int *start, unsigned long int *width)
 105 {
 106   unsigned int i;
 107
 108   assert (offset <= UINT_BIT);
 109   for (i = offset; i < UINT_BIT; i++)
 110     if (pattern & (1u << i))
 111       {
 112         *start = i;
 113         *width = count_one_bits (pattern >> i);
 114         return true;
 115       }
 116   return false;
 117 }
 118
 119 /* Searches the bits in PATTERN from left to right starting from
 120    just beyond bit OFFSET for one or more 1-bits.  If any are
 121    found, sets *START to the bit index of the first and *WIDTH to
 122    the number of contiguous 1-bits and returns true.  Otherwise,
 123    returns false.
 124    This implementation is designed to be obviously correct, not
 125    to be efficient. */
 126 static bool
 127 prev_region (unsigned int pattern, unsigned int offset,
 128              unsigned long int *start, unsigned long int *width)
 129 {
 130   unsigned int i;
 131
 132   assert (offset <= UINT_BIT);
 133   for (i = offset; i-- > 0;)
 134     if (pattern & (1u << i))
 135       {
 136         *start = i;
 137         *width = 1;
 138         while (i-- > 0 && pattern & (1u << i))
 139           {
 140             ++*width;
 141             --*start;
 142           }
 143         return true;
 144       }
 145   return false;
 146 }
 147
 148 /* Searches the bits in PATTERN from right to left starting from
 149    bit OFFSET.  Returns the bit index of the first 1-bit found,
 150    or ULONG_MAX if none is found. */
 151 static unsigned long int
 152 next_1bit (unsigned int pattern, unsigned int offset,
 153            unsigned long int pattern_offset)
 154 {
 155   for (; offset < UINT_BIT; offset++)
 156     if (pattern & (1u << offset))
 157       return offset + pattern_offset;
 158   return ULONG_MAX;
 159 }
 160
 161 static void
 162 print_structure (const struct abt_node *node_)
 163 {
 164   struct range_tower_node *node;
 165
 166   if (node_ == NULL)
 167     return;
 168   node = ABT_DATA (node_, struct range_tower_node, abt_node);
 169   printf ("%lu+%lu/%d", node->n_zeros, node->n_ones, node->abt_node.level);
 170   if (node->abt_node.down[0] || node->abt_node.down[1])
 171     {
 172       printf ("(");
 173       print_structure (node->abt_node.down[0]);
 174       printf (",");
 175       print_structure (node->abt_node.down[1]);
 176       printf (")");
 177     }
 178 }
 179
 180 /* Prints the regions in RT to stdout. */
 181 static void UNUSED
 182 print_regions (const struct range_tower *rt)
 183 {
 184   const struct range_tower_node *node;
 185
 186   printf ("contents:");
 187   for (node = range_tower_first__ (rt); node != NULL;
 188        node = range_tower_next__ (rt, node))
 189     printf (" (%lu,%lu)", node->n_zeros, node->n_ones);
 190   printf ("\n");
 191   printf ("structure:");
 192   print_structure (rt->abt.root);
 193   printf ("\n");
 194 }
 195
 196 static void
 197 check_tree (const struct abt_node *abt_node, unsigned long int *subtree_width)
 198 {
 199   const struct range_tower_node *node = range_tower_node_from_abt__ (abt_node);
 200   unsigned long int left_width, right_width;
 201
 202   if (node == NULL)
 203     {
 204       *subtree_width = 0;
 205       return;
 206     }
 207
 208   check_tree (node->abt_node.down[0], &left_width);
 209   check_tree (node->abt_node.down[1], &right_width);
 210
 211   *subtree_width = node->n_zeros + node->n_ones + left_width + right_width;
 212   check (node->subtree_width == *subtree_width);
 213 }
 214
 215 /* Checks that the regions in RT match the bits in PATTERN. */
 216 static void
 217 check_pattern (const struct range_tower *rt, unsigned int pattern,
 218                unsigned long int offset)
 219 {
 220   const struct range_tower_node *node;
 221   unsigned long int start, start2, width;
 222   unsigned long int tree_width;
 223   unsigned long int s1, s2;
 224   int i;
 225
 226   check_tree (rt->abt.root, &tree_width);
 227   check (tree_width == ULONG_MAX);
 228
 229   if (offset > ULONG_MAX - 32)
 230     {
 231       pattern <<= offset - (ULONG_MAX - 32);
 232       offset = ULONG_MAX - 32;
 233     }
 234
 235   for (node = rand () % 2 ? range_tower_first (rt) : range_tower_next (rt, NULL),
 236          start = width = 0;
 237        next_region (pattern, start + width, &start, &width);
 238        node = range_tower_next (rt, node))
 239     {
 240       unsigned long int node_start;
 241       unsigned long int x;
 242
 243       check (node != NULL);
 244       check (range_tower_node_get_start (node) == start + offset);
 245       check (range_tower_node_get_end (node) == start + offset + width);
 246       check (range_tower_node_get_width (node) == width);
 247
 248       x = start + offset - node->n_zeros;
 249       check (range_tower_lookup (rt, x, &node_start) == node);
 250       check (node_start == start + offset - node->n_zeros);
 251
 252       x = start + offset + width - 1;
 253       check (range_tower_lookup (rt, x, &node_start) == node);
 254       check (node_start == start + offset - node->n_zeros);
 255     }
 256   check (node == NULL);
 257
 258   start = width = 0;
 259   RANGE_TOWER_FOR_EACH (node, start2, rt)
 260     {
 261       check (next_region (pattern, start + width, &start, &width));
 262       check (start + offset == start2);
 263       check (range_tower_node_get_width (node) == width);
 264     }
 265   check (!next_region (pattern, start + width, &start, &width));
 266
 267   for (node = rand () % 2 ? range_tower_last (rt) : range_tower_prev (rt, NULL),
 268          start = UINT_BIT;
 269        prev_region (pattern, start, &start, &width);
 270        node = range_tower_prev (rt, node))
 271     {
 272       check (node != NULL);
 273       check (range_tower_node_get_start (node) == offset + start);
 274       check (range_tower_node_get_end (node) == offset + start + width);
 275       check (range_tower_node_get_width (node) == width);
 276     }
 277   check (node == NULL);
 278
 279   /* Scan from all possible positions, resetting the cache each
 280      time, to ensure that we get the correct answers without
 281      caching. */
 282   for (start = 0; start <= 32; start++)
 283     {
 284       struct range_tower *nonconst_rt = CONST_CAST (struct range_tower *, rt);
 285
 286       nonconst_rt->cache_end = 0;
 287       s1 = range_tower_scan (rt, offset + start);
 288       s2 = next_1bit (pattern, start, offset);
 289       check (s1 == s2);
 290     }
 291
 292   /* Scan in forward order to exercise expected cache behavior. */
 293   for (s1 = range_tower_scan (rt, 0), s2 = next_1bit (pattern, 0, offset); ;
 294        s1 = range_tower_scan (rt, s1 + 1), s2 = next_1bit (pattern, (s2 - offset) + 1, offset))
 295     {
 296       check (s1 == s2);
 297       if (s1 == ULONG_MAX)
 298         break;
 299     }
 300
 301   /* Scan in random order to frustrate cache. */
 302   for (i = 0; i < 32; i++)
 303     {
 304       start = rand () % 32;
 305       s1 = range_tower_scan (rt, start + offset);
 306       s2 = next_1bit (pattern, start, offset);
 307       check (s1 == s2);
 308     }
 309
 310   /* Test range_tower_scan() with negative cache. */
 311   check (!range_tower_contains (rt, 999));
 312   if (offset < 1111)
 313     check (range_tower_scan (rt, 1111) == ULONG_MAX);
 314
 315   /* Check for containment without caching. */
 316   for (i = 0; i < UINT_BIT; i++)
 317     {
 318       struct range_tower *nonconst_rt = CONST_CAST (struct range_tower *, rt);
 319       nonconst_rt->cache_end = 0;
 320       check (range_tower_contains (rt, i + offset)
 321              == ((pattern & (1u << i)) != 0));
 322     }
 323
 324   /* Check for containment with caching. */
 325   for (i = 0; i < UINT_BIT; i++)
 326     check (range_tower_contains (rt, i + offset)
 327              == ((pattern & (1u << i)) != 0));
 328
 329   check (!range_tower_contains (rt,
 330                                 UINT_BIT + rand () % (ULONG_MAX - UINT_BIT * 2)));
 331
 332   check (range_tower_is_empty (rt) == (pattern == 0));
 333 }
 334
 335 /* Creates and returns a range tower that contains regions for the
 336    bits tower in PATTERN. */
 337 static struct range_tower *
 338 make_pattern (unsigned int pattern, unsigned long int offset)
 339 {
 340   unsigned long int start = 0;
 341   unsigned long int width = 0;
 342   struct range_tower *rt = range_tower_create_pool (NULL);
 343   while (next_region (pattern, start + width, &start, &width))
 344     range_tower_set1 (rt, start + offset, width);
 345   check_pattern (rt, pattern, offset);
 346   return rt;
 347 }
 348
 349 /* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
 350    tower to 1, other bits tower to 0. */
 351 static unsigned int
 352 bit_range (unsigned int ofs, unsigned int cnt)
 353 {
 354   assert (ofs < UINT_BIT);
 355   assert (cnt <= UINT_BIT);
 356   assert (ofs + cnt <= UINT_BIT);
 357
 358   return cnt < UINT_BIT ? ((1u << cnt) - 1) << ofs : UINT_MAX;
 359 }
 360 \f
 361 /* Tests setting all possible ranges of 1s into all possible range sets (up to
 362    a small maximum number of bits). */
 363 static void
 364 test_set1 (void)
 365 {
 366   const int positions = 9;
 367   unsigned int init_pat;
 368   int start, width;
 369   int k;
 370
 371   for (k = 0; k < 2; k++)
 372     for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 373       for (start = 0; start < positions; start++)
 374         for (width = 0; width + start <= positions; width++)
 375           {
 376             unsigned long int offset = k ? ULONG_MAX - positions : 0;
 377             struct range_tower *rt, *rt2;
 378             unsigned int final_pat;
 379
 380             rt = make_pattern (init_pat, offset);
 381             range_tower_set1 (rt, offset + start, width);
 382             final_pat = init_pat | bit_range (start, width);
 383             check_pattern (rt, final_pat, offset);
 384             rt2 = range_tower_clone (rt, NULL);
 385             check_pattern (rt2, final_pat, offset);
 386             range_tower_destroy (rt);
 387             range_tower_destroy (rt2);
 388           }
 389 }
 390
 391 /* Tests setting all possible ranges of 0s into all possible range sets (up to
 392    a small maximum number of bits). */
 393 static void
 394 test_set0 (void)
 395 {
 396   const int positions = 9;
 397   unsigned int init_pat;
 398   int start, width, k;
 399
 400   for (k = 0; k < 2; k++)
 401     for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 402       for (start = 0; start < positions; start++)
 403         for (width = 0; start + width <= positions; width++)
 404           {
 405             unsigned long int offset = k ? ULONG_MAX - positions : 0;
 406             struct range_tower *rt;
 407             unsigned int final_pat;
 408
 409             rt = make_pattern (init_pat, offset);
 410             range_tower_set0 (rt, offset + start, width);
 411             final_pat = init_pat & ~bit_range (start, width);
 412             check_pattern (rt, final_pat, offset);
 413             range_tower_destroy (rt);
 414           }
 415 }
 416
 417 /* Tests inserting all possible ranges of 0s into all possible range sets (up
 418    to a small maximum number of bits). */
 419 static void
 420 test_insert0 (void)
 421 {
 422   const int positions = 9;
 423   unsigned int init_pat;
 424   int start, width, k;
 425
 426   for (k = 0; k < 2; k++)
 427     for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 428       for (start = 0; start < positions; start++)
 429         for (width = 0; start + width <= positions; width++)
 430           {
 431             unsigned long int offset = k ? ULONG_MAX - positions : 0;
 432             struct range_tower *rt;
 433             unsigned int final_pat;
 434
 435             rt = make_pattern (init_pat, offset);
 436             range_tower_insert0 (rt, offset + start, width);
 437             final_pat = init_pat & bit_range (0, start);
 438             final_pat |= (init_pat & bit_range (start, positions - start)) << width;
 439             check_pattern (rt, final_pat, offset);
 440             range_tower_destroy (rt);
 441           }
 442 }
 443
 444 /* Tests inserting all possible ranges of 1s into all possible range sets (up
 445    to a small maximum number of bits). */
 446 static void
 447 test_insert1 (void)
 448 {
 449   const int positions = 9;
 450   unsigned int init_pat;
 451   int start, width, k;
 452
 453   for (k = 0; k < 2; k++)
 454     for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 455       for (start = 0; start < positions; start++)
 456         for (width = 0; start + width <= positions; width++)
 457           {
 458             struct range_tower *rt;
 459             unsigned int final_pat;
 460
 461             rt = make_pattern (init_pat, 0);
 462             range_tower_insert1 (rt, start, width);
 463             final_pat = init_pat & bit_range (0, start);
 464             final_pat |= bit_range (start, width);
 465             final_pat |= (init_pat & bit_range (start, positions - start)) << width;
 466             check_pattern (rt, final_pat, 0);
 467             range_tower_destroy (rt);
 468           }
 469 }
 470
 471 /* Tests setting all possible ranges from all possible range sets (up to a
 472    small maximum number of bits). */
 473 static void
 474 test_delete (void)
 475 {
 476   const int positions = 9;
 477   unsigned int init_pat;
 478   int start, width, k;
 479
 480   for (k = 0; k < 2; k++)
 481     for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 482       for (start = 0; start < positions; start++)
 483         for (width = 0; start + width <= positions; width++)
 484           {
 485             unsigned long int offset = k ? ULONG_MAX - positions : 0;
 486             struct range_tower *rt;
 487             unsigned int final_pat;
 488
 489             rt = make_pattern (init_pat, offset);
 490             range_tower_delete (rt, start + offset, width);
 491             final_pat = init_pat & bit_range (0, start);
 492             final_pat |= (init_pat & (UINT_MAX << (start + width))) >> width;
 493             check_pattern (rt, final_pat, offset);
 494             range_tower_destroy (rt);
 495           }
 496 }
 497
 498 /* Tests moving all possible ranges (up to a small maximum number of bits). */
 499 static void
 500 test_move (void)
 501 {
 502   const int positions = 9;
 503   unsigned int init_pat;
 504   int new_start, old_start, width, k;
 505
 506   for (k = 0; k < 2; k++)
 507     for (init_pat = 0; init_pat < (1u << positions); init_pat++)
 508       for (width = 0; width <= positions; width++)
 509         for (new_start = 0; new_start + width <= positions; new_start++)
 510           for (old_start = 0; old_start + width <= positions; old_start++)
 511             {
 512               unsigned long int offset = k ? ULONG_MAX - positions : 0;
 513               struct range_tower *rt;
 514               unsigned int final_pat;
 515
 516               if (new_start == old_start || width == 0)
 517                 final_pat = init_pat;
 518               else if (new_start < old_start)
 519                 {
 520                   final_pat = init_pat & bit_range (0, new_start);
 521                   final_pat |= (init_pat & bit_range (old_start, width)) >> (old_start - new_start);
 522                   final_pat |= (init_pat & bit_range (new_start, old_start - new_start)) << width;
 523                   final_pat |= init_pat & bit_range (old_start + width, positions - (old_start + width));
 524                 }
 525               else
 526                 {
 527                   final_pat = init_pat & bit_range (0, old_start);
 528                   final_pat |= (init_pat & bit_range (old_start + width, new_start - old_start)) >> width;
 529                   final_pat |= (init_pat & bit_range (old_start, width)) << (new_start - old_start);
 530                   final_pat |= init_pat & bit_range (new_start + width, positions - (new_start + width));
 531                 }
 532
 533               rt = make_pattern (init_pat, offset);
 534               range_tower_move (rt, old_start + offset, new_start + offset,
 535                                 width);
 536               check_pattern (rt, final_pat, offset);
 537               range_tower_destroy (rt);
 538             }
 539 }
 540
 541 /* Tests freeing a range tower through a pool. */
 542 static void
 543 test_pool (void)
 544 {
 545   struct pool *pool;
 546   struct range_tower *rt;
 547
 548   /* Destroy the range tower, then the pool.
 549      Makes sure that this doesn't cause a double-free. */
 550   pool = pool_create ();
 551   rt = range_tower_create_pool (pool);
 552   range_tower_set1 (rt, 1, 10);
 553   range_tower_destroy (rt);
 554   pool_destroy (pool);
 555
 556   /* Just destroy the pool.
 557      Makes sure that this doesn't cause a leak. */
 558   pool = pool_create ();
 559   rt = range_tower_create_pool (pool);
 560   range_tower_set1 (rt, 1, 10);
 561   pool_destroy (pool);
 562 }
 563
 564 /* Tests range_tower_destroy(NULL). */
 565 static void
 566 test_destroy_null (void)
 567 {
 568   range_tower_destroy (NULL);
 569 }
 570 \f
 571 /* Main program. */
 572
 573 struct test
 574   {
 575     const char *name;
 576     const char *description;
 577     void (*function) (void);
 578   };
 579
 580 static const struct test tests[] =
 581   {
 582     {
 583       "set1",
 584       "set1",
 585       test_set1
 586     },
 587     {
 588       "set0",
 589       "set0",
 590       test_set0
 591     },
 592     {
 593       "insert0",
 594       "insert0",
 595       test_insert0
 596     },
 597     {
 598       "insert1",
 599       "insert1",
 600       test_insert1
 601     },
 602     {
 603       "delete",
 604       "delete",
 605       test_delete
 606     },
 607     {
 608       "move",
 609       "move",
 610       test_move
 611     },
 612     {
 613       "pool",
 614       "pool",
 615       test_pool
 616     },
 617     {
 618       "destroy-null",
 619       "destroy null",
 620       test_destroy_null
 621     },
 622   };
 623
 624 enum { N_TESTS = sizeof tests / sizeof *tests };
 625
 626 int
 627 main (int argc, char *argv[])
 628 {
 629   int i;
 630
 631   if (argc != 2)
 632     {
 633       fprintf (stderr, "exactly one argument required; use --help for help\n");
 634       return EXIT_FAILURE;
 635     }
 636   else if (!strcmp (argv[1], "--help"))
 637     {
 638       printf ("%s: test range tower library\n"
 639               "usage: %s TEST-NAME\n"
 640               "where TEST-NAME is one of the following:\n",
 641               argv[0], argv[0]);
 642       for (i = 0; i < N_TESTS; i++)
 643         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 644       return 0;
 645     }
 646   else
 647     {
 648       for (i = 0; i < N_TESTS; i++)
 649         if (!strcmp (argv[1], tests[i].name))
 650           {
 651             tests[i].function ();
 652             return 0;
 653           }
 654
 655       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 656       return EXIT_FAILURE;
 657     }
 658 }