suricata
queue.h
Go to the documentation of this file.
1/* $OpenBSD: queue.h,v 1.32 2007/04/30 18:42:34 pedro Exp $ */
2/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
3
4/*
5 * Copyright (c) 1991, 1993
6 * The Regents of the University of California. 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
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * @(#)queue.h 8.5 (Berkeley) 8/20/94
33 */
34
35// Disable clang-formatting as these implementations are copied from other
36// sources.
37//
38// clang-format off
39
40#ifndef SURICATA_QUEUE_H
41#define SURICATA_QUEUE_H
42
43/**
44 * This file started as a copy of sys/queue.h from OpenBSD and then had
45 * various changes made over time. Now we include the system sys/queue.h
46 * and then add missing behavior. On Windows this means we basically add
47 * everything. This allows for Suricata builds that integrate with other
48 * libraries that make use of sys/queue.h to use the exact same definitions
49 * from queue.h instead the Suricata copy.
50 */
51
52
53#if defined(HAVE_SYS_QUEUE_H) && !defined(__clang_analyzer__)
54#include <sys/queue.h>
55#endif
56
57#if defined(__clang_analyzer__)
58#define _Q_ASSERT(a) assert((a))
59#else
60#define _Q_ASSERT(a)
61#endif
62
63/* The BSDs have removed CIRCLEQ but it still exists in Linux.
64 *
65 * This implementation from OpenBSD sys/queue.h v1.40 as it still has
66 * CIRCLEQ and includes the safe variations.
67 * - _Q_INVALIDATE for some extra debugging has been removed as its
68 * not available on the Linux version of CIRCLEQ.
69 */
70
71#ifndef CIRCLEQ_HEAD
72
73/*
74 * Circular queue definitions.
75 */
76#define CIRCLEQ_HEAD(name, type) \
77struct name { \
78 struct type *cqh_first; /* first element */ \
79 struct type *cqh_last; /* last element */ \
80}
81
82#define CIRCLEQ_HEAD_INITIALIZER(head) \
83 { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
84
85#define CIRCLEQ_ENTRY(type) \
86struct { \
87 struct type *cqe_next; /* next element */ \
88 struct type *cqe_prev; /* previous element */ \
89}
90
91/*
92 * Circular queue access methods
93 */
94#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
95#define CIRCLEQ_LAST(head) ((head)->cqh_last)
96#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
97#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
98#define CIRCLEQ_EMPTY(head) \
99 (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
100
101#define CIRCLEQ_FOREACH(var, head, field) \
102 for((var) = CIRCLEQ_FIRST(head); \
103 (var) != CIRCLEQ_END(head); \
104 (var) = CIRCLEQ_NEXT(var, field))
105
106#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \
107 for ((var) = CIRCLEQ_FIRST(head); \
108 (var) != CIRCLEQ_END(head) && \
109 ((tvar) = CIRCLEQ_NEXT(var, field), 1); \
110 (var) = (tvar))
111
112#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
113 for((var) = CIRCLEQ_LAST(head); \
114 (var) != CIRCLEQ_END(head); \
115 (var) = CIRCLEQ_PREV(var, field))
116
117#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
118 for ((var) = CIRCLEQ_LAST(head, headname); \
119 (var) != CIRCLEQ_END(head) && \
120 ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \
121 (var) = (tvar))
122
123/*
124 * Circular queue functions.
125 */
126#define CIRCLEQ_INIT(head) do { \
127 (head)->cqh_first = CIRCLEQ_END(head); \
128 (head)->cqh_last = CIRCLEQ_END(head); \
129} while (0)
130
131#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
132 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
133 (elm)->field.cqe_prev = (listelm); \
134 if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
135 (head)->cqh_last = (elm); \
136 else \
137 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
138 (listelm)->field.cqe_next = (elm); \
139} while (0)
140
141#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
142 (elm)->field.cqe_next = (listelm); \
143 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
144 if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
145 (head)->cqh_first = (elm); \
146 else \
147 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
148 (listelm)->field.cqe_prev = (elm); \
149} while (0)
150
151#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
152 (elm)->field.cqe_next = (head)->cqh_first; \
153 (elm)->field.cqe_prev = CIRCLEQ_END(head); \
154 if ((head)->cqh_last == CIRCLEQ_END(head)) \
155 (head)->cqh_last = (elm); \
156 else \
157 (head)->cqh_first->field.cqe_prev = (elm); \
158 (head)->cqh_first = (elm); \
159} while (0)
160
161#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
162 (elm)->field.cqe_next = CIRCLEQ_END(head); \
163 (elm)->field.cqe_prev = (head)->cqh_last; \
164 if ((head)->cqh_first == CIRCLEQ_END(head)) \
165 (head)->cqh_first = (elm); \
166 else \
167 (head)->cqh_last->field.cqe_next = (elm); \
168 (head)->cqh_last = (elm); \
169} while (0)
170
171#define CIRCLEQ_REMOVE(head, elm, field) do { \
172 if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
173 (head)->cqh_last = (elm)->field.cqe_prev; \
174 else \
175 (elm)->field.cqe_next->field.cqe_prev = \
176 (elm)->field.cqe_prev; \
177 if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
178 (head)->cqh_first = (elm)->field.cqe_next; \
179 else \
180 (elm)->field.cqe_prev->field.cqe_next = \
181 (elm)->field.cqe_next; \
182} while (0)
183
184#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
185 if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
186 CIRCLEQ_END(head)) \
187 (head)->cqh_last = (elm2); \
188 else \
189 (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
190 if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
191 CIRCLEQ_END(head)) \
192 (head)->cqh_first = (elm2); \
193 else \
194 (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
195} while (0)
196
197#endif /* !CIRCLEQ_HEAD */
198
199/* Required by local implementation as well as _SAFE variations. */
200#ifndef CIRCLEQ_END
201#define CIRCLEQ_END(head) ((void *)(head))
202#endif /* !CIRCLEQ_END */
203
204#ifndef CIRCLEQ_FOREACH_SAFE
205#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \
206 for ((var) = CIRCLEQ_FIRST(head); \
207 (var) != CIRCLEQ_END(head) && \
208 ((tvar) = CIRCLEQ_NEXT(var, field), 1); \
209 (var) = (tvar))
210
211#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
212 for ((var) = CIRCLEQ_LAST(head, headname); \
213 (var) != CIRCLEQ_END(head) && \
214 ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \
215 (var) = (tvar))
216#endif /* !CIRCLEQ_FOREACH_SAFE */
217
218/*
219 * Complete TAILQ implementation as sys/queue.h is not available on Windows
220 * and used by Suricata.
221 *
222 * This implementation copied from FreeBSD sys/queue.h with the addition
223 * of our _Q_ASSERT macros to satisfy scan-build.
224 */
225#ifndef TAILQ_HEAD
226
227/*
228 * Tail queue declarations.
229 */
230#define TAILQ_HEAD(name, type) \
231struct name { \
232 struct type *tqh_first; /* first element */ \
233 struct type **tqh_last; /* addr of last next element */ \
234}
235
236#define TAILQ_HEAD_INITIALIZER(head) \
237 { NULL, &(head).tqh_first }
238
239#define TAILQ_ENTRY(type) \
240struct { \
241 struct type *tqe_next; /* next element */ \
242 struct type **tqe_prev; /* address of previous next element */ \
243}
244
245/*
246 * Tail queue functions.
247 */
248#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
249
250#define TAILQ_FIRST(head) ((head)->tqh_first)
251
252#define TAILQ_FOREACH(var, head, field) \
253 for ((var) = TAILQ_FIRST((head)); \
254 (var); \
255 (var) = TAILQ_NEXT((var), field))
256
257#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
258 for ((var) = TAILQ_LAST((head), headname); \
259 (var); \
260 (var) = TAILQ_PREV((var), headname, field))
261
262#define TAILQ_INIT(head) do { \
263 TAILQ_FIRST((head)) = NULL; \
264 (head)->tqh_last = &TAILQ_FIRST((head)); \
265} while (0)
266
267#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
268 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
269 TAILQ_NEXT((elm), field)->field.tqe_prev = \
270 &TAILQ_NEXT((elm), field); \
271 else \
272 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
273 TAILQ_NEXT((listelm), field) = (elm); \
274 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
275} while (0)
276
277#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
278 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
279 TAILQ_NEXT((elm), field) = (listelm); \
280 *(listelm)->field.tqe_prev = (elm); \
281 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
282} while (0)
283
284#define TAILQ_INSERT_HEAD(head, elm, field) do { \
285 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
286 TAILQ_FIRST((head))->field.tqe_prev = \
287 &TAILQ_NEXT((elm), field); \
288 else \
289 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
290 TAILQ_FIRST((head)) = (elm); \
291 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
292} while (0)
293
294#define TAILQ_INSERT_TAIL(head, elm, field) do { \
295 _Q_ASSERT((elm)); \
296 _Q_ASSERT((head)); \
297 TAILQ_NEXT((elm), field) = NULL; \
298 (elm)->field.tqe_prev = (head)->tqh_last; \
299 *(head)->tqh_last = (elm); \
300 _Q_ASSERT(*(head)->tqh_last); \
301 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
302} while (0)
303
304#define TAILQ_LAST(head, headname) \
305 (*(((struct headname *)((head)->tqh_last))->tqh_last))
306
307#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
308
309#define TAILQ_PREV(elm, headname, field) \
310 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
311
312#define TAILQ_REMOVE(head, elm, field) do { \
313 if ((TAILQ_NEXT((elm), field)) != NULL) \
314 TAILQ_NEXT((elm), field)->field.tqe_prev = \
315 (elm)->field.tqe_prev; \
316 else \
317 (head)->tqh_last = (elm)->field.tqe_prev; \
318 _Q_ASSERT((head)->tqh_first != (elm)); \
319 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
320} while (0)
321
322#endif /* !TAILQ_HEAD */
323
324/* Not included in Linux, but are in FreeBSD and friends.
325 *
326 * This implementation from FreeBSD's sys/queue.h.
327 */
328#ifndef TAILQ_FOREACH_SAFE
329#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
330 for ((var) = TAILQ_FIRST((head)); \
331 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
332 (var) = (tvar))
333#endif
334
335#endif /* !SURICATA_QUEUE_H */