Fix GCC 4.3 warning about uninitialized structure member.
[pspp] / tests / libpspp / range-map-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 routines defined in
18    range-map.c.  This test program aims to be as comprehensive as
19    possible.  With -DNDEBUG, "gcov -b" should report 100%
20    coverage of lines and branches in range-map.c routines.
21    (Without -DNDEBUG, branches caused by failed assertions will
22    not be taken.)  "valgrind --leak-check=yes
23    --show-reachable=yes" should give a clean report, both with
24    and without -DNDEBUG. */
25
26 #ifdef HAVE_CONFIG_H
27 #include <config.h>
28 #endif
29
30 #include <libpspp/range-map.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 /* Currently running test. */
43 static const char *test_name;
44
45 /* Exit with a failure code.
46    (Place a breakpoint on this function while debugging.) */
47 static void
48 check_die (void)
49 {
50   exit (EXIT_FAILURE);
51 }
52
53 /* If OK is not true, prints a message about failure on the
54    current source file and the given LINE and terminates. */
55 static void
56 check_func (bool ok, int line)
57 {
58   if (!ok)
59     {
60       printf ("Check failed in %s test at %s, line %d\n",
61               test_name, __FILE__, line);
62       check_die ();
63     }
64 }
65
66 /* Verifies that EXPR evaluates to true.
67    If not, prints a message citing the calling line number and
68    terminates. */
69 #define check(EXPR) check_func ((EXPR), __LINE__)
70 \f
71 /* Swaps *A and *B. */
72 static void
73 swap (int *a, int *b)
74 {
75   int t = *a;
76   *a = *b;
77   *b = t;
78 }
79
80 /* Reverses the order of the CNT integers starting at VALUES. */
81 static void
82 reverse (int *values, size_t cnt)
83 {
84   size_t i = 0;
85   size_t j = cnt;
86
87   while (j > i)
88     swap (&values[i++], &values[--j]);
89 }
90
91 /* Arranges the CNT blocks in VALUES into the lexicographically
92    next greater permutation.  Returns true if successful.
93    If VALUES is already the lexicographically greatest
94    permutation of its blocks (i.e. ordered from greatest to
95    smallest), arranges them into the lexicographically least
96    permutation (i.e. ordered from smallest to largest) and
97    returns false. */
98 static bool
99 next_permutation (int *values, size_t cnt)
100 {
101   if (cnt > 0)
102     {
103       size_t i = cnt - 1;
104       while (i != 0)
105         {
106           i--;
107           if (values[i] < values[i + 1])
108             {
109               size_t j;
110               for (j = cnt - 1; values[i] >= values[j]; j--)
111                 continue;
112               swap (values + i, values + j);
113               reverse (values + (i + 1), cnt - (i + 1));
114               return true;
115             }
116         }
117
118       reverse (values, cnt);
119     }
120
121   return false;
122 }
123
124 /* Returns N!. */
125 static unsigned int
126 factorial (unsigned int n)
127 {
128   unsigned int value = 1;
129   /* Disallow N values that overflow on 32-bit machines. */
130   assert (n <= 12);
131   for (; n > 1; )
132     value *= n--;
133   return value;
134 }
135
136 /* Tests whether PARTS is a K-part integer composition of N.
137    Returns true if so, false otherwise. */
138 static bool UNUSED
139 is_k_composition (int n, int k, const int parts[])
140 {
141   int sum;
142   int i;
143
144   sum = 0;
145   for (i = 0; i < k; i++)
146     {
147       if (parts[i] < 1 || parts[i] > n)
148         return false;
149       sum += parts[i];
150     }
151   return sum == n;
152 }
153
154 /* Advances the K-part integer composition of N stored in PARTS
155    to the next lexicographically greater one.
156    Returns true if successful, false if the composition was
157    already the greatest K-part composition of N (in which case
158    PARTS is unaltered). */
159 static bool
160 next_k_composition (int n UNUSED, int k, int parts[])
161 {
162   int x, i;
163
164   assert (is_k_composition (n, k, parts));
165   if (k == 1)
166     return false;
167
168   for (i = k - 1; i > 0; i--)
169     if (parts[i] > 1)
170       break;
171   if (i == 0)
172     return false;
173
174   x = parts[i] - 1;
175   parts[i] = 1;
176   parts[i - 1]++;
177   parts[k - 1] = x;
178
179   assert (is_k_composition (n, k, parts));
180   return true;
181 }
182
183 /* Sets the K integers in PARTS to the lexicographically first
184    K-part composition of N. */
185 static void
186 first_k_composition (int n, int k, int parts[])
187 {
188   int i;
189
190   assert (n >= k);
191
192   for (i = 0; i < k; i++)
193     parts[i] = 1;
194   parts[k - 1] += n - k;
195 }
196
197 /* Advances *K and PARTS to the next integer composition of N.
198    Compositions are ordered from shortest to longest and in
199    lexicographical order within a given length.
200    Before the first call, initialize *K to 0.
201    After each successful call, *K contains the length of the
202    current composition and the *K blocks in PARTS contain its
203    parts.
204    Returns true if successful, false if the set of compositions
205    has been exhausted. */
206 static bool
207 next_composition (int n, int *k, int parts[])
208 {
209   if (*k >= 1 && next_k_composition (n, *k, parts))
210     return true;
211   else if (*k < n)
212     {
213       first_k_composition (n, ++*k, parts);
214       return true;
215     }
216   else
217     return false;
218 }
219 \f
220 /* Test data element. */
221 struct element
222   {
223     struct range_map_node node; /* Embedded tower block. */
224     int x;                      /* Primary value. */
225   };
226
227 static struct element *
228 range_map_node_to_element (struct range_map_node *node)
229 {
230   return range_map_data (node, struct element, node);
231 }
232
233 /* Element we expect to find. */
234 struct expected_element
235   {
236     int x;                      /* Primary value. */
237     unsigned long int start;    /* Start of region. */
238     unsigned long int end;      /* End of region. */
239   };
240
241 /* Compares expected_element A and B and returns a strcmp()-type
242    result. */
243 static int
244 compare_expected_element (const void *a_, const void *b_)
245 {
246   const struct expected_element *a = (const struct expected_element *) a_;
247   const struct expected_element *b = (const struct expected_element *) b_;
248   return a->start < b->start ? -1 : a->start > b->start;
249 }
250
251 /* Checks that RM contains the ELEM_CNT elements described by
252    ELEMENTS[]. */
253 static void
254 check_range_map (struct range_map *rm,
255                  struct expected_element elements[], size_t elem_cnt)
256 {
257   struct expected_element *sorted;
258   struct range_map_node *node;
259   size_t i;
260
261   sorted = xnmalloc (elem_cnt, sizeof *sorted);
262   memcpy (sorted, elements, elem_cnt * sizeof *elements);
263   qsort (sorted, elem_cnt, sizeof *sorted, compare_expected_element);
264
265   check (range_map_is_empty (rm) == (elem_cnt == 0));
266
267   for (i = 0; i < elem_cnt; i++)
268     {
269       struct expected_element *e = &sorted[i];
270       unsigned long int position;
271
272       /* Check that range_map_lookup finds all the positions
273          within the element. */
274       for (position = e->start; position < e->end; position++)
275         {
276           struct range_map_node *found = range_map_lookup (rm, position);
277           check (found != NULL);
278           check (range_map_node_to_element (found)->x == e->x);
279           check (range_map_node_get_start (found) == e->start);
280           check (range_map_node_get_end (found) == e->end);
281           check (range_map_node_get_width (found) == e->end - e->start);
282         }
283
284       /* If there shouldn't be any elements in the positions just
285          before or after the element, verify that
286          range_map_lookup doesn't find any there. */
287       if (e->start > 0 && (i == 0 || e[-1].end < e->start))
288         check (range_map_lookup (rm, e->start - 1) == NULL);
289       if (i == elem_cnt - 1 || e->end < e[1].start)
290         check (range_map_lookup (rm, e->end) == NULL);
291     }
292
293   for (node = (rand () % 2 ? range_map_first (rm) : range_map_next (rm, NULL)),
294          i = 0;
295        node != NULL;
296        node = range_map_next (rm, node), i++)
297     {
298       struct expected_element *e = &sorted[i];
299       check (range_map_node_to_element (node)->x == e->x);
300     }
301   check (i == elem_cnt);
302
303   free (sorted);
304 }
305 \f
306 /* Tests inserting all possible sets of ranges into a range map
307    in all possible orders, up to a specified maximum overall
308    range. */
309 static void
310 test_insert (void)
311 {
312   const int max_range = 7;
313   int cnt;
314
315   for (cnt = 1; cnt <= max_range; cnt++)
316     {
317       unsigned int composition_cnt;
318       struct expected_element *expected;
319       int *widths;
320       int elem_cnt;
321       int *order;
322       struct element *elements;
323
324       expected = xnmalloc (cnt, sizeof *expected);
325       widths = xnmalloc (cnt, sizeof *widths);
326       order = xnmalloc (cnt, sizeof *order);
327       elements = xnmalloc (cnt, sizeof *elements);
328
329       elem_cnt = 0;
330       composition_cnt = 0;
331       while (next_composition (cnt, &elem_cnt, widths))
332         {
333           int i, j;
334           unsigned int permutation_cnt;
335
336           for (i = 0; i < elem_cnt; i++)
337             order[i] = i;
338
339           permutation_cnt = 0;
340           while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
341             {
342               struct range_map rm;
343
344               /* Inserts the elem_cnt elements with the given
345                  widths[] into T in the order given by order[]. */
346               range_map_init (&rm);
347               for (i = 0; i < elem_cnt; i++)
348                 {
349                   unsigned long int start, end;
350                   int idx;
351
352                   idx = order[i];
353                   elements[idx].x = idx;
354
355                   /* Find start and end of element. */
356                   start = 0;
357                   for (j = 0; j < idx; j++)
358                     start += widths[j];
359                   end = start + widths[j];
360
361                   /* Insert. */
362                   range_map_insert (&rm, start, end - start,
363                                     &elements[idx].node);
364
365                   /* Check map contents. */
366                   expected[i].x = idx;
367                   expected[i].start = start;
368                   expected[i].end = end;
369                   check_range_map (&rm, expected, i + 1);
370                 }
371               permutation_cnt++;
372             }
373           check (permutation_cnt == factorial (elem_cnt));
374
375           composition_cnt++;
376         }
377       check (composition_cnt == 1 << (cnt - 1));
378
379       free (expected);
380       free (widths);
381       free (order);
382       free (elements);
383     }
384 }
385
386 /* Tests deleting ranges from a range map in all possible orders,
387    up to a specified maximum overall range. */
388 static void
389 test_delete (int gap)
390 {
391   const int max_range = 7;
392   int cnt;
393
394   for (cnt = 1; cnt <= max_range; cnt++)
395     {
396       unsigned int composition_cnt;
397       struct expected_element *expected;
398       int *widths;
399       int elem_cnt;
400       int *order;
401       struct element *elements;
402
403       expected = xnmalloc (cnt, sizeof *expected);
404       widths = xnmalloc (cnt, sizeof *widths);
405       order = xnmalloc (cnt, sizeof *order);
406       elements = xnmalloc (cnt, sizeof *elements);
407
408       elem_cnt = 0;
409       composition_cnt = 0;
410       while (next_composition (cnt, &elem_cnt, widths))
411         {
412           int i, j;
413           unsigned int permutation_cnt;
414
415           for (i = 0; i < elem_cnt; i++)
416             order[i] = i;
417
418           permutation_cnt = 0;
419           while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
420             {
421               struct range_map rm;
422               unsigned long int start;
423
424               /* Insert all the elements. */
425               range_map_init (&rm);
426               start = 0;
427               for (i = 0; i < elem_cnt; i++)
428                 {
429                   int width = widths[i] > gap ? widths[i] - gap : widths[i];
430                   unsigned long int end = start + width;
431
432                   elements[i].x = i;
433                   range_map_insert (&rm, start, end - start,
434                                     &elements[i].node);
435
436                   for (j = 0; ; j++)
437                     {
438                       assert (j < elem_cnt);
439                       if (order[j] == i)
440                         {
441                           expected[j].x = i;
442                           expected[j].start = start;
443                           expected[j].end = end;
444                           break;
445                         }
446                     }
447
448                   start += widths[i];
449                 }
450               check_range_map (&rm, expected, elem_cnt);
451
452               /* Delete the elements in the specified order. */
453               for (i = 0; i < elem_cnt; i++)
454                 {
455                   range_map_delete (&rm, &elements[order[i]].node);
456                   check_range_map (&rm, expected + i + 1, elem_cnt - i - 1);
457                 }
458
459               permutation_cnt++;
460             }
461           check (permutation_cnt == factorial (elem_cnt));
462
463           composition_cnt++;
464         }
465       check (composition_cnt == 1 << (cnt - 1));
466
467       free (expected);
468       free (widths);
469       free (order);
470       free (elements);
471     }
472 }
473
474 /* Tests deleting ranges from a range map filled with contiguous
475    ranges in all possible orders, up to a specified maximum
476    overall range. */
477 static void
478 test_delete_contiguous (void)
479 {
480   test_delete (0);
481 }
482
483 /* Tests deleting ranges from a range map filled with ranges
484    sometimes separated by gaps in all possible orders, up to a
485    specified maximum overall range. */
486 static void
487 test_delete_gaps (void)
488 {
489   test_delete (1);
490 }
491 \f
492 /* Main program. */
493
494 /* Runs TEST_FUNCTION and prints a message about NAME. */
495 static void
496 run_test (void (*test_function) (void), const char *name)
497 {
498   test_name = name;
499   putchar ('.');
500   fflush (stdout);
501   test_function ();
502 }
503
504 int
505 main (void)
506 {
507   run_test (test_insert, "insert");
508   run_test (test_delete_contiguous, "delete from contiguous ranges");
509   run_test (test_delete_gaps, "delete from ranges separated by gaps");
510   putchar ('\n');
511
512   return 0;
513 }