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

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