tests/libpspp/sparse-array-test.c

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