Increment version to 0.7.9 to send to Translation Project.
[pspp-builds.git] / tests / libpspp / heap-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 routines defined in heap.c.
18    This test program aims to be as comprehensive as possible.
19    With -DNDEBUG, "gcov -b" should report 100% coverage of lines
20    and branches in heap.c routines, except for the is_heap
21    function, which is not called at all with -DNDEBUG.  (Without
22    -DNDEBUG, branches caused by failed assertions will also not
23    be taken.)  "valgrind --leak-check=yes --show-reachable=yes"
24    should give a clean report, both with and without -DNDEBUG. */
25
26 #ifdef HAVE_CONFIG_H
27 #include <config.h>
28 #endif
29
30 #include <libpspp/heap.h>
31
32 #include <assert.h>
33 #include <limits.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <string.h>
37
38 #include <libpspp/compiler.h>
39
40 #include "xalloc.h"
41 \f
42 /* Exit with a failure code.
43    (Place a breakpoint on this function while debugging.) */
44 static void
45 check_die (void)
46 {
47   exit (EXIT_FAILURE);
48 }
49
50 /* If OK is not true, prints a message about failure on the
51    current source file and the given LINE and terminates. */
52 static void
53 check_func (bool ok, int line)
54 {
55   if (!ok)
56     {
57       fprintf (stderr, "%s:%d: check failed\n", __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 \f
67 /* Node type and support routines. */
68
69 /* Test data element. */
70 struct element
71   {
72     struct heap_node node;      /* Embedded heap element. */
73     int x;                      /* Primary value. */
74   };
75
76 static int aux_data;
77
78 /* Returns the `struct element' that NODE is embedded within. */
79 static struct element *
80 heap_node_to_element (const struct heap_node *node)
81 {
82   return heap_data (node, struct element, node);
83 }
84
85 /* Compares the `x' values in A and B and returns a strcmp-type
86    return value.  Verifies that AUX points to aux_data. */
87 static int
88 compare_elements (const struct heap_node *a_, const struct heap_node *b_,
89                   const void *aux)
90 {
91   const struct element *a = heap_node_to_element (a_);
92   const struct element *b = heap_node_to_element (b_);
93
94   check (aux == &aux_data);
95   return a->x < b->x ? -1 : a->x > b->x;
96 }
97
98 /* Returns the smallest of the N integers in ARRAY. */
99 static int
100 min_int (int *array, size_t n)
101 {
102   int min;
103   size_t i;
104
105   min = INT_MAX;
106   for (i = 0; i < n; i++)
107     if (array[i] < min)
108       min = array[i];
109   return min;
110 }
111
112 /* Swaps *A and *B. */
113 static void
114 swap (int *a, int *b)
115 {
116   int t = *a;
117   *a = *b;
118   *b = t;
119 }
120
121 /* Reverses the order of the CNT integers starting at VALUES. */
122 static void
123 reverse (int *values, size_t cnt)
124 {
125   size_t i = 0;
126   size_t j = cnt;
127
128   while (j > i)
129     swap (&values[i++], &values[--j]);
130 }
131
132 /* Arranges the CNT elements in VALUES into the lexicographically
133    next greater permutation.  Returns true if successful.
134    If VALUES is already the lexicographically greatest
135    permutation of its elements (i.e. ordered from greatest to
136    smallest), arranges them into the lexicographically least
137    permutation (i.e. ordered from smallest to largest) and
138    returns false. */
139 static bool
140 next_permutation (int *values, size_t cnt)
141 {
142   if (cnt > 0)
143     {
144       size_t i = cnt - 1;
145       while (i != 0)
146         {
147           i--;
148           if (values[i] < values[i + 1])
149             {
150               size_t j;
151               for (j = cnt - 1; values[i] >= values[j]; j--)
152                 continue;
153               swap (values + i, values + j);
154               reverse (values + (i + 1), cnt - (i + 1));
155               return true;
156             }
157         }
158
159       reverse (values, cnt);
160     }
161
162   return false;
163 }
164
165 /* Returns N!. */
166 static unsigned int
167 factorial (unsigned int n)
168 {
169   unsigned int value = 1;
170   while (n > 1)
171     value *= n--;
172   return value;
173 }
174
175 /* Returns the number of permutations of the CNT values in
176    VALUES.  If VALUES contains duplicates, they must be
177    adjacent. */
178 static unsigned int
179 expected_perms (int *values, size_t cnt)
180 {
181   size_t i, j;
182   unsigned int perm_cnt;
183
184   perm_cnt = factorial (cnt);
185   for (i = 0; i < cnt; i = j)
186     {
187       for (j = i + 1; j < cnt; j++)
188         if (values[i] != values[j])
189           break;
190       perm_cnt /= factorial (j - i);
191     }
192   return perm_cnt;
193 }
194
195 /* Tests whether PARTS is a K-part integer composition of N.
196    Returns true if so, false otherwise. */
197 static bool UNUSED
198 is_k_composition (int n, int k, const int parts[])
199 {
200   int sum;
201   int i;
202
203   sum = 0;
204   for (i = 0; i < k; i++)
205     {
206       if (parts[i] < 1 || parts[i] > n)
207         return false;
208       sum += parts[i];
209     }
210   return sum == n;
211 }
212
213 /* Advances the K-part integer composition of N stored in PARTS
214    to the next lexicographically greater one.
215    Returns true if successful, false if the composition was
216    already the greatest K-part composition of N (in which case
217    PARTS is unaltered). */
218 static bool
219 next_k_composition (int n UNUSED, int k, int parts[])
220 {
221   int x, i;
222
223   assert (is_k_composition (n, k, parts));
224   if (k == 1)
225     return false;
226
227   for (i = k - 1; i > 0; i--)
228     if (parts[i] > 1)
229       break;
230   if (i == 0)
231     return false;
232
233   x = parts[i] - 1;
234   parts[i] = 1;
235   parts[i - 1]++;
236   parts[k - 1] = x;
237
238   assert (is_k_composition (n, k, parts));
239   return true;
240 }
241
242 /* Advances *K and PARTS to the next integer composition of N.
243    Compositions are ordered from shortest to longest and in
244    lexicographical order within a given length.
245    Before the first call, initialize *K to 0.
246    After each successful call, *K contains the length of the
247    current composition and the *K elements in PARTS contain its
248    parts.
249    Returns true if successful, false if the set of compositions
250    has been exhausted. */
251 static bool
252 next_composition (int n, int *k, int parts[])
253 {
254   if (*k >= 1 && next_k_composition (n, *k, parts))
255     return true;
256   else if (*k < n)
257     {
258       int i;
259       for (i = 0; i < *k; i++)
260         parts[i] = 1;
261       parts[i] = n - *k;
262       (*k)++;
263       return true;
264     }
265   else
266     return false;
267 }
268 \f
269 /* Inserts sequences without duplicates into a heap, and then
270    ensures that they appear as the minimum element in the correct
271    order as we delete them.  Exhaustively tests every input
272    permutation up to 'max_elems' elements. */
273 static void
274 test_insert_no_dups_delete_min (void)
275 {
276   const int max_elems = 8;
277   int cnt;
278
279   for (cnt = 0; cnt <= max_elems; cnt++)
280     {
281       struct heap *h;
282       struct element *elements;
283       int *values;
284       unsigned int permutation_cnt;
285       int i;
286
287       values = xnmalloc (cnt, sizeof *values);
288       elements = xnmalloc (cnt, sizeof *elements);
289       for (i = 0; i < cnt; i++)
290         values[i] = i;
291
292       h = heap_create (compare_elements, &aux_data);
293       permutation_cnt = 0;
294       while (permutation_cnt == 0 || next_permutation (values, cnt))
295         {
296           int i;
297
298           for (i = 0; i < cnt; i++)
299             elements[i].x = values[i];
300
301           check (heap_is_empty (h));
302           for (i = 0; i < cnt; i++)
303             {
304               heap_insert (h, &elements[i].node);
305               check (heap_node_to_element (heap_minimum (h))->x
306                      == min_int (values, i + 1));
307               check (heap_count (h) == i + 1);
308             }
309
310           for (i = 0; i < cnt; i++)
311             {
312               check (heap_node_to_element (heap_minimum (h))->x == i);
313               heap_delete (h, heap_minimum (h));
314             }
315           check (heap_is_empty (h));
316           permutation_cnt++;
317         }
318       check (permutation_cnt == factorial (cnt));
319       heap_destroy (h);
320       free (values);
321       free (elements);
322     }
323 }
324
325 /* Inserts sequences with duplicates into a heap, and then
326    ensures that they appear as the minimum element in the correct
327    order as we delete them.  Exhaustively tests every input
328    permutation up to 'max_elems' elements.
329
330    See Usenet article <87mz4utika.fsf@blp.benpfaff.org> for
331    details of the algorithm used here. */
332 static void
333 test_insert_with_dups_delete_min (void)
334 {
335   const int max_elems = 7;
336   int cnt;
337
338   for (cnt = 1; cnt <= max_elems; cnt++)
339     {
340       unsigned int composition_cnt;
341       int *dups;
342       int unique_cnt;
343       int *values;
344       int *sorted_values;
345       struct element *elements;
346       int n = 0;
347
348       dups = xnmalloc (cnt, sizeof *dups);
349       values = xnmalloc (cnt, sizeof *values);
350       sorted_values = xnmalloc (cnt, sizeof *sorted_values);
351       elements = xnmalloc (cnt, sizeof *elements);
352
353       unique_cnt = 0;
354       composition_cnt = 0;
355       while (next_composition (cnt, &unique_cnt, dups))
356         {
357           struct heap *h;
358           int i, j, k;
359           unsigned int permutation_cnt;
360
361           k = 0;
362           for (i = 0; i < unique_cnt; i++)
363             for (j = 0; j < dups[i]; j++)
364               {
365                 values[k] = i;
366                 sorted_values[k] = i;
367                 k++;
368               }
369           check (k == cnt);
370
371           h = heap_create (compare_elements, &aux_data);
372           permutation_cnt = 0;
373           while (permutation_cnt == 0 || next_permutation (values, cnt))
374             {
375               int min = INT_MAX;
376
377               for (i = 0; i < cnt; i++)
378                 elements[i].x = values[i];
379               n++;
380
381               check (heap_is_empty (h));
382               for (i = 0; i < cnt; i++)
383                 {
384                   heap_insert (h, &elements[i].node);
385                   if (values[i] < min)
386                     min = values[i];
387                   check (heap_node_to_element (heap_minimum (h))->x == min);
388                   check (heap_count (h) == i + 1);
389                 }
390
391               for (i = 0; i < cnt; i++)
392                 {
393                   struct element *min = heap_node_to_element (heap_minimum (h));
394                   check (min->x == sorted_values[i]);
395                   heap_delete (h, heap_minimum (h));
396                 }
397               check (heap_is_empty (h));
398               permutation_cnt++;
399             }
400           check (permutation_cnt == expected_perms (values, cnt));
401           heap_destroy (h);
402
403           composition_cnt++;
404         }
405       check (composition_cnt == 1 << (cnt - 1));
406
407       free (dups);
408       free (values);
409       free (sorted_values);
410       free (elements);
411     }
412 }
413
414 /* Inserts a sequence without duplicates into a heap, then
415    deletes them in a different order. */
416 static void
417 test_insert_no_dups_delete_random (void)
418 {
419   const int max_elems = 5;
420   int cnt;
421
422   for (cnt = 0; cnt <= max_elems; cnt++)
423     {
424       struct heap *h;
425       struct element *elements;
426       int *insert, *delete;
427       unsigned int insert_perm_cnt;
428       int i;
429
430       insert = xnmalloc (cnt, sizeof *insert);
431       delete = xnmalloc (cnt, sizeof *delete);
432       elements = xnmalloc (cnt, sizeof *elements);
433       for (i = 0; i < cnt; i++)
434         {
435           insert[i] = i;
436           delete[i] = i;
437           elements[i].x = i;
438         }
439
440       h = heap_create (compare_elements, &aux_data);
441       insert_perm_cnt = 0;
442       while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
443         {
444           unsigned int delete_perm_cnt = 0;
445
446           while (delete_perm_cnt == 0 || next_permutation (delete, cnt))
447             {
448               int min;
449               int i;
450
451               check (heap_is_empty (h));
452               min = INT_MAX;
453               for (i = 0; i < cnt; i++)
454                 {
455                   heap_insert (h, &elements[insert[i]].node);
456                   if (insert[i] < min)
457                     min = insert[i];
458                   check (heap_node_to_element (heap_minimum (h))->x == min);
459                   check (heap_count (h) == i + 1);
460                 }
461
462               for (i = 0; i < cnt; i++)
463                 {
464                   int new_min = min_int (delete + i + 1, cnt - i - 1);
465                   heap_delete (h, &elements[delete[i]].node);
466                   check (heap_count (h) == cnt - i - 1);
467                   if (!heap_is_empty (h))
468                     check (heap_node_to_element (heap_minimum (h))->x == new_min);
469                 }
470               check (heap_is_empty (h));
471               delete_perm_cnt++;
472             }
473           check (delete_perm_cnt == factorial (cnt));
474           insert_perm_cnt++;
475         }
476       check (insert_perm_cnt == factorial (cnt));
477       heap_destroy (h);
478       free (insert);
479       free (delete);
480       free (elements);
481     }
482 }
483
484 /* Inserts a set of values into a heap, then changes them to a
485    different random set of values, then removes them in sorted
486    order. */
487 static void
488 test_inc_dec (void)
489 {
490   const int max_elems = 8;
491   int cnt;
492
493   for (cnt = 0; cnt <= max_elems; cnt++)
494     {
495       struct heap *h;
496       struct element *elements;
497       int *insert, *delete;
498       unsigned int insert_perm_cnt;
499       int i;
500
501       insert = xnmalloc (cnt, sizeof *insert);
502       delete = xnmalloc (cnt, sizeof *delete);
503       elements = xnmalloc (cnt, sizeof *elements);
504       for (i = 0; i < cnt; i++)
505         insert[i] = i;
506
507       h = heap_create (compare_elements, &aux_data);
508       insert_perm_cnt = 0;
509       while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
510         {
511           for (i = 0; i < cnt; i++)
512             elements[i].x = insert[i];
513
514           check (heap_is_empty (h));
515           for (i = 0; i < cnt; i++)
516             {
517               int new_min = min_int (insert, i + 1);
518               heap_insert (h, &elements[i].node);
519               check (heap_node_to_element (heap_minimum (h))->x == new_min);
520               check (heap_count (h) == i + 1);
521             }
522
523           for (i = 0; i < cnt; i++)
524             delete[i] = insert[i];
525           for (i = 0; i < cnt; i++)
526             {
527               int old_value, old_min, new_min;
528               old_min = min_int (delete, cnt);
529               old_value = delete[i];
530               elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
531               new_min = min_int (delete, cnt);
532               heap_changed (h, &elements[i].node);
533               check (heap_node_to_element (heap_minimum (h))->x
534                      == min_int (delete, cnt));
535             }
536
537           for (i = 0; i < cnt; i++)
538             {
539               int new_min = min_int (delete + i + 1, cnt - i - 1);
540               heap_delete (h, &elements[i].node);
541               check (heap_count (h) == cnt - i - 1);
542               if (!heap_is_empty (h))
543                 check (heap_node_to_element (heap_minimum (h))->x == new_min);
544             }
545           check (heap_is_empty (h));
546           insert_perm_cnt++;
547         }
548       check (insert_perm_cnt == factorial (cnt));
549       heap_destroy (h);
550       free (insert);
551       free (delete);
552       free (elements);
553     }
554 }
555
556 /* Performs a random sequence of insertions and deletions in a
557    heap. */
558 static void
559 test_random_insert_delete (void)
560 {
561   const int max_elems = 64;
562   const int num_actions = 250000;
563   struct heap *h;
564   int *values;
565   struct element *elements;
566   int cnt;
567   int insert_chance;
568   int i;
569
570   values = xnmalloc (max_elems, sizeof *values);
571   elements = xnmalloc (max_elems, sizeof *elements);
572   cnt = 0;
573   insert_chance = 5;
574
575   h = heap_create (compare_elements, &aux_data);
576   for (i = 0; i < num_actions; i++)
577     {
578       enum { INSERT, DELETE } action;
579
580       if (cnt == 0)
581         {
582           action = INSERT;
583           if (insert_chance < 9)
584             insert_chance++;
585         }
586       else if (cnt == max_elems)
587         {
588           action = DELETE;
589           if (insert_chance > 0)
590             insert_chance--;
591         }
592       else
593         action = rand () % 10 < insert_chance ? INSERT : DELETE;
594
595       if (action == INSERT)
596         {
597           int new_value;
598           int old_min;
599
600           new_value = rand () % max_elems;
601           values[cnt] = new_value;
602           elements[cnt].x = new_value;
603
604           heap_insert (h, &elements[cnt].node);
605
606           old_min = min_int (values, cnt);
607
608           cnt++;
609         }
610       else if (action == DELETE)
611         {
612           int del_idx;
613           int del_value;
614           int old_min, new_min;
615
616           old_min = min_int (values, cnt);
617
618           del_idx = rand () % cnt;
619           del_value = values[del_idx];
620           heap_delete (h, &elements[del_idx].node);
621
622           cnt--;
623           if (del_idx != cnt)
624             {
625               values[del_idx] = values[cnt];
626               elements[del_idx] = elements[cnt];
627               heap_moved (h, &elements[del_idx].node);
628             }
629
630           new_min = min_int (values, cnt);
631         }
632       else
633         abort ();
634
635       check (heap_count (h) == cnt);
636       check (heap_is_empty (h) == (cnt == 0));
637       if (cnt > 0)
638         check (heap_node_to_element (heap_minimum (h))->x
639                == min_int (values, cnt));
640     }
641   heap_destroy (h);
642   free (elements);
643   free (values);
644 }
645 \f
646 /* Main program. */
647
648 struct test
649   {
650     const char *name;
651     const char *description;
652     void (*function) (void);
653   };
654
655 static const struct test tests[] =
656   {
657     {
658       "insert-no-dups-delete-min",
659       "insert (no dups), delete minimum values",
660       test_insert_no_dups_delete_min
661     },
662     {
663       "insert-with-dups-delete-min",
664       "insert with dups, delete minimum values",
665       test_insert_with_dups_delete_min
666     },
667     {
668       "insert-no-dups-delete-random",
669       "insert (no dups), delete in random order",
670       test_insert_no_dups_delete_random
671     },
672     {
673       "inc-dec",
674       "increase and decrease values",
675       test_inc_dec
676     },
677     {
678       "random-insert-delete",
679       "random insertions and deletions",
680       test_random_insert_delete
681     }
682   };
683
684 enum { N_TESTS = sizeof tests / sizeof *tests };
685
686 int
687 main (int argc, char *argv[])
688 {
689   int i;
690
691   if (argc != 2)
692     {
693       fprintf (stderr, "exactly one argument required; use --help for help\n");
694       return EXIT_FAILURE;
695     }
696   else if (!strcmp (argv[1], "--help"))
697     {
698       printf ("%s: test heap library\n"
699               "usage: %s TEST-NAME\n"
700               "where TEST-NAME is one of the following:\n",
701               argv[0], argv[0]);
702       for (i = 0; i < N_TESTS; i++)
703         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
704       return 0;
705     }
706   else
707     {
708       for (i = 0; i < N_TESTS; i++)
709         if (!strcmp (argv[1], tests[i].name))
710           {
711             tests[i].function ();
712             return 0;
713           }
714
715       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
716       return EXIT_FAILURE;
717     }
718 }