deque: New module
[ccan] / 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