src/libpspp/deque.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2011 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU 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, see <http://www.gnu.org/licenses/>. */
  16
  17 /* Deque data structure.
  18
  19    This code slightly simplifies the implementation of a deque as a circular
  20    queue.  To use it, declare a "struct deque" and a pointer to the element
  21    type.  For example, for deque of "int"s with an initial capacity of 0:
  22
  23         struct deque deque = DEQUE_EMPTY_INITIALIZER;
  24         int *data = NULL;
  25
  26    Alternatively, to initialize the deque with an initial minimum
  27    capacity of, e.g., 4:
  28
  29         struct deque deque;
  30         int *data = deque_init (&deque, 4, sizeof *data);
  31
  32    Functions that access elements in the deque return array
  33    indexes.  This is fairly convenient:
  34
  35         // Push X at the back of the deque.
  36         data[deque_push_back (&deque)] = x;
  37
  38         // Pop off the front of the deque into X.
  39         x = data[deque_pop_front (&deque)];
  40
  41         // Obtain the element just past the back of the deque as X.
  42         x = data[deque_back (&deque, 1)];
  43
  44    The push functions will not expand the deque on their own.
  45    Use the deque_expand function if necessary, as in:
  46
  47         // Push X at the back of the deque, first expanding the
  48         // deque if necessary.
  49         if (deque_is_full (&deque))
  50           data = deque_expand (&deque, data, sizeof *data);
  51         data[deque_push_back (&deque)] = x;
  52
  53    Expanding a deque will copy its elements from one memory
  54    region to another using memcpy.  Thus, your deque elements
  55    must tolerate copying if their deque is to be expanded. */
  56
  57 #ifndef LIBPSPP_DEQUE_H
  58 #define LIBPSPP_DEQUE_H 1
  59
  60 #include <stdbool.h>
  61 #include <stddef.h>
  62 #include <stdlib.h>
  63
  64 #include "libpspp/assertion.h"
  65
  66 /* A deque implemented as a circular buffer. */
  67 struct deque
  68   {
  69     size_t capacity;    /* Capacity, which must be a power of 2. */
  70     size_t front;       /* One past the front of the queue. */
  71     size_t back;        /* The back of the queue. */
  72   };
  73 #define DEQUE_EMPTY_INITIALIZER { .capacity = 0 }
  74
  75 void *deque_init (struct deque *, size_t capacity, size_t elem_size);
  76 void *deque_expand (struct deque *, void *, size_t elem_size);
  77
  78 /* Returns the number of elements currently in DEQUE. */
  79 static inline size_t
  80 deque_count (const struct deque *deque)
  81 {
  82   return deque->front - deque->back;
  83 }
  84
  85 /* Returns the maximum number of elements that DEQUE can hold at
  86    any time.  (Use deque_expand to increase a deque's
  87    capacity.) */
  88 static inline size_t
  89 deque_capacity (const struct deque *deque)
  90 {
  91   return deque->capacity;
  92 }
  93
  94 /* Returns true if DEQUE is currently empty (contains no
  95    elements), false otherwise. */
  96 static inline bool
  97 deque_is_empty (const struct deque *deque)
  98 {
  99   return deque_count (deque) == 0;
 100 }
 101
 102 /* Returns true if DEQUE is currently full (cannot take any more
 103    elements), false otherwise. */
 104 static inline bool
 105 deque_is_full (const struct deque *deque)
 106 {
 107   return deque_count (deque) >= deque_capacity (deque);
 108 }
 109
 110 /* Returns the index of the element in DEQUE that is OFFSET
 111    elements from its front.  A value 0 for OFFSET requests the
 112    element at the front, a value of 1 the element just behind the
 113    front, and so on.  OFFSET must be less than the current number
 114    of elements in DEQUE. */
 115 static inline size_t
 116 deque_front (const struct deque *deque, size_t offset)
 117 {
 118   assert (deque_count (deque) > offset);
 119   return (deque->front - offset - 1) & (deque->capacity - 1);
 120 }
 121
 122 /* Returns the index of the element in DEQUE that is OFFSET
 123    elements from its back.  A value 0 for OFFSET requests the
 124    element at the back, a value of 1 the element just ahead of
 125    the back, and so on.  OFFSET must be less than the current
 126    number of elements in DEQUE. */
 127 static inline size_t
 128 deque_back (const struct deque *deque, size_t offset)
 129 {
 130   assert (deque_count (deque) > offset);
 131   return (deque->back + offset) & (deque->capacity - 1);
 132 }
 133
 134 /* Adds a new element at the front of DEQUE, which must not be
 135    full, and returns the index of the new element.  The caller is
 136    responsible for assigning a value to the returned element. */
 137 static inline size_t
 138 deque_push_front (struct deque *deque)
 139 {
 140   assert (!deque_is_full (deque));
 141   return deque->front++ & (deque->capacity - 1);
 142 }
 143
 144 /* Adds a new element at the back of DEQUE, which must not be
 145    full, and returns the index of the new element.  The caller is
 146    responsible for assigning a value to the returned element. */
 147 static inline size_t
 148 deque_push_back (struct deque *deque)
 149 {
 150   assert (!deque_is_full (deque));
 151   return --deque->back & (deque->capacity - 1);
 152 }
 153
 154 /* Pops the front element off DEQUE (which must not be empty) and
 155    returns its index.  The element may be reused the next time an
 156    element is pushed into DEQUE or when DEQUE is expanded. */
 157 static inline size_t
 158 deque_pop_front (struct deque *deque)
 159 {
 160   assert (!deque_is_empty (deque));
 161   return --deque->front & (deque->capacity - 1);
 162 }
 163
 164 /* Pops the back element off DEQUE (which must not be empty) and
 165    returns its index.  The element may be reused the next time
 166    an element is pushed into DEQUE or when DEQUE is expanded. */
 167 static inline size_t
 168 deque_pop_back (struct deque *deque)
 169 {
 170   assert (!deque_is_empty (deque));
 171   return deque->back++ & (deque->capacity - 1);
 172 }
 173
 174 #endif /* libpspp/deque.h */