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