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