[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pspp-cvs] pspp src/data/datasheet.c src/libpspp/automake.... [simpler-p
|
From: |
Ben Pfaff |
|
Subject: |
[Pspp-cvs] pspp src/data/datasheet.c src/libpspp/automake.... [simpler-proc] |
|
Date: |
Sun, 01 Apr 2007 19:32:15 +0000 |
CVSROOT: /cvsroot/pspp
Module name: pspp
Branch: simpler-proc
Changes by: Ben Pfaff <blp> 07/04/01 19:32:15
Modified files:
src/data : datasheet.c
src/libpspp : automake.mk
tests : automake.mk
Added files:
src/libpspp : tower.c tower.h
tests/libpspp : tower-test.c
Removed files:
src/libpspp : fat-array.h
Log message:
Implement "tower" data structure (renamed from "fat array").
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/datasheet.c?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.2&r2=1.1.2.3
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/automake.mk?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.22.2.5&r2=1.22.2.6
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/tower.c?cvsroot=pspp&only_with_tag=simpler-proc&rev=1.1.2.1
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/tower.h?cvsroot=pspp&only_with_tag=simpler-proc&rev=1.1.2.1
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/fat-array.h?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.1&r2=0
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/automake.mk?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.27.2.7&r2=1.27.2.8
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/libpspp/tower-test.c?cvsroot=pspp&only_with_tag=simpler-proc&rev=1.1.2.1
Patches:
Index: src/data/datasheet.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/Attic/datasheet.c,v
retrieving revision 1.1.2.2
retrieving revision 1.1.2.3
diff -u -b -r1.1.2.2 -r1.1.2.3
--- src/data/datasheet.c 22 Mar 2007 04:12:59 -0000 1.1.2.2
+++ src/data/datasheet.c 1 Apr 2007 19:32:15 -0000 1.1.2.3
@@ -27,10 +27,10 @@
#include <data/case-tmpfile.h>
#include <data/settings.h>
#include <libpspp/assertion.h>
-#include <libpspp/fat-array.h>
#include <libpspp/range-map.h>
#include <libpspp/range-set.h>
#include <libpspp/sparse-array.h>
+#include <libpspp/tower.h>
#include "xalloc.h"
@@ -420,28 +420,28 @@
struct axis
{
- struct fat_array log_to_phy;
+ struct tower log_to_phy;
struct range_set *available;
unsigned long int phy_size;
};
struct axis_group
{
- struct fat_array_node logical;
+ struct tower_node logical;
unsigned long phy_start;
};
static struct axis_group *
-axis_group_from_fat_array_node (struct fat_array_node *node)
+axis_group_from_tower_node (struct tower_node *node)
{
- return fat_array_data (node, struct axis_group, logical);
+ return tower_data (node, struct axis_group, logical);
}
struct axis *
axis_create (void)
{
struct axis *axis = xmalloc (sizeof *axis);
- fat_array_init (&axis->log_to_phy);
+ tower_init (&axis->log_to_phy);
axis->available = range_set_create ();
axis->phy_size = 0;
return axis;
@@ -453,12 +453,12 @@
if (axis == NULL)
return;
- while (!fat_array_is_empty (&axis->log_to_phy))
+ while (!tower_is_empty (&axis->log_to_phy))
{
- struct fat_array_node *node = fat_array_first (&axis->log_to_phy);
- struct axis_group *group = fat_array_data (node, struct axis_group,
+ struct tower_node *node = tower_first (&axis->log_to_phy);
+ struct axis_group *group = tower_data (node, struct axis_group,
logical);
- fat_array_delete (&axis->log_to_phy, node);
+ tower_delete (&axis->log_to_phy, node);
free (group);
}
@@ -484,22 +484,22 @@
unsigned long int
axis_map (const struct axis *axis, unsigned long log_pos)
{
- struct fat_array_node *node;
+ struct tower_node *node;
struct axis_group *group;
unsigned long int group_start;
- node = fat_array_lookup (&axis->log_to_phy, log_pos, &group_start);
- group = fat_array_data (node, struct axis_group, logical);
+ node = tower_lookup (&axis->log_to_phy, log_pos, &group_start);
+ group = tower_data (node, struct axis_group, logical);
return group->phy_start + (log_pos - group_start);
}
unsigned long
axis_get_size (const struct axis *axis)
{
- return fat_array_size (&axis->log_to_phy);
+ return tower_height (&axis->log_to_phy);
}
-static struct fat_array_node *
+static struct tower_node *
make_axis_group (unsigned long phy_start)
{
struct axis_group *group = xmalloc (sizeof *group);
@@ -507,26 +507,26 @@
return &group->logical;
}
-static struct fat_array_node *
+static struct tower_node *
split_axis (struct axis *axis, unsigned long int where)
{
unsigned long int group_start;
- struct fat_array_node *group_node;
+ struct tower_node *group_node;
struct axis_group *group;
- group_node = fat_array_lookup (&axis->log_to_phy, where, &group_start);
+ group_node = tower_lookup (&axis->log_to_phy, where, &group_start);
if (group_node == NULL)
return NULL;
- group = axis_group_from_fat_array_node (group_node);
+ group = axis_group_from_tower_node (group_node);
if (where > group_start)
{
unsigned long int size_1 = where - group_start;
- unsigned long int size_2 = fat_array_node_get_width (group_node) -
size_1;
- struct fat_array_node *next = fat_array_next (&axis->log_to_phy,
group_node);
- struct fat_array_node *new = make_axis_group (group->phy_start + size_1);
- fat_array_resize (&axis->log_to_phy, group_node, size_1);
- fat_array_insert (&axis->log_to_phy, size_2, new, next);
+ unsigned long int size_2 = tower_node_get_height (group_node) - size_1;
+ struct tower_node *next = tower_next (&axis->log_to_phy, group_node);
+ struct tower_node *new = make_axis_group (group->phy_start + size_1);
+ tower_resize (&axis->log_to_phy, group_node, size_1);
+ tower_insert (&axis->log_to_phy, size_2, new, next);
return new;
}
else
@@ -538,9 +538,9 @@
unsigned long int log_start, unsigned long int phy_start,
unsigned long int cnt)
{
- struct fat_array_node *before = split_axis (axis, log_start);
- struct fat_array_node *new = make_axis_group (phy_start);
- fat_array_insert (&axis->log_to_phy, cnt, new, before);
+ struct tower_node *before = split_axis (axis, log_start);
+ struct tower_node *new = make_axis_group (phy_start);
+ tower_insert (&axis->log_to_phy, cnt, new, before);
}
void
@@ -549,12 +549,12 @@
{
if (cnt > 0)
{
- struct fat_array_node *last = split_axis (axis, start + cnt);
- struct fat_array_node *cur, *next;
+ struct tower_node *last = split_axis (axis, start + cnt);
+ struct tower_node *cur, *next;
for (cur = split_axis (axis, start); cur != last; cur = next)
{
- next = fat_array_delete (&axis->log_to_phy, cur);
- free (axis_group_from_fat_array_node (cur));
+ next = tower_delete (&axis->log_to_phy, cur);
+ free (axis_group_from_tower_node (cur));
}
}
}
@@ -566,18 +566,17 @@
{
if (cnt > 0 && old_start != new_start)
{
- struct fat_array_node *old_first, *old_last, *new_first;
- struct fat_array tmp_array;
+ struct tower_node *old_first, *old_last, *new_first;
+ struct tower tmp_array;
old_first = split_axis (axis, old_start);
old_last = split_axis (axis, old_start + cnt);
- fat_array_init (&tmp_array);
- fat_array_splice (&tmp_array, NULL,
+ tower_init (&tmp_array);
+ tower_splice (&tmp_array, NULL,
&axis->log_to_phy, old_first, old_last);
new_first = split_axis (axis, new_start);
- fat_array_splice (&axis->log_to_phy, new_first,
- &tmp_array, old_first, NULL);
+ tower_splice (&axis->log_to_phy, new_first, &tmp_array, old_first, NULL);
}
}
Index: src/libpspp/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/automake.mk,v
retrieving revision 1.22.2.5
retrieving revision 1.22.2.6
diff -u -b -r1.22.2.5 -r1.22.2.6
--- src/libpspp/automake.mk 30 Mar 2007 16:43:57 -0000 1.22.2.5
+++ src/libpspp/automake.mk 1 Apr 2007 19:32:15 -0000 1.22.2.6
@@ -59,6 +59,8 @@
src/libpspp/start-date.h \
src/libpspp/str.c \
src/libpspp/str.h \
+ src/libpspp/tower.c \
+ src/libpspp/tower.h \
src/libpspp/verbose-msg.c \
src/libpspp/verbose-msg.h \
src/libpspp/version.h
Index: tests/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/automake.mk,v
retrieving revision 1.27.2.7
retrieving revision 1.27.2.8
diff -u -b -r1.27.2.7 -r1.27.2.8
--- tests/automake.mk 31 Mar 2007 03:31:57 -0000 1.27.2.7
+++ tests/automake.mk 1 Apr 2007 19:32:15 -0000 1.27.2.8
@@ -138,6 +138,7 @@
tests/libpspp/abt-test \
tests/libpspp/bt-test \
tests/libpspp/range-set-test \
+ tests/libpspp/tower-test \
tests/libpspp/sparse-array-test
TESTS = $(dist_TESTS) $(nodist_TESTS)
@@ -192,6 +193,17 @@
tests_libpspp_range_set_test_LDADD = gl/libgl.a @LIBINTL@
tests_libpspp_range_set_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10
+tests_libpspp_tower_test_SOURCES = \
+ src/libpspp/abt.c \
+ src/libpspp/abt.h \
+ src/libpspp/pool.c \
+ src/libpspp/pool.h \
+ src/libpspp/tower.c \
+ src/libpspp/tower.h \
+ tests/libpspp/tower-test.c
+tests_libpspp_tower_test_LDADD = gl/libgl.a @LIBINTL@
+tests_libpspp_tower_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/tower.c
===================================================================
RCS file: src/libpspp/tower.c
diff -N src/libpspp/tower.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/libpspp/tower.c 1 Apr 2007 19:32:15 -0000 1.1.2.1
@@ -0,0 +1,225 @@
+/* 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/tower.h>
+
+#include <libpspp/assertion.h>
+#include <libpspp/compiler.h>
+
+static struct tower_node *abt_to_tower_node (const struct abt_node *);
+static struct tower_node *first_node (const struct tower *);
+static struct tower_node *next_node (const struct tower *,
+ const struct tower_node *);
+static unsigned long int get_subtree_height (const struct abt_node *);
+static void reaugment_tower_node (struct abt_node *,
+ const struct abt_node *,
+ const struct abt_node *,
+ const void *aux);
+
+/* Initializes T as an empty tower. */
+void
+tower_init (struct tower *t)
+{
+ abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
+}
+
+/* Returns true if T contains no nodes, false otherwise. */
+bool
+tower_is_empty (const struct tower *t)
+{
+ return t->abt.root == NULL;
+}
+
+/* Returns the total height of tower T. */
+unsigned long
+tower_height (const struct tower *t)
+{
+ return get_subtree_height (t->abt.root);
+}
+
+/* Inserts node NEW with the specified HEIGHT into T just below
+ node UNDER, or at the top of T if UNDER is a null pointer. */
+void
+tower_insert (struct tower *t, unsigned long height, struct tower_node *new,
+ struct tower_node *under)
+{
+ assert (height > 0);
+ new->height = height;
+ abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
+ &new->abt_node);
+}
+
+/* Deletes NODE from tower T. */
+struct tower_node *
+tower_delete (struct tower *t, struct tower_node *node)
+{
+ struct tower_node *next = next_node (t, node);
+ abt_delete (&t->abt, &node->abt_node);
+ return next;
+}
+
+/* Changes the height of NODE in tower T to NEW_HEIGHT. */
+void
+tower_resize (struct tower *t, struct tower_node *node,
+ unsigned long new_height)
+{
+ assert (new_height > 0);
+ node->height = new_height;
+ abt_reaugmented (&t->abt, &node->abt_node);
+}
+
+/* Removes nodes FIRST through LAST (exclusive) from tower SRC
+ and splices them into tower DST just below node UNDER, or at
+ the top of DST if UNDER is a null pointer.
+
+ It might be better to implement an abt_splice function and
+ turn this into a wrapper, but the asymptotic performance would
+ be the same. */
+void
+tower_splice (struct tower *dst, struct tower_node *under,
+ struct tower *src,
+ struct tower_node *first, struct tower_node *last)
+{
+ struct tower_node *next;
+
+ /* Conceptually, DST == SRC is valid.
+ Practically, it's more difficult to get it right, and our
+ client code doesn't need it. */
+ assert (dst != src);
+
+ for (; first != last; first = next)
+ {
+ next = tower_delete (src, first);
+ abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
+ &first->abt_node);
+ }
+}
+
+/* Returns the node at the given HEIGHT from the bottom of tower
+ T. HEIGHT must be less than T's height (as returned by
+ tower_height). Stores in *NODE_START the height of the bottom
+ of the returned node, which may be less than HEIGHT if HEIGHT
+ refers to the middle of a node instead of its bottom. */
+struct tower_node *
+tower_lookup (const struct tower *t,
+ unsigned long height,
+ unsigned long *node_start)
+{
+ struct abt_node *p;
+
+ assert (height < tower_height (t));
+
+ *node_start = 0;
+ p = t->abt.root;
+ for (;;)
+ {
+ unsigned long left_height = get_subtree_height (p->down[0]);
+ if (height < left_height)
+ {
+ /* Our goal height must lie within the left subtree. */
+ p = p->down[0];
+ }
+ else
+ {
+ /* Our goal height cannot be in the left subtree. */
+ struct tower_node *node = abt_to_tower_node (p);
+ unsigned long int node_height = node->height;
+
+ height -= left_height;
+ *node_start += left_height;
+ if (height < node_height)
+ {
+ /* Our goal height is in P. */
+ return node;
+ }
+ else
+ {
+ /* Our goal height is in the right subtree. */
+ p = p->down[1];
+ height -= node_height;
+ *node_start += node_height;
+ }
+ }
+ }
+}
+
+/* Returns the node at height 0 in tower T, or a null pointer if
+ T is empty. */
+struct tower_node *
+tower_first (const struct tower *t)
+{
+ return first_node (t);
+}
+
+/* If NODE is nonnull, returns the node just above NODE in tower
+ T, or a null pointer if NODE is the topmost node in T.
+ If NODE is null, acts like tower_first. */
+struct tower_node *
+tower_next (const struct tower *t, const struct tower_node *node)
+{
+ return node != NULL ? next_node (t, node) : first_node (t);
+}
+
+/* Returns the tower node corresponding to the given ABT_NODE. */
+static struct tower_node *
+abt_to_tower_node (const struct abt_node *abt_node)
+{
+ return abt_data (abt_node, struct tower_node, abt_node);
+}
+
+/* Returns the first node in TOWER. */
+static struct tower_node *
+first_node (const struct tower *t)
+{
+ struct abt_node *abt_node = abt_first (&t->abt);
+ return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
+}
+
+/* Returns the next node in TOWER after NODE. */
+static struct tower_node *
+next_node (const struct tower *t, const struct tower_node *node)
+{
+ struct abt_node *abt_node = abt_next (&t->abt, &node->abt_node);
+ return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
+}
+
+/* Returns the total height of the nodes in the subtree rooted at
+ P, or 0 if P is null. */
+static unsigned long int
+get_subtree_height (const struct abt_node *p)
+{
+ return p != NULL ? abt_to_tower_node (p)->subtree_height : 0;
+}
+
+/* Recalculates the subtree_height of NODE based on its LEFT and
+ RIGHT children's subtree_heights. */
+static void
+reaugment_tower_node (struct abt_node *node_,
+ const struct abt_node *left,
+ const struct abt_node *right,
+ const void *aux UNUSED)
+{
+ struct tower_node *node = abt_to_tower_node (node_);
+ node->subtree_height = node->height;
+ if (left != NULL)
+ node->subtree_height += abt_to_tower_node (left)->subtree_height;
+ if (right != NULL)
+ node->subtree_height += abt_to_tower_node (right)->subtree_height;
+}
Index: src/libpspp/tower.h
===================================================================
RCS file: src/libpspp/tower.h
diff -N src/libpspp/tower.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/libpspp/tower.h 1 Apr 2007 19:32:15 -0000 1.1.2.1
@@ -0,0 +1,101 @@
+/* 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. */
+
+/* "Tower" data structure, implemented as an augmented binary
+ tree.
+
+ Imagine a tall stack of books on a table; actually, call it a
+ "tower" of books because "stack" is already taken. If you're
+ careful enough and strong enough, you can pull individual
+ books out of the stack, as well as insert new books between
+ existing ones or at the bottom or top of the stack.
+
+ At any given time, you can refer to a book in the tower by
+ measuring the book's height above the tower in some unit,
+ e.g. mm. This isn't necessarily equivalent to the number of
+ books in the tower below the book in question, like an array
+ index, because the books in the stack aren't necessarily all
+ the same thickness: some might be as thin as K&R and others as
+ thick as _Introduction to Algorithms_.
+
+ This is the analogy behind this data structure. Each node in
+ the data structure has a "thickness", which is actually called
+ the node's "height" because "thickness" is just too awkward a
+ name. The primary way to look up nodes is by a height from
+ the bottom of the tower; any height within a node retrieves
+ that node, not just the distance to the bottom of the node.
+ You can insert a new node between any two existing nodes, or
+ at either end, which shifts up the height of all the nodes
+ above it. You can also delete any node, which shifts down the
+ height of all the nodes above it. */
+
+#ifndef LIBPSPP_TOWER_H
+#define LIBPSPP_TOWER_H
+
+#include <stdbool.h>
+#include <libpspp/abt.h>
+
+/* Returns the data structure corresponding to the given NODE,
+ assuming that NODE is embedded as the given MEMBER name in
+ data type STRUCT. */
+#define tower_data(NODE, STRUCT, MEMBER) \
+ ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
+
+/* A node within a tower. */
+struct tower_node
+ {
+ struct abt_node abt_node; /* ABT node. */
+ unsigned long int subtree_height; /* Node's plus descendants' heights. */
+ unsigned long int height; /* Height. */
+ };
+
+/* Returns the height of a tower node. */
+static inline unsigned long
+tower_node_get_height (const struct tower_node *node)
+{
+ return node->height;
+}
+
+/* A tower. */
+struct tower
+ {
+ struct abt abt; /* Tree. */
+ };
+
+void tower_init (struct tower *);
+
+bool tower_is_empty (const struct tower *);
+unsigned long int tower_height (const struct tower *);
+
+void tower_insert (struct tower *, unsigned long int height,
+ struct tower_node *new, struct tower_node *under);
+struct tower_node *tower_delete (struct tower *, struct tower_node *);
+void tower_resize (struct tower *, struct tower_node *,
+ unsigned long int new_height);
+void tower_splice (struct tower *dst, struct tower_node *under,
+ struct tower *src,
+ struct tower_node *first, struct tower_node *last);
+
+struct tower_node *tower_lookup (const struct tower *,
+ unsigned long int level,
+ unsigned long int *node_start);
+struct tower_node *tower_first (const struct tower *);
+struct tower_node *tower_next (const struct tower *,
+ const struct tower_node *);
+
+#endif /* libpspp/tower.h */
Index: tests/libpspp/tower-test.c
===================================================================
RCS file: tests/libpspp/tower-test.c
diff -N tests/libpspp/tower-test.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/libpspp/tower-test.c 1 Apr 2007 19:32:15 -0000 1.1.2.1
@@ -0,0 +1,689 @@
+/* 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 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 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 <config.h>
+#endif
+
+#include <libpspp/tower.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__)
+
+/* Node type and support routines. */
+
+/* Test data block. */
+struct block
+ {
+ struct tower_node node; /* Embedded tower block. */
+ int x; /* Primary value. */
+ };
+
+/* Returns the `struct block' that NODE is embedded within. */
+static struct block *
+tower_node_to_block (const struct tower_node *node)
+{
+ return tower_data (node, struct block, node);
+}
+
+/* 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;
+}
+
+/* Returns C(n, k), the number of ways that K choices can be made
+ from N items when order is unimportant. */
+static unsigned int
+binomial_cofficient (unsigned int n, unsigned int k)
+{
+ assert (n >= k);
+ return factorial (n) / factorial (k) / factorial (n - k);
+}
+
+/* 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;
+}
+
+/* A block expected to be found in a tower. */
+struct expected_block
+ {
+ int height; /* Expected height of bottom of block. */
+ int x; /* Expected value for `x' member. */
+ };
+
+/* Checks that tower T contains the BLOCK_CNT blocks described by
+ BLOCKS[]. */
+static void
+check_tower (struct tower *t,
+ struct expected_block blocks[], size_t block_cnt)
+{
+ int total_height;
+ struct tower_node *node;
+ size_t i;
+
+ check (tower_is_empty (t) == (block_cnt == 0));
+
+ total_height = 0;
+ for (i = 0; i < block_cnt; i++)
+ {
+ unsigned long int level;
+ for (level = total_height;
+ level < total_height + blocks[i].height;
+ level++)
+ {
+ struct tower_node *found;
+ unsigned long int block_start;
+ found = tower_lookup (t, level, &block_start);
+ check (found != NULL);
+ check (tower_node_to_block (found)->x == blocks[i].x);
+ check (block_start == total_height);
+ }
+ total_height += blocks[i].height;
+ }
+ check (tower_height (t) == total_height);
+
+ for (node = tower_first (t), i = 0;
+ node != NULL;
+ node = tower_next (t, node), i++)
+ {
+ check (tower_node_get_height (node) == blocks[i].height);
+ check (tower_node_to_block (node)->x == blocks[i].x);
+ }
+ check (i == block_cnt);
+}
+
+/* Tests inserting all possible sets of block heights into a
+ tower in all possible orders, up to a specified maximum tower
+ height. */
+static void
+test_insert (void)
+{
+ const int max_height = 7;
+ int cnt;
+
+ for (cnt = 1; cnt <= max_height; cnt++)
+ {
+ unsigned int composition_cnt;
+ struct expected_block *expected;
+ int *heights;
+ int block_cnt;
+ int *order;
+ struct block *blocks;
+
+ expected = xnmalloc (cnt, sizeof *expected);
+ heights = xnmalloc (cnt, sizeof *heights);
+ order = xnmalloc (cnt, sizeof *order);
+ blocks = xnmalloc (cnt, sizeof *blocks);
+
+ block_cnt = 0;
+ composition_cnt = 0;
+ while (next_composition (cnt, &block_cnt, heights))
+ {
+ int i, j;
+ unsigned int permutation_cnt;
+
+ for (i = 0; i < block_cnt; i++)
+ order[i] = i;
+
+ permutation_cnt = 0;
+ while (permutation_cnt == 0 || next_permutation (order, block_cnt))
+ {
+ struct tower t;
+
+ /* Inserts the block_cnt blocks with the given
+ heights[] into T in the order given by order[]. */
+ tower_init (&t);
+ for (i = 0; i < block_cnt; i++)
+ {
+ struct block *under;
+ int idx;
+
+ idx = order[i];
+ blocks[idx].x = idx;
+
+ under = NULL;
+ for (j = 0; j < i; j++)
+ if (idx < order[j]
+ && (under == NULL || under->x > order[j]))
+ under = &blocks[order[j]];
+
+ tower_insert (&t, heights[idx], &blocks[idx].node,
+ under != NULL ? &under->node : NULL);
+ }
+
+ /* Check that the result is what we expect. */
+ for (i = 0; i < block_cnt; i++)
+ {
+ expected[i].height = heights[i];
+ expected[i].x = i;
+ }
+ check_tower (&t, expected, block_cnt);
+
+ permutation_cnt++;
+ }
+ check (permutation_cnt == factorial (block_cnt));
+
+ composition_cnt++;
+ }
+ check (composition_cnt == 1 << (cnt - 1));
+
+ free (expected);
+ free (heights);
+ free (order);
+ free (blocks);
+ }
+}
+
+/* Tests deleting blocks from towers that initially contain all
+ possible sets of block heights into a tower in all possible
+ orders, up to a specified maximum tower height. */
+static void
+test_delete (void)
+{
+ const int max_height = 7;
+ int cnt;
+
+ for (cnt = 1; cnt <= max_height; cnt++)
+ {
+ unsigned int composition_cnt;
+ struct expected_block *expected;
+ int *heights;
+ int block_cnt;
+ int *order;
+ struct block *blocks;
+
+ expected = xnmalloc (cnt, sizeof *expected);
+ heights = xnmalloc (cnt, sizeof *heights);
+ order = xnmalloc (cnt, sizeof *order);
+ blocks = xnmalloc (cnt, sizeof *blocks);
+
+ block_cnt = 0;
+ composition_cnt = 0;
+ while (next_composition (cnt, &block_cnt, heights))
+ {
+ int i;
+ unsigned int permutation_cnt;
+
+ for (i = 0; i < block_cnt; i++)
+ order[i] = i;
+
+ permutation_cnt = 0;
+ while (permutation_cnt == 0 || next_permutation (order, block_cnt))
+ {
+ struct tower t;
+
+ /* Insert blocks into tower in ascending order. */
+ tower_init (&t);
+ for (i = 0; i < block_cnt; i++)
+ {
+ blocks[i].x = i;
+ tower_insert (&t, heights[i], &blocks[i].node, NULL);
+ expected[i].x = i;
+ expected[i].height = heights[i];
+ }
+ check_tower (&t, expected, block_cnt);
+
+ /* Delete blocks from tower in the order of
+ order[]. */
+ for (i = 0; i < block_cnt; i++)
+ {
+ int idx = order[i];
+ int j;
+ tower_delete (&t, &blocks[idx].node);
+ for (j = 0; ; j++)
+ {
+ assert (j < block_cnt - i);
+ if (expected[j].x == idx)
+ {
+ memcpy (&expected[j], &expected[j + 1],
+ sizeof *expected * (block_cnt - i - j - 1));
+ break;
+ }
+ }
+ check_tower (&t, expected, block_cnt - i - 1);
+ }
+
+ permutation_cnt++;
+ }
+ check (permutation_cnt == factorial (block_cnt));
+
+ composition_cnt++;
+ }
+ check (composition_cnt == 1 << (cnt - 1));
+
+ free (expected);
+ free (heights);
+ free (order);
+ free (blocks);
+ }
+}
+
+/* Tests towers containing all possible block heights, resizing
+ the blocks to all possible heights that conserve the total
+ tower height, up to a maximum total tower height. */
+static void
+test_resize (void)
+{
+ const int max_height = 9;
+ int cnt;
+
+ for (cnt = 1; cnt <= max_height; cnt++)
+ {
+ unsigned int composition_cnt;
+ struct expected_block *expected;
+ int *heights, *new_heights;
+ int block_cnt;
+ int *order;
+ struct block *blocks;
+
+ expected = xnmalloc (cnt, sizeof *expected);
+ heights = xnmalloc (cnt, sizeof *heights);
+ new_heights = xnmalloc (cnt, sizeof *new_heights);
+ order = xnmalloc (cnt, sizeof *order);
+ blocks = xnmalloc (cnt, sizeof *blocks);
+
+ block_cnt = 0;
+ composition_cnt = 0;
+ while (next_composition (cnt, &block_cnt, heights))
+ {
+ int i;
+ unsigned int resizes = 0;
+
+ for (resizes = 0, first_k_composition (cnt, block_cnt, new_heights);
+ (resizes == 0
+ || next_k_composition (cnt, block_cnt, new_heights));
+ resizes++)
+ {
+ struct tower t;
+
+ /* Insert blocks into tower in ascending order. */
+ tower_init (&t);
+ for (i = 0; i < block_cnt; i++)
+ {
+ blocks[i].x = i;
+ tower_insert (&t, heights[i], &blocks[i].node, NULL);
+ expected[i].x = i;
+ expected[i].height = heights[i];
+ }
+ check_tower (&t, expected, block_cnt);
+
+ /* Resize all the blocks. */
+ for (i = 0; i < block_cnt; i++)
+ {
+ if (expected[i].height != new_heights[i] || rand () % 2)
+ tower_resize (&t, &blocks[i].node, new_heights[i]);
+ expected[i].height = new_heights[i];
+ }
+ check_tower (&t, expected, block_cnt);
+ }
+ check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1));
+
+ composition_cnt++;
+ }
+ check (composition_cnt == 1 << (cnt - 1));
+
+ free (expected);
+ free (new_heights);
+ free (heights);
+ free (order);
+ free (blocks);
+ }
+}
+
+/* Tests splicing all possible contiguous sets of blocks out of one
+ tower into a second, initially empty tower. */
+static void
+test_splice_out (void)
+{
+ const int max_height = 9;
+ int cnt;
+
+ for (cnt = 1; cnt <= max_height; cnt++)
+ {
+ unsigned int composition_cnt;
+ struct expected_block *expected;
+ int *heights, *new_heights;
+ int block_cnt;
+ int *order;
+ struct block *blocks;
+
+ expected = xnmalloc (cnt, sizeof *expected);
+ heights = xnmalloc (cnt, sizeof *heights);
+ new_heights = xnmalloc (cnt, sizeof *new_heights);
+ order = xnmalloc (cnt, sizeof *order);
+ blocks = xnmalloc (cnt, sizeof *blocks);
+
+ block_cnt = 0;
+ composition_cnt = 0;
+ while (next_composition (cnt, &block_cnt, heights))
+ {
+ int i, j;
+
+ for (i = 0; i < block_cnt; i++)
+ for (j = i; j <= block_cnt; j++)
+ {
+ struct tower src, dst;
+ int k;
+
+ tower_init (&src);
+ tower_init (&dst);
+
+ /* Insert blocks into SRC and DST in ascending order. */
+ for (k = 0; k < block_cnt; k++)
+ {
+ blocks[k].x = k;
+ tower_insert (&src, heights[k], &blocks[k].node, NULL);
+ expected[k].x = k;
+ expected[k].height = heights[k];
+ }
+ check_tower (&src, expected, block_cnt);
+
+ /* Splice blocks I...J into DST. */
+ tower_splice (&dst, NULL, &src, &blocks[i].node,
+ j < block_cnt ? &blocks[j].node : NULL);
+ check_tower (&dst, &expected[i], j - i);
+ memmove (&expected[i], &expected[j],
+ sizeof *expected * (block_cnt - j));
+ check_tower (&src, expected, block_cnt - (j - i));
+ }
+ composition_cnt++;
+ }
+ check (composition_cnt == 1 << (cnt - 1));
+
+ free (expected);
+ free (new_heights);
+ free (heights);
+ free (order);
+ free (blocks);
+ }
+}
+
+/* Tests splicing all of the contents of a tower into all
+ possible positions in a second tower. */
+static void
+test_splice_in (void)
+{
+ const int max_height = 9;
+ int cnt;
+
+ for (cnt = 1; cnt <= max_height; cnt++)
+ {
+ unsigned int composition_cnt;
+ struct expected_block *expected;
+ int *heights, *new_heights;
+ int block_cnt;
+ int *order;
+ struct block *blocks;
+
+ expected = xnmalloc (cnt, sizeof *expected);
+ heights = xnmalloc (cnt, sizeof *heights);
+ new_heights = xnmalloc (cnt, sizeof *new_heights);
+ order = xnmalloc (cnt, sizeof *order);
+ blocks = xnmalloc (cnt, sizeof *blocks);
+
+ block_cnt = 0;
+ composition_cnt = 0;
+ while (next_composition (cnt, &block_cnt, heights))
+ {
+ int i, j;
+
+ for (i = 0; i < block_cnt; i++)
+ for (j = i; j <= block_cnt; j++)
+ {
+ struct tower src, dst;
+ int k;
+
+ tower_init (&src);
+ tower_init (&dst);
+
+ /* Insert blocks into SRC and DST in ascending order. */
+ for (k = 0; k < block_cnt; k++)
+ {
+ blocks[k].x = k;
+ tower_insert (k >= i && k < j ? &src : &dst,
+ heights[k], &blocks[k].node, NULL);
+ expected[k].x = k;
+ expected[k].height = heights[k];
+ }
+
+ /* Splice SRC into DST. */
+ tower_splice (&dst, j < block_cnt ? &blocks[j].node : NULL,
+ &src, i != j ? &blocks[i].node : NULL, NULL);
+ check_tower (&dst, expected, block_cnt);
+ }
+ composition_cnt++;
+ }
+ check (composition_cnt == 1 << (cnt - 1));
+
+ free (expected);
+ free (new_heights);
+ free (heights);
+ free (order);
+ free (blocks);
+ }
+}
+
+
+/* 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_resize, "resize");
+ run_test (test_splice_out, "splice out");
+ run_test (test_splice_in, "splice in");
+ putchar ('\n');
+
+ return 0;
+}
Index: src/libpspp/fat-array.h
===================================================================
RCS file: src/libpspp/fat-array.h
diff -N src/libpspp/fat-array.h
--- src/libpspp/fat-array.h 19 Mar 2007 21:36:24 -0000 1.1.2.1
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,69 +0,0 @@
-/* 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. */
-
-#ifndef LIBPSPP_FAT_ARRAY_H
-#define LIBPSPP_FAT_ARRAY_H
-
-#include <libpspp/abt.h>
-
-/* Returns the data structure corresponding to the given NODE,
- assuming that NODE is embedded as the given MEMBER name in
- data type STRUCT. */
-#define fat_array_data(NODE, STRUCT, MEMBER) \
- ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
-
-struct fat_array_node
- {
- struct abt_node abt_node;
- unsigned long subtree_width;
- unsigned long width;
- };
-
-unsigned long fat_array_node_get_width (const struct fat_array_node *);
-
-struct fat_array
- {
- struct abt abt;
- };
-
-
-void fat_array_init (struct fat_array *);
-
-bool fat_array_is_empty (const struct fat_array *);
-unsigned long fat_array_size (const struct fat_array *);
-
-struct fat_array_node *fat_array_lookup (const struct fat_array *,
- unsigned long idx,
- unsigned long *node_start);
-void fat_array_insert (struct fat_array *, unsigned long width,
- struct fat_array_node *new,
- struct fat_array_node *before);
-void fat_array_splice (struct fat_array *dst, struct fat_array_node *before,
- struct fat_array *src,
- struct fat_array_node *first,
- struct fat_array_node *last);
-struct fat_array_node *fat_array_delete (struct fat_array *,
- struct fat_array_node *);
-void fat_array_resize (struct fat_array *, struct fat_array_node *,
- unsigned long new_width);
-struct fat_array_node *fat_array_first (struct fat_array *);
-struct fat_array_node *fat_array_next (struct fat_array *,
- struct fat_array_node *);
-
-
-#endif /* libpspp/fat-array.h */
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Pspp-cvs] pspp src/data/datasheet.c src/libpspp/automake.... [simpler-proc],
Ben Pfaff <=