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 #include "autoconf.h"
53 
54 #if defined(HAVE_SYS_QUEUE_H) && !defined(__clang_analyzer__)
55 #include <sys/queue.h>
56 #endif
57 
58 #if defined(__clang_analyzer__)
59 #define _Q_ASSERT(a) assert((a))
60 #else
61 #define _Q_ASSERT(a)
62 #endif
63 
64 /* The BSDs have removed CIRCLEQ but it still exists in Linux.
65  *
66  * This implementation from OpenBSD sys/queue.h v1.40 as it still has
67  * CIRCLEQ and includes the safe variations.
68  * - _Q_INVALIDATE for some extra debugging has been removed as its
69  * not available on the Linux version of CIRCLEQ.
70  */
71 
72 #ifndef CIRCLEQ_HEAD
73 
74 /*
75  * Circular queue definitions.
76  */
77 #define CIRCLEQ_HEAD(name, type) \
78 struct name { \
79  struct type *cqh_first; /* first element */ \
80  struct type *cqh_last; /* last element */ \
81 }
82 
83 #define CIRCLEQ_HEAD_INITIALIZER(head) \
84  { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
85 
86 #define CIRCLEQ_ENTRY(type) \
87 struct { \
88  struct type *cqe_next; /* next element */ \
89  struct type *cqe_prev; /* previous element */ \
90 }
91 
92 /*
93  * Circular queue access methods
94  */
95 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
96 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
97 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
98 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
99 #define CIRCLEQ_EMPTY(head) \
100  (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
101 
102 #define CIRCLEQ_FOREACH(var, head, field) \
103  for((var) = CIRCLEQ_FIRST(head); \
104  (var) != CIRCLEQ_END(head); \
105  (var) = CIRCLEQ_NEXT(var, field))
106 
107 #define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \
108  for ((var) = CIRCLEQ_FIRST(head); \
109  (var) != CIRCLEQ_END(head) && \
110  ((tvar) = CIRCLEQ_NEXT(var, field), 1); \
111  (var) = (tvar))
112 
113 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
114  for((var) = CIRCLEQ_LAST(head); \
115  (var) != CIRCLEQ_END(head); \
116  (var) = CIRCLEQ_PREV(var, field))
117 
118 #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
119  for ((var) = CIRCLEQ_LAST(head, headname); \
120  (var) != CIRCLEQ_END(head) && \
121  ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \
122  (var) = (tvar))
123 
124 /*
125  * Circular queue functions.
126  */
127 #define CIRCLEQ_INIT(head) do { \
128  (head)->cqh_first = CIRCLEQ_END(head); \
129  (head)->cqh_last = CIRCLEQ_END(head); \
130 } while (0)
131 
132 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
133  (elm)->field.cqe_next = (listelm)->field.cqe_next; \
134  (elm)->field.cqe_prev = (listelm); \
135  if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
136  (head)->cqh_last = (elm); \
137  else \
138  (listelm)->field.cqe_next->field.cqe_prev = (elm); \
139  (listelm)->field.cqe_next = (elm); \
140 } while (0)
141 
142 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
143  (elm)->field.cqe_next = (listelm); \
144  (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
145  if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
146  (head)->cqh_first = (elm); \
147  else \
148  (listelm)->field.cqe_prev->field.cqe_next = (elm); \
149  (listelm)->field.cqe_prev = (elm); \
150 } while (0)
151 
152 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
153  (elm)->field.cqe_next = (head)->cqh_first; \
154  (elm)->field.cqe_prev = CIRCLEQ_END(head); \
155  if ((head)->cqh_last == CIRCLEQ_END(head)) \
156  (head)->cqh_last = (elm); \
157  else \
158  (head)->cqh_first->field.cqe_prev = (elm); \
159  (head)->cqh_first = (elm); \
160 } while (0)
161 
162 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
163  (elm)->field.cqe_next = CIRCLEQ_END(head); \
164  (elm)->field.cqe_prev = (head)->cqh_last; \
165  if ((head)->cqh_first == CIRCLEQ_END(head)) \
166  (head)->cqh_first = (elm); \
167  else \
168  (head)->cqh_last->field.cqe_next = (elm); \
169  (head)->cqh_last = (elm); \
170 } while (0)
171 
172 #define CIRCLEQ_REMOVE(head, elm, field) do { \
173  if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
174  (head)->cqh_last = (elm)->field.cqe_prev; \
175  else \
176  (elm)->field.cqe_next->field.cqe_prev = \
177  (elm)->field.cqe_prev; \
178  if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
179  (head)->cqh_first = (elm)->field.cqe_next; \
180  else \
181  (elm)->field.cqe_prev->field.cqe_next = \
182  (elm)->field.cqe_next; \
183 } while (0)
184 
185 #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
186  if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
187  CIRCLEQ_END(head)) \
188  (head)->cqh_last = (elm2); \
189  else \
190  (elm2)->field.cqe_next->field.cqe_prev = (elm2); \
191  if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
192  CIRCLEQ_END(head)) \
193  (head)->cqh_first = (elm2); \
194  else \
195  (elm2)->field.cqe_prev->field.cqe_next = (elm2); \
196 } while (0)
197 
198 #endif /* !CIRCLEQ_HEAD */
199 
200 /* Required by local implementation as well as _SAFE variations. */
201 #ifndef CIRCLEQ_END
202 #define CIRCLEQ_END(head) ((void *)(head))
203 #endif /* !CIRCLEQ_END */
204 
205 #ifndef CIRCLEQ_FOREACH_SAFE
206 #define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \
207  for ((var) = CIRCLEQ_FIRST(head); \
208  (var) != CIRCLEQ_END(head) && \
209  ((tvar) = CIRCLEQ_NEXT(var, field), 1); \
210  (var) = (tvar))
211 
212 #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
213  for ((var) = CIRCLEQ_LAST(head, headname); \
214  (var) != CIRCLEQ_END(head) && \
215  ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \
216  (var) = (tvar))
217 #endif /* !CIRCLEQ_FOREACH_SAFE */
218 
219 /*
220  * Complete TAILQ implementation as sys/queue.h is not available on Windows
221  * and used by Suricata.
222  *
223  * This implementation copied from FreeBSD sys/queue.h with the addition
224  * of our _Q_ASSERT macros to satisy scan-build.
225  */
226 #ifndef TAILQ_HEAD
227 
228 /*
229  * Tail queue declarations.
230  */
231 #define TAILQ_HEAD(name, type) \
232 struct name { \
233  struct type *tqh_first; /* first element */ \
234  struct type **tqh_last; /* addr of last next element */ \
235 }
236 
237 #define TAILQ_HEAD_INITIALIZER(head) \
238  { NULL, &(head).tqh_first }
239 
240 #define TAILQ_ENTRY(type) \
241 struct { \
242  struct type *tqe_next; /* next element */ \
243  struct type **tqe_prev; /* address of previous next element */ \
244 }
245 
246 /*
247  * Tail queue functions.
248  */
249 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
250 
251 #define TAILQ_FIRST(head) ((head)->tqh_first)
252 
253 #define TAILQ_FOREACH(var, head, field) \
254  for ((var) = TAILQ_FIRST((head)); \
255  (var); \
256  (var) = TAILQ_NEXT((var), field))
257 
258 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
259  for ((var) = TAILQ_LAST((head), headname); \
260  (var); \
261  (var) = TAILQ_PREV((var), headname, field))
262 
263 #define TAILQ_INIT(head) do { \
264  TAILQ_FIRST((head)) = NULL; \
265  (head)->tqh_last = &TAILQ_FIRST((head)); \
266 } while (0)
267 
268 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
269  if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
270  TAILQ_NEXT((elm), field)->field.tqe_prev = \
271  &TAILQ_NEXT((elm), field); \
272  else \
273  (head)->tqh_last = &TAILQ_NEXT((elm), field); \
274  TAILQ_NEXT((listelm), field) = (elm); \
275  (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
276 } while (0)
277 
278 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
279  (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
280  TAILQ_NEXT((elm), field) = (listelm); \
281  *(listelm)->field.tqe_prev = (elm); \
282  (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
283 } while (0)
284 
285 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
286  if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
287  TAILQ_FIRST((head))->field.tqe_prev = \
288  &TAILQ_NEXT((elm), field); \
289  else \
290  (head)->tqh_last = &TAILQ_NEXT((elm), field); \
291  TAILQ_FIRST((head)) = (elm); \
292  (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
293 } while (0)
294 
295 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
296  _Q_ASSERT((elm)); \
297  _Q_ASSERT((head)); \
298  TAILQ_NEXT((elm), field) = NULL; \
299  (elm)->field.tqe_prev = (head)->tqh_last; \
300  *(head)->tqh_last = (elm); \
301  _Q_ASSERT(*(head)->tqh_last); \
302  (head)->tqh_last = &TAILQ_NEXT((elm), field); \
303 } while (0)
304 
305 #define TAILQ_LAST(head, headname) \
306  (*(((struct headname *)((head)->tqh_last))->tqh_last))
307 
308 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
309 
310 #define TAILQ_PREV(elm, headname, field) \
311  (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
312 
313 #define TAILQ_REMOVE(head, elm, field) do { \
314  if ((TAILQ_NEXT((elm), field)) != NULL) \
315  TAILQ_NEXT((elm), field)->field.tqe_prev = \
316  (elm)->field.tqe_prev; \
317  else \
318  (head)->tqh_last = (elm)->field.tqe_prev; \
319  _Q_ASSERT((head)->tqh_first != (elm)); \
320  *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
321 } while (0)
322 
323 #endif /* !TAILQ_HEAD */
324 
325 /* Not included in Linux, but are in FreeBSD and friends.
326  *
327  * This implementation from FreeBSD's sys/queue.h.
328  */
329 #ifndef TAILQ_FOREACH_SAFE
330 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
331  for ((var) = TAILQ_FIRST((head)); \
332  (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
333  (var) = (tvar))
334 #endif
335 
336 #endif /* !SURICATA_QUEUE_H */