1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009, 2010, 2011, 2012 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-set.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-set.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-set.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 #include <libpspp/pool.h>
40
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 /* A contiguous region. */
68 struct region
69 {
70 unsigned long int start; /* Start of region. */
71 unsigned long int end; /* One past the end. */
72 };
73
74 /* Number of bits in an unsigned int. */
75 #define UINT_BIT (CHAR_BIT * sizeof (unsigned int))
76
77 /* Returns the number of contiguous 1-bits in X starting from bit
78 0.
79 This implementation is designed to be obviously correct, not
80 to be efficient. */
81 static int
count_one_bits(unsigned long int x)82 count_one_bits (unsigned long int x)
83 {
84 int count = 0;
85 while (x & 1)
86 {
87 count++;
88 x >>= 1;
89 }
90 return count;
91 }
92
93 /* Searches the bits in PATTERN from right to left starting from
94 bit OFFSET for one or more 1-bits. If any are found, sets
95 *START to the bit index of the first and *WIDTH to the number
96 of contiguous 1-bits and returns true. Otherwise, returns
97 false.
98 This implementation is designed to be obviously correct, not
99 to be efficient. */
100 static bool
next_region(unsigned int pattern,unsigned int offset,unsigned long int * start,unsigned long int * width)101 next_region (unsigned int pattern, unsigned int offset,
102 unsigned long int *start, unsigned long int *width)
103 {
104 unsigned int i;
105
106 assert (offset <= UINT_BIT);
107 for (i = offset; i < UINT_BIT; i++)
108 if (pattern & (1u << i))
109 {
110 *start = i;
111 *width = count_one_bits (pattern >> i);
112 return true;
113 }
114 return false;
115 }
116
117 /* Searches the bits in PATTERN from left to right starting from
118 just beyond bit OFFSET for one or more 1-bits. If any are
119 found, sets *START to the bit index of the first and *WIDTH to
120 the number of contiguous 1-bits and returns true. Otherwise,
121 returns false.
122 This implementation is designed to be obviously correct, not
123 to be efficient. */
124 static bool
prev_region(unsigned int pattern,unsigned int offset,unsigned long int * start,unsigned long int * width)125 prev_region (unsigned int pattern, unsigned int offset,
126 unsigned long int *start, unsigned long int *width)
127 {
128 unsigned int i;
129
130 assert (offset <= UINT_BIT);
131 for (i = offset; i-- > 0;)
132 if (pattern & (1u << i))
133 {
134 *start = i;
135 *width = 1;
136 while (i-- > 0 && pattern & (1u << i))
137 {
138 ++*width;
139 --*start;
140 }
141 return true;
142 }
143 return false;
144 }
145
146 /* Searches the bits in PATTERN from right to left starting from
147 bit OFFSET. Returns the bit index of the first 1-bit found,
148 or ULONG_MAX if none is found. */
149 static unsigned long int
next_1bit(unsigned int pattern,unsigned int offset)150 next_1bit (unsigned int pattern, unsigned int offset)
151 {
152 for (; offset < UINT_BIT; offset++)
153 if (pattern & (1u << offset))
154 return offset;
155 return ULONG_MAX;
156 }
157
158 /* Prints the regions in RS to stdout. */
159 static void UNUSED
print_regions(const struct range_set * rs)160 print_regions (const struct range_set *rs)
161 {
162 const struct range_set_node *node;
163
164 printf ("result:");
165 RANGE_SET_FOR_EACH (node, rs)
166 printf (" (%lu,%lu)",
167 range_set_node_get_start (node), range_set_node_get_end (node));
168 printf ("\n");
169 }
170
171 /* Checks that the regions in RS match the bits in PATTERN. */
172 static void
check_pattern(const struct range_set * rs,unsigned int pattern)173 check_pattern (const struct range_set *rs, unsigned int pattern)
174 {
175 const struct range_set_node *node;
176 unsigned long int start, width;
177 unsigned long int s1, s2;
178 int i;
179
180 for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL),
181 start = width = 0;
182 next_region (pattern, start + width, &start, &width);
183 node = range_set_next (rs, node))
184 {
185 check (node != NULL);
186 check (range_set_node_get_start (node) == start);
187 check (range_set_node_get_end (node) == start + width);
188 check (range_set_node_get_width (node) == width);
189 }
190 check (node == NULL);
191
192 for (node = rand () % 2 ? range_set_last (rs) : range_set_prev (rs, NULL),
193 start = UINT_BIT;
194 prev_region (pattern, start, &start, &width);
195 node = range_set_prev (rs, node))
196 {
197 check (node != NULL);
198 check (range_set_node_get_start (node) == start);
199 check (range_set_node_get_end (node) == start + width);
200 check (range_set_node_get_width (node) == width);
201 }
202 check (node == NULL);
203
204 /* Scan from all possible positions, resetting the cache each
205 time, to ensure that we get the correct answers without
206 caching. */
207 for (start = 0; start <= 32; start++)
208 {
209 struct range_set *nonconst_rs = CONST_CAST (struct range_set *, rs);
210 nonconst_rs->cache_end = 0;
211 s1 = range_set_scan (rs, start);
212 s2 = next_1bit (pattern, start);
213 check (s1 == s2);
214 }
215
216 /* Scan in forward order to exercise expected cache behavior. */
217 for (s1 = range_set_scan (rs, 0), s2 = next_1bit (pattern, 0); ;
218 s1 = range_set_scan (rs, s1 + 1), s2 = next_1bit (pattern, s2 + 1))
219 {
220 check (s1 == s2);
221 if (s1 == ULONG_MAX)
222 break;
223 }
224
225 /* Scan in random order to frustrate cache. */
226 for (i = 0; i < 32; i++)
227 {
228 start = rand () % 32;
229 s1 = range_set_scan (rs, start);
230 s2 = next_1bit (pattern, start);
231 check (s1 == s2);
232 }
233
234 /* Test range_set_scan() with negative cache. */
235 check (!range_set_contains (rs, 999));
236 check (range_set_scan (rs, 1111) == ULONG_MAX);
237
238 for (i = 0; i < UINT_BIT; i++)
239 check (range_set_contains (rs, i) == ((pattern & (1u << i)) != 0));
240 check (!range_set_contains (rs,
241 UINT_BIT + rand () % (ULONG_MAX - UINT_BIT)));
242
243 check (range_set_is_empty (rs) == (pattern == 0));
244 }
245
246 /* Creates and returns a range set that contains regions for the
247 bits set in PATTERN. */
248 static struct range_set *
make_pattern(unsigned int pattern)249 make_pattern (unsigned int pattern)
250 {
251 unsigned long int start = 0;
252 unsigned long int width = 0;
253 struct range_set *rs = range_set_create_pool (NULL);
254 while (next_region (pattern, start + width, &start, &width))
255 range_set_set1 (rs, start, width);
256 check_pattern (rs, pattern);
257 return rs;
258 }
259
260 /* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
261 set to 1, other bits set to 0. */
262 static unsigned int
bit_range(unsigned int ofs,unsigned int cnt)263 bit_range (unsigned int ofs, unsigned int cnt)
264 {
265 assert (ofs < UINT_BIT);
266 assert (cnt <= UINT_BIT);
267 assert (ofs + cnt <= UINT_BIT);
268
269 return cnt < UINT_BIT ? ((1u << cnt) - 1) << ofs : UINT_MAX;
270 }
271
272 /* Tests inserting all possible patterns into all possible range
273 sets (up to a small maximum number of bits). */
274 static void
test_insert(void)275 test_insert (void)
276 {
277 const int positions = 9;
278 unsigned int init_pat;
279 int i, j;
280
281 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
282 for (i = 0; i < positions + 1; i++)
283 for (j = i; j <= positions + 1; j++)
284 {
285 struct range_set *rs, *rs2;
286 unsigned int final_pat;
287
288 rs = make_pattern (init_pat);
289 range_set_set1 (rs, i, j - i);
290 final_pat = init_pat | bit_range (i, j - i);
291 check_pattern (rs, final_pat);
292 rs2 = range_set_clone (rs, NULL);
293 check_pattern (rs2, final_pat);
294 range_set_destroy (rs);
295 range_set_destroy (rs2);
296 }
297 }
298
299 /* Tests deleting all possible patterns from all possible range
300 sets (up to a small maximum number of bits). */
301 static void
test_delete(void)302 test_delete (void)
303 {
304 const int positions = 9;
305 unsigned int init_pat;
306 int i, j;
307
308 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
309 for (i = 0; i < positions + 1; i++)
310 for (j = i; j <= positions + 1; j++)
311 {
312 struct range_set *rs;
313 unsigned int final_pat;
314
315 rs = make_pattern (init_pat);
316 range_set_set0 (rs, i, j - i);
317 final_pat = init_pat & ~bit_range (i, j - i);
318 check_pattern (rs, final_pat);
319 range_set_destroy (rs);
320 }
321 }
322
323 /* Tests all possible allocation in all possible range sets (up
324 to a small maximum number of bits). */
325 static void
test_allocate(void)326 test_allocate (void)
327 {
328 const int positions = 9;
329 unsigned int init_pat;
330 int request;
331
332 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
333 for (request = 1; request <= positions + 1; request++)
334 {
335 struct range_set *rs;
336 unsigned long int start, width, expect_start, expect_width;
337 bool success, expect_success;
338 unsigned int final_pat;
339 int i;
340
341 /* Figure out expected results. */
342 expect_success = false;
343 expect_start = expect_width = 0;
344 final_pat = init_pat;
345 for (i = 0; i < positions; i++)
346 if (init_pat & (1u << i))
347 {
348 expect_success = true;
349 expect_start = i;
350 expect_width = count_one_bits (init_pat >> i);
351 if (expect_width > request)
352 expect_width = request;
353 final_pat &= ~bit_range (expect_start, expect_width);
354 break;
355 }
356
357 /* Test. */
358 rs = make_pattern (init_pat);
359 success = range_set_allocate (rs, request, &start, &width);
360 check_pattern (rs, final_pat);
361 range_set_destroy (rs);
362
363 /* Check results. */
364 check (success == expect_success);
365 if (expect_success)
366 {
367 check (start == expect_start);
368 check (width == expect_width);
369 }
370 }
371 }
372
373 /* Tests all possible full allocations in all possible range sets
374 (up to a small maximum number of bits). */
375 static void
test_allocate_fully(void)376 test_allocate_fully (void)
377 {
378 const int positions = 9;
379 unsigned int init_pat;
380 int request;
381
382 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
383 for (request = 1; request <= positions + 1; request++)
384 {
385 struct range_set *rs;
386 unsigned long int start, expect_start;
387 bool success, expect_success;
388 unsigned int final_pat;
389 int i;
390
391 /* Figure out expected results. */
392 expect_success = false;
393 expect_start = 0;
394 final_pat = init_pat;
395 for (i = 0; i < positions - request + 1; i++)
396 {
397 int j;
398
399 final_pat = init_pat;
400 for (j = i; j < i + request; j++)
401 {
402 if (!(init_pat & (1u << j)))
403 goto next;
404 final_pat &= ~(1u << j);
405 }
406
407 expect_success = true;
408 expect_start = i;
409 break;
410 next:
411 final_pat = init_pat;
412 }
413
414 /* Test. */
415 rs = make_pattern (init_pat);
416 success = range_set_allocate_fully (rs, request, &start);
417 check_pattern (rs, final_pat);
418 range_set_destroy (rs);
419
420 /* Check results. */
421 check (success == expect_success);
422 if (expect_success)
423 check (start == expect_start);
424 }
425 }
426
427 /* Tests freeing a range set through a pool. */
428 static void
test_pool(void)429 test_pool (void)
430 {
431 struct pool *pool;
432 struct range_set *rs;
433
434 /* Destroy the range set, then the pool.
435 Makes sure that this doesn't cause a double-free. */
436 pool = pool_create ();
437 rs = range_set_create_pool (pool);
438 range_set_set1 (rs, 1, 10);
439 range_set_destroy (rs);
440 pool_destroy (pool);
441
442 /* Just destroy the pool.
443 Makes sure that this doesn't cause a leak. */
444 pool = pool_create ();
445 rs = range_set_create_pool (pool);
446 range_set_set1 (rs, 1, 10);
447 pool_destroy (pool);
448 }
449
450 /* Tests range_set_destroy(NULL). */
451 static void
test_destroy_null(void)452 test_destroy_null (void)
453 {
454 range_set_destroy (NULL);
455 }
456
457 /* Main program. */
458
459 struct test
460 {
461 const char *name;
462 const char *description;
463 void (*function) (void);
464 };
465
466 static const struct test tests[] =
467 {
468 {
469 "insert",
470 "insert",
471 test_insert
472 },
473 {
474 "delete",
475 "delete",
476 test_delete
477 },
478 {
479 "allocate",
480 "allocate",
481 test_allocate
482 },
483 {
484 "allocate-fully",
485 "allocate_fully",
486 test_allocate_fully
487 },
488 {
489 "pool",
490 "pool",
491 test_pool
492 },
493 {
494 "destroy-null",
495 "destroy null",
496 test_destroy_null
497 },
498 };
499
500 enum { N_TESTS = sizeof tests / sizeof *tests };
501
502 int
main(int argc,char * argv[])503 main (int argc, char *argv[])
504 {
505 int i;
506
507 if (argc != 2)
508 {
509 fprintf (stderr, "exactly one argument required; use --help for help\n");
510 return EXIT_FAILURE;
511 }
512 else if (!strcmp (argv[1], "--help"))
513 {
514 printf ("%s: test range set library\n"
515 "usage: %s TEST-NAME\n"
516 "where TEST-NAME is one of the following:\n",
517 argv[0], argv[0]);
518 for (i = 0; i < N_TESTS; i++)
519 printf (" %s\n %s\n", tests[i].name, tests[i].description);
520 return 0;
521 }
522 else
523 {
524 for (i = 0; i < N_TESTS; i++)
525 if (!strcmp (argv[1], tests[i].name))
526 {
527 tests[i].function ();
528 return 0;
529 }
530
531 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
532 return EXIT_FAILURE;
533 }
534 }
535