1/* $NetBSD: queue.h,v 1.74 2019/03/23 12:01:18 maxv 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(_KERNEL) && defined(_KERNEL_OPT)
95#include "opt_diagnostic.h"
96#ifdef DIAGNOSTIC
97#define QUEUEDEBUG 1
98#endif
99#endif
100
101#if defined(QUEUEDEBUG)
102# if defined(_KERNEL)
103# define QUEUEDEBUG_ABORT(...) panic(__VA_ARGS__)
104# else
105# include <err.h>
106# define QUEUEDEBUG_ABORT(...) err(1, __VA_ARGS__)
107# endif
108#endif
109
110/*
111 * Singly-linked List definitions.
112 */
113#define SLIST_HEAD(name, type) \
114struct name { \
115 struct type *slh_first; /* first element */ \
116}
117
118#define SLIST_HEAD_INITIALIZER(head) \
119 { NULL }
120
121#define SLIST_ENTRY(type) \
122struct { \
123 struct type *sle_next; /* next element */ \
124}
125
126/*
127 * Singly-linked List access methods.
128 */
129#define SLIST_FIRST(head) ((head)->slh_first)
130#define SLIST_END(head) NULL
131#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
132#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
133
134#define SLIST_FOREACH(var, head, field) \
135 for((var) = (head)->slh_first; \
136 (var) != SLIST_END(head); \
137 (var) = (var)->field.sle_next)
138
139#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
140 for ((var) = SLIST_FIRST((head)); \
141 (var) != SLIST_END(head) && \
142 ((tvar) = SLIST_NEXT((var), field), 1); \
143 (var) = (tvar))
144
145/*
146 * Singly-linked List functions.
147 */
148#define SLIST_INIT(head) do { \
149 (head)->slh_first = SLIST_END(head); \
150} while (/*CONSTCOND*/0)
151
152#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
153 (elm)->field.sle_next = (slistelm)->field.sle_next; \
154 (slistelm)->field.sle_next = (elm); \
155} while (/*CONSTCOND*/0)
156
157#define SLIST_INSERT_HEAD(head, elm, field) do { \
158 (elm)->field.sle_next = (head)->slh_first; \
159 (head)->slh_first = (elm); \
160} while (/*CONSTCOND*/0)
161
162#define SLIST_REMOVE_AFTER(slistelm, field) do { \
163 (slistelm)->field.sle_next = \
164 SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \
165} while (/*CONSTCOND*/0)
166
167#define SLIST_REMOVE_HEAD(head, field) do { \
168 (head)->slh_first = (head)->slh_first->field.sle_next; \
169} while (/*CONSTCOND*/0)
170
171#define SLIST_REMOVE(head, elm, type, field) do { \
172 if ((head)->slh_first == (elm)) { \
173 SLIST_REMOVE_HEAD((head), field); \
174 } \
175 else { \
176 struct type *curelm = (head)->slh_first; \
177 while(curelm->field.sle_next != (elm)) \
178 curelm = curelm->field.sle_next; \
179 curelm->field.sle_next = \
180 curelm->field.sle_next->field.sle_next; \
181 } \
182} while (/*CONSTCOND*/0)
183
184
185/*
186 * List definitions.
187 */
188#define LIST_HEAD(name, type) \
189struct name { \
190 struct type *lh_first; /* first element */ \
191}
192
193#define LIST_HEAD_INITIALIZER(head) \
194 { NULL }
195
196#define LIST_ENTRY(type) \
197struct { \
198 struct type *le_next; /* next element */ \
199 struct type **le_prev; /* address of previous next element */ \
200}
201
202/*
203 * List access methods.
204 */
205#define LIST_FIRST(head) ((head)->lh_first)
206#define LIST_END(head) NULL
207#define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head))
208#define LIST_NEXT(elm, field) ((elm)->field.le_next)
209
210#define LIST_FOREACH(var, head, field) \
211 for ((var) = ((head)->lh_first); \
212 (var) != LIST_END(head); \
213 (var) = ((var)->field.le_next))
214
215#define LIST_FOREACH_SAFE(var, head, field, tvar) \
216 for ((var) = LIST_FIRST((head)); \
217 (var) != LIST_END(head) && \
218 ((tvar) = LIST_NEXT((var), field), 1); \
219 (var) = (tvar))
220
221#define LIST_MOVE(head1, head2, field) do { \
222 LIST_INIT((head2)); \
223 if (!LIST_EMPTY((head1))) { \
224 (head2)->lh_first = (head1)->lh_first; \
225 (head2)->lh_first->field.le_prev = &(head2)->lh_first; \
226 LIST_INIT((head1)); \
227 } \
228} while (/*CONSTCOND*/0)
229
230/*
231 * List functions.
232 */
233#if defined(QUEUEDEBUG)
234#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \
235 if ((head)->lh_first && \
236 (head)->lh_first->field.le_prev != &(head)->lh_first) \
237 QUEUEDEBUG_ABORT("LIST_INSERT_HEAD %p %s:%d", (head), \
238 __FILE__, __LINE__);
239#define QUEUEDEBUG_LIST_OP(elm, field) \
240 if ((elm)->field.le_next && \
241 (elm)->field.le_next->field.le_prev != \
242 &(elm)->field.le_next) \
243 QUEUEDEBUG_ABORT("LIST_* forw %p %s:%d", (elm), \
244 __FILE__, __LINE__); \
245 if (*(elm)->field.le_prev != (elm)) \
246 QUEUEDEBUG_ABORT("LIST_* back %p %s:%d", (elm), \
247 __FILE__, __LINE__);
248#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \
249 (elm)->field.le_next = (void *)1L; \
250 (elm)->field.le_prev = (void *)1L;
251#else
252#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
253#define QUEUEDEBUG_LIST_OP(elm, field)
254#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
255#endif
256
257#define LIST_INIT(head) do { \
258 (head)->lh_first = LIST_END(head); \
259} while (/*CONSTCOND*/0)
260
261#define LIST_INSERT_AFTER(listelm, elm, field) do { \
262 QUEUEDEBUG_LIST_OP((listelm), field) \
263 if (((elm)->field.le_next = (listelm)->field.le_next) != \
264 LIST_END(head)) \
265 (listelm)->field.le_next->field.le_prev = \
266 &(elm)->field.le_next; \
267 (listelm)->field.le_next = (elm); \
268 (elm)->field.le_prev = &(listelm)->field.le_next; \
269} while (/*CONSTCOND*/0)
270
271#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
272 QUEUEDEBUG_LIST_OP((listelm), field) \
273 (elm)->field.le_prev = (listelm)->field.le_prev; \
274 (elm)->field.le_next = (listelm); \
275 *(listelm)->field.le_prev = (elm); \
276 (listelm)->field.le_prev = &(elm)->field.le_next; \
277} while (/*CONSTCOND*/0)
278
279#define LIST_INSERT_HEAD(head, elm, field) do { \
280 QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \
281 if (((elm)->field.le_next = (head)->lh_first) != LIST_END(head))\
282 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
283 (head)->lh_first = (elm); \
284 (elm)->field.le_prev = &(head)->lh_first; \
285} while (/*CONSTCOND*/0)
286
287#define LIST_REMOVE(elm, field) do { \
288 QUEUEDEBUG_LIST_OP((elm), field) \
289 if ((elm)->field.le_next != NULL) \
290 (elm)->field.le_next->field.le_prev = \
291 (elm)->field.le_prev; \
292 *(elm)->field.le_prev = (elm)->field.le_next; \
293 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
294} while (/*CONSTCOND*/0)
295
296#define LIST_REPLACE(elm, elm2, field) do { \
297 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
298 (elm2)->field.le_next->field.le_prev = \
299 &(elm2)->field.le_next; \
300 (elm2)->field.le_prev = (elm)->field.le_prev; \
301 *(elm2)->field.le_prev = (elm2); \
302 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
303} while (/*CONSTCOND*/0)
304
305/*
306 * Simple queue definitions.
307 */
308#define SIMPLEQ_HEAD(name, type) \
309struct name { \
310 struct type *sqh_first; /* first element */ \
311 struct type **sqh_last; /* addr of last next element */ \
312}
313
314#define SIMPLEQ_HEAD_INITIALIZER(head) \
315 { NULL, &(head).sqh_first }
316
317#define SIMPLEQ_ENTRY(type) \
318struct { \
319 struct type *sqe_next; /* next element */ \
320}
321
322/*
323 * Simple queue access methods.
324 */
325#define SIMPLEQ_FIRST(head) ((head)->sqh_first)
326#define SIMPLEQ_END(head) NULL
327#define SIMPLEQ_EMPTY(head) ((head)->sqh_first == SIMPLEQ_END(head))
328#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
329
330#define SIMPLEQ_FOREACH(var, head, field) \
331 for ((var) = ((head)->sqh_first); \
332 (var) != SIMPLEQ_END(head); \
333 (var) = ((var)->field.sqe_next))
334
335#define SIMPLEQ_FOREACH_SAFE(var, head, field, next) \
336 for ((var) = ((head)->sqh_first); \
337 (var) != SIMPLEQ_END(head) && \
338 ((next = ((var)->field.sqe_next)), 1); \
339 (var) = (next))
340
341/*
342 * Simple queue functions.
343 */
344#define SIMPLEQ_INIT(head) do { \
345 (head)->sqh_first = NULL; \
346 (head)->sqh_last = &(head)->sqh_first; \
347} while (/*CONSTCOND*/0)
348
349#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
350 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
351 (head)->sqh_last = &(elm)->field.sqe_next; \
352 (head)->sqh_first = (elm); \
353} while (/*CONSTCOND*/0)
354
355#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
356 (elm)->field.sqe_next = NULL; \
357 *(head)->sqh_last = (elm); \
358 (head)->sqh_last = &(elm)->field.sqe_next; \
359} while (/*CONSTCOND*/0)
360
361#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
362 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
363 (head)->sqh_last = &(elm)->field.sqe_next; \
364 (listelm)->field.sqe_next = (elm); \
365} while (/*CONSTCOND*/0)
366
367#define SIMPLEQ_REMOVE_HEAD(head, field) do { \
368 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
369 (head)->sqh_last = &(head)->sqh_first; \
370} while (/*CONSTCOND*/0)
371
372#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
373 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
374 == NULL) \
375 (head)->sqh_last = &(elm)->field.sqe_next; \
376} while (/*CONSTCOND*/0)
377
378#define SIMPLEQ_REMOVE(head, elm, type, field) do { \
379 if ((head)->sqh_first == (elm)) { \
380 SIMPLEQ_REMOVE_HEAD((head), field); \
381 } else { \
382 struct type *curelm = (head)->sqh_first; \
383 while (curelm->field.sqe_next != (elm)) \
384 curelm = curelm->field.sqe_next; \
385 if ((curelm->field.sqe_next = \
386 curelm->field.sqe_next->field.sqe_next) == NULL) \
387 (head)->sqh_last = &(curelm)->field.sqe_next; \
388 } \
389} while (/*CONSTCOND*/0)
390
391#define SIMPLEQ_CONCAT(head1, head2) do { \
392 if (!SIMPLEQ_EMPTY((head2))) { \
393 *(head1)->sqh_last = (head2)->sqh_first; \
394 (head1)->sqh_last = (head2)->sqh_last; \
395 SIMPLEQ_INIT((head2)); \
396 } \
397} while (/*CONSTCOND*/0)
398
399#define SIMPLEQ_LAST(head, type, field) \
400 (SIMPLEQ_EMPTY((head)) ? \
401 NULL : \
402 ((struct type *)(void *) \
403 ((char *)((head)->sqh_last) - offsetof(struct type, field))))
404
405/*
406 * Tail queue definitions.
407 */
408#define _TAILQ_HEAD(name, type, qual) \
409struct name { \
410 qual type *tqh_first; /* first element */ \
411 qual type *qual *tqh_last; /* addr of last next element */ \
412}
413#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,)
414
415#define TAILQ_HEAD_INITIALIZER(head) \
416 { TAILQ_END(head), &(head).tqh_first }
417
418#define _TAILQ_ENTRY(type, qual) \
419struct { \
420 qual type *tqe_next; /* next element */ \
421 qual type *qual *tqe_prev; /* address of previous next element */\
422}
423#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,)
424
425/*
426 * Tail queue access methods.
427 */
428#define TAILQ_FIRST(head) ((head)->tqh_first)
429#define TAILQ_END(head) (NULL)
430#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
431#define TAILQ_LAST(head, headname) \
432 (*(((struct headname *)(void *)((head)->tqh_last))->tqh_last))
433#define TAILQ_PREV(elm, headname, field) \
434 (*(((struct headname *)(void *)((elm)->field.tqe_prev))->tqh_last))
435#define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head))
436
437
438#define TAILQ_FOREACH(var, head, field) \
439 for ((var) = ((head)->tqh_first); \
440 (var) != TAILQ_END(head); \
441 (var) = ((var)->field.tqe_next))
442
443#define TAILQ_FOREACH_SAFE(var, head, field, next) \
444 for ((var) = ((head)->tqh_first); \
445 (var) != TAILQ_END(head) && \
446 ((next) = TAILQ_NEXT(var, field), 1); (var) = (next))
447
448#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
449 for ((var) = TAILQ_LAST((head), headname); \
450 (var) != TAILQ_END(head); \
451 (var) = TAILQ_PREV((var), headname, field))
452
453#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \
454 for ((var) = TAILQ_LAST((head), headname); \
455 (var) != TAILQ_END(head) && \
456 ((prev) = TAILQ_PREV((var), headname, field), 1); (var) = (prev))
457
458/*
459 * Tail queue functions.
460 */
461#if defined(QUEUEDEBUG)
462#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \
463 if ((head)->tqh_first && \
464 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \
465 QUEUEDEBUG_ABORT("TAILQ_INSERT_HEAD %p %s:%d", (head), \
466 __FILE__, __LINE__);
467#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \
468 if (*(head)->tqh_last != NULL) \
469 QUEUEDEBUG_ABORT("TAILQ_INSERT_TAIL %p %s:%d", (head), \
470 __FILE__, __LINE__);
471#define QUEUEDEBUG_TAILQ_OP(elm, field) \
472 if ((elm)->field.tqe_next && \
473 (elm)->field.tqe_next->field.tqe_prev != \
474 &(elm)->field.tqe_next) \
475 QUEUEDEBUG_ABORT("TAILQ_* forw %p %s:%d", (elm), \
476 __FILE__, __LINE__); \
477 if (*(elm)->field.tqe_prev != (elm)) \
478 QUEUEDEBUG_ABORT("TAILQ_* back %p %s:%d", (elm), \
479 __FILE__, __LINE__);
480#define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \
481 if ((elm)->field.tqe_next == NULL && \
482 (head)->tqh_last != &(elm)->field.tqe_next) \
483 QUEUEDEBUG_ABORT("TAILQ_PREREMOVE head %p elm %p %s:%d",\
484 (head), (elm), __FILE__, __LINE__);
485#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \
486 (elm)->field.tqe_next = (void *)1L; \
487 (elm)->field.tqe_prev = (void *)1L;
488#else
489#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
490#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
491#define QUEUEDEBUG_TAILQ_OP(elm, field)
492#define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
493#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
494#endif
495
496#define TAILQ_INIT(head) do { \
497 (head)->tqh_first = TAILQ_END(head); \
498 (head)->tqh_last = &(head)->tqh_first; \
499} while (/*CONSTCOND*/0)
500
501#define TAILQ_INSERT_HEAD(head, elm, field) do { \
502 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \
503 if (((elm)->field.tqe_next = (head)->tqh_first) != TAILQ_END(head))\
504 (head)->tqh_first->field.tqe_prev = \
505 &(elm)->field.tqe_next; \
506 else \
507 (head)->tqh_last = &(elm)->field.tqe_next; \
508 (head)->tqh_first = (elm); \
509 (elm)->field.tqe_prev = &(head)->tqh_first; \
510} while (/*CONSTCOND*/0)
511
512#define TAILQ_INSERT_TAIL(head, elm, field) do { \
513 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \
514 (elm)->field.tqe_next = TAILQ_END(head); \
515 (elm)->field.tqe_prev = (head)->tqh_last; \
516 *(head)->tqh_last = (elm); \
517 (head)->tqh_last = &(elm)->field.tqe_next; \
518} while (/*CONSTCOND*/0)
519
520#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
521 QUEUEDEBUG_TAILQ_OP((listelm), field) \
522 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != \
523 TAILQ_END(head)) \
524 (elm)->field.tqe_next->field.tqe_prev = \
525 &(elm)->field.tqe_next; \
526 else \
527 (head)->tqh_last = &(elm)->field.tqe_next; \
528 (listelm)->field.tqe_next = (elm); \
529 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
530} while (/*CONSTCOND*/0)
531
532#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
533 QUEUEDEBUG_TAILQ_OP((listelm), field) \
534 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
535 (elm)->field.tqe_next = (listelm); \
536 *(listelm)->field.tqe_prev = (elm); \
537 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
538} while (/*CONSTCOND*/0)
539
540#define TAILQ_REMOVE(head, elm, field) do { \
541 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \
542 QUEUEDEBUG_TAILQ_OP((elm), field) \
543 if (((elm)->field.tqe_next) != TAILQ_END(head)) \
544 (elm)->field.tqe_next->field.tqe_prev = \
545 (elm)->field.tqe_prev; \
546 else \
547 (head)->tqh_last = (elm)->field.tqe_prev; \
548 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
549 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
550} while (/*CONSTCOND*/0)
551
552#define TAILQ_REPLACE(head, elm, elm2, field) do { \
553 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != \
554 TAILQ_END(head)) \
555 (elm2)->field.tqe_next->field.tqe_prev = \
556 &(elm2)->field.tqe_next; \
557 else \
558 (head)->tqh_last = &(elm2)->field.tqe_next; \
559 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
560 *(elm2)->field.tqe_prev = (elm2); \
561 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
562} while (/*CONSTCOND*/0)
563
564#define TAILQ_CONCAT(head1, head2, field) do { \
565 if (!TAILQ_EMPTY(head2)) { \
566 *(head1)->tqh_last = (head2)->tqh_first; \
567 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
568 (head1)->tqh_last = (head2)->tqh_last; \
569 TAILQ_INIT((head2)); \
570 } \
571} while (/*CONSTCOND*/0)
572
573/*
574 * Singly-linked Tail queue declarations.
575 */
576#define STAILQ_HEAD(name, type) \
577struct name { \
578 struct type *stqh_first; /* first element */ \
579 struct type **stqh_last; /* addr of last next element */ \
580}
581
582#define STAILQ_HEAD_INITIALIZER(head) \
583 { NULL, &(head).stqh_first }
584
585#define STAILQ_ENTRY(type) \
586struct { \
587 struct type *stqe_next; /* next element */ \
588}
589
590/*
591 * Singly-linked Tail queue access methods.
592 */
593#define STAILQ_FIRST(head) ((head)->stqh_first)
594#define STAILQ_END(head) NULL
595#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
596#define STAILQ_EMPTY(head) (STAILQ_FIRST(head) == STAILQ_END(head))
597
598/*
599 * Singly-linked Tail queue functions.
600 */
601#define STAILQ_INIT(head) do { \
602 (head)->stqh_first = NULL; \
603 (head)->stqh_last = &(head)->stqh_first; \
604} while (/*CONSTCOND*/0)
605
606#define STAILQ_INSERT_HEAD(head, elm, field) do { \
607 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
608 (head)->stqh_last = &(elm)->field.stqe_next; \
609 (head)->stqh_first = (elm); \
610} while (/*CONSTCOND*/0)
611
612#define STAILQ_INSERT_TAIL(head, elm, field) do { \
613 (elm)->field.stqe_next = NULL; \
614 *(head)->stqh_last = (elm); \
615 (head)->stqh_last = &(elm)->field.stqe_next; \
616} while (/*CONSTCOND*/0)
617
618#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
619 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
620 (head)->stqh_last = &(elm)->field.stqe_next; \
621 (listelm)->field.stqe_next = (elm); \
622} while (/*CONSTCOND*/0)
623
624#define STAILQ_REMOVE_HEAD(head, field) do { \
625 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
626 (head)->stqh_last = &(head)->stqh_first; \
627} while (/*CONSTCOND*/0)
628
629#define STAILQ_REMOVE(head, elm, type, field) do { \
630 if ((head)->stqh_first == (elm)) { \
631 STAILQ_REMOVE_HEAD((head), field); \
632 } else { \
633 struct type *curelm = (head)->stqh_first; \
634 while (curelm->field.stqe_next != (elm)) \
635 curelm = curelm->field.stqe_next; \
636 if ((curelm->field.stqe_next = \
637 curelm->field.stqe_next->field.stqe_next) == NULL) \
638 (head)->stqh_last = &(curelm)->field.stqe_next; \
639 } \
640} while (/*CONSTCOND*/0)
641
642#define STAILQ_FOREACH(var, head, field) \
643 for ((var) = ((head)->stqh_first); \
644 (var); \
645 (var) = ((var)->field.stqe_next))
646
647#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
648 for ((var) = STAILQ_FIRST((head)); \
649 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
650 (var) = (tvar))
651
652#define STAILQ_CONCAT(head1, head2) do { \
653 if (!STAILQ_EMPTY((head2))) { \
654 *(head1)->stqh_last = (head2)->stqh_first; \
655 (head1)->stqh_last = (head2)->stqh_last; \
656 STAILQ_INIT((head2)); \
657 } \
658} while (/*CONSTCOND*/0)
659
660#define STAILQ_LAST(head, type, field) \
661 (STAILQ_EMPTY((head)) ? \
662 NULL : \
663 ((struct type *)(void *) \
664 ((char *)((head)->stqh_last) - offsetof(struct type, field))))
665
666
667#ifndef _KERNEL
668/*
669 * Circular queue definitions. Do not use. We still keep the macros
670 * for compatibility but because of pointer aliasing issues their use
671 * is discouraged!
672 */
673
674/*
675 * __launder_type(): We use this ugly hack to work around the compiler
676 * noticing that two types may not alias each other and elide tests in code.
677 * We hit this in the CIRCLEQ macros when comparing 'struct name *' and
678 * 'struct type *' (see CIRCLEQ_HEAD()). Modern compilers (such as GCC
679 * 4.8) declare these comparisons as always false, causing the code to
680 * not run as designed.
681 *
682 * This hack is only to be used for comparisons and thus can be fully const.
683 * Do not use for assignment.
684 *
685 * If we ever choose to change the ABI of the CIRCLEQ macros, we could fix
686 * this by changing the head/tail sentinal values, but see the note above
687 * this one.
688 */
689static __inline const void * __launder_type(const void *);
690static __inline const void *
691__launder_type(const void *__x)
692{
693 __asm __volatile("" : "+r" (__x));
694 return __x;
695}
696
697#if defined(QUEUEDEBUG)
698#define QUEUEDEBUG_CIRCLEQ_HEAD(head, field) \
699 if ((head)->cqh_first != CIRCLEQ_ENDC(head) && \
700 (head)->cqh_first->field.cqe_prev != CIRCLEQ_ENDC(head)) \
701 QUEUEDEBUG_ABORT("CIRCLEQ head forw %p %s:%d", (head), \
702 __FILE__, __LINE__); \
703 if ((head)->cqh_last != CIRCLEQ_ENDC(head) && \
704 (head)->cqh_last->field.cqe_next != CIRCLEQ_ENDC(head)) \
705 QUEUEDEBUG_ABORT("CIRCLEQ head back %p %s:%d", (head), \
706 __FILE__, __LINE__);
707#define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field) \
708 if ((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) { \
709 if ((head)->cqh_last != (elm)) \
710 QUEUEDEBUG_ABORT("CIRCLEQ elm last %p %s:%d", \
711 (elm), __FILE__, __LINE__); \
712 } else { \
713 if ((elm)->field.cqe_next->field.cqe_prev != (elm)) \
714 QUEUEDEBUG_ABORT("CIRCLEQ elm forw %p %s:%d", \
715 (elm), __FILE__, __LINE__); \
716 } \
717 if ((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) { \
718 if ((head)->cqh_first != (elm)) \
719 QUEUEDEBUG_ABORT("CIRCLEQ elm first %p %s:%d", \
720 (elm), __FILE__, __LINE__); \
721 } else { \
722 if ((elm)->field.cqe_prev->field.cqe_next != (elm)) \
723 QUEUEDEBUG_ABORT("CIRCLEQ elm prev %p %s:%d", \
724 (elm), __FILE__, __LINE__); \
725 }
726#define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field) \
727 (elm)->field.cqe_next = (void *)1L; \
728 (elm)->field.cqe_prev = (void *)1L;
729#else
730#define QUEUEDEBUG_CIRCLEQ_HEAD(head, field)
731#define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field)
732#define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field)
733#endif
734
735#define CIRCLEQ_HEAD(name, type) \
736struct name { \
737 struct type *cqh_first; /* first element */ \
738 struct type *cqh_last; /* last element */ \
739}
740
741#define CIRCLEQ_HEAD_INITIALIZER(head) \
742 { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
743
744#define CIRCLEQ_ENTRY(type) \
745struct { \
746 struct type *cqe_next; /* next element */ \
747 struct type *cqe_prev; /* previous element */ \
748}
749
750/*
751 * Circular queue functions.
752 */
753#define CIRCLEQ_INIT(head) do { \
754 (head)->cqh_first = CIRCLEQ_END(head); \
755 (head)->cqh_last = CIRCLEQ_END(head); \
756} while (/*CONSTCOND*/0)
757
758#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
759 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
760 QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \
761 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
762 (elm)->field.cqe_prev = (listelm); \
763 if ((listelm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
764 (head)->cqh_last = (elm); \
765 else \
766 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
767 (listelm)->field.cqe_next = (elm); \
768} while (/*CONSTCOND*/0)
769
770#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
771 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
772 QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \
773 (elm)->field.cqe_next = (listelm); \
774 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
775 if ((listelm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
776 (head)->cqh_first = (elm); \
777 else \
778 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
779 (listelm)->field.cqe_prev = (elm); \
780} while (/*CONSTCOND*/0)
781
782#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
783 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
784 (elm)->field.cqe_next = (head)->cqh_first; \
785 (elm)->field.cqe_prev = CIRCLEQ_END(head); \
786 if ((head)->cqh_last == CIRCLEQ_ENDC(head)) \
787 (head)->cqh_last = (elm); \
788 else \
789 (head)->cqh_first->field.cqe_prev = (elm); \
790 (head)->cqh_first = (elm); \
791} while (/*CONSTCOND*/0)
792
793#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
794 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
795 (elm)->field.cqe_next = CIRCLEQ_END(head); \
796 (elm)->field.cqe_prev = (head)->cqh_last; \
797 if ((head)->cqh_first == CIRCLEQ_ENDC(head)) \
798 (head)->cqh_first = (elm); \
799 else \
800 (head)->cqh_last->field.cqe_next = (elm); \
801 (head)->cqh_last = (elm); \
802} while (/*CONSTCOND*/0)
803
804#define CIRCLEQ_REMOVE(head, elm, field) do { \
805 QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \
806 QUEUEDEBUG_CIRCLEQ_ELM((head), (elm), field) \
807 if ((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
808 (head)->cqh_last = (elm)->field.cqe_prev; \
809 else \
810 (elm)->field.cqe_next->field.cqe_prev = \
811 (elm)->field.cqe_prev; \
812 if ((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
813 (head)->cqh_first = (elm)->field.cqe_next; \
814 else \
815 (elm)->field.cqe_prev->field.cqe_next = \
816 (elm)->field.cqe_next; \
817 QUEUEDEBUG_CIRCLEQ_POSTREMOVE((elm), field) \
818} while (/*CONSTCOND*/0)
819
820#define CIRCLEQ_FOREACH(var, head, field) \
821 for ((var) = ((head)->cqh_first); \
822 (var) != CIRCLEQ_ENDC(head); \
823 (var) = ((var)->field.cqe_next))
824
825#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
826 for ((var) = ((head)->cqh_last); \
827 (var) != CIRCLEQ_ENDC(head); \
828 (var) = ((var)->field.cqe_prev))
829
830/*
831 * Circular queue access methods.
832 */
833#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
834#define CIRCLEQ_LAST(head) ((head)->cqh_last)
835/* For comparisons */
836#define CIRCLEQ_ENDC(head) (__launder_type(head))
837/* For assignments */
838#define CIRCLEQ_END(head) ((void *)(head))
839#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
840#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
841#define CIRCLEQ_EMPTY(head) \
842 (CIRCLEQ_FIRST(head) == CIRCLEQ_ENDC(head))
843
844#define CIRCLEQ_LOOP_NEXT(head, elm, field) \
845 (((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) \
846 ? ((head)->cqh_first) \
847 : (elm->field.cqe_next))
848#define CIRCLEQ_LOOP_PREV(head, elm, field) \
849 (((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \
850 ? ((head)->cqh_last) \
851 : (elm->field.cqe_prev))
852#endif /* !_KERNEL */
853
854#endif /* !_SYS_QUEUE_H_ */
855