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-tower.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-tower.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-tower.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 #include "gl/minmax.h"
42 #include "gl/xalloc.h"
43
44 /* Exit with a failure code.
45 (Place a breakpoint on this function while debugging.) */
46 static void
check_die(void)47 check_die (void)
48 {
49 abort ();
50 }
51
52 /* If OK is not true, prints a message about failure on the
53 current source file and the given LINE and terminates. */
54 static void
check_func(bool ok,int line)55 check_func (bool ok, int line)
56 {
57 if (!ok)
58 {
59 fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
60 check_die ();
61 }
62 }
63
64 /* Verifies that EXPR evaluates to true.
65 If not, prints a message citing the calling line number and
66 terminates. */
67 #define check(EXPR) check_func ((EXPR), __LINE__)
68
69 /* A contiguous region. */
70 struct region
71 {
72 unsigned long int start; /* Start of region. */
73 unsigned long int end; /* One past the end. */
74 };
75
76 /* Number of bits in an unsigned int. */
77 #define UINT_BIT (CHAR_BIT * sizeof (unsigned int))
78
79 /* Returns the number of contiguous 1-bits in X starting from bit
80 0.
81 This implementation is designed to be obviously correct, not
82 to be efficient. */
83 static int
count_one_bits(unsigned long int x)84 count_one_bits (unsigned long int x)
85 {
86 int count = 0;
87 while (x & 1)
88 {
89 count++;
90 x >>= 1;
91 }
92 return count;
93 }
94
95 /* Searches the bits in PATTERN from right to left starting from
96 bit OFFSET for one or more 1-bits. If any are found, sets
97 *START to the bit index of the first and *WIDTH to the number
98 of contiguous 1-bits and returns true. Otherwise, returns
99 false.
100 This implementation is designed to be obviously correct, not
101 to be efficient. */
102 static bool
next_region(unsigned int pattern,unsigned int offset,unsigned long int * start,unsigned long int * width)103 next_region (unsigned int pattern, unsigned int offset,
104 unsigned long int *start, unsigned long int *width)
105 {
106 unsigned int i;
107
108 assert (offset <= UINT_BIT);
109 for (i = offset; i < UINT_BIT; i++)
110 if (pattern & (1u << i))
111 {
112 *start = i;
113 *width = count_one_bits (pattern >> i);
114 return true;
115 }
116 return false;
117 }
118
119 /* Searches the bits in PATTERN from left to right starting from
120 just beyond bit OFFSET for one or more 1-bits. If any are
121 found, sets *START to the bit index of the first and *WIDTH to
122 the number of contiguous 1-bits and returns true. Otherwise,
123 returns false.
124 This implementation is designed to be obviously correct, not
125 to be efficient. */
126 static bool
prev_region(unsigned int pattern,unsigned int offset,unsigned long int * start,unsigned long int * width)127 prev_region (unsigned int pattern, unsigned int offset,
128 unsigned long int *start, unsigned long int *width)
129 {
130 unsigned int i;
131
132 assert (offset <= UINT_BIT);
133 for (i = offset; i-- > 0;)
134 if (pattern & (1u << i))
135 {
136 *start = i;
137 *width = 1;
138 while (i-- > 0 && pattern & (1u << i))
139 {
140 ++*width;
141 --*start;
142 }
143 return true;
144 }
145 return false;
146 }
147
148 /* Searches the bits in PATTERN from right to left starting from
149 bit OFFSET. Returns the bit index of the first 1-bit found,
150 or ULONG_MAX if none is found. */
151 static unsigned long int
next_1bit(unsigned int pattern,unsigned int offset,unsigned long int pattern_offset)152 next_1bit (unsigned int pattern, unsigned int offset,
153 unsigned long int pattern_offset)
154 {
155 for (; offset < UINT_BIT; offset++)
156 if (pattern & (1u << offset))
157 return offset + pattern_offset;
158 return ULONG_MAX;
159 }
160
161 static void
print_structure(const struct abt_node * node_)162 print_structure (const struct abt_node *node_)
163 {
164 struct range_tower_node *node;
165
166 if (node_ == NULL)
167 return;
168 node = ABT_DATA (node_, struct range_tower_node, abt_node);
169 printf ("%lu+%lu/%d", node->n_zeros, node->n_ones, node->abt_node.level);
170 if (node->abt_node.down[0] || node->abt_node.down[1])
171 {
172 printf ("(");
173 print_structure (node->abt_node.down[0]);
174 printf (",");
175 print_structure (node->abt_node.down[1]);
176 printf (")");
177 }
178 }
179
180 /* Prints the regions in RT to stdout. */
181 static void UNUSED
print_regions(const struct range_tower * rt)182 print_regions (const struct range_tower *rt)
183 {
184 const struct range_tower_node *node;
185
186 printf ("contents:");
187 for (node = range_tower_first__ (rt); node != NULL;
188 node = range_tower_next__ (rt, node))
189 printf (" (%lu,%lu)", node->n_zeros, node->n_ones);
190 printf ("\n");
191 printf ("structure:");
192 print_structure (rt->abt.root);
193 printf ("\n");
194 }
195
196 static void
check_tree(const struct abt_node * abt_node,unsigned long int * subtree_width)197 check_tree (const struct abt_node *abt_node, unsigned long int *subtree_width)
198 {
199 const struct range_tower_node *node = range_tower_node_from_abt__ (abt_node);
200 unsigned long int left_width, right_width;
201
202 if (node == NULL)
203 {
204 *subtree_width = 0;
205 return;
206 }
207
208 check_tree (node->abt_node.down[0], &left_width);
209 check_tree (node->abt_node.down[1], &right_width);
210
211 *subtree_width = node->n_zeros + node->n_ones + left_width + right_width;
212 check (node->subtree_width == *subtree_width);
213 }
214
215 /* Checks that the regions in RT match the bits in PATTERN. */
216 static void
check_pattern(const struct range_tower * rt,unsigned int pattern,unsigned long int offset)217 check_pattern (const struct range_tower *rt, unsigned int pattern,
218 unsigned long int offset)
219 {
220 const struct range_tower_node *node;
221 unsigned long int start, start2, width;
222 unsigned long int tree_width;
223 unsigned long int s1, s2;
224 int i;
225
226 check_tree (rt->abt.root, &tree_width);
227 check (tree_width == ULONG_MAX);
228
229 if (offset > ULONG_MAX - 32)
230 {
231 pattern <<= offset - (ULONG_MAX - 32);
232 offset = ULONG_MAX - 32;
233 }
234
235 for (node = rand () % 2 ? range_tower_first (rt) : range_tower_next (rt, NULL),
236 start = width = 0;
237 next_region (pattern, start + width, &start, &width);
238 node = range_tower_next (rt, node))
239 {
240 unsigned long int node_start;
241 unsigned long int x;
242
243 check (node != NULL);
244 check (range_tower_node_get_start (node) == start + offset);
245 check (range_tower_node_get_end (node) == start + offset + width);
246 check (range_tower_node_get_width (node) == width);
247
248 x = start + offset - node->n_zeros;
249 check (range_tower_lookup (rt, x, &node_start) == node);
250 check (node_start == start + offset - node->n_zeros);
251
252 x = start + offset + width - 1;
253 check (range_tower_lookup (rt, x, &node_start) == node);
254 check (node_start == start + offset - node->n_zeros);
255 }
256 check (node == NULL);
257
258 start = width = 0;
259 RANGE_TOWER_FOR_EACH (node, start2, rt)
260 {
261 check (next_region (pattern, start + width, &start, &width));
262 check (start + offset == start2);
263 check (range_tower_node_get_width (node) == width);
264 }
265 check (!next_region (pattern, start + width, &start, &width));
266
267 for (node = rand () % 2 ? range_tower_last (rt) : range_tower_prev (rt, NULL),
268 start = UINT_BIT;
269 prev_region (pattern, start, &start, &width);
270 node = range_tower_prev (rt, node))
271 {
272 check (node != NULL);
273 check (range_tower_node_get_start (node) == offset + start);
274 check (range_tower_node_get_end (node) == offset + start + width);
275 check (range_tower_node_get_width (node) == width);
276 }
277 check (node == NULL);
278
279 /* Scan from all possible positions, resetting the cache each
280 time, to ensure that we get the correct answers without
281 caching. */
282 for (start = 0; start <= 32; start++)
283 {
284 struct range_tower *nonconst_rt = CONST_CAST (struct range_tower *, rt);
285
286 nonconst_rt->cache_end = 0;
287 s1 = range_tower_scan (rt, offset + start);
288 s2 = next_1bit (pattern, start, offset);
289 check (s1 == s2);
290 }
291
292 /* Scan in forward order to exercise expected cache behavior. */
293 for (s1 = range_tower_scan (rt, 0), s2 = next_1bit (pattern, 0, offset); ;
294 s1 = range_tower_scan (rt, s1 + 1), s2 = next_1bit (pattern, (s2 - offset) + 1, offset))
295 {
296 check (s1 == s2);
297 if (s1 == ULONG_MAX)
298 break;
299 }
300
301 /* Scan in random order to frustrate cache. */
302 for (i = 0; i < 32; i++)
303 {
304 start = rand () % 32;
305 s1 = range_tower_scan (rt, start + offset);
306 s2 = next_1bit (pattern, start, offset);
307 check (s1 == s2);
308 }
309
310 /* Test range_tower_scan() with negative cache. */
311 check (!range_tower_contains (rt, 999));
312 if (offset < 1111)
313 check (range_tower_scan (rt, 1111) == ULONG_MAX);
314
315 /* Check for containment without caching. */
316 for (i = 0; i < UINT_BIT; i++)
317 {
318 struct range_tower *nonconst_rt = CONST_CAST (struct range_tower *, rt);
319 nonconst_rt->cache_end = 0;
320 check (range_tower_contains (rt, i + offset)
321 == ((pattern & (1u << i)) != 0));
322 }
323
324 /* Check for containment with caching. */
325 for (i = 0; i < UINT_BIT; i++)
326 check (range_tower_contains (rt, i + offset)
327 == ((pattern & (1u << i)) != 0));
328
329 check (!range_tower_contains (rt,
330 UINT_BIT + rand () % (ULONG_MAX - UINT_BIT * 2)));
331
332 check (range_tower_is_empty (rt) == (pattern == 0));
333 }
334
335 /* Creates and returns a range tower that contains regions for the
336 bits tower in PATTERN. */
337 static struct range_tower *
make_pattern(unsigned int pattern,unsigned long int offset)338 make_pattern (unsigned int pattern, unsigned long int offset)
339 {
340 unsigned long int start = 0;
341 unsigned long int width = 0;
342 struct range_tower *rt = range_tower_create_pool (NULL);
343 while (next_region (pattern, start + width, &start, &width))
344 range_tower_set1 (rt, start + offset, width);
345 check_pattern (rt, pattern, offset);
346 return rt;
347 }
348
349 /* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
350 tower to 1, other bits tower to 0. */
351 static unsigned int
bit_range(unsigned int ofs,unsigned int cnt)352 bit_range (unsigned int ofs, unsigned int cnt)
353 {
354 assert (ofs < UINT_BIT);
355 assert (cnt <= UINT_BIT);
356 assert (ofs + cnt <= UINT_BIT);
357
358 return cnt < UINT_BIT ? ((1u << cnt) - 1) << ofs : UINT_MAX;
359 }
360
361 /* Tests setting all possible ranges of 1s into all possible range sets (up to
362 a small maximum number of bits). */
363 static void
test_set1(void)364 test_set1 (void)
365 {
366 const int positions = 9;
367 unsigned int init_pat;
368 int start, width;
369 int k;
370
371 for (k = 0; k < 2; k++)
372 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
373 for (start = 0; start < positions; start++)
374 for (width = 0; width + start <= positions; width++)
375 {
376 unsigned long int offset = k ? ULONG_MAX - positions : 0;
377 struct range_tower *rt, *rt2;
378 unsigned int final_pat;
379
380 rt = make_pattern (init_pat, offset);
381 range_tower_set1 (rt, offset + start, width);
382 final_pat = init_pat | bit_range (start, width);
383 check_pattern (rt, final_pat, offset);
384 rt2 = range_tower_clone (rt, NULL);
385 check_pattern (rt2, final_pat, offset);
386 range_tower_destroy (rt);
387 range_tower_destroy (rt2);
388 }
389 }
390
391 /* Tests setting all possible ranges of 0s into all possible range sets (up to
392 a small maximum number of bits). */
393 static void
test_set0(void)394 test_set0 (void)
395 {
396 const int positions = 9;
397 unsigned int init_pat;
398 int start, width, k;
399
400 for (k = 0; k < 2; k++)
401 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
402 for (start = 0; start < positions; start++)
403 for (width = 0; start + width <= positions; width++)
404 {
405 unsigned long int offset = k ? ULONG_MAX - positions : 0;
406 struct range_tower *rt;
407 unsigned int final_pat;
408
409 rt = make_pattern (init_pat, offset);
410 range_tower_set0 (rt, offset + start, width);
411 final_pat = init_pat & ~bit_range (start, width);
412 check_pattern (rt, final_pat, offset);
413 range_tower_destroy (rt);
414 }
415 }
416
417 /* Tests inserting all possible ranges of 0s into all possible range sets (up
418 to a small maximum number of bits). */
419 static void
test_insert0(void)420 test_insert0 (void)
421 {
422 const int positions = 9;
423 unsigned int init_pat;
424 int start, width, k;
425
426 for (k = 0; k < 2; k++)
427 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
428 for (start = 0; start < positions; start++)
429 for (width = 0; start + width <= positions; width++)
430 {
431 unsigned long int offset = k ? ULONG_MAX - positions : 0;
432 struct range_tower *rt;
433 unsigned int final_pat;
434
435 rt = make_pattern (init_pat, offset);
436 range_tower_insert0 (rt, offset + start, width);
437 final_pat = init_pat & bit_range (0, start);
438 final_pat |= (init_pat & bit_range (start, positions - start)) << width;
439 check_pattern (rt, final_pat, offset);
440 range_tower_destroy (rt);
441 }
442 }
443
444 /* Tests inserting all possible ranges of 1s into all possible range sets (up
445 to a small maximum number of bits). */
446 static void
test_insert1(void)447 test_insert1 (void)
448 {
449 const int positions = 9;
450 unsigned int init_pat;
451 int start, width, k;
452
453 for (k = 0; k < 2; k++)
454 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
455 for (start = 0; start < positions; start++)
456 for (width = 0; start + width <= positions; width++)
457 {
458 struct range_tower *rt;
459 unsigned int final_pat;
460
461 rt = make_pattern (init_pat, 0);
462 range_tower_insert1 (rt, start, width);
463 final_pat = init_pat & bit_range (0, start);
464 final_pat |= bit_range (start, width);
465 final_pat |= (init_pat & bit_range (start, positions - start)) << width;
466 check_pattern (rt, final_pat, 0);
467 range_tower_destroy (rt);
468 }
469 }
470
471 /* Tests setting all possible ranges from all possible range sets (up to a
472 small maximum number of bits). */
473 static void
test_delete(void)474 test_delete (void)
475 {
476 const int positions = 9;
477 unsigned int init_pat;
478 int start, width, k;
479
480 for (k = 0; k < 2; k++)
481 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
482 for (start = 0; start < positions; start++)
483 for (width = 0; start + width <= positions; width++)
484 {
485 unsigned long int offset = k ? ULONG_MAX - positions : 0;
486 struct range_tower *rt;
487 unsigned int final_pat;
488
489 rt = make_pattern (init_pat, offset);
490 range_tower_delete (rt, start + offset, width);
491 final_pat = init_pat & bit_range (0, start);
492 final_pat |= (init_pat & (UINT_MAX << (start + width))) >> width;
493 check_pattern (rt, final_pat, offset);
494 range_tower_destroy (rt);
495 }
496 }
497
498 /* Tests moving all possible ranges (up to a small maximum number of bits). */
499 static void
test_move(void)500 test_move (void)
501 {
502 const int positions = 9;
503 unsigned int init_pat;
504 int new_start, old_start, width, k;
505
506 for (k = 0; k < 2; k++)
507 for (init_pat = 0; init_pat < (1u << positions); init_pat++)
508 for (width = 0; width <= positions; width++)
509 for (new_start = 0; new_start + width <= positions; new_start++)
510 for (old_start = 0; old_start + width <= positions; old_start++)
511 {
512 unsigned long int offset = k ? ULONG_MAX - positions : 0;
513 struct range_tower *rt;
514 unsigned int final_pat;
515
516 if (new_start == old_start || width == 0)
517 final_pat = init_pat;
518 else if (new_start < old_start)
519 {
520 final_pat = init_pat & bit_range (0, new_start);
521 final_pat |= (init_pat & bit_range (old_start, width)) >> (old_start - new_start);
522 final_pat |= (init_pat & bit_range (new_start, old_start - new_start)) << width;
523 final_pat |= init_pat & bit_range (old_start + width, positions - (old_start + width));
524 }
525 else
526 {
527 final_pat = init_pat & bit_range (0, old_start);
528 final_pat |= (init_pat & bit_range (old_start + width, new_start - old_start)) >> width;
529 final_pat |= (init_pat & bit_range (old_start, width)) << (new_start - old_start);
530 final_pat |= init_pat & bit_range (new_start + width, positions - (new_start + width));
531 }
532
533 rt = make_pattern (init_pat, offset);
534 range_tower_move (rt, old_start + offset, new_start + offset,
535 width);
536 check_pattern (rt, final_pat, offset);
537 range_tower_destroy (rt);
538 }
539 }
540
541 /* Tests freeing a range tower through a pool. */
542 static void
test_pool(void)543 test_pool (void)
544 {
545 struct pool *pool;
546 struct range_tower *rt;
547
548 /* Destroy the range tower, then the pool.
549 Makes sure that this doesn't cause a double-free. */
550 pool = pool_create ();
551 rt = range_tower_create_pool (pool);
552 range_tower_set1 (rt, 1, 10);
553 range_tower_destroy (rt);
554 pool_destroy (pool);
555
556 /* Just destroy the pool.
557 Makes sure that this doesn't cause a leak. */
558 pool = pool_create ();
559 rt = range_tower_create_pool (pool);
560 range_tower_set1 (rt, 1, 10);
561 pool_destroy (pool);
562 }
563
564 /* Tests range_tower_destroy(NULL). */
565 static void
test_destroy_null(void)566 test_destroy_null (void)
567 {
568 range_tower_destroy (NULL);
569 }
570
571 /* Main program. */
572
573 struct test
574 {
575 const char *name;
576 const char *description;
577 void (*function) (void);
578 };
579
580 static const struct test tests[] =
581 {
582 {
583 "set1",
584 "set1",
585 test_set1
586 },
587 {
588 "set0",
589 "set0",
590 test_set0
591 },
592 {
593 "insert0",
594 "insert0",
595 test_insert0
596 },
597 {
598 "insert1",
599 "insert1",
600 test_insert1
601 },
602 {
603 "delete",
604 "delete",
605 test_delete
606 },
607 {
608 "move",
609 "move",
610 test_move
611 },
612 {
613 "pool",
614 "pool",
615 test_pool
616 },
617 {
618 "destroy-null",
619 "destroy null",
620 test_destroy_null
621 },
622 };
623
624 enum { N_TESTS = sizeof tests / sizeof *tests };
625
626 int
main(int argc,char * argv[])627 main (int argc, char *argv[])
628 {
629 int i;
630
631 if (argc != 2)
632 {
633 fprintf (stderr, "exactly one argument required; use --help for help\n");
634 return EXIT_FAILURE;
635 }
636 else if (!strcmp (argv[1], "--help"))
637 {
638 printf ("%s: test range tower library\n"
639 "usage: %s TEST-NAME\n"
640 "where TEST-NAME is one of the following:\n",
641 argv[0], argv[0]);
642 for (i = 0; i < N_TESTS; i++)
643 printf (" %s\n %s\n", tests[i].name, tests[i].description);
644 return 0;
645 }
646 else
647 {
648 for (i = 0; i < N_TESTS; i++)
649 if (!strcmp (argv[1], tests[i].name))
650 {
651 tests[i].function ();
652 return 0;
653 }
654
655 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
656 return EXIT_FAILURE;
657 }
658 }
659