tests/libpspp/stringi-set-test.c

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