src/data/format.c (fmt_affix_free): Fix memory leak
[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 <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 \f
38 /* Exit with a failure code.
39    (Place a breakpoint on this function while debugging.) */
40 static 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
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
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 *
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 *
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 *
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 \f
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 *
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
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
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
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
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
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
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
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
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
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
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
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
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 \f
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
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
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
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
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
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
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
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
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 \f
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
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 }