[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pspp-cvs] pspp tests/automake.mk src/libpspp/range-set.h ... [simpler-p
|
From: |
Ben Pfaff |
|
Subject: |
[Pspp-cvs] pspp tests/automake.mk src/libpspp/range-set.h ... [simpler-proc] |
|
Date: |
Fri, 30 Mar 2007 16:43:57 +0000 |
CVSROOT: /cvsroot/pspp
Module name: pspp
Branch: simpler-proc
Changes by: Ben Pfaff <blp> 07/03/30 16:43:57
Modified files:
tests : automake.mk
src/libpspp : range-set.h automake.mk
Added files:
tests/libpspp : range-set-test.c
src/libpspp : range-set.c
Log message:
Implement range_set.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/libpspp/range-set-test.c?cvsroot=pspp&only_with_tag=simpler-proc&rev=1.1.2.1
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/automake.mk?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.27.2.5&r2=1.27.2.6
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/range-set.h?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.1&r2=1.1.2.2
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/automake.mk?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.22.2.4&r2=1.22.2.5
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/range-set.c?cvsroot=pspp&only_with_tag=simpler-proc&rev=1.1.2.1
Patches:
Index: tests/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/automake.mk,v
retrieving revision 1.27.2.5
retrieving revision 1.27.2.6
diff -u -b -r1.27.2.5 -r1.27.2.6
--- tests/automake.mk 28 Mar 2007 04:58:42 -0000 1.27.2.5
+++ tests/automake.mk 30 Mar 2007 16:43:57 -0000 1.27.2.6
@@ -137,6 +137,7 @@
tests/libpspp/heap-test \
tests/libpspp/abt-test \
tests/libpspp/bt-test \
+ tests/libpspp/range-set-test \
tests/libpspp/sparse-array-test
TESTS = $(dist_TESTS) $(nodist_TESTS)
@@ -180,6 +181,15 @@
tests_libpspp_bt_test_LDADD = gl/libgl.a
tests_libpspp_bt_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10
+tests_libpspp_range_set_test_SOURCES = \
+ src/libpspp/bt.c \
+ src/libpspp/bt.h \
+ src/libpspp/range-set.c \
+ src/libpspp/range-set.h \
+ tests/libpspp/range-set-test.c
+tests_libpspp_range_set_test_LDADD = gl/libgl.a
+tests_libpspp_range_set_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10
+
tests_libpspp_sparse_array_test_SOURCES = \
src/libpspp/sparse-array.c \
src/libpspp/sparse-array.h \
Index: src/libpspp/range-set.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/Attic/range-set.h,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -u -b -r1.1.2.1 -r1.1.2.2
--- src/libpspp/range-set.h 19 Mar 2007 21:36:24 -0000 1.1.2.1
+++ src/libpspp/range-set.h 30 Mar 2007 16:43:57 -0000 1.1.2.2
@@ -16,6 +16,13 @@
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA. */
+/* Bitmap, implemented as a balanced binary tree.
+
+ 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_SET_H
#define LIBPSPP_RANGE_SET_H
@@ -30,11 +37,15 @@
unsigned long int start, unsigned long int width);
bool range_set_allocate (struct range_set *, unsigned long int request,
unsigned long int *start, unsigned long int *width);
-bool range_set_contains (struct range_set *, unsigned long int index);
+bool range_set_contains (const struct range_set *, unsigned long int position);
bool range_set_is_empty (const struct range_set *);
-struct range_set_node *range_set_first (struct range_set *);
-struct range_set_node *range_set_next (struct range_set *,
- struct range_set_node *);
+
+const struct range_set_node *range_set_first (const struct range_set *);
+const struct range_set_node *range_set_next (const struct range_set *,
+ const struct range_set_node *);
+unsigned long int range_set_node_get_start (const struct range_set_node *);
+unsigned long int range_set_node_get_end (const struct range_set_node *);
+unsigned long int range_set_node_get_width (const struct range_set_node *);
#endif /* libpspp/range-set.h */
Index: src/libpspp/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/automake.mk,v
retrieving revision 1.22.2.4
retrieving revision 1.22.2.5
diff -u -b -r1.22.2.4 -r1.22.2.5
--- src/libpspp/automake.mk 28 Mar 2007 17:26:48 -0000 1.22.2.4
+++ src/libpspp/automake.mk 30 Mar 2007 16:43:57 -0000 1.22.2.5
@@ -47,6 +47,8 @@
src/libpspp/misc.h \
src/libpspp/pool.c \
src/libpspp/pool.h \
+ src/libpspp/range-set.c \
+ src/libpspp/range-set.h \
src/libpspp/sparse-array.c \
src/libpspp/sparse-array.h \
src/libpspp/syntax-gen.c \
Index: tests/libpspp/range-set-test.c
===================================================================
RCS file: tests/libpspp/range-set-test.c
diff -N tests/libpspp/range-set-test.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/libpspp/range-set-test.c 30 Mar 2007 16:43:57 -0000 1.1.2.1
@@ -0,0 +1,309 @@
+/* PSPP - computes sample statistics.
+ Copyright (C) 2007 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 2 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, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
+
+/* This is a test program for the routines defined in
+ range-set.c. This test program aims to be as comprehensive as
+ possible. With -DNDEBUG, "gcov -b" should report 100%
+ coverage of lines and branches in heap.c routines. (Without
+ -DNDEBUG, branches caused by failed assertions will also 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-set.h>
+
+#include <assert.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <libpspp/compiler.h>
+
+#include "xalloc.h"
+
+/* Currently running test. */
+static const char *test_name;
+
+/* Exit with a failure code.
+ (Place a breakpoint on this function while debugging.) */
+static void
+check_die (void)
+{
+ exit (EXIT_FAILURE);
+}
+
+/* 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)
+ {
+ printf ("Check failed in %s test at %s, line %d\n",
+ test_name, __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;
+}
+
+/* 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))
+ printf (" (%lu,%lu)",
+ range_set_node_get_start (node), range_set_node_get_end (node));
+ printf ("\n");
+}
+
+/* Checks that the regions in RS match the bits in PATTERN. */
+static void
+check_pattern (const struct range_set *rs, unsigned int pattern)
+{
+ const struct range_set_node *node;
+ unsigned long int start, width;
+ int i;
+
+ for (node = rand () % 2 ? range_set_first (rs) : range_set_next (rs, NULL),
+ start = width = 0;
+ next_region (pattern, start + width, &start, &width);
+ node = range_set_next (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);
+
+ for (i = 0; i < UINT_BIT; i++)
+ check (range_set_contains (rs, i) == ((pattern & (1u << i)) != 0));
+ check (!range_set_contains (rs,
+ UINT_BIT + rand () % (ULONG_MAX - UINT_BIT)));
+
+ check (range_set_is_empty (rs) == (pattern == 0));
+}
+
+/* Creates and returns a range set that contains regions for the
+ bits set in PATTERN. */
+static struct range_set *
+make_pattern (unsigned int pattern)
+{
+ unsigned long int start = 0;
+ unsigned long int width = 0;
+ struct range_set *rs = range_set_create ();
+ while (next_region (pattern, start + width, &start, &width))
+ range_set_insert (rs, start, width);
+ check_pattern (rs, pattern);
+ return rs;
+}
+
+/* Returns an unsigned int with bits OFS...OFS+CNT (exclusive)
+ set to 1, other bits set 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 inserting all possible patterns into all possible range
+ sets (up to a small maximum number of bits). */
+static void
+test_insert (void)
+{
+ const int positions = 9;
+ unsigned int init_pat;
+ int i, j;
+
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (i = 0; i < positions + 1; i++)
+ for (j = i; j <= positions + 1; j++)
+ {
+ struct range_set *rs;
+ unsigned int final_pat;
+
+ rs = make_pattern (init_pat);
+ range_set_insert (rs, i, j - i);
+ final_pat = init_pat | bit_range (i, j - i);
+ check_pattern (rs, final_pat);
+ range_set_destroy (rs);
+ }
+}
+
+/* Tests deleting all possible patterns 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 i, j;
+
+ for (init_pat = 0; init_pat < (1u << positions); init_pat++)
+ for (i = 0; i < positions + 1; i++)
+ for (j = i; j <= positions + 1; j++)
+ {
+ struct range_set *rs;
+ unsigned int final_pat;
+
+ rs = make_pattern (init_pat);
+ range_set_delete (rs, i, j - i);
+ final_pat = init_pat & ~bit_range (i, j - i);
+ check_pattern (rs, final_pat);
+ range_set_destroy (rs);
+ }
+}
+
+/* Tests all possible allocation in all possible range sets (up
+ to a small maximum number of bits). */
+static void
+test_allocate (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, width, expect_start, expect_width;
+ bool success, expect_success;
+ unsigned int final_pat;
+ int i;
+
+ /* Figure out expected results. */
+ expect_success = false;
+ expect_start = expect_width = 0;
+ final_pat = init_pat;
+ for (i = 0; i < positions; i++)
+ if (init_pat & (1u << i))
+ {
+ expect_success = true;
+ expect_start = i;
+ expect_width = count_one_bits (init_pat >> i);
+ if (expect_width > request)
+ expect_width = request;
+ final_pat &= ~bit_range (expect_start, expect_width);
+ break;
+ }
+
+ /* Test. */
+ rs = make_pattern (init_pat);
+ success = range_set_allocate (rs, request, &start, &width);
+ check_pattern (rs, final_pat);
+ range_set_destroy (rs);
+
+ /* Check results. */
+ check (success == expect_success);
+ if (expect_success)
+ {
+ check (start == expect_start);
+ check (width == expect_width);
+ }
+ }
+}
+
+/* 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 ();
+}
+
+int
+main (void)
+{
+ run_test (test_insert, "insert");
+ run_test (test_delete, "delete");
+ run_test (test_allocate, "allocate");
+ putchar ('\n');
+
+ return 0;
+}
Index: src/libpspp/range-set.c
===================================================================
RCS file: src/libpspp/range-set.c
diff -N src/libpspp/range-set.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/libpspp/range-set.c 30 Mar 2007 16:43:57 -0000 1.1.2.1
@@ -0,0 +1,464 @@
+/* PSPP - computes sample statistics.
+ Copyright (C) 2007 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 2 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, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
+
+/* Bitmap, implemented as a balanced binary tree. */
+
+/* If you add routines in this file, please add a corresponding
+ test to range-set-test.c. This test program should achieve
+ 100% coverage of lines and branches in this code, as reported
+ by "gcov -b". */
+
+#include <config.h>
+
+#include <libpspp/range-set.h>
+
+#include <limits.h>
+#include <stdlib.h>
+
+#include <libpspp/assertion.h>
+#include <libpspp/bt.h>
+#include <libpspp/compiler.h>
+
+#include "xalloc.h"
+
+/* A set of ranges. */
+struct range_set
+ {
+ /* Tree of range_set_nodes. */
+ struct bt bt;
+
+ /* 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 set? */
+ };
+
+/* A node in the range set. */
+struct range_set_node
+ {
+ struct bt_node bt_node; /* Binary tree node. */
+ unsigned long int start; /* Start of region. */
+ unsigned long int end; /* One past end of region. */
+ };
+
+static struct range_set_node *bt_to_rs_node (const struct bt_node *);
+static int compare_range_set_nodes (const struct bt_node *,
+ const struct bt_node *,
+ const void *aux);
+static struct range_set_node *first_node (const struct range_set *);
+static struct range_set_node *next_node (const struct range_set *,
+ const struct range_set_node *);
+static void delete_node (struct range_set *, struct range_set_node *);
+static struct range_set_node *delete_node_get_next (struct range_set *,
+ struct range_set_node *);
+static struct range_set_node *find_node_le (const struct range_set *,
+ unsigned long int position);
+static struct range_set_node *insert_node (struct range_set *,
+ unsigned long int start,
+ unsigned long int end);
+static void insert_just_before (struct range_set *,
+ unsigned long int start, unsigned long int end,
+ struct range_set_node *);
+static void merge_node_with_successors (struct range_set *,
+ struct range_set_node *);
+
+/* Creates and returns a new, empty range set. */
+struct range_set *
+range_set_create (void)
+{
+ struct range_set *rs = xmalloc (sizeof *rs);
+ bt_init (&rs->bt, compare_range_set_nodes, NULL);
+ rs->cache_end = 0;
+ return rs;
+}
+
+/* Destroys range set RS. */
+void
+range_set_destroy (struct range_set *rs)
+{
+ while (!range_set_is_empty (rs))
+ delete_node (rs, first_node (rs));
+ free (rs);
+}
+
+/* Inserts the region starting at START and extending for WIDTH
+ into RS. */
+void
+range_set_insert (struct range_set *rs,
+ unsigned long int start, unsigned long int width)
+{
+ unsigned long int end = start + width;
+ struct range_set_node *node;
+
+ assert (width == 0 || start + width - 1 >= start);
+
+ if (width == 0)
+ return;
+
+ /* Invalidate cache. */
+ rs->cache_end = 0;
+
+ node = find_node_le (rs, start);
+ if (node != NULL)
+ {
+ if (start > node->end)
+ {
+ /* New region does not overlap NODE, but it might
+ overlap the next node. */
+ insert_just_before (rs, start, end, next_node (rs, node));
+ }
+ else if (end > node->end)
+ {
+ /* New region starts in the middle of NODE and
+ continues past its end, so extend NODE, then merge
+ it with any following node that it now potentially
+ overlaps. */
+ node->end = end;
+ merge_node_with_successors (rs, node);
+ }
+ else
+ {
+ /* New region is completely contained by NODE, so
+ there's nothing to do. */
+ }
+ }
+ else
+ {
+ /* New region starts before any existing region, but it
+ might overlap the first region. */
+ insert_just_before (rs, start, end, first_node (rs));
+ }
+}
+
+/* Inserts the region starting at START and extending for WIDTH
+ from RS. */
+void
+range_set_delete (struct range_set *rs,
+ unsigned long int start, unsigned long int width)
+{
+ unsigned long int end = start + width;
+ struct range_set_node *node;
+
+ assert (width == 0 || start + width - 1 >= start);
+
+ if (width == 0)
+ return;
+
+ /* Invalidate cache. */
+ rs->cache_end = 0;
+
+ node = find_node_le (rs, start);
+ if (node == NULL)
+ node = first_node (rs);
+
+ while (node != NULL && end > node->start)
+ {
+ if (start <= node->start)
+ {
+ if (end >= node->end)
+ {
+ /* Region to delete covers entire node. */
+ node = delete_node_get_next (rs, node);
+ }
+ else
+ {
+ /* Region to delete covers only left part of node. */
+ node->start = end;
+ break;
+ }
+ }
+ else if (start < node->end)
+ {
+ if (end < node->end)
+ {
+ /* Region to delete covers middle of the node, so
+ we have to split the node into two pieces. */
+ unsigned long int old_node_end = node->end;
+ node->end = start;
+ insert_node (rs, end, old_node_end);
+ break;
+ }
+ else
+ {
+ /* Region to delete covers only right part of
+ node. */
+ node->end = start;
+ node = next_node (rs, node);
+ }
+ }
+ else
+ node = next_node (rs, node);
+ }
+}
+
+/* Scans RS for its first 1-bit and deletes up to REQUEST
+ contiguous 1-bits starting at that position. Unless RS is
+ completely empty, sets *START to the position of the first
+ 1-bit deleted and *WIDTH to the number actually deleted, which
+ may be less than REQUEST if fewer contiguous 1-bits were
+ present, and returns true. If RS is completely empty, returns
+ false. */
+bool
+range_set_allocate (struct range_set *rs, unsigned long int request,
+ unsigned long int *start, unsigned long int *width)
+{
+ struct range_set_node *node;
+ unsigned long int node_width;
+
+ assert (request > 0);
+
+ node = first_node (rs);
+ if (node == NULL)
+ return false;
+ node_width = node->end - node->start;
+
+ *start = node->start;
+ if (request < node_width)
+ {
+ *width = request;
+ node->start += request;
+ }
+ else
+ {
+ *width = node_width;
+ delete_node (rs, node);
+ }
+
+ rs->cache_end = 0;
+
+ return true;
+}
+
+/* Returns true if there is a 1-bit at the given POSITION in RS,
+ false otherwise. */
+bool
+range_set_contains (const struct range_set *rs_, unsigned long int position)
+{
+ struct range_set *rs = (struct range_set *) rs_;
+ if (position < rs->cache_end && position >= rs->cache_start)
+ return rs->cache_value;
+ else
+ {
+ struct range_set_node *node = find_node_le (rs, position);
+ if (node != NULL)
+ {
+ if (position < node->end)
+ {
+ rs->cache_start = node->start;
+ rs->cache_end = node->end;
+ rs->cache_value = true;
+ return true;
+ }
+ else
+ {
+ struct range_set_node *next = next_node (rs, node);
+ rs->cache_start = node->end;
+ rs->cache_end = next != NULL ? next->start : ULONG_MAX;
+ rs->cache_value = false;
+ return false;
+ }
+ }
+ else
+ {
+ node = first_node (rs);
+ rs->cache_start = 0;
+ rs->cache_end = node != NULL ? node->start : ULONG_MAX;
+ rs->cache_value = false;
+ return false;
+ }
+ }
+}
+
+/* Returns true if RS contains no 1-bits, false otherwise. */
+bool
+range_set_is_empty (const struct range_set *rs)
+{
+ return bt_count (&rs->bt) == 0;
+}
+
+/* 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_set_insert, range_set_delete, or
+ range_set_allocate invalidates the returned node. */
+const struct range_set_node *
+range_set_first (const struct range_set *rs)
+{
+ return first_node (rs);
+}
+
+/* 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_set_first.
+ Any call to range_set_insert, range_set_delete, or
+ range_set_allocate invalidates the returned node. */
+const struct range_set_node *
+range_set_next (const struct range_set *rs, const struct range_set_node *node)
+{
+ return (node != NULL
+ ? next_node (rs, (struct range_set_node *) node)
+ : first_node (rs));
+}
+
+/* Returns the position of the first 1-bit in NODE. */
+unsigned long int
+range_set_node_get_start (const struct range_set_node *node)
+{
+ return node->start;
+}
+
+/* Returns one past the position of the last 1-bit in NODE. */
+unsigned long int
+range_set_node_get_end (const struct range_set_node *node)
+{
+ return node->end;
+}
+
+/* Returns the number of contiguous 1-bits in NODE. */
+unsigned long int
+range_set_node_get_width (const struct range_set_node *node)
+{
+ return node->end - node->start;
+}
+
+/* Returns the range_set_node corresponding to the given
+ BT_NODE. Returns a null pointer if BT_NODE is null. */
+static struct range_set_node *
+bt_to_rs_node (const struct bt_node *bt_node)
+{
+ return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
+}
+
+/* Compares `range_set_node's A and B and returns a strcmp-like
+ return value. */
+static int
+compare_range_set_nodes (const struct bt_node *a_,
+ const struct bt_node *b_,
+ const void *aux UNUSED)
+{
+ const struct range_set_node *a = bt_to_rs_node (a_);
+ const struct range_set_node *b = bt_to_rs_node (b_);
+
+ return a->start < b->start ? -1 : a->start > b->start;
+}
+
+/* Returns the first range_set_node in RS,
+ or a null pointer if RS is empty. */
+static struct range_set_node *
+first_node (const struct range_set *rs)
+{
+ return bt_to_rs_node (bt_first (&rs->bt));
+}
+
+/* Returns the next range_set_node in RS after NODE,
+ or a null pointer if NODE is the last node in RS. */
+static struct range_set_node *
+next_node (const struct range_set *rs, const struct range_set_node *node)
+{
+ return bt_to_rs_node (bt_next (&rs->bt, &node->bt_node));
+}
+
+/* Deletes NODE from RS and frees it. */
+static void
+delete_node (struct range_set *rs, struct range_set_node *node)
+{
+ bt_delete (&rs->bt, &node->bt_node);
+ free (node);
+}
+
+/* Deletes NODE from RS, frees it, and returns the following
+ node. */
+static struct range_set_node *
+delete_node_get_next (struct range_set *rs, struct range_set_node *node)
+{
+ struct range_set_node *next = next_node (rs, node);
+ delete_node (rs, node);
+ return next;
+}
+
+/* Returns the node in RS that would be just before POSITION if a
+ range_set_node with `start' as POSITION were inserted.
+ Returns a null pointer if POSITION is before any existing node
+ in RS. If POSITION would duplicate an existing region's
+ start, returns that region. */
+static struct range_set_node *
+find_node_le (const struct range_set *rs, unsigned long int position)
+{
+ struct range_set_node tmp;
+ tmp.start = position;
+ return bt_to_rs_node (bt_find_le (&rs->bt, &tmp.bt_node));
+}
+
+/* Creates a new region with the given START and END, inserts the
+ region into RS, and returns the new region. */
+static struct range_set_node *
+insert_node (struct range_set *rs,
+ unsigned long int start, unsigned long int end)
+{
+ struct range_set_node *node = xmalloc (sizeof *node);
+ struct bt_node *dummy;
+ node->start = start;
+ node->end = end;
+ dummy = bt_insert (&rs->bt, &node->bt_node);
+ assert (dummy == NULL);
+ return node;
+}
+
+/* Inserts the region START...END (exclusive) into RS given that
+ the new region is "just before" NODE, that is, if NODE is
+ nonnull, the new region is known not to overlap any node
+ preceding NODE, and START precedes NODE's start; if NODE is
+ null, then the new region is known to follow any and all
+ regions already in RS. */
+static void
+insert_just_before (struct range_set *rs,
+ unsigned long int start, unsigned long int end,
+ struct range_set_node *node)
+{
+ assert (node == NULL || start < node->start);
+ if (node != NULL && end >= node->start)
+ {
+ /* New region overlaps NODE, so just extend NODE. */
+ node->start = start;
+ if (end > node->end)
+ {
+ node->end = end;
+ merge_node_with_successors (rs, node);
+ }
+ }
+ else
+ {
+ /* New region does not overlap NODE. */
+ insert_node (rs, start, end);
+ }
+}
+
+/* Merges NODE in RS with its successors. */
+static void
+merge_node_with_successors (struct range_set *rs, struct range_set_node *node)
+{
+ struct range_set_node *next;
+
+ while ((next = next_node (rs, node)) != NULL && node->end >= next->start)
+ {
+ if (next->end > node->end)
+ node->end = next->end;
+ delete_node (rs, next);
+ }
+}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Pspp-cvs] pspp tests/automake.mk src/libpspp/range-set.h ... [simpler-proc],
Ben Pfaff <=