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