/* PSPP - a program for statistical analysis.
- Copyright (C) 2007 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2009 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
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;
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 = (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,
}
}
+/* Tests all possible full allocations in all possible range sets
+ (up to a small maximum number of bits). */
+static void
+test_allocate_fully (void)
+{
+ const int positions = 9;
+ unsigned int init_pat;
+ int request;
+
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (request = 1; request <= positions + 1; request++)
+ {
+ struct range_set *rs;
+ unsigned long int start, expect_start;
+ bool success, expect_success;
+ unsigned int final_pat;
+ int i;
+
+ /* Figure out expected results. */
+ expect_success = false;
+ expect_start = 0;
+ final_pat = init_pat;
+ for (i = 0; i < positions - request + 1; i++)
+ {
+ int j;
+
+ final_pat = init_pat;
+ for (j = i; j < i + request; j++)
+ {
+ if (!(init_pat & (1u << j)))
+ goto next;
+ final_pat &= ~(1u << j);
+ }
+
+ expect_success = true;
+ expect_start = i;
+ break;
+ next:
+ final_pat = init_pat;
+ }
+
+ /* Test. */
+ rs = make_pattern (init_pat);
+ success = range_set_allocate_fully (rs, request, &start);
+ check_pattern (rs, final_pat);
+ range_set_destroy (rs);
+
+ /* Check results. */
+ check (success == expect_success);
+ if (expect_success)
+ check (start == expect_start);
+ }
+}
+
/* Tests freeing a range set through a pool. */
static void
test_pool (void)
range_set_insert (rs, 1, 10);
pool_destroy (pool);
}
+
+/* Tests range_set_destroy(NULL). */
+static void
+test_destroy_null (void)
+{
+ range_set_destroy (NULL);
+}
\f
/* Main program. */
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;
projects / pspp-builds.git / blobdiff