X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fdeque.h;fp=src%2Flibpspp%2Fdeque.h;h=f9bf57d6355df8f2e4c552887746e7783e6741e2;hb=8b708f4291deb6ee408e8f62a694b638c581c40e;hp=0000000000000000000000000000000000000000;hpb=ac0bf135a197ff174ef3ea5e12db8cf93ec6523c;p=pspp-builds.git diff --git a/src/libpspp/deque.h b/src/libpspp/deque.h new file mode 100644 index 00000000..f9bf57d6 --- /dev/null +++ b/src/libpspp/deque.h @@ -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 +#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); \ +} + +#endif /* libpspp/deque.h */