1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2010, 2011 Free Software Foundation, Inc.
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.
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.
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/>. */
17 /* This is a test program for the abt_* routines defined in
18 abt.c. This test program aims to be as comprehensive as
19 possible. "gcov -b" should report 100% coverage of lines and
20 branches in the abt_* routines. "valgrind --leak-check=yes
21 --show-reachable=yes" should give a clean report. */
27 #include <libpspp/abt.h>
36 #include <libpspp/compiler.h>
38 /* Exit with a failure code.
39 (Place a breakpoint on this function while debugging.) */
46 /* If OK is not true, prints a message about failure on the
47 current source file and the given LINE and terminates. */
49 check_func (bool ok, int line)
53 fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
58 /* Verifies that EXPR evaluates to true.
59 If not, prints a message citing the calling line number and
61 #define check(EXPR) check_func ((EXPR), __LINE__)
63 /* Prints a message about memory exhaustion and exits with a
68 printf ("virtual memory exhausted\n");
72 /* Allocates and returns N bytes of memory. */
89 xmemdup (const void *p, size_t n)
91 void *q = xmalloc (n);
96 /* Allocates and returns N * M bytes of memory. */
98 xnmalloc (size_t n, size_t m)
100 if ((size_t) -1 / m <= n)
102 return xmalloc (n * m);
105 /* Node type and support routines. */
107 /* Test data element. */
110 struct abt_node node; /* Embedded binary tree element. */
111 int data; /* Primary value. */
112 int count; /* Number of nodes in subtree,
113 including this node. */
118 /* Returns the `struct element' that NODE is embedded within. */
119 static struct element *
120 abt_node_to_element (const struct abt_node *node)
122 return abt_data (node, struct element, node);
125 /* Compares the `x' values in A and B and returns a strcmp-type
126 return value. Verifies that AUX points to aux_data. */
128 compare_elements (const struct abt_node *a_, const struct abt_node *b_,
131 const struct element *a = abt_node_to_element (a_);
132 const struct element *b = abt_node_to_element (b_);
134 check (aux == &aux_data);
135 return a->data < b->data ? -1 : a->data > b->data;
138 /* Recalculates the count for NODE's subtree by adding up the
139 counts for its LEFT and RIGHT child subtrees. */
141 reaugment_elements (struct abt_node *node_, const void *aux)
143 struct element *node = abt_node_to_element (node_);
145 check (aux == &aux_data);
148 if (node->node.down[0] != NULL)
149 node->count += abt_node_to_element (node->node.down[0])->count;
150 if (node->node.down[1] != NULL)
151 node->count += abt_node_to_element (node->node.down[1])->count;
154 /* Compares A and B and returns a strcmp-type return value. */
156 compare_ints_noaux (const void *a_, const void *b_)
161 return *a < *b ? -1 : *a > *b;
164 /* Swaps *A and *B. */
166 swap (int *a, int *b)
173 /* Reverses the order of the CNT integers starting at VALUES. */
175 reverse (int *values, size_t cnt)
181 swap (&values[i++], &values[--j]);
184 /* Arranges the CNT elements in VALUES into the lexicographically
185 next greater permutation. Returns true if successful.
186 If VALUES is already the lexicographically greatest
187 permutation of its elements (i.e. ordered from greatest to
188 smallest), arranges them into the lexicographically least
189 permutation (i.e. ordered from smallest to largest) and
192 next_permutation (int *values, size_t cnt)
200 if (values[i] < values[i + 1])
203 for (j = cnt - 1; values[i] >= values[j]; j--)
205 swap (values + i, values + j);
206 reverse (values + (i + 1), cnt - (i + 1));
211 reverse (values, cnt);
219 factorial (unsigned int n)
221 unsigned int value = 1;
227 /* Randomly shuffles the CNT elements in ARRAY, each of which is
228 SIZE bytes in size. */
230 random_shuffle (void *array_, size_t cnt, size_t size)
232 char *array = array_;
233 char *tmp = xmalloc (size);
236 for (i = 0; i < cnt; i++)
238 size_t j = rand () % (cnt - i) + i;
241 memcpy (tmp, array + j * size, size);
242 memcpy (array + j * size, array + i * size, size);
243 memcpy (array + i * size, tmp, size);
250 /* Finds and returns the element in ABT that is in the given
251 0-based POSITION in in-order. */
252 static struct element *
253 find_by_position (struct abt *abt, int position)
256 for (p = abt->root; p != NULL; )
258 int p_pos = p->down[0] ? abt_node_to_element (p->down[0])->count : 0;
259 if (position == p_pos)
260 return abt_node_to_element (p);
261 else if (position < p_pos)
266 position -= p_pos + 1;
272 /* Checks that all the augmentations are correct in the subtree
273 rooted at P. Returns the number of nodes in the subtree. */
275 check_augmentations (struct abt_node *p_)
281 struct element *p = abt_node_to_element (p_);
282 int left_count = check_augmentations (p->node.down[0]);
283 int right_count = check_augmentations (p->node.down[1]);
284 int total = left_count + right_count + 1;
285 check (p->count == total);
290 /* Check that the levels are correct in the subtree rooted at P. */
292 check_levels (struct abt_node *p)
298 check_levels (p->down[0]);
299 check_levels (p->down[1]);
301 check (p->level >= 1);
304 struct abt_node *q = p->down[1];
306 check (q->level == p->level || q->level == p->level - 1);
309 for (i = 0; i < 2; i++)
310 if (p->down[i] != NULL)
311 for (j = 0; j < 2; j++)
312 if (p->down[i]->down[j] != NULL)
313 check (p->down[i]->down[j]->level < p->level);
317 /* Checks that ABT contains the CNT ints in DATA, that its
318 structure is correct, and that certain operations on ABT
319 produce the expected results. */
321 check_abt (struct abt *abt, const int data[], size_t cnt)
327 order = xmemdup (data, cnt * sizeof *data);
328 qsort (order, cnt, sizeof *order, compare_ints_noaux);
330 if (abt->compare != NULL)
332 for (i = 0; i < cnt; i++)
338 p = abt_find (abt, &e.node);
340 p = abt_insert (abt, &e.node);
342 check (p != &e.node);
343 check (abt_node_to_element (p)->data == data[i]);
347 check (abt_find (abt, &e.node) == NULL);
350 check_levels (abt->root);
351 check_augmentations (abt->root);
352 for (i = 0; i < cnt; i++)
353 check (find_by_position (abt, i)->data == order[i]);
357 check (abt_first (abt) == NULL);
358 check (abt_last (abt) == NULL);
359 check (abt_next (abt, NULL) == NULL);
360 check (abt_prev (abt, NULL) == NULL);
366 for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
367 check (abt_node_to_element (p)->data == order[i]);
370 for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
371 check (abt_node_to_element (p)->data == order[cnt - i - 1]);
378 /* Ways that nodes can be inserted. */
379 enum insertion_method
381 INSERT, /* With abt_insert. */
382 INSERT_AFTER, /* With abt_insert_after. */
383 INSERT_BEFORE /* With abt_insert_before. */
386 /* Inserts INSERT into ABT with the given METHOD. */
388 insert_node (struct abt *abt, struct element *insert,
389 enum insertion_method method)
391 if (method == INSERT)
392 check (abt_insert (abt, &insert->node) == NULL);
395 struct abt_node *p = abt->root;
400 dir = insert->data > abt_node_to_element (p)->data;
401 if (p->down[dir] == NULL)
405 if (method == INSERT_AFTER)
407 if (p != NULL && (dir != 1 || p->down[1] != NULL))
408 p = abt_prev (abt, p);
409 abt_insert_after (abt, p, &insert->node);
413 if (p != NULL && (dir != 0 || p->down[0] != NULL))
414 p = abt_next (abt, p);
415 abt_insert_before (abt, p, &insert->node);
421 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
422 ABT in the order specified by INSERTIONS using the given
423 METHOD, then deletes them in the order specified by DELETIONS,
424 checking the ABT's contents for correctness after each
427 do_test_insert_delete (enum insertion_method method,
428 const int insertions[],
429 const int deletions[],
432 struct element *elements;
436 elements = xnmalloc (cnt, sizeof *elements);
437 for (i = 0; i < cnt; i++)
438 elements[i].data = i;
440 abt_init (&abt, method == INSERT ? compare_elements : NULL,
441 reaugment_elements, &aux_data);
442 check_abt (&abt, NULL, 0);
443 for (i = 0; i < cnt; i++)
445 insert_node (&abt, &elements[insertions[i]], method);
446 check_abt (&abt, insertions, i + 1);
448 for (i = 0; i < cnt; i++)
450 abt_delete (&abt, &elements[deletions[i]].node);
451 check_abt (&abt, deletions + i + 1, cnt - i - 1);
457 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
458 ABT in the order specified by INSERTIONS, then deletes them in
459 the order specified by DELETIONS, checking the ABT's contents
460 for correctness after each operation. */
462 test_insert_delete (const int insertions[],
463 const int deletions[],
466 do_test_insert_delete (INSERT, insertions, deletions, cnt);
467 do_test_insert_delete (INSERT_AFTER, insertions, deletions, cnt);
468 do_test_insert_delete (INSERT_BEFORE, insertions, deletions, cnt);
471 /* Inserts values into an ABT in each possible order, then
472 removes them in each possible order, up to a specified maximum
475 test_insert_any_remove_any (void)
477 const int max_elems = 5;
480 for (cnt = 0; cnt <= max_elems; cnt++)
482 int *insertions, *deletions;
483 unsigned int ins_perm_cnt;
486 insertions = xnmalloc (cnt, sizeof *insertions);
487 deletions = xnmalloc (cnt, sizeof *deletions);
488 for (i = 0; i < cnt; i++)
491 for (ins_perm_cnt = 0;
492 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
495 unsigned int del_perm_cnt;
498 for (i = 0; i < cnt; i++)
501 for (del_perm_cnt = 0;
502 del_perm_cnt == 0 || next_permutation (deletions, cnt);
504 test_insert_delete (insertions, deletions, cnt);
506 check (del_perm_cnt == factorial (cnt));
508 check (ins_perm_cnt == factorial (cnt));
515 /* Inserts values into an ABT in each possible order, then
516 removes them in the same order, up to a specified maximum
519 test_insert_any_remove_same (void)
521 const int max_elems = 7;
524 for (cnt = 0; cnt <= max_elems; cnt++)
527 unsigned int permutation_cnt;
530 values = xnmalloc (cnt, sizeof *values);
531 for (i = 0; i < cnt; i++)
534 for (permutation_cnt = 0;
535 permutation_cnt == 0 || next_permutation (values, cnt);
537 test_insert_delete (values, values, cnt);
538 check (permutation_cnt == factorial (cnt));
544 /* Inserts values into an ABT in each possible order, then
545 removes them in reverse order, up to a specified maximum
548 test_insert_any_remove_reverse (void)
550 const int max_elems = 7;
553 for (cnt = 0; cnt <= max_elems; cnt++)
555 int *insertions, *deletions;
556 unsigned int permutation_cnt;
559 insertions = xnmalloc (cnt, sizeof *insertions);
560 deletions = xnmalloc (cnt, sizeof *deletions);
561 for (i = 0; i < cnt; i++)
564 for (permutation_cnt = 0;
565 permutation_cnt == 0 || next_permutation (insertions, cnt);
568 memcpy (deletions, insertions, sizeof *insertions * cnt);
569 reverse (deletions, cnt);
571 test_insert_delete (insertions, deletions, cnt);
573 check (permutation_cnt == factorial (cnt));
580 /* Inserts and removes values in an ABT in random orders. */
582 test_random_sequence (void)
584 const int max_elems = 128;
585 const int max_trials = 8;
588 for (cnt = 0; cnt <= max_elems; cnt += 2)
590 int *insertions, *deletions;
594 insertions = xnmalloc (cnt, sizeof *insertions);
595 deletions = xnmalloc (cnt, sizeof *deletions);
596 for (i = 0; i < cnt; i++)
598 for (i = 0; i < cnt; i++)
601 for (trial = 0; trial < max_trials; trial++)
603 random_shuffle (insertions, cnt, sizeof *insertions);
604 random_shuffle (deletions, cnt, sizeof *deletions);
606 test_insert_delete (insertions, deletions, cnt);
614 /* Inserts elements into an ABT in ascending order. */
616 test_insert_ordered (void)
618 const int max_elems = 1024;
619 struct element *elements;
624 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
625 elements = xnmalloc (max_elems, sizeof *elements);
626 values = xnmalloc (max_elems, sizeof *values);
627 for (i = 0; i < max_elems; i++)
629 values[i] = elements[i].data = i;
630 check (abt_insert (&abt, &elements[i].node) == NULL);
631 check_abt (&abt, values, i + 1);
637 /* Inserts elements into an ABT, then moves the nodes around in
642 const int max_elems = 128;
643 struct element *e[2];
649 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
650 e[0] = xnmalloc (max_elems, sizeof *e[0]);
651 e[1] = xnmalloc (max_elems, sizeof *e[1]);
652 values = xnmalloc (max_elems, sizeof *values);
654 for (i = 0; i < max_elems; i++)
656 values[i] = e[cur][i].data = i;
657 check (abt_insert (&abt, &e[cur][i].node) == NULL);
658 check_abt (&abt, values, i + 1);
660 for (j = 0; j <= i; j++)
662 e[!cur][j] = e[cur][j];
663 abt_moved (&abt, &e[!cur][j].node);
664 check_abt (&abt, values, i + 1);
673 /* Inserts values into an ABT, then changes their values. */
677 const int max_elems = 6;
680 for (cnt = 0; cnt <= max_elems; cnt++)
682 int *values, *changed_values;
683 struct element *elements;
684 unsigned int permutation_cnt;
687 values = xnmalloc (cnt, sizeof *values);
688 changed_values = xnmalloc (cnt, sizeof *changed_values);
689 elements = xnmalloc (cnt, sizeof *elements);
690 for (i = 0; i < cnt; i++)
693 for (permutation_cnt = 0;
694 permutation_cnt == 0 || next_permutation (values, cnt);
697 for (i = 0; i < cnt; i++)
700 for (j = 0; j <= cnt; j++)
703 struct abt_node *changed_retval;
705 abt_init (&abt, compare_elements, reaugment_elements,
708 /* Add to ABT in order. */
709 for (k = 0; k < cnt; k++)
712 elements[n].data = n;
713 check (abt_insert (&abt, &elements[n].node) == NULL);
715 check_abt (&abt, values, cnt);
717 /* Change value i to j. */
718 elements[i].data = j;
719 for (k = 0; k < cnt; k++)
720 changed_values[k] = k;
721 changed_retval = abt_changed (&abt, &elements[i].node);
722 if (i != j && j < cnt)
724 /* Will cause duplicate. */
725 check (changed_retval == &elements[j].node);
726 changed_values[i] = changed_values[cnt - 1];
727 check_abt (&abt, changed_values, cnt - 1);
732 check (changed_retval == NULL);
733 changed_values[i] = j;
734 check_abt (&abt, changed_values, cnt);
739 check (permutation_cnt == factorial (cnt));
742 free (changed_values);
752 const char *description;
753 void (*function) (void);
756 static const struct test tests[] =
759 "insert-any-remove-any",
760 "insert any order, delete any order",
761 test_insert_any_remove_any
764 "insert-any-remove-same",
765 "insert any order, delete same order",
766 test_insert_any_remove_same
769 "insert-any-remove-reverse",
770 "insert any order, delete reverse order",
771 test_insert_any_remove_reverse
775 "insert and delete in random sequence",
780 "insert in ascending order",
785 "move elements around in memory",
790 "change key data in nodes",
795 enum { N_TESTS = sizeof tests / sizeof *tests };
798 main (int argc, char *argv[])
804 fprintf (stderr, "exactly one argument required; use --help for help\n");
807 else if (!strcmp (argv[1], "--help"))
809 printf ("%s: test augmented binary tree\n"
810 "usage: %s TEST-NAME\n"
811 "where TEST-NAME is one of the following:\n",
813 for (i = 0; i < N_TESTS; i++)
814 printf (" %s\n %s\n", tests[i].name, tests[i].description);
819 for (i = 0; i < N_TESTS; i++)
820 if (!strcmp (argv[1], tests[i].name))
822 tests[i].function ();
826 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);