1 /* $OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $ */
2 /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
5 * Copyright (c) 1991, 1993
6 * The Regents of the University of California. All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
32 * @(#)queue.h 8.5 (Berkeley) 8/20/94
35 /* OPENBSD ORIGINAL: sys/sys/queue.h */
37 #ifndef _FAKE_QUEUE_H_
38 #define _FAKE_QUEUE_H_
41 * Require for OS/X and other platforms that have old/broken/incomplete
48 #undef CIRCLEQ_FOREACH
49 #undef CIRCLEQ_FOREACH_REVERSE
51 #undef CIRCLEQ_HEAD_INITIALIZER
53 #undef CIRCLEQ_INSERT_AFTER
54 #undef CIRCLEQ_INSERT_BEFORE
55 #undef CIRCLEQ_INSERT_HEAD
56 #undef CIRCLEQ_INSERT_TAIL
61 #undef CIRCLEQ_REPLACE
67 #undef LIST_FOREACH_SAFE
69 #undef LIST_HEAD_INITIALIZER
71 #undef LIST_INSERT_AFTER
72 #undef LIST_INSERT_BEFORE
73 #undef LIST_INSERT_HEAD
82 #undef SIMPLEQ_FOREACH
83 #undef SIMPLEQ_FOREACH_SAFE
85 #undef SIMPLEQ_HEAD_INITIALIZER
87 #undef SIMPLEQ_INSERT_AFTER
88 #undef SIMPLEQ_INSERT_HEAD
89 #undef SIMPLEQ_INSERT_TAIL
91 #undef SIMPLEQ_REMOVE_AFTER
92 #undef SIMPLEQ_REMOVE_HEAD
98 #undef SLIST_FOREACH_PREVPTR
99 #undef SLIST_FOREACH_SAFE
101 #undef SLIST_HEAD_INITIALIZER
103 #undef SLIST_INSERT_AFTER
104 #undef SLIST_INSERT_HEAD
107 #undef SLIST_REMOVE_AFTER
108 #undef SLIST_REMOVE_HEAD
109 #undef SLIST_REMOVE_NEXT
116 #undef TAILQ_FOREACH_REVERSE
117 #undef TAILQ_FOREACH_REVERSE_SAFE
118 #undef TAILQ_FOREACH_SAFE
120 #undef TAILQ_HEAD_INITIALIZER
122 #undef TAILQ_INSERT_AFTER
123 #undef TAILQ_INSERT_BEFORE
124 #undef TAILQ_INSERT_HEAD
125 #undef TAILQ_INSERT_TAIL
133 * This file defines five types of data structures: singly-linked lists,
134 * lists, simple queues, tail queues and XOR simple queues.
137 * A singly-linked list is headed by a single forward pointer. The elements
138 * are singly linked for minimum space and pointer manipulation overhead at
139 * the expense of O(n) removal for arbitrary elements. New elements can be
140 * added to the list after an existing element or at the head of the list.
141 * Elements being removed from the head of the list should use the explicit
142 * macro for this purpose for optimum efficiency. A singly-linked list may
143 * only be traversed in the forward direction. Singly-linked lists are ideal
144 * for applications with large datasets and few or no removals or for
145 * implementing a LIFO queue.
147 * A list is headed by a single forward pointer (or an array of forward
148 * pointers for a hash table header). The elements are doubly linked
149 * so that an arbitrary element can be removed without a need to
150 * traverse the list. New elements can be added to the list before
151 * or after an existing element or at the head of the list. A list
152 * may only be traversed in the forward direction.
154 * A simple queue is headed by a pair of pointers, one to the head of the
155 * list and the other to the tail of the list. The elements are singly
156 * linked to save space, so elements can only be removed from the
157 * head of the list. New elements can be added to the list before or after
158 * an existing element, at the head of the list, or at the end of the
159 * list. A simple queue may only be traversed in the forward direction.
161 * A tail queue is headed by a pair of pointers, one to the head of the
162 * list and the other to the tail of the list. The elements are doubly
163 * linked so that an arbitrary element can be removed without a need to
164 * traverse the list. New elements can be added to the list before or
165 * after an existing element, at the head of the list, or at the end of
166 * the list. A tail queue may be traversed in either direction.
168 * An XOR simple queue is used in the same way as a regular simple queue.
169 * The difference is that the head structure also includes a "cookie" that
170 * is XOR'd with the queue pointer (first, last or next) to generate the
171 * real pointer value.
173 * For details on the use of these macros, see the queue(3) manual page.
176 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
177 #define _Q_INVALID ((void *)-1)
178 #define _Q_INVALIDATE(a) (a) = _Q_INVALID
180 #define _Q_INVALIDATE(a)
184 * Singly-linked List definitions.
186 #define SLIST_HEAD(name, type) \
188 struct type *slh_first; /* first element */ \
191 #define SLIST_HEAD_INITIALIZER(head) \
194 #define SLIST_ENTRY(type) \
196 struct type *sle_next; /* next element */ \
200 * Singly-linked List access methods.
202 #define SLIST_FIRST(head) ((head)->slh_first)
203 #define SLIST_END(head) NULL
204 #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
205 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
207 #define SLIST_FOREACH(var, head, field) \
208 for((var) = SLIST_FIRST(head); \
209 (var) != SLIST_END(head); \
210 (var) = SLIST_NEXT(var, field))
212 #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
213 for ((var) = SLIST_FIRST(head); \
214 (var) && ((tvar) = SLIST_NEXT(var, field), 1); \
218 * Singly-linked List functions.
220 #define SLIST_INIT(head) { \
221 SLIST_FIRST(head) = SLIST_END(head); \
224 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
225 (elm)->field.sle_next = (slistelm)->field.sle_next; \
226 (slistelm)->field.sle_next = (elm); \
229 #define SLIST_INSERT_HEAD(head, elm, field) do { \
230 (elm)->field.sle_next = (head)->slh_first; \
231 (head)->slh_first = (elm); \
234 #define SLIST_REMOVE_AFTER(elm, field) do { \
235 (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
238 #define SLIST_REMOVE_HEAD(head, field) do { \
239 (head)->slh_first = (head)->slh_first->field.sle_next; \
242 #define SLIST_REMOVE(head, elm, type, field) do { \
243 if ((head)->slh_first == (elm)) { \
244 SLIST_REMOVE_HEAD((head), field); \
246 struct type *curelm = (head)->slh_first; \
248 while (curelm->field.sle_next != (elm)) \
249 curelm = curelm->field.sle_next; \
250 curelm->field.sle_next = \
251 curelm->field.sle_next->field.sle_next; \
253 _Q_INVALIDATE((elm)->field.sle_next); \
259 #define LIST_HEAD(name, type) \
261 struct type *lh_first; /* first element */ \
264 #define LIST_HEAD_INITIALIZER(head) \
267 #define LIST_ENTRY(type) \
269 struct type *le_next; /* next element */ \
270 struct type **le_prev; /* address of previous next element */ \
274 * List access methods.
276 #define LIST_FIRST(head) ((head)->lh_first)
277 #define LIST_END(head) NULL
278 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
279 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
281 #define LIST_FOREACH(var, head, field) \
282 for((var) = LIST_FIRST(head); \
283 (var)!= LIST_END(head); \
284 (var) = LIST_NEXT(var, field))
286 #define LIST_FOREACH_SAFE(var, head, field, tvar) \
287 for ((var) = LIST_FIRST(head); \
288 (var) && ((tvar) = LIST_NEXT(var, field), 1); \
294 #define LIST_INIT(head) do { \
295 LIST_FIRST(head) = LIST_END(head); \
298 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
299 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
300 (listelm)->field.le_next->field.le_prev = \
301 &(elm)->field.le_next; \
302 (listelm)->field.le_next = (elm); \
303 (elm)->field.le_prev = &(listelm)->field.le_next; \
306 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
307 (elm)->field.le_prev = (listelm)->field.le_prev; \
308 (elm)->field.le_next = (listelm); \
309 *(listelm)->field.le_prev = (elm); \
310 (listelm)->field.le_prev = &(elm)->field.le_next; \
313 #define LIST_INSERT_HEAD(head, elm, field) do { \
314 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
315 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
316 (head)->lh_first = (elm); \
317 (elm)->field.le_prev = &(head)->lh_first; \
320 #define LIST_REMOVE(elm, field) do { \
321 if ((elm)->field.le_next != NULL) \
322 (elm)->field.le_next->field.le_prev = \
323 (elm)->field.le_prev; \
324 *(elm)->field.le_prev = (elm)->field.le_next; \
325 _Q_INVALIDATE((elm)->field.le_prev); \
326 _Q_INVALIDATE((elm)->field.le_next); \
329 #define LIST_REPLACE(elm, elm2, field) do { \
330 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
331 (elm2)->field.le_next->field.le_prev = \
332 &(elm2)->field.le_next; \
333 (elm2)->field.le_prev = (elm)->field.le_prev; \
334 *(elm2)->field.le_prev = (elm2); \
335 _Q_INVALIDATE((elm)->field.le_prev); \
336 _Q_INVALIDATE((elm)->field.le_next); \
340 * Simple queue definitions.
342 #define SIMPLEQ_HEAD(name, type) \
344 struct type *sqh_first; /* first element */ \
345 struct type **sqh_last; /* addr of last next element */ \
348 #define SIMPLEQ_HEAD_INITIALIZER(head) \
349 { NULL, &(head).sqh_first }
351 #define SIMPLEQ_ENTRY(type) \
353 struct type *sqe_next; /* next element */ \
357 * Simple queue access methods.
359 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
360 #define SIMPLEQ_END(head) NULL
361 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
362 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
364 #define SIMPLEQ_FOREACH(var, head, field) \
365 for((var) = SIMPLEQ_FIRST(head); \
366 (var) != SIMPLEQ_END(head); \
367 (var) = SIMPLEQ_NEXT(var, field))
369 #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
370 for ((var) = SIMPLEQ_FIRST(head); \
371 (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \
375 * Simple queue functions.
377 #define SIMPLEQ_INIT(head) do { \
378 (head)->sqh_first = NULL; \
379 (head)->sqh_last = &(head)->sqh_first; \
382 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
383 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
384 (head)->sqh_last = &(elm)->field.sqe_next; \
385 (head)->sqh_first = (elm); \
388 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
389 (elm)->field.sqe_next = NULL; \
390 *(head)->sqh_last = (elm); \
391 (head)->sqh_last = &(elm)->field.sqe_next; \
394 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
395 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
396 (head)->sqh_last = &(elm)->field.sqe_next; \
397 (listelm)->field.sqe_next = (elm); \
400 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
401 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
402 (head)->sqh_last = &(head)->sqh_first; \
405 #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
406 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
408 (head)->sqh_last = &(elm)->field.sqe_next; \
411 #define SIMPLEQ_CONCAT(head1, head2) do { \
412 if (!SIMPLEQ_EMPTY((head2))) { \
413 *(head1)->sqh_last = (head2)->sqh_first; \
414 (head1)->sqh_last = (head2)->sqh_last; \
415 SIMPLEQ_INIT((head2)); \
420 * XOR Simple queue definitions.
422 #define XSIMPLEQ_HEAD(name, type) \
424 struct type *sqx_first; /* first element */ \
425 struct type **sqx_last; /* addr of last next element */ \
426 unsigned long sqx_cookie; \
429 #define XSIMPLEQ_ENTRY(type) \
431 struct type *sqx_next; /* next element */ \
435 * XOR Simple queue access methods.
437 #define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \
438 (unsigned long)(ptr)))
439 #define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
440 #define XSIMPLEQ_END(head) NULL
441 #define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
442 #define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
445 #define XSIMPLEQ_FOREACH(var, head, field) \
446 for ((var) = XSIMPLEQ_FIRST(head); \
447 (var) != XSIMPLEQ_END(head); \
448 (var) = XSIMPLEQ_NEXT(head, var, field))
450 #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
451 for ((var) = XSIMPLEQ_FIRST(head); \
452 (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
456 * XOR Simple queue functions.
458 #define XSIMPLEQ_INIT(head) do { \
459 arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
460 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
461 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
464 #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
465 if (((elm)->field.sqx_next = (head)->sqx_first) == \
466 XSIMPLEQ_XOR(head, NULL)) \
467 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
468 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
471 #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
472 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
473 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
474 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
477 #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
478 if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \
479 XSIMPLEQ_XOR(head, NULL)) \
480 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
481 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
484 #define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
485 if (((head)->sqx_first = XSIMPLEQ_XOR(head, \
486 (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
487 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
490 #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
491 if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
492 (elm)->field.sqx_next)->field.sqx_next) \
493 == XSIMPLEQ_XOR(head, NULL)) \
495 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
500 * Tail queue definitions.
502 #define TAILQ_HEAD(name, type) \
504 struct type *tqh_first; /* first element */ \
505 struct type **tqh_last; /* addr of last next element */ \
508 #define TAILQ_HEAD_INITIALIZER(head) \
509 { NULL, &(head).tqh_first }
511 #define TAILQ_ENTRY(type) \
513 struct type *tqe_next; /* next element */ \
514 struct type **tqe_prev; /* address of previous next element */ \
518 * Tail queue access methods.
520 #define TAILQ_FIRST(head) ((head)->tqh_first)
521 #define TAILQ_END(head) NULL
522 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
523 #define TAILQ_LAST(head, headname) \
524 (*(((struct headname *)((head)->tqh_last))->tqh_last))
526 #define TAILQ_PREV(elm, headname, field) \
527 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
528 #define TAILQ_EMPTY(head) \
529 (TAILQ_FIRST(head) == TAILQ_END(head))
531 #define TAILQ_FOREACH(var, head, field) \
532 for((var) = TAILQ_FIRST(head); \
533 (var) != TAILQ_END(head); \
534 (var) = TAILQ_NEXT(var, field))
536 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
537 for ((var) = TAILQ_FIRST(head); \
538 (var) != TAILQ_END(head) && \
539 ((tvar) = TAILQ_NEXT(var, field), 1); \
543 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
544 for((var) = TAILQ_LAST(head, headname); \
545 (var) != TAILQ_END(head); \
546 (var) = TAILQ_PREV(var, headname, field))
548 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
549 for ((var) = TAILQ_LAST(head, headname); \
550 (var) != TAILQ_END(head) && \
551 ((tvar) = TAILQ_PREV(var, headname, field), 1); \
555 * Tail queue functions.
557 #define TAILQ_INIT(head) do { \
558 (head)->tqh_first = NULL; \
559 (head)->tqh_last = &(head)->tqh_first; \
562 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
563 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
564 (head)->tqh_first->field.tqe_prev = \
565 &(elm)->field.tqe_next; \
567 (head)->tqh_last = &(elm)->field.tqe_next; \
568 (head)->tqh_first = (elm); \
569 (elm)->field.tqe_prev = &(head)->tqh_first; \
572 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
573 (elm)->field.tqe_next = NULL; \
574 (elm)->field.tqe_prev = (head)->tqh_last; \
575 *(head)->tqh_last = (elm); \
576 (head)->tqh_last = &(elm)->field.tqe_next; \
579 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
580 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
581 (elm)->field.tqe_next->field.tqe_prev = \
582 &(elm)->field.tqe_next; \
584 (head)->tqh_last = &(elm)->field.tqe_next; \
585 (listelm)->field.tqe_next = (elm); \
586 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
589 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
590 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
591 (elm)->field.tqe_next = (listelm); \
592 *(listelm)->field.tqe_prev = (elm); \
593 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
596 #define TAILQ_REMOVE(head, elm, field) do { \
597 if (((elm)->field.tqe_next) != NULL) \
598 (elm)->field.tqe_next->field.tqe_prev = \
599 (elm)->field.tqe_prev; \
601 (head)->tqh_last = (elm)->field.tqe_prev; \
602 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
603 _Q_INVALIDATE((elm)->field.tqe_prev); \
604 _Q_INVALIDATE((elm)->field.tqe_next); \
607 #define TAILQ_REPLACE(head, elm, elm2, field) do { \
608 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
609 (elm2)->field.tqe_next->field.tqe_prev = \
610 &(elm2)->field.tqe_next; \
612 (head)->tqh_last = &(elm2)->field.tqe_next; \
613 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
614 *(elm2)->field.tqe_prev = (elm2); \
615 _Q_INVALIDATE((elm)->field.tqe_prev); \
616 _Q_INVALIDATE((elm)->field.tqe_next); \
619 #define TAILQ_CONCAT(head1, head2, field) do { \
620 if (!TAILQ_EMPTY(head2)) { \
621 *(head1)->tqh_last = (head2)->tqh_first; \
622 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
623 (head1)->tqh_last = (head2)->tqh_last; \
624 TAILQ_INIT((head2)); \
628 #endif /* !_SYS_QUEUE_H_ */