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