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