LOOP: Convert tests to Autotest framework.
[pspp] / tests / libpspp / abt-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 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 /* 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 abt_node node;       /* Embedded binary tree element. */
111     int data;                   /* Primary value. */
112     int count;                  /* Number of nodes in subtree,
113                                    including this node. */
114   };
115
116 static int aux_data;
117
118 /* Returns the `struct element' that NODE is embedded within. */
119 static struct element *
120 abt_node_to_element (const struct abt_node *node)
121 {
122   return abt_data (node, struct element, node);
123 }
124
125 /* Compares the `x' values in A and B and returns a strcmp-type
126    return value.  Verifies that AUX points to aux_data. */
127 static int
128 compare_elements (const struct abt_node *a_, const struct abt_node *b_,
129                   const void *aux)
130 {
131   const struct element *a = abt_node_to_element (a_);
132   const struct element *b = abt_node_to_element (b_);
133
134   check (aux == &aux_data);
135   return a->data < b->data ? -1 : a->data > b->data;
136 }
137
138 /* Recalculates the count for NODE's subtree by adding up the
139    counts for its LEFT and RIGHT child subtrees. */
140 static void
141 reaugment_elements (struct abt_node *node_,
142                     const struct abt_node *left,
143                     const struct abt_node *right,
144                     const void *aux)
145 {
146   struct element *node = abt_node_to_element (node_);
147
148   check (aux == &aux_data);
149
150   node->count = 1;
151   if (left != NULL)
152     node->count += abt_node_to_element (left)->count;
153   if (right != NULL)
154     node->count += abt_node_to_element (right)->count;
155 }
156
157 /* Compares A and B and returns a strcmp-type return value. */
158 static int
159 compare_ints_noaux (const void *a_, const void *b_)
160 {
161   const int *a = a_;
162   const int *b = b_;
163
164   return *a < *b ? -1 : *a > *b;
165 }
166
167 /* Swaps *A and *B. */
168 static void
169 swap (int *a, int *b)
170 {
171   int t = *a;
172   *a = *b;
173   *b = t;
174 }
175
176 /* Reverses the order of the CNT integers starting at VALUES. */
177 static void
178 reverse (int *values, size_t cnt)
179 {
180   size_t i = 0;
181   size_t j = cnt;
182
183   while (j > i)
184     swap (&values[i++], &values[--j]);
185 }
186
187 /* Arranges the CNT elements in VALUES into the lexicographically
188    next greater permutation.  Returns true if successful.
189    If VALUES is already the lexicographically greatest
190    permutation of its elements (i.e. ordered from greatest to
191    smallest), arranges them into the lexicographically least
192    permutation (i.e. ordered from smallest to largest) and
193    returns false. */
194 static bool
195 next_permutation (int *values, size_t cnt)
196 {
197   if (cnt > 0)
198     {
199       size_t i = cnt - 1;
200       while (i != 0)
201         {
202           i--;
203           if (values[i] < values[i + 1])
204             {
205               size_t j;
206               for (j = cnt - 1; values[i] >= values[j]; j--)
207                 continue;
208               swap (values + i, values + j);
209               reverse (values + (i + 1), cnt - (i + 1));
210               return true;
211             }
212         }
213
214       reverse (values, cnt);
215     }
216
217   return false;
218 }
219
220 /* Returns N!. */
221 static unsigned int
222 factorial (unsigned int n)
223 {
224   unsigned int value = 1;
225   while (n > 1)
226     value *= n--;
227   return value;
228 }
229
230 /* Randomly shuffles the CNT elements in ARRAY, each of which is
231    SIZE bytes in size. */
232 static void
233 random_shuffle (void *array_, size_t cnt, size_t size)
234 {
235   char *array = array_;
236   char *tmp = xmalloc (size);
237   size_t i;
238
239   for (i = 0; i < cnt; i++)
240     {
241       size_t j = rand () % (cnt - i) + i;
242       if (i != j)
243         {
244           memcpy (tmp, array + j * size, size);
245           memcpy (array + j * size, array + i * size, size);
246           memcpy (array + i * size, tmp, size);
247         }
248     }
249
250   free (tmp);
251 }
252
253 /* Finds and returns the element in ABT that is in the given
254    0-based POSITION in in-order. */
255 static struct element *
256 find_by_position (struct abt *abt, int position)
257 {
258   struct abt_node *p;
259   for (p = abt->root; p != NULL; )
260     {
261       int p_pos = p->down[0] ? abt_node_to_element (p->down[0])->count : 0;
262       if (position == p_pos)
263         return abt_node_to_element (p);
264       else if (position < p_pos)
265         p = p->down[0];
266       else
267         {
268           p = p->down[1];
269           position -= p_pos + 1;
270         }
271     }
272   return NULL;
273 }
274
275 /* Checks that all the augmentations are correct in the subtree
276    rooted at P.  Returns the number of nodes in the subtree. */
277 static int
278 check_augmentations (struct abt_node *p_)
279 {
280   if (p_ == NULL)
281     return 0;
282   else
283     {
284       struct element *p = abt_node_to_element (p_);
285       int left_count = check_augmentations (p->node.down[0]);
286       int right_count = check_augmentations (p->node.down[1]);
287       int total = left_count + right_count + 1;
288       check (p->count == total);
289       return total;
290     }
291 }
292
293 /* Check that the levels are correct in the subtree rooted at P. */
294 static void
295 check_levels (struct abt_node *p)
296 {
297   if (p != NULL)
298     {
299       int i, j;
300
301       check_levels (p->down[0]);
302       check_levels (p->down[1]);
303
304       check (p->level >= 1);
305       if (p->level > 1)
306         {
307           struct abt_node *q = p->down[1];
308           check (q != NULL);
309           check (q->level == p->level || q->level == p->level - 1);
310         }
311
312       for (i = 0; i < 2; i++)
313         if (p->down[i] != NULL)
314           for (j = 0; j < 2; j++)
315             if (p->down[i]->down[j] != NULL)
316               check (p->down[i]->down[j]->level < p->level);
317     }
318 }
319
320 /* Checks that ABT contains the CNT ints in DATA, that its
321    structure is correct, and that certain operations on ABT
322    produce the expected results. */
323 static void
324 check_abt (struct abt *abt, const int data[], size_t cnt)
325 {
326   struct element e;
327   size_t i;
328   int *order;
329
330   order = xmemdup (data, cnt * sizeof *data);
331   qsort (order, cnt, sizeof *order, compare_ints_noaux);
332
333   if (abt->compare != NULL)
334     {
335       for (i = 0; i < cnt; i++)
336         {
337           struct abt_node *p;
338
339           e.data = data[i];
340           if (rand () % 2)
341             p = abt_find (abt, &e.node);
342           else
343             p = abt_insert (abt, &e.node);
344           check (p != NULL);
345           check (p != &e.node);
346           check (abt_node_to_element (p)->data == data[i]);
347         }
348
349       e.data = -1;
350       check (abt_find (abt, &e.node) == NULL);
351     }
352
353   check_levels (abt->root);
354   check_augmentations (abt->root);
355   for (i = 0; i < cnt; i++)
356     check (find_by_position (abt, i)->data == order[i]);
357
358   if (cnt == 0)
359     {
360       check (abt_first (abt) == NULL);
361       check (abt_last (abt) == NULL);
362       check (abt_next (abt, NULL) == NULL);
363       check (abt_prev (abt, NULL) == NULL);
364     }
365   else
366     {
367       struct abt_node *p;
368
369       for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
370         check (abt_node_to_element (p)->data == order[i]);
371       check (p == NULL);
372
373       for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
374         check (abt_node_to_element (p)->data == order[cnt - i - 1]);
375       check (p == NULL);
376     }
377
378   free (order);
379 }
380
381 /* Ways that nodes can be inserted. */
382 enum insertion_method
383   {
384     INSERT,             /* With abt_insert. */
385     INSERT_AFTER,       /* With abt_insert_after. */
386     INSERT_BEFORE       /* With abt_insert_before. */
387   };
388
389 /* Inserts INSERT into ABT with the given METHOD. */
390 static void
391 insert_node (struct abt *abt, struct element *insert,
392              enum insertion_method method)
393 {
394   if (method == INSERT)
395     check (abt_insert (abt, &insert->node) == NULL);
396   else
397     {
398       struct abt_node *p = abt->root;
399       int dir = 0;
400       if (p != NULL)
401         for (;;)
402           {
403             dir = insert->data > abt_node_to_element (p)->data;
404             if (p->down[dir] == NULL)
405               break;
406             p = p->down[dir];
407           }
408       if (method == INSERT_AFTER)
409         {
410           if (p != NULL && (dir != 1 || p->down[1] != NULL))
411             p = abt_prev (abt, p);
412           abt_insert_after (abt, p, &insert->node);
413         }
414       else
415         {
416           if (p != NULL && (dir != 0 || p->down[0] != NULL))
417             p = abt_next (abt, p);
418           abt_insert_before (abt, p, &insert->node);
419         }
420     }
421 }
422
423
424 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
425    ABT in the order specified by INSERTIONS using the given
426    METHOD, then deletes them in the order specified by DELETIONS,
427    checking the ABT's contents for correctness after each
428    operation. */
429 static void
430 do_test_insert_delete (enum insertion_method method,
431                        const int insertions[],
432                        const int deletions[],
433                        size_t cnt)
434 {
435   struct element *elements;
436   struct abt abt;
437   size_t i;
438
439   elements = xnmalloc (cnt, sizeof *elements);
440   for (i = 0; i < cnt; i++)
441     elements[i].data = i;
442
443   abt_init (&abt, method == INSERT ? compare_elements : NULL,
444             reaugment_elements, &aux_data);
445   check_abt (&abt, NULL, 0);
446   for (i = 0; i < cnt; i++)
447     {
448       insert_node (&abt, &elements[insertions[i]], method);
449       check_abt (&abt, insertions, i + 1);
450     }
451   for (i = 0; i < cnt; i++)
452     {
453       abt_delete (&abt, &elements[deletions[i]].node);
454       check_abt (&abt, deletions + i + 1, cnt - i - 1);
455     }
456
457   free (elements);
458 }
459
460 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
461    ABT in the order specified by INSERTIONS, then deletes them in
462    the order specified by DELETIONS, checking the ABT's contents
463    for correctness after each operation. */
464 static void
465 test_insert_delete (const int insertions[],
466                     const int deletions[],
467                     size_t cnt)
468 {
469   do_test_insert_delete (INSERT, insertions, deletions, cnt);
470   do_test_insert_delete (INSERT_AFTER, insertions, deletions, cnt);
471   do_test_insert_delete (INSERT_BEFORE, insertions, deletions, cnt);
472 }
473 \f
474 /* Inserts values into an ABT in each possible order, then
475    removes them in each possible order, up to a specified maximum
476    size. */
477 static void
478 test_insert_any_remove_any (void)
479 {
480   const int max_elems = 5;
481   int cnt;
482
483   for (cnt = 0; cnt <= max_elems; cnt++)
484     {
485       int *insertions, *deletions;
486       unsigned int ins_perm_cnt;
487       int i;
488
489       insertions = xnmalloc (cnt, sizeof *insertions);
490       deletions = xnmalloc (cnt, sizeof *deletions);
491       for (i = 0; i < cnt; i++)
492         insertions[i] = i;
493
494       for (ins_perm_cnt = 0;
495            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
496            ins_perm_cnt++)
497         {
498           unsigned int del_perm_cnt;
499           int i;
500
501           for (i = 0; i < cnt; i++)
502             deletions[i] = i;
503
504           for (del_perm_cnt = 0;
505                del_perm_cnt == 0 || next_permutation (deletions, cnt);
506                del_perm_cnt++)
507             test_insert_delete (insertions, deletions, cnt);
508
509           check (del_perm_cnt == factorial (cnt));
510         }
511       check (ins_perm_cnt == factorial (cnt));
512
513       free (insertions);
514       free (deletions);
515     }
516 }
517
518 /* Inserts values into an ABT in each possible order, then
519    removes them in the same order, up to a specified maximum
520    size. */
521 static void
522 test_insert_any_remove_same (void)
523 {
524   const int max_elems = 7;
525   int cnt;
526
527   for (cnt = 0; cnt <= max_elems; cnt++)
528     {
529       int *values;
530       unsigned int permutation_cnt;
531       int i;
532
533       values = xnmalloc (cnt, sizeof *values);
534       for (i = 0; i < cnt; i++)
535         values[i] = i;
536
537       for (permutation_cnt = 0;
538            permutation_cnt == 0 || next_permutation (values, cnt);
539            permutation_cnt++)
540         test_insert_delete (values, values, cnt);
541       check (permutation_cnt == factorial (cnt));
542
543       free (values);
544     }
545 }
546
547 /* Inserts values into an ABT in each possible order, then
548    removes them in reverse order, up to a specified maximum
549    size. */
550 static void
551 test_insert_any_remove_reverse (void)
552 {
553   const int max_elems = 7;
554   int cnt;
555
556   for (cnt = 0; cnt <= max_elems; cnt++)
557     {
558       int *insertions, *deletions;
559       unsigned int permutation_cnt;
560       int i;
561
562       insertions = xnmalloc (cnt, sizeof *insertions);
563       deletions = xnmalloc (cnt, sizeof *deletions);
564       for (i = 0; i < cnt; i++)
565         insertions[i] = i;
566
567       for (permutation_cnt = 0;
568            permutation_cnt == 0 || next_permutation (insertions, cnt);
569            permutation_cnt++)
570         {
571           memcpy (deletions, insertions, sizeof *insertions * cnt);
572           reverse (deletions, cnt);
573
574           test_insert_delete (insertions, deletions, cnt);
575         }
576       check (permutation_cnt == factorial (cnt));
577
578       free (insertions);
579       free (deletions);
580     }
581 }
582
583 /* Inserts and removes values in an ABT in random orders. */
584 static void
585 test_random_sequence (void)
586 {
587   const int max_elems = 128;
588   const int max_trials = 8;
589   int cnt;
590
591   for (cnt = 0; cnt <= max_elems; cnt += 2)
592     {
593       int *insertions, *deletions;
594       int trial;
595       int i;
596
597       insertions = xnmalloc (cnt, sizeof *insertions);
598       deletions = xnmalloc (cnt, sizeof *deletions);
599       for (i = 0; i < cnt; i++)
600         insertions[i] = i;
601       for (i = 0; i < cnt; i++)
602         deletions[i] = i;
603
604       for (trial = 0; trial < max_trials; trial++)
605         {
606           random_shuffle (insertions, cnt, sizeof *insertions);
607           random_shuffle (deletions, cnt, sizeof *deletions);
608
609           test_insert_delete (insertions, deletions, cnt);
610         }
611
612       free (insertions);
613       free (deletions);
614     }
615 }
616
617 /* Inserts elements into an ABT in ascending order. */
618 static void
619 test_insert_ordered (void)
620 {
621   const int max_elems = 1024;
622   struct element *elements;
623   int *values;
624   struct abt abt;
625   int i;
626
627   abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
628   elements = xnmalloc (max_elems, sizeof *elements);
629   values = xnmalloc (max_elems, sizeof *values);
630   for (i = 0; i < max_elems; i++)
631     {
632       values[i] = elements[i].data = i;
633       check (abt_insert (&abt, &elements[i].node) == NULL);
634       check_abt (&abt, values, i + 1);
635     }
636   free (elements);
637   free (values);
638 }
639
640 /* Inserts elements into an ABT, then moves the nodes around in
641    memory. */
642 static void
643 test_moved (void)
644 {
645   const int max_elems = 128;
646   struct element *e[2];
647   int cur;
648   int *values;
649   struct abt abt;
650   int i, j;
651
652   abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
653   e[0] = xnmalloc (max_elems, sizeof *e[0]);
654   e[1] = xnmalloc (max_elems, sizeof *e[1]);
655   values = xnmalloc (max_elems, sizeof *values);
656   cur = 0;
657   for (i = 0; i < max_elems; i++)
658     {
659       values[i] = e[cur][i].data = i;
660       check (abt_insert (&abt, &e[cur][i].node) == NULL);
661       check_abt (&abt, values, i + 1);
662
663       for (j = 0; j <= i; j++)
664         {
665           e[!cur][j] = e[cur][j];
666           abt_moved (&abt, &e[!cur][j].node);
667           check_abt (&abt, values, i + 1);
668         }
669       cur = !cur;
670     }
671   free (e[0]);
672   free (e[1]);
673   free (values);
674 }
675
676 /* Inserts values into an ABT, then changes their values. */
677 static void
678 test_changed (void)
679 {
680   const int max_elems = 6;
681   int cnt;
682
683   for (cnt = 0; cnt <= max_elems; cnt++)
684     {
685       int *values, *changed_values;
686       struct element *elements;
687       unsigned int permutation_cnt;
688       int i;
689
690       values = xnmalloc (cnt, sizeof *values);
691       changed_values = xnmalloc (cnt, sizeof *changed_values);
692       elements = xnmalloc (cnt, sizeof *elements);
693       for (i = 0; i < cnt; i++)
694         values[i] = i;
695
696       for (permutation_cnt = 0;
697            permutation_cnt == 0 || next_permutation (values, cnt);
698            permutation_cnt++)
699         {
700           for (i = 0; i < cnt; i++)
701             {
702               int j, k;
703               for (j = 0; j <= cnt; j++)
704                 {
705                   struct abt abt;
706                   struct abt_node *changed_retval;
707
708                   abt_init (&abt, compare_elements, reaugment_elements,
709                             &aux_data);
710
711                   /* Add to ABT in order. */
712                   for (k = 0; k < cnt; k++)
713                     {
714                       int n = values[k];
715                       elements[n].data = n;
716                       check (abt_insert (&abt, &elements[n].node) == NULL);
717                     }
718                   check_abt (&abt, values, cnt);
719
720                   /* Change value i to j. */
721                   elements[i].data = j;
722                   for (k = 0; k < cnt; k++)
723                     changed_values[k] = k;
724                   changed_retval = abt_changed (&abt, &elements[i].node);
725                   if (i != j && j < cnt)
726                     {
727                       /* Will cause duplicate. */
728                       check (changed_retval == &elements[j].node);
729                       changed_values[i] = changed_values[cnt - 1];
730                       check_abt (&abt, changed_values, cnt - 1);
731                     }
732                   else
733                     {
734                       /* Succeeds. */
735                       check (changed_retval == NULL);
736                       changed_values[i] = j;
737                       check_abt (&abt, changed_values, cnt);
738                     }
739                 }
740             }
741         }
742       check (permutation_cnt == factorial (cnt));
743
744       free (values);
745       free (changed_values);
746       free (elements);
747     }
748 }
749 \f
750 /* Main program. */
751
752 struct test
753   {
754     const char *name;
755     const char *description;
756     void (*function) (void);
757   };
758
759 static const struct test tests[] =
760   {
761     {
762       "insert-any-remove-any",
763       "insert any order, delete any order",
764       test_insert_any_remove_any
765     },
766     {
767       "insert-any-remove-same",
768       "insert any order, delete same order",
769       test_insert_any_remove_same
770     },
771     {
772       "insert-any-remove-reverse",
773       "insert any order, delete reverse order",
774       test_insert_any_remove_reverse
775     },
776     {
777       "random-sequence",
778       "insert and delete in random sequence",
779       test_random_sequence
780     },
781     {
782       "insert-ordered",
783       "insert in ascending order",
784       test_insert_ordered
785     },
786     {
787       "moved",
788       "move elements around in memory",
789       test_moved
790     },
791     {
792       "changed",
793       "change key data in nodes",
794       test_changed
795     }
796   };
797
798 enum { N_TESTS = sizeof tests / sizeof *tests };
799
800 int
801 main (int argc, char *argv[])
802 {
803   int i;
804
805   if (argc != 2)
806     {
807       fprintf (stderr, "exactly one argument required; use --help for help\n");
808       return EXIT_FAILURE;
809     }
810   else if (!strcmp (argv[1], "--help"))
811     {
812       printf ("%s: test augmented binary tree\n"
813               "usage: %s TEST-NAME\n"
814               "where TEST-NAME is one of the following:\n",
815               argv[0], argv[0]);
816       for (i = 0; i < N_TESTS; i++)
817         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
818       return 0;
819     }
820   else
821     {
822       for (i = 0; i < N_TESTS; i++)
823         if (!strcmp (argv[1], tests[i].name))
824           {
825             tests[i].function ();
826             return 0;
827           }
828
829       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
830       return EXIT_FAILURE;
831     }
832 }