1 /* Licensed under Apache License v2.0 - see LICENSE file for details */
5 #if !HAVE_STATEMENT_EXPR
6 #error "This code needs compiler support for statement expressions. Try using gcc or clang."
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
21 * @shrink: flag specifying shrink behavior
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.
28 enum deq_flag { DEQ_NO_SHRINK, DEQ_SHRINK_IF_EMPTY, DEQ_SHRINK_AT_20PCT };
32 unsigned head, tail, len, cap, min, esz, shrink;
36 * DEQ_WRAP - declare a wrapper type for struct deq and base type
37 * @basetype: the base type to wrap
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);
44 * // or init and malloc by function call
45 * struct vector3 { double x, y, z; };
46 * typedef DEQ_WRAP(struct vector3) vector3q_t;
49 * if (deq_init(&v, 16, DEQ_SHRINK_IF_EMPTY) == -1)
53 * // first malloc for pointq
54 * if (deq_push(&pointq, a) == -1)
57 #define DEQ_WRAP(basetype) \
63 #define DEQ_INIT_DEQ(esz, min, shrink) \
64 (struct deq) { 0, 0, 0, 0, 0, (min), (esz), (shrink) }
66 #define DEQ_INIT(esz, min, shrink) { .deq = DEQ_INIT_DEQ(esz, min, shrink) }
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
74 * Returns: 0 on success, -1 on error
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)); \
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
91 * if (deq_new(z, 16, DEQ_SHRINK_AT_20PCT) == -1)
96 * Returns: 0 on success, -1 on error
98 #define deq_new(w, min, shrink) ({ \
99 w = malloc(sizeof(*w)); \
100 if (w && deq_init(w, min, shrink) == -1) { \
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);
111 * deq_push - add element to end of deque
112 * @w: pointer to wrapper
115 * Returns: 1 on success, -1 on error
117 #define deq_push(w, e) ({ \
119 int __ret = deq_op_(&(w)->deq, DEQ_PUSH, &__i); \
126 * deq_unshift - add element to beginning of deque
127 * @w: pointer to wrapper
130 * Returns: 1 on success, -1 on error
132 #define deq_unshift(w, e) ({ \
134 int __ret = deq_op_(&(w)->deq, DEQ_UNSHIFT, &__i); \
141 * deq_pop - dequeue element from end of deque
142 * @w: pointer to wrapper
143 * @e: pointer to receive dequeued element
145 * Returns: 1 on success, 0 if deque is empty, -1 on error
148 * DEQ_WRAP(int) w = DEQ_INIT(sizeof(int), 8, DEQ_NO_SHRINK);
150 * // ... after enqueuing some ints
151 * while ((ret = deq_pop(&w, &i)) == 1)
156 #define deq_pop(w, e) ({ \
158 int __ret = deq_op_(&(w)->deq, DEQ_POP, &__i); \
160 *(e) = (w)->v[__i]; \
165 * deq_shift - dequeue element from beginning of deque
166 * @w: pointer to wrapper
167 * @e: pointer to receive dequeued element
169 * Returns: 1 on success, 0 if deque is empty, -1 on error
171 #define deq_shift(w, e) ({ \
173 int __ret = deq_op_(&(w)->deq, DEQ_SHIFT, &__i); \
175 *(e) = (w)->v[__i]; \
180 * deq_first - get element from beginning of deque, deque is unchanged
181 * @w: pointer to wrapper
182 * @e: pointer to receive element
184 * Returns: 1 on success, 0 if deque is empty
186 #define deq_first(w, e) ({ \
190 if ((w)->deq.len > 0) { \
191 *(e) = (w)->v[(w)->deq.head]; \
198 * deq_last - get element from end of deque, deque is unchanged
199 * @w: pointer to wrapper
200 * @e: pointer to receive element
202 * Returns: 1 on success, 0 if deque is empty
204 #define deq_last(w, 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]; \
218 * deq_reset - set struct deq indexes and counters to zero, and free malloced buffer
219 * @w: pointer to wrapper
223 void deq_reset_(struct deq *q);
224 #define deq_reset(w) do { \
226 deq_reset_(&(w)->deq); \
231 * deq_free - run deq_reset and free malloced wrapper
232 * @w: pointer to wrapper
236 #define deq_free(w) do { \
243 * deq_len - return deque length
244 * @w: pointer to wrapper
248 #define deq_len(w) ({ assert(w); (w)->deq.len; })
251 * deq_cap - return deque capacity
252 * @w: pointer to wrapper
256 #define deq_cap(w) ({ assert(w); (w)->deq.cap; })