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