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 for (i = 0; i < cnt; i++)
345 p = abt_find (abt, &e.node);
347 p = abt_insert (abt, &e.node);
349 check (p != &e.node);
350 check (abt_node_to_element (p)->data == data[i]);
354 check (abt_find (abt, &e.node) == NULL);
356 check_levels (abt->root);
357 check_augmentations (abt->root);
358 for (i = 0; i < cnt; i++)
359 check (find_by_position (abt, i)->data == order[i]);
363 check (abt_first (abt) == NULL);
364 check (abt_last (abt) == NULL);
365 check (abt_next (abt, NULL) == NULL);
366 check (abt_prev (abt, NULL) == NULL);
372 for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
373 check (abt_node_to_element (p)->data == order[i]);
376 for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
377 check (abt_node_to_element (p)->data == order[cnt - i - 1]);
384 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
385 ABT in the order specified by INSERTIONS, then deletes them in
386 the order specified by DELETIONS, checking the ABT's contents
387 for correctness after each operation. */
389 test_insert_delete (const int insertions[],
390 const int deletions[],
393 struct element *elements;
397 elements = xnmalloc (cnt, sizeof *elements);
398 for (i = 0; i < cnt; i++)
399 elements[i].data = i;
401 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
402 check_abt (&abt, NULL, 0);
403 for (i = 0; i < cnt; i++)
405 check (abt_insert (&abt, &elements[insertions[i]].node) == NULL);
406 check_abt (&abt, insertions, i + 1);
408 for (i = 0; i < cnt; i++)
410 abt_delete (&abt, &elements[deletions[i]].node);
411 check_abt (&abt, deletions + i + 1, cnt - i - 1);
417 /* Inserts values into an ABT in each possible order, then
418 removes them in each possible order, up to a specified maximum
421 test_insert_any_remove_any (void)
423 const int max_elems = 5;
426 for (cnt = 0; cnt <= max_elems; cnt++)
428 int *insertions, *deletions;
429 unsigned int ins_perm_cnt;
432 insertions = xnmalloc (cnt, sizeof *insertions);
433 deletions = xnmalloc (cnt, sizeof *deletions);
434 for (i = 0; i < cnt; i++)
437 for (ins_perm_cnt = 0;
438 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
441 unsigned int del_perm_cnt;
444 for (i = 0; i < cnt; i++)
447 for (del_perm_cnt = 0;
448 del_perm_cnt == 0 || next_permutation (deletions, cnt);
450 test_insert_delete (insertions, deletions, cnt);
452 check (del_perm_cnt == factorial (cnt));
454 check (ins_perm_cnt == factorial (cnt));
461 /* Inserts values into an ABT in each possible order, then
462 removes them in the same order, up to a specified maximum
465 test_insert_any_remove_same (void)
467 const int max_elems = 7;
470 for (cnt = 0; cnt <= max_elems; cnt++)
473 unsigned int permutation_cnt;
476 values = xnmalloc (cnt, sizeof *values);
477 for (i = 0; i < cnt; i++)
480 for (permutation_cnt = 0;
481 permutation_cnt == 0 || next_permutation (values, cnt);
483 test_insert_delete (values, values, cnt);
484 check (permutation_cnt == factorial (cnt));
490 /* Inserts values into an ABT in each possible order, then
491 removes them in reverse order, up to a specified maximum
494 test_insert_any_remove_reverse (void)
496 const int max_elems = 7;
499 for (cnt = 0; cnt <= max_elems; cnt++)
501 int *insertions, *deletions;
502 unsigned int permutation_cnt;
505 insertions = xnmalloc (cnt, sizeof *insertions);
506 deletions = xnmalloc (cnt, sizeof *deletions);
507 for (i = 0; i < cnt; i++)
510 for (permutation_cnt = 0;
511 permutation_cnt == 0 || next_permutation (insertions, cnt);
514 memcpy (deletions, insertions, sizeof *insertions * cnt);
515 reverse (deletions, cnt);
517 test_insert_delete (insertions, deletions, cnt);
519 check (permutation_cnt == factorial (cnt));
526 /* Inserts and removes values in an ABT in random orders. */
528 test_random_sequence (void)
530 const int max_elems = 128;
531 const int max_trials = 8;
534 for (cnt = 0; cnt <= max_elems; cnt += 2)
536 int *insertions, *deletions;
540 insertions = xnmalloc (cnt, sizeof *insertions);
541 deletions = xnmalloc (cnt, sizeof *deletions);
542 for (i = 0; i < cnt; i++)
544 for (i = 0; i < cnt; i++)
547 for (trial = 0; trial < max_trials; trial++)
549 random_shuffle (insertions, cnt, sizeof *insertions);
550 random_shuffle (deletions, cnt, sizeof *deletions);
552 test_insert_delete (insertions, deletions, cnt);
560 /* Inserts elements into an ABT in ascending order. */
562 test_insert_ordered (void)
564 const int max_elems = 1024;
565 struct element *elements;
570 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
571 elements = xnmalloc (max_elems, sizeof *elements);
572 values = xnmalloc (max_elems, sizeof *values);
573 for (i = 0; i < max_elems; i++)
575 values[i] = elements[i].data = i;
576 check (abt_insert (&abt, &elements[i].node) == NULL);
577 check_abt (&abt, values, i + 1);
583 /* Inserts elements into an ABT, then moves the nodes around in
588 const int max_elems = 128;
589 struct element *e[2];
595 abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
596 e[0] = xnmalloc (max_elems, sizeof *e[0]);
597 e[1] = xnmalloc (max_elems, sizeof *e[1]);
598 values = xnmalloc (max_elems, sizeof *values);
600 for (i = 0; i < max_elems; i++)
602 values[i] = e[cur][i].data = i;
603 check (abt_insert (&abt, &e[cur][i].node) == NULL);
604 check_abt (&abt, values, i + 1);
606 for (j = 0; j <= i; j++)
608 e[!cur][j] = e[cur][j];
609 abt_moved (&abt, &e[!cur][j].node);
610 check_abt (&abt, values, i + 1);
619 /* Inserts values into an ABT, then changes their values. */
623 const int max_elems = 6;
626 for (cnt = 0; cnt <= max_elems; cnt++)
628 int *values, *changed_values;
629 struct element *elements;
630 unsigned int permutation_cnt;
633 values = xnmalloc (cnt, sizeof *values);
634 changed_values = xnmalloc (cnt, sizeof *changed_values);
635 elements = xnmalloc (cnt, sizeof *elements);
636 for (i = 0; i < cnt; i++)
639 for (permutation_cnt = 0;
640 permutation_cnt == 0 || next_permutation (values, cnt);
643 for (i = 0; i < cnt; i++)
646 for (j = 0; j <= cnt; j++)
649 struct abt_node *changed_retval;
651 abt_init (&abt, compare_elements, reaugment_elements,
654 /* Add to ABT in order. */
655 for (k = 0; k < cnt; k++)
658 elements[n].data = n;
659 check (abt_insert (&abt, &elements[n].node) == NULL);
661 check_abt (&abt, values, cnt);
663 /* Change value i to j. */
664 elements[i].data = j;
665 for (k = 0; k < cnt; k++)
666 changed_values[k] = k;
667 changed_retval = abt_changed (&abt, &elements[i].node);
668 if (i != j && j < cnt)
670 /* Will cause duplicate. */
671 check (changed_retval == &elements[j].node);
672 changed_values[i] = changed_values[cnt - 1];
673 check_abt (&abt, changed_values, cnt - 1);
678 check (changed_retval == NULL);
679 changed_values[i] = j;
680 check_abt (&abt, changed_values, cnt);
685 check (permutation_cnt == factorial (cnt));
688 free (changed_values);
695 /* Runs TEST_FUNCTION and prints a message about NAME. */
697 run_test (void (*test_function) (void), const char *name)
708 run_test (test_insert_any_remove_any,
709 "insert any order, delete any order");
710 run_test (test_insert_any_remove_same,
711 "insert any order, delete same order");
712 run_test (test_insert_any_remove_reverse,
713 "insert any order, delete reverse order");
714 run_test (test_random_sequence,
715 "insert and delete in random sequence");
716 run_test (test_insert_ordered,
717 "insert in ascending order");
718 run_test (test_moved, "move elements around in memory");
719 run_test (test_changed, "change key data in nodes");