[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pspp-cvs] pspp src/libpspp/automake.mk src/libpspp/range-... [simpler-p
|
From: |
Ben Pfaff |
|
Subject: |
[Pspp-cvs] pspp src/libpspp/automake.mk src/libpspp/range-... [simpler-proc] |
|
Date: |
Mon, 02 Apr 2007 13:53:49 +0000 |
CVSROOT: /cvsroot/pspp
Module name: pspp
Branch: simpler-proc
Changes by: Ben Pfaff <blp> 07/04/02 13:53:49
Modified files:
src/libpspp : automake.mk range-map.h
tests : automake.mk
Added files:
src/libpspp : range-map.c
tests/libpspp : range-map-test.c
Log message:
Implement range_map data structure.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/automake.mk?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.22.2.6&r2=1.22.2.7
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/range-map.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/range-map.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.8&r2=1.27.2.9
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/libpspp/range-map-test.c?cvsroot=pspp&only_with_tag=simpler-proc&rev=1.1.2.1
Patches:
Index: src/libpspp/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/automake.mk,v
retrieving revision 1.22.2.6
retrieving revision 1.22.2.7
diff -u -b -r1.22.2.6 -r1.22.2.7
--- src/libpspp/automake.mk 1 Apr 2007 19:32:15 -0000 1.22.2.6
+++ src/libpspp/automake.mk 2 Apr 2007 13:53:49 -0000 1.22.2.7
@@ -47,6 +47,8 @@
src/libpspp/misc.h \
src/libpspp/pool.c \
src/libpspp/pool.h \
+ src/libpspp/range-map.c \
+ src/libpspp/range-map.h \
src/libpspp/range-set.c \
src/libpspp/range-set.h \
src/libpspp/sparse-array.c \
Index: src/libpspp/range-map.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/Attic/range-map.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-map.h 19 Mar 2007 21:36:24 -0000 1.1.2.1
+++ src/libpspp/range-map.h 2 Apr 2007 13:53:49 -0000 1.1.2.2
@@ -19,7 +19,22 @@
#ifndef LIBPSPP_RANGE_MAP_H
#define LIBPSPP_RANGE_MAP_H
-#include <libpspp/abt.h>
+/* Range map data structure, implemented as a balanced binary
+ tree.
+
+ This is a dictionary data structure that maps from contiguous
+ ranges of "unsigned long int" keys to arbitrary data
+ values.
+
+ The implementation is not robust against ranges that include
+ ULONG_MAX in their ranges. Such ranges are difficult to deal
+ with in C anyhow, because a range that includes 0 through
+ ULONG_MAX inclusive has a width of ULONG_MAX + 1, which equals
+ 0. */
+
+#include <stdbool.h>
+
+#include <libpspp/bt.h>
/* Returns the data structure corresponding to the given NODE,
assuming that NODE is embedded as the given MEMBER name in
@@ -27,38 +42,54 @@
#define range_map_data(NODE, STRUCT, MEMBER) \
((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
+/* A range map node, to be embedded in the data value. */
struct range_map_node
{
- struct abt_node abt_node;
- unsigned long subtree_min_width;
- unsigned long start;
- unsigned long width;
+ struct bt_node bt_node; /* Balanced tree node. */
+ unsigned long int start; /* Start of range. */
+ unsigned long int end; /* End of range, plus one. */
};
-unsigned long range_map_node_get_start (const struct range_map_node *);
-unsigned long range_map_node_get_end (const struct range_map_node *);
-unsigned long range_map_node_get_width (const struct range_map_node *);
+/* Returns the start of the range in the given NODE. */
+static inline unsigned long int
+range_map_node_get_start (const struct range_map_node *node)
+{
+ return node->start;
+}
+
+/* Returns the end of the range in the given NODE, plus one. */
+static inline unsigned long int
+range_map_node_get_end (const struct range_map_node *node)
+{
+ return node->end;
+}
+
+/* Returns the width of the range in the given NODE. */
+static inline unsigned long int
+range_map_node_get_width (const struct range_map_node *node)
+{
+ return node->end - node->start;
+}
+/* Range map. */
struct range_map
{
- struct abt abt;
+ struct bt bt;
};
void range_map_init (struct range_map *);
bool range_map_is_empty (const struct range_map *);
-struct range_map_node *range_map_lookup (const struct range_map *,
- unsigned long int position);
-void range_map_insert (struct range_map *, unsigned long int start,
- unsigned long int width,
+void range_map_insert (struct range_map *,
+ unsigned long int start, unsigned long int width,
struct range_map_node *new);
void range_map_delete (struct range_map *, struct range_map_node *);
-void range_map_resize (struct range_map *, struct range_map_node *,
- unsigned long new_width);
-struct range_map_node *range_map_first (struct range_map *);
-struct range_map_node *range_map_next (struct range_map *,
- struct range_map_node *);
+struct range_map_node *range_map_lookup (const struct range_map *,
+ unsigned long int position);
+struct range_map_node *range_map_first (const struct range_map *);
+struct range_map_node *range_map_next (const struct range_map *,
+ const struct range_map_node *);
#endif /* libpspp/range-map.h */
Index: tests/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/automake.mk,v
retrieving revision 1.27.2.8
retrieving revision 1.27.2.9
diff -u -b -r1.27.2.8 -r1.27.2.9
--- tests/automake.mk 1 Apr 2007 19:32:15 -0000 1.27.2.8
+++ tests/automake.mk 2 Apr 2007 13:53:49 -0000 1.27.2.9
@@ -132,14 +132,15 @@
tests/expressions/vectors.sh
nodist_TESTS = \
- tests/libpspp/ll-test \
- tests/libpspp/llx-test \
- tests/libpspp/heap-test \
tests/libpspp/abt-test \
tests/libpspp/bt-test \
+ tests/libpspp/heap-test \
+ tests/libpspp/ll-test \
+ tests/libpspp/llx-test \
+ tests/libpspp/range-map-test \
tests/libpspp/range-set-test \
- tests/libpspp/tower-test \
- tests/libpspp/sparse-array-test
+ tests/libpspp/sparse-array-test \
+ tests/libpspp/tower-test
TESTS = $(dist_TESTS) $(nodist_TESTS)
@@ -182,6 +183,15 @@
tests_libpspp_bt_test_LDADD = gl/libgl.a
tests_libpspp_bt_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10
+tests_libpspp_range_map_test_SOURCES = \
+ src/libpspp/bt.c \
+ src/libpspp/bt.h \
+ src/libpspp/range-map.c \
+ src/libpspp/range-map.h \
+ tests/libpspp/range-map-test.c
+tests_libpspp_range_map_test_LDADD = gl/libgl.a
+tests_libpspp_range_map_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10
+
tests_libpspp_range_set_test_SOURCES = \
src/libpspp/bt.c \
src/libpspp/bt.h \
Index: src/libpspp/range-map.c
===================================================================
RCS file: src/libpspp/range-map.c
diff -N src/libpspp/range-map.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/libpspp/range-map.c 2 Apr 2007 13:53:49 -0000 1.1.2.1
@@ -0,0 +1,158 @@
+/* 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. */
+
+#include <config.h>
+
+#include <libpspp/range-map.h>
+
+#include <libpspp/assertion.h>
+#include <libpspp/compiler.h>
+
+static struct range_map_node *bt_to_range_map_node (const struct bt_node *);
+static int compare_range_map_nodes (const struct bt_node *,
+ const struct bt_node *,
+ const void *aux);
+static struct range_map_node *first_node (const struct range_map *);
+static struct range_map_node *next_node (const struct range_map *,
+ const struct range_map_node *);
+static struct range_map_node *prev_node (const struct range_map *,
+ const struct range_map_node *) UNUSED;
+
+/* Initializes RM as an empty range map. */
+void
+range_map_init (struct range_map *rm)
+{
+ bt_init (&rm->bt, compare_range_map_nodes, NULL);
+}
+
+/* Returns true if RM contains no mappings,
+ false if it contains at least one. */
+bool
+range_map_is_empty (const struct range_map *rm)
+{
+ return bt_count (&rm->bt) == 0;
+}
+
+/* Inserts node NEW into RM, covering the range beginning at
+ START and ending at START + WIDTH (exclusive). WIDTH must be
+ at least 1. The new range must not overlap any existing range
+ already in RM. */
+void
+range_map_insert (struct range_map *rm,
+ unsigned long int start, unsigned long int width,
+ struct range_map_node *new)
+{
+ unsigned long int end = start + width;
+ struct range_map_node *dup;
+
+ assert (width > 0);
+ assert (end - 1 >= start);
+
+ new->start = start;
+ new->end = end;
+ dup = bt_to_range_map_node (bt_insert (&rm->bt, &new->bt_node));
+
+ /* Make sure NEW doesn't overlap any other node. */
+ assert (dup == NULL);
+ assert (prev_node (rm, new) == NULL || start >= prev_node (rm, new)->end);
+ assert (next_node (rm, new) == NULL || next_node (rm, new)->start >= end);
+}
+
+/* Deletes NODE from RM. */
+void
+range_map_delete (struct range_map *rm, struct range_map_node *node)
+{
+ bt_delete (&rm->bt, &node->bt_node);
+}
+
+/* Returns the node in RM that contains the given POSITION, or a
+ null pointer if no node contains POSITION. */
+struct range_map_node *
+range_map_lookup (const struct range_map *rm,
+ unsigned long int position)
+{
+ struct range_map_node tmp, *node;
+
+ tmp.start = position;
+ node = bt_to_range_map_node (bt_find_le (&rm->bt, &tmp.bt_node));
+ return node != NULL && position < node->end ? node : NULL;
+}
+
+/* Returns the first node in RM, or a null pointer if RM is
+ empty. */
+struct range_map_node *
+range_map_first (const struct range_map *rm)
+{
+ return first_node (rm);
+}
+
+/* If NODE is nonnull, returns the node in RM following NODE, or
+ a null pointer if NODE is the last node in RM.
+ If NODE is null, behaves like range_map_first. */
+struct range_map_node *
+range_map_next (const struct range_map *rm,
+ const struct range_map_node *node)
+{
+ return node != NULL ? next_node (rm, node) : first_node (rm);
+}
+
+/* Returns the range_map_node containing BT_NODE. */
+static struct range_map_node *
+bt_to_range_map_node (const struct bt_node *bt_node)
+{
+ return (bt_node != NULL
+ ? bt_data (bt_node, struct range_map_node, bt_node)
+ : NULL);
+}
+
+/* Compares range map nodes A and B and returns a strcmp()-type
+ result. */
+static int
+compare_range_map_nodes (const struct bt_node *a_,
+ const struct bt_node *b_,
+ const void *aux UNUSED)
+{
+ const struct range_map_node *a = bt_to_range_map_node (a_);
+ const struct range_map_node *b = bt_to_range_map_node (b_);
+ return a->start < b->start ? -1 : a->start > b->start;
+}
+
+/* Returns the first range map node in RM, or a null pointer if
+ RM is empty. */
+static struct range_map_node *
+first_node (const struct range_map *rm)
+{
+ return bt_to_range_map_node (bt_first (&rm->bt));
+}
+
+/* Returns the next range map node in RM following NODE, or a
+ null pointer if NODE is the last node in RM. */
+static struct range_map_node *
+next_node (const struct range_map *rm, const struct range_map_node *node)
+{
+ return bt_to_range_map_node (bt_next (&rm->bt, &node->bt_node));
+}
+
+/* Returns the previous range map node in RM preceding NODE, or a
+ null pointer if NODE is the first node in RM. */
+static struct range_map_node *
+prev_node (const struct range_map *rm, const struct range_map_node *node)
+{
+ return bt_to_range_map_node (bt_prev (&rm->bt, &node->bt_node));
+}
+
Index: tests/libpspp/range-map-test.c
===================================================================
RCS file: tests/libpspp/range-map-test.c
diff -N tests/libpspp/range-map-test.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/libpspp/range-map-test.c 2 Apr 2007 13:53:49 -0000 1.1.2.1
@@ -0,0 +1,515 @@
+/* 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-map.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-map.c routines.
+ (Without -DNDEBUG, branches caused by failed assertions will
+ not be taken.) "valgrind --leak-check=yes
+ --show-reachable=yes" should give a clean report, both with
+ and without -DNDEBUG. */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <libpspp/range-map.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__)
+
+/* Swaps *A and *B. */
+static void
+swap (int *a, int *b)
+{
+ int t = *a;
+ *a = *b;
+ *b = t;
+}
+
+/* Reverses the order of the CNT integers starting at VALUES. */
+static void
+reverse (int *values, size_t cnt)
+{
+ size_t i = 0;
+ size_t j = cnt;
+
+ while (j > i)
+ swap (&values[i++], &values[--j]);
+}
+
+/* Arranges the CNT blocks in VALUES into the lexicographically
+ next greater permutation. Returns true if successful.
+ If VALUES is already the lexicographically greatest
+ permutation of its blocks (i.e. ordered from greatest to
+ smallest), arranges them into the lexicographically least
+ permutation (i.e. ordered from smallest to largest) and
+ returns false. */
+static bool
+next_permutation (int *values, size_t cnt)
+{
+ if (cnt > 0)
+ {
+ size_t i = cnt - 1;
+ while (i != 0)
+ {
+ i--;
+ if (values[i] < values[i + 1])
+ {
+ size_t j;
+ for (j = cnt - 1; values[i] >= values[j]; j--)
+ continue;
+ swap (values + i, values + j);
+ reverse (values + (i + 1), cnt - (i + 1));
+ return true;
+ }
+ }
+
+ reverse (values, cnt);
+ }
+
+ return false;
+}
+
+/* Returns N!. */
+static unsigned int
+factorial (unsigned int n)
+{
+ unsigned int value = 1;
+ /* Disallow N values that overflow on 32-bit machines. */
+ assert (n <= 12);
+ for (; n > 1; )
+ value *= n--;
+ return value;
+}
+
+/* Tests whether PARTS is a K-part integer composition of N.
+ Returns true if so, false otherwise. */
+static bool UNUSED
+is_k_composition (int n, int k, const int parts[])
+{
+ int sum;
+ int i;
+
+ sum = 0;
+ for (i = 0; i < k; i++)
+ {
+ if (parts[i] < 1 || parts[i] > n)
+ return false;
+ sum += parts[i];
+ }
+ return sum == n;
+}
+
+/* Advances the K-part integer composition of N stored in PARTS
+ to the next lexicographically greater one.
+ Returns true if successful, false if the composition was
+ already the greatest K-part composition of N (in which case
+ PARTS is unaltered). */
+static bool
+next_k_composition (int n UNUSED, int k, int parts[])
+{
+ int x, i;
+
+ assert (is_k_composition (n, k, parts));
+ if (k == 1)
+ return false;
+
+ for (i = k - 1; i > 0; i--)
+ if (parts[i] > 1)
+ break;
+ if (i == 0)
+ return false;
+
+ x = parts[i] - 1;
+ parts[i] = 1;
+ parts[i - 1]++;
+ parts[k - 1] = x;
+
+ assert (is_k_composition (n, k, parts));
+ return true;
+}
+
+/* Sets the K integers in PARTS to the lexicographically first
+ K-part composition of N. */
+static void
+first_k_composition (int n, int k, int parts[])
+{
+ int i;
+
+ assert (n >= k);
+
+ for (i = 0; i < k; i++)
+ parts[i] = 1;
+ parts[k - 1] += n - k;
+}
+
+/* Advances *K and PARTS to the next integer composition of N.
+ Compositions are ordered from shortest to longest and in
+ lexicographical order within a given length.
+ Before the first call, initialize *K to 0.
+ After each successful call, *K contains the length of the
+ current composition and the *K blocks in PARTS contain its
+ parts.
+ Returns true if successful, false if the set of compositions
+ has been exhausted. */
+static bool
+next_composition (int n, int *k, int parts[])
+{
+ if (*k >= 1 && next_k_composition (n, *k, parts))
+ return true;
+ else if (*k < n)
+ {
+ first_k_composition (n, ++*k, parts);
+ return true;
+ }
+ else
+ return false;
+}
+
+/* Test data element. */
+struct element
+ {
+ struct range_map_node node; /* Embedded tower block. */
+ int x; /* Primary value. */
+ };
+
+static struct element *
+range_map_node_to_element (struct range_map_node *node)
+{
+ return range_map_data (node, struct element, node);
+}
+
+/* Element we expect to find. */
+struct expected_element
+ {
+ int x; /* Primary value. */
+ unsigned long int start; /* Start of region. */
+ unsigned long int end; /* End of region. */
+ };
+
+/* Compares expected_element A and B and returns a strcmp()-type
+ result. */
+static int
+compare_expected_element (const void *a_, const void *b_)
+{
+ const struct expected_element *a = (const struct expected_element *) a_;
+ const struct expected_element *b = (const struct expected_element *) b_;
+ return a->start < b->start ? -1 : a->start > b->start;
+}
+
+/* Checks that RM contains the ELEM_CNT elements described by
+ ELEMENTS[]. */
+static void
+check_range_map (struct range_map *rm,
+ struct expected_element elements[], size_t elem_cnt)
+{
+ struct expected_element *sorted;
+ struct range_map_node *node;
+ size_t i;
+
+ sorted = xnmalloc (elem_cnt, sizeof *sorted);
+ memcpy (sorted, elements, elem_cnt * sizeof *elements);
+ qsort (sorted, elem_cnt, sizeof *sorted, compare_expected_element);
+
+ check (range_map_is_empty (rm) == (elem_cnt == 0));
+
+ for (i = 0; i < elem_cnt; i++)
+ {
+ struct expected_element *e = &sorted[i];
+ unsigned long int position;
+
+ /* Check that range_map_lookup finds all the positions
+ within the element. */
+ for (position = e->start; position < e->end; position++)
+ {
+ struct range_map_node *found = range_map_lookup (rm, position);
+ check (found != NULL);
+ check (range_map_node_to_element (found)->x == e->x);
+ check (range_map_node_get_start (found) == e->start);
+ check (range_map_node_get_end (found) == e->end);
+ check (range_map_node_get_width (found) == e->end - e->start);
+ }
+
+ /* If there shouldn't be any elements in the positions just
+ before or after the element, verify that
+ range_map_lookup doesn't find any there. */
+ if (e->start > 0 && (i == 0 || e[-1].end < e->start))
+ check (range_map_lookup (rm, e->start - 1) == NULL);
+ if (i == elem_cnt - 1 || e->end < e[1].start)
+ check (range_map_lookup (rm, e->end) == NULL);
+ }
+
+ for (node = (rand () % 2 ? range_map_first (rm) : range_map_next (rm, NULL)),
+ i = 0;
+ node != NULL;
+ node = range_map_next (rm, node), i++)
+ {
+ struct expected_element *e = &sorted[i];
+ check (range_map_node_to_element (node)->x == e->x);
+ }
+ check (i == elem_cnt);
+
+ free (sorted);
+}
+
+/* Tests inserting all possible sets of ranges into a range map
+ in all possible orders, up to a specified maximum overall
+ range. */
+static void
+test_insert (void)
+{
+ const int max_range = 7;
+ int cnt;
+
+ for (cnt = 1; cnt <= max_range; cnt++)
+ {
+ unsigned int composition_cnt;
+ struct expected_element *expected;
+ int *widths;
+ int elem_cnt;
+ int *order;
+ struct element *elements;
+
+ expected = xnmalloc (cnt, sizeof *expected);
+ widths = xnmalloc (cnt, sizeof *widths);
+ order = xnmalloc (cnt, sizeof *order);
+ elements = xnmalloc (cnt, sizeof *elements);
+
+ elem_cnt = 0;
+ composition_cnt = 0;
+ while (next_composition (cnt, &elem_cnt, widths))
+ {
+ int i, j;
+ unsigned int permutation_cnt;
+
+ for (i = 0; i < elem_cnt; i++)
+ order[i] = i;
+
+ permutation_cnt = 0;
+ while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
+ {
+ struct range_map rm;
+
+ /* Inserts the elem_cnt elements with the given
+ widths[] into T in the order given by order[]. */
+ range_map_init (&rm);
+ for (i = 0; i < elem_cnt; i++)
+ {
+ unsigned long int start, end;
+ int idx;
+
+ idx = order[i];
+ elements[idx].x = idx;
+
+ /* Find start and end of element. */
+ start = 0;
+ for (j = 0; j < idx; j++)
+ start += widths[j];
+ end = start + widths[j];
+
+ /* Insert. */
+ range_map_insert (&rm, start, end - start,
+ &elements[idx].node);
+
+ /* Check map contents. */
+ expected[i].x = idx;
+ expected[i].start = start;
+ expected[i].end = end;
+ check_range_map (&rm, expected, i + 1);
+ }
+ permutation_cnt++;
+ }
+ check (permutation_cnt == factorial (elem_cnt));
+
+ composition_cnt++;
+ }
+ check (composition_cnt == 1 << (cnt - 1));
+
+ free (expected);
+ free (widths);
+ free (order);
+ free (elements);
+ }
+}
+
+/* Tests deleting ranges from a range map in all possible orders,
+ up to a specified maximum overall range. */
+static void
+test_delete (int gap)
+{
+ const int max_range = 7;
+ int cnt;
+
+ for (cnt = 1; cnt <= max_range; cnt++)
+ {
+ unsigned int composition_cnt;
+ struct expected_element *expected;
+ int *widths;
+ int elem_cnt;
+ int *order;
+ struct element *elements;
+
+ expected = xnmalloc (cnt, sizeof *expected);
+ widths = xnmalloc (cnt, sizeof *widths);
+ order = xnmalloc (cnt, sizeof *order);
+ elements = xnmalloc (cnt, sizeof *elements);
+
+ elem_cnt = 0;
+ composition_cnt = 0;
+ while (next_composition (cnt, &elem_cnt, widths))
+ {
+ int i, j;
+ unsigned int permutation_cnt;
+
+ for (i = 0; i < elem_cnt; i++)
+ order[i] = i;
+
+ permutation_cnt = 0;
+ while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
+ {
+ struct range_map rm;
+ unsigned long int start;
+
+ /* Insert all the elements. */
+ range_map_init (&rm);
+ start = 0;
+ for (i = 0; i < elem_cnt; i++)
+ {
+ int width = widths[i] > gap ? widths[i] - gap : widths[i];
+ unsigned long int end = start + width;
+
+ elements[i].x = i;
+ range_map_insert (&rm, start, end - start,
+ &elements[i].node);
+
+ for (j = 0; ; j++)
+ {
+ assert (j < elem_cnt);
+ if (order[j] == i)
+ {
+ expected[j].x = i;
+ expected[j].start = start;
+ expected[j].end = end;
+ break;
+ }
+ }
+
+ start += widths[i];
+ }
+ check_range_map (&rm, expected, elem_cnt);
+
+ /* Delete the elements in the specified order. */
+ for (i = 0; i < elem_cnt; i++)
+ {
+ range_map_delete (&rm, &elements[order[i]].node);
+ check_range_map (&rm, expected + i + 1, elem_cnt - i - 1);
+ }
+
+ permutation_cnt++;
+ }
+ check (permutation_cnt == factorial (elem_cnt));
+
+ composition_cnt++;
+ }
+ check (composition_cnt == 1 << (cnt - 1));
+
+ free (expected);
+ free (widths);
+ free (order);
+ free (elements);
+ }
+}
+
+/* Tests deleting ranges from a range map filled with contiguous
+ ranges in all possible orders, up to a specified maximum
+ overall range. */
+static void
+test_delete_contiguous (void)
+{
+ test_delete (0);
+}
+
+/* Tests deleting ranges from a range map filled with ranges
+ sometimes separated by gaps in all possible orders, up to a
+ specified maximum overall range. */
+static void
+test_delete_gaps (void)
+{
+ test_delete (1);
+}
+
+/* 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_contiguous, "delete from contiguous ranges");
+ run_test (test_delete_gaps, "delete from ranges separated by gaps");
+ putchar ('\n');
+
+ return 0;
+}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Pspp-cvs] pspp src/libpspp/automake.mk src/libpspp/range-... [simpler-proc],
Ben Pfaff <=