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