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