[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pspp-cvs] pspp/src data/ChangeLog data/automake.mk data/p...
From: |
Ben Pfaff |
Subject: |
[Pspp-cvs] pspp/src data/ChangeLog data/automake.mk data/p... |
Date: |
Tue, 16 Jan 2007 00:14:41 +0000 |
CVSROOT: /cvsroot/pspp
Module name: pspp
Changes by: Ben Pfaff <blp> 07/01/16 00:14:41
Modified files:
src/data : ChangeLog automake.mk procedure.c procedure.h
src/language/expressions: parse.c
src/libpspp : ChangeLog automake.mk
Added files:
src/data : casedeque.h
src/libpspp : deque.h
Log message:
Add a deque, implemented as a circular queue, to libpspp.
Demonstrate how to use it by instantiating it for use as a deque of
cases and then uses that "casedeque" to reimplement the LAG
functionality for procedures.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/ChangeLog?cvsroot=pspp&r1=1.98&r2=1.99
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/automake.mk?cvsroot=pspp&r1=1.14&r2=1.15
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/procedure.c?cvsroot=pspp&r1=1.24&r2=1.25
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/procedure.h?cvsroot=pspp&r1=1.11&r2=1.12
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/casedeque.h?cvsroot=pspp&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/pspp/src/language/expressions/parse.c?cvsroot=pspp&r1=1.22&r2=1.23
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/ChangeLog?cvsroot=pspp&r1=1.47&r2=1.48
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/automake.mk?cvsroot=pspp&r1=1.19&r2=1.20
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/deque.h?cvsroot=pspp&rev=1.1
Patches:
Index: data/ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/ChangeLog,v
retrieving revision 1.98
retrieving revision 1.99
diff -u -b -r1.98 -r1.99
--- data/ChangeLog 10 Jan 2007 09:22:42 -0000 1.98
+++ data/ChangeLog 16 Jan 2007 00:14:41 -0000 1.99
@@ -1,3 +1,22 @@
+Sun Jan 14 21:41:12 2007 Ben Pfaff <address@hidden>
+
+ * automake.mk: Add casedeque.h to sources.
+
+ * casedeque.h: New file.
+
+ * procedure.c: (struct dataset) Change lag_count, lag_head,
+ lag_queue member into single struct casedeque member. Update all
+ users to use the casedeque instead.
+ (lag_case) Removed.
+
+Sun Jan 14 21:43:12 2007 Ben Pfaff <address@hidden>
+
+ * procedure.c: Simplify lagged cases interface. Updated all
+ clients--well, the only client--to use the simplified interface.
+ (dataset_n_lag) Removed.
+ (dataset_set_n_lag) Removed.
+ (dataset_need_lag) New function.
+
Tue Jan 9 07:20:05 WST 2007 John Darrington <address@hidden>
* dictionary.c procedure.c: More changes to ensure that callbacks occur
Index: data/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/automake.mk,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -b -r1.14 -r1.15
--- data/automake.mk 4 Jan 2007 08:15:27 -0000 1.14
+++ data/automake.mk 16 Jan 2007 00:14:41 -0000 1.15
@@ -13,6 +13,7 @@
src/data/case-source.c \
src/data/case-source.h \
src/data/case.c \
+ src/data/casedeque.h \
src/data/casefilter.c \
src/data/casefilter.h \
src/data/casefile.h \
Index: data/procedure.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/procedure.c,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -b -r1.24 -r1.25
--- data/procedure.c 10 Jan 2007 09:22:42 -0000 1.24
+++ data/procedure.c 16 Jan 2007 00:14:41 -0000 1.25
@@ -26,6 +26,7 @@
#include <data/case-source.h>
#include <data/case-sink.h>
#include <data/case.h>
+#include <data/casedeque.h>
#include <data/casefile.h>
#include <data/fastfile.h>
#include <data/dictionary.h>
@@ -75,11 +76,9 @@
/* Time at which proc was last invoked. */
time_t last_proc_invocation;
- /* Lag queue. */
+ /* Cases just before ("lagging") the current one. */
int n_lag; /* Number of cases to lag. */
- int lag_count; /* Number of cases in lag_queue so far. */
- int lag_head; /* Index where next case will be added. */
- struct ccase *lag_queue; /* Array of n_lag ccase * elements. */
+ struct casedeque lagged_cases; /* Lagged cases. */
/* Procedure data. */
bool is_open; /* Procedure open? */
@@ -100,7 +99,6 @@
static void update_last_proc_invocation (struct dataset *ds);
static void create_trns_case (struct ccase *, struct dictionary *);
static void open_active_file (struct dataset *ds);
-static void lag_case (struct dataset *ds, const struct ccase *c);
static void clear_case (const struct dataset *ds, struct ccase *c);
static bool close_active_file (struct dataset *ds);
@@ -294,9 +292,14 @@
if (retval != TRNS_CONTINUE)
continue;
- /* Write case to LAG queue. */
- if (ds->n_lag)
- lag_case (ds, &ds->trns_case);
+ /* Write case to collection of lagged cases. */
+ if (ds->n_lag > 0)
+ {
+ while (casedeque_count (&ds->lagged_cases) >= ds->n_lag)
+ case_destroy (casedeque_pop_back (&ds->lagged_cases));
+ case_clone (casedeque_push_front (&ds->lagged_cases),
+ &ds->trns_case);
+ }
/* Write case to replacement active file. */
ds->cases_written++;
@@ -416,29 +419,8 @@
if (ds->proc_sink->class->open != NULL)
ds->proc_sink->class->open (ds->proc_sink);
- /* Allocate memory for lag queue. */
- if (ds->n_lag > 0)
- {
- int i;
-
- ds->lag_count = 0;
- ds->lag_head = 0;
- ds->lag_queue = xnmalloc (ds->n_lag, sizeof *ds->lag_queue);
- for (i = 0; i < ds->n_lag; i++)
- case_nullify (&ds->lag_queue[i]);
- }
-}
-
-/* Add C to the lag queue. */
-static void
-lag_case (struct dataset *ds, const struct ccase *c)
-{
- if (ds->lag_count < ds->n_lag)
- ds->lag_count++;
- case_destroy (&ds->lag_queue[ds->lag_head]);
- case_clone (&ds->lag_queue[ds->lag_head], c);
- if (++ds->lag_head >= ds->n_lag)
- ds->lag_head = 0;
+ /* Allocate memory for lagged cases. */
+ casedeque_init (&ds->lagged_cases, ds->n_lag);
}
/* Clears the variables in C that need to be cleared between
@@ -466,16 +448,10 @@
static bool
close_active_file (struct dataset *ds)
{
- /* Free memory for lag queue, and turn off lagging. */
- if (ds->n_lag > 0)
- {
- int i;
-
- for (i = 0; i < ds->n_lag; i++)
- case_destroy (&ds->lag_queue[i]);
- free (ds->lag_queue);
- ds->n_lag = 0;
- }
+ /* Free memory for lagged cases. */
+ while (!casedeque_is_empty (&ds->lagged_cases))
+ case_destroy (casedeque_pop_back (&ds->lagged_cases));
+ casedeque_destroy (&ds->lagged_cases);
/* Dictionary from before TEMPORARY becomes permanent. */
proc_cancel_temporary_transformations (ds);
@@ -504,16 +480,11 @@
struct ccase *
lagged_case (const struct dataset *ds, int n_before)
{
- assert (n_before >= 1 );
+ assert (n_before >= 1);
assert (n_before <= ds->n_lag);
- if (n_before <= ds->lag_count)
- {
- int index = ds->lag_head - n_before;
- if (index < 0)
- index += ds->n_lag;
- return &ds->lag_queue[index];
- }
+ if (n_before <= casedeque_count (&ds->lagged_cases))
+ return casedeque_front (&ds->lagged_cases, n_before - 1);
else
return NULL;
}
@@ -1028,19 +999,12 @@
dict_destroy (old_dict);
}
-int
-dataset_n_lag (const struct dataset *ds)
-{
- return ds->n_lag;
-}
-
void
-dataset_set_n_lag (struct dataset *ds, int n_lag)
+dataset_need_lag (struct dataset *ds, int n_before)
{
- ds->n_lag = n_lag;
+ ds->n_lag = MAX (ds->n_lag, n_before);
}
-
struct casefile_factory *
dataset_get_casefile_factory (const struct dataset *ds)
{
Index: data/procedure.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/procedure.h,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -b -r1.11 -r1.12
--- data/procedure.h 1 Jan 2007 01:44:33 -0000 1.11
+++ data/procedure.h 16 Jan 2007 00:14:41 -0000 1.12
@@ -1,5 +1,5 @@
/* PSPP - computes sample statistics.
- Copyright (C) 1997-9, 2000, 2006 Free Software Foundation, Inc.
+ Copyright (C) 1997-9, 2000, 2006, 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
@@ -116,8 +116,6 @@
inline struct dictionary *dataset_dict (const struct dataset *ds);
inline void dataset_set_dict ( struct dataset *ds, struct dictionary *dict);
-inline int dataset_n_lag (const struct dataset *ds);
-inline void dataset_set_n_lag (struct dataset *ds, int n_lag);
-
+void dataset_need_lag (struct dataset *ds, int n_before);
#endif /* procedure.h */
Index: language/expressions/parse.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/language/expressions/parse.c,v
retrieving revision 1.22
retrieving revision 1.23
diff -u -b -r1.22 -r1.23
--- language/expressions/parse.c 15 Dec 2006 00:16:02 -0000 1.22
+++ language/expressions/parse.c 16 Jan 2007 00:14:41 -0000 1.23
@@ -1278,18 +1278,14 @@
n->composite.min_valid = min_valid != -1 ? min_valid : f->array_min_elems;
if (n->type == OP_LAG_Vn || n->type == OP_LAG_Vs)
- {
- if (dataset_n_lag (e->ds) < 1)
- dataset_set_n_lag (e->ds, 1);
- }
+ dataset_need_lag (e->ds, 1);
else if (n->type == OP_LAG_Vnn || n->type == OP_LAG_Vsn)
{
int n_before;
assert (n->composite.arg_cnt == 2);
assert (n->composite.args[1]->type == OP_pos_int);
n_before = n->composite.args[1]->integer.i;
- if ( dataset_n_lag (e->ds) < n_before)
- dataset_set_n_lag (e->ds, n_before);
+ dataset_need_lag (e->ds, n_before);
}
free (args);
Index: libpspp/ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/ChangeLog,v
retrieving revision 1.47
retrieving revision 1.48
diff -u -b -r1.47 -r1.48
--- libpspp/ChangeLog 10 Jan 2007 14:50:16 -0000 1.47
+++ libpspp/ChangeLog 16 Jan 2007 00:14:41 -0000 1.48
@@ -1,3 +1,9 @@
+Sun Jan 14 21:44:18 2007 Ben Pfaff <address@hidden>
+
+ * automake.mk: Add deque.h to sources.
+
+ * deque.h: New file.
+
Wed Jan 10 06:49:38 2007 Ben Pfaff <address@hidden>
* automake.mk: Add heap.c, heap.h to sources.
Index: libpspp/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/automake.mk,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -b -r1.19 -r1.20
--- libpspp/automake.mk 10 Jan 2007 14:50:16 -0000 1.19
+++ libpspp/automake.mk 16 Jan 2007 00:14:41 -0000 1.20
@@ -15,6 +15,7 @@
src/libpspp/copyleft.c \
src/libpspp/copyleft.h \
src/libpspp/compiler.h \
+ src/libpspp/deque.h \
src/libpspp/float-format.c \
src/libpspp/float-format.h \
src/libpspp/freaderror.c \
Index: data/casedeque.h
===================================================================
RCS file: data/casedeque.h
diff -N data/casedeque.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ data/casedeque.h 16 Jan 2007 00:14:41 -0000 1.1
@@ -0,0 +1,27 @@
+/* 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 DATA_CASEDEQUE_H
+#define DATA_CASEDEQUE_H 1
+
+#include <data/case.h>
+#include <libpspp/deque.h>
+
+DEQUE_DECLARE (casedeque, struct ccase)
+
+#endif /* data/casedeque.h */
Index: libpspp/deque.h
===================================================================
RCS file: libpspp/deque.h
diff -N libpspp/deque.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ libpspp/deque.h 16 Jan 2007 00:14:41 -0000 1.1
@@ -0,0 +1,170 @@
+/* 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_DEQUE_H
+#define LIBPSPP_DEQUE_H 1
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#include <libpspp/compiler.h>
+
+#include "xalloc.h"
+
+/* Declares data and functions for a deque whose elements have
+ the given ELEMENT_TYPE. Instances of the deque are declared
+ as "struct NAME", and each function that operates on the deque
+ has NAME_ as a prefix. */
+#define DEQUE_DECLARE(NAME, ELEMENT_TYPE) \
+/* An instance of the deque. */ \
+struct NAME \
+ { \
+ size_t capacity; /* Capacity, which must be a power of 2. */ \
+ size_t front; /* One past the front of the queue. */ \
+ size_t back; /* The back of the queue. */ \
+ ELEMENT_TYPE *data; /* Pointer to CAPACITY elements. */ \
+ }; \
+ \
+/* Initializes DEQUE as an empty deque that can store at least \
+ CAPACITY elements. (The actual capacity may be larger and is \
+ always a power of 2.) */ \
+static inline void \
+NAME##_init (struct NAME *deque, size_t capacity) \
+{ \
+ deque->capacity = 1; \
+ while (deque->capacity < capacity) \
+ deque->capacity <<= 1; \
+ deque->front = deque->back = 0; \
+ deque->data = xnmalloc (deque->capacity, sizeof *deque->data); \
+} \
+ \
+/* Destroys DEQUE, which must be empty. */ \
+static inline void \
+NAME##_destroy (struct NAME *deque) \
+{ \
+ free (deque->data); \
+} \
+ \
+/* Returns the number of elements currently in DEQUE. */ \
+static inline size_t \
+NAME##_count (const struct NAME *deque) \
+{ \
+ return deque->front - deque->back; \
+} \
+ \
+/* Returns the maximum number of elements that DEQUE can hold at \
+ any time. */ \
+static inline size_t \
+NAME##_capacity (const struct NAME *deque) \
+{ \
+ return deque->capacity; \
+} \
+ \
+/* Returns true if DEQUE is currently empty (contains no \
+ elements), false otherwise. */ \
+static inline bool \
+NAME##_is_empty (const struct NAME *deque) \
+{ \
+ return NAME##_count (deque) == 0; \
+} \
+ \
+/* Returns true if DEQUE is currently full (cannot take any more \
+ elements), false otherwise. */ \
+static inline bool \
+NAME##_is_full (const struct NAME *deque) \
+{ \
+ return NAME##_count (deque) >= NAME##_capacity (deque); \
+} \
+ \
+/* Returns the element in DEQUE that is OFFSET elements from its \
+ front. A value 0 for OFFSET requests the element at the \
+ front, a value of 1 the element just behind the front, and so \
+ on. OFFSET must be less than the current number of elements \
+ in DEQUE. */ \
+static inline ELEMENT_TYPE * \
+NAME##_front (const struct NAME *deque, size_t offset) \
+{ \
+ assert (NAME##_count (deque) > offset); \
+ return &deque->data[(deque->front - offset - 1) & (deque->capacity - 1)]; \
+} \
+ \
+/* Returns the element in DEQUE that is OFFSET elements from its \
+ back. A value 0 for OFFSET requests the element at the back, \
+ a value of 1 the element just ahead of the back, and so on. \
+ OFFSET must be less than the current number of elements in \
+ DEQUE. */ \
+static inline ELEMENT_TYPE * \
+NAME##_back (const struct NAME *deque, size_t offset) \
+{ \
+ assert (NAME##_count (deque) > offset); \
+ return &deque->data[(deque->back + offset) & (deque->capacity - 1)]; \
+} \
+ \
+/* Adds and returns the address of a new element at the front of \
+ DEQUE, which must not be full. The caller is responsible for \
+ assigning a value to the returned element. */ \
+static inline ELEMENT_TYPE * \
+NAME##_push_front (struct NAME *deque) \
+{ \
+ assert (!NAME##_is_full (deque)); \
+ return &deque->data[deque->front++ & (deque->capacity - 1)]; \
+} \
+ \
+/* Adds and returns the address of a new element at the back of \
+ DEQUE, which must not be full. The caller is responsible for \
+ assigning a value to the returned element. */ \
+static inline ELEMENT_TYPE * \
+NAME##_push_back (struct NAME *deque) \
+{ \
+ assert (!NAME##_is_full (deque)); \
+ return &deque->data[--deque->back & (deque->capacity - 1)]; \
+} \
+ \
+/* Pops the front element off DEQUE (which must not be empty) and \
+ returns its address. The element may be reused the next time \
+ an element is pushed into DEQUE or when DEQUE is expanded. */ \
+static inline ELEMENT_TYPE * \
+NAME##_pop_front (struct NAME *deque) \
+{ \
+ assert (!NAME##_is_empty (deque)); \
+ return &deque->data[--deque->front & (deque->capacity - 1)]; \
+} \
+ \
+/* Pops the back element off DEQUE (which must not be empty) and \
+ returns its address. The element may be reused the next time \
+ an element is pushed into DEQUE or when DEQUE is expanded. */ \
+static inline ELEMENT_TYPE * \
+NAME##_pop_back (struct NAME *deque) \
+{ \
+ assert (!NAME##_is_empty (deque)); \
+ return &deque->data[deque->back++ & (deque->capacity - 1)]; \
+} \
+ \
+/* Expands DEQUE, doubling its capacity. */ \
+static inline void \
+NAME##_expand (struct NAME *deque) \
+{ \
+ struct NAME old_deque = *deque; \
+ NAME##_init (deque, deque->capacity * 2); \
+ while (!NAME##_is_empty (&old_deque)) \
+ *NAME##_push_front (deque) = *NAME##_pop_back (&old_deque); \
+ free (old_deque.data); \
+}
+
+#endif /* libpspp/deque.h */
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Pspp-cvs] pspp/src data/ChangeLog data/automake.mk data/p...,
Ben Pfaff <=