tests/libpspp/string-set-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2008, 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 string_set_* routines defined in
  18    string-set.c.  This test program aims to be as comprehensive as possible.
  19    "gcov -a -b" should report almost complete coverage of lines, blocks and
  20    branches in string-set.c, except that one branch caused by hash collision is
  21    not exercised because our hash function has so few collisions.  "valgrind
  22    --leak-check=yes --show-reachable=yes" should give a clean report. */
  23
  24 #include <config.h>
  25
  26 #include <libpspp/string-set.h>
  27
  28 #include <assert.h>
  29 #include <limits.h>
  30 #include <stdbool.h>
  31 #include <stddef.h>
  32 #include <stdint.h>
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36
  37 #include <libpspp/compiler.h>
  38 \f
  39 /* Currently running test. */
  40 static const char *test_name;
  41
  42 /* Exit with a failure code.
  43    (Place a breakpoint on this function while debugging.) */
  44 static void
  45 check_die (void)
  46 {
  47   exit (EXIT_FAILURE);
  48 }
  49
  50 /* If OK is not true, prints a message about failure on the
  51    current source file and the given LINE and terminates. */
  52 static void
  53 check_func (bool ok, int line)
  54 {
  55   if (!ok)
  56     {
  57       printf ("Check failed in %s test at %s, line %d\n",
  58               test_name, __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 static void *xmalloc (size_t n) MALLOC_LIKE;
  78 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
  79 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
  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 static void *
  98 xmemdup (const void *p, size_t n)
  99 {
 100   void *q = xmalloc (n);
 101   memcpy (q, p, n);
 102   return q;
 103 }
 104
 105 /* Clone STRING.  */
 106 static char *
 107 xstrdup (const char *string)
 108 {
 109   return xmemdup (string, strlen (string) + 1);
 110 }
 111
 112 /* Allocates and returns N * M bytes of memory. */
 113 static void *
 114 xnmalloc (size_t n, size_t m)
 115 {
 116   if ((size_t) -1 / m <= n)
 117     xalloc_die ();
 118   return xmalloc (n * m);
 119 }
 120 \f
 121 /* Support routines. */
 122
 123 enum { MAX_VALUE = 1024 };
 124
 125 static char *string_table[MAX_VALUE];
 126
 127 static const char *
 128 make_string (int value)
 129 {
 130   char **s;
 131
 132   assert (value >= 0 && value < MAX_VALUE);
 133   s = &string_table[value];
 134   if (*s == NULL)
 135     {
 136       *s = xmalloc (16);
 137       sprintf (*s, "%d", value);
 138     }
 139   return *s;
 140 }
 141
 142 static void
 143 free_strings (void)
 144 {
 145   int i;
 146
 147   for (i = 0; i < MAX_VALUE; i++)
 148     free (string_table[i]);
 149 }
 150
 151 /* Swaps *A and *B. */
 152 static void
 153 swap (int *a, int *b)
 154 {
 155   int t = *a;
 156   *a = *b;
 157   *b = t;
 158 }
 159
 160 /* Reverses the order of the CNT integers starting at VALUES. */
 161 static void
 162 reverse (int *values, size_t cnt)
 163 {
 164   size_t i = 0;
 165   size_t j = cnt;
 166
 167   while (j > i)
 168     swap (&values[i++], &values[--j]);
 169 }
 170
 171 /* Arranges the CNT elements in VALUES into the lexicographically
 172    next greater permutation.  Returns true if successful.
 173    If VALUES is already the lexicographically greatest
 174    permutation of its elements (i.e. ordered from greatest to
 175    smallest), arranges them into the lexicographically least
 176    permutation (i.e. ordered from smallest to largest) and
 177    returns false. */
 178 static bool
 179 next_permutation (int *values, size_t cnt)
 180 {
 181   if (cnt > 0)
 182     {
 183       size_t i = cnt - 1;
 184       while (i != 0)
 185         {
 186           i--;
 187           if (values[i] < values[i + 1])
 188             {
 189               size_t j;
 190               for (j = cnt - 1; values[i] >= values[j]; j--)
 191                 continue;
 192               swap (values + i, values + j);
 193               reverse (values + (i + 1), cnt - (i + 1));
 194               return true;
 195             }
 196         }
 197
 198       reverse (values, cnt);
 199     }
 200
 201   return false;
 202 }
 203
 204 /* Returns N!. */
 205 static unsigned int
 206 factorial (unsigned int n)
 207 {
 208   unsigned int value = 1;
 209   while (n > 1)
 210     value *= n--;
 211   return value;
 212 }
 213
 214 /* Randomly shuffles the CNT elements in ARRAY, each of which is
 215    SIZE bytes in size. */
 216 static void
 217 random_shuffle (void *array_, size_t cnt, size_t size)
 218 {
 219   char *array = array_;
 220   char *tmp = xmalloc (size);
 221   size_t i;
 222
 223   for (i = 0; i < cnt; i++)
 224     {
 225       size_t j = rand () % (cnt - i) + i;
 226       if (i != j)
 227         {
 228           memcpy (tmp, array + j * size, size);
 229           memcpy (array + j * size, array + i * size, size);
 230           memcpy (array + i * size, tmp, size);
 231         }
 232     }
 233
 234   free (tmp);
 235 }
 236
 237 /* Checks that SET contains the CNT strings in DATA, that its structure is
 238    correct, and that certain operations on SET produce the expected results. */
 239 static void
 240 check_string_set (struct string_set *set, const int data[], size_t cnt)
 241 {
 242   size_t i;
 243
 244   check (string_set_is_empty (set) == (cnt == 0));
 245   check (string_set_count (set) == cnt);
 246
 247   for (i = 0; i < cnt; i++)
 248     {
 249       struct string_set_node *node;
 250       const char *s = make_string (data[i]);
 251
 252       check (string_set_contains (set, s));
 253       check (!string_set_insert (set, s));
 254       check (!string_set_insert_nocopy (set, xstrdup (s)));
 255
 256       node = string_set_find_node (set, s);
 257       check (node != NULL);
 258       check (!strcmp (s, string_set_node_get_string (node)));
 259     }
 260
 261   check (!string_set_contains (set, "xxx"));
 262   check (string_set_find_node (set, "") == NULL);
 263
 264   if (cnt == 0)
 265     check (string_set_first (set) == NULL);
 266   else
 267     {
 268       const struct string_set_node *node;
 269       int *data_copy;
 270       int left;
 271
 272       data_copy = xmemdup (data, cnt * sizeof *data);
 273       left = cnt;
 274       for (node = string_set_first (set), i = 0; i < cnt;
 275            node = string_set_next (set, node), i++)
 276         {
 277           const char *s = string_set_node_get_string (node);
 278           size_t j;
 279
 280           for (j = 0; j < left; j++)
 281             if (!strcmp (s, make_string (data_copy[j])))
 282               {
 283                 data_copy[j] = data_copy[--left];
 284                 goto next;
 285               }
 286           check_die ();
 287
 288         next: ;
 289         }
 290       check (node == NULL);
 291       free (data_copy);
 292     }
 293 }
 294
 295 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the
 296    order specified by INSERTIONS, then deletes them in the order specified by
 297    DELETIONS, checking the set's contents for correctness after each
 298    operation.  */
 299 static void
 300 test_insert_delete (const int insertions[],
 301                     const int deletions[],
 302                     size_t cnt)
 303 {
 304   struct string_set set;
 305   size_t i;
 306
 307   string_set_init (&set);
 308   check_string_set (&set, NULL, 0);
 309   for (i = 0; i < cnt; i++)
 310     {
 311       check (string_set_insert (&set, make_string (insertions[i])));
 312       check_string_set (&set, insertions, i + 1);
 313     }
 314   for (i = 0; i < cnt; i++)
 315     {
 316       check (string_set_delete (&set, make_string (deletions[i])));
 317       check_string_set (&set, deletions + i + 1, cnt - i - 1);
 318     }
 319   string_set_destroy (&set);
 320 }
 321 \f
 322 /* Inserts strings into a set in each possible order, then removes them in each
 323    possible order, up to a specified maximum size. */
 324 static void
 325 test_insert_any_remove_any (void)
 326 {
 327   const int max_elems = 5;
 328   int cnt;
 329
 330   for (cnt = 0; cnt <= max_elems; cnt++)
 331     {
 332       int *insertions, *deletions;
 333       unsigned int ins_perm_cnt;
 334       int i;
 335
 336       insertions = xnmalloc (cnt, sizeof *insertions);
 337       deletions = xnmalloc (cnt, sizeof *deletions);
 338       for (i = 0; i < cnt; i++)
 339         insertions[i] = i;
 340
 341       for (ins_perm_cnt = 0;
 342            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 343            ins_perm_cnt++)
 344         {
 345           unsigned int del_perm_cnt;
 346           int i;
 347
 348           for (i = 0; i < cnt; i++)
 349             deletions[i] = i;
 350
 351           for (del_perm_cnt = 0;
 352                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 353                del_perm_cnt++)
 354             test_insert_delete (insertions, deletions, cnt);
 355
 356           check (del_perm_cnt == factorial (cnt));
 357         }
 358       check (ins_perm_cnt == factorial (cnt));
 359
 360       free (insertions);
 361       free (deletions);
 362     }
 363 }
 364
 365 /* Inserts strings into a set in each possible order, then removes them in the
 366    same order, up to a specified maximum size. */
 367 static void
 368 test_insert_any_remove_same (void)
 369 {
 370   const int max_elems = 7;
 371   int cnt;
 372
 373   for (cnt = 0; cnt <= max_elems; cnt++)
 374     {
 375       int *values;
 376       unsigned int permutation_cnt;
 377       int i;
 378
 379       values = xnmalloc (cnt, sizeof *values);
 380       for (i = 0; i < cnt; i++)
 381         values[i] = i;
 382
 383       for (permutation_cnt = 0;
 384            permutation_cnt == 0 || next_permutation (values, cnt);
 385            permutation_cnt++)
 386         test_insert_delete (values, values, cnt);
 387       check (permutation_cnt == factorial (cnt));
 388
 389       free (values);
 390     }
 391 }
 392
 393 /* Inserts strings into a set in each possible order, then
 394    removes them in reverse order, up to a specified maximum
 395    size. */
 396 static void
 397 test_insert_any_remove_reverse (void)
 398 {
 399   const int max_elems = 7;
 400   int cnt;
 401
 402   for (cnt = 0; cnt <= max_elems; cnt++)
 403     {
 404       int *insertions, *deletions;
 405       unsigned int permutation_cnt;
 406       int i;
 407
 408       insertions = xnmalloc (cnt, sizeof *insertions);
 409       deletions = xnmalloc (cnt, sizeof *deletions);
 410       for (i = 0; i < cnt; i++)
 411         insertions[i] = i;
 412
 413       for (permutation_cnt = 0;
 414            permutation_cnt == 0 || next_permutation (insertions, cnt);
 415            permutation_cnt++)
 416         {
 417           memcpy (deletions, insertions, sizeof *insertions * cnt);
 418           reverse (deletions, cnt);
 419
 420           test_insert_delete (insertions, deletions, cnt);
 421         }
 422       check (permutation_cnt == factorial (cnt));
 423
 424       free (insertions);
 425       free (deletions);
 426     }
 427 }
 428
 429 /* Inserts and removes strings in a set, in random order. */
 430 static void
 431 test_random_sequence (void)
 432 {
 433   const int max_elems = 64;
 434   const int max_trials = 8;
 435   int cnt;
 436
 437   for (cnt = 0; cnt <= max_elems; cnt += 2)
 438     {
 439       int *insertions, *deletions;
 440       int trial;
 441       int i;
 442
 443       insertions = xnmalloc (cnt, sizeof *insertions);
 444       deletions = xnmalloc (cnt, sizeof *deletions);
 445       for (i = 0; i < cnt; i++)
 446         insertions[i] = i;
 447       for (i = 0; i < cnt; i++)
 448         deletions[i] = i;
 449
 450       for (trial = 0; trial < max_trials; trial++)
 451         {
 452           random_shuffle (insertions, cnt, sizeof *insertions);
 453           random_shuffle (deletions, cnt, sizeof *deletions);
 454
 455           test_insert_delete (insertions, deletions, cnt);
 456         }
 457
 458       free (insertions);
 459       free (deletions);
 460     }
 461 }
 462
 463 /* Inserts strings into a set in ascending order, then delete in ascending
 464    order. */
 465 static void
 466 test_insert_ordered (void)
 467 {
 468   const int max_elems = 64;
 469   int *values;
 470   struct string_set set;
 471   int i;
 472
 473   string_set_init (&set);
 474   values = xnmalloc (max_elems, sizeof *values);
 475   for (i = 0; i < max_elems; i++)
 476     {
 477       values[i] = i;
 478       string_set_insert_nocopy (&set, xstrdup (make_string (i)));
 479       check_string_set (&set, values, i + 1);
 480     }
 481   for (i = 0; i < max_elems; i++)
 482     {
 483       string_set_delete (&set, make_string (i));
 484       check_string_set (&set, values + i + 1, max_elems - i - 1);
 485     }
 486   string_set_destroy (&set);
 487   free (values);
 488 }
 489
 490 static void
 491 test_boolean_ops (void (*function)(struct string_set *a, struct string_set *b,
 492                                    unsigned int *a_pat, unsigned int *b_pat))
 493 {
 494   enum { MAX_STRINGS = 7 };
 495   unsigned int a_pat, b_pat;
 496
 497   for (a_pat = 0; a_pat < (1u << MAX_STRINGS); a_pat++)
 498     for (b_pat = 0; b_pat < (1u << MAX_STRINGS); b_pat++)
 499       {
 500         unsigned int new_a_pat = a_pat;
 501         unsigned int new_b_pat = b_pat;
 502         struct string_set a, b;
 503         int a_strings[MAX_STRINGS], b_strings[MAX_STRINGS];
 504         size_t i, n_a, n_b;
 505
 506         string_set_init (&a);
 507         string_set_init (&b);
 508         for (i = 0; i < MAX_STRINGS; i++)
 509           {
 510             if (a_pat & (1u << i))
 511               string_set_insert (&a, make_string (i));
 512             if (b_pat & (1u << i))
 513               string_set_insert (&b, make_string (i));
 514           }
 515
 516         function (&a, &b, &new_a_pat, &new_b_pat);
 517
 518         n_a = n_b = 0;
 519         for (i = 0; i < MAX_STRINGS; i++)
 520           {
 521             if (new_a_pat & (1u << i))
 522               a_strings[n_a++] = i;
 523             if (new_b_pat & (1u << i))
 524               b_strings[n_b++] = i;
 525           }
 526         check_string_set (&a, a_strings, n_a);
 527         check_string_set (&b, b_strings, n_b);
 528         string_set_destroy (&a);
 529         string_set_destroy (&b);
 530       }
 531 }
 532
 533 static void
 534 union_cb (struct string_set *a, struct string_set *b,
 535           unsigned int *a_pat, unsigned int *b_pat)
 536 {
 537   string_set_union (a, b);
 538   *a_pat |= *b_pat;
 539 }
 540
 541 static void
 542 test_union (void)
 543 {
 544   test_boolean_ops (union_cb);
 545 }
 546
 547 static void
 548 union_and_intersection_cb (struct string_set *a, struct string_set *b,
 549                            unsigned int *a_pat, unsigned int *b_pat)
 550 {
 551   unsigned int orig_a_pat = *a_pat;
 552   unsigned int orig_b_pat = *b_pat;
 553
 554   string_set_union_and_intersection (a, b);
 555   *a_pat = orig_a_pat | orig_b_pat;
 556   *b_pat = orig_a_pat & orig_b_pat;
 557 }
 558
 559 static void
 560 test_union_and_intersection (void)
 561 {
 562   test_boolean_ops (union_and_intersection_cb);
 563 }
 564
 565 static void
 566 intersect_cb (struct string_set *a, struct string_set *b,
 567               unsigned int *a_pat, unsigned int *b_pat)
 568 {
 569   string_set_intersect (a, b);
 570   *a_pat &= *b_pat;
 571 }
 572
 573 static void
 574 test_intersect (void)
 575 {
 576   test_boolean_ops (intersect_cb);
 577 }
 578
 579 static void
 580 subtract_cb (struct string_set *a, struct string_set *b,
 581               unsigned int *a_pat, unsigned int *b_pat)
 582 {
 583   string_set_subtract (a, b);
 584   *a_pat &= ~*b_pat;
 585 }
 586
 587 static void
 588 test_subtract (void)
 589 {
 590   test_boolean_ops (subtract_cb);
 591 }
 592
 593 static void
 594 swap_cb (struct string_set *a, struct string_set *b,
 595          unsigned int *a_pat, unsigned int *b_pat)
 596 {
 597   unsigned int tmp;
 598   string_set_swap (a, b);
 599   tmp = *a_pat;
 600   *a_pat = *b_pat;
 601   *b_pat = tmp;
 602 }
 603
 604 static void
 605 test_swap (void)
 606 {
 607   test_boolean_ops (swap_cb);
 608 }
 609
 610 static void
 611 clear_cb (struct string_set *a, struct string_set *b UNUSED,
 612          unsigned int *a_pat, unsigned int *b_pat UNUSED)
 613 {
 614   string_set_clear (a);
 615   *a_pat = 0;
 616 }
 617
 618 static void
 619 test_clear (void)
 620 {
 621   test_boolean_ops (clear_cb);
 622 }
 623
 624 static void
 625 clone_cb (struct string_set *a, struct string_set *b,
 626          unsigned int *a_pat, unsigned int *b_pat)
 627 {
 628   string_set_destroy (a);
 629   string_set_clone (a, b);
 630   *a_pat = *b_pat;
 631 }
 632
 633 static void
 634 test_clone (void)
 635 {
 636   test_boolean_ops (clone_cb);
 637 }
 638
 639 static void
 640 test_destroy_null (void)
 641 {
 642   string_set_destroy (NULL);
 643 }
 644 \f
 645 /* Main program. */
 646
 647 /* Runs TEST_FUNCTION and prints a message about NAME. */
 648 static void
 649 run_test (void (*test_function) (void), const char *name)
 650 {
 651   test_name = name;
 652   putchar ('.');
 653   fflush (stdout);
 654   test_function ();
 655 }
 656
 657 int
 658 main (void)
 659 {
 660   run_test (test_insert_any_remove_any, "insert any order, delete any order");
 661   run_test (test_insert_any_remove_same,
 662             "insert any order, delete same order");
 663   run_test (test_insert_any_remove_reverse,
 664             "insert any order, delete reverse order");
 665   run_test (test_random_sequence, "insert and delete in random sequence");
 666   run_test (test_insert_ordered, "insert in ascending order");
 667   run_test (test_union, "union");
 668   run_test (test_union_and_intersection, "union and intersection");
 669   run_test (test_intersect, "intersect");
 670   run_test (test_subtract, "subtract");
 671   run_test (test_swap, "swap");
 672   run_test (test_clear, "clear");
 673   run_test (test_clone, "clone");
 674   run_test (test_destroy_null, "destroying null table");
 675
 676   putchar ('\n');
 677
 678   free_strings ();
 679
 680   return 0;
 681 }