1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2010, 2013 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 routines defined in tower.c.
18    This test program aims to be as comprehensive as possible.
19    With -DNDEBUG, "gcov -b" should report 100% coverage of lines
20    and branches in tower.c routines.  (Without -DNDEBUG, branches
21    caused by failed assertions will not be taken.)  "valgrind
22    --leak-check=yes --show-reachable=yes" should give a clean
23    report, both with and without -DNDEBUG. */
24 
25 #ifdef HAVE_CONFIG_H
26 #include <config.h>
27 #endif
28 
29 #include <libpspp/tower.h>
30 
31 #include <assert.h>
32 #include <limits.h>
33 #include <stdint.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <string.h>
37 
38 #include <libpspp/compiler.h>
39 
40 #include "xalloc.h"
41 
42 /* Exit with a failure code.
43    (Place a breakpoint on this function while debugging.) */
44 static void
check_die(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
check_func(bool ok,int line)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 /* Node type and support routines. */
68 
69 /* Test data block. */
70 struct block
71   {
72     struct tower_node node;     /* Embedded tower block. */
73     int x;                      /* Primary value. */
74   };
75 
76 /* Returns the `struct block' that NODE is embedded within. */
77 static struct block *
tower_node_to_block(const struct tower_node * node)78 tower_node_to_block (const struct tower_node *node)
79 {
80   return tower_data (node, struct block, node);
81 }
82 
83 /* Swaps *A and *B. */
84 static void
swap(int * a,int * b)85 swap (int *a, int *b)
86 {
87   int t = *a;
88   *a = *b;
89   *b = t;
90 }
91 
92 /* Reverses the order of the CNT integers starting at VALUES. */
93 static void
reverse(int * values,size_t cnt)94 reverse (int *values, size_t cnt)
95 {
96   size_t i = 0;
97   size_t j = cnt;
98 
99   while (j > i)
100     swap (&values[i++], &values[--j]);
101 }
102 
103 /* Arranges the CNT blocks in VALUES into the lexicographically
104    next greater permutation.  Returns true if successful.
105    If VALUES is already the lexicographically greatest
106    permutation of its blocks (i.e. ordered from greatest to
107    smallest), arranges them into the lexicographically least
108    permutation (i.e. ordered from smallest to largest) and
109    returns false. */
110 static bool
next_permutation(int * values,size_t cnt)111 next_permutation (int *values, size_t cnt)
112 {
113   if (cnt > 0)
114     {
115       size_t i = cnt - 1;
116       while (i != 0)
117         {
118           i--;
119           if (values[i] < values[i + 1])
120             {
121               size_t j;
122               for (j = cnt - 1; values[i] >= values[j]; j--)
123                 continue;
124               swap (values + i, values + j);
125               reverse (values + (i + 1), cnt - (i + 1));
126               return true;
127             }
128         }
129 
130       reverse (values, cnt);
131     }
132 
133   return false;
134 }
135 
136 /* Returns N!. */
137 static unsigned int
factorial(unsigned int n)138 factorial (unsigned int n)
139 {
140   unsigned int value = 1;
141   /* Disallow N values that overflow on 32-bit machines. */
142   assert (n <= 12);
143   for (; n > 1;)
144     value *= n--;
145   return value;
146 }
147 
148 /* Returns C(n, k), the number of ways that K choices can be made
149    from N items when order is unimportant. */
150 static unsigned int
binomial_cofficient(unsigned int n,unsigned int k)151 binomial_cofficient (unsigned int n, unsigned int k)
152 {
153   assert (n >= k);
154   return factorial (n) / factorial (k) / factorial (n - k);
155 }
156 
157 /* Tests whether PARTS is a K-part integer composition of N.
158    Returns true if so, false otherwise. */
159 static bool UNUSED
is_k_composition(int n,int k,const int parts[])160 is_k_composition (int n, int k, const int parts[])
161 {
162   int sum;
163   int i;
164 
165   sum = 0;
166   for (i = 0; i < k; i++)
167     {
168       if (parts[i] < 1 || parts[i] > n)
169         return false;
170       sum += parts[i];
171     }
172   return sum == n;
173 }
174 
175 /* Advances the K-part integer composition of N stored in PARTS
176    to the next lexicographically greater one.
177    Returns true if successful, false if the composition was
178    already the greatest K-part composition of N (in which case
179    PARTS is unaltered). */
180 static bool
next_k_composition(int n UNUSED,int k,int parts[])181 next_k_composition (int n UNUSED, int k, int parts[])
182 {
183   int x, i;
184 
185   assert (is_k_composition (n, k, parts));
186   if (k == 1)
187     return false;
188 
189   for (i = k - 1; i > 0; i--)
190     if (parts[i] > 1)
191       break;
192   if (i == 0)
193     return false;
194 
195   x = parts[i] - 1;
196   parts[i] = 1;
197   parts[i - 1]++;
198   parts[k - 1] = x;
199 
200   assert (is_k_composition (n, k, parts));
201   return true;
202 }
203 
204 /* Sets the K integers in PARTS to the lexicographically first
205    K-part composition of N. */
206 static void
first_k_composition(int n,int k,int parts[])207 first_k_composition (int n, int k, int parts[])
208 {
209   int i;
210 
211   assert (n >= k);
212 
213   for (i = 0; i < k; i++)
214     parts[i] = 1;
215   parts[k - 1] += n - k;
216 }
217 
218 /* Advances *K and PARTS to the next integer composition of N.
219    Compositions are ordered from shortest to longest and in
220    lexicographical order within a given length.
221    Before the first call, initialize *K to 0.
222    After each successful call, *K contains the length of the
223    current composition and the *K blocks in PARTS contain its
224    parts.
225    Returns true if successful, false if the set of compositions
226    has been exhausted. */
227 static bool
next_composition(int n,int * k,int parts[])228 next_composition (int n, int *k, int parts[])
229 {
230   if (*k >= 1 && next_k_composition (n, *k, parts))
231     return true;
232   else if (*k < n)
233     {
234       first_k_composition (n, ++*k, parts);
235       return true;
236     }
237   else
238     return false;
239 }
240 
241 /* A block expected to be found in a tower. */
242 struct expected_block
243   {
244     int size;           /* Expected thickness of block. */
245     int x;              /* Expected value for `x' member. */
246   };
247 
248 /* Checks that tower T contains the BLOCK_CNT blocks described by
249    BLOCKS[]. */
250 static void
check_tower(struct tower * t,struct expected_block blocks[],size_t block_cnt)251 check_tower (struct tower *t,
252              struct expected_block blocks[], size_t block_cnt)
253 {
254   int total_height;
255   struct tower_node *node;
256   size_t i;
257 
258   check (tower_count (t) == block_cnt);
259   check (tower_is_empty (t) == (block_cnt == 0));
260 
261   total_height = 0;
262   for (i = 0; i < block_cnt; i++)
263     {
264       unsigned long int level;
265       for (level = total_height;
266            level < total_height + blocks[i].size;
267            level++)
268         {
269           struct tower_node *found;
270           unsigned long int block_start;
271           found = tower_lookup (t, level, &block_start);
272           check (found != NULL);
273           check (tower_node_to_block (found)->x == blocks[i].x);
274           check (block_start == total_height);
275           check (tower_node_get_level (found) == total_height);
276           check (tower_node_get_index (found) == i);
277           check (tower_get (t, i) == found);
278         }
279       total_height += blocks[i].size;
280     }
281   check (tower_height (t) == total_height);
282 
283   for (node = tower_first (t), i = 0;
284        node != NULL;
285        node = tower_next (t, node), i++)
286     {
287       check (tower_node_get_size (node) == blocks[i].size);
288       check (tower_node_to_block (node)->x == blocks[i].x);
289     }
290   check (i == block_cnt);
291 
292   for (node = tower_last (t), i = block_cnt - 1;
293        node != NULL;
294        node = tower_prev (t, node), i--)
295     {
296       check (tower_node_get_size (node) == blocks[i].size);
297       check (tower_node_to_block (node)->x == blocks[i].x);
298     }
299   check (i == SIZE_MAX);
300 }
301 
302 /* Tests inserting all possible sets of block heights into a
303    tower in all possible orders, up to a specified maximum tower
304    height. */
305 static void
test_insert(void)306 test_insert (void)
307 {
308   const int max_height = 7;
309   int cnt;
310 
311   for (cnt = 1; cnt <= max_height; cnt++)
312     {
313       unsigned int composition_cnt;
314       struct expected_block *expected;
315       int *sizes;
316       int block_cnt;
317       int *order;
318       struct block *blocks;
319 
320       expected = xnmalloc (cnt, sizeof *expected);
321       sizes = xnmalloc (cnt, sizeof *sizes);
322       order = xnmalloc (cnt, sizeof *order);
323       blocks = xnmalloc (cnt, sizeof *blocks);
324 
325       block_cnt = 0;
326       composition_cnt = 0;
327       while (next_composition (cnt, &block_cnt, sizes))
328         {
329           int i, j;
330           unsigned int permutation_cnt;
331 
332           for (i = 0; i < block_cnt; i++)
333             order[i] = i;
334 
335           permutation_cnt = 0;
336           while (permutation_cnt == 0 || next_permutation (order, block_cnt))
337             {
338               struct tower t;
339 
340               /* Inserts the block_cnt blocks with the given
341                  sizes[] into T in the order given by order[]. */
342               tower_init (&t);
343               for (i = 0; i < block_cnt; i++)
344                 {
345                   struct block *under;
346                   int idx;
347 
348                   idx = order[i];
349                   blocks[idx].x = idx;
350 
351                   under = NULL;
352                   for (j = 0; j < i; j++)
353                     if (idx < order[j]
354                         && (under == NULL || under->x > order[j]))
355                       under = &blocks[order[j]];
356 
357                   tower_insert (&t, sizes[idx], &blocks[idx].node,
358                                 under != NULL ? &under->node : NULL);
359                 }
360 
361               /* Check that the result is what we expect. */
362               for (i = 0; i < block_cnt; i++)
363                 {
364                   expected[i].size = sizes[i];
365                   expected[i].x = i;
366                 }
367               check_tower (&t, expected, block_cnt);
368 
369               permutation_cnt++;
370             }
371           check (permutation_cnt == factorial (block_cnt));
372 
373           composition_cnt++;
374         }
375       check (composition_cnt == 1 << (cnt - 1));
376 
377       free (expected);
378       free (sizes);
379       free (order);
380       free (blocks);
381     }
382 }
383 
384 /* Tests deleting blocks from towers that initially contain all
385    possible sets of block sizes into a tower in all possible
386    orders, up to a specified maximum tower height. */
387 static void
test_delete(void)388 test_delete (void)
389 {
390   const int max_height = 7;
391   int cnt;
392 
393   for (cnt = 1; cnt <= max_height; cnt++)
394     {
395       unsigned int composition_cnt;
396       struct expected_block *expected;
397       int *sizes;
398       int block_cnt;
399       int *order;
400       struct block *blocks;
401 
402       expected = xnmalloc (cnt, sizeof *expected);
403       sizes = xnmalloc (cnt, sizeof *sizes);
404       order = xnmalloc (cnt, sizeof *order);
405       blocks = xnmalloc (cnt, sizeof *blocks);
406 
407       block_cnt = 0;
408       composition_cnt = 0;
409       while (next_composition (cnt, &block_cnt, sizes))
410         {
411           int i;
412           unsigned int permutation_cnt;
413 
414           for (i = 0; i < block_cnt; i++)
415             order[i] = i;
416 
417           permutation_cnt = 0;
418           while (permutation_cnt == 0 || next_permutation (order, block_cnt))
419             {
420               struct tower t;
421 
422               /* Insert blocks into tower in ascending order. */
423               tower_init (&t);
424               for (i = 0; i < block_cnt; i++)
425                 {
426                   blocks[i].x = i;
427                   tower_insert (&t, sizes[i], &blocks[i].node, NULL);
428                   expected[i].x = i;
429                   expected[i].size = sizes[i];
430                 }
431               check_tower (&t, expected, block_cnt);
432 
433               /* Delete blocks from tower in the order of
434                  order[]. */
435               for (i = 0; i < block_cnt; i++)
436                 {
437                   int idx = order[i];
438                   int j;
439                   tower_delete (&t, &blocks[idx].node);
440                   for (j = 0; ; j++)
441                     {
442                       assert (j < block_cnt - i);
443                       if (expected[j].x == idx)
444                         {
445                           memmove (&expected[j], &expected[j + 1],
446                                    sizeof *expected * (block_cnt - i - j - 1));
447                           break;
448                         }
449                     }
450                   check_tower (&t, expected, block_cnt - i - 1);
451                 }
452 
453               permutation_cnt++;
454             }
455           check (permutation_cnt == factorial (block_cnt));
456 
457           composition_cnt++;
458         }
459       check (composition_cnt == 1 << (cnt - 1));
460 
461       free (expected);
462       free (sizes);
463       free (order);
464       free (blocks);
465     }
466 }
467 
468 /* Tests towers containing all possible block sizes, resizing
469    the blocks to all possible sizes that conserve the total
470    tower height, up to a maximum total tower height. */
471 static void
test_resize(void)472 test_resize (void)
473 {
474   const int max_height = 9;
475   int cnt;
476 
477   for (cnt = 1; cnt <= max_height; cnt++)
478     {
479       unsigned int composition_cnt;
480       struct expected_block *expected;
481       int *sizes, *new_sizes;
482       int block_cnt;
483       int *order;
484       struct block *blocks;
485 
486       expected = xnmalloc (cnt, sizeof *expected);
487       sizes = xnmalloc (cnt, sizeof *sizes);
488       new_sizes = xnmalloc (cnt, sizeof *new_sizes);
489       order = xnmalloc (cnt, sizeof *order);
490       blocks = xnmalloc (cnt, sizeof *blocks);
491 
492       block_cnt = 0;
493       composition_cnt = 0;
494       while (next_composition (cnt, &block_cnt, sizes))
495         {
496           int i;
497           unsigned int resizes = 0;
498 
499           for (resizes = 0, first_k_composition (cnt, block_cnt, new_sizes);
500                (resizes == 0
501                 || next_k_composition (cnt, block_cnt, new_sizes));
502                resizes++)
503             {
504               struct tower t;
505 
506               /* Insert blocks into tower in ascending order. */
507               tower_init (&t);
508               for (i = 0; i < block_cnt; i++)
509                 {
510                   blocks[i].x = i;
511                   tower_insert (&t, sizes[i], &blocks[i].node, NULL);
512                   expected[i].x = i;
513                   expected[i].size = sizes[i];
514                 }
515               check_tower (&t, expected, block_cnt);
516 
517               /* Resize all the blocks. */
518               for (i = 0; i < block_cnt; i++)
519                 {
520                   if (expected[i].size != new_sizes[i] || rand () % 2)
521                     tower_resize (&t, &blocks[i].node, new_sizes[i]);
522                   expected[i].size = new_sizes[i];
523                 }
524               check_tower (&t, expected, block_cnt);
525             }
526           check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1));
527 
528           composition_cnt++;
529         }
530       check (composition_cnt == 1 << (cnt - 1));
531 
532       free (expected);
533       free (new_sizes);
534       free (sizes);
535       free (order);
536       free (blocks);
537     }
538 }
539 
540 /* Tests splicing all possible contiguous sets of blocks out of one
541    tower into a second, initially empty tower. */
542 static void
test_splice_out(void)543 test_splice_out (void)
544 {
545   const int max_height = 9;
546   int cnt;
547 
548   for (cnt = 1; cnt <= max_height; cnt++)
549     {
550       unsigned int composition_cnt;
551       struct expected_block *expected;
552       int *sizes, *new_sizes;
553       int block_cnt;
554       int *order;
555       struct block *blocks;
556 
557       expected = xnmalloc (cnt, sizeof *expected);
558       sizes = xnmalloc (cnt, sizeof *sizes);
559       new_sizes = xnmalloc (cnt, sizeof *new_sizes);
560       order = xnmalloc (cnt, sizeof *order);
561       blocks = xnmalloc (cnt, sizeof *blocks);
562 
563       block_cnt = 0;
564       composition_cnt = 0;
565       while (next_composition (cnt, &block_cnt, sizes))
566         {
567           int i, j;
568 
569           for (i = 0; i < block_cnt; i++)
570             for (j = i; j <= block_cnt; j++)
571               {
572                 struct tower src, dst;
573                 int k;
574 
575                 tower_init (&src);
576                 tower_init (&dst);
577 
578                 /* Insert blocks into SRC and DST in ascending order. */
579                 for (k = 0; k < block_cnt; k++)
580                   {
581                     blocks[k].x = k;
582                     tower_insert (&src, sizes[k], &blocks[k].node, NULL);
583                     expected[k].x = k;
584                     expected[k].size = sizes[k];
585                   }
586                 check_tower (&src, expected, block_cnt);
587 
588                 /* Splice blocks I...J into DST. */
589                 tower_splice (&dst, NULL, &src, &blocks[i].node,
590                               j < block_cnt ? &blocks[j].node : NULL);
591                 check_tower (&dst, &expected[i], j - i);
592                 memmove (&expected[i], &expected[j],
593                          sizeof *expected * (block_cnt - j));
594                 check_tower (&src, expected, block_cnt - (j - i));
595               }
596            composition_cnt++;
597         }
598       check (composition_cnt == 1 << (cnt - 1));
599 
600       free (expected);
601       free (new_sizes);
602       free (sizes);
603       free (order);
604       free (blocks);
605     }
606 }
607 
608 /* Tests splicing all of the contents of a tower into all
609    possible positions in a second tower. */
610 static void
test_splice_in(void)611 test_splice_in (void)
612 {
613   const int max_height = 9;
614   int cnt;
615 
616   for (cnt = 1; cnt <= max_height; cnt++)
617     {
618       unsigned int composition_cnt;
619       struct expected_block *expected;
620       int *sizes, *new_sizes;
621       int block_cnt;
622       int *order;
623       struct block *blocks;
624 
625       expected = xnmalloc (cnt, sizeof *expected);
626       sizes = xnmalloc (cnt, sizeof *sizes);
627       new_sizes = xnmalloc (cnt, sizeof *new_sizes);
628       order = xnmalloc (cnt, sizeof *order);
629       blocks = xnmalloc (cnt, sizeof *blocks);
630 
631       block_cnt = 0;
632       composition_cnt = 0;
633       while (next_composition (cnt, &block_cnt, sizes))
634         {
635           int i, j;
636 
637           for (i = 0; i < block_cnt; i++)
638             for (j = i; j <= block_cnt; j++)
639               {
640                 struct tower src, dst;
641                 int k;
642 
643                 tower_init (&src);
644                 tower_init (&dst);
645 
646                 /* Insert blocks into SRC and DST in ascending order. */
647                 for (k = 0; k < block_cnt; k++)
648                   {
649                     blocks[k].x = k;
650                     tower_insert (k >= i && k < j ? &src : &dst,
651                                   sizes[k], &blocks[k].node, NULL);
652                     expected[k].x = k;
653                     expected[k].size = sizes[k];
654                   }
655 
656                 /* Splice SRC into DST. */
657                 tower_splice (&dst, j < block_cnt ? &blocks[j].node : NULL,
658                               &src, i != j ? &blocks[i].node : NULL, NULL);
659                 check_tower (&dst, expected, block_cnt);
660               }
661            composition_cnt++;
662         }
663       check (composition_cnt == 1 << (cnt - 1));
664 
665       free (expected);
666       free (new_sizes);
667       free (sizes);
668       free (order);
669       free (blocks);
670     }
671 }
672 
673 
674 /* Main program. */
675 
676 struct test
677   {
678     const char *name;
679     const char *description;
680     void (*function) (void);
681   };
682 
683 static const struct test tests[] =
684   {
685     {
686       "insert",
687       "insert",
688       test_insert
689     },
690     {
691       "delete",
692       "delete",
693       test_delete
694     },
695     {
696       "resize",
697       "resize",
698       test_resize
699     },
700     {
701       "splice-out",
702       "splice out",
703       test_splice_out
704     },
705     {
706       "splice-in",
707       "splice in",
708       test_splice_in
709     },
710   };
711 
712 enum { N_TESTS = sizeof tests / sizeof *tests };
713 
714 int
main(int argc,char * argv[])715 main (int argc, char *argv[])
716 {
717   int i;
718 
719   if (argc != 2)
720     {
721       fprintf (stderr, "exactly one argument required; use --help for help\n");
722       return EXIT_FAILURE;
723     }
724   else if (!strcmp (argv[1], "--help"))
725     {
726       printf ("%s: test tower library\n"
727               "usage: %s TEST-NAME\n"
728               "where TEST-NAME is one of the following:\n",
729               argv[0], argv[0]);
730       for (i = 0; i < N_TESTS; i++)
731         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
732       return 0;
733     }
734   else
735     {
736       for (i = 0; i < N_TESTS; i++)
737         if (!strcmp (argv[1], tests[i].name))
738           {
739             tests[i].function ();
740             return 0;
741           }
742 
743       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
744       return EXIT_FAILURE;
745     }
746 }
747