git.ozlabs.org Git - ccan/blob - ccan/deque/deque.h

   1 /* Licensed under Apache License v2.0 - see LICENSE file for details */
   2 #ifndef CCAN_DEQUE_H
   3 #define CCAN_DEQUE_H
   4 #include "config.h"
   5 #if !HAVE_STATEMENT_EXPR
   6 #error "This code needs compiler support for statement expressions. Try using gcc or clang."
   7 #endif
   8 #include <assert.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11
  12 /**
  13  * struct deq - deque metadata
  14  * @v: char pointer to malloced memory
  15  * @head: index of first item in deque
  16  * @tail: index after last item in deque
  17  * @len: length of deque
  18  * @cap: total capacity of deque
  19  * @min: initial capacity of deque
  20  * @esz: element size
  21  * @shrink: flag specifying shrink behavior
  22  *
  23  * len is distance between head and tail. cap changes with resizing.
  24  * shrink must be one of DEQ_NO_SHRINK, DEQ_SHRINK_IF_EMPTY, or DEQ_SHRINK_AT_20PCT.
  25  * When shrinking, min is the smallest size.
  26  */
  27
  28 enum deq_flag { DEQ_NO_SHRINK, DEQ_SHRINK_IF_EMPTY, DEQ_SHRINK_AT_20PCT };
  29
  30 struct deq {
  31         char *v;
  32         unsigned head, tail, len, cap, min, esz, shrink;
  33 };
  34
  35 /**
  36  * DEQ_WRAP - declare a wrapper type for struct deq and base type
  37  * @basetype: the base type to wrap
  38  *
  39  * Example:
  40  *      // init inline, defer malloc to first push/unshift
  41  *      struct point { int x, y; } a;
  42  *      DEQ_WRAP(struct point) pointq = DEQ_INIT(sizeof(struct point), 64, DEQ_NO_SHRINK);
  43  *
  44  *      // or init and malloc by function call
  45  *      struct vector3 { double x, y, z; };
  46  *      typedef DEQ_WRAP(struct vector3) vector3q_t;
  47  *      vector3q_t v;
  48  *
  49  *      if (deq_init(&v, 16, DEQ_SHRINK_IF_EMPTY) == -1)
  50  *              err(1, "deq_init");
  51  *
  52  *      a.x = 1; a.y = 1;
  53  *      // first malloc for pointq
  54  *      if (deq_push(&pointq, a) == -1)
  55  *              err(1, "deq_push");
  56  */
  57 #define DEQ_WRAP(basetype)      \
  58         union {                 \
  59                 struct deq deq; \
  60                 basetype *v;    \
  61         }
  62
  63 #define DEQ_INIT_DEQ(esz, min, shrink) \
  64         (struct deq) { 0, 0, 0, 0, 0, (min), (esz), (shrink) }
  65
  66 #define DEQ_INIT(esz, min, shrink) { .deq = DEQ_INIT_DEQ(esz, min, shrink) }
  67
  68 /**
  69  * deq_init - initialize struct deq and malloc
  70  * @w: pointer to wrapper
  71  * @min: initial capacity of deque
  72  * @shrink: flag specifying shrink behavior
  73  *
  74  * Returns: 0 on success, -1 on error
  75  */
  76 int deq_resize_(struct deq *q, unsigned n);
  77 #define deq_init(w, min, shrink) ({                             \
  78         (w)->deq = DEQ_INIT_DEQ(sizeof(*(w)->v), min, shrink);  \
  79         deq_resize_(&(w)->deq, (min));                          \
  80 })
  81
  82 /**
  83  * deq_new - malloc wrapper and run deq_init
  84  * @w: pointer to wrapper
  85  * @min: initial capacity of deque
  86  * @shrink: flag specifying shrink behavior
  87  *
  88  * Example:
  89  *      vector3q_t *z;
  90  *
  91  *      if (deq_new(z, 16, DEQ_SHRINK_AT_20PCT) == -1)
  92  *              err(1, "deq_new");
  93  *      //later
  94  *      deq_free(z);
  95  *
  96  * Returns: 0 on success, -1 on error
  97  */
  98 #define deq_new(w, min, shrink) ({                      \
  99         w = malloc(sizeof(*w));                         \
 100         if (w && deq_init(w, min, shrink) == -1) {      \
 101                 free(w);                                \
 102                 w = 0;                                  \
 103         }                                               \
 104         w ? 0 : -1;                                     \
 105 })
 106
 107 enum deq_op { DEQ_PUSH, DEQ_POP, DEQ_SHIFT, DEQ_UNSHIFT };
 108 int deq_op_(struct deq *q, enum deq_op op, unsigned *i);
 109
 110 /**
 111  * deq_push - add element to end of deque
 112  * @w: pointer to wrapper
 113  * @e: element to add
 114  *
 115  * Returns: 1 on success, -1 on error
 116  */
 117 #define deq_push(w, e) ({                                       \
 118         unsigned __i;                                           \
 119         int __ret = deq_op_(&(w)->deq, DEQ_PUSH, &__i);         \
 120         if (__ret == 1)                                         \
 121                 (w)->v[__i] = (e);                              \
 122         __ret;                                                  \
 123 })
 124
 125 /**
 126  * deq_unshift - add element to beginning of deque
 127  * @w: pointer to wrapper
 128  * @e: element to add
 129  *
 130  * Returns: 1 on success, -1 on error
 131  */
 132 #define deq_unshift(w, e) ({                                    \
 133         unsigned __i;                                           \
 134         int __ret = deq_op_(&(w)->deq, DEQ_UNSHIFT, &__i);      \
 135         if (__ret == 1)                                         \
 136                 (w)->v[__i] = (e);                              \
 137         __ret;                                                  \
 138 })
 139
 140 /**
 141  * deq_pop - dequeue element from end of deque
 142  * @w: pointer to wrapper
 143  * @e: pointer to receive dequeued element
 144  *
 145  * Returns: 1 on success, 0 if deque is empty, -1 on error
 146  *
 147  * Example:
 148  *      DEQ_WRAP(int) w = DEQ_INIT(sizeof(int), 8, DEQ_NO_SHRINK);
 149  *      int ret, i;
 150  *      // ... after enqueuing some ints
 151  *      while ((ret = deq_pop(&w, &i)) == 1)
 152  *              printf("%d\n", i);
 153  *      if (ret == -1)
 154  *              err(1, "deq_pop");
 155  */
 156 #define deq_pop(w, e) ({                                        \
 157         unsigned __i;                                           \
 158         int __ret = deq_op_(&(w)->deq, DEQ_POP, &__i);          \
 159         if (__ret == 1)                                         \
 160                 *(e) = (w)->v[__i];                             \
 161         __ret;                                                  \
 162 })
 163
 164 /**
 165  * deq_shift - dequeue element from beginning of deque
 166  * @w: pointer to wrapper
 167  * @e: pointer to receive dequeued element
 168  *
 169  * Returns: 1 on success, 0 if deque is empty, -1 on error
 170  */
 171 #define deq_shift(w, e) ({                                      \
 172         unsigned __i;                                           \
 173         int __ret = deq_op_(&(w)->deq, DEQ_SHIFT, &__i);        \
 174         if (__ret == 1)                                         \
 175                 *(e) = (w)->v[__i];                             \
 176         __ret;                                                  \
 177 })
 178
 179 /**
 180  * deq_first - get element from beginning of deque, deque is unchanged
 181  * @w: pointer to wrapper
 182  * @e: pointer to receive element
 183  *
 184  * Returns: 1 on success, 0 if deque is empty
 185  */
 186 #define deq_first(w, e) ({                      \
 187         int __ret = 0;                          \
 188         assert(w);                              \
 189         assert(e);                              \
 190         if ((w)->deq.len > 0) {                 \
 191                 *(e) = (w)->v[(w)->deq.head];   \
 192                 __ret = 1;                      \
 193         }                                       \
 194         __ret;                                  \
 195 })
 196
 197 /**
 198  * deq_last - get element from end of deque, deque is unchanged
 199  * @w: pointer to wrapper
 200  * @e: pointer to receive element
 201  *
 202  * Returns: 1 on success, 0 if deque is empty
 203  */
 204 #define deq_last(w, e) ({                               \
 205         int __ret = 0;                                  \
 206         assert(w);                                      \
 207         assert(e);                                      \
 208         if ((w)->deq.len > 0) {                         \
 209                 unsigned __i = (w)->deq.tail == 0 ?     \
 210                         (w)->deq.cap : (w)->deq.tail;   \
 211                 *(e) = (w)->v[__i - 1];                 \
 212                 __ret = 1;                              \
 213         }                                               \
 214         __ret;                                          \
 215 })
 216
 217 /**
 218  * deq_reset - set struct deq indexes and counters to zero, and free malloced buffer
 219  * @w: pointer to wrapper
 220  *
 221  * Returns: void
 222  */
 223 void deq_reset_(struct deq *q);
 224 #define deq_reset(w) do {       \
 225         assert(w);              \
 226         deq_reset_(&(w)->deq);  \
 227         (w)->v = 0;             \
 228 } while (0)
 229
 230 /**
 231  * deq_free - run deq_reset and free malloced wrapper
 232  * @w: pointer to wrapper
 233  *
 234  * Returns: void
 235  */
 236 #define deq_free(w) do {        \
 237         deq_reset(w);           \
 238         free(w);                \
 239         w = 0;                  \
 240 } while (0)
 241
 242 /**
 243  * deq_len - return deque length
 244  * @w: pointer to wrapper
 245  *
 246  * Returns: int
 247  */
 248 #define deq_len(w) ({ assert(w); (w)->deq.len; })
 249
 250 /**
 251  * deq_cap - return deque capacity
 252  * @w: pointer to wrapper
 253  *
 254  * Returns: int
 255  */
 256 #define deq_cap(w) ({ assert(w); (w)->deq.cap; })
 257
 258 #endif