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