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