pintos-os.org Git - pspp/blob - 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     check (stringi_set_first (set) == NULL);
 287   else
 288     {
 289       const struct stringi_set_node *node;
 290       int *data_copy;
 291       int left;
 292
 293       data_copy = xmemdup (data, cnt * sizeof *data);
 294       left = cnt;
 295       for (node = stringi_set_first (set), i = 0; i < cnt;
 296            node = stringi_set_next (set, node), i++)
 297         {
 298           const char *s = stringi_set_node_get_string (node);
 299           size_t j;
 300
 301           for (j = 0; j < left; j++)
 302             if (!strcasecmp (s, make_string (data_copy[j])))
 303               {
 304                 data_copy[j] = data_copy[--left];
 305                 goto next;
 306               }
 307           check_die ();
 308
 309         next: ;
 310         }
 311       check (node == NULL);
 312       free (data_copy);
 313     }
 314 }
 315
 316 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the
 317    order specified by INSERTIONS, then deletes them in the order specified by
 318    DELETIONS, checking the set's contents for correctness after each
 319    operation.  */
 320 static void
 321 test_insert_delete (const int insertions[],
 322                     const int deletions[],
 323                     size_t cnt)
 324 {
 325   struct stringi_set set;
 326   size_t i;
 327
 328   stringi_set_init (&set);
 329   check_stringi_set (&set, NULL, 0);
 330   for (i = 0; i < cnt; i++)
 331     {
 332       check (stringi_set_insert (&set, make_string (insertions[i])));
 333       check_stringi_set (&set, insertions, i + 1);
 334     }
 335   for (i = 0; i < cnt; i++)
 336     {
 337       check (stringi_set_delete (&set, make_string (deletions[i])));
 338       check_stringi_set (&set, deletions + i + 1, cnt - i - 1);
 339     }
 340   stringi_set_destroy (&set);
 341 }
 342 \f
 343 /* Inserts strings into a set in each possible order, then removes them in each
 344    possible order, up to a specified maximum size. */
 345 static void
 346 test_insert_any_remove_any (void)
 347 {
 348   const int max_elems = 5;
 349   int cnt;
 350
 351   for (cnt = 0; cnt <= max_elems; cnt++)
 352     {
 353       int *insertions, *deletions;
 354       unsigned int ins_perm_cnt;
 355       int i;
 356
 357       insertions = xnmalloc (cnt, sizeof *insertions);
 358       deletions = xnmalloc (cnt, sizeof *deletions);
 359       for (i = 0; i < cnt; i++)
 360         insertions[i] = i;
 361
 362       for (ins_perm_cnt = 0;
 363            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 364            ins_perm_cnt++)
 365         {
 366           unsigned int del_perm_cnt;
 367           int i;
 368
 369           for (i = 0; i < cnt; i++)
 370             deletions[i] = i;
 371
 372           for (del_perm_cnt = 0;
 373                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 374                del_perm_cnt++)
 375             test_insert_delete (insertions, deletions, cnt);
 376
 377           check (del_perm_cnt == factorial (cnt));
 378         }
 379       check (ins_perm_cnt == factorial (cnt));
 380
 381       free (insertions);
 382       free (deletions);
 383     }
 384 }
 385
 386 /* Inserts strings into a set in each possible order, then removes them in the
 387    same order, up to a specified maximum size. */
 388 static void
 389 test_insert_any_remove_same (void)
 390 {
 391   const int max_elems = 7;
 392   int cnt;
 393
 394   for (cnt = 0; cnt <= max_elems; cnt++)
 395     {
 396       int *values;
 397       unsigned int permutation_cnt;
 398       int i;
 399
 400       values = xnmalloc (cnt, sizeof *values);
 401       for (i = 0; i < cnt; i++)
 402         values[i] = i;
 403
 404       for (permutation_cnt = 0;
 405            permutation_cnt == 0 || next_permutation (values, cnt);
 406            permutation_cnt++)
 407         test_insert_delete (values, values, cnt);
 408       check (permutation_cnt == factorial (cnt));
 409
 410       free (values);
 411     }
 412 }
 413
 414 /* Inserts strings into a set in each possible order, then
 415    removes them in reverse order, up to a specified maximum
 416    size. */
 417 static void
 418 test_insert_any_remove_reverse (void)
 419 {
 420   const int max_elems = 7;
 421   int cnt;
 422
 423   for (cnt = 0; cnt <= max_elems; cnt++)
 424     {
 425       int *insertions, *deletions;
 426       unsigned int permutation_cnt;
 427       int i;
 428
 429       insertions = xnmalloc (cnt, sizeof *insertions);
 430       deletions = xnmalloc (cnt, sizeof *deletions);
 431       for (i = 0; i < cnt; i++)
 432         insertions[i] = i;
 433
 434       for (permutation_cnt = 0;
 435            permutation_cnt == 0 || next_permutation (insertions, cnt);
 436            permutation_cnt++)
 437         {
 438           memcpy (deletions, insertions, sizeof *insertions * cnt);
 439           reverse (deletions, cnt);
 440
 441           test_insert_delete (insertions, deletions, cnt);
 442         }
 443       check (permutation_cnt == factorial (cnt));
 444
 445       free (insertions);
 446       free (deletions);
 447     }
 448 }
 449
 450 /* Inserts and removes strings in a set, in random order. */
 451 static void
 452 test_random_sequence (void)
 453 {
 454   const int max_elems = 64;
 455   const int max_trials = 8;
 456   int cnt;
 457
 458   for (cnt = 0; cnt <= max_elems; cnt += 2)
 459     {
 460       int *insertions, *deletions;
 461       int trial;
 462       int i;
 463
 464       insertions = xnmalloc (cnt, sizeof *insertions);
 465       deletions = xnmalloc (cnt, sizeof *deletions);
 466       for (i = 0; i < cnt; i++)
 467         insertions[i] = i;
 468       for (i = 0; i < cnt; i++)
 469         deletions[i] = i;
 470
 471       for (trial = 0; trial < max_trials; trial++)
 472         {
 473           random_shuffle (insertions, cnt, sizeof *insertions);
 474           random_shuffle (deletions, cnt, sizeof *deletions);
 475
 476           test_insert_delete (insertions, deletions, cnt);
 477         }
 478
 479       free (insertions);
 480       free (deletions);
 481     }
 482 }
 483
 484 /* Inserts strings into a set in ascending order, then delete in ascending
 485    order. */
 486 static void
 487 test_insert_ordered (void)
 488 {
 489   const int max_elems = 64;
 490   int *values;
 491   struct stringi_set set;
 492   int i;
 493
 494   stringi_set_init (&set);
 495   values = xnmalloc (max_elems, sizeof *values);
 496   for (i = 0; i < max_elems; i++)
 497     {
 498       values[i] = i;
 499       stringi_set_insert_nocopy (&set, xstrdup (make_string (i)));
 500       check_stringi_set (&set, values, i + 1);
 501     }
 502   for (i = 0; i < max_elems; i++)
 503     {
 504       stringi_set_delete (&set, make_string (i));
 505       check_stringi_set (&set, values + i + 1, max_elems - i - 1);
 506     }
 507   stringi_set_destroy (&set);
 508   free (values);
 509 }
 510
 511 static void
 512 test_boolean_ops (void (*function)(struct stringi_set *a, struct stringi_set *b,
 513                                    unsigned int *a_pat, unsigned int *b_pat))
 514 {
 515   enum { MAX_STRINGS = 7 };
 516   unsigned int a_pat, b_pat;
 517
 518   for (a_pat = 0; a_pat < (1u << MAX_STRINGS); a_pat++)
 519     for (b_pat = 0; b_pat < (1u << MAX_STRINGS); b_pat++)
 520       {
 521         unsigned int new_a_pat = a_pat;
 522         unsigned int new_b_pat = b_pat;
 523         struct stringi_set a, b;
 524         int a_strings[MAX_STRINGS], b_strings[MAX_STRINGS];
 525         size_t i, n_a, n_b;
 526
 527         stringi_set_init (&a);
 528         stringi_set_init (&b);
 529         for (i = 0; i < MAX_STRINGS; i++)
 530           {
 531             if (a_pat & (1u << i))
 532               stringi_set_insert (&a, make_string (i));
 533             if (b_pat & (1u << i))
 534               stringi_set_insert (&b, make_string (i));
 535           }
 536
 537         function (&a, &b, &new_a_pat, &new_b_pat);
 538
 539         n_a = n_b = 0;
 540         for (i = 0; i < MAX_STRINGS; i++)
 541           {
 542             if (new_a_pat & (1u << i))
 543               a_strings[n_a++] = i;
 544             if (new_b_pat & (1u << i))
 545               b_strings[n_b++] = i;
 546           }
 547         check_stringi_set (&a, a_strings, n_a);
 548         check_stringi_set (&b, b_strings, n_b);
 549         stringi_set_destroy (&a);
 550         stringi_set_destroy (&b);
 551       }
 552 }
 553
 554 static void
 555 union_cb (struct stringi_set *a, struct stringi_set *b,
 556           unsigned int *a_pat, unsigned int *b_pat)
 557 {
 558   stringi_set_union (a, b);
 559   *a_pat |= *b_pat;
 560 }
 561
 562 static void
 563 test_union (void)
 564 {
 565   test_boolean_ops (union_cb);
 566 }
 567
 568 static void
 569 union_and_intersection_cb (struct stringi_set *a, struct stringi_set *b,
 570                            unsigned int *a_pat, unsigned int *b_pat)
 571 {
 572   unsigned int orig_a_pat = *a_pat;
 573   unsigned int orig_b_pat = *b_pat;
 574
 575   stringi_set_union_and_intersection (a, b);
 576   *a_pat = orig_a_pat | orig_b_pat;
 577   *b_pat = orig_a_pat & orig_b_pat;
 578 }
 579
 580 static void
 581 test_union_and_intersection (void)
 582 {
 583   test_boolean_ops (union_and_intersection_cb);
 584 }
 585
 586 static void
 587 intersect_cb (struct stringi_set *a, struct stringi_set *b,
 588               unsigned int *a_pat, unsigned int *b_pat)
 589 {
 590   stringi_set_intersect (a, b);
 591   *a_pat &= *b_pat;
 592 }
 593
 594 static void
 595 test_intersect (void)
 596 {
 597   test_boolean_ops (intersect_cb);
 598 }
 599
 600 static void
 601 subtract_cb (struct stringi_set *a, struct stringi_set *b,
 602               unsigned int *a_pat, unsigned int *b_pat)
 603 {
 604   stringi_set_subtract (a, b);
 605   *a_pat &= ~*b_pat;
 606 }
 607
 608 static void
 609 test_subtract (void)
 610 {
 611   test_boolean_ops (subtract_cb);
 612 }
 613
 614 static void
 615 swap_cb (struct stringi_set *a, struct stringi_set *b,
 616          unsigned int *a_pat, unsigned int *b_pat)
 617 {
 618   unsigned int tmp;
 619   stringi_set_swap (a, b);
 620   tmp = *a_pat;
 621   *a_pat = *b_pat;
 622   *b_pat = tmp;
 623 }
 624
 625 static void
 626 test_swap (void)
 627 {
 628   test_boolean_ops (swap_cb);
 629 }
 630
 631 static void
 632 clear_cb (struct stringi_set *a, struct stringi_set *b UNUSED,
 633          unsigned int *a_pat, unsigned int *b_pat UNUSED)
 634 {
 635   stringi_set_clear (a);
 636   *a_pat = 0;
 637 }
 638
 639 static void
 640 test_clear (void)
 641 {
 642   test_boolean_ops (clear_cb);
 643 }
 644
 645 static void
 646 clone_cb (struct stringi_set *a, struct stringi_set *b,
 647          unsigned int *a_pat, unsigned int *b_pat)
 648 {
 649   stringi_set_destroy (a);
 650   stringi_set_clone (a, b);
 651   *a_pat = *b_pat;
 652 }
 653
 654 static void
 655 test_clone (void)
 656 {
 657   test_boolean_ops (clone_cb);
 658 }
 659
 660 static void
 661 test_destroy_null (void)
 662 {
 663   stringi_set_destroy (NULL);
 664 }
 665 \f
 666 /* Main program. */
 667
 668 /* Runs TEST_FUNCTION and prints a message about NAME. */
 669 static void
 670 run_test (void (*test_function) (void), const char *name)
 671 {
 672   test_name = name;
 673   putchar ('.');
 674   fflush (stdout);
 675   test_function ();
 676 }
 677
 678 int
 679 main (void)
 680 {
 681   run_test (test_insert_any_remove_any, "insert any order, delete any order");
 682   run_test (test_insert_any_remove_same,
 683             "insert any order, delete same order");
 684   run_test (test_insert_any_remove_reverse,
 685             "insert any order, delete reverse order");
 686   run_test (test_random_sequence, "insert and delete in random sequence");
 687   run_test (test_insert_ordered, "insert in ascending order");
 688   run_test (test_union, "union");
 689   run_test (test_union_and_intersection, "union and intersection");
 690   run_test (test_intersect, "intersect");
 691   run_test (test_subtract, "subtract");
 692   run_test (test_swap, "swap");
 693   run_test (test_clear, "clear");
 694   run_test (test_clone, "clone");
 695   run_test (test_destroy_null, "destroying null table");
 696
 697   putchar ('\n');
 698
 699   free_strings ();
 700
 701   return 0;
 702 }