1 /* $NetBSD: queue.h,v 1.68 2014/11/19 08:10:01 uebayasi Exp $ */
2
3 /*
4 * Copyright (c) 1991, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 * @(#)queue.h 8.5 (Berkeley) 8/20/94
32 */
33
34 #ifndef _SYS_QUEUE_H_
35 #define _SYS_QUEUE_H_
36
37 /*
38 * This file defines five types of data structures: singly-linked lists,
39 * lists, simple queues, tail queues, and circular queues.
40 *
41 * A singly-linked list is headed by a single forward pointer. The
42 * elements are singly linked for minimum space and pointer manipulation
43 * overhead at the expense of O(n) removal for arbitrary elements. New
44 * elements can be added to the list after an existing element or at the
45 * head of the list. Elements being removed from the head of the list
46 * should use the explicit macro for this purpose for optimum
47 * efficiency. A singly-linked list may only be traversed in the forward
48 * direction. Singly-linked lists are ideal for applications with large
49 * datasets and few or no removals or for implementing a LIFO queue.
50 *
51 * A list is headed by a single forward pointer (or an array of forward
52 * pointers for a hash table header). The elements are doubly linked
53 * so that an arbitrary element can be removed without a need to
54 * traverse the list. New elements can be added to the list before
55 * or after an existing element or at the head of the list. A list
56 * may only be traversed in the forward direction.
57 *
58 * A simple queue is headed by a pair of pointers, one the head of the
59 * list and the other to the tail of the list. The elements are singly
60 * linked to save space, so elements can only be removed from the
61 * head of the list. New elements can be added to the list after
62 * an existing element, at the head of the list, or at the end of the
63 * list. A simple queue may only be traversed in the forward direction.
64 *
65 * A tail queue is headed by a pair of pointers, one to the head of the
66 * list and the other to the tail of the list. The elements are doubly
67 * linked so that an arbitrary element can be removed without a need to
68 * traverse the list. New elements can be added to the list before or
69 * after an existing element, at the head of the list, or at the end of
70 * the list. A tail queue may be traversed in either direction.
71 *
72 * A circle queue is headed by a pair of pointers, one to the head of the
73 * list and the other to the tail of the list. The elements are doubly
74 * linked so that an arbitrary element can be removed without a need to
75 * traverse the list. New elements can be added to the list before or after
76 * an existing element, at the head of the list, or at the end of the list.
77 * A circle queue may be traversed in either direction, but has a more
78 * complex end of list detection.
79 *
80 * For details on the use of these macros, see the queue(3) manual page.
81 */
82
83 /*
84 * Include the definition of NULL only on NetBSD because sys/null.h
85 * is not available elsewhere. This conditional makes the header
86 * portable and it can simply be dropped verbatim into any system.
87 * The caveat is that on other systems some other header
88 * must provide NULL before the macros can be used.
89 */
90 #ifdef __NetBSD__
91 #include <sys/null.h>
92 #endif
93
94 #if defined(QUEUEDEBUG)
95 # if defined(_KERNEL)
96 # define QUEUEDEBUG_ABORT(...) panic(__VA_ARGS__)
97 # else
98 # include <err.h>
99 # define QUEUEDEBUG_ABORT(...) err(1, __VA_ARGS__)
100 # endif
101 #endif
102
103 /*
104 * Singly-linked List definitions.
105 */
106 #define SLIST_HEAD(name, type) \
107 struct name { \
108 struct type *slh_first; /* first element */ \
109 }
110
111 #define SLIST_HEAD_INITIALIZER(head) \
112 { NULL }
113
114 #define SLIST_ENTRY(type) \
115 struct { \
116 struct type *sle_next; /* next element */ \
117 }
118
119 /*
120 * Singly-linked List access methods.
121 */
122 #define SLIST_FIRST(head) ((head)->slh_first)
123 #define SLIST_END(head) NULL
124 #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
125 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
126
127 #define SLIST_FOREACH(var, head, field) \
128 for((var) = (head)->slh_first; \
129 (var) != SLIST_END(head); \
130 (var) = (var)->field.sle_next)
131
132 #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
133 for ((var) = SLIST_FIRST((head)); \
134 (var) != SLIST_END(head) && \
135 ((tvar) = SLIST_NEXT((var), field), 1); \
136 (var) = (tvar))
137
138 /*
139 * Singly-linked List functions.
140 */
141 #define SLIST_INIT(head) do { \
142 (head)->slh_first = SLIST_END(head); \
143 } while (/*CONSTCOND*/0)
144
145 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
146 (elm)->field.sle_next = (slistelm)->field.sle_next; \
147 (slistelm)->field.sle_next = (elm); \
148 } while (/*CONSTCOND*/0)
149
150 #define SLIST_INSERT_HEAD(head, elm, field) do { \
151 (elm)->field.sle_next = (head)->slh_first; \
152 (head)->slh_first = (elm); \
153 } while (/*CONSTCOND*/0)
154
155 #define SLIST_REMOVE_AFTER(slistelm, field) do { \
156 (slistelm)->field.sle_next = \
157 SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \
158 } while (/*CONSTCOND*/0)
159
160 #define SLIST_REMOVE_HEAD(head, field) do { \
161 (head)->slh_first = (head)->slh_first->field.sle_next; \
162 } while (/*CONSTCOND*/0)
163
164 #define SLIST_REMOVE(head, elm, type, field) do { \
165 if ((head)->slh_first == (elm)) { \
166 SLIST_REMOVE_HEAD((head), field); \
167 } \
168 else { \
169 struct type *curelm = (head)->slh_first; \
170 while(curelm->field.sle_next != (elm)) \
171 curelm = curelm->field.sle_next; \
172 curelm->field.sle_next = \
173 curelm->field.sle_next->field.sle_next; \
174 } \
175 } while (/*CONSTCOND*/0)
176
177
178 /*
179 * List definitions.
180 */
181 #define LIST_HEAD(name, type) \
182 struct name { \
183 struct type *lh_first; /* first element */ \
184 }
185
186 #define LIST_HEAD_INITIALIZER(head) \
187 { NULL }
188
189 #define LIST_ENTRY(type) \
190 struct { \
191 struct type *le_next; /* next element */ \
192 struct type **le_prev; /* address of previous next element */ \
193 }
194
195 /*
196 * List access methods.
197 */
198 #define LIST_FIRST(head) ((head)->lh_first)
199 #define LIST_END(head) NULL
200 #define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head))
201 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
202
203 #define LIST_FOREACH(var, head, field) \
204 for ((var) = ((head)->lh_first); \
205 (var) != LIST_END(head); \
206 (var) = ((var)->field.le_next))
207
208 #define LIST_FOREACH_SAFE(var, head, field, tvar) \
209 for ((var) = LIST_FIRST((head)); \
210 (var) != LIST_END(head) && \
211 ((tvar) = LIST_NEXT((var), field), 1); \
212 (var) = (tvar))
213
214 #define LIST_MOVE(head1, head2) do { \
215 LIST_INIT((head2)); \
216 if (!LIST_EMPTY((head1))) { \
217 (head2)->lh_first = (head1)->lh_first; \
218 LIST_INIT((head1)); \
219 } \
220 } while (/*CONSTCOND*/0)
221
222 /*
223 * List functions.
224 */
225 #if defined(QUEUEDEBUG)
226 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \
227 if ((head)->lh_first && \
228 (head)->lh_first->field.le_prev != &(head)->lh_first) \
229 QUEUEDEBUG_ABORT("LIST_INSERT_HEAD %p %s:%d", (head), \
230 __FILE__, __LINE__);
231 #define QUEUEDEBUG_LIST_OP(elm, field) \
232 if ((elm)->field.le_next && \
233 (elm)->field.le_next->field.le_prev != \
234 &(elm)->field.le_next) \
235 QUEUEDEBUG_ABORT("LIST_* forw %p %s:%d", (elm), \
236 __FILE__, __LINE__); \
237 if (*(elm)->field.le_prev != (elm)) \
238 QUEUEDEBUG_ABORT("LIST_* back %p %s:%d", (elm), \
239 __FILE__, __LINE__);
240 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \
241 (elm)->field.le_next = (void *)1L; \
242 (elm)->field.le_prev = (void *)1L;
243 #else
244 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
245 #define QUEUEDEBUG_LIST_OP(elm, field)
246 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
247 #endif
248
249 #define LIST_INIT(head) do { \
250 (head)->lh_first = LIST_END(head); \
251 } while (/*CONSTCOND*/0)
252
253 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
254 QUEUEDEBUG_LIST_OP((listelm), field) \
255 if (((elm)->field.le_next = (listelm)->field.le_next) != \
256 LIST_END(head)) \
257 (listelm)->field.le_next->field.le_prev = \
258 &(elm)->field.le_next; \
259 (listelm)->field.le_next = (elm); \
260 (elm)->field.le_prev = &(listelm)->field.le_next; \
261 } while (/*CONSTCOND*/0)
262
263 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
264 QUEUEDEBUG_LIST_OP((listelm), field) \
265 (elm)->field.le_prev = (listelm)->field.le_prev; \
266 (elm)->field.le_next = (listelm); \
267 *(listelm)->field.le_prev = (elm); \
268 (listelm)->field.le_prev = &(elm)->field.le_next; \
269 } while (/*CONSTCOND*/0)
270
271 #define LIST_INSERT_HEAD(head, elm, field) do { \
272 QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \
273 if (((elm)->field.le_next = (head)->lh_first) != LIST_END(head))\
274 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
275 (head)->lh_first = (elm); \
276 (elm)->field.le_prev = &(head)->lh_first; \
277 } while (/*CONSTCOND*/0)
278
279 #define LIST_REMOVE(elm, field) do { \
280 QUEUEDEBUG_LIST_OP((elm), field) \
281 if ((elm)->field.le_next != NULL) \
282 (elm)->field.le_next->field.le_prev = \
283 (elm)->field.le_prev; \
284 *(elm)->field.le_prev = (elm)->field.le_next; \
285 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
286 } while (/*CONSTCOND*/0)
287
288 #define LIST_REPLACE(elm, elm2, field) do { \
289 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
290 (elm2)->field.le_next->field.le_prev = \
291 &(elm2)->field.le_next; \
292 (elm2)->field.le_prev = (elm)->field.le_prev; \
293 *(elm2)->field.le_prev = (elm2); \
294 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
295 } while (/*CONSTCOND*/0)
296
297 /*
298 * Simple queue definitions.
299 */
300 #define SIMPLEQ_HEAD(name, type) \
301 struct name { \
302 struct type *sqh_first; /* first element */ \
303 struct type **sqh_last; /* addr of last next element */ \
304 }
305
306 #define SIMPLEQ_HEAD_INITIALIZER(head) \
307 { NULL, &(head).sqh_first }
308
309 #define SIMPLEQ_ENTRY(type) \
310 struct { \
311 struct type *sqe_next; /* next element */ \
312 }
313
314 /*
315 * Simple queue access methods.
316 */
317 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
318 #define SIMPLEQ_END(head) NULL
319 #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == SIMPLEQ_END(head))
320 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
321
322 #define SIMPLEQ_FOREACH(var, head, field) \
323 for ((var) = ((head)->sqh_first); \
324 (var) != SIMPLEQ_END(head); \
325 (var) = ((var)->field.sqe_next))
326
327 #define SIMPLEQ_FOREACH_SAFE(var, head, field, next) \
328 for ((var) = ((head)->sqh_first); \
329 (var) != SIMPLEQ_END(head) && \
330 ((next = ((var)->field.sqe_next)), 1); \
331 (var) = (next))
332
333 /*
334 * Simple queue functions.
335 */
336 #define SIMPLEQ_INIT(head) do { \
337 (head)->sqh_first = NULL; \
338 (head)->sqh_last = &(head)->sqh_first; \
339 } while (/*CONSTCOND*/0)
340
341 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
342 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
343 (head)->sqh_last = &(elm)->field.sqe_next; \
344 (head)->sqh_first = (elm); \
345 } while (/*CONSTCOND*/0)
346
347 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
348 (elm)->field.sqe_next = NULL; \
349 *(head)->sqh_last = (elm); \
350 (head)->sqh_last = &(elm)->field.sqe_next; \
351 } while (/*CONSTCOND*/0)
352
353 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
354 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
355 (head)->sqh_last = &(elm)->field.sqe_next; \
356 (listelm)->field.sqe_next = (elm); \
357 } while (/*CONSTCOND*/0)
358
359 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
360 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
361 (head)->sqh_last = &(head)->sqh_first; \
362 } while (/*CONSTCOND*/0)
363
364 #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
365 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
366 == NULL) \
367 (head)->sqh_last = &(elm)->field.sqe_next; \
368 } while (/*CONSTCOND*/0)
369
370 #define SIMPLEQ_REMOVE(head, elm, type, field) do { \
371 if ((head)->sqh_first == (elm)) { \
372 SIMPLEQ_REMOVE_HEAD((head), field); \
373 } else { \
374 struct type *curelm = (head)->sqh_first; \
375 while (curelm->field.sqe_next != (elm)) \
376 curelm = curelm->field.sqe_next; \
377 if ((curelm->field.sqe_next = \
378 curelm->field.sqe_next->field.sqe_next) == NULL) \
379 (head)->sqh_last = &(curelm)->field.sqe_next; \
380 } \
381 } while (/*CONSTCOND*/0)
382
383 #define SIMPLEQ_CONCAT(head1, head2) do { \
384 if (!SIMPLEQ_EMPTY((head2))) { \
385 *(head1)->sqh_last = (head2)->sqh_first; \
386 (head1)->sqh_last = (head2)->sqh_last; \
387 SIMPLEQ_INIT((head2)); \
388 } \
389 } while (/*CONSTCOND*/0)
390
391 #define SIMPLEQ_LAST(head, type, field) \
392 (SIMPLEQ_EMPTY((head)) ? \
393 NULL : \
394 ((struct type *)(void *) \
395 ((char *)((head)->sqh_last) - offsetof(struct type, field))))
396
397 /*
398 * Tail queue definitions.
399 */
400 #define _TAILQ_HEAD(name, type, qual) \
401 struct name { \
402 qual type *tqh_first; /* first element */ \
403 qual type *qual *tqh_last; /* addr of last next element */ \
404 }
405 #define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,)
406
407 #define TAILQ_HEAD_INITIALIZER(head) \
408 { TAILQ_END(head), &(head).tqh_first }
409
410 #define _TAILQ_ENTRY(type, qual) \
411 struct { \
412 qual type *tqe_next; /* next element */ \
413 qual type *qual *tqe_prev; /* address of previous next element */\
414 }
415 #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,)
416
417 /*
418 * Tail queue access methods.
419 */
420 #define TAILQ_FIRST(head) ((head)->tqh_first)
421 #define TAILQ_END(head) (NULL)
422 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
423 #define TAILQ_LAST(head, headname) \
424 (*(((struct headname *)((head)->tqh_last))->tqh_last))
425 #define TAILQ_PREV(elm, headname, field) \
426 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
427 #define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head))
428
429
430 #define TAILQ_FOREACH(var, head, field) \
431 for ((var) = ((head)->tqh_first); \
432 (var) != TAILQ_END(head); \
433 (var) = ((var)->field.tqe_next))
434
435 #define TAILQ_FOREACH_SAFE(var, head, field, next) \
436 for ((var) = ((head)->tqh_first); \
437 (var) != TAILQ_END(head) && \
438 ((next) = TAILQ_NEXT(var, field), 1); (var) = (next))
439
440 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
441 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\
442 (var) != TAILQ_END(head); \
443 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
444
445 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \
446 for ((var) = TAILQ_LAST((head), headname); \
447 (var) != TAILQ_END(head) && \
448 ((prev) = TAILQ_PREV((var), headname, field), 1); (var) = (prev))
449
450 /*
451 * Tail queue functions.
452 */
453 #if defined(QUEUEDEBUG)
454 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \
455 if ((head)->tqh_first && \
456 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \
457 QUEUEDEBUG_ABORT("TAILQ_INSERT_HEAD %p %s:%d", (head), \
458 __FILE__, __LINE__);
459 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \
460 if (*(head)->tqh_last != NULL) \
461 QUEUEDEBUG_ABORT("TAILQ_INSERT_TAIL %p %s:%d", (head), \
462 __FILE__, __LINE__);
463 #define QUEUEDEBUG_TAILQ_OP(elm, field) \
464 if ((elm)->field.tqe_next && \
465 (elm)->field.tqe_next->field.tqe_prev != \
466 &(elm)->field.tqe_next) \
467 QUEUEDEBUG_ABORT("TAILQ_* forw %p %s:%d", (elm), \
468 __FILE__, __LINE__); \
469 if (*(elm)->field.tqe_prev != (elm)) \
470 QUEUEDEBUG_ABORT("TAILQ_* back %p %s:%d", (elm), \
471 __FILE__, __LINE__);
472 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \
473 if ((elm)->field.tqe_next == NULL && \
474 (head)->tqh_last != &(elm)->field.tqe_next) \
475 QUEUEDEBUG_ABORT("TAILQ_PREREMOVE head %p elm %p %s:%d",\
476 (head), (elm), __FILE__, __LINE__);
477 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \
478 (elm)->field.tqe_next = (void *)1L; \
479 (elm)->field.tqe_prev = (void *)1L;
480 #else
481 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
482 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
483 #define QUEUEDEBUG_TAILQ_OP(elm, field)
484 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
485 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
486 #endif
487
488 #define TAILQ_INIT(head) do { \
489 (head)->tqh_first = TAILQ_END(head); \
490 (head)->tqh_last = &(head)->tqh_first; \
491 } while (/*CONSTCOND*/0)
492
493 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
494 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \
495 if (((elm)->field.tqe_next = (head)->tqh_first) != TAILQ_END(head))\
496 (head)->tqh_first->field.tqe_prev = \
497 &(elm)->field.tqe_next; \
498 else \
499 (head)->tqh_last = &(elm)->field.tqe_next; \
500 (head)->tqh_first = (elm); \
501 (elm)->field.tqe_prev = &(head)->tqh_first; \
502 } while (/*CONSTCOND*/0)
503
504 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
505 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \
506 (elm)->field.tqe_next = TAILQ_END(head); \
507 (elm)->field.tqe_prev = (head)->tqh_last; \
508 *(head)->tqh_last = (elm); \
509 (head)->tqh_last = &(elm)->field.tqe_next; \
510 } while (/*CONSTCOND*/0)
511
512 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
513 QUEUEDEBUG_TAILQ_OP((listelm), field) \
514 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != \
515 TAILQ_END(head)) \
516 (elm)->field.tqe_next->field.tqe_prev = \
517 &(elm)->field.tqe_next; \
518 else \
519 (head)->tqh_last = &(elm)->field.tqe_next; \
520 (listelm)->field.tqe_next = (elm); \
521 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
522 } while (/*CONSTCOND*/0)
523
524 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
525 QUEUEDEBUG_TAILQ_OP((listelm), field) \
526 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
527 (elm)->field.tqe_next = (listelm); \
528 *(listelm)->field.tqe_prev = (elm); \
529 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
530 } while (/*CONSTCOND*/0)
531
532 #define TAILQ_REMOVE(head, elm, field) do { \
533 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \
534 QUEUEDEBUG_TAILQ_OP((elm), field) \
535 if (((elm)->field.tqe_next) != TAILQ_END(head)) \
536 (elm)->field.tqe_next->field.tqe_prev = \
537 (elm)->field.tqe_prev; \
538 else \
539 (head)->tqh_last = (elm)->field.tqe_prev; \
540 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
541 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
542 } while (/*CONSTCOND*/0)
543
544 #define TAILQ_REPLACE(head, elm, elm2, field) do { \
545 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != \
546 TAILQ_END(head)) \
547 (elm2)->field.tqe_next->field.tqe_prev = \
548 &(elm2)->field.tqe_next; \
549 else \
550 (head)->tqh_last = &(elm2)->field.tqe_next; \
551 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
552 *(elm2)->field.tqe_prev = (elm2); \
553 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
554 } while (/*CONSTCOND*/0)
555
556 #define TAILQ_CONCAT(head1, head2, field) do { \
557 if (!TAILQ_EMPTY(head2)) { \
558 *(head1)->tqh_last = (head2)->tqh_first; \
559 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
560 (head1)->tqh_last = (head2)->tqh_last; \
561 TAILQ_INIT((head2)); \
562 } \
563 } while (/*CONSTCOND*/0)
564
565 /*
566 * Singly-linked Tail queue declarations.
567 */
568 #define STAILQ_HEAD(name, type) \
569 struct name { \
570 struct type *stqh_first; /* first element */ \
571 struct type **stqh_last; /* addr of last next element */ \
572 }
573
574 #define STAILQ_HEAD_INITIALIZER(head) \
575 { NULL, &(head).stqh_first }
576
577 #define STAILQ_ENTRY(type) \
578 struct { \
579 struct type *stqe_next; /* next element */ \
580 }
581
582 /*
583 * Singly-linked Tail queue access methods.
584 */
585 #define STAILQ_FIRST(head) ((head)->stqh_first)
586 #define STAILQ_END(head) NULL
587 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
588 #define STAILQ_EMPTY(head) (STAILQ_FIRST(head) == STAILQ_END(head))
589
590 /*
591 * Singly-linked Tail queue functions.
592 */
593 #define STAILQ_INIT(head) do { \
594 (head)->stqh_first = NULL; \
595 (head)->stqh_last = &(head)->stqh_first; \
596 } while (/*CONSTCOND*/0)
597
598 #define STAILQ_INSERT_HEAD(head, elm, field) do { \
599 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
600 (head)->stqh_last = &(elm)->field.stqe_next; \
601 (head)->stqh_first = (elm); \
602 } while (/*CONSTCOND*/0)
603
604 #define STAILQ_INSERT_TAIL(head, elm, field) do { \
605 (elm)->field.stqe_next = NULL; \
606 *(head)->stqh_last = (elm); \
607 (head)->stqh_last = &(elm)->field.stqe_next; \
608 } while (/*CONSTCOND*/0)
609
610 #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
611 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
612 (head)->stqh_last = &(elm)->field.stqe_next; \
613 (listelm)->field.stqe_next = (elm); \
614 } while (/*CONSTCOND*/0)
615
616 #define STAILQ_REMOVE_HEAD(head, field) do { \
617 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
618 (head)->stqh_last = &(head)->stqh_first; \
619 } while (/*CONSTCOND*/0)
620
621 #define STAILQ_REMOVE(head, elm, type, field) do { \
622 if ((head)->stqh_first == (elm)) { \
623 STAILQ_REMOVE_HEAD((head), field); \
624 } else { \
625 struct type *curelm = (head)->stqh_first; \
626 while (curelm->field.stqe_next != (elm)) \
627 curelm = curelm->field.stqe_next; \
628 if ((curelm->field.stqe_next = \
629 curelm->field.stqe_next->field.stqe_next) == NULL) \
630 (head)->stqh_last = &(curelm)->field.stqe_next; \
631 } \
632 } while (/*CONSTCOND*/0)
633
634 #define STAILQ_FOREACH(var, head, field) \
635 for ((var) = ((head)->stqh_first); \
636 (var); \
637 (var) = ((var)->field.stqe_next))
638
639 #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
640 for ((var) = STAILQ_FIRST((head)); \
641 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
642 (var) = (tvar))
643
644 #define STAILQ_CONCAT(head1, head2) do { \
645 if (!STAILQ_EMPTY((head2))) { \
646 *(head1)->stqh_last = (head2)->stqh_first; \
647 (head1)->stqh_last = (head2)->stqh_last; \
648 STAILQ_INIT((head2)); \
649 } \
650 } while (/*CONSTCOND*/0)
651
652 #define STAILQ_LAST(head, type, field) \
653 (STAILQ_EMPTY((head)) ? \
654 NULL : \
655 ((struct type *)(void *) \
656 ((char *)((head)->stqh_last) - offsetof(struct type, field))))
657
658
659 #ifndef _KERNEL
660 /*
661 * Circular queue definitions. Do not use. We still keep the macros
662 * for compatibility but because of pointer aliasing issues their use
663 * is discouraged!
664 */
665
666 /*
667 * __launder_type(): We use this ugly hack to work around the the compiler
668 * noticing that two types may not alias each other and elide tests in code.
669 * We hit this in the CIRCLEQ macros when comparing 'struct name *' and
670 * 'struct type *' (see CIRCLEQ_HEAD()). Modern compilers (such as GCC
671 * 4.8) declare these comparisons as always false, causing the code to
672 * not run as designed.
673 *
674 * This hack is only to be used for comparisons and thus can be fully const.
675 * Do not use for assignment.
676 *
677 * If we ever choose to change the ABI of the CIRCLEQ macros, we could fix
678 * this by changing the head/tail sentinal values, but see the note above
679 * this one.
680 */
681 #ifdef _MSC_VER
682 #define __launder_type(x) ((const void *)(x))
683 #else
684 static inline const void * __launder_type(const void *);
685 static inline const void *
__launder_type(const void * __x)686 __launder_type(const void *__x)
687 {
688 __asm __volatile("" : "+r" (__x));
689 return __x;
690 }
691 #endif
692
693 #if defined(QUEUEDEBUG)
694 #define QUEUEDEBUG_CIRCLEQ_HEAD(head, field) \
695 if ((head)->cqh_first != CIRCLEQ_ENDC(head) && \
696 (head)->cqh_first->field.cqe_prev != CIRCLEQ_ENDC(head)) \
697 QUEUEDEBUG_ABORT("CIRCLEQ head forw %p %s:%d", (head), \
698 __FILE__, __LINE__); \
699 if ((head)->cqh_last != CIRCLEQ_ENDC(head) && \
700 (head)->cqh_last->field.cqe_next != CIRCLEQ_ENDC(head)) \
701 QUEUEDEBUG_ABORT("CIRCLEQ head back %p %s:%d", (head), \
702 __FILE__, __LINE__);
703 #define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field) \
704 if ((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) { \
705 if ((head)->cqh_last != (elm)) \
706 QUEUEDEBUG_ABORT("CIRCLEQ elm last %p %s:%d", \
707 (elm), __FILE__, __LINE__); \
708 } else { \
709 if ((elm)->field.cqe_next->field.cqe_prev != (elm)) \
710 QUEUEDEBUG_ABORT("CIRCLEQ elm forw %p %s:%d", \
711 (elm), __FILE__, __LINE__); \
712 } \
713 if ((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) { \
714 if ((head)->cqh_first != (elm)) \
715 QUEUEDEBUG_ABORT("CIRCLEQ elm first %p %s:%d", \
716 (elm), __FILE__, __LINE__); \
717 } else { \
718 if ((elm)->field.cqe_prev->field.cqe_next != (elm)) \
719 QUEUEDEBUG_ABORT("CIRCLEQ elm prev %p %s:%d", \
720 (elm), __FILE__, __LINE__); \
721 }
722 #define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field) \
723 (elm)->field.cqe_next = (void *)1L; \
724 (elm)->field.cqe_prev = (void *)1L;
725 #else
726 #define QUEUEDEBUG_CIRCLEQ_HEAD(head, field)
727 #define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field)
728 #define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field)
729 #endif
730
731 #define CIRCLEQ_HEAD(name, type) \
732 struct name { \
733 struct type *cqh_first; /* first element */ \
734 struct type *cqh_last; /* last element */ \
735 }
736
737 #define CIRCLEQ_HEAD_INITIALIZER(head) \
738 { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
739
740 #define CIRCLEQ_ENTRY(type) \
741 struct { \
742 struct type *cqe_next; /* next element */ \
743 struct type *cqe_prev; /* previous element */ \
744 }
745
746 /*
747 * Circular queue functions.
748 */
749 #define CIRCLEQ_INIT(head) do { \
750 (head)->cqh_first = CIRCLEQ_END(head); \
751 (head)->cqh_last = CIRCLEQ_END(head); \
752 } while (/*CONSTCOND*/0)
753
754 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
755 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
756 QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \
757 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
758 (elm)->field.cqe_prev = (listelm); \
759 if ((listelm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
760 (head)->cqh_last = (elm); \
761 else \
762 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
763 (listelm)->field.cqe_next = (elm); \
764 } while (/*CONSTCOND*/0)
765
766 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
767 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
768 QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \
769 (elm)->field.cqe_next = (listelm); \
770 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
771 if ((listelm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
772 (head)->cqh_first = (elm); \
773 else \
774 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
775 (listelm)->field.cqe_prev = (elm); \
776 } while (/*CONSTCOND*/0)
777
778 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
779 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
780 (elm)->field.cqe_next = (head)->cqh_first; \
781 (elm)->field.cqe_prev = CIRCLEQ_END(head); \
782 if ((head)->cqh_last == CIRCLEQ_ENDC(head)) \
783 (head)->cqh_last = (elm); \
784 else \
785 (head)->cqh_first->field.cqe_prev = (elm); \
786 (head)->cqh_first = (elm); \
787 } while (/*CONSTCOND*/0)
788
789 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
790 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
791 (elm)->field.cqe_next = CIRCLEQ_END(head); \
792 (elm)->field.cqe_prev = (head)->cqh_last; \
793 if ((head)->cqh_first == CIRCLEQ_ENDC(head)) \
794 (head)->cqh_first = (elm); \
795 else \
796 (head)->cqh_last->field.cqe_next = (elm); \
797 (head)->cqh_last = (elm); \
798 } while (/*CONSTCOND*/0)
799
800 #define CIRCLEQ_REMOVE(head, elm, field) do { \
801 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
802 QUEUEDEBUG_CIRCLEQ_ELM((head), (elm), field) \
803 if ((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
804 (head)->cqh_last = (elm)->field.cqe_prev; \
805 else \
806 (elm)->field.cqe_next->field.cqe_prev = \
807 (elm)->field.cqe_prev; \
808 if ((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
809 (head)->cqh_first = (elm)->field.cqe_next; \
810 else \
811 (elm)->field.cqe_prev->field.cqe_next = \
812 (elm)->field.cqe_next; \
813 QUEUEDEBUG_CIRCLEQ_POSTREMOVE((elm), field) \
814 } while (/*CONSTCOND*/0)
815
816 #define CIRCLEQ_FOREACH(var, head, field) \
817 for ((var) = ((head)->cqh_first); \
818 (var) != CIRCLEQ_ENDC(head); \
819 (var) = ((var)->field.cqe_next))
820
821 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
822 for ((var) = ((head)->cqh_last); \
823 (var) != CIRCLEQ_ENDC(head); \
824 (var) = ((var)->field.cqe_prev))
825
826 /*
827 * Circular queue access methods.
828 */
829 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
830 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
831 /* For comparisons */
832 #define CIRCLEQ_ENDC(head) (__launder_type(head))
833 /* For assignments */
834 #define CIRCLEQ_END(head) ((void *)(head))
835 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
836 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
837 #define CIRCLEQ_EMPTY(head) \
838 (CIRCLEQ_FIRST(head) == CIRCLEQ_ENDC(head))
839
840 #define CIRCLEQ_LOOP_NEXT(head, elm, field) \
841 (((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
842 ? ((head)->cqh_first) \
843 : (elm->field.cqe_next))
844 #define CIRCLEQ_LOOP_PREV(head, elm, field) \
845 (((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
846 ? ((head)->cqh_last) \
847 : (elm->field.cqe_prev))
848 #endif /* !_KERNEL */
849
850 #endif /* !_SYS_QUEUE_H_ */
851