From 4bc7fb8814bc15858ab801be55b3b6cd79dd06e6 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Thu, 25 Aug 2011 20:20:52 -0700 Subject: [PATCH] New "range-tower" data structure. A range tower is a bitmap, implemented as an augmented binary tree. Beyond the usual features of a bitmap, a range tower can efficiently implement a "splice" operation that shifts ranges of bits left or right. This feature does cost memory and time, so use a range tower only if this feature is actually needed. Otherwise, use a range set (see range-set.h), which can do everything that a range tower can do except the "splice" operation. Each operation has O(lg N) cost, where N is the number of contiguous regions of 1-bits in the bitmap. Also, a cache reduces the second and subsequent containment tests within a single contiguous region to O(1). --- src/libpspp/automake.mk | 2 + src/libpspp/range-tower.c | 1033 ++++++++++++++++++++++++++++++ src/libpspp/range-tower.h | 250 ++++++++ tests/automake.mk | 8 + tests/libpspp/range-tower-test.c | 658 +++++++++++++++++++ tests/libpspp/range-tower.at | 15 + 6 files changed, 1966 insertions(+) create mode 100644 src/libpspp/range-tower.c create mode 100644 src/libpspp/range-tower.h create mode 100644 tests/libpspp/range-tower-test.c create mode 100644 tests/libpspp/range-tower.at diff --git a/src/libpspp/automake.mk b/src/libpspp/automake.mk index 567e56a492..244f1d1520 100644 --- a/src/libpspp/automake.mk +++ b/src/libpspp/automake.mk @@ -62,6 +62,8 @@ src_libpspp_liblibpspp_la_SOURCES = \ src/libpspp/range-map.h \ src/libpspp/range-set.c \ src/libpspp/range-set.h \ + src/libpspp/range-tower.c \ + src/libpspp/range-tower.h \ src/libpspp/sparse-array.c \ src/libpspp/sparse-array.h \ src/libpspp/sparse-xarray.c \ diff --git a/src/libpspp/range-tower.c b/src/libpspp/range-tower.c new file mode 100644 index 0000000000..9d9f8aaa84 --- /dev/null +++ b/src/libpspp/range-tower.c @@ -0,0 +1,1033 @@ +/* pspp - a program for statistical analysis. + Copyright (C) 2007, 2009, 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 . */ + +/* Bitmap, implemented as a balanced binary tree. */ + +/* If you add routines in this file, please add a corresponding + test to range-tower-test.c. This test program should achieve + 100% coverage of lines and branches in this code, as reported + by "gcov -b". */ + +#include + +#include "libpspp/range-tower.h" + +#include +#include + +#include "libpspp/assertion.h" +#include "libpspp/compiler.h" +#include "libpspp/pool.h" + +#include "gl/minmax.h" +#include "gl/xalloc.h" + +static void reaugment_range_tower_node (struct abt_node *, const void *aux); +static void delete_node (struct range_tower *, struct range_tower_node *); + +static void destroy_pool (void *); + +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 char *title, const struct range_tower *rt) +{ + const struct range_tower_node *node; + + printf ("%s:", title); + 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 struct range_tower_node * +range_tower_node_from_abt_node (const struct abt_node *abt_node) +{ + return abt_data (abt_node, struct range_tower_node, abt_node); +} + +/* Returns the total width (zeros and ones) of the nodes in the subtree rooted + at P, or 0 if P is null. */ +static unsigned long int +subtree_width (const struct abt_node *p) +{ + return p != NULL ? range_tower_node_from_abt_node (p)->subtree_width : 0; +} + +/* Returns the position of the first 1-bit in NODE. + + The performance of this function is O(lg n) in the number of nodes in the + range tower. It is often possible to avoid calling this function, either by + taking advantage of the NODE_START parameter to tower_lookup or by + incrementally keeping track of height while iterating through a tower. In + the former case the asymptotic performance is no different, since + tower_lookup is also O(lg n), but in the latter case performance improves + from O(lg n) to O(1). */ +unsigned long int +range_tower_node_get_start (const struct range_tower_node *node) +{ + const struct abt_node *p = &node->abt_node; + unsigned long start = subtree_width (p->down[0]) + range_tower_node_from_abt_node (p)->n_zeros; + while (p->up != NULL) + { + if (p == p->up->down[1]) + { + const struct range_tower_node *up + = range_tower_node_from_abt_node (p->up); + start += subtree_width (p->up->down[0]) + up->n_zeros + up->n_ones; + } + p = p->up; + } + return start; +} + +/* Returns one past the position of the last 1-bit in NODE. + + Like range_tower_node_get_start(), the performance of this function is O(lg + n) in the number of nodes in the range tower. */ +unsigned long int +range_tower_node_get_end (const struct range_tower_node *node) +{ + return range_tower_node_get_start (node) + node->n_ones; +} + +/* Creates and returns a new, empty range tower. */ +struct range_tower * +range_tower_create (void) +{ + return range_tower_create_pool (NULL); +} + +static struct range_tower * +range_tower_create_pool__ (struct pool *pool) +{ + struct range_tower *rt = xmalloc (sizeof *rt); + + rt->pool = pool; + if (pool != NULL) + pool_register (pool, destroy_pool, rt); + + abt_init (&rt->abt, NULL, reaugment_range_tower_node, NULL); + rt->cache_end = 0; + + return rt; +} + +/* Creates and returns a new, empty range tower in the given POOL. */ +struct range_tower * +range_tower_create_pool (struct pool *pool) +{ + struct range_tower_node *node; + struct range_tower *rt; + + rt = range_tower_create_pool__ (pool); + + node = xmalloc (sizeof *node); + node->n_zeros = ULONG_MAX; + node->n_ones = 0; + abt_insert_after (&rt->abt, NULL, &node->abt_node); + + return rt; +} + +/* Creates and returns a clone of OLD range tower in the given POOL + (which may be null). */ +struct range_tower * +range_tower_clone (const struct range_tower *old, struct pool *pool) +{ + const struct range_tower_node *old_node; + struct abt_node *prev_node; + struct range_tower *new; + + new = range_tower_create_pool__ (pool); + prev_node = NULL; + for (old_node = range_tower_first__ (old); old_node != NULL; + old_node = range_tower_next__ (old, old_node)) + { + struct range_tower_node *new_node; + + new_node = xmalloc (sizeof *new_node); + new_node->n_zeros = old_node->n_zeros; + new_node->n_ones = old_node->n_ones; + + abt_insert_after (&new->abt, prev_node, &new_node->abt_node); + prev_node = &new_node->abt_node; + } + return new; +} + +/* Destroys range tower RT. */ +void +range_tower_destroy (struct range_tower *rt) +{ + if (rt != NULL) + { + if (rt->pool != NULL) + pool_unregister (rt->pool, rt); + while (!abt_is_empty (&rt->abt)) + delete_node (rt, range_tower_first__ (rt)); + free (rt); + } +} + +/* Sets the WIDTH bits starting at START in RT to 1-bits. */ +void +range_tower_set1 (struct range_tower *rt, + unsigned long int start, unsigned long int width) +{ + struct range_tower_node *node; + unsigned long int node_start; + + assert (width == 0 || start + width - 1 >= start); + + node = range_tower_lookup (rt, start, &node_start); + while (width > 0) + { + unsigned long int node_ofs = start - node_start; + + if (node_ofs >= node->n_zeros) + { + /* There are already some 1-bits here, so skip them. */ + unsigned long ones_left = (node->n_zeros + node->n_ones) - node_ofs; + if (width <= ones_left) + return; + + start += ones_left; + width -= ones_left; + node_start += node->n_zeros + node->n_ones; + node_ofs = 0; + node = range_tower_next__ (rt, node); + } + + /* Invalidate cache. */ + rt->cache_end = 0; + + if (node_ofs == 0) + { + if (node_start > 0) + { + struct range_tower_node *prev = range_tower_prev__ (rt, node); + if (width >= node->n_zeros) + { + /* All zeros in NODE are replaced by ones. Change NODE's + entire width into PREV's trailing ones, e.g. 00001111 + 00001111 becomes 0000111111111111. */ + int node_width = node->n_zeros + node->n_ones; + abt_delete (&rt->abt, &node->abt_node); + prev->n_ones += node_width; + abt_reaugmented (&rt->abt, &prev->abt_node); + if (width <= node_width) + return; + + /* Go around again with NODE replaced by PREV's new + successor. */ + width -= node_width; + start += node_width; + node = range_tower_next__ (rt, prev); + node_start += node_width; + } + else + { + /* Leading zeros in NODE change into trailing ones in PREV, + but trailing zeros in NODE remain, e.g. 00001111 00001111 + becomes 0000111111 001111. */ + node->n_zeros -= width; + abt_reaugmented (&rt->abt, &node->abt_node); + + prev->n_ones += width; + abt_reaugmented (&rt->abt, &prev->abt_node); + return; + } + } + else + { + if (width >= node->n_zeros) + { + /* All zeros in NODE are replaced by ones, e.g. 00001111 + becomes 11111111. */ + node->n_ones += node->n_zeros; + node->n_zeros = 0; + if (width <= node->n_ones) + return; + + start += node->n_ones; + node_start += node->n_ones; + width -= node->n_ones; + node = range_tower_next__ (rt, node); + } + else + { + /* Leading zeros in NODE (which starts at offset 0) are + replaced by ones, but some zeros remain. This requires a + node split, e.g. 00001111 becomes 11 001111. */ + struct range_tower_node *new_node; + + node->n_zeros -= width; + abt_reaugmented (&rt->abt, &node->abt_node); + + new_node = xmalloc (sizeof *new_node); + new_node->n_zeros = 0; + new_node->n_ones = width; + abt_insert_before (&rt->abt, &node->abt_node, + &new_node->abt_node); + return; + } + } + } + else + { + unsigned long int zeros_left = node->n_zeros - node_ofs; + if (width >= zeros_left) + { + /* Trailing zeros in NODE are replaced by ones, but leading + zeros remain, e.g. 00001111 becomes 00111111. */ + node->n_zeros -= zeros_left; + node->n_ones += zeros_left; + if (width <= node->n_ones) + return; + start += node->n_ones; + width -= node->n_ones; + node_start += node->n_zeros + node->n_ones; + node = range_tower_next__ (rt, node); + } + else + { + /* Zeros that are neither leading or trailing turn into ones. + Split the node into two nodes, e.g. 00001111 becomes 011 + 01111. */ + struct range_tower_node *new_node; + + new_node = xmalloc (sizeof *new_node); + new_node->n_ones = node->n_ones; + new_node->n_zeros = zeros_left - width; + + node->n_zeros = node_ofs; + node->n_ones = width; + abt_reaugmented (&rt->abt, &node->abt_node); + + abt_insert_after (&rt->abt, &node->abt_node, + &new_node->abt_node); + return; + } + } + } +} + +/* Sets the WIDTH bits starting at START in RT to 0-bits. */ +void +range_tower_set0 (struct range_tower *rt, + unsigned long int start, unsigned long int width) +{ + struct range_tower_node *node; + unsigned long int node_start; + + assert (width == 0 || start + width - 1 >= start); + + node = range_tower_lookup (rt, start, &node_start); + while (width > 0) + { + unsigned long int node_ofs = start - node_start; + + if (node_ofs < node->n_zeros) + { + /* Deleting zeros is a no-op, so skip them. */ + unsigned long zeros_left = node->n_zeros - node_ofs; + if (zeros_left >= width) + { + /* We are deleting only existing zeros. Nothing to do. */ + return; + } + + width -= zeros_left; + start += zeros_left; + node_ofs = node->n_zeros; + } + + rt->cache_end = 0; + + if (node_ofs == node->n_zeros) + { + if (node->n_ones > width) + { + /* DELTA leading ones within NODE turn into zeros, but some ones + remain, e.g. 00001111 becomes 00111111. No reaugmentation + because n_zeros + n_ones doesn't change. */ + node->n_zeros += width; + node->n_ones -= width; + return; + } + else + { + /* All ones in NODE turn into zeros, so merge NODE with the + following node, e.g. 00001111 00001111 becomes + 0000000000001111, and then do it again with the merged + node. */ + unsigned long int next_zeros, next_ones; + struct range_tower_node *next; + + next = range_tower_next__ (rt, node); + if (next == NULL) + { + node->n_zeros += node->n_ones; + node->n_ones = 0; + return; + } + + next_zeros = next->n_zeros; + next_ones = next->n_ones; + abt_delete (&rt->abt, &next->abt_node); + + node->n_zeros += node->n_ones + next_zeros; + node->n_ones = next_ones; + abt_reaugmented (&rt->abt, &node->abt_node); + } + } + else if (node_ofs + width >= node->n_zeros + node->n_ones) + { + /* Trailing ones in NODE turn into zeros, but leading ones remain, + e.g. 000011{11} 00001111 becomes 000011 {00}00001111. Give the + trailing ones to the next node as zeros and go around again with + the next node. */ + struct range_tower_node *next; + unsigned long int delta; + + delta = node->n_ones - (node_ofs - node->n_zeros); + node->n_ones -= delta; + abt_reaugmented (&rt->abt, &node->abt_node); + + next = range_tower_next__ (rt, node); + if (next == NULL) + { + struct range_tower_node *new_node; + + new_node = xmalloc (sizeof *new_node); + new_node->n_zeros = delta; + new_node->n_ones = 0; + + abt_insert_before (&rt->abt, NULL, &new_node->abt_node); + return; + } + + next->n_zeros += delta; + abt_reaugmented (&rt->abt, &next->abt_node); + + node_start += node->n_zeros + node->n_ones; + start = node_start; + node = next; + } + else + { + /* Ones that are neither leading or trailing turn into zeros, + e.g. 00001111 becomes 00001 001. Split the node into two nodes + and we're done. */ + unsigned long int end = start + width; + struct range_tower_node *new_node; + + new_node = xmalloc (sizeof *new_node); + new_node->n_zeros = width; + new_node->n_ones = (node_start + node->n_zeros + node->n_ones) - end; + + node->n_ones = node_ofs - node->n_zeros; + abt_reaugmented (&rt->abt, &node->abt_node); + + abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node); + return; + } + } +} + +static void +range_tower_delete__ (struct range_tower *rt, + unsigned long int start, unsigned long int width) +{ + struct range_tower_node *node; + unsigned long int node_start; + + rt->cache_end = 0; + node = range_tower_lookup (rt, start, &node_start); + for (;;) + { + unsigned long int node_ofs = start - node_start; + + if (node_ofs < node->n_zeros) + { + if (node_ofs + width < node->n_zeros) + { + node->n_zeros -= width; + abt_reaugmented (&rt->abt, &node->abt_node); + break; + } + else if (node_ofs > 0) + { + width -= node->n_zeros - node_ofs; + node->n_zeros = node_ofs; + abt_reaugmented (&rt->abt, &node->abt_node); + if (width == 0) + break; + /* Continue with 1-bits. */ + } + else if (width < node->n_zeros + node->n_ones) + { + struct range_tower_node *prev = range_tower_prev__ (rt, node); + unsigned long int ones_left; + + ones_left = (node->n_zeros + node->n_ones) - width; + if (prev != NULL) + { + abt_delete (&rt->abt, &node->abt_node); + prev->n_ones += ones_left; + abt_reaugmented (&rt->abt, &prev->abt_node); + } + else + { + node->n_zeros = 0; + node->n_ones = ones_left; + abt_reaugmented (&rt->abt, &node->abt_node); + } + break; + } + else + { + /* Delete entire node. */ + struct range_tower_node *next = range_tower_next__ (rt, node); + + width -= node->n_zeros + node->n_ones; + abt_delete (&rt->abt, &node->abt_node); + if (next == NULL) + break; + + node = next; + continue; + } + } + + if (node_ofs + width < node->n_zeros + node->n_ones) + { + node->n_ones -= width; + abt_reaugmented (&rt->abt, &node->abt_node); + break; + } + else if (node_ofs > node->n_zeros) + { + unsigned long int ones_ofs = node_ofs - node->n_zeros; + width -= node->n_ones - ones_ofs; + node->n_ones = ones_ofs; + abt_reaugmented (&rt->abt, &node->abt_node); + if (width == 0) + break; + /* continue with next node */ + node_start += node->n_zeros + node->n_ones; + node = range_tower_next__ (rt, node); + } + else + { + /* Merge with next node */ + struct range_tower_node *next = range_tower_next__ (rt, node); + if (next != NULL) + { + unsigned long int next_zeros = next->n_zeros; + unsigned long int next_ones = next->n_ones; + + abt_delete (&rt->abt, &next->abt_node); + + width -= node->n_ones; + + node->n_zeros += next_zeros; + node->n_ones = next_ones; + abt_reaugmented (&rt->abt, &node->abt_node); + + if (width == 0) + break; + } + else + { + node->n_ones = 0; + abt_reaugmented (&rt->abt, &node->abt_node); + break; + } + } + } +} + +void +range_tower_delete (struct range_tower *rt, + unsigned long int start, unsigned long int width) +{ + struct range_tower_node *node; + + if (width == 0) + return; + + assert (start + width - 1 >= start); + + range_tower_delete__ (rt, start, width); + + node = range_tower_last__ (rt); + if (node != NULL && node->n_ones == 0) + { + node->n_zeros += width; + abt_reaugmented (&rt->abt, &node->abt_node); + } + else + { + struct range_tower_node *new_node; + + new_node = xmalloc (sizeof *new_node); + new_node->n_zeros = width; + new_node->n_ones = 0; + + abt_insert_before (&rt->abt, NULL, &new_node->abt_node); + } +} + +static struct range_tower_node * +range_tower_insert0__ (struct range_tower *rt, struct range_tower_node *node, + unsigned long int *node_startp, + unsigned long int start, unsigned long int width) +{ + unsigned long int node_ofs = start - *node_startp; + + if (node_ofs <= node->n_zeros) + { + /* 00+00+001111 => 0000001111. */ + node->n_zeros += width; + abt_reaugmented (&rt->abt, &node->abt_node); + + return node; + } + else + { + /* 000011+00+11 => 000011 0011. */ + struct range_tower_node *new_node; + + new_node = xmalloc (sizeof *new_node); + new_node->n_zeros = width; + new_node->n_ones = node->n_zeros + node->n_ones - node_ofs; + + node->n_ones -= new_node->n_ones; + abt_reaugmented (&rt->abt, &node->abt_node); + abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node); + + *node_startp += node->n_zeros + node->n_ones; + return new_node; + } +} + +void +range_tower_insert0 (struct range_tower *rt, + unsigned long int start, unsigned long int width) +{ + if (width == 0) + return; + + assert (width == 0 || start + width - 1 >= start); + + if (start + width == ULONG_MAX) + range_tower_set0 (rt, start, width); + else + { + struct range_tower_node *node; + unsigned long int node_start; + + range_tower_delete__ (rt, ULONG_MAX - width, width); + + node = range_tower_lookup (rt, start, &node_start); + range_tower_insert0__ (rt, node, &node_start, start, width); + } +} + +static struct range_tower_node * +range_tower_insert1__ (struct range_tower *rt, struct range_tower_node *node, + unsigned long int *node_startp, + unsigned long int start, unsigned long int width) +{ + + unsigned long int node_start = *node_startp; + unsigned long int node_ofs = start - node_start; + + if (node_ofs >= node->n_zeros) + { + node->n_ones += width; + abt_reaugmented (&rt->abt, &node->abt_node); + return node; + } + else if (node_ofs == 0 && node_start > 0) + { + struct range_tower_node *prev = range_tower_prev__ (rt, node); + + prev->n_ones += width; + abt_reaugmented (&rt->abt, &prev->abt_node); + + *node_startp += width; + return node; + } + else + { + /* 00001111 => 0+11+0001111 => 011 0001111 */ + struct range_tower_node *new_node; + + new_node = xmalloc (sizeof *new_node); + new_node->n_zeros = node->n_zeros - node_ofs; + new_node->n_ones = node->n_ones; + + node->n_zeros = node_ofs; + node->n_ones = width; + abt_reaugmented (&rt->abt, &node->abt_node); + + abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node); + + *node_startp += node->n_zeros + node->n_ones; + return new_node; + } +} + +void +range_tower_insert1 (struct range_tower *rt, + unsigned long int start, unsigned long int width) +{ + struct range_tower_node *node; + unsigned long int node_start; + + if (width == 0) + return; + + range_tower_delete__ (rt, ULONG_MAX - width, width); + + assert (width == 0 || start + width - 1 >= start); + + node = range_tower_lookup (rt, start, &node_start); + range_tower_insert1__ (rt, node, &node_start, start, width); +} + +void +range_tower_move (struct range_tower *rt, + unsigned long int old_start, + unsigned long int new_start, + unsigned long int width) +{ + unsigned long int node_start; + int i; + + if (width == 0 || old_start == new_start) + return; + + assert (old_start + width - 1 >= old_start); + assert (new_start + width - 1 >= new_start); + + i = 0; + do + { + struct range_tower_node *node; + unsigned long int node_ofs; + unsigned long int zeros, ones; + + node = range_tower_lookup (rt, old_start, &node_start); + node_ofs = old_start - node_start; + + if (node_ofs >= node->n_zeros) + { + unsigned long int max_ones; + + zeros = 0; + max_ones = (node->n_zeros + node->n_ones) - node_ofs; + ones = MIN (width, max_ones); + } + else + { + unsigned long int max_zeros; + + max_zeros = node->n_zeros - node_ofs; + zeros = MIN (width, max_zeros); + if (zeros < width) + ones = MIN (width - zeros, node->n_ones); + else + ones = 0; + } + + node->n_zeros -= zeros; + node->n_ones -= ones; + abt_reaugmented (&rt->abt, &node->abt_node); + + if (node->n_zeros == 0) + { + if (node->n_ones == 0) + abt_delete (&rt->abt, &node->abt_node); + else if (node_start > 0) + { + /* Merge with previous. */ + unsigned long int n_ones = node->n_ones; + struct range_tower_node *prev = range_tower_prev__ (rt, node); + + abt_delete (&rt->abt, &node->abt_node); + prev->n_ones += n_ones; + abt_reaugmented (&rt->abt, &prev->abt_node); + } + } + else if (node->n_ones == 0) + { + struct range_tower_node *next = range_tower_next__ (rt, node); + if (next != NULL) + { + /* Merge with next. */ + unsigned long int n_zeros = node->n_zeros; + + abt_delete (&rt->abt, &node->abt_node); + next->n_zeros += n_zeros; + abt_reaugmented (&rt->abt, &next->abt_node); + } + } + + if (new_start < old_start) + { + node = range_tower_lookup (rt, new_start, &node_start); + if (zeros) + { + node = range_tower_insert0__ (rt, node, &node_start, + new_start, zeros); + old_start += zeros; + new_start += zeros; + } + + if (ones) + { + node = range_tower_insert1__ (rt, node, &node_start, + new_start, ones); + old_start += ones; + new_start += ones; + } + } + else + { + unsigned long int remaining = width - (zeros + ones); + + if (new_start + remaining < ULONG_MAX - (zeros + ones)) + { + node = range_tower_lookup (rt, new_start + remaining, + &node_start); + if (zeros) + { + node = range_tower_insert0__ (rt, node, &node_start, + new_start + remaining, zeros); + new_start += zeros; + } + + if (ones) + { + node = range_tower_insert1__ (rt, node, &node_start, + new_start + remaining, ones); + new_start += ones; + } + } + else + { + node = range_tower_last__ (rt); + if (zeros) + { + if (node->n_ones) + { + struct range_tower_node *new_node; + + new_node = xmalloc (sizeof *new_node); + new_node->n_zeros = zeros; + new_node->n_ones = 0; + + abt_insert_after (&rt->abt, &node->abt_node, + &new_node->abt_node); + + node_start += node->n_zeros + node->n_ones; + node = new_node; + } + else + { + node->n_zeros += zeros; + abt_reaugmented (&rt->abt, &node->abt_node); + } + } + if (ones) + { + node->n_ones += ones; + abt_reaugmented (&rt->abt, &node->abt_node); + } + + new_start += zeros + ones; + } + } + width -= zeros + ones; + } + while (width > 0); +} + +/* Returns true if there is a 1-bit at the given POSITION in RT, + false otherwise. */ +bool +range_tower_contains (const struct range_tower *rt_, unsigned long int position) +{ + struct range_tower *rt = CONST_CAST (struct range_tower *, rt_); + if (position >= rt->cache_end || position < rt->cache_start) + { + struct range_tower_node *node; + unsigned long int node_start; + + node = range_tower_lookup (rt, position, &node_start); + if (position < node_start + node->n_zeros) + { + rt->cache_start = node_start; + rt->cache_end = node_start + node->n_zeros; + rt->cache_value = false; + } + else + { + rt->cache_start = node_start + node->n_zeros; + rt->cache_end = rt->cache_start + node->n_ones; + rt->cache_value = true; + } + } + return rt->cache_value; +} + +/* Returns the smallest position of a 1-bit greater than or + equal to START. Returns ULONG_MAX if there is no 1-bit with + position greater than or equal to START. */ +unsigned long int +range_tower_scan (const struct range_tower *rt_, unsigned long int start) +{ + struct range_tower *rt = CONST_CAST (struct range_tower *, rt_); + + if (start < rt->cache_end && start >= rt->cache_start && rt->cache_value) + return start; + + if (start != ULONG_MAX) + { + struct range_tower_node *node; + unsigned long int node_start; + + node = range_tower_lookup (rt, start, &node_start); + if (node->n_ones) + { + rt->cache_start = node_start + node->n_zeros; + rt->cache_end = rt->cache_start + node->n_ones; + rt->cache_value = true; + return MAX (start, rt->cache_start); + } + else + { + rt->cache_start = node_start; + rt->cache_end = ULONG_MAX; + rt->cache_value = false; + } + } + return ULONG_MAX; +} + +/* Recalculates the subtree_width of NODE based on its LEFT and + RIGHT children's "subtree_width"s. */ +static void +reaugment_range_tower_node (struct abt_node *node_, const void *aux UNUSED) +{ + struct range_tower_node *node = range_tower_node_from_abt_node (node_); + + node->subtree_width = node->n_zeros + node->n_ones; + if (node->abt_node.down[0] != NULL) + { + struct range_tower_node *left; + + left = range_tower_node_from_abt_node (node->abt_node.down[0]); + node->subtree_width += left->subtree_width; + } + if (node->abt_node.down[1] != NULL) + { + struct range_tower_node *right; + + right = range_tower_node_from_abt_node (node->abt_node.down[1]); + node->subtree_width += right->subtree_width; + } +} + +/* Deletes NODE from RT and frees it. */ +static void +delete_node (struct range_tower *rt, struct range_tower_node *node) +{ + abt_delete (&rt->abt, &node->abt_node); + free (node); +} + +struct range_tower_node * +range_tower_lookup (const struct range_tower *rt, unsigned long int position, + unsigned long int *node_start) +{ + const struct range_tower_node *node; + const struct abt_node *abt_node; + + abt_node = rt->abt.root; + node = range_tower_node_from_abt_node (abt_node); + *node_start = subtree_width (abt_node->down[0]); + for (;;) + { + unsigned long int left_width = subtree_width (abt_node->down[0]); + + if (position < left_width) + { + abt_node = abt_node->down[0]; + *node_start -= left_width - subtree_width (abt_node->down[0]); + } + else + { + unsigned long int node_width = node->n_zeros + node->n_ones; + + position -= left_width; + if (position < node_width) + return CONST_CAST (struct range_tower_node *, node); + + position -= node_width; + abt_node = abt_node->down[1]; + left_width = subtree_width (abt_node->down[0]); + *node_start += node_width + left_width; + } + node = range_tower_node_from_abt_node (abt_node); + } +} + +/* Destroys range tower RT. + Helper function for range_tower_create_pool. */ +static void +destroy_pool (void *rt_) +{ + struct range_tower *rt = rt_; + rt->pool = NULL; + range_tower_destroy (rt); +} diff --git a/src/libpspp/range-tower.h b/src/libpspp/range-tower.h new file mode 100644 index 0000000000..98c25183b5 --- /dev/null +++ b/src/libpspp/range-tower.h @@ -0,0 +1,250 @@ +/* PSPP - a program for statistical analysis. + Copyright (C) 2007, 2009, 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 . */ + +/* Bitmap, implemented as an augmented binary tree. + + Beyond the usual features of a bitmap, a range tower can efficiently + implement a "splice" operation that shifts ranges of bits left or right. + This feature does cost memory and time, so use a range tower only if this + feature is actually needed. Otherwise, use a range set (see range-set.h), + which can do everything that a range tower can do except the "splice" + operation. + + Each operation has O(lg N) cost, where N is the number of contiguous regions + of 1-bits in the bitmap. Also, a cache reduces the second and subsequent + containment tests within a single contiguous region to O(1). */ + +#ifndef LIBPSPP_RANGE_TOWER_H +#define LIBPSPP_RANGE_TOWER_H + +#include +#include +#include "libpspp/abt.h" +#include "libpspp/cast.h" + +/* A tower of ranges. */ +struct range_tower + { + struct pool *pool; /* Pool for freeing range_tower. */ + struct abt abt; /* Tree of range_tower_nodes. */ + + /* Cache. */ + unsigned long int cache_start; /* Start of region. */ + unsigned long int cache_end; /* One past end of region. */ + bool cache_value; /* Is the region in the tower? */ + }; + +/* A node in the range tower. */ +struct range_tower_node + { + struct abt_node abt_node; /* Augmented binary tree node. */ + unsigned long int n_zeros; /* Number of leading zeros. */ + unsigned long int n_ones; /* Number of ones following the zeros. */ + unsigned long int subtree_width; /* n_zeros + n_ones + sum of descendants. */ + }; + +struct range_tower *range_tower_create (void); +struct range_tower *range_tower_create_pool (struct pool *); +struct range_tower *range_tower_clone (const struct range_tower *, + struct pool *); +void range_tower_destroy (struct range_tower *); + +void range_tower_splice (struct range_tower *, + unsigned long int start, + unsigned long int old_width, + unsigned long int new_width); + +void range_tower_set1 (struct range_tower *, + unsigned long int start, unsigned long int width); +void range_tower_set0 (struct range_tower *, + unsigned long int start, unsigned long int width); + +void range_tower_insert1 (struct range_tower *, + unsigned long int start, unsigned long int width); +void range_tower_insert0 (struct range_tower *, + unsigned long int start, unsigned long int width); + +void range_tower_delete (struct range_tower *, + unsigned long int start, unsigned long int width); + +void range_tower_move (struct range_tower *, + unsigned long int old_start, + unsigned long int new_start, + unsigned long int width); + +bool range_tower_contains (const struct range_tower *, + unsigned long int position); +unsigned long int range_tower_scan (const struct range_tower *, + unsigned long int start); + +static inline bool range_tower_is_empty (const struct range_tower *); + +#define RANGE_TOWER_FOR_EACH(NODE, START, RANGE_TOWER) \ + for ((NODE) = range_tower_first (RANGE_TOWER), (START) = 0; \ + (NODE) && ((START) += (NODE)->n_zeros, true); \ + (START) += (NODE)->n_ones, \ + (NODE) = range_tower_next (RANGE_TOWER, NODE)) + +static inline const struct range_tower_node *range_tower_first ( + const struct range_tower *); +static inline const struct range_tower_node *range_tower_next ( + const struct range_tower *, const struct range_tower_node *); +static inline const struct range_tower_node *range_tower_last ( + const struct range_tower *); +static inline const struct range_tower_node *range_tower_prev ( + const struct range_tower *, const struct range_tower_node *); +unsigned long int range_tower_node_get_start (const struct range_tower_node *); +unsigned long int range_tower_node_get_end (const struct range_tower_node *); +static inline unsigned long int range_tower_node_get_width ( + const struct range_tower_node *); + +/* Inline functions. */ + +static inline struct range_tower_node *range_tower_node_from_abt__ ( + const struct abt_node *); +static inline struct range_tower_node *range_tower_next__ ( + const struct range_tower *, const struct range_tower_node *); +static inline struct range_tower_node *range_tower_first__ ( + const struct range_tower *); +static inline struct range_tower_node *range_tower_prev__ ( + const struct range_tower *, const struct range_tower_node *); +static inline struct range_tower_node *range_tower_last__ ( + const struct range_tower *); + +/* Returns true if RS contains no 1-bits, false otherwise. */ +static inline bool +range_tower_is_empty (const struct range_tower *rs) +{ + const struct range_tower_node *node = + abt_data (rs->abt.root, struct range_tower_node, abt_node); + + return node->n_zeros == ULONG_MAX; +} + +/* Returns the node representing the first contiguous region of + 1-bits in RS, or a null pointer if RS is empty. + Any call to range_tower_set1, range_tower_set0, or + range_tower_allocate invalidates the returned node. */ +static inline const struct range_tower_node * +range_tower_first (const struct range_tower *rs) +{ + const struct range_tower_node *node = range_tower_first__ (rs); + return node->n_ones ? node : NULL; +} + +/* If NODE is nonnull, returns the node representing the next + contiguous region of 1-bits in RS following NODE, or a null + pointer if NODE is the last region in RS. + If NODE is null, returns the first region in RS, as for + range_tower_first. + Any call to range_tower_set1, range_tower_set0, or + range_tower_allocate invalidates the returned node. */ +static inline const struct range_tower_node * +range_tower_next (const struct range_tower *rs, + const struct range_tower_node *node) +{ + if (node != NULL) + { + const struct range_tower_node *next = range_tower_next__ (rs, node); + return next != NULL && next->n_ones ? next : NULL; + } + else + return range_tower_first (rs); +} + +/* Returns the node representing the last contiguous region of + 1-bits in RS, or a null pointer if RS is empty. + Any call to range_tower_set1, range_tower_set0, or + range_tower_allocate invalidates the returned node. */ +static inline const struct range_tower_node * +range_tower_last (const struct range_tower *rs) +{ + const struct range_tower_node *node = range_tower_last__ (rs); + return node->n_ones ? node : range_tower_prev__(rs, node); +} + +/* If NODE is nonnull, returns the node representing the previous + contiguous region of 1-bits in RS following NODE, or a null + pointer if NODE is the first region in RS. + If NODE is null, returns the last region in RS, as for + range_tower_last. + Any call to range_tower_set1, range_tower_set0, or + range_tower_allocate invalidates the returned node. */ +static inline const struct range_tower_node * +range_tower_prev (const struct range_tower *rs, + const struct range_tower_node *node) +{ + return node != NULL ? range_tower_prev__ (rs, node) : range_tower_last (rs); +} + +/* Returns the number of contiguous 1-bits in NODE. */ +static inline unsigned long int +range_tower_node_get_width (const struct range_tower_node *node) +{ + return node->n_ones; +} + +/* Internal helper functions. */ + +/* Returns the range_tower_node corresponding to the given + ABT_NODE. Returns a null pointer if ABT_NODE is null. */ +static inline struct range_tower_node * +range_tower_node_from_abt__ (const struct abt_node *abt_node) +{ + return (abt_node + ? abt_data (abt_node, struct range_tower_node, abt_node) + : NULL); +} + +/* Returns the next range_tower_node in RS after NODE, + or a null pointer if NODE is the last node in RS. */ +static inline struct range_tower_node * +range_tower_next__ (const struct range_tower *rs, + const struct range_tower_node *node) +{ + return range_tower_node_from_abt__ (abt_next (&rs->abt, &node->abt_node)); +} + +/* Returns the first range_tower_node in RS, + or a null pointer if RS is empty. */ +static inline struct range_tower_node * +range_tower_first__ (const struct range_tower *rs) +{ + return range_tower_node_from_abt__ (abt_first (&rs->abt)); +} + +/* Returns the previous range_tower_node in RS after NODE, + or a null pointer if NODE is the first node in RS. */ +static inline struct range_tower_node * +range_tower_prev__ (const struct range_tower *rs, + const struct range_tower_node *node) +{ + return range_tower_node_from_abt__ (abt_prev (&rs->abt, &node->abt_node)); +} + +/* Returns the last range_tower_node in RS, + or a null pointer if RS is empty. */ +static inline struct range_tower_node * +range_tower_last__ (const struct range_tower *rs) +{ + return range_tower_node_from_abt__ (abt_last (&rs->abt)); +} + +struct range_tower_node *range_tower_lookup ( + const struct range_tower *, unsigned long int position, + unsigned long int *node_start); + +#endif /* libpspp/range-tower.h */ diff --git a/tests/automake.mk b/tests/automake.mk index 59d1977b95..ade39f9e7b 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -18,6 +18,7 @@ check_PROGRAMS += \ tests/libpspp/llx-test \ tests/libpspp/range-map-test \ tests/libpspp/range-set-test \ + tests/libpspp/range-tower-test \ tests/libpspp/sparse-array-test \ tests/libpspp/sparse-xarray-test \ tests/libpspp/str-test \ @@ -99,6 +100,11 @@ tests_libpspp_range_set_test_SOURCES = \ tests_libpspp_range_set_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10 tests_libpspp_range_set_test_LDADD = src/libpspp/liblibpspp.la gl/libgl.la +tests_libpspp_range_tower_test_SOURCES = \ + tests/libpspp/range-tower-test.c +tests_libpspp_range_tower_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10 +tests_libpspp_range_tower_test_LDADD = src/libpspp/libpspp.la gl/libgl.la + tests_libpspp_str_test_SOURCES = \ tests/libpspp/str-test.c tests_libpspp_str_test_LDADD = src/libpspp/liblibpspp.la gl/libgl.la @@ -318,6 +324,7 @@ TESTSUITE_AT = \ tests/libpspp/llx.at \ tests/libpspp/range-map.at \ tests/libpspp/range-set.at \ + tests/libpspp/range-tower.at \ tests/libpspp/sparse-array.at \ tests/libpspp/sparse-xarray-test.at \ tests/libpspp/str.at \ @@ -393,6 +400,7 @@ valgrind_wrappers = \ tests/valgrind/llx-test \ tests/valgrind/range-map-test \ tests/valgrind/range-set-test \ + tests/valgrind/range-tower-test \ tests/valgrind/sparse-array-test \ tests/valgrind/sparse-xarray-test \ tests/valgrind/str-test \ diff --git a/tests/libpspp/range-tower-test.c b/tests/libpspp/range-tower-test.c new file mode 100644 index 0000000000..f5da5e230e --- /dev/null +++ b/tests/libpspp/range-tower-test.c @@ -0,0 +1,658 @@ +/* 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 . */ + +/* 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 +#endif + +#include "libpspp/range-tower.h" + +#include +#include +#include +#include +#include + +#include "libpspp/compiler.h" +#include "libpspp/pool.h" + +#include "gl/minmax.h" +#include "gl/xalloc.h" + +/* 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__) + +/* 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; +} + +/* 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); +} + +/* 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; + } +} diff --git a/tests/libpspp/range-tower.at b/tests/libpspp/range-tower.at new file mode 100644 index 0000000000..77fccf2175 --- /dev/null +++ b/tests/libpspp/range-tower.at @@ -0,0 +1,15 @@ +AT_BANNER([range tower library]) + +m4_define([CHECK_RANGE_TOWER], + [AT_SETUP([range-tower -- $1]) + AT_CHECK([range-tower-test $1]) + AT_CLEANUP]) + +CHECK_RANGE_TOWER([set1]) +CHECK_RANGE_TOWER([set0]) +CHECK_RANGE_TOWER([insert0]) +CHECK_RANGE_TOWER([insert1]) +CHECK_RANGE_TOWER([delete]) +CHECK_RANGE_TOWER([move]) +CHECK_RANGE_TOWER([pool]) +CHECK_RANGE_TOWER([destroy-null]) -- 2.30.2