From 84d8b182e81aea6cd7422611888192bcc1ac6980 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 30 Mar 2007 16:40:52 +0000 Subject: [PATCH] Deuglify deque code. Patch #5829. --- src/data/ChangeLog | 4 + src/data/procedure.c | 23 ++-- src/libpspp/ChangeLog | 10 ++ src/libpspp/automake.mk | 1 + src/libpspp/deque.c | 77 +++++++++++ src/libpspp/deque.h | 296 +++++++++++++++++++++------------------- 6 files changed, 257 insertions(+), 154 deletions(-) create mode 100644 src/libpspp/deque.c diff --git a/src/data/ChangeLog b/src/data/ChangeLog index 8422c60d..4a8535c4 100644 --- a/src/data/ChangeLog +++ b/src/data/ChangeLog @@ -1,3 +1,7 @@ +2007-03-30 Ben Pfaff + + * procedure.c: Adapt to new deque data structure. + Mon Feb 19 10:53:21 2007 John McCabe-Dansted Ben Pfaff diff --git a/src/data/procedure.c b/src/data/procedure.c index ed69420c..7a9b4321 100644 --- a/src/data/procedure.c +++ b/src/data/procedure.c @@ -26,7 +26,6 @@ #include #include #include -#include #include #include #include @@ -36,6 +35,7 @@ #include #include #include +#include #include #include @@ -78,7 +78,8 @@ struct dataset { /* 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 @@ proc_read (struct dataset *ds, struct ccase **c) /* 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 @@ open_active_file (struct dataset *ds) 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 @@ static bool 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 @@ lagged_case (const struct dataset *ds, int n_before) 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; } diff --git a/src/libpspp/ChangeLog b/src/libpspp/ChangeLog index e029f4e3..4a2c8263 100644 --- a/src/libpspp/ChangeLog +++ b/src/libpspp/ChangeLog @@ -1,3 +1,13 @@ +2007-03-30 Ben Pfaff + + 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 * automake.mk (src_libpspp_libpspp_a_SOURCES): Add diff --git a/src/libpspp/automake.mk b/src/libpspp/automake.mk index fd0c8632..cc099a5f 100644 --- a/src/libpspp/automake.mk +++ b/src/libpspp/automake.mk @@ -17,6 +17,7 @@ src_libpspp_libpspp_a_SOURCES = \ 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 \ diff --git a/src/libpspp/deque.c b/src/libpspp/deque.c new file mode 100644 index 00000000..3143ce41 --- /dev/null +++ b/src/libpspp/deque.c @@ -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 + +#include +#include + +#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; +} diff --git a/src/libpspp/deque.h b/src/libpspp/deque.h index f9bf57d6..be1121bf 100644 --- a/src/libpspp/deque.h +++ b/src/libpspp/deque.h @@ -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 #include #include -#include - -#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); \ +#include + +/* 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. */ + }; + +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); +} + +/* 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 */ -- 2.30.2