Add a deque, implemented as a circular queue, to libpspp.
authorBen Pfaff <blp@gnu.org>
Tue, 16 Jan 2007 00:14:41 +0000 (00:14 +0000)
committerBen Pfaff <blp@gnu.org>
Tue, 16 Jan 2007 00:14:41 +0000 (00:14 +0000)
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.

src/data/ChangeLog
src/data/automake.mk
src/data/casedeque.h [new file with mode: 0644]
src/data/procedure.c
src/data/procedure.h
src/language/expressions/parse.c
src/libpspp/ChangeLog
src/libpspp/automake.mk
src/libpspp/deque.h [new file with mode: 0644]

index df9915d5bfaaed372cfed8bf3bdde6440b950f26..fab0145ef228e9d3b9a7599b20def32916878219 100644 (file)
@@ -1,3 +1,22 @@
+Sun Jan 14 21:41:12 2007  Ben Pfaff  <blp@gnu.org>
+
+       * 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  <blp@gnu.org>
+
+       * 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 <john@darrington.wattle.id.au>
 
        * dictionary.c procedure.c: More changes to ensure that callbacks occur
index 0b9ab88544d8eced4dc0e28a5ab1c03d6b362746..54fddf05162f20ca2e4d7e5094fde20aa0e108fe 100644 (file)
@@ -13,6 +13,7 @@ src_data_libdata_a_SOURCES = \
        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 \
diff --git a/src/data/casedeque.h b/src/data/casedeque.h
new file mode 100644 (file)
index 0000000..189b514
--- /dev/null
@@ -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 b6f988aabbaf46b2707940aca2e646504ced5ffa..ed69420c3e464bd71221bd3bff5ee0ad3e727037 100644 (file)
@@ -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 @@ struct dataset {
   /* 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 bool internal_procedure (struct dataset *ds, case_func *,
 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);
 \f
@@ -294,9 +292,14 @@ proc_read (struct dataset *ds, struct ccase **c)
       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 @@ open_active_file (struct dataset *ds)
   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 @@ clear_case (const struct dataset *ds, struct ccase *c)
 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 @@ close_active_file (struct dataset *ds)
 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 @@ dataset_set_dict (struct dataset *ds, struct dictionary *dict)
   dict_destroy (old_dict);
 }
 
-int
-dataset_n_lag (const struct dataset *ds)
+void 
+dataset_need_lag (struct dataset *ds, int n_before)
 {
-  return ds->n_lag;
+  ds->n_lag = MAX (ds->n_lag, n_before);
 }
 
-void
-dataset_set_n_lag (struct dataset *ds, int n_lag)
-{
-  ds->n_lag = n_lag;
-}
-
-
 struct casefile_factory *
 dataset_get_casefile_factory (const struct dataset *ds)
 {
index f4d473b9aeaa6ee3ac321deea1f19766f0ac5618..0e8d286bde1c481cb6b6b166009cdd7aa4f45dda 100644 (file)
@@ -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 @@ struct ccase *lagged_case (const struct dataset *ds, int n_before);
 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 272090b17db88983700ae9c1fe952d75dc80abb1..5c1e4632fd5105d50ea840d4fdb93381dc9f11ec 100644 (file)
@@ -1278,18 +1278,14 @@ parse_function (struct lexer *lexer, struct expression *e)
   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 ecdad8745e474412efa01b95103c1b1a195f46f5..ddecc4dff587f0b0f8d748ccde0f98380ca73d6d 100644 (file)
@@ -1,3 +1,9 @@
+Sun Jan 14 21:44:18 2007  Ben Pfaff  <blp@gnu.org>
+
+       * automake.mk: Add deque.h to sources.
+       
+       * deque.h: New file.
+
 Wed Jan 10 06:49:38 2007  Ben Pfaff  <blp@gnu.org>
 
        * automake.mk: Add heap.c, heap.h to sources.
index 942a72f30b08767426727a0ad7ce874864e919c2..0dcdc1b1b4d8b74c08feb7253d0a12bd43bd68e1 100644 (file)
@@ -15,6 +15,7 @@ src_libpspp_libpspp_a_SOURCES = \
        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 \
diff --git a/src/libpspp/deque.h b/src/libpspp/deque.h
new file mode 100644 (file)
index 0000000..f9bf57d
--- /dev/null
@@ -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 */