1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2010 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
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. */
22
23 #ifdef HAVE_CONFIG_H
24 #include <config.h>
25 #endif
26
27 #include <libpspp/bt.h>
28
29 #include <stdbool.h>
30 #include <stddef.h>
31 #include <stdint.h>
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35
36 #include <libpspp/compiler.h>
37
38 /* Exit with a failure code.
39 (Place a breakpoint on this function while debugging.) */
40 static void
check_die(void)41 check_die (void)
42 {
43 exit (EXIT_FAILURE);
44 }
45
46 /* If OK is not true, prints a message about failure on the
47 current source file and the given LINE and terminates. */
48 static void
check_func(bool ok,int line)49 check_func (bool ok, int line)
50 {
51 if (!ok)
52 {
53 fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
54 check_die ();
55 }
56 }
57
58 /* Verifies that EXPR evaluates to true.
59 If not, prints a message citing the calling line number and
60 terminates. */
61 #define check(EXPR) check_func ((EXPR), __LINE__)
62
63 /* Prints a message about memory exhaustion and exits with a
64 failure code. */
65 static void
xalloc_die(void)66 xalloc_die (void)
67 {
68 printf ("virtual memory exhausted\n");
69 exit (EXIT_FAILURE);
70 }
71
72 /* Allocates and returns N bytes of memory. */
73 static void *
xmalloc(size_t n)74 xmalloc (size_t n)
75 {
76 if (n != 0)
77 {
78 void *p = malloc (n);
79 if (p == NULL)
80 xalloc_die ();
81
82 return p;
83 }
84 else
85 return NULL;
86 }
87
88 static void *
xmemdup(const void * p,size_t n)89 xmemdup (const void *p, size_t n)
90 {
91 void *q = xmalloc (n);
92 memcpy (q, p, n);
93 return q;
94 }
95
96 /* Allocates and returns N * M bytes of memory. */
97 static void *
xnmalloc(size_t n,size_t m)98 xnmalloc (size_t n, size_t m)
99 {
100 if ((size_t) -1 / m <= n)
101 xalloc_die ();
102 return xmalloc (n * m);
103 }
104
105 /* Node type and support routines. */
106
107 /* Test data element. */
108 struct element
109 {
110 struct bt_node node; /* Embedded binary tree element. */
111 int data; /* Primary value. */
112 };
113
114 static int aux_data;
115
116 /* Returns the `struct element' that NODE is embedded within. */
117 static struct element *
bt_node_to_element(const struct bt_node * node)118 bt_node_to_element (const struct bt_node *node)
119 {
120 return BT_DATA (node, struct element, node);
121 }
122
123 /* Compares the `x' values in A and B and returns a strcmp-type
124 return value. Verifies that AUX points to aux_data. */
125 static int
compare_elements(const struct bt_node * a_,const struct bt_node * b_,const void * aux)126 compare_elements (const struct bt_node *a_, const struct bt_node *b_,
127 const void *aux)
128 {
129 const struct element *a = bt_node_to_element (a_);
130 const struct element *b = bt_node_to_element (b_);
131
132 check (aux == &aux_data);
133 return a->data < b->data ? -1 : a->data > b->data;
134 }
135
136 /* Compares A and B and returns a strcmp-type return value. */
137 static int
compare_ints_noaux(const void * a_,const void * b_)138 compare_ints_noaux (const void *a_, const void *b_)
139 {
140 const int *a = a_;
141 const int *b = b_;
142
143 return *a < *b ? -1 : *a > *b;
144 }
145
146 /* Swaps *A and *B. */
147 static void
swap(int * a,int * b)148 swap (int *a, int *b)
149 {
150 int t = *a;
151 *a = *b;
152 *b = t;
153 }
154
155 /* Reverses the order of the CNT integers starting at VALUES. */
156 static void
reverse(int * values,size_t cnt)157 reverse (int *values, size_t cnt)
158 {
159 size_t i = 0;
160 size_t j = cnt;
161
162 while (j > i)
163 swap (&values[i++], &values[--j]);
164 }
165
166 /* Arranges the CNT elements in VALUES into the lexicographically
167 next greater permutation. Returns true if successful.
168 If VALUES is already the lexicographically greatest
169 permutation of its elements (i.e. ordered from greatest to
170 smallest), arranges them into the lexicographically least
171 permutation (i.e. ordered from smallest to largest) and
172 returns false. */
173 static bool
next_permutation(int * values,size_t cnt)174 next_permutation (int *values, size_t cnt)
175 {
176 if (cnt > 0)
177 {
178 size_t i = cnt - 1;
179 while (i != 0)
180 {
181 i--;
182 if (values[i] < values[i + 1])
183 {
184 size_t j;
185 for (j = cnt - 1; values[i] >= values[j]; j--)
186 continue;
187 swap (values + i, values + j);
188 reverse (values + (i + 1), cnt - (i + 1));
189 return true;
190 }
191 }
192
193 reverse (values, cnt);
194 }
195
196 return false;
197 }
198
199 /* Returns N!. */
200 static unsigned int
factorial(unsigned int n)201 factorial (unsigned int n)
202 {
203 unsigned int value = 1;
204 while (n > 1)
205 value *= n--;
206 return value;
207 }
208
209 /* Randomly shuffles the CNT elements in ARRAY, each of which is
210 SIZE bytes in size. */
211 static void
random_shuffle(void * array_,size_t cnt,size_t size)212 random_shuffle (void *array_, size_t cnt, size_t size)
213 {
214 char *array = array_;
215 char *tmp = xmalloc (size);
216 size_t i;
217
218 for (i = 0; i < cnt; i++)
219 {
220 size_t j = rand () % (cnt - i) + i;
221 if (i != j)
222 {
223 memcpy (tmp, array + j * size, size);
224 memcpy (array + j * size, array + i * size, size);
225 memcpy (array + i * size, tmp, size);
226 }
227 }
228
229 free (tmp);
230 }
231
232 /* Calculates floor(log(n)/log(sqrt(2))). */
233 static int
calculate_h_alpha(size_t n)234 calculate_h_alpha (size_t n)
235 {
236 size_t thresholds[] =
237 {
238 0, 2, 2, 3, 4, 6, 8, 12, 16, 23, 32, 46, 64, 91, 128, 182, 256, 363,
239 512, 725, 1024, 1449, 2048, 2897, 4096, 5793, 8192, 11586, 16384,
240 23171, 32768, 46341, 65536, 92682, 131072, 185364, 262144, 370728,
241 524288, 741456, 1048576, 1482911, 2097152, 2965821, 4194304, 5931642,
242 8388608, 11863284, 16777216, 23726567, 33554432, 47453133, 67108864,
243 94906266, 134217728, 189812532, 268435456, 379625063, 536870912,
244 759250125, 1073741824, 1518500250, 2147483648, 3037000500,
245 };
246 size_t threshold_cnt = sizeof thresholds / sizeof *thresholds;
247 size_t i;
248
249 for (i = 0; i < threshold_cnt; i++)
250 if (thresholds[i] > n)
251 break;
252 return i - 1;
253 }
254
255 /* Returns the height of the tree rooted at NODE. */
256 static int
get_height(struct bt_node * node)257 get_height (struct bt_node *node)
258 {
259 if (node == NULL)
260 return 0;
261 else
262 {
263 int left = get_height (node->down[0]);
264 int right = get_height (node->down[1]);
265 return 1 + (left > right ? left : right);
266 }
267 }
268
269 /* Checks that BT is loosely alpha-height balanced, that is, that
270 its height is no more than h_alpha(count) + 1, where
271 h_alpha(n) = floor(log(n)/log(1/alpha)). */
272 static void
check_balance(struct bt * bt)273 check_balance (struct bt *bt)
274 {
275 /* In the notation of the Galperin and Rivest paper (and of
276 CLR), the height of a tree is the number of edges in the
277 longest path from the root to a leaf, so we have to subtract
278 1 from our measured height. */
279 int height = get_height (bt->root) - 1;
280 int max_height = calculate_h_alpha (bt_count (bt)) + 1;
281 check (height <= max_height);
282 }
283
284 /* Checks that BT contains the CNT ints in DATA, that its
285 structure is correct, and that certain operations on BT
286 produce the expected results. */
287 static void
check_bt(struct bt * bt,const int data[],size_t cnt)288 check_bt (struct bt *bt, const int data[], size_t cnt)
289 {
290 struct element e;
291 size_t i;
292 int *order;
293
294 order = xmemdup (data, cnt * sizeof *data);
295 qsort (order, cnt, sizeof *order, compare_ints_noaux);
296
297 for (i = 0; i < cnt; i++)
298 {
299 struct bt_node *p;
300
301 e.data = data[i];
302 if (rand () % 2)
303 p = bt_find (bt, &e.node);
304 else
305 p = bt_insert (bt, &e.node);
306 check (p != NULL);
307 check (p != &e.node);
308 check (bt_node_to_element (p)->data == data[i]);
309 }
310
311 e.data = -1;
312 check (bt_find (bt, &e.node) == NULL);
313
314 check_balance (bt);
315
316 if (cnt == 0)
317 {
318 check (bt_first (bt) == NULL);
319 check (bt_last (bt) == NULL);
320 check (bt_next (bt, NULL) == NULL);
321 check (bt_prev (bt, NULL) == NULL);
322 }
323 else
324 {
325 struct bt_node *p;
326
327 for (p = bt_first (bt), i = 0; i < cnt; p = bt_next (bt, p), i++)
328 check (bt_node_to_element (p)->data == order[i]);
329 check (p == NULL);
330
331 for (p = bt_last (bt), i = 0; i < cnt; p = bt_prev (bt, p), i++)
332 check (bt_node_to_element (p)->data == order[cnt - i - 1]);
333 check (p == NULL);
334 }
335
336 free (order);
337 }
338
339 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
340 BT in the order specified by INSERTIONS, then deletes them in
341 the order specified by DELETIONS, checking the BT's contents
342 for correctness after each operation. */
343 static void
test_insert_delete(const int insertions[],const int deletions[],size_t cnt)344 test_insert_delete (const int insertions[],
345 const int deletions[],
346 size_t cnt)
347 {
348 struct element *elements;
349 struct bt bt;
350 size_t i;
351
352 elements = xnmalloc (cnt, sizeof *elements);
353 for (i = 0; i < cnt; i++)
354 elements[i].data = i;
355
356 bt_init (&bt, compare_elements, &aux_data);
357 check_bt (&bt, NULL, 0);
358 for (i = 0; i < cnt; i++)
359 {
360 check (bt_insert (&bt, &elements[insertions[i]].node) == NULL);
361 check_bt (&bt, insertions, i + 1);
362 }
363 for (i = 0; i < cnt; i++)
364 {
365 bt_delete (&bt, &elements[deletions[i]].node);
366 check_bt (&bt, deletions + i + 1, cnt - i - 1);
367 }
368
369 free (elements);
370 }
371
372 /* Inserts values into an BT in each possible order, then
373 removes them in each possible order, up to a specified maximum
374 size. */
375 static void
test_insert_any_remove_any(void)376 test_insert_any_remove_any (void)
377 {
378 const int max_elems = 5;
379 int cnt;
380
381 for (cnt = 0; cnt <= max_elems; cnt++)
382 {
383 int *insertions, *deletions;
384 unsigned int ins_perm_cnt;
385 int i;
386
387 insertions = xnmalloc (cnt, sizeof *insertions);
388 deletions = xnmalloc (cnt, sizeof *deletions);
389 for (i = 0; i < cnt; i++)
390 insertions[i] = i;
391
392 for (ins_perm_cnt = 0;
393 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
394 ins_perm_cnt++)
395 {
396 unsigned int del_perm_cnt;
397 int i;
398
399 for (i = 0; i < cnt; i++)
400 deletions[i] = i;
401
402 for (del_perm_cnt = 0;
403 del_perm_cnt == 0 || next_permutation (deletions, cnt);
404 del_perm_cnt++)
405 test_insert_delete (insertions, deletions, cnt);
406
407 check (del_perm_cnt == factorial (cnt));
408 }
409 check (ins_perm_cnt == factorial (cnt));
410
411 free (insertions);
412 free (deletions);
413 }
414 }
415
416 /* Inserts values into an BT in each possible order, then
417 removes them in the same order, up to a specified maximum
418 size. */
419 static void
test_insert_any_remove_same(void)420 test_insert_any_remove_same (void)
421 {
422 const int max_elems = 7;
423 int cnt;
424
425 for (cnt = 0; cnt <= max_elems; cnt++)
426 {
427 int *values;
428 unsigned int permutation_cnt;
429 int i;
430
431 values = xnmalloc (cnt, sizeof *values);
432 for (i = 0; i < cnt; i++)
433 values[i] = i;
434
435 for (permutation_cnt = 0;
436 permutation_cnt == 0 || next_permutation (values, cnt);
437 permutation_cnt++)
438 test_insert_delete (values, values, cnt);
439 check (permutation_cnt == factorial (cnt));
440
441 free (values);
442 }
443 }
444
445 /* Inserts values into an BT in each possible order, then
446 removes them in reverse order, up to a specified maximum
447 size. */
448 static void
test_insert_any_remove_reverse(void)449 test_insert_any_remove_reverse (void)
450 {
451 const int max_elems = 7;
452 int cnt;
453
454 for (cnt = 0; cnt <= max_elems; cnt++)
455 {
456 int *insertions, *deletions;
457 unsigned int permutation_cnt;
458 int i;
459
460 insertions = xnmalloc (cnt, sizeof *insertions);
461 deletions = xnmalloc (cnt, sizeof *deletions);
462 for (i = 0; i < cnt; i++)
463 insertions[i] = i;
464
465 for (permutation_cnt = 0;
466 permutation_cnt == 0 || next_permutation (insertions, cnt);
467 permutation_cnt++)
468 {
469 memcpy (deletions, insertions, sizeof *insertions * cnt);
470 reverse (deletions, cnt);
471
472 test_insert_delete (insertions, deletions, cnt);
473 }
474 check (permutation_cnt == factorial (cnt));
475
476 free (insertions);
477 free (deletions);
478 }
479 }
480
481 /* Inserts and removes values in an BT in random orders. */
482 static void
test_random_sequence(void)483 test_random_sequence (void)
484 {
485 const int max_elems = 128;
486 const int max_trials = 8;
487 int cnt;
488
489 for (cnt = 0; cnt <= max_elems; cnt += 2)
490 {
491 int *insertions, *deletions;
492 int trial;
493 int i;
494
495 insertions = xnmalloc (cnt, sizeof *insertions);
496 deletions = xnmalloc (cnt, sizeof *deletions);
497 for (i = 0; i < cnt; i++)
498 insertions[i] = i;
499 for (i = 0; i < cnt; i++)
500 deletions[i] = i;
501
502 for (trial = 0; trial < max_trials; trial++)
503 {
504 random_shuffle (insertions, cnt, sizeof *insertions);
505 random_shuffle (deletions, cnt, sizeof *deletions);
506
507 test_insert_delete (insertions, deletions, cnt);
508 }
509
510 free (insertions);
511 free (deletions);
512 }
513 }
514
515 /* Inserts elements into an BT in ascending order. */
516 static void
test_insert_ordered(void)517 test_insert_ordered (void)
518 {
519 const int max_elems = 1024;
520 struct element *elements;
521 int *values;
522 struct bt bt;
523 int i;
524
525 bt_init (&bt, compare_elements, &aux_data);
526 elements = xnmalloc (max_elems, sizeof *elements);
527 values = xnmalloc (max_elems, sizeof *values);
528 for (i = 0; i < max_elems; i++)
529 {
530 values[i] = elements[i].data = i;
531 check (bt_insert (&bt, &elements[i].node) == NULL);
532 check_bt (&bt, values, i + 1);
533 }
534 free (elements);
535 free (values);
536 }
537
538 /* Tests bt_find_ge and bt_find_le. */
539 static void
test_find_ge_le(void)540 test_find_ge_le (void)
541 {
542 const int max_elems = 10;
543 struct element *elements;
544 int *values;
545 unsigned int inc_pat;
546
547 elements = xnmalloc (max_elems, sizeof *elements);
548 values = xnmalloc (max_elems, sizeof *values);
549 for (inc_pat = 0; inc_pat < (1u << max_elems); inc_pat++)
550 {
551 struct bt bt;
552 int elem_cnt = 0;
553 int i;
554
555 /* Insert the values in the pattern into BT. */
556 bt_init (&bt, compare_elements, &aux_data);
557 for (i = 0; i < max_elems; i++)
558 if (inc_pat & (1u << i))
559 {
560 values[elem_cnt] = elements[elem_cnt].data = i;
561 check (bt_insert (&bt, &elements[elem_cnt].node) == NULL);
562 elem_cnt++;
563 }
564 check_bt (&bt, values, elem_cnt);
565
566 /* Try find_ge and find_le for each possible element value. */
567 for (i = -1; i <= max_elems; i++)
568 {
569 struct element tmp;
570 struct bt_node *ge, *le;
571 int j;
572
573 ge = le = NULL;
574 for (j = 0; j < elem_cnt; j++)
575 {
576 if (ge == NULL && values[j] >= i)
577 ge = &elements[j].node;
578 if (values[j] <= i)
579 le = &elements[j].node;
580 }
581
582 tmp.data = i;
583 check (bt_find_ge (&bt, &tmp.node) == ge);
584 check (bt_find_le (&bt, &tmp.node) == le);
585 }
586 }
587 free (elements);
588 free (values);
589 }
590
591 /* Inserts elements into an BT, then moves the nodes around in
592 memory. */
593 static void
test_moved(void)594 test_moved (void)
595 {
596 const int max_elems = 128;
597 struct element *e[2];
598 int cur;
599 int *values;
600 struct bt bt;
601 int i, j;
602
603 bt_init (&bt, compare_elements, &aux_data);
604 e[0] = xnmalloc (max_elems, sizeof *e[0]);
605 e[1] = xnmalloc (max_elems, sizeof *e[1]);
606 values = xnmalloc (max_elems, sizeof *values);
607 cur = 0;
608 for (i = 0; i < max_elems; i++)
609 {
610 values[i] = e[cur][i].data = i;
611 check (bt_insert (&bt, &e[cur][i].node) == NULL);
612 check_bt (&bt, values, i + 1);
613
614 for (j = 0; j <= i; j++)
615 {
616 e[!cur][j] = e[cur][j];
617 bt_moved (&bt, &e[!cur][j].node);
618 check_bt (&bt, values, i + 1);
619 }
620 cur = !cur;
621 }
622 free (e[0]);
623 free (e[1]);
624 free (values);
625 }
626
627 /* Inserts values into an BT, then changes their values. */
628 static void
test_changed(void)629 test_changed (void)
630 {
631 const int max_elems = 6;
632 int cnt;
633
634 for (cnt = 0; cnt <= max_elems; cnt++)
635 {
636 int *values, *changed_values;
637 struct element *elements;
638 unsigned int permutation_cnt;
639 int i;
640
641 values = xnmalloc (cnt, sizeof *values);
642 changed_values = xnmalloc (cnt, sizeof *changed_values);
643 elements = xnmalloc (cnt, sizeof *elements);
644 for (i = 0; i < cnt; i++)
645 values[i] = i;
646
647 for (permutation_cnt = 0;
648 permutation_cnt == 0 || next_permutation (values, cnt);
649 permutation_cnt++)
650 {
651 for (i = 0; i < cnt; i++)
652 {
653 int j, k;
654 for (j = 0; j <= cnt; j++)
655 {
656 struct bt bt;
657 struct bt_node *changed_retval;
658
659 bt_init (&bt, compare_elements, &aux_data);
660
661 /* Add to BT in order. */
662 for (k = 0; k < cnt; k++)
663 {
664 int n = values[k];
665 elements[n].data = n;
666 check (bt_insert (&bt, &elements[n].node) == NULL);
667 }
668 check_bt (&bt, values, cnt);
669
670 /* Change value i to j. */
671 elements[i].data = j;
672 for (k = 0; k < cnt; k++)
673 changed_values[k] = k;
674 changed_retval = bt_changed (&bt, &elements[i].node);
675 if (i != j && j < cnt)
676 {
677 /* Will cause duplicate. */
678 check (changed_retval == &elements[j].node);
679 changed_values[i] = changed_values[cnt - 1];
680 check_bt (&bt, changed_values, cnt - 1);
681 }
682 else
683 {
684 /* Succeeds. */
685 check (changed_retval == NULL);
686 changed_values[i] = j;
687 check_bt (&bt, changed_values, cnt);
688 }
689 }
690 }
691 }
692 check (permutation_cnt == factorial (cnt));
693
694 free (values);
695 free (changed_values);
696 free (elements);
697 }
698 }
699
700 /* Main program. */
701
702 struct test
703 {
704 const char *name;
705 const char *description;
706 void (*function) (void);
707 };
708
709 static const struct test tests[] =
710 {
711 {
712 "insert-any-remove-any",
713 "insert any order, delete any order",
714 test_insert_any_remove_any
715 },
716 {
717 "insert-any-remove-same",
718 "insert any order, delete same order",
719 test_insert_any_remove_same
720 },
721 {
722 "insert-any-remove-reverse",
723 "insert any order, delete reverse order",
724 test_insert_any_remove_reverse
725 },
726 {
727 "random-sequence",
728 "insert and delete in random sequence",
729 test_random_sequence
730 },
731 {
732 "insert-ordered",
733 "insert in ascending order",
734 test_insert_ordered
735 },
736 {
737 "find-ge-le",
738 "find_ge and find_le",
739 test_find_ge_le
740 },
741 {
742 "moved",
743 "move elements around in memory",
744 test_moved
745 },
746 {
747 "changed",
748 "change key data in nodes",
749 test_changed
750 }
751 };
752
753 enum { N_TESTS = sizeof tests / sizeof *tests };
754
755 int
main(int argc,char * argv[])756 main (int argc, char *argv[])
757 {
758 int i;
759
760 if (argc != 2)
761 {
762 fprintf (stderr, "exactly one argument required; use --help for help\n");
763 return EXIT_FAILURE;
764 }
765 else if (!strcmp (argv[1], "--help"))
766 {
767 printf ("%s: test balanced tree\n"
768 "usage: %s TEST-NAME\n"
769 "where TEST-NAME is one of the following:\n",
770 argv[0], argv[0]);
771 for (i = 0; i < N_TESTS; i++)
772 printf (" %s\n %s\n", tests[i].name, tests[i].description);
773 return 0;
774 }
775 else
776 {
777 for (i = 0; i < N_TESTS; i++)
778 if (!strcmp (argv[1], tests[i].name))
779 {
780 tests[i].function ();
781 return 0;
782 }
783
784 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
785 return EXIT_FAILURE;
786 }
787 }
788