Added a dict parameter to data_in and dealt with the consequences.
[pspp-builds.git] / tests / libpspp / bt-test.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007 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 /* Currently running test. */
40 static const char *test_name;
41
42 /* Exit with a failure code.
43    (Place a breakpoint on this function while debugging.) */
44 static void
45 check_die (void)
46 {
47   exit (EXIT_FAILURE);
48 }
49
50 /* If OK is not true, prints a message about failure on the
51    current source file and the given LINE and terminates. */
52 static void
53 check_func (bool ok, int line)
54 {
55   if (!ok)
56     {
57       printf ("Check failed in %s test at %s, line %d\n",
58               test_name, __FILE__, line);
59       check_die ();
60     }
61 }
62
63 /* Verifies that EXPR evaluates to true.
64    If not, prints a message citing the calling line number and
65    terminates. */
66 #define check(EXPR) check_func ((EXPR), __LINE__)
67
68 /* Prints a message about memory exhaustion and exits with a
69    failure code. */
70 static void
71 xalloc_die (void)
72 {
73   printf ("virtual memory exhausted\n");
74   exit (EXIT_FAILURE);
75 }
76
77 /* Allocates and returns N bytes of memory. */
78 static void *
79 xmalloc (size_t n)
80 {
81   if (n != 0)
82     {
83       void *p = malloc (n);
84       if (p == NULL)
85         xalloc_die ();
86
87       return p;
88     }
89   else
90     return NULL;
91 }
92
93 static void *
94 xmemdup (const void *p, size_t n)
95 {
96   void *q = xmalloc (n);
97   memcpy (q, p, n);
98   return q;
99 }
100
101 /* Allocates and returns N * M bytes of memory. */
102 static void *
103 xnmalloc (size_t n, size_t m)
104 {
105   if ((size_t) -1 / m <= n)
106     xalloc_die ();
107   return xmalloc (n * m);
108 }
109 \f
110 /* Node type and support routines. */
111
112 /* Test data element. */
113 struct element
114   {
115     struct bt_node node;        /* Embedded binary tree element. */
116     int data;                   /* Primary value. */
117   };
118
119 static int aux_data;
120
121 /* Returns the `struct element' that NODE is embedded within. */
122 static struct element *
123 bt_node_to_element (const struct bt_node *node)
124 {
125   return bt_data (node, struct element, node);
126 }
127
128 /* Compares the `x' values in A and B and returns a strcmp-type
129    return value.  Verifies that AUX points to aux_data. */
130 static int
131 compare_elements (const struct bt_node *a_, const struct bt_node *b_,
132                   const void *aux)
133 {
134   const struct element *a = bt_node_to_element (a_);
135   const struct element *b = bt_node_to_element (b_);
136
137   check (aux == &aux_data);
138   return a->data < b->data ? -1 : a->data > b->data;
139 }
140
141 /* Compares A and B and returns a strcmp-type return value. */
142 static int
143 compare_ints_noaux (const void *a_, const void *b_)
144 {
145   const int *a = a_;
146   const int *b = b_;
147
148   return *a < *b ? -1 : *a > *b;
149 }
150
151 /* Swaps *A and *B. */
152 static void
153 swap (int *a, int *b)
154 {
155   int t = *a;
156   *a = *b;
157   *b = t;
158 }
159
160 /* Reverses the order of the CNT integers starting at VALUES. */
161 static void
162 reverse (int *values, size_t cnt)
163 {
164   size_t i = 0;
165   size_t j = cnt;
166
167   while (j > i)
168     swap (&values[i++], &values[--j]);
169 }
170
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
177    returns false. */
178 static bool
179 next_permutation (int *values, size_t cnt)
180 {
181   if (cnt > 0)
182     {
183       size_t i = cnt - 1;
184       while (i != 0)
185         {
186           i--;
187           if (values[i] < values[i + 1])
188             {
189               size_t j;
190               for (j = cnt - 1; values[i] >= values[j]; j--)
191                 continue;
192               swap (values + i, values + j);
193               reverse (values + (i + 1), cnt - (i + 1));
194               return true;
195             }
196         }
197
198       reverse (values, cnt);
199     }
200
201   return false;
202 }
203
204 /* Returns N!. */
205 static unsigned int
206 factorial (unsigned int n)
207 {
208   unsigned int value = 1;
209   while (n > 1)
210     value *= n--;
211   return value;
212 }
213
214 /* Randomly shuffles the CNT elements in ARRAY, each of which is
215    SIZE bytes in size. */
216 static void
217 random_shuffle (void *array_, size_t cnt, size_t size)
218 {
219   char *array = array_;
220   char *tmp = xmalloc (size);
221   size_t i;
222
223   for (i = 0; i < cnt; i++)
224     {
225       size_t j = rand () % (cnt - i) + i;
226       if (i != j)
227         {
228           memcpy (tmp, array + j * size, size);
229           memcpy (array + j * size, array + i * size, size);
230           memcpy (array + i * size, tmp, size);
231         }
232     }
233
234   free (tmp);
235 }
236
237 /* Calculates floor(log(n)/log(sqrt(2))). */
238 static int
239 calculate_h_alpha (size_t n)
240 {
241   size_t thresholds[] =
242     {
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,
250     };
251   size_t threshold_cnt = sizeof thresholds / sizeof *thresholds;
252   size_t i;
253
254   for (i = 0; i < threshold_cnt; i++)
255     if (thresholds[i] > n)
256       break;
257   return i - 1;
258 }
259
260 /* Returns the height of the tree rooted at NODE. */
261 static int
262 get_height (struct bt_node *node)
263 {
264   if (node == NULL)
265     return 0;
266   else
267     {
268       int left = get_height (node->down[0]);
269       int right = get_height (node->down[1]);
270       return 1 + (left > right ? left : right);
271     }
272 }
273
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)). */
277 static void
278 check_balance (struct bt *bt)
279 {
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);
287 }
288
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. */
292 static void
293 check_bt (struct bt *bt, const int data[], size_t cnt)
294 {
295   struct element e;
296   size_t i;
297   int *order;
298
299   order = xmemdup (data, cnt * sizeof *data);
300   qsort (order, cnt, sizeof *order, compare_ints_noaux);
301
302   for (i = 0; i < cnt; i++)
303     {
304       struct bt_node *p;
305
306       e.data = data[i];
307       if (rand () % 2)
308         p = bt_find (bt, &e.node);
309       else
310         p = bt_insert (bt, &e.node);
311       check (p != NULL);
312       check (p != &e.node);
313       check (bt_node_to_element (p)->data == data[i]);
314     }
315
316   e.data = -1;
317   check (bt_find (bt, &e.node) == NULL);
318
319   check_balance (bt);
320
321   if (cnt == 0)
322     {
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);
327     }
328   else
329     {
330       struct bt_node *p;
331
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]);
334       check (p == NULL);
335
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]);
338       check (p == NULL);
339     }
340
341   free (order);
342 }
343
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. */
348 static void
349 test_insert_delete (const int insertions[],
350                     const int deletions[],
351                     size_t cnt)
352 {
353   struct element *elements;
354   struct bt bt;
355   size_t i;
356
357   elements = xnmalloc (cnt, sizeof *elements);
358   for (i = 0; i < cnt; i++)
359     elements[i].data = i;
360
361   bt_init (&bt, compare_elements, &aux_data);
362   check_bt (&bt, NULL, 0);
363   for (i = 0; i < cnt; i++)
364     {
365       check (bt_insert (&bt, &elements[insertions[i]].node) == NULL);
366       check_bt (&bt, insertions, i + 1);
367     }
368   for (i = 0; i < cnt; i++)
369     {
370       bt_delete (&bt, &elements[deletions[i]].node);
371       check_bt (&bt, deletions + i + 1, cnt - i - 1);
372     }
373
374   free (elements);
375 }
376 \f
377 /* Inserts values into an BT in each possible order, then
378    removes them in each possible order, up to a specified maximum
379    size. */
380 static void
381 test_insert_any_remove_any (void)
382 {
383   const int max_elems = 5;
384   int cnt;
385
386   for (cnt = 0; cnt <= max_elems; cnt++)
387     {
388       int *insertions, *deletions;
389       unsigned int ins_perm_cnt;
390       int i;
391
392       insertions = xnmalloc (cnt, sizeof *insertions);
393       deletions = xnmalloc (cnt, sizeof *deletions);
394       for (i = 0; i < cnt; i++)
395         insertions[i] = i;
396
397       for (ins_perm_cnt = 0;
398            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
399            ins_perm_cnt++)
400         {
401           unsigned int del_perm_cnt;
402           int i;
403
404           for (i = 0; i < cnt; i++)
405             deletions[i] = i;
406
407           for (del_perm_cnt = 0;
408                del_perm_cnt == 0 || next_permutation (deletions, cnt);
409                del_perm_cnt++)
410             test_insert_delete (insertions, deletions, cnt);
411
412           check (del_perm_cnt == factorial (cnt));
413         }
414       check (ins_perm_cnt == factorial (cnt));
415
416       free (insertions);
417       free (deletions);
418     }
419 }
420
421 /* Inserts values into an BT in each possible order, then
422    removes them in the same order, up to a specified maximum
423    size. */
424 static void
425 test_insert_any_remove_same (void)
426 {
427   const int max_elems = 7;
428   int cnt;
429
430   for (cnt = 0; cnt <= max_elems; cnt++)
431     {
432       int *values;
433       unsigned int permutation_cnt;
434       int i;
435
436       values = xnmalloc (cnt, sizeof *values);
437       for (i = 0; i < cnt; i++)
438         values[i] = i;
439
440       for (permutation_cnt = 0;
441            permutation_cnt == 0 || next_permutation (values, cnt);
442            permutation_cnt++)
443         test_insert_delete (values, values, cnt);
444       check (permutation_cnt == factorial (cnt));
445
446       free (values);
447     }
448 }
449
450 /* Inserts values into an BT in each possible order, then
451    removes them in reverse order, up to a specified maximum
452    size. */
453 static void
454 test_insert_any_remove_reverse (void)
455 {
456   const int max_elems = 7;
457   int cnt;
458
459   for (cnt = 0; cnt <= max_elems; cnt++)
460     {
461       int *insertions, *deletions;
462       unsigned int permutation_cnt;
463       int i;
464
465       insertions = xnmalloc (cnt, sizeof *insertions);
466       deletions = xnmalloc (cnt, sizeof *deletions);
467       for (i = 0; i < cnt; i++)
468         insertions[i] = i;
469
470       for (permutation_cnt = 0;
471            permutation_cnt == 0 || next_permutation (insertions, cnt);
472            permutation_cnt++)
473         {
474           memcpy (deletions, insertions, sizeof *insertions * cnt);
475           reverse (deletions, cnt);
476
477           test_insert_delete (insertions, deletions, cnt);
478         }
479       check (permutation_cnt == factorial (cnt));
480
481       free (insertions);
482       free (deletions);
483     }
484 }
485
486 /* Inserts and removes values in an BT in random orders. */
487 static void
488 test_random_sequence (void)
489 {
490   const int max_elems = 128;
491   const int max_trials = 8;
492   int cnt;
493
494   for (cnt = 0; cnt <= max_elems; cnt += 2)
495     {
496       int *insertions, *deletions;
497       int trial;
498       int i;
499
500       insertions = xnmalloc (cnt, sizeof *insertions);
501       deletions = xnmalloc (cnt, sizeof *deletions);
502       for (i = 0; i < cnt; i++)
503         insertions[i] = i;
504       for (i = 0; i < cnt; i++)
505         deletions[i] = i;
506
507       for (trial = 0; trial < max_trials; trial++)
508         {
509           random_shuffle (insertions, cnt, sizeof *insertions);
510           random_shuffle (deletions, cnt, sizeof *deletions);
511
512           test_insert_delete (insertions, deletions, cnt);
513         }
514
515       free (insertions);
516       free (deletions);
517     }
518 }
519
520 /* Inserts elements into an BT in ascending order. */
521 static void
522 test_insert_ordered (void)
523 {
524   const int max_elems = 1024;
525   struct element *elements;
526   int *values;
527   struct bt bt;
528   int i;
529
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++)
534     {
535       values[i] = elements[i].data = i;
536       check (bt_insert (&bt, &elements[i].node) == NULL);
537       check_bt (&bt, values, i + 1);
538     }
539   free (elements);
540   free (values);
541 }
542
543 /* Tests bt_find_ge and bt_find_le. */
544 static void
545 test_find_ge_le (void)
546 {
547   const int max_elems = 10;
548   struct element *elements;
549   int *values;
550   unsigned int inc_pat;
551
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++)
555     {
556       struct bt bt;
557       int elem_cnt = 0;
558       int i;
559
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))
564           {
565             values[elem_cnt] = elements[elem_cnt].data = i;
566             check (bt_insert (&bt, &elements[elem_cnt].node) == NULL);
567             elem_cnt++;
568           }
569       check_bt (&bt, values, elem_cnt);
570
571       /* Try find_ge and find_le for each possible element value. */
572       for (i = -1; i <= max_elems; i++)
573         {
574           struct element tmp;
575           struct bt_node *ge, *le;
576           int j;
577
578           ge = le = NULL;
579           for (j = 0; j < elem_cnt; j++)
580             {
581               if (ge == NULL && values[j] >= i)
582                 ge = &elements[j].node;
583               if (values[j] <= i)
584                 le = &elements[j].node;
585             }
586
587           tmp.data = i;
588           check (bt_find_ge (&bt, &tmp.node) == ge);
589           check (bt_find_le (&bt, &tmp.node) == le);
590         }
591     }
592   free (elements);
593   free (values);
594 }
595
596 /* Inserts elements into an BT, then moves the nodes around in
597    memory. */
598 static void
599 test_moved (void)
600 {
601   const int max_elems = 128;
602   struct element *e[2];
603   int cur;
604   int *values;
605   struct bt bt;
606   int i, j;
607
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);
612   cur = 0;
613   for (i = 0; i < max_elems; i++)
614     {
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);
618
619       for (j = 0; j <= i; j++)
620         {
621           e[!cur][j] = e[cur][j];
622           bt_moved (&bt, &e[!cur][j].node);
623           check_bt (&bt, values, i + 1);
624         }
625       cur = !cur;
626     }
627   free (e[0]);
628   free (e[1]);
629   free (values);
630 }
631
632 /* Inserts values into an BT, then changes their values. */
633 static void
634 test_changed (void)
635 {
636   const int max_elems = 6;
637   int cnt;
638
639   for (cnt = 0; cnt <= max_elems; cnt++)
640     {
641       int *values, *changed_values;
642       struct element *elements;
643       unsigned int permutation_cnt;
644       int i;
645
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++)
650         values[i] = i;
651
652       for (permutation_cnt = 0;
653            permutation_cnt == 0 || next_permutation (values, cnt);
654            permutation_cnt++)
655         {
656           for (i = 0; i < cnt; i++)
657             {
658               int j, k;
659               for (j = 0; j <= cnt; j++)
660                 {
661                   struct bt bt;
662                   struct bt_node *changed_retval;
663
664                   bt_init (&bt, compare_elements, &aux_data);
665
666                   /* Add to BT in order. */
667                   for (k = 0; k < cnt; k++)
668                     {
669                       int n = values[k];
670                       elements[n].data = n;
671                       check (bt_insert (&bt, &elements[n].node) == NULL);
672                     }
673                   check_bt (&bt, values, cnt);
674
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)
681                     {
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);
686                     }
687                   else
688                     {
689                       /* Succeeds. */
690                       check (changed_retval == NULL);
691                       changed_values[i] = j;
692                       check_bt (&bt, changed_values, cnt);
693                     }
694                 }
695             }
696         }
697       check (permutation_cnt == factorial (cnt));
698
699       free (values);
700       free (changed_values);
701       free (elements);
702     }
703 }
704 \f
705 /* Main program. */
706
707 /* Runs TEST_FUNCTION and prints a message about NAME. */
708 static void
709 run_test (void (*test_function) (void), const char *name)
710 {
711   test_name = name;
712   putchar ('.');
713   fflush (stdout);
714   test_function ();
715 }
716
717 int
718 main (void)
719 {
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");
733   putchar ('\n');
734
735   return 0;
736 }