tests/libpspp/sparse-array-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009, 2010 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 sparse array routines defined
  18    in sparse-array.c.  This test program aims to be as
  19    comprehensive as possible.  "gcov -b" should report 100%
  20    coverage of lines and branches in sparse-array.c when compiled
  21    with -DNDEBUG and BITS_PER_LEVEL is greater than the number of
  22    bits in a long.  "valgrind --leak-check=yes
  23    --show-reachable=yes" should give a clean report. */
  24
  25 #ifdef HAVE_CONFIG_H
  26 #include <config.h>
  27 #endif
  28
  29 #include <libpspp/sparse-array.h>
  30 #include <assert.h>
  31 #include <limits.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35 \f
  36 /* Support preliminaries. */
  37 #if __GNUC__ >= 2 && !defined UNUSED
  38 #define UNUSED __attribute__ ((unused))
  39 #else
  40 #define UNUSED
  41 #endif
  42
  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
  68 /* Prints a message about memory exhaustion and exits with a
  69    failure code. */
  70 static void
  71 xalloc_die (void)
  72 {
  73   printf ("virtual memory exhausted\n");
  74   exit (EXIT_FAILURE);
  75 }
  76
  77 /* Allocates and returns N bytes of memory. */
  78 static void *
  79 xmalloc (size_t n)
  80 {
  81   if (n != 0)
  82     {
  83       void *p = malloc (n);
  84       if (p == NULL)
  85         xalloc_die ();
  86
  87       return p;
  88     }
  89   else
  90     return NULL;
  91 }
  92
  93 /* Returns a malloc()'d duplicate of the N bytes starting at
  94    P. */
  95 static void *
  96 xmemdup (const void *p, size_t n)
  97 {
  98   void *q = xmalloc (n);
  99   memcpy (q, p, n);
 100   return q;
 101 }
 102
 103 /* Allocates and returns N * M bytes of memory. */
 104 static void *
 105 xnmalloc (size_t n, size_t m)
 106 {
 107   if ((size_t) -1 / m <= n)
 108     xalloc_die ();
 109   return xmalloc (n * m);
 110 }
 111 \f
 112 /* Compares A and B and returns a strcmp-type return value. */
 113 static int
 114 compare_unsigned_longs_noaux (const void *a_, const void *b_)
 115 {
 116   const unsigned long *a = a_;
 117   const unsigned long *b = b_;
 118
 119   return *a < *b ? -1 : *a > *b;
 120 }
 121
 122 /* Checks that SPAR contains the CNT ints in DATA, that its
 123    structure is correct, and that certain operations on SPAR
 124    produce the expected results. */
 125 static void
 126 check_sparse_array (struct sparse_array *spar,
 127                     const unsigned long data[], size_t cnt)
 128 {
 129   unsigned long idx;
 130   unsigned long *order;
 131   unsigned long *p;
 132   size_t i;
 133
 134   check (sparse_array_count (spar) == cnt);
 135
 136   for (i = 0; i < cnt; i++)
 137     {
 138       p = sparse_array_get (spar, data[i]);
 139       check (p != NULL);
 140       check (*p == data[i]);
 141     }
 142
 143   order = xmemdup (data, cnt * sizeof *data);
 144   qsort (order, cnt, sizeof *order, compare_unsigned_longs_noaux);
 145
 146   for (i = 0; i < cnt; i++)
 147     {
 148       p = sparse_array_get (spar, order[i]);
 149       check (p != NULL);
 150       check (*p == order[i]);
 151     }
 152
 153   if (cnt > 0 && order[0] - 1 != order[cnt - 1])
 154     {
 155       check (sparse_array_get (spar, order[0] - 1) == NULL);
 156       check (!sparse_array_remove (spar, order[0] - 1));
 157     }
 158   if (cnt > 0 && order[0] != order[cnt - 1] + 1)
 159     {
 160       check (sparse_array_get (spar, order[cnt - 1] + 1) == NULL);
 161       check (!sparse_array_remove (spar, order[cnt - 1] + 1));
 162     }
 163
 164   for (i = 0, p = sparse_array_first (spar, &idx); i < cnt;
 165        i++, p = sparse_array_next (spar, idx, &idx))
 166     {
 167       check (p != NULL);
 168       check (idx == order[i]);
 169       check (*p == order[i]);
 170     }
 171   check (p == NULL);
 172
 173   for (i = 0, p = sparse_array_last (spar, &idx); i < cnt;
 174        i++, p = sparse_array_prev (spar, idx, &idx))
 175     {
 176       check (p != NULL);
 177       check (idx == order[cnt - i - 1]);
 178       check (*p == order[cnt - i - 1]);
 179     }
 180   check (p == NULL);
 181
 182   free (order);
 183 }
 184
 185 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
 186    sparse array in the order specified by INSERTIONS, then
 187    deletes them in the order specified by DELETIONS, checking the
 188    array's contents for correctness after each operation. */
 189 static void
 190 test_insert_delete (const unsigned long insertions[],
 191                     const unsigned long deletions[],
 192                     size_t cnt)
 193 {
 194   struct sparse_array *spar;
 195   size_t i;
 196
 197   spar = sparse_array_create (sizeof *insertions);
 198   for (i = 0; i < cnt; i++)
 199     {
 200       unsigned long *p = sparse_array_insert (spar, insertions[i]);
 201       *p = insertions[i];
 202       check_sparse_array (spar, insertions, i + 1);
 203     }
 204   for (i = 0; i < cnt; i++)
 205     {
 206       bool deleted = sparse_array_remove (spar, deletions[i]);
 207       check (deleted);
 208       check_sparse_array (spar, deletions + i + 1, cnt - (i + 1));
 209     }
 210   check_sparse_array (spar, NULL, 0);
 211   sparse_array_destroy (spar);
 212 }
 213
 214 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into a
 215    sparse array in the order specified by INSERTIONS, then
 216    destroys the sparse array, to check that sparse_cases_destroy
 217    properly frees all the nodes. */
 218 static void
 219 test_destroy (const unsigned long insertions[], size_t cnt)
 220 {
 221   struct sparse_array *spar;
 222   size_t i;
 223
 224   spar = sparse_array_create (sizeof *insertions);
 225   for (i = 0; i < cnt; i++)
 226     {
 227       unsigned long *p = sparse_array_insert (spar, insertions[i]);
 228       *p = insertions[i];
 229       check_sparse_array (spar, insertions, i + 1);
 230     }
 231   sparse_array_destroy (spar);
 232 }
 233
 234 /* Randomly shuffles the CNT elements in ARRAY, each of which is
 235    SIZE bytes in size. */
 236 static void
 237 random_shuffle (void *array_, size_t cnt, size_t size)
 238 {
 239   char *array = array_;
 240   char *tmp = xmalloc (size);
 241   size_t i;
 242
 243   for (i = 0; i < cnt; i++)
 244     {
 245       size_t j = rand () % (cnt - i) + i;
 246       if (i != j)
 247         {
 248           memcpy (tmp, array + j * size, size);
 249           memcpy (array + j * size, array + i * size, size);
 250           memcpy (array + i * size, tmp, size);
 251         }
 252     }
 253
 254   free (tmp);
 255 }
 256 \f
 257 /* Tests inserting and deleting elements whose values are
 258    determined by starting from various offsets and skipping
 259    across various strides, and doing so in various orders. */
 260 static void
 261 test_insert_delete_strides (void)
 262 {
 263   static const unsigned long strides[] =
 264     {
 265       1, 2, 4, 16, 64, 4096, 262144, 16777216,
 266       3, 5, 17, 67, 4099, 262147, 16777259,
 267     };
 268   const size_t stride_cnt = sizeof strides / sizeof *strides;
 269
 270   static const unsigned long offsets[] =
 271     {
 272       0,
 273       1024ul * 1024 + 1,
 274       1024ul * 1024 * 512 + 23,
 275       ULONG_MAX - 59,
 276     };
 277   const size_t offset_cnt = sizeof offsets / sizeof *offsets;
 278
 279   int cnt = 100;
 280   unsigned long *insertions, *deletions;
 281   const unsigned long *stride, *offset;
 282
 283   insertions = xnmalloc (cnt, sizeof *insertions);
 284   deletions = xnmalloc (cnt, sizeof *deletions);
 285   for (stride = strides; stride < strides + stride_cnt; stride++)
 286     {
 287       printf ("%lu\n", *stride);
 288       for (offset = offsets; offset < offsets + offset_cnt; offset++)
 289         {
 290           int k;
 291
 292           for (k = 0; k < cnt; k++)
 293             insertions[k] = *stride * k + *offset;
 294
 295           test_insert_delete (insertions, insertions, cnt);
 296           test_destroy (insertions, cnt);
 297
 298           for (k = 0; k < cnt; k++)
 299             deletions[k] = insertions[cnt - k - 1];
 300           test_insert_delete (insertions, deletions, cnt);
 301
 302           random_shuffle (insertions, cnt, sizeof *insertions);
 303           test_insert_delete (insertions, insertions, cnt);
 304           test_insert_delete (insertions, deletions, cnt);
 305         }
 306     }
 307   free (insertions);
 308   free (deletions);
 309 }
 310
 311 /* Returns the index in ARRAY of the (CNT+1)th element that has
 312    the TARGET value. */
 313 static int
 314 scan_bools (bool target, bool array[], size_t cnt)
 315 {
 316   size_t i;
 317
 318   for (i = 0; ; i++)
 319     if (array[i] == target && cnt-- == 0)
 320       return i;
 321 }
 322
 323 /* Performs a random sequence of insertions and deletions in a
 324    sparse array. */
 325 static void
 326 test_random_insert_delete (void)
 327 {
 328   unsigned long int values[] =
 329     {
 330       0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
 331       8192, 16384, 32768, 65536, 131072, 262144, 4194304, 8388608,
 332       16777216, 33554432, 67108864, 134217728, 268435456, 536870912,
 333       1073741824, 2147483648,
 334
 335       3, 7, 15, 31, 63, 127, 257, 511, 1023, 2047, 4095,
 336       8191, 16383, 32767, 65535, 131071, 262143, 4194303, 8388607,
 337       16777215, 33554431, 67108863, 134217727, 268435455, 536870911,
 338       1073741823, 2147483647, 4294967295,
 339     };
 340   const int max_values = sizeof values / sizeof *values;
 341
 342   const int num_actions = 250000;
 343   struct sparse_array *spar;
 344   bool *has_values;
 345   int cnt;
 346   int insert_chance;
 347   int i;
 348
 349   has_values = xnmalloc (max_values, sizeof *has_values);
 350   memset (has_values, 0, max_values * sizeof *has_values);
 351
 352   cnt = 0;
 353   insert_chance = 5;
 354
 355   spar = sparse_array_create (sizeof *values);
 356   for (i = 0; i < num_actions; i++)
 357     {
 358       enum { INSERT, DELETE } action;
 359       unsigned long *p;
 360       int j;
 361
 362       if (cnt == 0)
 363         {
 364           action = INSERT;
 365           if (insert_chance < 9)
 366             insert_chance++;
 367         }
 368       else if (cnt == max_values)
 369         {
 370           action = DELETE;
 371           if (insert_chance > 0)
 372             insert_chance--;
 373         }
 374       else
 375         action = rand () % 10 < insert_chance ? INSERT : DELETE;
 376
 377       if (action == INSERT)
 378         {
 379           int ins_index;
 380
 381           ins_index = scan_bools (false, has_values,
 382                                   rand () % (max_values - cnt));
 383           assert (has_values[ins_index] == false);
 384           has_values[ins_index] = true;
 385
 386           p = sparse_array_insert (spar, values[ins_index]);
 387           check (p != NULL);
 388           *p = values[ins_index];
 389
 390           cnt++;
 391         }
 392       else if (action == DELETE)
 393         {
 394           int del_index;
 395
 396           del_index = scan_bools (true, has_values, rand () % cnt);
 397           assert (has_values[del_index] == true);
 398           has_values[del_index] = false;
 399
 400           check (sparse_array_remove (spar, values[del_index]));
 401           cnt--;
 402         }
 403       else
 404         abort ();
 405
 406       check (sparse_array_count (spar) == cnt);
 407       for (j = 0; j < max_values; j++)
 408         {
 409           p = sparse_array_get (spar, values[j]);
 410           if (has_values[j])
 411             {
 412               check (p != NULL);
 413               check (*p == values[j]);
 414             }
 415           else
 416             {
 417               check (p == NULL);
 418               if (rand () % 10 == 0)
 419                 sparse_array_remove (spar, values[j]);
 420             }
 421         }
 422     }
 423   sparse_array_destroy (spar);
 424   free (has_values);
 425 }
 426 \f
 427 /* Main program. */
 428
 429 struct test
 430   {
 431     const char *name;
 432     const char *description;
 433     void (*function) (void);
 434   };
 435
 436 static const struct test tests[] =
 437   {
 438     {
 439       "random-insert-delete",
 440       "random insertions and deletions",
 441       test_random_insert_delete
 442     },
 443     {
 444       "insert-delete-strides",
 445       "insert in ascending order with strides and offset",
 446       test_insert_delete_strides
 447     },
 448   };
 449
 450 enum { N_TESTS = sizeof tests / sizeof *tests };
 451
 452 int
 453 main (int argc, char *argv[])
 454 {
 455   int i;
 456
 457   if (argc != 2)
 458     {
 459       fprintf (stderr, "exactly one argument required; use --help for help\n");
 460       return EXIT_FAILURE;
 461     }
 462   else if (!strcmp (argv[1], "--help"))
 463     {
 464       printf ("%s: test sparse array library\n"
 465               "usage: %s TEST-NAME\n"
 466               "where TEST-NAME is one of the following:\n",
 467               argv[0], argv[0]);
 468       for (i = 0; i < N_TESTS; i++)
 469         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 470       return 0;
 471     }
 472   else
 473     {
 474       for (i = 0; i < N_TESTS; i++)
 475         if (!strcmp (argv[1], tests[i].name))
 476           {
 477             tests[i].function ();
 478             return 0;
 479           }
 480
 481       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 482       return EXIT_FAILURE;
 483     }
 484 }