tests/libpspp/sparse-array-test.c

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