pspp-cvs
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Pspp-cvs] pspp/src libpspp/deque.h libpspp/automake.mk da... [simpler-p


From: Ben Pfaff
Subject: [Pspp-cvs] pspp/src libpspp/deque.h libpspp/automake.mk da... [simpler-proc]
Date: Wed, 28 Mar 2007 17:26:49 +0000

CVSROOT:        /cvsroot/pspp
Module name:    pspp
Branch:         simpler-proc
Changes by:     Ben Pfaff <blp> 07/03/28 17:26:48

Modified files:
        src/libpspp    : deque.h automake.mk 
        src/data       : procedure.c casewindow.c 
Added files:
        src/libpspp    : deque.c 
Removed files:
        src/data       : casedeque.h 

Log message:
        Rewrite and de-uglify deque code.
        Patch #5829.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/deque.h?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.1&r2=1.1.2.2
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/automake.mk?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.22.2.3&r2=1.22.2.4
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/deque.c?cvsroot=pspp&only_with_tag=simpler-proc&rev=1.1.2.1
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/procedure.c?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.25.2.1&r2=1.25.2.2
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/casewindow.c?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.1&r2=1.1.2.2
http://cvs.savannah.gnu.org/viewcvs/pspp/src/data/casedeque.h?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1&r2=0

Patches:
Index: libpspp/deque.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/deque.h,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -u -b -r1.1.2.1 -r1.1.2.2
--- libpspp/deque.h     19 Mar 2007 21:36:24 -0000      1.1.2.1
+++ libpspp/deque.h     28 Mar 2007 17:26:48 -0000      1.1.2.2
@@ -16,156 +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 <stdlib.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/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/automake.mk,v
retrieving revision 1.22.2.3
retrieving revision 1.22.2.4
diff -u -b -r1.22.2.3 -r1.22.2.4
--- libpspp/automake.mk 28 Mar 2007 04:58:42 -0000      1.22.2.3
+++ libpspp/automake.mk 28 Mar 2007 17:26:48 -0000      1.22.2.4
@@ -19,6 +19,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: data/procedure.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/procedure.c,v
retrieving revision 1.25.2.1
retrieving revision 1.25.2.2
diff -u -b -r1.25.2.1 -r1.25.2.2
--- data/procedure.c    19 Mar 2007 21:36:24 -0000      1.25.2.1
+++ data/procedure.c    28 Mar 2007 17:26:48 -0000      1.25.2.2
@@ -24,7 +24,6 @@
 #include <unistd.h>
 
 #include <data/case.h>
-#include <data/casedeque.h>
 #include <data/caseinit.h>
 #include <data/casereader.h>
 #include <data/casereader-private.h>
@@ -35,6 +34,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>
 
@@ -79,7 +79,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. */
   enum 
@@ -208,9 +209,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), c); 
+          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)], c); 
         }
 
       /* Write case to replacement active file. */
@@ -325,7 +326,7 @@
     }
 
   /* 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);
 }
 
 /* Closes the active file. */
@@ -333,9 +334,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);
@@ -377,8 +378,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: data/casewindow.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/data/Attic/casewindow.c,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -u -b -r1.1.2.1 -r1.1.2.2
--- data/casewindow.c   19 Mar 2007 21:36:24 -0000      1.1.2.1
+++ data/casewindow.c   28 Mar 2007 17:26:48 -0000      1.1.2.2
@@ -18,9 +18,14 @@
 
 #include <config.h>
 
-#include <data/casedeque.h>
 #include <data/casewindow.h>
+
+#include <stdlib.h>
+
 #include <data/case-tmpfile.h>
+#include <libpspp/assertion.h>
+#include <libpspp/compiler.h>
+#include <libpspp/deque.h>
 
 #include "xalloc.h"
 
@@ -160,58 +165,64 @@
   return !cw->ok;
 }
 
