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