LOOP: Convert tests to Autotest framework.
[pspp] / 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 }