1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
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.
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.
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
19 /* This is a test program for the routines defined in
20 range-map.c. This test program aims to be as comprehensive as
21 possible. With -DNDEBUG, "gcov -b" should report 100%
22 coverage of lines and branches in range-map.c routines.
23 (Without -DNDEBUG, branches caused by failed assertions will
24 not be taken.) "valgrind --leak-check=yes
25 --show-reachable=yes" should give a clean report, both with
26 and without -DNDEBUG. */
32 #include <libpspp/range-map.h>
40 #include <libpspp/compiler.h>
44 /* Currently running test. */
45 static const char *test_name;
47 /* Exit with a failure code.
48 (Place a breakpoint on this function while debugging.) */
55 /* If OK is not true, prints a message about failure on the
56 current source file and the given LINE and terminates. */
58 check_func (bool ok, int line)
62 printf ("Check failed in %s test at %s, line %d\n",
63 test_name, __FILE__, line);
68 /* Verifies that EXPR evaluates to true.
69 If not, prints a message citing the calling line number and
71 #define check(EXPR) check_func ((EXPR), __LINE__)
73 /* Swaps *A and *B. */
82 /* Reverses the order of the CNT integers starting at VALUES. */
84 reverse (int *values, size_t cnt)
90 swap (&values[i++], &values[--j]);
93 /* Arranges the CNT blocks in VALUES into the lexicographically
94 next greater permutation. Returns true if successful.
95 If VALUES is already the lexicographically greatest
96 permutation of its blocks (i.e. ordered from greatest to
97 smallest), arranges them into the lexicographically least
98 permutation (i.e. ordered from smallest to largest) and
101 next_permutation (int *values, size_t cnt)
109 if (values[i] < values[i + 1])
112 for (j = cnt - 1; values[i] >= values[j]; j--)
114 swap (values + i, values + j);
115 reverse (values + (i + 1), cnt - (i + 1));
120 reverse (values, cnt);
128 factorial (unsigned int n)
130 unsigned int value = 1;
131 /* Disallow N values that overflow on 32-bit machines. */
138 /* Tests whether PARTS is a K-part integer composition of N.
139 Returns true if so, false otherwise. */
141 is_k_composition (int n, int k, const int parts[])
147 for (i = 0; i < k; i++)
149 if (parts[i] < 1 || parts[i] > n)
156 /* Advances the K-part integer composition of N stored in PARTS
157 to the next lexicographically greater one.
158 Returns true if successful, false if the composition was
159 already the greatest K-part composition of N (in which case
160 PARTS is unaltered). */
162 next_k_composition (int n UNUSED, int k, int parts[])
166 assert (is_k_composition (n, k, parts));
170 for (i = k - 1; i > 0; i--)
181 assert (is_k_composition (n, k, parts));
185 /* Sets the K integers in PARTS to the lexicographically first
186 K-part composition of N. */
188 first_k_composition (int n, int k, int parts[])
194 for (i = 0; i < k; i++)
196 parts[k - 1] += n - k;
199 /* Advances *K and PARTS to the next integer composition of N.
200 Compositions are ordered from shortest to longest and in
201 lexicographical order within a given length.
202 Before the first call, initialize *K to 0.
203 After each successful call, *K contains the length of the
204 current composition and the *K blocks in PARTS contain its
206 Returns true if successful, false if the set of compositions
207 has been exhausted. */
209 next_composition (int n, int *k, int parts[])
211 if (*k >= 1 && next_k_composition (n, *k, parts))
215 first_k_composition (n, ++*k, parts);
222 /* Test data element. */
225 struct range_map_node node; /* Embedded tower block. */
226 int x; /* Primary value. */
229 static struct element *
230 range_map_node_to_element (struct range_map_node *node)
232 return range_map_data (node, struct element, node);
235 /* Element we expect to find. */
236 struct expected_element
238 int x; /* Primary value. */
239 unsigned long int start; /* Start of region. */
240 unsigned long int end; /* End of region. */
243 /* Compares expected_element A and B and returns a strcmp()-type
246 compare_expected_element (const void *a_, const void *b_)
248 const struct expected_element *a = (const struct expected_element *) a_;
249 const struct expected_element *b = (const struct expected_element *) b_;
250 return a->start < b->start ? -1 : a->start > b->start;
253 /* Checks that RM contains the ELEM_CNT elements described by
256 check_range_map (struct range_map *rm,
257 struct expected_element elements[], size_t elem_cnt)
259 struct expected_element *sorted;
260 struct range_map_node *node;
263 sorted = xnmalloc (elem_cnt, sizeof *sorted);
264 memcpy (sorted, elements, elem_cnt * sizeof *elements);
265 qsort (sorted, elem_cnt, sizeof *sorted, compare_expected_element);
267 check (range_map_is_empty (rm) == (elem_cnt == 0));
269 for (i = 0; i < elem_cnt; i++)
271 struct expected_element *e = &sorted[i];
272 unsigned long int position;
274 /* Check that range_map_lookup finds all the positions
275 within the element. */
276 for (position = e->start; position < e->end; position++)
278 struct range_map_node *found = range_map_lookup (rm, position);
279 check (found != NULL);
280 check (range_map_node_to_element (found)->x == e->x);
281 check (range_map_node_get_start (found) == e->start);
282 check (range_map_node_get_end (found) == e->end);
283 check (range_map_node_get_width (found) == e->end - e->start);
286 /* If there shouldn't be any elements in the positions just
287 before or after the element, verify that
288 range_map_lookup doesn't find any there. */
289 if (e->start > 0 && (i == 0 || e[-1].end < e->start))
290 check (range_map_lookup (rm, e->start - 1) == NULL);
291 if (i == elem_cnt - 1 || e->end < e[1].start)
292 check (range_map_lookup (rm, e->end) == NULL);
295 for (node = (rand () % 2 ? range_map_first (rm) : range_map_next (rm, NULL)),
298 node = range_map_next (rm, node), i++)
300 struct expected_element *e = &sorted[i];
301 check (range_map_node_to_element (node)->x == e->x);
303 check (i == elem_cnt);
308 /* Tests inserting all possible sets of ranges into a range map
309 in all possible orders, up to a specified maximum overall
314 const int max_range = 7;
317 for (cnt = 1; cnt <= max_range; cnt++)
319 unsigned int composition_cnt;
320 struct expected_element *expected;
324 struct element *elements;
326 expected = xnmalloc (cnt, sizeof *expected);
327 widths = xnmalloc (cnt, sizeof *widths);
328 order = xnmalloc (cnt, sizeof *order);
329 elements = xnmalloc (cnt, sizeof *elements);
333 while (next_composition (cnt, &elem_cnt, widths))
336 unsigned int permutation_cnt;
338 for (i = 0; i < elem_cnt; i++)
342 while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
346 /* Inserts the elem_cnt elements with the given
347 widths[] into T in the order given by order[]. */
348 range_map_init (&rm);
349 for (i = 0; i < elem_cnt; i++)
351 unsigned long int start, end;
355 elements[idx].x = idx;
357 /* Find start and end of element. */
359 for (j = 0; j < idx; j++)
361 end = start + widths[j];
364 range_map_insert (&rm, start, end - start,
365 &elements[idx].node);
367 /* Check map contents. */
369 expected[i].start = start;
370 expected[i].end = end;
371 check_range_map (&rm, expected, i + 1);
375 check (permutation_cnt == factorial (elem_cnt));
379 check (composition_cnt == 1 << (cnt - 1));
388 /* Tests deleting ranges from a range map in all possible orders,
389 up to a specified maximum overall range. */
391 test_delete (int gap)
393 const int max_range = 7;
396 for (cnt = 1; cnt <= max_range; cnt++)
398 unsigned int composition_cnt;
399 struct expected_element *expected;
403 struct element *elements;
405 expected = xnmalloc (cnt, sizeof *expected);
406 widths = xnmalloc (cnt, sizeof *widths);
407 order = xnmalloc (cnt, sizeof *order);
408 elements = xnmalloc (cnt, sizeof *elements);
412 while (next_composition (cnt, &elem_cnt, widths))
415 unsigned int permutation_cnt;
417 for (i = 0; i < elem_cnt; i++)
421 while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
424 unsigned long int start;
426 /* Insert all the elements. */
427 range_map_init (&rm);
429 for (i = 0; i < elem_cnt; i++)
431 int width = widths[i] > gap ? widths[i] - gap : widths[i];
432 unsigned long int end = start + width;
435 range_map_insert (&rm, start, end - start,
440 assert (j < elem_cnt);
444 expected[j].start = start;
445 expected[j].end = end;
452 check_range_map (&rm, expected, elem_cnt);
454 /* Delete the elements in the specified order. */
455 for (i = 0; i < elem_cnt; i++)
457 range_map_delete (&rm, &elements[order[i]].node);
458 check_range_map (&rm, expected + i + 1, elem_cnt - i - 1);
463 check (permutation_cnt == factorial (elem_cnt));
467 check (composition_cnt == 1 << (cnt - 1));
476 /* Tests deleting ranges from a range map filled with contiguous
477 ranges in all possible orders, up to a specified maximum
480 test_delete_contiguous (void)
485 /* Tests deleting ranges from a range map filled with ranges
486 sometimes separated by gaps in all possible orders, up to a
487 specified maximum overall range. */
489 test_delete_gaps (void)
496 /* Runs TEST_FUNCTION and prints a message about NAME. */
498 run_test (void (*test_function) (void), const char *name)
509 run_test (test_insert, "insert");
510 run_test (test_delete_contiguous, "delete from contiguous ranges");
511 run_test (test_delete_gaps, "delete from ranges separated by gaps");