1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007 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 bt_* routines defined in bt.c.
18 This test program aims to be as comprehensive as possible.
19 "gcov -b" should report 100% coverage of lines and branches in
20 bt.c. "valgrind --leak-check=yes --show-reachable=yes" should
21 give a clean report. */
27 #include <libpspp/bt.h>
37 #include <libpspp/compiler.h>
39 /* Currently running test. */
40 static const char *test_name;
42 /* Exit with a failure code.
43 (Place a breakpoint on this function while debugging.) */
50 /* If OK is not true, prints a message about failure on the
51 current source file and the given LINE and terminates. */
53 check_func (bool ok, int line)
57 printf ("Check failed in %s test at %s, line %d\n",
58 test_name, __FILE__, line);
63 /* Verifies that EXPR evaluates to true.
64 If not, prints a message citing the calling line number and
66 #define check(EXPR) check_func ((EXPR), __LINE__)
68 /* Prints a message about memory exhaustion and exits with a
73 printf ("virtual memory exhausted\n");
77 /* Allocates and returns N bytes of memory. */
94 xmemdup (const void *p, size_t n)
96 void *q = xmalloc (n);
101 /* Allocates and returns N * M bytes of memory. */
103 xnmalloc (size_t n, size_t m)
105 if ((size_t) -1 / m <= n)
107 return xmalloc (n * m);
110 /* Node type and support routines. */
112 /* Test data element. */
115 struct bt_node node; /* Embedded binary tree element. */
116 int data; /* Primary value. */
121 /* Returns the `struct element' that NODE is embedded within. */
122 static struct element *
123 bt_node_to_element (const struct bt_node *node)
125 return bt_data (node, struct element, node);
128 /* Compares the `x' values in A and B and returns a strcmp-type
129 return value. Verifies that AUX points to aux_data. */
131 compare_elements (const struct bt_node *a_, const struct bt_node *b_,
134 const struct element *a = bt_node_to_element (a_);
135 const struct element *b = bt_node_to_element (b_);
137 check (aux == &aux_data);
138 return a->data < b->data ? -1 : a->data > b->data;
141 /* Compares A and B and returns a strcmp-type return value. */
143 compare_ints_noaux (const void *a_, const void *b_)
148 return *a < *b ? -1 : *a > *b;
151 /* Swaps *A and *B. */
153 swap (int *a, int *b)
160 /* Reverses the order of the CNT integers starting at VALUES. */
162 reverse (int *values, size_t cnt)
168 swap (&values[i++], &values[--j]);
171 /* Arranges the CNT elements in VALUES into the lexicographically
172 next greater permutation. Returns true if successful.
173 If VALUES is already the lexicographically greatest
174 permutation of its elements (i.e. ordered from greatest to
175 smallest), arranges them into the lexicographically least
176 permutation (i.e. ordered from smallest to largest) and
179 next_permutation (int *values, size_t cnt)
187 if (values[i] < values[i + 1])
190 for (j = cnt - 1; values[i] >= values[j]; j--)
192 swap (values + i, values + j);
193 reverse (values + (i + 1), cnt - (i + 1));
198 reverse (values, cnt);
206 factorial (unsigned int n)
208 unsigned int value = 1;
214 /* Randomly shuffles the CNT elements in ARRAY, each of which is
215 SIZE bytes in size. */
217 random_shuffle (void *array_, size_t cnt, size_t size)
219 char *array = array_;
220 char *tmp = xmalloc (size);
223 for (i = 0; i < cnt; i++)
225 size_t j = rand () % (cnt - i) + i;
228 memcpy (tmp, array + j * size, size);
229 memcpy (array + j * size, array + i * size, size);
230 memcpy (array + i * size, tmp, size);
237 /* Calculates floor(log(n)/log(sqrt(2))). */
239 calculate_h_alpha (size_t n)
241 size_t thresholds[] =
243 0, 2, 2, 3, 4, 6, 8, 12, 16, 23, 32, 46, 64, 91, 128, 182, 256, 363,
244 512, 725, 1024, 1449, 2048, 2897, 4096, 5793, 8192, 11586, 16384,
245 23171, 32768, 46341, 65536, 92682, 131072, 185364, 262144, 370728,
246 524288, 741456, 1048576, 1482911, 2097152, 2965821, 4194304, 5931642,
247 8388608, 11863284, 16777216, 23726567, 33554432, 47453133, 67108864,
248 94906266, 134217728, 189812532, 268435456, 379625063, 536870912,
249 759250125, 1073741824, 1518500250, 2147483648, 3037000500,
251 size_t threshold_cnt = sizeof thresholds / sizeof *thresholds;
254 for (i = 0; i < threshold_cnt; i++)
255 if (thresholds[i] > n)
260 /* Returns the height of the tree rooted at NODE. */
262 get_height (struct bt_node *node)
268 int left = get_height (node->down[0]);
269 int right = get_height (node->down[1]);
270 return 1 + (left > right ? left : right);
274 /* Checks that BT is loosely alpha-height balanced, that is, that
275 its height is no more than h_alpha(count) + 1, where
276 h_alpha(n) = floor(log(n)/log(1/alpha)). */
278 check_balance (struct bt *bt)
280 /* In the notation of the Galperin and Rivest paper (and of
281 CLR), the height of a tree is the number of edges in the
282 longest path from the root to a leaf, so we have to subtract
283 1 from our measured height. */
284 int height = get_height (bt->root) - 1;
285 int max_height = calculate_h_alpha (bt_count (bt)) + 1;
286 check (height <= max_height);
289 /* Checks that BT contains the CNT ints in DATA, that its
290 structure is correct, and that certain operations on BT
291 produce the expected results. */
293 check_bt (struct bt *bt, const int data[], size_t cnt)
299 order = xmemdup (data, cnt * sizeof *data);
300 qsort (order, cnt, sizeof *order, compare_ints_noaux);
302 for (i = 0; i < cnt; i++)
308 p = bt_find (bt, &e.node);
310 p = bt_insert (bt, &e.node);
312 check (p != &e.node);
313 check (bt_node_to_element (p)->data == data[i]);
317 check (bt_find (bt, &e.node) == NULL);
323 check (bt_first (bt) == NULL);
324 check (bt_last (bt) == NULL);
325 check (bt_next (bt, NULL) == NULL);
326 check (bt_prev (bt, NULL) == NULL);
332 for (p = bt_first (bt), i = 0; i < cnt; p = bt_next (bt, p), i++)
333 check (bt_node_to_element (p)->data == order[i]);
336 for (p = bt_last (bt), i = 0; i < cnt; p = bt_prev (bt, p), i++)
337 check (bt_node_to_element (p)->data == order[cnt - i - 1]);
344 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
345 BT in the order specified by INSERTIONS, then deletes them in
346 the order specified by DELETIONS, checking the BT's contents
347 for correctness after each operation. */
349 test_insert_delete (const int insertions[],
350 const int deletions[],
353 struct element *elements;
357 elements = xnmalloc (cnt, sizeof *elements);
358 for (i = 0; i < cnt; i++)
359 elements[i].data = i;
361 bt_init (&bt, compare_elements, &aux_data);
362 check_bt (&bt, NULL, 0);
363 for (i = 0; i < cnt; i++)
365 check (bt_insert (&bt, &elements[insertions[i]].node) == NULL);
366 check_bt (&bt, insertions, i + 1);
368 for (i = 0; i < cnt; i++)
370 bt_delete (&bt, &elements[deletions[i]].node);
371 check_bt (&bt, deletions + i + 1, cnt - i - 1);
377 /* Inserts values into an BT in each possible order, then
378 removes them in each possible order, up to a specified maximum
381 test_insert_any_remove_any (void)
383 const int max_elems = 5;
386 for (cnt = 0; cnt <= max_elems; cnt++)
388 int *insertions, *deletions;
389 unsigned int ins_perm_cnt;
392 insertions = xnmalloc (cnt, sizeof *insertions);
393 deletions = xnmalloc (cnt, sizeof *deletions);
394 for (i = 0; i < cnt; i++)
397 for (ins_perm_cnt = 0;
398 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
401 unsigned int del_perm_cnt;
404 for (i = 0; i < cnt; i++)
407 for (del_perm_cnt = 0;
408 del_perm_cnt == 0 || next_permutation (deletions, cnt);
410 test_insert_delete (insertions, deletions, cnt);
412 check (del_perm_cnt == factorial (cnt));
414 check (ins_perm_cnt == factorial (cnt));
421 /* Inserts values into an BT in each possible order, then
422 removes them in the same order, up to a specified maximum
425 test_insert_any_remove_same (void)
427 const int max_elems = 7;
430 for (cnt = 0; cnt <= max_elems; cnt++)
433 unsigned int permutation_cnt;
436 values = xnmalloc (cnt, sizeof *values);
437 for (i = 0; i < cnt; i++)
440 for (permutation_cnt = 0;
441 permutation_cnt == 0 || next_permutation (values, cnt);
443 test_insert_delete (values, values, cnt);
444 check (permutation_cnt == factorial (cnt));
450 /* Inserts values into an BT in each possible order, then
451 removes them in reverse order, up to a specified maximum
454 test_insert_any_remove_reverse (void)
456 const int max_elems = 7;
459 for (cnt = 0; cnt <= max_elems; cnt++)
461 int *insertions, *deletions;
462 unsigned int permutation_cnt;
465 insertions = xnmalloc (cnt, sizeof *insertions);
466 deletions = xnmalloc (cnt, sizeof *deletions);
467 for (i = 0; i < cnt; i++)
470 for (permutation_cnt = 0;
471 permutation_cnt == 0 || next_permutation (insertions, cnt);
474 memcpy (deletions, insertions, sizeof *insertions * cnt);
475 reverse (deletions, cnt);
477 test_insert_delete (insertions, deletions, cnt);
479 check (permutation_cnt == factorial (cnt));
486 /* Inserts and removes values in an BT in random orders. */
488 test_random_sequence (void)
490 const int max_elems = 128;
491 const int max_trials = 8;
494 for (cnt = 0; cnt <= max_elems; cnt += 2)
496 int *insertions, *deletions;
500 insertions = xnmalloc (cnt, sizeof *insertions);
501 deletions = xnmalloc (cnt, sizeof *deletions);
502 for (i = 0; i < cnt; i++)
504 for (i = 0; i < cnt; i++)
507 for (trial = 0; trial < max_trials; trial++)
509 random_shuffle (insertions, cnt, sizeof *insertions);
510 random_shuffle (deletions, cnt, sizeof *deletions);
512 test_insert_delete (insertions, deletions, cnt);
520 /* Inserts elements into an BT in ascending order. */
522 test_insert_ordered (void)
524 const int max_elems = 1024;
525 struct element *elements;
530 bt_init (&bt, compare_elements, &aux_data);
531 elements = xnmalloc (max_elems, sizeof *elements);
532 values = xnmalloc (max_elems, sizeof *values);
533 for (i = 0; i < max_elems; i++)
535 values[i] = elements[i].data = i;
536 check (bt_insert (&bt, &elements[i].node) == NULL);
537 check_bt (&bt, values, i + 1);
543 /* Tests bt_find_ge and bt_find_le. */
545 test_find_ge_le (void)
547 const int max_elems = 10;
548 struct element *elements;
550 unsigned int inc_pat;
552 elements = xnmalloc (max_elems, sizeof *elements);
553 values = xnmalloc (max_elems, sizeof *values);
554 for (inc_pat = 0; inc_pat < (1u << max_elems); inc_pat++)
560 /* Insert the values in the pattern into BT. */
561 bt_init (&bt, compare_elements, &aux_data);
562 for (i = 0; i < max_elems; i++)
563 if (inc_pat & (1u << i))
565 values[elem_cnt] = elements[elem_cnt].data = i;
566 check (bt_insert (&bt, &elements[elem_cnt].node) == NULL);
569 check_bt (&bt, values, elem_cnt);
571 /* Try find_ge and find_le for each possible element value. */
572 for (i = -1; i <= max_elems; i++)
575 struct bt_node *ge, *le;
579 for (j = 0; j < elem_cnt; j++)
581 if (ge == NULL && values[j] >= i)
582 ge = &elements[j].node;
584 le = &elements[j].node;
588 check (bt_find_ge (&bt, &tmp.node) == ge);
589 check (bt_find_le (&bt, &tmp.node) == le);
596 /* Inserts elements into an BT, then moves the nodes around in
601 const int max_elems = 128;
602 struct element *e[2];
608 bt_init (&bt, compare_elements, &aux_data);
609 e[0] = xnmalloc (max_elems, sizeof *e[0]);
610 e[1] = xnmalloc (max_elems, sizeof *e[1]);
611 values = xnmalloc (max_elems, sizeof *values);
613 for (i = 0; i < max_elems; i++)
615 values[i] = e[cur][i].data = i;
616 check (bt_insert (&bt, &e[cur][i].node) == NULL);
617 check_bt (&bt, values, i + 1);
619 for (j = 0; j <= i; j++)
621 e[!cur][j] = e[cur][j];
622 bt_moved (&bt, &e[!cur][j].node);
623 check_bt (&bt, values, i + 1);
632 /* Inserts values into an BT, then changes their values. */
636 const int max_elems = 6;
639 for (cnt = 0; cnt <= max_elems; cnt++)
641 int *values, *changed_values;
642 struct element *elements;
643 unsigned int permutation_cnt;
646 values = xnmalloc (cnt, sizeof *values);
647 changed_values = xnmalloc (cnt, sizeof *changed_values);
648 elements = xnmalloc (cnt, sizeof *elements);
649 for (i = 0; i < cnt; i++)
652 for (permutation_cnt = 0;
653 permutation_cnt == 0 || next_permutation (values, cnt);
656 for (i = 0; i < cnt; i++)
659 for (j = 0; j <= cnt; j++)
662 struct bt_node *changed_retval;
664 bt_init (&bt, compare_elements, &aux_data);
666 /* Add to BT in order. */
667 for (k = 0; k < cnt; k++)
670 elements[n].data = n;
671 check (bt_insert (&bt, &elements[n].node) == NULL);
673 check_bt (&bt, values, cnt);
675 /* Change value i to j. */
676 elements[i].data = j;
677 for (k = 0; k < cnt; k++)
678 changed_values[k] = k;
679 changed_retval = bt_changed (&bt, &elements[i].node);
680 if (i != j && j < cnt)
682 /* Will cause duplicate. */
683 check (changed_retval == &elements[j].node);
684 changed_values[i] = changed_values[cnt - 1];
685 check_bt (&bt, changed_values, cnt - 1);
690 check (changed_retval == NULL);
691 changed_values[i] = j;
692 check_bt (&bt, changed_values, cnt);
697 check (permutation_cnt == factorial (cnt));
700 free (changed_values);
707 /* Runs TEST_FUNCTION and prints a message about NAME. */
709 run_test (void (*test_function) (void), const char *name)
720 run_test (test_insert_any_remove_any,
721 "insert any order, delete any order");
722 run_test (test_insert_any_remove_same,
723 "insert any order, delete same order");
724 run_test (test_insert_any_remove_reverse,
725 "insert any order, delete reverse order");
726 run_test (test_random_sequence,
727 "insert and delete in random sequence");
728 run_test (test_insert_ordered,
729 "insert in ascending order");
730 run_test (test_find_ge_le, "find_ge and find_le");
731 run_test (test_moved, "move elements around in memory");
732 run_test (test_changed, "change key data in nodes");