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
42 /* Exit with a failure code.
43 (Place a breakpoint on this function while debugging.) */
44 static void
check_die(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
check_func(bool ok,int line)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
67 /* Swaps *A and *B. */
68 static void
swap(int * a,int * b)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
reverse(int * values,size_t cnt)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
next_permutation(int * values,size_t cnt)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
factorial(unsigned int n)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
is_k_composition(int n,int k,const int parts[])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
next_k_composition(int n UNUSED,int k,int parts[])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
first_k_composition(int n,int k,int parts[])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
next_composition(int n,int * k,int parts[])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
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 *
range_map_node_to_element(struct range_map_node * node)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
compare_expected_element(const void * a_,const void * b_)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
check_range_map(struct range_map * rm,struct expected_element elements[],size_t elem_cnt)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
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
test_insert(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
test_delete(int gap)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
test_delete_contiguous(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
test_delete_gaps(void)483 test_delete_gaps (void)
484 {
485 test_delete (1);
486 }
487
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
main(int argc,char * argv[])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 }
551