[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pspp-cvs] pspp/src/data datasheet.c datasheet.h [simpler-proc]
|
From: |
Ben Pfaff |
|
Subject: |
[Pspp-cvs] pspp/src/data datasheet.c datasheet.h [simpler-proc] |
|
Date: |
Wed, 18 Apr 2007 23:16:18 +0000 |
CVSROOT: /cvsroot/pspp
Module name: pspp
Branch: simpler-proc
Changes by: Ben Pfaff <blp> 07/04/18 23:16:18
Modified files:
src/data : datasheet.c datasheet.h
Log message:
Document the datasheet code.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/datasheet.c?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.8&r2=1.1.2.9
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/datasheet.h?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.3&r2=1.1.2.4
Patches:
Index: datasheet.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/Attic/datasheet.c,v
retrieving revision 1.1.2.8
retrieving revision 1.1.2.9
diff -u -b -r1.1.2.8 -r1.1.2.9
--- datasheet.c 18 Apr 2007 05:41:26 -0000 1.1.2.8
+++ datasheet.c 18 Apr 2007 23:16:18 -0000 1.1.2.9
@@ -39,8 +39,11 @@
#include "xalloc.h"
static struct axis *axis_create (void);
+static struct axis *axis_clone (const struct axis *);
static void axis_destroy (struct axis *);
+static void axis_hash (const struct axis *, struct md4_ctx *);
+
static bool axis_allocate (struct axis *, unsigned long int request,
unsigned long int *start,
unsigned long int *width);
@@ -65,7 +68,7 @@
static struct source *source_create_empty (size_t column_cnt);
static struct source *source_create_casereader (struct casereader *);
-static struct source *clone_source (const struct source *);
+static struct source *source_clone (const struct source *);
static void source_destroy (struct source *);
static casenumber source_get_backing_row_cnt (const struct source *);
@@ -73,10 +76,10 @@
static bool source_read (const struct source *,
casenumber row, size_t column,
- union value *, size_t value_cnt);
+ union value[], size_t value_cnt);
static bool source_write (struct source *,
casenumber row, size_t column,
- const union value *, size_t value_cnt);
+ const union value[], size_t value_cnt);
static bool source_write_columns (struct source *, size_t start_column,
const union value[], size_t value_cnt);
static bool source_has_backing (const struct source *);
@@ -104,8 +107,11 @@
/* A datasheet. */
struct datasheet
{
+ /* Mappings from logical to physical columns/rows. */
struct axis *columns;
struct axis *rows;
+
+ /* Mapping from physical columns to "source_info"s. */
struct range_map sources;
/* Minimum number of columns to put in a new source when we
@@ -114,32 +120,48 @@
needed by the datasheet to a minimum, reducing the
likelihood of running out. */
unsigned column_min_alloc;
+
+ /* True if an I/O error has occurred. */
+ bool error;
};
+/* Maps from a range of physical columns to a source. */
struct source_info
{
struct range_map_node column_range;
struct source *source;
};
+/* Is this operation a read or a write? */
+enum rw_op
+ {
+ OP_READ,
+ OP_WRITE
+ };
+
+static void free_source_info (struct datasheet *, struct source_info *);
+static struct source_info *source_info_from_range_map (
+ struct range_map_node *);
+static bool rw_case (struct datasheet *ds, enum rw_op op,
+ casenumber lrow, size_t start_column, size_t column_cnt,
+ union value data[]);
-static struct source_info *
-source_info_from_range_map (struct range_map_node *node)
-{
- return range_map_data (node, struct source_info, column_range);
-}
+/* Creates and returns a new datasheet.
+ If READER is nonnull, then the datasheet initially contains
+ the contents of READER. */
struct datasheet *
datasheet_create (struct casereader *reader)
{
- struct datasheet *ds;
-
- ds = xmalloc (sizeof *ds);
+ /* Create datasheet. */
+ struct datasheet *ds = xmalloc (sizeof *ds);
ds->columns = axis_create ();
ds->rows = axis_create ();
range_map_init (&ds->sources);
ds->column_min_alloc = 1;
+ ds->error = false;
+ /* Add backing. */
if (reader != NULL)
{
size_t column_cnt;
@@ -168,14 +190,7 @@
return ds;
}
-static void
-free_source_info (struct datasheet *ds, struct source_info *si)
-{
- range_map_delete (&ds->sources, &si->column_range);
- source_destroy (si->source);
- free (si);
-}
-
+/* Destroys datasheet DS. */
void
datasheet_destroy (struct datasheet *ds)
{
@@ -193,18 +208,52 @@
free (ds);
}
+/* Moves datasheet DS to a new location in memory, and returns
+ the new location. Afterward, the datasheet must not be
+ accessed at its former location.
+
+ This function is useful for ensuring that all references to a
+ datasheet have been dropped, especially in conjunction with
+ tools like Valgrind. */
+struct datasheet *
+datasheet_rename (struct datasheet *ds)
+{
+ struct datasheet *new = xmemdup (ds, sizeof *ds);
+#ifndef NDEBUG
+ memset (ds, 0xcc, sizeof *ds);
+#endif
+ free (ds);
+ return new;
+}
+
+/* Returns true if a I/O error has occurred while processing a
+ datasheet operation. */
+bool
+datasheet_error (const struct datasheet *ds)
+{
+ return ds->error;
+}
+
+/* Returns the number of rows in DS. */
casenumber
datasheet_get_row_cnt (const struct datasheet *ds)
{
return axis_get_size (ds->rows);
}
+/* Returns the number of columns in DS. */
size_t
datasheet_get_column_cnt (const struct datasheet *ds)
{
return axis_get_size (ds->columns);
}
+/* Inserts CNT columns into datasheet DS just before column
+ BEFORE. Initializes the contents of each row in the inserted
+ columns to the CNT values in INIT_VALUES.
+
+ Returns true if successful, false on failure. In case of
+ failure, the datasheet is unchanged. */
bool
datasheet_insert_columns (struct datasheet *ds,
const union value init_values[], size_t cnt,
@@ -213,11 +262,15 @@
size_t added = 0;
while (cnt > 0)
{
- unsigned long first_phy;
- unsigned long phy_cnt;
+ unsigned long first_phy; /* First allocated physical column. */
+ unsigned long phy_cnt; /* Number of allocated physical columns. */
+ /* Allocate physical columns from the pool of available
+ columns. */
if (!axis_allocate (ds->columns, cnt, &first_phy, &phy_cnt))
{
+ /* No columns were available. Create a new source and
+ extend the axis to make some new ones available. */
struct source_info *si;
phy_cnt = MAX (cnt, ds->column_min_alloc);
@@ -236,27 +289,38 @@
}
}
+ /* Initialize the columns and insert them into the columns
+ axis. */
while (phy_cnt > 0)
{
- struct range_map_node *r;
- struct source_info *s;
- size_t source_cnt;
-
+ struct range_map_node *r; /* Range map holding FIRST_PHY column. */
+ struct source_info *s; /* Source containing FIRST_PHY column. */
+ size_t source_avail; /* Number of phys columns available. */
+ size_t source_cnt; /* Number of phys columns to use. */
+
+ /* Figure out how many columns we can and want to take
+ starting at FIRST_PHY, and then insert them into the
+ columns axis. */
r = range_map_lookup (&ds->sources, first_phy);
s = source_info_from_range_map (r);
- source_cnt = MIN (phy_cnt, range_map_node_get_end (r) - first_phy);
+ source_avail = range_map_node_get_end (r) - first_phy;
+ source_cnt = MIN (phy_cnt, source_avail);
axis_insert (ds->columns, before, first_phy, source_cnt);
+ /* Initialize the data for those columns in the
+ source. */
if (!source_write_columns (s->source,
first_phy - range_map_node_get_start (r),
init_values, source_cnt))
{
datasheet_delete_columns (ds, before - added,
source_cnt + added);
+ ds->error = true;
return false;
}
source_increase_use (s->source, source_cnt);
+ /* Advance. */
phy_cnt -= source_cnt;
first_phy += source_cnt;
init_values += source_cnt;
@@ -268,6 +332,7 @@
return true;
}
+/* Deletes the CNT columns in DS starting from column START. */
void
datasheet_delete_columns (struct datasheet *ds, size_t start, size_t cnt)
{
@@ -294,6 +359,8 @@
axis_remove (ds->columns, start, cnt);
}
+/* Moves the CNT columns in DS starting at position OLD_START so
+ that they then start at position NEW_START. */
void
datasheet_move_columns (struct datasheet *ds,
size_t old_start, size_t new_start,
@@ -302,44 +369,9 @@
axis_move (ds->columns, old_start, new_start, cnt);
}
-enum rw_op
- {
- OP_READ,
- OP_WRITE
- };
-
-static bool
-rw_case (struct datasheet *ds, enum rw_op op,
- casenumber lrow, size_t start_column, size_t column_cnt,
- union value data[])
-{
- casenumber prow;
- size_t lcol;
-
- assert (lrow < datasheet_get_row_cnt (ds));
- assert (column_cnt <= datasheet_get_column_cnt (ds));
- assert (start_column + column_cnt <= datasheet_get_column_cnt (ds));
-
- prow = axis_map (ds->rows, lrow);
- for (lcol = start_column; lcol < start_column + column_cnt; lcol++, data++)
- {
- size_t pcol;
- struct range_map_node *r;
- struct source_info *s;
- size_t pcol_ofs;
-
- pcol = axis_map (ds->columns, lcol);
- r = range_map_lookup (&ds->sources, pcol);
- s = source_info_from_range_map (r);
- pcol_ofs = pcol - range_map_node_get_start (r);
- if (!(op == OP_READ
- ? source_read (s->source, prow, pcol_ofs, data, 1)
- : source_write (s->source, prow, pcol_ofs, data, 1)))
- return false;
- }
- return true;
-}
-
+/* Retrieves the contents of the given ROW in datasheet DS into
+ newly created case C. Returns true if successful, false on
+ I/O error. */
bool
datasheet_get_row (const struct datasheet *ds, casenumber row, struct ccase *c)
{
@@ -355,6 +387,10 @@
}
}
+/* Stores the contents of case C, which is destroyed, into the
+ given ROW in DS. Returns true on success, false on I/O error.
+ On failure, the given ROW might be partially modified or
+ corrupted. */
bool
datasheet_put_row (struct datasheet *ds, casenumber row, struct ccase *c)
{
@@ -365,6 +401,9 @@
return ok;
}
+/* Stores the values of the WIDTH columns in DS in the given ROW
+ starting at COLUMN in DS into VALUES. Returns true if
+ successful, false on I/O error. */
bool
datasheet_get_value (const struct datasheet *ds, casenumber row, size_t column,
union value *value, int width)
@@ -373,6 +412,10 @@
OP_READ, row, column, value_cnt_from_width (width), value);
}
+/* Stores the WIDTH given VALUES into the given ROW in DS
+ starting at COLUMN. Returns true if successful, false on I/O
+ error. On failure, the given ROW might be partially modified
+ or corrupted. */
bool
datasheet_put_value (struct datasheet *ds, casenumber row, size_t column,
const union value *value, int width)
@@ -381,9 +424,13 @@
(union value *) value);
}
+/* Inserts the CNT cases at C, which are destroyed, into
+ datasheet DS just before row BEFORE. Returns true if
+ successful, false on I/O error. On failure, datasheet DS is
+ not modified. */
bool
datasheet_insert_rows (struct datasheet *ds,
- casenumber before, struct ccase *c,
+ casenumber before, struct ccase c[],
casenumber cnt)
{
casenumber added = 0;
@@ -393,13 +440,20 @@
unsigned long phy_cnt;
unsigned long i;
+ /* Allocate physical rows from the pool of available
+ rows. */
if (!axis_allocate (ds->rows, cnt, &first_phy, &phy_cnt))
{
+ /* No rows were available. Extend the row axis to make
+ some new ones available. */
phy_cnt = cnt;
first_phy = axis_extend (ds->rows, cnt);
}
+ /* Insert the new rows into the row mapping. */
axis_insert (ds->rows, before, first_phy, phy_cnt);
+
+ /* Initialize the new rows. */
for (i = 0; i < phy_cnt; i++)
if (!datasheet_put_row (ds, before + i, &c[i]))
{
@@ -409,6 +463,7 @@
return false;
}
+ /* Advance. */
c += phy_cnt;
cnt -= phy_cnt;
before += phy_cnt;
@@ -417,6 +472,7 @@
return true;
}
+/* Deletes the CNT rows in DS starting from row FIRST. */
void
datasheet_delete_rows (struct datasheet *ds,
casenumber first, casenumber cnt)
@@ -432,6 +488,8 @@
axis_remove (ds->rows, first, cnt);
}
+/* Moves the CNT rows in DS starting at position OLD_START so
+ that they then start at position NEW_START. */
void
datasheet_move_rows (struct datasheet *ds,
size_t old_start, size_t new_start,
@@ -442,14 +500,10 @@
static const struct buffered_reader_class datasheet_reader_class;
-static struct datasheet *
-datasheet_rename (struct datasheet *old)
-{
- struct datasheet *new = xmemdup (old, sizeof *old);
- free (old);
- return new;
-}
-
+/* Creates and returns a casereader whose input cases are the
+ rows in datasheet DS. From the caller's perspective, DS is
+ effectively destroyed by this operation, such that the caller
+ must not reference it again. */
struct casereader *
datasheet_make_reader (struct datasheet *ds)
{
@@ -472,8 +526,8 @@
static bool
datasheet_reader_error (void *ds_)
{
- struct datasheet *ds = ds_;
- return false; /* FIXME */
+ const struct datasheet *ds = ds_;
+ return datasheet_error (ds);
}
static bool
@@ -481,7 +535,7 @@
{
struct datasheet *ds = ds_;
datasheet_destroy (ds);
- return true; /* FIXME */
+ return true;
}
static void
@@ -499,27 +553,90 @@
datasheet_reader_advance,
};
+/* Removes SI from DS's set of sources and destroys its
+ source. */
+static void
+free_source_info (struct datasheet *ds, struct source_info *si)
+{
+ range_map_delete (&ds->sources, &si->column_range);
+ source_destroy (si->source);
+ free (si);
+}
+
+static struct source_info *
+source_info_from_range_map (struct range_map_node *node)
+{
+ return range_map_data (node, struct source_info, column_range);
+}
+
+/* Reads (if OP is OP_READ) or writes (if op is OP_WRITE) the
+ COLUMN_CNT columns starting from column START_COLUMN in row
+ LROW to/from the COLUMN_CNT values in DATA. */
+static bool
+rw_case (struct datasheet *ds, enum rw_op op,
+ casenumber lrow, size_t start_column, size_t column_cnt,
+ union value data[])
+{
+ casenumber prow;
+ size_t lcol;
+
+ assert (lrow < datasheet_get_row_cnt (ds));
+ assert (column_cnt <= datasheet_get_column_cnt (ds));
+ assert (start_column + column_cnt <= datasheet_get_column_cnt (ds));
+
+ prow = axis_map (ds->rows, lrow);
+ for (lcol = start_column; lcol < start_column + column_cnt; lcol++, data++)
+ {
+ size_t pcol = axis_map (ds->columns, lcol);
+ struct range_map_node *r = range_map_lookup (&ds->sources, pcol);
+ struct source_info *s = source_info_from_range_map (r);
+ size_t pcol_ofs = pcol - range_map_node_get_start (r);
+ if (!(op == OP_READ
+ ? source_read (s->source, prow, pcol_ofs, data, 1)
+ : source_write (s->source, prow, pcol_ofs, data, 1)))
+ {
+ ds->error = true;
+ return false;
+ }
+ }
+ return true;
+}
+
+/* An axis.
+
+ An axis has two functions. First, it maintains a mapping from
+ logical (client-visible) to physical (storage) ordinates. The
+ axis_map and axis_get_size functions inspect this mapping, and
+ the axis_insert, axis_remove, and axis_move functions modify
+ it. Second, it tracks the set of ordinates that are unused
+ and available for reuse. (Not all unused ordinates are
+ available for reuse: in particular, unused columns that are
+ backed by a casereader are never reused.) The axis_allocate,
+ axis_make_available, and axis_extend functions affect the set
+ of available ordinates. */
struct axis
{
- struct tower log_to_phy;
- struct range_set *available;
- unsigned long int phy_size;
+ struct tower log_to_phy; /* Map from logical to physical ordinates;
+ contains "struct axis_group"s. */
+ struct range_set *available; /* Set of unused, available ordinates. */
+ unsigned long int phy_size; /* Current physical length of axis. */
};
+/* A mapping from logical to physical ordinates. */
struct axis_group
{
- struct tower_node logical;
- unsigned long phy_start;
+ struct tower_node logical; /* Range of logical ordinates. */
+ unsigned long phy_start; /* First corresponding physical ordinate. */
};
-static struct axis_group *
-axis_group_from_tower_node (struct tower_node *node)
-{
- return tower_data (node, struct axis_group, logical);
-}
-
+static struct axis_group *axis_group_from_tower_node (struct tower_node *);
static struct tower_node *make_axis_group (unsigned long int phy_start);
+static struct tower_node *split_axis (struct axis *, unsigned long int where);
+static void merge_axis_nodes (struct axis *, struct tower_node *,
+ struct tower_node **other_node);
+static void check_axis_merged (const struct axis *axis UNUSED);
+/* Creates and returns a new, initially empty axis. */
static struct axis *
axis_create (void)
{
@@ -530,8 +647,12 @@
return axis;
}
+/* Returns a clone of existing axis OLD.
+
+ Currently this is used only by the datasheet model checker
+ driver, but it could be otherwise useful. */
static struct axis *
-clone_axis (const struct axis *old)
+axis_clone (const struct axis *old)
{
const struct tower_node *node;
struct axis *new;
@@ -553,8 +674,12 @@
return new;
}
+/* Adds the state of AXIS to the MD4 hash context CTX.
+
+ This is only used by the datasheet model checker driver. It
+ is unlikely to be otherwise useful. */
static void
-hash_axis (const struct axis *axis, struct md4_ctx *ctx)
+axis_hash (const struct axis *axis, struct md4_ctx *ctx)
{
const struct tower_node *tn;
const struct range_set_node *rsn;
@@ -583,6 +708,7 @@
md4_process_bytes (&axis->phy_size, sizeof axis->phy_size, ctx);
}
+/* Destroys AXIS. */
static void
axis_destroy (struct axis *axis)
{
@@ -602,14 +728,21 @@
free (axis);
}
+/* Allocates up to REQUEST contiguous unused and available
+ ordinates from AXIS. If successful, stores the number
+ obtained into *WIDTH and the ordinate of the first into
+ *START, marks the ordinates as now unavailable return true.
+ On failure, which occurs only if AXIS has no unused and
+ available ordinates, returns false without modifying AXIS. */
static bool
axis_allocate (struct axis *axis, unsigned long int request,
- unsigned long int *start,
- unsigned long int *width)
+ unsigned long int *start, unsigned long int *width)
{
return range_set_allocate (axis->available, request, start, width);
}
+/* Marks the WIDTH contiguous ordinates in AXIS, starting from
+ START, as unused and available. */
static void
axis_make_available (struct axis *axis,
unsigned long int start, unsigned long int width)
@@ -617,6 +750,8 @@
range_set_insert (axis->available, start, width);
}
+/* Extends the total physical length of AXIS by WIDTH and returns
+ the first ordinate in the new physical region. */
static unsigned long int
axis_extend (struct axis *axis, unsigned long int width)
{
@@ -625,6 +760,9 @@
return start;
}
+/* Returns the physical ordinate in AXIS corresponding to logical
+ ordinate LOG_POS. LOG_POS must be less than the logical
+ length of AXIS. */
static unsigned long int
axis_map (const struct axis *axis, unsigned long log_pos)
{
@@ -637,12 +775,94 @@
return group->phy_start + (log_pos - group_start);
}
+/* Returns the logical length of AXIS. */
static unsigned long
axis_get_size (const struct axis *axis)
{
return tower_height (&axis->log_to_phy);
}
+/* Inserts the CNT contiguous physical ordinates starting at
+ PHY_START into AXIS's logical-to-physical mapping, starting at
+ logical position LOG_START. */
+static void
+axis_insert (struct axis *axis,
+ unsigned long int log_start, unsigned long int phy_start,
+ unsigned long int cnt)
+{
+ 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);
+ merge_axis_nodes (axis, new, NULL);
+ check_axis_merged (axis);
+}
+
+/* Removes CNT ordinates from AXIS's logical-to-physical mapping
+ starting at logical position START. */
+static void
+axis_remove (struct axis *axis,
+ unsigned long int start, unsigned long int cnt)
+{
+ if (cnt > 0)
+ {
+ 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 = tower_delete (&axis->log_to_phy, cur);
+ free (axis_group_from_tower_node (cur));
+ }
+ merge_axis_nodes (axis, last, NULL);
+ check_axis_merged (axis);
+ }
+}
+
+/* Moves the CNT ordinates in AXIS's logical-to-mapping starting
+ at logical position OLD_START so that they then start at
+ position NEW_START. */
+static void
+axis_move (struct axis *axis,
+ unsigned long int old_start, unsigned long int new_start,
+ unsigned long int cnt)
+{
+ if (cnt > 0 && old_start != new_start)
+ {
+ struct tower_node *old_first, *old_last, *new_first;
+ struct tower_node *merge1, *merge2;
+ struct tower tmp_array;
+
+ /* Move ordinates OLD_START...(OLD_START + CNT) into new,
+ separate TMP_ARRAY. */
+ old_first = split_axis (axis, old_start);
+ old_last = split_axis (axis, old_start + cnt);
+ tower_init (&tmp_array);
+ tower_splice (&tmp_array, NULL,
+ &axis->log_to_phy, old_first, old_last);
+ merge_axis_nodes (axis, old_last, NULL);
+ check_axis_merged (axis);
+
+ /* Move TMP_ARRAY to position NEW_START. */
+ new_first = split_axis (axis, new_start);
+ merge1 = tower_first (&tmp_array);
+ merge2 = tower_last (&tmp_array);
+ if (merge2 == merge1)
+ merge2 = NULL;
+ tower_splice (&axis->log_to_phy, new_first, &tmp_array, old_first, NULL);
+ merge_axis_nodes (axis, merge1, &merge2);
+ merge_axis_nodes (axis, merge2, NULL);
+ check_axis_merged (axis);
+ }
+}
+
+/* Returns the axis_group in which NODE is embedded. */
+static struct axis_group *
+axis_group_from_tower_node (struct tower_node *node)
+{
+ return tower_data (node, struct axis_group, logical);
+}
+
+/* Creates and returns a new axis_group at physical position
+ PHY_START. */
static struct tower_node *
make_axis_group (unsigned long phy_start)
{
@@ -651,6 +871,12 @@
return &group->logical;
}
+/* Returns the tower_node in AXIS's logical-to-physical map whose
+ bottom edge is at exact level WHERE. If there is no such
+ tower_node in AXIS's logical-to-physical map, then split_axis
+ creates one by breaking an existing tower_node into two
+ separate ones, unless WHERE is equal to the tower height, in
+ which case it simply returns a null pointer. */
static struct tower_node *
split_axis (struct axis *axis, unsigned long int where)
{
@@ -658,6 +884,7 @@
struct tower_node *group_node;
struct axis_group *group;
+ assert (where <= tower_height (&axis->log_to_phy));
if (where >= tower_height (&axis->log_to_phy))
return NULL;
@@ -677,6 +904,15 @@
return &group->logical;
}
+/* Within AXIS, attempts to merge NODE (or the last node in AXIS,
+ if NODE is null) with its neighbor nodes. This is possible
+ when logically adjacent nodes are also adjacent physically (in
+ the same order).
+
+ When a merge occurs, and OTHER_NODE is non-null and points to
+ the node to be deleted, this function also updates
+ *OTHER_NODE, if necessary, to ensure that it remains a valid
+ pointer. */
static void
merge_axis_nodes (struct axis *axis, struct tower_node *node,
struct tower_node **other_node)
@@ -685,12 +921,14 @@
struct axis_group *group;
struct tower_node *next, *prev;
+ /* Find node to potentially merge with neighbors. */
if (node == NULL)
node = tower_last (t);
if (node == NULL)
return;
group = axis_group_from_tower_node (node);
+ /* Try to merge NODE with successor. */
next = tower_next (t, node);
if (next != NULL)
{
@@ -708,6 +946,7 @@
}
}
+ /* Try to merge NODE with predecessor. */
prev = tower_prev (t, node);
if (prev != NULL)
{
@@ -727,10 +966,12 @@
}
}
+/* Verify that all potentially merge-able nodes in AXIS are
+ actually merged. */
static void
check_axis_merged (const struct axis *axis UNUSED)
{
-#if 0//ASSERT_LEVEL >= 10
+#if ASSERT_LEVEL >= 10
struct tower_node *prev, *node;
for (prev = NULL, node = tower_first (&axis->log_to_phy); node != NULL;
@@ -745,78 +986,17 @@
#endif
}
-static void
-axis_insert (struct axis *axis,
- unsigned long int log_start, unsigned long int phy_start,
- unsigned long int cnt)
-{
- 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);
- merge_axis_nodes (axis, new, NULL);
- check_axis_merged (axis);
-}
-
-static void
-axis_remove (struct axis *axis,
- unsigned long int start, unsigned long int cnt)
-{
- if (cnt > 0)
- {
- 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 = tower_delete (&axis->log_to_phy, cur);
- free (axis_group_from_tower_node (cur));
- }
- merge_axis_nodes (axis, last, NULL);
- check_axis_merged (axis);
- }
-}
-
-static void
-axis_move (struct axis *axis,
- unsigned long int old_start, unsigned long int new_start,
- unsigned long int cnt)
-{
- if (cnt > 0 && old_start != new_start)
- {
- struct tower_node *old_first, *old_last, *new_first;
- struct tower_node *merge1, *merge2;
- struct tower tmp_array;
-
- old_first = split_axis (axis, old_start);
- old_last = split_axis (axis, old_start + cnt);
- tower_init (&tmp_array);
- tower_splice (&tmp_array, NULL,
- &axis->log_to_phy, old_first, old_last);
- merge_axis_nodes (axis, old_last, NULL);
-
- check_axis_merged (axis);
-
- new_first = split_axis (axis, new_start);
- merge1 = tower_first (&tmp_array);
- merge2 = tower_last (&tmp_array);
- if (merge2 == merge1)
- merge2 = NULL;
- tower_splice (&axis->log_to_phy, new_first, &tmp_array, old_first, NULL);
- merge_axis_nodes (axis, merge1, &merge2);
- merge_axis_nodes (axis, merge2, NULL);
-
- check_axis_merged (axis);
- }
-}
-
/* A source. */
struct source
{
- size_t columns_used;
- struct sparse_cases *data;
- struct casereader *backing;
- casenumber backing_rows;
+ size_t columns_used; /* Number of columns in use by client. */
+ struct sparse_cases *data; /* Data at top level, atop the backing. */
+ struct casereader *backing; /* Backing casereader (or null). */
+ casenumber backing_rows; /* Number of rows in backing (if nonnull). */
};
+/* Creates and returns an empty, unbacked source with COLUMN_CNT
+ columns and an initial "columns_used" of 0. */
static struct source *
source_create_empty (size_t column_cnt)
{
@@ -828,6 +1008,8 @@
return source;
}
+/* Creates and returns a new source backed by READER and with the
+ same initial dimensions and content. */
static struct source *
source_create_casereader (struct casereader *reader)
{
@@ -838,9 +1020,13 @@
return source;
}
-/* For testing purposes only. */
+/* Returns a clone of source OLD with the same data and backing
+ (if any).
+
+ Currently this is used only by the datasheet model checker
+ driver, but it could be otherwise useful. */
static struct source *
-clone_source (const struct source *old)
+source_clone (const struct source *old)
{
struct source *new = xmalloc (sizeof *new);
new->columns_used = old->columns_used;
@@ -855,6 +1041,8 @@
return new;
}
+/* Increases the columns_used count of SOURCE by DELTA.
+ The new value must not exceed SOURCE's number of columns. */
static void
source_increase_use (struct source *source, size_t delta)
{
@@ -862,19 +1050,25 @@
assert (source->columns_used <= sparse_cases_get_value_cnt (source->data));
}
+/* Decreases the columns_used count of SOURCE by DELTA.
+ This must not attempt to decrease the columns_used count below
+ zero. */
static void
source_decrease_use (struct source *source, size_t delta)
{
+ assert (delta <= source->columns_used);
source->columns_used -= delta;
- assert (source->columns_used <= sparse_cases_get_value_cnt (source->data));
}
+/* Returns true if SOURCE has any columns in use,
+ false otherwise. */
static bool
source_in_use (const struct source *source)
{
return source->columns_used > 0;
}
+/* Destroys SOURCE and its data and backing, if any. */
static void
source_destroy (struct source *source)
{
@@ -886,6 +1080,8 @@
}
}
+/* Returns the number of rows in SOURCE's backing casereader
+ (SOURCE must have a backing casereader). */
static casenumber
source_get_backing_row_cnt (const struct source *source)
{
@@ -893,16 +1089,20 @@
return source->backing_rows;
}
+/* Returns the number of columns in SOURCE. */
static size_t
source_get_column_cnt (const struct source *source)
{
return sparse_cases_get_value_cnt (source->data);
}
+/* Reads VALUE_CNT columns from SOURCE in the given ROW, starting
+ from COLUMN, into VALUES. Returns true if successful, false
+ on I/O error. */
static bool
source_read (const struct source *source,
casenumber row, size_t column,
- union value *values, size_t value_cnt)
+ union value values[], size_t value_cnt)
{
if (source->backing == NULL || sparse_cases_contains_row (source->data, row))
return sparse_cases_read (source->data, row, column, values, value_cnt);
@@ -922,10 +1122,15 @@
}
}
+/* Writes the VALUE_CNT values in VALUES to SOURCE in the given
+ ROW, starting at ROW. Returns true if successful, false on
+ I/O error. On error, the row's data may be completely or
+ partially corrupted, both inside and outside the region to be
+ written. */
static bool
source_write (struct source *source,
casenumber row, size_t column,
- const union value *values, size_t value_cnt)
+ const union value values[], size_t value_cnt)
{
size_t column_cnt = sparse_cases_get_value_cnt (source->data);
bool ok;
@@ -963,29 +1168,44 @@
return ok;
}
+/* Within SOURCE, which must not have a backing casereader,
+ writes the VALUE_CNT values in VALUES_CNT to the VALUE_CNT
+ columns starting from START_COLUMN, in every row, even in rows
+ not yet otherwise initialized. Returns true if successful,
+ false if an I/O error occurs.
+
+ We don't support backing != NULL because (1) it's harder and
+ (2) source_write_columns is only called by
+ datasheet_insert_columns, which doesn't reuse columns from
+ sources that are backed by casereaders. */
static bool
source_write_columns (struct source *source, size_t start_column,
const union value values[], size_t value_cnt)
{
- /* We don't support backing != NULL because (1) it's harder and
- (2) source_write_columns is only called by
- datasheet_insert_columns, which doesn't reuse columns from
- sources that are backed by casereaders. */
assert (source->backing == NULL);
return sparse_cases_write_columns (source->data, start_column,
values, value_cnt);
}
+/* Returns true if SOURCE has a backing casereader, false
+ otherwise. */
static bool
-source_has_backing (const struct source *s)
+source_has_backing (const struct source *source)
{
- return s->backing != NULL;
+ return source->backing != NULL;
}
-#define MAX_ROWS 4
-#define MAX_COLS 4
+/* Datasheet model checker test driver. */
+
+/* Maximum size of datasheet supported for model checking
+ purposes. */
+#define MAX_ROWS 5
+#define MAX_COLS 5
+/* Hashes the structure of datasheet DS and returns the hash.
+ We use MD4 because it is much faster than MD5 or SHA-1 but its
+ collision resistance is just as good. */
static unsigned int
hash_datasheet (const struct datasheet *ds)
{
@@ -994,8 +1214,8 @@
struct range_map_node *r;
md4_init_ctx (&ctx);
- hash_axis (ds->columns, &ctx);
- hash_axis (ds->rows, &ctx);
+ axis_hash (ds->columns, &ctx);
+ axis_hash (ds->rows, &ctx);
for (r = range_map_first (&ds->sources); r != NULL;
r = range_map_next (&ds->sources, r))
{
@@ -1003,7 +1223,6 @@
unsigned long int end = range_map_node_get_end (r);
md4_process_bytes (&start, sizeof start, &ctx);
md4_process_bytes (&end, sizeof end, &ctx);
- /* FIXME: hash anything more? */
}
md4_process_bytes (&ds->column_min_alloc, sizeof ds->column_min_alloc,
&ctx);
@@ -1011,11 +1230,19 @@
return hash[0];
}
+/* Checks that datasheet DS contains has ROW_CNT rows, COLUMN_CNT
+ columns, and the same contents as ARRAY, reporting any
+ mismatches via mc_error. Then, adds DS to MC as a new state. */
static void
check_datasheet (struct mc *mc, struct datasheet *ds,
double array[MAX_ROWS][MAX_COLS],
size_t row_cnt, size_t column_cnt)
{
+ assert (row_cnt < MAX_ROWS);
+ assert (column_cnt < MAX_COLS);
+
+ /* If it's has a duplicate hash, discard the state before
+ checking its consistency, to save time. */
if (mc_discard_dup_state (mc, hash_datasheet (ds)))
{
datasheet_destroy (ds);
@@ -1047,6 +1274,7 @@
mc_add_state (mc, ds);
}
+/* Extracts the contents of DS into DATA. */
static void
extract_data (const struct datasheet *ds, double data[MAX_ROWS][MAX_COLS])
{
@@ -1054,6 +1282,8 @@
size_t row_cnt = datasheet_get_row_cnt (ds);
size_t row, col;
+ assert (row_cnt < MAX_ROWS);
+ assert (column_cnt < MAX_COLS);
for (row = 0; row < row_cnt; row++)
for (col = 0; col < column_cnt; col++)
{
@@ -1064,6 +1294,8 @@
}
}
+/* Clones the structure and contents of ODS into *DS,
+ and the contents of ODATA into DATA. */
static void
clone_model (const struct datasheet *ods, double odata[MAX_ROWS][MAX_COLS],
struct datasheet **ds_, double data[MAX_ROWS][MAX_COLS])
@@ -1073,15 +1305,15 @@
/* Clone ODS into DS. */
ds = *ds_ = xmalloc (sizeof *ds);
- ds->columns = clone_axis (ods->columns);
- ds->rows = clone_axis (ods->rows);
+ ds->columns = axis_clone (ods->columns);
+ ds->rows = axis_clone (ods->rows);
range_map_init (&ds->sources);
for (r = range_map_first (&ods->sources); r != NULL;
r = range_map_next (&ods->sources, r))
{
const struct source_info *osi = source_info_from_range_map (r);
struct source_info *si = xmalloc (sizeof *si);
- si->source = clone_source (osi->source);
+ si->source = source_clone (osi->source);
range_map_insert (&ds->sources, range_map_node_get_start (r),
range_map_node_get_width (r), &si->column_range);
}
@@ -1091,6 +1323,7 @@
memcpy (data, odata, MAX_ROWS * MAX_COLS * sizeof **data);
}
+/* "init" function for struct mc_class. */
static void
datasheet_mc_init (struct mc *mc)
{
@@ -1099,12 +1332,14 @@
if (params->backing_rows == 0 && params->backing_cols == 0)
{
+ /* Create unbacked datasheet. */
ds = datasheet_create (NULL);
mc_name_operation (mc, "empty datasheet");
check_datasheet (mc, ds, NULL, 0, 0);
}
else
{
+ /* Create datasheet with backing. */
struct casewriter *writer;
struct casereader *reader;
double data[MAX_ROWS][MAX_COLS];
@@ -1139,6 +1374,7 @@
}
}
+/* "mutate" function for struct mc_class. */
static void
datasheet_mc_mutate (struct mc *mc, const void *ods_)
{
@@ -1153,6 +1389,8 @@
extract_data (ods, odata);
+ /* Insert all possible numbers of columns in all possible
+ positions. */
for (pos = 0; pos <= column_cnt; pos++)
for (cnt = 0; cnt <= params->max_cols - column_cnt; cnt++)
if (mc_include_state (mc))
@@ -1181,6 +1419,8 @@
check_datasheet (mc, ds, data, row_cnt, column_cnt + cnt);
}
+ /* Delete all possible numbers of columns from all possible
+ positions. */
for (pos = 0; pos < column_cnt; pos++)
for (cnt = 0; cnt < column_cnt - pos; cnt++)
if (mc_include_state (mc))
@@ -1199,6 +1439,8 @@
check_datasheet (mc, ds, data, row_cnt, column_cnt - cnt);
}
+ /* Move all possible numbers of columns from all possible
+ existing positions to all possible new positions. */
for (pos = 0; pos < column_cnt; pos++)
for (cnt = 0; cnt < column_cnt - pos; cnt++)
for (new_pos = 0; new_pos < column_cnt - cnt; new_pos++)
@@ -1220,6 +1462,8 @@
check_datasheet (mc, ds, data, row_cnt, column_cnt);
}
+ /* Insert all possible numbers of rows in all possible
+ positions. */
for (pos = 0; pos <= row_cnt; pos++)
for (cnt = 0; cnt <= params->max_rows - row_cnt; cnt++)
if (mc_include_state (mc))
@@ -1249,6 +1493,8 @@
check_datasheet (mc, ds, data, row_cnt + cnt, column_cnt);
}
+ /* Delete all possible numbers of rows from all possible
+ positions. */
for (pos = 0; pos < row_cnt; pos++)
for (cnt = 0; cnt < row_cnt - pos; cnt++)
if (mc_include_state (mc))
@@ -1265,6 +1511,8 @@
check_datasheet (mc, ds, data, row_cnt - cnt, column_cnt);
}
+ /* Move all possible numbers of rows from all possible existing
+ positions to all possible new positions. */
for (pos = 0; pos < row_cnt; pos++)
for (cnt = 0; cnt < row_cnt - pos; cnt++)
for (new_pos = 0; new_pos < row_cnt - cnt; new_pos++)
@@ -1285,6 +1533,7 @@
}
}
+/* "destroy" function for struct mc_class. */
static void
datasheet_mc_destroy (const struct mc *mc UNUSED, void *ds_)
{
@@ -1292,6 +1541,13 @@
datasheet_destroy (ds);
}
+/* Executes the model checker on the datasheet test driver with
+ the given OPTIONS and passing in the given PARAMS, which must
+ point to a modifiable "struct datasheet_test_params". If any
+ value in PARAMS is out of range, it will be adjusted into the
+ valid range before running the test.
+
+ Returns the results of the model checking run. */
struct mc_results *
datasheet_test (struct mc_options *options, void *params_)
{
Index: datasheet.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/Attic/datasheet.h,v
retrieving revision 1.1.2.3
retrieving revision 1.1.2.4
diff -u -b -r1.1.2.3 -r1.1.2.4
--- datasheet.h 14 Apr 2007 23:02:14 -0000 1.1.2.3
+++ datasheet.h 18 Apr 2007 23:16:18 -0000 1.1.2.4
@@ -31,6 +31,9 @@
struct datasheet *datasheet_create (struct casereader *);
void datasheet_destroy (struct datasheet *);
+struct datasheet *datasheet_rename (struct datasheet *);
+
+bool datasheet_error (const struct datasheet *);
struct casereader *datasheet_make_reader (struct datasheet *);
@@ -47,7 +50,7 @@
/* Rows. */
casenumber datasheet_get_row_cnt (const struct datasheet *);
bool datasheet_insert_rows (struct datasheet *,
- casenumber before, struct ccase *,
+ casenumber before, struct ccase[],
casenumber cnt);
void datasheet_delete_rows (struct datasheet *,
casenumber first, casenumber cnt);
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Pspp-cvs] pspp/src/data datasheet.c datasheet.h [simpler-proc],
Ben Pfaff <=