src/libpspp/deque.h

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 #ifndef LIBPSPP_DEQUE_H
  20 #define LIBPSPP_DEQUE_H 1
  21
  22 #include <assert.h>
  23 #include <stdbool.h>
  24 #include <stddef.h>
  25
  26 #include <libpspp/compiler.h>
  27
  28 #include "xalloc.h"
  29
  30 /* Declares data and functions for a deque whose elements have
  31    the given ELEMENT_TYPE.  Instances of the deque are declared
  32    as "struct NAME", and each function that operates on the deque
  33    has NAME_ as a prefix. */
  34 #define DEQUE_DECLARE(NAME, ELEMENT_TYPE)                                   \
  35 /* An instance of the deque. */                                             \
  36 struct NAME                                                                 \
  37   {                                                                         \
  38     size_t capacity;    /* Capacity, which must be a power of 2. */         \
  39     size_t front;       /* One past the front of the queue. */              \
  40     size_t back;        /* The back of the queue. */                        \
  41     ELEMENT_TYPE *data; /* Pointer to CAPACITY elements. */                 \
  42   };                                                                        \
  43                                                                             \
  44 /* Initializes DEQUE as an empty deque that can store at least              \
  45    CAPACITY elements.  (The actual capacity may be larger and is            \
  46    always a power of 2.) */                                                 \
  47 static inline void                                                          \
  48 NAME##_init (struct NAME *deque, size_t capacity)                           \
  49 {                                                                           \
  50   deque->capacity = 1;                                                      \
  51   while (deque->capacity < capacity)                                        \
  52     deque->capacity <<= 1;                                                  \
  53   deque->front = deque->back = 0;                                           \
  54   deque->data = xnmalloc (deque->capacity, sizeof *deque->data);            \
  55 }                                                                           \
  56                                                                             \
  57 /* Destroys DEQUE, which must be empty. */                                  \
  58 static inline void                                                          \
  59 NAME##_destroy (struct NAME *deque)                                         \
  60 {                                                                           \
  61   free (deque->data);                                                       \
  62 }                                                                           \
  63                                                                             \
  64 /* Returns the number of elements currently in DEQUE. */                    \
  65 static inline size_t                                                        \
  66 NAME##_count (const struct NAME *deque)                                     \
  67 {                                                                           \
  68   return deque->front - deque->back;                                        \
  69 }                                                                           \
  70                                                                             \
  71 /* Returns the maximum number of elements that DEQUE can hold at            \
  72    any time. */                                                             \
  73 static inline size_t                                                        \
  74 NAME##_capacity (const struct NAME *deque)                                  \
  75 {                                                                           \
  76   return deque->capacity;                                                   \
  77 }                                                                           \
  78                                                                             \
  79 /* Returns true if DEQUE is currently empty (contains no                    \
  80    elements), false otherwise. */                                           \
  81 static inline bool                                                          \
  82 NAME##_is_empty (const struct NAME *deque)                                  \
  83 {                                                                           \
  84   return NAME##_count (deque) == 0;                                         \
  85 }                                                                           \
  86                                                                             \
  87 /* Returns true if DEQUE is currently full (cannot take any more            \
  88    elements), false otherwise. */                                           \
  89 static inline bool                                                          \
  90 NAME##_is_full (const struct NAME *deque)                                   \
  91 {                                                                           \
  92   return NAME##_count (deque) >= NAME##_capacity (deque);                   \
  93 }                                                                           \
  94                                                                             \
  95 /* Returns the element in DEQUE that is OFFSET elements from its            \
  96    front.  A value 0 for OFFSET requests the element at the                 \
  97    front, a value of 1 the element just behind the front, and so            \
  98    on.  OFFSET must be less than the current number of elements             \
  99    in DEQUE. */                                                             \
 100 static inline ELEMENT_TYPE *                                                \
 101 NAME##_front (const struct NAME *deque, size_t offset)                      \
 102 {                                                                           \
 103   assert (NAME##_count (deque) > offset);                                   \
 104   return &deque->data[(deque->front - offset - 1) & (deque->capacity - 1)]; \
 105 }                                                                           \
 106                                                                             \
 107 /* Returns the element in DEQUE that is OFFSET elements from its            \
 108    back.  A value 0 for OFFSET requests the element at the back,            \
 109    a value of 1 the element just ahead of the back, and so on.              \
 110    OFFSET must be less than the current number of elements in               \
 111    DEQUE. */                                                                \
 112 static inline ELEMENT_TYPE *                                                \
 113 NAME##_back (const struct NAME *deque, size_t offset)                       \
 114 {                                                                           \
 115   assert (NAME##_count (deque) > offset);                                   \
 116   return &deque->data[(deque->back + offset) & (deque->capacity - 1)];      \
 117 }                                                                           \
 118                                                                             \
 119 /* Adds and returns the address of a new element at the front of            \
 120    DEQUE, which must not be full.  The caller is responsible for            \
 121    assigning a value to the returned element. */                            \
 122 static inline ELEMENT_TYPE *                                                \
 123 NAME##_push_front (struct NAME *deque)                                      \
 124 {                                                                           \
 125   assert (!NAME##_is_full (deque));                                         \
 126   return &deque->data[deque->front++ & (deque->capacity - 1)];              \
 127 }                                                                           \
 128                                                                             \
 129 /* Adds and returns the address of a new element at the back of             \
 130    DEQUE, which must not be full.  The caller is responsible for            \
 131    assigning a value to the returned element. */                            \
 132 static inline ELEMENT_TYPE *                                                \
 133 NAME##_push_back (struct NAME *deque)                                       \
 134 {                                                                           \
 135   assert (!NAME##_is_full (deque));                                         \
 136   return &deque->data[--deque->back & (deque->capacity - 1)];               \
 137 }                                                                           \
 138                                                                             \
 139 /* Pops the front element off DEQUE (which must not be empty) and           \
 140    returns its address.  The element may be reused the next time            \
 141    an element is pushed into DEQUE or when DEQUE is expanded. */            \
 142 static inline ELEMENT_TYPE *                                                \
 143 NAME##_pop_front (struct NAME *deque)                                       \
 144 {                                                                           \
 145   assert (!NAME##_is_empty (deque));                                        \
 146   return &deque->data[--deque->front & (deque->capacity - 1)];              \
 147 }                                                                           \
 148                                                                             \
 149 /* Pops the back element off DEQUE (which must not be empty) and            \
 150    returns its address.  The element may be reused the next time            \
 151    an element is pushed into DEQUE or when DEQUE is expanded. */            \
 152 static inline ELEMENT_TYPE *                                                \
 153 NAME##_pop_back (struct NAME *deque)                                        \
 154 {                                                                           \
 155   assert (!NAME##_is_empty (deque));                                        \
 156   return &deque->data[deque->back++ & (deque->capacity - 1)];               \
 157 }                                                                           \
 158                                                                             \
 159 /* Expands DEQUE, doubling its capacity. */                                 \
 160 static inline void                                                          \
 161 NAME##_expand (struct NAME *deque)                                          \
 162 {                                                                           \
 163   struct NAME old_deque = *deque;                                           \
 164   NAME##_init (deque, deque->capacity * 2);                                 \
 165   while (!NAME##_is_empty (&old_deque))                                     \
 166     *NAME##_push_front (deque) = *NAME##_pop_back (&old_deque);             \
 167   free (old_deque.data);                                                    \
 168 }
 169
 170 #endif /* libpspp/deque.h */