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