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]);
374 check (abt_is_empty (abt) == (cnt == 0));
379 /* Ways that nodes can be inserted. */
380 enum insertion_method
382 INSERT, /* With abt_insert. */
383 INSERT_AFTER, /* With abt_insert_after. */
384 INSERT_BEFORE /* With abt_insert_before. */
387 /* Inserts INSERT into ABT with the given METHOD. */
389 insert_node (struct abt *abt, struct element *insert,
390 enum insertion_method method)
392 if (method == INSERT)
393 check (abt_insert (abt, &insert->node) == NULL);
396 struct abt_node *p = abt->root;
401 dir = insert->data > abt_node_to_element (p)->data;
402 if (p->down[dir] == NULL)
406 if (method == INSERT_AFTER)
408 if (p != NULL && (dir != 1 || p->down[1] != NULL))
409 p = abt_prev (abt, p);
410 abt_insert_after (abt, p, &insert->node);
414 if (p != NULL && (dir != 0 || p->down[0] != NULL))
415 p = abt_next (abt, p);
416 abt_insert_before (abt, p, &insert->node);
422 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
423 ABT in the order specified by INSERTIONS using the given
424 METHOD, then deletes them in the order specified by DELETIONS,
425 checking the ABT's contents for correctness after each
428 do_test_insert_delete (enum insertion_method method,
429 const int insertions[],
430 const int deletions[],
433 struct element *elements;
437 elements = xnmalloc (cnt, sizeof *elements);
438 for (i = 0; i < cnt; i++)
439 elements[i].data = i;
441 abt_init (&abt, method == INSERT ? compare_elements : NULL,
442 reaugment_elements, &aux_data);
443 check_abt (&abt, NULL, 0);
444 for (i = 0; i < cnt; i++)
446 insert_node (&abt, &elements[insertions[i]], method);
447 check_abt (&abt, insertions, i + 1);
449 for (i = 0; i < cnt; i++)
451 abt_delete (&abt, &elements[deletions[i]].node);
452 check_abt (&abt, deletions + i + 1, cnt - i - 1);
458 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
459 ABT in the order specified by INSERTIONS, then deletes them in
460 the order specified by DELETIONS, checking the ABT's contents
461 for correctness after each operation. */
463 test_insert_delete (const int insertions[],
464 const int deletions[],
467 do_test_insert_delete (INSERT, insertions, deletions, cnt);
468 do_test_insert_delete (INSERT_AFTER, insertions, deletions, cnt);
469 do_test_insert_delete (INSERT_BEFORE, insertions, deletions, cnt);
472 /* Inserts values into an ABT in each possible order, then
473 removes them in each possible order, up to a specified maximum
476 test_insert_any_remove_any (void)
478 const int max_elems = 5;
481 for (cnt = 0; cnt <= max_elems; cnt++)
483 int *insertions, *deletions;
484 unsigned int ins_perm_cnt;
487 insertions = xnmalloc (cnt, sizeof *insertions);
488 deletions = xnmalloc (cnt, sizeof *deletions);
489 for (i = 0; i < cnt; i++)
492 for (ins_perm_cnt = 0;
493 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
496 unsigned int del_perm_cnt;
499 for (i = 0; i < cnt; i++)
502 for (del_perm_cnt = 0;
503 del_perm_cnt == 0 || next_permutation (deletions, cnt);
505 test_insert_delete (insertions, deletions, cnt);
507 check (del_perm_cnt == factorial (cnt));
509 check (ins_perm_cnt == factorial (cnt));
516 /* Inserts values into an ABT in each possible order, then
517 removes them in the same order, up to a specified maximum
520 test_insert_any_remove_same (void)
522 const int max_elems = 7;
525 for (cnt = 0; cnt <= max_elems; cnt++)
528 unsigned int permutation_cnt;
531 values = xnmalloc (cnt, sizeof *values);
532 for (i = 0; i < cnt; i++)
535 for (permutation_cnt = 0;
536 permutation_cnt == 0 || next_permutation (values, cnt);
538 test_insert_delete (values, values, cnt);
539 check (permutation_cnt == factorial (cnt));
545 /* Inserts values into an ABT in each possible order, then
546 removes them in reverse order, up to a specified maximum
549 test_insert_any_remove_reverse (void)
551 const int max_elems = 7;
554 for (cnt = 0; cnt <= max_elems; cnt++)
556 int *insertions, *deletions;
557 unsigned int permutation_cnt;
560 insertions = xnmalloc (cnt, sizeof *insertions);
561 deletions = xnmalloc (cnt, sizeof *deletions);
562 for (i = 0; i < cnt; i++)
565 for (permutation_cnt = 0;
566 permutation_cnt == 0 || next_permutation (insertions, cnt);
569 memcpy (deletions, insertions, sizeof *insertions * cnt);
570 reverse (deletions, cnt);
572 test_insert_delete (insertions, deletions, cnt);
574 check (permutation_cnt == factorial (cnt));
581 /* Inserts and removes values in an ABT in random orders. */
583 test_random_sequence (void)
585 const int max_elems = 128;
586 const int max_trials = 8;
589 for (cnt = 0; cnt <= max_elems; cnt += 2)
591 int *insertions, *deletions;
595 insertions = xnmalloc (cnt, sizeof *insertions);
596 deletions = xnmalloc (cnt, sizeof *deletions);
597 for (i = 0; i < cnt; i++)
599 for (i = 0; i < cnt; i++)
602 for (trial = 0; trial < max_trials; trial++)
604 random_shuffle (insertions, cnt, sizeof *insertions);
605 random_shuffle (deletions, cnt, sizeof *deletions);
607 test_insert_delete (insertions, deletions, cnt);
615 /* Inserts elements into an ABT in ascending order. */
617 test_insert_ordered (void)
619 const int max_elems = 1024;
620 struct element *elements;
625 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
626 elements = xnmalloc (max_elems, sizeof *elements);
627 values = xnmalloc (max_elems, sizeof *values);
628 for (i = 0; i < max_elems; i++)
630 values[i] = elements[i].data = i;
631 check (abt_insert (&abt, &elements[i].node) == NULL);
632 check_abt (&abt, values, i + 1);
638 /* Inserts elements into an ABT, then moves the nodes around in
643 const int max_elems = 128;
644 struct element *e[2];
650 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
651 e[0] = xnmalloc (max_elems, sizeof *e[0]);
652 e[1] = xnmalloc (max_elems, sizeof *e[1]);
653 values = xnmalloc (max_elems, sizeof *values);
655 for (i = 0; i < max_elems; i++)
657 values[i] = e[cur][i].data = i;
658 check (abt_insert (&abt, &e[cur][i].node) == NULL);
659 check_abt (&abt, values, i + 1);
661 for (j = 0; j <= i; j++)
663 e[!cur][j] = e[cur][j];
664 abt_moved (&abt, &e[!cur][j].node);
665 check_abt (&abt, values, i + 1);
674 /* Inserts values into an ABT, then changes their values. */
678 const int max_elems = 6;
681 for (cnt = 0; cnt <= max_elems; cnt++)
683 int *values, *changed_values;
684 struct element *elements;
685 unsigned int permutation_cnt;
688 values = xnmalloc (cnt, sizeof *values);
689 changed_values = xnmalloc (cnt, sizeof *changed_values);
690 elements = xnmalloc (cnt, sizeof *elements);
691 for (i = 0; i < cnt; i++)
694 for (permutation_cnt = 0;
695 permutation_cnt == 0 || next_permutation (values, cnt);
698 for (i = 0; i < cnt; i++)
701 for (j = 0; j <= cnt; j++)
704 struct abt_node *changed_retval;
706 abt_init (&abt, compare_elements, reaugment_elements,
709 /* Add to ABT in order. */
710 for (k = 0; k < cnt; k++)
713 elements[n].data = n;
714 check (abt_insert (&abt, &elements[n].node) == NULL);
716 check_abt (&abt, values, cnt);
718 /* Change value i to j. */
719 elements[i].data = j;
720 for (k = 0; k < cnt; k++)
721 changed_values[k] = k;
722 changed_retval = abt_changed (&abt, &elements[i].node);
723 if (i != j && j < cnt)
725 /* Will cause duplicate. */
726 check (changed_retval == &elements[j].node);
727 changed_values[i] = changed_values[cnt - 1];
728 check_abt (&abt, changed_values, cnt - 1);
733 check (changed_retval == NULL);
734 changed_values[i] = j;
735 check_abt (&abt, changed_values, cnt);
740 check (permutation_cnt == factorial (cnt));
743 free (changed_values);
753 const char *description;
754 void (*function) (void);
757 static const struct test tests[] =
760 "insert-any-remove-any",
761 "insert any order, delete any order",
762 test_insert_any_remove_any
765 "insert-any-remove-same",
766 "insert any order, delete same order",
767 test_insert_any_remove_same
770 "insert-any-remove-reverse",
771 "insert any order, delete reverse order",
772 test_insert_any_remove_reverse
776 "insert and delete in random sequence",
781 "insert in ascending order",
786 "move elements around in memory",
791 "change key data in nodes",
796 enum { N_TESTS = sizeof tests / sizeof *tests };
799 main (int argc, char *argv[])
805 fprintf (stderr, "exactly one argument required; use --help for help\n");
808 else if (!strcmp (argv[1], "--help"))
810 printf ("%s: test augmented binary tree\n"
811 "usage: %s TEST-NAME\n"
812 "where TEST-NAME is one of the following:\n",
814 for (i = 0; i < N_TESTS; i++)
815 printf (" %s\n %s\n", tests[i].name, tests[i].description);
820 for (i = 0; i < N_TESTS; i++)
821 if (!strcmp (argv[1], tests[i].name))
823 tests[i].function ();
827 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);