1/*
2 * librd - Rapid Development C library
3 *
4 * Copyright (c) 2012-2013, Magnus Edenhill
5 * Copyright (c) 2012-2013, Andreas Öman
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright notice,
12 * this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright notice,
14 * this list of conditions and the following disclaimer in the documentation
15 * and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 */
29
30
31/*
32
33 *
34 * Redistribution and use in source and binary forms, with or without
35 * modification, are permitted provided that the following conditions
36 * are met:
37 * 1. Redistributions of source code must retain the above copyright
38 * notice, this list of conditions and the following disclaimer.
39 * 2. Redistributions in binary form must reproduce the above copyright
40 * notice, this list of conditions and the following disclaimer in the
41 * documentation and/or other materials provided with the distribution.
42 *
43 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
44 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
45 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
46 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
47 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
48 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
49 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
50 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
51 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
52 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
53 * POSSIBILITY OF SUCH DAMAGE.
54 */
55
56#ifndef _RDSYSQUEUE_H_
57#define _RDSYSQUEUE_H_
58
59#include "queue.h"
60
61/*
62 * Complete missing LIST-ops
63 */
64
65#ifndef LIST_FOREACH
66#define LIST_FOREACH(var, head, field) \
67 for ((var) = ((head)->lh_first); \
68 (var); \
69 (var) = ((var)->field.le_next))
70#endif
71
72#ifndef LIST_EMPTY
73#define LIST_EMPTY(head) ((head)->lh_first == NULL)
74#endif
75
76#ifndef LIST_FIRST
77#define LIST_FIRST(head) ((head)->lh_first)
78#endif
79
80#ifndef LIST_NEXT
81#define LIST_NEXT(elm, field) ((elm)->field.le_next)
82#endif
83
84#ifndef LIST_INSERT_BEFORE
85#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
86 (elm)->field.le_prev = (listelm)->field.le_prev; \
87 (elm)->field.le_next = (listelm); \
88 *(listelm)->field.le_prev = (elm); \
89 (listelm)->field.le_prev = &(elm)->field.le_next; \
90} while (/*CONSTCOND*/0)
91#endif
92
93/*
94 * Complete missing TAILQ-ops
95 */
96
97#ifndef TAILQ_HEAD_INITIALIZER
98#define TAILQ_HEAD_INITIALIZER(head) \
99 { NULL, &(head).tqh_first }
100#endif
101
102#ifndef TAILQ_INSERT_BEFORE
103#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
104 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
105 (elm)->field.tqe_next = (listelm); \
106 *(listelm)->field.tqe_prev = (elm); \
107 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
108} while (0)
109#endif
110
111#ifndef TAILQ_FOREACH
112#define TAILQ_FOREACH(var, head, field) \
113 for ((var) = ((head)->tqh_first); (var); (var) = ((var)->field.tqe_next))
114#endif
115
116#ifndef TAILQ_EMPTY
117#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
118#endif
119
120#ifndef TAILQ_FIRST
121#define TAILQ_FIRST(head) ((head)->tqh_first)
122#endif
123
124#ifndef TAILQ_NEXT
125#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
126#endif
127
128#ifndef TAILQ_LAST
129#define TAILQ_LAST(head, headname) \
130 (*(((struct headname *)((head)->tqh_last))->tqh_last))
131#endif
132
133#ifndef TAILQ_PREV
134#define TAILQ_PREV(elm, headname, field) \
135 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
136#endif
137
138#ifndef TAILQ_FOREACH_SAFE
139/*
140 * TAILQ_FOREACH_SAFE() provides a traversal where the current iterated element
141 * may be freed or unlinked.
142 * It does not allow freeing or modifying any other element in the list,
143 * at least not the next element.
144 */
145#define TAILQ_FOREACH_SAFE(elm,head,field,tmpelm) \
146 for ((elm) = TAILQ_FIRST(head) ; \
147 (elm) && ((tmpelm) = TAILQ_NEXT((elm), field), 1) ; \
148 (elm) = (tmpelm))
149#endif
150
151/*
152 * In Mac OS 10.4 and earlier TAILQ_FOREACH_REVERSE was defined
153 * differently, redefined it.
154 */
155#ifdef __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__
156#if __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ < 1050
157#undef TAILQ_FOREACH_REVERSE
158#endif
159#endif
160
161#ifndef TAILQ_FOREACH_REVERSE
162#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
163 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
164 (var); \
165 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
166#endif
167
168
169/**
170 * Treat the TAILQ as a circular list and return the previous/next entry,
171 * possibly wrapping to the end/beginning.
172 */
173#define TAILQ_CIRC_PREV(var, head, headname, field) \
174 ((var) != TAILQ_FIRST(head) ? \
175 TAILQ_PREV(var, headname, field) : \
176 TAILQ_LAST(head, headname))
177
178#define TAILQ_CIRC_NEXT(var, head, headname, field) \
179 ((var) != TAILQ_LAST(head, headname) ? \
180 TAILQ_NEXT(var, field) : \
181 TAILQ_FIRST(head))
182
183/*
184 * Some extra functions for LIST manipulation
185 */
186
187#define LIST_INSERT_SORTED(head, elm, elmtype, field, cmpfunc) do { \
188 if(LIST_EMPTY(head)) { \
189 LIST_INSERT_HEAD(head, elm, field); \
190 } else { \
191 elmtype _tmp; \
192 LIST_FOREACH(_tmp,head,field) { \
193 if(cmpfunc(elm,_tmp) < 0) { \
194 LIST_INSERT_BEFORE(_tmp,elm,field); \
195 break; \
196 } \
197 if(!LIST_NEXT(_tmp,field)) { \
198 LIST_INSERT_AFTER(_tmp,elm,field); \
199 break; \
200 } \
201 } \
202 } \
203} while(0)
204
205#ifndef TAILQ_INSERT_SORTED
206#define TAILQ_INSERT_SORTED(head, elm, elmtype, field, cmpfunc) do { \
207 if(TAILQ_FIRST(head) == NULL) { \
208 TAILQ_INSERT_HEAD(head, elm, field); \
209 } else { \
210 elmtype _tmp; \
211 TAILQ_FOREACH(_tmp,head,field) { \
212 if(cmpfunc(elm,_tmp) < 0) { \
213 TAILQ_INSERT_BEFORE(_tmp,elm,field); \
214 break; \
215 } \
216 if(!TAILQ_NEXT(_tmp,field)) { \
217 TAILQ_INSERT_AFTER(head,_tmp,elm,field); \
218 break; \
219 } \
220 } \
221 } \
222} while(0)
223#endif
224
225#define TAILQ_MOVE(newhead, oldhead, field) do { \
226 if(TAILQ_FIRST(oldhead)) { \
227 TAILQ_FIRST(oldhead)->field.tqe_prev = &(newhead)->tqh_first; \
228 (newhead)->tqh_first = (oldhead)->tqh_first; \
229 (newhead)->tqh_last = (oldhead)->tqh_last; \
230 TAILQ_INIT(oldhead); \
231 } else \
232 TAILQ_INIT(newhead); \
233 } while (/*CONSTCOND*/0)
234
235#ifndef TAILQ_CONCAT
236#define TAILQ_CONCAT(dhead, shead, field) do { \
237 if (!TAILQ_EMPTY(shead)) { \
238 *(dhead)->tqh_last = (shead)->tqh_first; \
239 (shead)->tqh_first->field.tqe_prev = \
240 (dhead)->tqh_last; \
241 (dhead)->tqh_last = (shead)->tqh_last; \
242 TAILQ_INIT((shead)); \
243 } \
244 } while (0)
245#endif
246
247/* @brief Insert \p shead after element \p listelm in \p dhead */
248#define TAILQ_INSERT_LIST(dhead,listelm,shead,headname,elmtype,field) do { \
249 if (TAILQ_LAST(dhead, headname) == listelm) { \
250 TAILQ_CONCAT(dhead, shead, field); \
251 } else { \
252 elmtype _elm = TAILQ_FIRST(shead); \
253 elmtype _last = TAILQ_LAST(shead, headname); \
254 elmtype _aft = TAILQ_NEXT(listelm, field); \
255 (listelm)->field.tqe_next = _elm; \
256 _elm->field.tqe_prev = &(listelm)->field.tqe_next; \
257 _last->field.tqe_next = _aft; \
258 _aft->field.tqe_prev = &_last->field.tqe_next; \
259 TAILQ_INIT((shead)); \
260 } \
261 } while (0)
262
263#ifndef SIMPLEQ_HEAD
264#define SIMPLEQ_HEAD(name, type) \
265struct name { \
266struct type *sqh_first; \
267struct type **sqh_last; \
268}
269#endif
270
271#ifndef SIMPLEQ_ENTRY
272#define SIMPLEQ_ENTRY(type) \
273struct { \
274struct type *sqe_next; \
275}
276#endif
277
278#ifndef SIMPLEQ_FIRST
279#define SIMPLEQ_FIRST(head) ((head)->sqh_first)
280#endif
281
282#ifndef SIMPLEQ_REMOVE_HEAD
283#define SIMPLEQ_REMOVE_HEAD(head, field) do { \
284if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
285(head)->sqh_last = &(head)->sqh_first; \
286} while (0)
287#endif
288
289#ifndef SIMPLEQ_INSERT_TAIL
290#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
291(elm)->field.sqe_next = NULL; \
292*(head)->sqh_last = (elm); \
293(head)->sqh_last = &(elm)->field.sqe_next; \
294} while (0)
295#endif
296
297#ifndef SIMPLEQ_INIT
298#define SIMPLEQ_INIT(head) do { \
299(head)->sqh_first = NULL; \
300(head)->sqh_last = &(head)->sqh_first; \
301} while (0)
302#endif
303
304#ifndef SIMPLEQ_INSERT_HEAD
305#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
306if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
307(head)->sqh_last = &(elm)->field.sqe_next; \
308(head)->sqh_first = (elm); \
309} while (0)
310#endif
311
312#ifndef SIMPLEQ_FOREACH
313#define SIMPLEQ_FOREACH(var, head, field) \
314for((var) = SIMPLEQ_FIRST(head); \
315(var) != SIMPLEQ_END(head); \
316(var) = SIMPLEQ_NEXT(var, field))
317#endif
318
319#ifndef SIMPLEQ_INSERT_AFTER
320#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
321if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \
322(head)->sqh_last = &(elm)->field.sqe_next; \
323(listelm)->field.sqe_next = (elm); \
324} while (0)
325#endif
326
327#ifndef SIMPLEQ_END
328#define SIMPLEQ_END(head) NULL
329#endif
330
331#ifndef SIMPLEQ_NEXT
332#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
333#endif
334
335#ifndef SIMPLEQ_HEAD_INITIALIZER
336#define SIMPLEQ_HEAD_INITIALIZER(head) \
337{ NULL, &(head).sqh_first }
338#endif
339
340#ifndef SIMPLEQ_EMPTY
341#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
342#endif
343
344
345
346
347
348#endif /* _RDSYSQUEUE_H_ */
349