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