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