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) \
77 struct 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) \
86 struct { \
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 satisy scan-build.
224  */
225 #ifndef TAILQ_HEAD
226 
227 /*
228  * Tail queue declarations.
229  */
230 #define TAILQ_HEAD(name, type) \
231 struct 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) \
240 struct { \
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 */