[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pspp-cvs] pspp/src data/ChangeLog data/procedure.c libpsp...
|
From: |
Ben Pfaff |
|
Subject: |
[Pspp-cvs] pspp/src data/ChangeLog data/procedure.c libpsp... |
|
Date: |
Fri, 30 Mar 2007 16:40:52 +0000 |
CVSROOT: /cvsroot/pspp
Module name: pspp
Changes by: Ben Pfaff <blp> 07/03/30 16:40:52
Modified files:
src/data : ChangeLog procedure.c
src/libpspp : ChangeLog automake.mk deque.h
Added files:
src/libpspp : deque.c
Log message:
Deuglify deque code. Patch #5829.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/ChangeLog?cvsroot=pspp&r1=1.108&r2=1.109
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/procedure.c?cvsroot=pspp&r1=1.25&r2=1.26
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/ChangeLog?cvsroot=pspp&r1=1.57&r2=1.58
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/automake.mk?cvsroot=pspp&r1=1.24&r2=1.25
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/deque.h?cvsroot=pspp&r1=1.1&r2=1.2
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/deque.c?cvsroot=pspp&rev=1.2
Patches:
Index: data/ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/ChangeLog,v
retrieving revision 1.108
retrieving revision 1.109
diff -u -b -r1.108 -r1.109
--- data/ChangeLog 19 Feb 2007 18:57:04 -0000 1.108
+++ data/ChangeLog 30 Mar 2007 16:40:52 -0000 1.109
@@ -1,3 +1,7 @@
+2007-03-30 Ben Pfaff <address@hidden>
+
+ * procedure.c: Adapt to new deque data structure.
+
Mon Feb 19 10:53:21 2007 John McCabe-Dansted <address@hidden>
Ben Pfaff <address@hidden>
Index: data/procedure.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/procedure.c,v
retrieving revision 1.25
retrieving revision 1.26
diff -u -b -r1.25 -r1.26
--- data/procedure.c 16 Jan 2007 00:14:41 -0000 1.25
+++ data/procedure.c 30 Mar 2007 16:40:52 -0000 1.26
@@ -26,7 +26,6 @@
#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>
@@ -36,6 +35,7 @@
#include <data/transformations.h>
#include <data/variable.h>
#include <libpspp/alloc.h>
+#include <libpspp/deque.h>
#include <libpspp/misc.h>
#include <libpspp/str.h>
@@ -78,7 +78,8 @@
/* Cases just before ("lagging") the current one. */
int n_lag; /* Number of cases to lag. */
- struct casedeque lagged_cases; /* Lagged cases. */
+ struct deque lag; /* Deque of lagged cases. */
+ struct ccase *lag_cases; /* Lagged cases managed by deque. */
/* Procedure data. */
bool is_open; /* Procedure open? */
@@ -295,9 +296,9 @@
/* 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),
+ while (deque_count (&ds->lag) >= ds->n_lag)
+ case_destroy (&ds->lag_cases[deque_pop_back (&ds->lag)]);
+ case_clone (&ds->lag_cases[deque_push_front (&ds->lag)],
&ds->trns_case);
}
@@ -420,7 +421,7 @@
ds->proc_sink->class->open (ds->proc_sink);
/* Allocate memory for lagged cases. */
- casedeque_init (&ds->lagged_cases, ds->n_lag);
+ ds->lag_cases = deque_init (&ds->lag, ds->n_lag, sizeof *ds->lag_cases);
}
/* Clears the variables in C that need to be cleared between
@@ -449,9 +450,9 @@
close_active_file (struct dataset *ds)
{
/* 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);
+ while (!deque_is_empty (&ds->lag))
+ case_destroy (&ds->lag_cases[deque_pop_back (&ds->lag)]);
+ free (ds->lag_cases);
/* Dictionary from before TEMPORARY becomes permanent. */
proc_cancel_temporary_transformations (ds);
@@ -483,8 +484,8 @@
assert (n_before >= 1);
assert (n_before <= ds->n_lag);
- if (n_before <= casedeque_count (&ds->lagged_cases))
- return casedeque_front (&ds->lagged_cases, n_before - 1);
+ if (n_before <= deque_count (&ds->lag))
+ return &ds->lag_cases[deque_front (&ds->lag, n_before - 1)];
else
return NULL;
}
Index: libpspp/ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/ChangeLog,v
retrieving revision 1.57
retrieving revision 1.58
diff -u -b -r1.57 -r1.58
--- libpspp/ChangeLog 25 Mar 2007 22:13:06 -0000 1.57
+++ libpspp/ChangeLog 30 Mar 2007 16:40:52 -0000 1.58
@@ -1,3 +1,13 @@
+2007-03-30 Ben Pfaff <address@hidden>
+
+ Patch #5829.
+
+ * automake.mk (src_libpspp_libpspp_a_SOURCES): Add deque.c.
+
+ * deque.h: Completely rewrote. Adapted client to new interface.
+
+ * deque.c: New file.
+
2007-03-25 Ben Pfaff <address@hidden>
* automake.mk (src_libpspp_libpspp_a_SOURCES): Add
Index: libpspp/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/automake.mk,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -b -r1.24 -r1.25
--- libpspp/automake.mk 25 Mar 2007 22:13:06 -0000 1.24
+++ libpspp/automake.mk 30 Mar 2007 16:40:52 -0000 1.25
@@ -17,6 +17,7 @@
src/libpspp/copyleft.c \
src/libpspp/copyleft.h \
src/libpspp/compiler.h \
+ src/libpspp/deque.c \
src/libpspp/deque.h \
src/libpspp/float-format.c \
src/libpspp/float-format.h \
Index: libpspp/deque.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/deque.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -b -r1.1 -r1.2
--- libpspp/deque.h 16 Jan 2007 00:14:41 -0000 1.1
+++ libpspp/deque.h 30 Mar 2007 16:40:52 -0000 1.2
@@ -16,155 +16,165 @@
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA. */
+/* Deque data structure.
+
+ This code slightly simplifies the implementation of a deque as
+ a circular queue. To use it, declare a "struct deque" and a
+ pointer to the element type. For example, for a deque of
+ "int"s:
+
+ struct deque deque;
+ int *data;
+
+ To initialize the deque with a initial capacity of 0:
+
+ deque_init_null (&deque);
+ data = NULL;
+
+ Alternatively, to initialize the deque with an initial minimum
+ capacity of, e.g., 4:
+
+ data = deque_init (&deque, 4, sizeof *data);
+
+ Functions that access elements in the deque return array
+ indexes. This is fairly convenient:
+
+ // Push X at the back of the deque.
+ data[deque_push_back (&deque)] = x;
+
+ // Pop off the front of the deque into X.
+ x = data[deque_pop_front (&deque)];
+
+ // Obtain the element just past the back of the deque as X.
+ x = data[deque_back (&deque, 1)];
+
+ The push functions will not expand the deque on their own.
+ Use the deque_expand function if necessary, as in:
+
+ // Push X at the back of the deque, first expanding the
+ // deque if necessary.
+ if (deque_is_full (&deque))
+ data = deque_expand (&deque, data, sizeof *data);
+ data[deque_push_back (&deque)] = x;
+
+ Expanding a deque will copy its elements from one memory
+ region to another using memcpy. Thus, your deque elements
+ must tolerate copying if their deque is to be expanded. */
+
#ifndef LIBPSPP_DEQUE_H
#define LIBPSPP_DEQUE_H 1
-#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
-#include <libpspp/compiler.h>
+#include <libpspp/assertion.h>
+
+/* A deque implemented as a circular buffer. */
+struct deque
+ {
+ 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. */
+ };
-#include "xalloc.h"
+void deque_init_null (struct deque *);
+void *deque_init (struct deque *, size_t capacity, size_t elem_size);
+void *deque_expand (struct deque *, void *, size_t elem_size);
+
+/* Returns the number of elements currently in DEQUE. */
+static inline size_t
+deque_count (const struct deque *deque)
+{
+ return deque->front - deque->back;
+}
+
+/* Returns the maximum number of elements that DEQUE can hold at
+ any time. (Use deque_expand to increase a deque's
+ capacity.) */
+static inline size_t
+deque_capacity (const struct deque *deque)
+{
+ return deque->capacity;
+}
+
+/* Returns true if DEQUE is currently empty (contains no
+ elements), false otherwise. */
+static inline bool
+deque_is_empty (const struct deque *deque)
+{
+ return deque_count (deque) == 0;
+}
+
+/* Returns true if DEQUE is currently full (cannot take any more
+ elements), false otherwise. */
+static inline bool
+deque_is_full (const struct deque *deque)
+{
+ return deque_count (deque) >= deque_capacity (deque);
+}
+
+/* Returns the index of 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 size_t
+deque_front (const struct deque *deque, size_t offset)
+{
+ assert (deque_count (deque) > offset);
+ return (deque->front - offset - 1) & (deque->capacity - 1);
+}
+
+/* Returns the index of 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 size_t
+deque_back (const struct deque *deque, size_t offset)
+{
+ assert (deque_count (deque) > offset);
+ return (deque->back + offset) & (deque->capacity - 1);
+}
+
+/* Adds a new element at the front of DEQUE, which must not be
+ full, and returns the index of the new element. The caller is
+ responsible for assigning a value to the returned element. */
+static inline size_t
+deque_push_front (struct deque *deque)
+{
+ assert (!deque_is_full (deque));
+ return deque->front++ & (deque->capacity - 1);
+}
+
+/* Adds a new element at the back of DEQUE, which must not be
+ full, and returns the index of the new element. The caller is
+ responsible for assigning a value to the returned element. */
+static inline size_t
+deque_push_back (struct deque *deque)
+{
+ assert (!deque_is_full (deque));
+ return --deque->back & (deque->capacity - 1);
+}
+
+/* Pops the front element off DEQUE (which must not be empty) and
+ returns its index. The element may be reused the next time an
+ element is pushed into DEQUE or when DEQUE is expanded. */
+static inline size_t
+deque_pop_front (struct deque *deque)
+{
+ assert (!deque_is_empty (deque));
+ return --deque->front & (deque->capacity - 1);
+}
-/* 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); \
+/* Pops the back element off DEQUE (which must not be empty) and
+ returns its index. The element may be reused the next time
+ an element is pushed into DEQUE or when DEQUE is expanded. */
+static inline size_t
+deque_pop_back (struct deque *deque)
+{
+ assert (!deque_is_empty (deque));
+ return deque->back++ & (deque->capacity - 1);
}
#endif /* libpspp/deque.h */
Index: libpspp/deque.c
===================================================================
RCS file: libpspp/deque.c
diff -N libpspp/deque.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ libpspp/deque.c 30 Mar 2007 16:40:52 -0000 1.2
@@ -0,0 +1,77 @@
+/* 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/deque.h>
+#include <string.h>
+
+#include "minmax.h"
+#include "xalloc.h"
+
+/* Initializes DEQUE as an empty deque with an initial capacity
+ of zero. */
+void
+deque_init_null (struct deque *deque)
+{
+ deque->capacity = 0;
+ deque->front = 0;
+ deque->back = 0;
+}
+
+/* Initializes DEQUE as an empty deque of elements ELEM_SIZE
+ bytes in size, with an initial capacity of at least
+ CAPACITY. Returns the initial deque data array. */
+void *
+deque_init (struct deque *deque, size_t capacity, size_t elem_size)
+{
+ void *data = NULL;
+ deque_init_null (deque);
+ if (capacity > 0)
+ {
+ deque->capacity = 1;
+ while (deque->capacity < capacity)
+ deque->capacity <<= 1;
+ data = xnmalloc (deque->capacity, elem_size);
+ }
+ return data;
+}
+
+/* Increases the capacity of DEQUE and returns a new deque data
+ array that replaces the old data array. */
+void *
+deque_expand (struct deque *deque, void *old_data_, size_t elem_size)
+{
+ size_t old_capacity = deque->capacity;
+ size_t new_capacity = MAX (4, old_capacity * 2);
+ char *old_data = old_data_;
+ char *new_data = xnmalloc (new_capacity, elem_size);
+ size_t idx, copy_cnt;
+ for (idx = deque->back; idx != deque->front; idx += copy_cnt)
+ {
+ size_t can_copy = old_capacity - (idx & (old_capacity - 1));
+ size_t want_copy = deque->front - idx;
+ copy_cnt = MIN (can_copy, want_copy);
+ memcpy (new_data + (idx & (new_capacity - 1)) * elem_size,
+ old_data + (idx & (old_capacity - 1)) * elem_size,
+ copy_cnt * elem_size);
+ }
+ deque->capacity = new_capacity;
+ free (old_data);
+ return new_data;
+}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Pspp-cvs] pspp/src data/ChangeLog data/procedure.c libpsp...,
Ben Pfaff <=