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