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