1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 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, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* This is a test program for the abt_* routines defined in
20 abt.c. This test program aims to be as comprehensive as
21 possible. "gcov -b" should report 100% coverage of lines and
22 branches in the abt_* routines. "valgrind --leak-check=yes
23 --show-reachable=yes" should give a clean report. */
29 #include <libpspp/abt.h>
38 #include <libpspp/compiler.h>
40 /* Currently running test. */
41 static const char *test_name;
43 /* Exit with a failure code.
44 (Place a breakpoint on this function while debugging.) */
51 /* If OK is not true, prints a message about failure on the
52 current source file and the given LINE and terminates. */
54 check_func (bool ok, int line)
58 printf ("Check failed in %s test at %s, line %d\n",
59 test_name, __FILE__, line);
64 /* Verifies that EXPR evaluates to true.
65 If not, prints a message citing the calling line number and
67 #define check(EXPR) check_func ((EXPR), __LINE__)
69 /* Prints a message about memory exhaustion and exits with a
74 printf ("virtual memory exhausted\n");
78 /* Allocates and returns N bytes of memory. */
95 xmemdup (const void *p, size_t n)
97 void *q = xmalloc (n);
102 /* Allocates and returns N * M bytes of memory. */
104 xnmalloc (size_t n, size_t m)
106 if ((size_t) -1 / m <= n)
108 return xmalloc (n * m);
111 /* Node type and support routines. */
113 /* Test data element. */
116 struct abt_node node; /* Embedded binary tree element. */
117 int data; /* Primary value. */
118 int count; /* Number of nodes in subtree,
119 including this node. */
124 /* Returns the `struct element' that NODE is embedded within. */
125 static struct element *
126 abt_node_to_element (const struct abt_node *node)
128 return abt_data (node, struct element, node);
131 /* Compares the `x' values in A and B and returns a strcmp-type
132 return value. Verifies that AUX points to aux_data. */
134 compare_elements (const struct abt_node *a_, const struct abt_node *b_,
137 const struct element *a = abt_node_to_element (a_);
138 const struct element *b = abt_node_to_element (b_);
140 check (aux == &aux_data);
141 return a->data < b->data ? -1 : a->data > b->data;
144 /* Recalculates the count for NODE's subtree by adding up the
145 counts for its LEFT and RIGHT child subtrees. */
147 reaugment_elements (struct abt_node *node_,
148 const struct abt_node *left,
149 const struct abt_node *right,
152 struct element *node = abt_node_to_element (node_);
154 check (aux == &aux_data);
158 node->count += abt_node_to_element (left)->count;
160 node->count += abt_node_to_element (right)->count;
163 /* Compares A and B and returns a strcmp-type return value. */
165 compare_ints_noaux (const void *a_, const void *b_)
170 return *a < *b ? -1 : *a > *b;
173 /* Swaps *A and *B. */
175 swap (int *a, int *b)
182 /* Reverses the order of the CNT integers starting at VALUES. */
184 reverse (int *values, size_t cnt)
190 swap (&values[i++], &values[--j]);
193 /* Arranges the CNT elements in VALUES into the lexicographically
194 next greater permutation. Returns true if successful.
195 If VALUES is already the lexicographically greatest
196 permutation of its elements (i.e. ordered from greatest to
197 smallest), arranges them into the lexicographically least
198 permutation (i.e. ordered from smallest to largest) and
201 next_permutation (int *values, size_t cnt)
209 if (values[i] < values[i + 1])
212 for (j = cnt - 1; values[i] >= values[j]; j--)
214 swap (values + i, values + j);
215 reverse (values + (i + 1), cnt - (i + 1));
220 reverse (values, cnt);
228 factorial (unsigned int n)
230 unsigned int value = 1;
236 /* Randomly shuffles the CNT elements in ARRAY, each of which is
237 SIZE bytes in size. */
239 random_shuffle (void *array_, size_t cnt, size_t size)
241 char *array = array_;
242 char *tmp = xmalloc (size);
245 for (i = 0; i < cnt; i++)
247 size_t j = rand () % (cnt - i) + i;
250 memcpy (tmp, array + j * size, size);
251 memcpy (array + j * size, array + i * size, size);
252 memcpy (array + i * size, tmp, size);
259 /* Finds and returns the element in ABT that is in the given
260 0-based POSITION in in-order. */
261 static struct element *
262 find_by_position (struct abt *abt, int position)
265 for (p = abt->root; p != NULL; )
267 int p_pos = p->down[0] ? abt_node_to_element (p->down[0])->count : 0;
268 if (position == p_pos)
269 return abt_node_to_element (p);
270 else if (position < p_pos)
275 position -= p_pos + 1;
281 /* Checks that all the augmentations are correct in the subtree
282 rooted at P. Returns the number of nodes in the subtree. */
284 check_augmentations (struct abt_node *p_)
290 struct element *p = abt_node_to_element (p_);
291 int left_count = check_augmentations (p->node.down[0]);
292 int right_count = check_augmentations (p->node.down[1]);
293 int total = left_count + right_count + 1;
294 check (p->count == total);
299 /* Check that the levels are correct in the subtree rooted at P. */
301 check_levels (struct abt_node *p)
307 check_levels (p->down[0]);
308 check_levels (p->down[1]);
310 check (p->level >= 1);
313 struct abt_node *q = p->down[1];
315 check (q->level == p->level || q->level == p->level - 1);
318 for (i = 0; i < 2; i++)
319 if (p->down[i] != NULL)
320 for (j = 0; j < 2; j++)
321 if (p->down[i]->down[j] != NULL)
322 check (p->down[i]->down[j]->level < p->level);
326 /* Checks that ABT contains the CNT ints in DATA, that its
327 structure is correct, and that certain operations on ABT
328 produce the expected results. */
330 check_abt (struct abt *abt, const int data[], size_t cnt)
336 order = xmemdup (data, cnt * sizeof *data);
337 qsort (order, cnt, sizeof *order, compare_ints_noaux);
339 if (abt->compare != NULL)
341 for (i = 0; i < cnt; i++)
347 p = abt_find (abt, &e.node);
349 p = abt_insert (abt, &e.node);
351 check (p != &e.node);
352 check (abt_node_to_element (p)->data == data[i]);
356 check (abt_find (abt, &e.node) == NULL);
359 check_levels (abt->root);
360 check_augmentations (abt->root);
361 for (i = 0; i < cnt; i++)
362 check (find_by_position (abt, i)->data == order[i]);
366 check (abt_first (abt) == NULL);
367 check (abt_last (abt) == NULL);
368 check (abt_next (abt, NULL) == NULL);
369 check (abt_prev (abt, NULL) == NULL);
375 for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
376 check (abt_node_to_element (p)->data == order[i]);
379 for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
380 check (abt_node_to_element (p)->data == order[cnt - i - 1]);
387 /* Ways that nodes can be inserted. */
388 enum insertion_method
390 INSERT, /* With abt_insert. */
391 INSERT_AFTER, /* With abt_insert_after. */
392 INSERT_BEFORE /* With abt_insert_before. */
395 /* Inserts INSERT into ABT with the given METHOD. */
397 insert_node (struct abt *abt, struct element *insert,
398 enum insertion_method method)
400 if (method == INSERT)
401 check (abt_insert (abt, &insert->node) == NULL);
404 struct abt_node *p = abt->root;
409 dir = insert->data > abt_node_to_element (p)->data;
410 if (p->down[dir] == NULL)
414 if (method == INSERT_AFTER)
416 if (p != NULL && (dir != 1 || p->down[1] != NULL))
417 p = abt_prev (abt, p);
418 abt_insert_after (abt, p, &insert->node);
422 if (p != NULL && (dir != 0 || p->down[0] != NULL))
423 p = abt_next (abt, p);
424 abt_insert_before (abt, p, &insert->node);
430 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
431 ABT in the order specified by INSERTIONS using the given
432 METHOD, then deletes them in the order specified by DELETIONS,
433 checking the ABT's contents for correctness after each
436 do_test_insert_delete (enum insertion_method method,
437 const int insertions[],
438 const int deletions[],
441 struct element *elements;
445 elements = xnmalloc (cnt, sizeof *elements);
446 for (i = 0; i < cnt; i++)
447 elements[i].data = i;
449 abt_init (&abt, method == INSERT ? compare_elements : NULL,
450 reaugment_elements, &aux_data);
451 check_abt (&abt, NULL, 0);
452 for (i = 0; i < cnt; i++)
454 insert_node (&abt, &elements[insertions[i]], method);
455 check_abt (&abt, insertions, i + 1);
457 for (i = 0; i < cnt; i++)
459 abt_delete (&abt, &elements[deletions[i]].node);
460 check_abt (&abt, deletions + i + 1, cnt - i - 1);
466 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
467 ABT in the order specified by INSERTIONS, then deletes them in
468 the order specified by DELETIONS, checking the ABT's contents
469 for correctness after each operation. */
471 test_insert_delete (const int insertions[],
472 const int deletions[],
475 do_test_insert_delete (INSERT, insertions, deletions, cnt);
476 do_test_insert_delete (INSERT_AFTER, insertions, deletions, cnt);
477 do_test_insert_delete (INSERT_BEFORE, insertions, deletions, cnt);
480 /* Inserts values into an ABT in each possible order, then
481 removes them in each possible order, up to a specified maximum
484 test_insert_any_remove_any (void)
486 const int max_elems = 5;
489 for (cnt = 0; cnt <= max_elems; cnt++)
491 int *insertions, *deletions;
492 unsigned int ins_perm_cnt;
495 insertions = xnmalloc (cnt, sizeof *insertions);
496 deletions = xnmalloc (cnt, sizeof *deletions);
497 for (i = 0; i < cnt; i++)
500 for (ins_perm_cnt = 0;
501 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
504 unsigned int del_perm_cnt;
507 for (i = 0; i < cnt; i++)
510 for (del_perm_cnt = 0;
511 del_perm_cnt == 0 || next_permutation (deletions, cnt);
513 test_insert_delete (insertions, deletions, cnt);
515 check (del_perm_cnt == factorial (cnt));
517 check (ins_perm_cnt == factorial (cnt));
524 /* Inserts values into an ABT in each possible order, then
525 removes them in the same order, up to a specified maximum
528 test_insert_any_remove_same (void)
530 const int max_elems = 7;
533 for (cnt = 0; cnt <= max_elems; cnt++)
536 unsigned int permutation_cnt;
539 values = xnmalloc (cnt, sizeof *values);
540 for (i = 0; i < cnt; i++)
543 for (permutation_cnt = 0;
544 permutation_cnt == 0 || next_permutation (values, cnt);
546 test_insert_delete (values, values, cnt);
547 check (permutation_cnt == factorial (cnt));
553 /* Inserts values into an ABT in each possible order, then
554 removes them in reverse order, up to a specified maximum
557 test_insert_any_remove_reverse (void)
559 const int max_elems = 7;
562 for (cnt = 0; cnt <= max_elems; cnt++)
564 int *insertions, *deletions;
565 unsigned int permutation_cnt;
568 insertions = xnmalloc (cnt, sizeof *insertions);
569 deletions = xnmalloc (cnt, sizeof *deletions);
570 for (i = 0; i < cnt; i++)
573 for (permutation_cnt = 0;
574 permutation_cnt == 0 || next_permutation (insertions, cnt);
577 memcpy (deletions, insertions, sizeof *insertions * cnt);
578 reverse (deletions, cnt);
580 test_insert_delete (insertions, deletions, cnt);
582 check (permutation_cnt == factorial (cnt));
589 /* Inserts and removes values in an ABT in random orders. */
591 test_random_sequence (void)
593 const int max_elems = 128;
594 const int max_trials = 8;
597 for (cnt = 0; cnt <= max_elems; cnt += 2)
599 int *insertions, *deletions;
603 insertions = xnmalloc (cnt, sizeof *insertions);
604 deletions = xnmalloc (cnt, sizeof *deletions);
605 for (i = 0; i < cnt; i++)
607 for (i = 0; i < cnt; i++)
610 for (trial = 0; trial < max_trials; trial++)
612 random_shuffle (insertions, cnt, sizeof *insertions);
613 random_shuffle (deletions, cnt, sizeof *deletions);
615 test_insert_delete (insertions, deletions, cnt);
623 /* Inserts elements into an ABT in ascending order. */
625 test_insert_ordered (void)
627 const int max_elems = 1024;
628 struct element *elements;
633 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
634 elements = xnmalloc (max_elems, sizeof *elements);
635 values = xnmalloc (max_elems, sizeof *values);
636 for (i = 0; i < max_elems; i++)
638 values[i] = elements[i].data = i;
639 check (abt_insert (&abt, &elements[i].node) == NULL);
640 check_abt (&abt, values, i + 1);
646 /* Inserts elements into an ABT, then moves the nodes around in
651 const int max_elems = 128;
652 struct element *e[2];
658 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
659 e[0] = xnmalloc (max_elems, sizeof *e[0]);
660 e[1] = xnmalloc (max_elems, sizeof *e[1]);
661 values = xnmalloc (max_elems, sizeof *values);
663 for (i = 0; i < max_elems; i++)
665 values[i] = e[cur][i].data = i;
666 check (abt_insert (&abt, &e[cur][i].node) == NULL);
667 check_abt (&abt, values, i + 1);
669 for (j = 0; j <= i; j++)
671 e[!cur][j] = e[cur][j];
672 abt_moved (&abt, &e[!cur][j].node);
673 check_abt (&abt, values, i + 1);
682 /* Inserts values into an ABT, then changes their values. */
686 const int max_elems = 6;
689 for (cnt = 0; cnt <= max_elems; cnt++)
691 int *values, *changed_values;
692 struct element *elements;
693 unsigned int permutation_cnt;
696 values = xnmalloc (cnt, sizeof *values);
697 changed_values = xnmalloc (cnt, sizeof *changed_values);
698 elements = xnmalloc (cnt, sizeof *elements);
699 for (i = 0; i < cnt; i++)
702 for (permutation_cnt = 0;
703 permutation_cnt == 0 || next_permutation (values, cnt);
706 for (i = 0; i < cnt; i++)
709 for (j = 0; j <= cnt; j++)
712 struct abt_node *changed_retval;
714 abt_init (&abt, compare_elements, reaugment_elements,
717 /* Add to ABT in order. */
718 for (k = 0; k < cnt; k++)
721 elements[n].data = n;
722 check (abt_insert (&abt, &elements[n].node) == NULL);
724 check_abt (&abt, values, cnt);
726 /* Change value i to j. */
727 elements[i].data = j;
728 for (k = 0; k < cnt; k++)
729 changed_values[k] = k;
730 changed_retval = abt_changed (&abt, &elements[i].node);
731 if (i != j && j < cnt)
733 /* Will cause duplicate. */
734 check (changed_retval == &elements[j].node);
735 changed_values[i] = changed_values[cnt - 1];
736 check_abt (&abt, changed_values, cnt - 1);
741 check (changed_retval == NULL);
742 changed_values[i] = j;
743 check_abt (&abt, changed_values, cnt);
748 check (permutation_cnt == factorial (cnt));
751 free (changed_values);
758 /* Runs TEST_FUNCTION and prints a message about NAME. */
760 run_test (void (*test_function) (void), const char *name)
771 run_test (test_insert_any_remove_any,
772 "insert any order, delete any order");
773 run_test (test_insert_any_remove_same,
774 "insert any order, delete same order");
775 run_test (test_insert_any_remove_reverse,
776 "insert any order, delete reverse order");
777 run_test (test_random_sequence,
778 "insert and delete in random sequence");
779 run_test (test_insert_ordered,
780 "insert in ascending order");
781 run_test (test_moved, "move elements around in memory");
782 run_test (test_changed, "change key data in nodes");