+struct casewindow_memory 
+  {
+    struct deque deque;
+    struct ccase *cases;
+  };
+
 static void *
 casewindow_memory_create (size_t value_cnt UNUSED) 
 {
-  struct casedeque *deque = xmalloc (sizeof *deque);
-  casedeque_init (deque, 4);
-  return deque;
+  struct casewindow_memory *cwm = xmalloc (sizeof *cwm);
+  cwm->cases = deque_init (&cwm->deque, 4, sizeof *cwm->cases);
+  return cwm;
 }
 
 static bool
-casewindow_memory_destroy (void *deque_) 
+casewindow_memory_destroy (void *cwm_) 
 {
-  struct casedeque *deque = deque_;
-  while (!casedeque_is_empty (deque)) 
-    case_destroy (casedeque_pop_front (deque));
-  casedeque_destroy (deque);
-  free (deque);
+  struct casewindow_memory *cwm = cwm_;
+  while (!deque_is_empty (&cwm->deque)) 
+    case_destroy (&cwm->cases[deque_pop_front (&cwm->deque)]);
+  free (cwm->cases);
+  free (cwm);
   return true;
 }
 
 static bool
-casewindow_memory_push_head (void *deque_, struct ccase *c)
+casewindow_memory_push_head (void *cwm_, struct ccase *c)
 {
-  struct casedeque *deque = deque_;
-  if (casedeque_is_full (deque))
-    casedeque_expand (deque);
-  case_move (casedeque_push_back (deque), c);
+  struct casewindow_memory *cwm = cwm_;
+  if (deque_is_full (&cwm->deque))
+    cwm->cases = deque_expand (&cwm->deque, cwm->cases, sizeof *cwm->cases);
+  case_move (&cwm->cases[deque_push_back (&cwm->deque)], c);
   return true;
 }
 
 static bool
-casewindow_memory_pop_tail (void *deque_, casenumber case_cnt)
+casewindow_memory_pop_tail (void *cwm_, casenumber case_cnt)
 {
-  struct casedeque *deque = deque_;
-  assert (casedeque_count (deque) >= case_cnt);
+  struct casewindow_memory *cwm = cwm_;
+  assert (deque_count (&cwm->deque) >= case_cnt);
   while (case_cnt-- > 0) 
-    case_destroy (casedeque_pop_front (deque));
+    case_destroy (&cwm->cases[deque_pop_front (&cwm->deque)]);
   return true;
 }
 
 static bool
-casewindow_memory_get_case (void *deque_, casenumber ofs, struct ccase *c) 
+casewindow_memory_get_case (void *cwm_, casenumber ofs, struct ccase *c) 
 {
-  struct casedeque *deque = deque_;
-  case_clone (c, casedeque_front (deque, ofs));
+  struct casewindow_memory *cwm = cwm_;
+  case_clone (c, &cwm->cases[deque_front (&cwm->deque, ofs)]);
   return true;
 }
 
 static casenumber
-casewindow_memory_get_case_cnt (const void *deque_) 
+casewindow_memory_get_case_cnt (const void *cwm_) 
 {
-  const struct casedeque *deque = deque_;
-  return casedeque_count (deque);
+  const struct casewindow_memory *cwm = cwm_;
+  return deque_count (&cwm->deque);
 }
 
 static const struct casewindow_class casewindow_memory_class = 

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     28 Mar 2007 17:26:48 -0000      1.1.2.1
@@ -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;
+}

Index: data/casedeque.h
===================================================================
RCS file: data/casedeque.h
diff -N data/casedeque.h
--- data/casedeque.h    16 Jan 2007 00:14:41 -0000      1.1
+++ /dev/null   1 Jan 1970 00:00:00 -0000
@@ -1,27 +0,0 @@
-/* PSPP - computes sample statistics.
-   Copyright (C) 2007 Free Software Foundation, Inc.
-
-   This program is free software; you can redistribute it and/or
-   modify it under the terms of the GNU General Public License as
-   published by the Free Software Foundation; either version 2 of the
-   License, or (at your option) any later version.
-
-   This program is distributed in the hope that it will be useful, but
-   WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   General Public License for more details.
-
-   You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
-   02110-1301, USA. */
-
-#ifndef 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 */




reply via email to

[Prev in Thread] Current Thread [Next in Thread]