--- /dev/null
+/* PSPP - a program for statistical analysis.
+ Copyright (C) 2007, 2009, 2010, 2011 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+/* This is a test program for the routines defined in
+ range-tower.c. This test program aims to be as comprehensive as
+ possible. With -DNDEBUG, "gcov -b" should report 100%
+ coverage of lines and branches in range-tower.c routines.
+ (Without -DNDEBUG, branches caused by failed assertions will
+ not be taken.) "valgrind --leak-check=yes
+ --show-reachable=yes" should give a clean report, both with
+ and without -DNDEBUG. */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include "libpspp/range-tower.h"
+
+#include <assert.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "libpspp/compiler.h"
+#include "libpspp/pool.h"
+
+#include "gl/minmax.h"
+#include "gl/xalloc.h"
+\f
+/* Exit with a failure code.
+ (Place a breakpoint on this function while debugging.) */
+static void
+check_die (void)
+{
+ abort ();
+}
+
+/* If OK is not true, prints a message about failure on the
+ current source file and the given LINE and terminates. */
+static void
+check_func (bool ok, int line)
+{
+ if (!ok)
+ {
+ fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
+ check_die ();
+ }
+}
+
+/* Verifies that EXPR evaluates to true.
+ If not, prints a message citing the calling line number and
+ terminates. */
+#define check(EXPR) check_func ((EXPR), __LINE__)
+\f
+/* A contiguous region. */
+struct region
+ {
+ unsigned long int start; /* Start of region. */
+ unsigned long int end; /* One past the end. */
+ };
+
+/* Number of bits in an unsigned int. */
+#define UINT_BIT (CHAR_BIT * sizeof (unsigned int))
+
+/* Returns the number of contiguous 1-bits in X starting from bit
+ 0.
+ This implementation is designed to be obviously correct, not
+ to be efficient. */
+static int
+count_one_bits (unsigned long int x)
+{
+ int count = 0;
+ while (x & 1)
+ {
+ count++;
+ x >>= 1;
+ }
+ return count;
+}
+
+/* Searches the bits in PATTERN from right to left starting from
+ bit OFFSET for one or more 1-bits. If any are found, sets
+ *START to the bit index of the first and *WIDTH to the number
+ of contiguous 1-bits and returns true. Otherwise, returns
+ false.
+ This implementation is designed to be obviously correct, not
+ to be efficient. */
+static bool
+next_region (unsigned int pattern, unsigned int offset,
+ unsigned long int *start, unsigned long int *width)
+{
+ unsigned int i;
+
+ assert (offset <= UINT_BIT);
+ for (i = offset; i < UINT_BIT; i++)
+ if (pattern & (1u << i))
+ {
+ *start = i;
+ *width = count_one_bits (pattern >> i);
+ return true;
+ }
+ return false;
+}
+
+/* Searches the bits in PATTERN from left to right starting from
+ just beyond bit OFFSET for one or more 1-bits. If any are
+ found, sets *START to the bit index of the first and *WIDTH to
+ the number of contiguous 1-bits and returns true. Otherwise,
+ returns false.
+ This implementation is designed to be obviously correct, not
+ to be efficient. */
+static bool
+prev_region (unsigned int pattern, unsigned int offset,
+ unsigned long int *start, unsigned long int *width)
+{
+ unsigned int i;
+
+ assert (offset <= UINT_BIT);
+ for (i = offset; i-- > 0; )
+ if (pattern & (1u << i))
+ {
+ *start = i;
+ *width = 1;
+ while (i-- > 0 && pattern & (1u << i))
+ {
+ ++*width;
+ --*start;
+ }
+ return true;
+ }
+ return false;
+}
+
+/* Searches the bits in PATTERN from right to left starting from
+ bit OFFSET. Returns the bit index of the first 1-bit found,
+ or ULONG_MAX if none is found. */
+static unsigned long int
+next_1bit (unsigned int pattern, unsigned int offset,
+ unsigned int pattern_offset)
+{
+ for (; offset < UINT_BIT; offset++)
+ if (pattern & (1u << offset))
+ return offset + pattern_offset;
+ return ULONG_MAX;
+}
+
+static void
+print_structure (const struct abt_node *node_)
+{
+ struct range_tower_node *node;
+
+ if (node_ == NULL)
+ return;
+ node = abt_data (node_, struct range_tower_node, abt_node);
+ printf ("%lu+%lu/%d", node->n_zeros, node->n_ones, node->abt_node.level);
+ if (node->abt_node.down[0] || node->abt_node.down[1])
+ {
+ printf ("(");
+ print_structure (node->abt_node.down[0]);
+ printf (",");
+ print_structure (node->abt_node.down[1]);
+ printf (")");
+ }
+}
+
+/* Prints the regions in RT to stdout. */
+static void UNUSED
+print_regions (const struct range_tower *rt)
+{
+ const struct range_tower_node *node;
+
+ printf ("contents:");
+ for (node = range_tower_first__ (rt); node != NULL;
+ node = range_tower_next__ (rt, node))
+ printf (" (%lu,%lu)", node->n_zeros, node->n_ones);
+ printf ("\n");
+ printf ("structure:");
+ print_structure (rt->abt.root);
+ printf ("\n");
+}
+
+static void
+check_tree (const struct abt_node *abt_node, unsigned long int *subtree_width)
+{
+ const struct range_tower_node *node = range_tower_node_from_abt__ (abt_node);
+ unsigned long int left_width, right_width;
+
+ if (node == NULL)
+ {
+ *subtree_width = 0;
+ return;
+ }
+
+ check_tree (node->abt_node.down[0], &left_width);
+ check_tree (node->abt_node.down[1], &right_width);
+
+ *subtree_width = node->n_zeros + node->n_ones + left_width + right_width;
+ check (node->subtree_width == *subtree_width);
+}
+
+/* Checks that the regions in RT match the bits in PATTERN. */
+static void
+check_pattern (const struct range_tower *rt, unsigned int pattern,
+ unsigned long int offset)
+{
+ const struct range_tower_node *node;
+ unsigned long int start, start2, width;
+ unsigned long int tree_width;
+ unsigned long int s1, s2;
+ int i;
+
+ check_tree (rt->abt.root, &tree_width);
+ check (tree_width == ULONG_MAX);
+
+ if (offset > ULONG_MAX - 32)
+ {
+ pattern <<= offset - (ULONG_MAX - 32);
+ offset = ULONG_MAX - 32;
+ }
+
+ for (node = rand () % 2 ? range_tower_first (rt) : range_tower_next (rt, NULL),
+ start = width = 0;
+ next_region (pattern, start + width, &start, &width);
+ node = range_tower_next (rt, node))
+ {
+ unsigned long int node_start;
+ unsigned long int x;
+
+ check (node != NULL);
+ check (range_tower_node_get_start (node) == start + offset);
+ check (range_tower_node_get_end (node) == start + offset + width);
+ check (range_tower_node_get_width (node) == width);
+
+ x = start + offset - node->n_zeros;
+ check (range_tower_lookup (rt, x, &node_start) == node);
+ check (node_start == start + offset - node->n_zeros);
+
+ x = start + offset + width - 1;
+ check (range_tower_lookup (rt, x, &node_start) == node);
+ check (node_start == start + offset - node->n_zeros);
+ }
+ check (node == NULL);
+
+ start = width = 0;
+ RANGE_TOWER_FOR_EACH (node, start2, rt)
+ {
+ check (next_region (pattern, start + width, &start, &width));
+ check (start + offset == start2);
+ check (range_tower_node_get_width (node) == width);
+ }
+ check (!next_region (pattern, start + width, &start, &width));
+
+ for (node = rand () % 2 ? range_tower_last (rt) : range_tower_prev (rt, NULL),
+ start = UINT_BIT;
+ prev_region (pattern, start, &start, &width);
+ node = range_tower_prev (rt, node))
+ {
+ check (node != NULL);
+ check (range_tower_node_get_start (node) == offset + start);
+ check (range_tower_node_get_end (node) == offset + start + width);
+ check (range_tower_node_get_width (node) == width);
+ }
+ check (node == NULL);
+
+ /* Scan from all possible positions, resetting the cache each
+ time, to ensure that we get the correct answers without
+ caching. */
+ for (start = 0; start <= 32; start++)
+ {
+ struct range_tower *nonconst_rt = CONST_CAST (struct range_tower *, rt);
+
+ nonconst_rt->cache_end = 0;
+ s1 = range_tower_scan (rt, offset + start);
+ s2 = next_1bit (pattern, start, offset);
+ check (s1 == s2);
+ }
+
+ /* Scan in forward order to exercise expected cache behavior. */
+ for (s1 = range_tower_scan (rt, 0), s2 = next_1bit (pattern, 0, offset); ;
+ s1 = range_tower_scan (rt, s1 + 1), s2 = next_1bit (pattern, (s2 - offset) + 1, offset))
+ {
+ check (s1 == s2);
+ if (s1 == ULONG_MAX)
+ break;
+ }
+
+ /* Scan in random order to frustrate cache. */
+ for (i = 0; i < 32; i++)
+ {
+ start = rand () % 32;
+ s1 = range_tower_scan (rt, start + offset);
+ s2 = next_1bit (pattern, start, offset);
+ check (s1 == s2);
+ }
+
+ /* Test range_tower_scan() with negative cache. */
+ check (!range_tower_contains (rt, 999));
+ if (offset < 1111)
+ check (range_tower_scan (rt, 1111) == ULONG_MAX);
+
+ /* Check for containment without caching. */
+ for (i = 0; i < UINT_BIT; i++)
+ {
+ struct range_tower *nonconst_rt = CONST_CAST (struct range_tower *, rt);
+ nonconst_rt->cache_end = 0;
+ check (range_tower_contains (rt, i + offset)
+ == ((pattern & (1u << i)) != 0));
+ }
+
+ /* Check for containment with caching. */
+ for (i = 0; i < UINT_BIT; i++)
+ check (range_tower_contains (rt, i + offset)
+ == ((pattern & (1u << i)) != 0));
+
+ check (!range_tower_contains (rt,
+ UINT_BIT + rand () % (ULONG_MAX - UINT_BIT * 2)));
+
+ check (range_tower_is_empty (rt) == (pattern == 0));
+}
+
+/* Creates and returns a range tower that contains regions for the
+ bits tower in PATTERN. */
+static struct range_tower *
+make_pattern (unsigned int pattern, unsigned long int offset)
+{
+ unsigned long int start = 0;
+ unsigned long int width = 0;
+ struct range_tower *rt = range_tower_create_pool (NULL);
+ while (next_region (pattern, start + width, &start, &width))
+ range_tower_set1 (rt, start + offset, width);
+ check_pattern (rt, pattern, offset);
+ return rt;
+}
+
+/* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
+ tower to 1, other bits tower to 0. */
+static unsigned int
+bit_range (unsigned int ofs, unsigned int cnt)
+{
+ assert (ofs < UINT_BIT);
+ assert (cnt <= UINT_BIT);
+ assert (ofs + cnt <= UINT_BIT);
+
+ return cnt < UINT_BIT ? ((1u << cnt) - 1) << ofs : UINT_MAX;
+}
+\f
+/* Tests setting all possible ranges of 1s into all possible range sets (up to
+ a small maximum number of bits). */
+static void
+test_set1 (void)
+{
+ const int positions = 9;
+ unsigned int init_pat;
+ int start, width;
+ int k;
+
+ for (k = 0; k < 2; k++)
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (start = 0; start < positions; start++)
+ for (width = 0; width + start <= positions; width++)
+ {
+ unsigned long int offset = k ? ULONG_MAX - positions : 0;
+ struct range_tower *rt, *rt2;
+ unsigned int final_pat;
+
+ rt = make_pattern (init_pat, offset);
+ range_tower_set1 (rt, offset + start, width);
+ final_pat = init_pat | bit_range (start, width);
+ check_pattern (rt, final_pat, offset);
+ rt2 = range_tower_clone (rt, NULL);
+ check_pattern (rt2, final_pat, offset);
+ range_tower_destroy (rt);
+ range_tower_destroy (rt2);
+ }
+}
+
+/* Tests setting all possible ranges of 0s into all possible range sets (up to
+ a small maximum number of bits). */
+static void
+test_set0 (void)
+{
+ const int positions = 9;
+ unsigned int init_pat;
+ int start, width, k;
+
+ for (k = 0; k < 2; k++)
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (start = 0; start < positions; start++)
+ for (width = 0; start + width <= positions; width++)
+ {
+ unsigned long int offset = k ? ULONG_MAX - positions : 0;
+ struct range_tower *rt;
+ unsigned int final_pat;
+
+ rt = make_pattern (init_pat, offset);
+ range_tower_set0 (rt, offset + start, width);
+ final_pat = init_pat & ~bit_range (start, width);
+ check_pattern (rt, final_pat, offset);
+ range_tower_destroy (rt);
+ }
+}
+
+/* Tests inserting all possible ranges of 0s into all possible range sets (up
+ to a small maximum number of bits). */
+static void
+test_insert0 (void)
+{
+ const int positions = 9;
+ unsigned int init_pat;
+ int start, width, k;
+
+ for (k = 0; k < 2; k++)
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (start = 0; start < positions; start++)
+ for (width = 0; start + width <= positions; width++)
+ {
+ unsigned long int offset = k ? ULONG_MAX - positions : 0;
+ struct range_tower *rt;
+ unsigned int final_pat;
+
+ rt = make_pattern (init_pat, offset);
+ range_tower_insert0 (rt, offset + start, width);
+ final_pat = init_pat & bit_range (0, start);
+ final_pat |= (init_pat & bit_range (start, positions - start)) << width;
+ check_pattern (rt, final_pat, offset);
+ range_tower_destroy (rt);
+ }
+}
+
+/* Tests inserting all possible ranges of 1s into all possible range sets (up
+ to a small maximum number of bits). */
+static void
+test_insert1 (void)
+{
+ const int positions = 9;
+ unsigned int init_pat;
+ int start, width, k;
+
+ for (k = 0; k < 2; k++)
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (start = 0; start < positions; start++)
+ for (width = 0; start + width <= positions; width++)
+ {
+ struct range_tower *rt;
+ unsigned int final_pat;
+
+ rt = make_pattern (init_pat, 0);
+ range_tower_insert1 (rt, start, width);
+ final_pat = init_pat & bit_range (0, start);
+ final_pat |= bit_range (start, width);
+ final_pat |= (init_pat & bit_range (start, positions - start)) << width;
+ check_pattern (rt, final_pat, 0);
+ range_tower_destroy (rt);
+ }
+}
+
+/* Tests setting all possible ranges from all possible range sets (up to a
+ small maximum number of bits). */
+static void
+test_delete (void)
+{
+ const int positions = 9;
+ unsigned int init_pat;
+ int start, width, k;
+
+ for (k = 0; k < 2; k++)
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (start = 0; start < positions; start++)
+ for (width = 0; start + width <= positions; width++)
+ {
+ unsigned long int offset = k ? ULONG_MAX - positions : 0;
+ struct range_tower *rt;
+ unsigned int final_pat;
+
+ rt = make_pattern (init_pat, offset);
+ range_tower_delete (rt, start + offset, width);
+ final_pat = init_pat & bit_range (0, start);
+ final_pat |= (init_pat & (UINT_MAX << (start + width))) >> width;
+ check_pattern (rt, final_pat, offset);
+ range_tower_destroy (rt);
+ }
+}
+
+/* Tests moving all possible ranges (up to a small maximum number of bits). */
+static void
+test_move (void)
+{
+ const int positions = 9;
+ unsigned int init_pat;
+ int new_start, old_start, width, k;
+
+ for (k = 0; k < 2; k++)
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (width = 0; width <= positions; width++)
+ for (new_start = 0; new_start + width <= positions; new_start++)
+ for (old_start = 0; old_start + width <= positions; old_start++)
+ {
+ unsigned long int offset = k ? ULONG_MAX - positions : 0;
+ struct range_tower *rt;
+ unsigned int final_pat;
+
+ if (new_start == old_start || width == 0)
+ final_pat = init_pat;
+ else if (new_start < old_start)
+ {
+ final_pat = init_pat & bit_range (0, new_start);
+ final_pat |= (init_pat & bit_range (old_start, width)) >> (old_start - new_start);
+ final_pat |= (init_pat & bit_range (new_start, old_start - new_start)) << width;
+ final_pat |= init_pat & bit_range (old_start + width, positions - (old_start + width));
+ }
+ else
+ {
+ final_pat = init_pat & bit_range (0, old_start);
+ final_pat |= (init_pat & bit_range (old_start + width, new_start - old_start)) >> width;
+ final_pat |= (init_pat & bit_range (old_start, width)) << (new_start - old_start);
+ final_pat |= init_pat & bit_range (new_start + width, positions - (new_start + width));
+ }
+
+ rt = make_pattern (init_pat, offset);
+ range_tower_move (rt, old_start + offset, new_start + offset,
+ width);
+ check_pattern (rt, final_pat, offset);
+ range_tower_destroy (rt);
+ }
+}
+
+/* Tests freeing a range tower through a pool. */
+static void
+test_pool (void)
+{
+ struct pool *pool;
+ struct range_tower *rt;
+
+ /* Destroy the range tower, then the pool.
+ Makes sure that this doesn't cause a double-free. */
+ pool = pool_create ();
+ rt = range_tower_create_pool (pool);
+ range_tower_set1 (rt, 1, 10);
+ range_tower_destroy (rt);
+ pool_destroy (pool);
+
+ /* Just destroy the pool.
+ Makes sure that this doesn't cause a leak. */
+ pool = pool_create ();
+ rt = range_tower_create_pool (pool);
+ range_tower_set1 (rt, 1, 10);
+ pool_destroy (pool);
+}
+
+/* Tests range_tower_destroy(NULL). */
+static void
+test_destroy_null (void)
+{
+ range_tower_destroy (NULL);
+}
+\f
+/* Main program. */
+
+struct test
+ {
+ const char *name;
+ const char *description;
+ void (*function) (void);
+ };
+
+static const struct test tests[] =
+ {
+ {
+ "set1",
+ "set1",
+ test_set1
+ },
+ {
+ "set0",
+ "set0",
+ test_set0
+ },
+ {
+ "insert0",
+ "insert0",
+ test_insert0
+ },
+ {
+ "insert1",
+ "insert1",
+ test_insert1
+ },
+ {
+ "delete",
+ "delete",
+ test_delete
+ },
+ {
+ "move",
+ "move",
+ test_move
+ },
+ {
+ "pool",
+ "pool",
+ test_pool
+ },
+ {
+ "destroy-null",
+ "destroy null",
+ test_destroy_null
+ },
+ };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
+
+int
+main (int argc, char *argv[])
+{
+ int i;
+
+ if (argc != 2)
+ {
+ fprintf (stderr, "exactly one argument required; use --help for help\n");
+ return EXIT_FAILURE;
+ }
+ else if (!strcmp (argv[1], "--help"))
+ {
+ printf ("%s: test range tower library\n"
+ "usage: %s TEST-NAME\n"
+ "where TEST-NAME is one of the following:\n",
+ argv[0], argv[0]);
+ for (i = 0; i < N_TESTS; i++)
+ printf (" %s\n %s\n", tests[i].name, tests[i].description);
+ return 0;
+ }
+ else
+ {
+ for (i = 0; i < N_TESTS; i++)
+ if (!strcmp (argv[1], tests[i].name))
+ {
+ tests[i].function ();
+ return 0;
+ }
+
+ fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
+ return EXIT_FAILURE;
+ }
+}
projects / pspp / blobdiff