/* PSPP - a program for statistical analysis.
- Copyright (C) 2007, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2009, 2010, 2011, 2012 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
#include "xalloc.h"
\f
-/* Currently running test. */
-static const char *test_name;
-
/* Exit with a failure code.
(Place a breakpoint on this function while debugging.) */
static void
{
if (!ok)
{
- printf ("Check failed in %s test at %s, line %d\n",
- test_name, __FILE__, line);
+ fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
check_die ();
}
}
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)
+{
+ for (; offset < UINT_BIT; offset++)
+ if (pattern & (1u << offset))
+ return offset;
+ return ULONG_MAX;
+}
+
/* Prints the regions in RS to stdout. */
static void UNUSED
print_regions (const struct range_set *rs)
const struct range_set_node *node;
printf ("result:");
- for (node = range_set_first (rs); node != NULL;
- node = range_set_next (rs, node))
+ RANGE_SET_FOR_EACH (node, rs)
printf (" (%lu,%lu)",
range_set_node_get_start (node), range_set_node_get_end (node));
printf ("\n");
{
const struct range_set_node *node;
unsigned long int start, width;
+ unsigned long int s1, s2;
int i;
for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL),
}
check (node == NULL);
+ for (node = rand () % 2 ? range_set_last (rs) : range_set_prev (rs, NULL),
+ start = UINT_BIT;
+ prev_region (pattern, start, &start, &width);
+ node = range_set_prev (rs, node))
+ {
+ check (node != NULL);
+ check (range_set_node_get_start (node) == start);
+ check (range_set_node_get_end (node) == start + width);
+ check (range_set_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_set *nonconst_rs = CONST_CAST (struct range_set *, rs);
+ nonconst_rs->cache_end = 0;
+ s1 = range_set_scan (rs, start);
+ s2 = next_1bit (pattern, start);
+ check (s1 == s2);
+ }
+
+ /* Scan in forward order to exercise expected cache behavior. */
+ for (s1 = range_set_scan (rs, 0), s2 = next_1bit (pattern, 0); ;
+ s1 = range_set_scan (rs, s1 + 1), s2 = next_1bit (pattern, s2 + 1))
+ {
+ 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_set_scan (rs, start);
+ s2 = next_1bit (pattern, start);
+ check (s1 == s2);
+ }
+
+ /* Test range_set_scan() with negative cache. */
+ check (!range_set_contains (rs, 999));
+ check (range_set_scan (rs, 1111) == ULONG_MAX);
+
for (i = 0; i < UINT_BIT; i++)
check (range_set_contains (rs, i) == ((pattern & (1u << i)) != 0));
check (!range_set_contains (rs,
unsigned long int width = 0;
struct range_set *rs = range_set_create_pool (NULL);
while (next_region (pattern, start + width, &start, &width))
- range_set_insert (rs, start, width);
+ range_set_set1 (rs, start, width);
check_pattern (rs, pattern);
return rs;
}
unsigned int final_pat;
rs = make_pattern (init_pat);
- range_set_insert (rs, i, j - i);
+ range_set_set1 (rs, i, j - i);
final_pat = init_pat | bit_range (i, j - i);
check_pattern (rs, final_pat);
rs2 = range_set_clone (rs, NULL);
unsigned int final_pat;
rs = make_pattern (init_pat);
- range_set_delete (rs, i, j - i);
+ range_set_set0 (rs, i, j - i);
final_pat = init_pat & ~bit_range (i, j - i);
check_pattern (rs, final_pat);
range_set_destroy (rs);
Makes sure that this doesn't cause a double-free. */
pool = pool_create ();
rs = range_set_create_pool (pool);
- range_set_insert (rs, 1, 10);
+ range_set_set1 (rs, 1, 10);
range_set_destroy (rs);
pool_destroy (pool);
Makes sure that this doesn't cause a leak. */
pool = pool_create ();
rs = range_set_create_pool (pool);
- range_set_insert (rs, 1, 10);
+ range_set_set1 (rs, 1, 10);
pool_destroy (pool);
}
\f
/* Main program. */
-/* Runs TEST_FUNCTION and prints a message about NAME. */
-static void
-run_test (void (*test_function) (void), const char *name)
-{
- test_name = name;
- putchar ('.');
- fflush (stdout);
- test_function ();
-}
+struct test
+ {
+ const char *name;
+ const char *description;
+ void (*function) (void);
+ };
+
+static const struct test tests[] =
+ {
+ {
+ "insert",
+ "insert",
+ test_insert
+ },
+ {
+ "delete",
+ "delete",
+ test_delete
+ },
+ {
+ "allocate",
+ "allocate",
+ test_allocate
+ },
+ {
+ "allocate-fully",
+ "allocate_fully",
+ test_allocate_fully
+ },
+ {
+ "pool",
+ "pool",
+ test_pool
+ },
+ {
+ "destroy-null",
+ "destroy null",
+ test_destroy_null
+ },
+ };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
int
-main (void)
+main (int argc, char *argv[])
{
- run_test (test_insert, "insert");
- run_test (test_delete, "delete");
- run_test (test_allocate, "allocate");
- run_test (test_allocate_fully, "allocate_fully");
- run_test (test_pool, "pool");
- run_test (test_destroy_null, "destroy null");
- putchar ('\n');
-
- return 0;
+ 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 set 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;
+ }
}