ccan: make tal_dump() format more regular.
[ccan] / 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