message: Make msg_emit() take full ownership of its argument.
[pspp] / tests / libpspp / range-tower-test.c
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 \f
44 /* Exit with a failure code.
45    (Place a breakpoint on this function while debugging.) */
46 static 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
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 \f
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
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
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
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
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
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
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
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
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 *
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
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 \f
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
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
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
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
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
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
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
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
566 test_destroy_null (void)
567 {
568   range_tower_destroy (NULL);
569 }
570 \f
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
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 }