1*2c81fb9cSAntonio Huete Jimenez /* $OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $ */ 22c0338ffSzrj /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ 32c0338ffSzrj 42c0338ffSzrj /* 52c0338ffSzrj * Copyright (c) 1991, 1993 62c0338ffSzrj * The Regents of the University of California. All rights reserved. 72c0338ffSzrj * 82c0338ffSzrj * Redistribution and use in source and binary forms, with or without 92c0338ffSzrj * modification, are permitted provided that the following conditions 102c0338ffSzrj * are met: 112c0338ffSzrj * 1. Redistributions of source code must retain the above copyright 122c0338ffSzrj * notice, this list of conditions and the following disclaimer. 132c0338ffSzrj * 2. Redistributions in binary form must reproduce the above copyright 142c0338ffSzrj * notice, this list of conditions and the following disclaimer in the 152c0338ffSzrj * documentation and/or other materials provided with the distribution. 162c0338ffSzrj * 3. Neither the name of the University nor the names of its contributors 172c0338ffSzrj * may be used to endorse or promote products derived from this software 182c0338ffSzrj * without specific prior written permission. 192c0338ffSzrj * 202c0338ffSzrj * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 212c0338ffSzrj * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 222c0338ffSzrj * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 232c0338ffSzrj * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 242c0338ffSzrj * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 252c0338ffSzrj * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 262c0338ffSzrj * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 272c0338ffSzrj * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 282c0338ffSzrj * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 292c0338ffSzrj * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 302c0338ffSzrj * SUCH DAMAGE. 312c0338ffSzrj * 322c0338ffSzrj * @(#)queue.h 8.5 (Berkeley) 8/20/94 332c0338ffSzrj */ 342c0338ffSzrj 352c0338ffSzrj /* OPENBSD ORIGINAL: sys/sys/queue.h */ 362c0338ffSzrj 372c0338ffSzrj #ifndef _FAKE_QUEUE_H_ 382c0338ffSzrj #define _FAKE_QUEUE_H_ 392c0338ffSzrj 402c0338ffSzrj /* 412c0338ffSzrj * Require for OS/X and other platforms that have old/broken/incomplete 422c0338ffSzrj * <sys/queue.h>. 432c0338ffSzrj */ 44*2c81fb9cSAntonio Huete Jimenez #undef CIRCLEQ_EMPTY 45*2c81fb9cSAntonio Huete Jimenez #undef CIRCLEQ_END 462c0338ffSzrj #undef CIRCLEQ_ENTRY 472c0338ffSzrj #undef CIRCLEQ_FIRST 482c0338ffSzrj #undef CIRCLEQ_FOREACH 492c0338ffSzrj #undef CIRCLEQ_FOREACH_REVERSE 50*2c81fb9cSAntonio Huete Jimenez #undef CIRCLEQ_HEAD 51*2c81fb9cSAntonio Huete Jimenez #undef CIRCLEQ_HEAD_INITIALIZER 522c0338ffSzrj #undef CIRCLEQ_INIT 532c0338ffSzrj #undef CIRCLEQ_INSERT_AFTER 542c0338ffSzrj #undef CIRCLEQ_INSERT_BEFORE 552c0338ffSzrj #undef CIRCLEQ_INSERT_HEAD 562c0338ffSzrj #undef CIRCLEQ_INSERT_TAIL 57*2c81fb9cSAntonio Huete Jimenez #undef CIRCLEQ_LAST 58*2c81fb9cSAntonio Huete Jimenez #undef CIRCLEQ_NEXT 59*2c81fb9cSAntonio Huete Jimenez #undef CIRCLEQ_PREV 602c0338ffSzrj #undef CIRCLEQ_REMOVE 612c0338ffSzrj #undef CIRCLEQ_REPLACE 62*2c81fb9cSAntonio Huete Jimenez #undef LIST_EMPTY 63*2c81fb9cSAntonio Huete Jimenez #undef LIST_END 64*2c81fb9cSAntonio Huete Jimenez #undef LIST_ENTRY 65*2c81fb9cSAntonio Huete Jimenez #undef LIST_FIRST 66*2c81fb9cSAntonio Huete Jimenez #undef LIST_FOREACH 67*2c81fb9cSAntonio Huete Jimenez #undef LIST_FOREACH_SAFE 68*2c81fb9cSAntonio Huete Jimenez #undef LIST_HEAD 69*2c81fb9cSAntonio Huete Jimenez #undef LIST_HEAD_INITIALIZER 70*2c81fb9cSAntonio Huete Jimenez #undef LIST_INIT 71*2c81fb9cSAntonio Huete Jimenez #undef LIST_INSERT_AFTER 72*2c81fb9cSAntonio Huete Jimenez #undef LIST_INSERT_BEFORE 73*2c81fb9cSAntonio Huete Jimenez #undef LIST_INSERT_HEAD 74*2c81fb9cSAntonio Huete Jimenez #undef LIST_NEXT 75*2c81fb9cSAntonio Huete Jimenez #undef LIST_REMOVE 76*2c81fb9cSAntonio Huete Jimenez #undef LIST_REPLACE 77*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_CONCAT 78*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_EMPTY 79*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_END 80*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_ENTRY 81*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_FIRST 82*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_FOREACH 83*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_FOREACH_SAFE 84*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_HEAD 85*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_HEAD_INITIALIZER 86*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_INIT 87*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_INSERT_AFTER 88*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_INSERT_HEAD 89*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_INSERT_TAIL 90*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_NEXT 91*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_REMOVE_AFTER 92*2c81fb9cSAntonio Huete Jimenez #undef SIMPLEQ_REMOVE_HEAD 93*2c81fb9cSAntonio Huete Jimenez #undef SLIST_EMPTY 94*2c81fb9cSAntonio Huete Jimenez #undef SLIST_END 95*2c81fb9cSAntonio Huete Jimenez #undef SLIST_ENTRY 96*2c81fb9cSAntonio Huete Jimenez #undef SLIST_FIRST 97*2c81fb9cSAntonio Huete Jimenez #undef SLIST_FOREACH 98*2c81fb9cSAntonio Huete Jimenez #undef SLIST_FOREACH_PREVPTR 99*2c81fb9cSAntonio Huete Jimenez #undef SLIST_FOREACH_SAFE 100*2c81fb9cSAntonio Huete Jimenez #undef SLIST_HEAD 101*2c81fb9cSAntonio Huete Jimenez #undef SLIST_HEAD_INITIALIZER 102*2c81fb9cSAntonio Huete Jimenez #undef SLIST_INIT 103*2c81fb9cSAntonio Huete Jimenez #undef SLIST_INSERT_AFTER 104*2c81fb9cSAntonio Huete Jimenez #undef SLIST_INSERT_HEAD 105*2c81fb9cSAntonio Huete Jimenez #undef SLIST_NEXT 106*2c81fb9cSAntonio Huete Jimenez #undef SLIST_REMOVE 107*2c81fb9cSAntonio Huete Jimenez #undef SLIST_REMOVE_AFTER 108*2c81fb9cSAntonio Huete Jimenez #undef SLIST_REMOVE_HEAD 109*2c81fb9cSAntonio Huete Jimenez #undef SLIST_REMOVE_NEXT 110*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_CONCAT 111*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_EMPTY 112*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_END 113*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_ENTRY 114*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_FIRST 115*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_FOREACH 116*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_FOREACH_REVERSE 117*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_FOREACH_REVERSE_SAFE 118*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_FOREACH_SAFE 119*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_HEAD 120*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_HEAD_INITIALIZER 121*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_INIT 122*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_INSERT_AFTER 123*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_INSERT_BEFORE 124*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_INSERT_HEAD 125*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_INSERT_TAIL 126*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_LAST 127*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_NEXT 128*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_PREV 129*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_REMOVE 130*2c81fb9cSAntonio Huete Jimenez #undef TAILQ_REPLACE 1312c0338ffSzrj 1322c0338ffSzrj /* 1332c0338ffSzrj * This file defines five types of data structures: singly-linked lists, 134*2c81fb9cSAntonio Huete Jimenez * lists, simple queues, tail queues and XOR simple queues. 1352c0338ffSzrj * 1362c0338ffSzrj * 1372c0338ffSzrj * A singly-linked list is headed by a single forward pointer. The elements 1382c0338ffSzrj * are singly linked for minimum space and pointer manipulation overhead at 1392c0338ffSzrj * the expense of O(n) removal for arbitrary elements. New elements can be 1402c0338ffSzrj * added to the list after an existing element or at the head of the list. 1412c0338ffSzrj * Elements being removed from the head of the list should use the explicit 1422c0338ffSzrj * macro for this purpose for optimum efficiency. A singly-linked list may 1432c0338ffSzrj * only be traversed in the forward direction. Singly-linked lists are ideal 1442c0338ffSzrj * for applications with large datasets and few or no removals or for 1452c0338ffSzrj * implementing a LIFO queue. 1462c0338ffSzrj * 1472c0338ffSzrj * A list is headed by a single forward pointer (or an array of forward 1482c0338ffSzrj * pointers for a hash table header). The elements are doubly linked 1492c0338ffSzrj * so that an arbitrary element can be removed without a need to 1502c0338ffSzrj * traverse the list. New elements can be added to the list before 1512c0338ffSzrj * or after an existing element or at the head of the list. A list 1522c0338ffSzrj * may only be traversed in the forward direction. 1532c0338ffSzrj * 154*2c81fb9cSAntonio Huete Jimenez * A simple queue is headed by a pair of pointers, one to the head of the 1552c0338ffSzrj * list and the other to the tail of the list. The elements are singly 1562c0338ffSzrj * linked to save space, so elements can only be removed from the 1572c0338ffSzrj * head of the list. New elements can be added to the list before or after 1582c0338ffSzrj * an existing element, at the head of the list, or at the end of the 1592c0338ffSzrj * list. A simple queue may only be traversed in the forward direction. 1602c0338ffSzrj * 1612c0338ffSzrj * A tail queue is headed by a pair of pointers, one to the head of the 1622c0338ffSzrj * list and the other to the tail of the list. The elements are doubly 1632c0338ffSzrj * linked so that an arbitrary element can be removed without a need to 1642c0338ffSzrj * traverse the list. New elements can be added to the list before or 1652c0338ffSzrj * after an existing element, at the head of the list, or at the end of 1662c0338ffSzrj * the list. A tail queue may be traversed in either direction. 1672c0338ffSzrj * 168*2c81fb9cSAntonio Huete Jimenez * An XOR simple queue is used in the same way as a regular simple queue. 169*2c81fb9cSAntonio Huete Jimenez * The difference is that the head structure also includes a "cookie" that 170*2c81fb9cSAntonio Huete Jimenez * is XOR'd with the queue pointer (first, last or next) to generate the 171*2c81fb9cSAntonio Huete Jimenez * real pointer value. 1722c0338ffSzrj * 1732c0338ffSzrj * For details on the use of these macros, see the queue(3) manual page. 1742c0338ffSzrj */ 1752c0338ffSzrj 1762c0338ffSzrj #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) 177*2c81fb9cSAntonio Huete Jimenez #define _Q_INVALID ((void *)-1) 178*2c81fb9cSAntonio Huete Jimenez #define _Q_INVALIDATE(a) (a) = _Q_INVALID 1792c0338ffSzrj #else 1802c0338ffSzrj #define _Q_INVALIDATE(a) 1812c0338ffSzrj #endif 1822c0338ffSzrj 1832c0338ffSzrj /* 1842c0338ffSzrj * Singly-linked List definitions. 1852c0338ffSzrj */ 1862c0338ffSzrj #define SLIST_HEAD(name, type) \ 1872c0338ffSzrj struct name { \ 1882c0338ffSzrj struct type *slh_first; /* first element */ \ 1892c0338ffSzrj } 1902c0338ffSzrj 1912c0338ffSzrj #define SLIST_HEAD_INITIALIZER(head) \ 1922c0338ffSzrj { NULL } 1932c0338ffSzrj 1942c0338ffSzrj #define SLIST_ENTRY(type) \ 1952c0338ffSzrj struct { \ 1962c0338ffSzrj struct type *sle_next; /* next element */ \ 1972c0338ffSzrj } 1982c0338ffSzrj 1992c0338ffSzrj /* 2002c0338ffSzrj * Singly-linked List access methods. 2012c0338ffSzrj */ 2022c0338ffSzrj #define SLIST_FIRST(head) ((head)->slh_first) 2032c0338ffSzrj #define SLIST_END(head) NULL 2042c0338ffSzrj #define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) 2052c0338ffSzrj #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 2062c0338ffSzrj 2072c0338ffSzrj #define SLIST_FOREACH(var, head, field) \ 2082c0338ffSzrj for((var) = SLIST_FIRST(head); \ 2092c0338ffSzrj (var) != SLIST_END(head); \ 2102c0338ffSzrj (var) = SLIST_NEXT(var, field)) 2112c0338ffSzrj 2122c0338ffSzrj #define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 2132c0338ffSzrj for ((var) = SLIST_FIRST(head); \ 2142c0338ffSzrj (var) && ((tvar) = SLIST_NEXT(var, field), 1); \ 2152c0338ffSzrj (var) = (tvar)) 2162c0338ffSzrj 2172c0338ffSzrj /* 2182c0338ffSzrj * Singly-linked List functions. 2192c0338ffSzrj */ 2202c0338ffSzrj #define SLIST_INIT(head) { \ 2212c0338ffSzrj SLIST_FIRST(head) = SLIST_END(head); \ 2222c0338ffSzrj } 2232c0338ffSzrj 2242c0338ffSzrj #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 2252c0338ffSzrj (elm)->field.sle_next = (slistelm)->field.sle_next; \ 2262c0338ffSzrj (slistelm)->field.sle_next = (elm); \ 2272c0338ffSzrj } while (0) 2282c0338ffSzrj 2292c0338ffSzrj #define SLIST_INSERT_HEAD(head, elm, field) do { \ 2302c0338ffSzrj (elm)->field.sle_next = (head)->slh_first; \ 2312c0338ffSzrj (head)->slh_first = (elm); \ 2322c0338ffSzrj } while (0) 2332c0338ffSzrj 2342c0338ffSzrj #define SLIST_REMOVE_AFTER(elm, field) do { \ 2352c0338ffSzrj (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \ 2362c0338ffSzrj } while (0) 2372c0338ffSzrj 2382c0338ffSzrj #define SLIST_REMOVE_HEAD(head, field) do { \ 2392c0338ffSzrj (head)->slh_first = (head)->slh_first->field.sle_next; \ 2402c0338ffSzrj } while (0) 2412c0338ffSzrj 2422c0338ffSzrj #define SLIST_REMOVE(head, elm, type, field) do { \ 2432c0338ffSzrj if ((head)->slh_first == (elm)) { \ 2442c0338ffSzrj SLIST_REMOVE_HEAD((head), field); \ 2452c0338ffSzrj } else { \ 2462c0338ffSzrj struct type *curelm = (head)->slh_first; \ 2472c0338ffSzrj \ 2482c0338ffSzrj while (curelm->field.sle_next != (elm)) \ 2492c0338ffSzrj curelm = curelm->field.sle_next; \ 2502c0338ffSzrj curelm->field.sle_next = \ 2512c0338ffSzrj curelm->field.sle_next->field.sle_next; \ 2522c0338ffSzrj } \ 253*2c81fb9cSAntonio Huete Jimenez _Q_INVALIDATE((elm)->field.sle_next); \ 2542c0338ffSzrj } while (0) 2552c0338ffSzrj 2562c0338ffSzrj /* 2572c0338ffSzrj * List definitions. 2582c0338ffSzrj */ 2592c0338ffSzrj #define LIST_HEAD(name, type) \ 2602c0338ffSzrj struct name { \ 2612c0338ffSzrj struct type *lh_first; /* first element */ \ 2622c0338ffSzrj } 2632c0338ffSzrj 2642c0338ffSzrj #define LIST_HEAD_INITIALIZER(head) \ 2652c0338ffSzrj { NULL } 2662c0338ffSzrj 2672c0338ffSzrj #define LIST_ENTRY(type) \ 2682c0338ffSzrj struct { \ 2692c0338ffSzrj struct type *le_next; /* next element */ \ 2702c0338ffSzrj struct type **le_prev; /* address of previous next element */ \ 2712c0338ffSzrj } 2722c0338ffSzrj 2732c0338ffSzrj /* 274*2c81fb9cSAntonio Huete Jimenez * List access methods. 2752c0338ffSzrj */ 2762c0338ffSzrj #define LIST_FIRST(head) ((head)->lh_first) 2772c0338ffSzrj #define LIST_END(head) NULL 2782c0338ffSzrj #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) 2792c0338ffSzrj #define LIST_NEXT(elm, field) ((elm)->field.le_next) 2802c0338ffSzrj 2812c0338ffSzrj #define LIST_FOREACH(var, head, field) \ 2822c0338ffSzrj for((var) = LIST_FIRST(head); \ 2832c0338ffSzrj (var)!= LIST_END(head); \ 2842c0338ffSzrj (var) = LIST_NEXT(var, field)) 2852c0338ffSzrj 2862c0338ffSzrj #define LIST_FOREACH_SAFE(var, head, field, tvar) \ 2872c0338ffSzrj for ((var) = LIST_FIRST(head); \ 2882c0338ffSzrj (var) && ((tvar) = LIST_NEXT(var, field), 1); \ 2892c0338ffSzrj (var) = (tvar)) 2902c0338ffSzrj 2912c0338ffSzrj /* 2922c0338ffSzrj * List functions. 2932c0338ffSzrj */ 2942c0338ffSzrj #define LIST_INIT(head) do { \ 2952c0338ffSzrj LIST_FIRST(head) = LIST_END(head); \ 2962c0338ffSzrj } while (0) 2972c0338ffSzrj 2982c0338ffSzrj #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 2992c0338ffSzrj if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 3002c0338ffSzrj (listelm)->field.le_next->field.le_prev = \ 3012c0338ffSzrj &(elm)->field.le_next; \ 3022c0338ffSzrj (listelm)->field.le_next = (elm); \ 3032c0338ffSzrj (elm)->field.le_prev = &(listelm)->field.le_next; \ 3042c0338ffSzrj } while (0) 3052c0338ffSzrj 3062c0338ffSzrj #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 3072c0338ffSzrj (elm)->field.le_prev = (listelm)->field.le_prev; \ 3082c0338ffSzrj (elm)->field.le_next = (listelm); \ 3092c0338ffSzrj *(listelm)->field.le_prev = (elm); \ 3102c0338ffSzrj (listelm)->field.le_prev = &(elm)->field.le_next; \ 3112c0338ffSzrj } while (0) 3122c0338ffSzrj 3132c0338ffSzrj #define LIST_INSERT_HEAD(head, elm, field) do { \ 3142c0338ffSzrj if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 3152c0338ffSzrj (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 3162c0338ffSzrj (head)->lh_first = (elm); \ 3172c0338ffSzrj (elm)->field.le_prev = &(head)->lh_first; \ 3182c0338ffSzrj } while (0) 3192c0338ffSzrj 3202c0338ffSzrj #define LIST_REMOVE(elm, field) do { \ 3212c0338ffSzrj if ((elm)->field.le_next != NULL) \ 3222c0338ffSzrj (elm)->field.le_next->field.le_prev = \ 3232c0338ffSzrj (elm)->field.le_prev; \ 3242c0338ffSzrj *(elm)->field.le_prev = (elm)->field.le_next; \ 3252c0338ffSzrj _Q_INVALIDATE((elm)->field.le_prev); \ 3262c0338ffSzrj _Q_INVALIDATE((elm)->field.le_next); \ 3272c0338ffSzrj } while (0) 3282c0338ffSzrj 3292c0338ffSzrj #define LIST_REPLACE(elm, elm2, field) do { \ 3302c0338ffSzrj if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ 3312c0338ffSzrj (elm2)->field.le_next->field.le_prev = \ 3322c0338ffSzrj &(elm2)->field.le_next; \ 3332c0338ffSzrj (elm2)->field.le_prev = (elm)->field.le_prev; \ 3342c0338ffSzrj *(elm2)->field.le_prev = (elm2); \ 3352c0338ffSzrj _Q_INVALIDATE((elm)->field.le_prev); \ 3362c0338ffSzrj _Q_INVALIDATE((elm)->field.le_next); \ 3372c0338ffSzrj } while (0) 3382c0338ffSzrj 3392c0338ffSzrj /* 3402c0338ffSzrj * Simple queue definitions. 3412c0338ffSzrj */ 3422c0338ffSzrj #define SIMPLEQ_HEAD(name, type) \ 3432c0338ffSzrj struct name { \ 3442c0338ffSzrj struct type *sqh_first; /* first element */ \ 3452c0338ffSzrj struct type **sqh_last; /* addr of last next element */ \ 3462c0338ffSzrj } 3472c0338ffSzrj 3482c0338ffSzrj #define SIMPLEQ_HEAD_INITIALIZER(head) \ 3492c0338ffSzrj { NULL, &(head).sqh_first } 3502c0338ffSzrj 3512c0338ffSzrj #define SIMPLEQ_ENTRY(type) \ 3522c0338ffSzrj struct { \ 3532c0338ffSzrj struct type *sqe_next; /* next element */ \ 3542c0338ffSzrj } 3552c0338ffSzrj 3562c0338ffSzrj /* 3572c0338ffSzrj * Simple queue access methods. 3582c0338ffSzrj */ 3592c0338ffSzrj #define SIMPLEQ_FIRST(head) ((head)->sqh_first) 3602c0338ffSzrj #define SIMPLEQ_END(head) NULL 3612c0338ffSzrj #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) 3622c0338ffSzrj #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 3632c0338ffSzrj 3642c0338ffSzrj #define SIMPLEQ_FOREACH(var, head, field) \ 3652c0338ffSzrj for((var) = SIMPLEQ_FIRST(head); \ 3662c0338ffSzrj (var) != SIMPLEQ_END(head); \ 3672c0338ffSzrj (var) = SIMPLEQ_NEXT(var, field)) 3682c0338ffSzrj 3692c0338ffSzrj #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ 3702c0338ffSzrj for ((var) = SIMPLEQ_FIRST(head); \ 3712c0338ffSzrj (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \ 3722c0338ffSzrj (var) = (tvar)) 3732c0338ffSzrj 3742c0338ffSzrj /* 3752c0338ffSzrj * Simple queue functions. 3762c0338ffSzrj */ 3772c0338ffSzrj #define SIMPLEQ_INIT(head) do { \ 3782c0338ffSzrj (head)->sqh_first = NULL; \ 3792c0338ffSzrj (head)->sqh_last = &(head)->sqh_first; \ 3802c0338ffSzrj } while (0) 3812c0338ffSzrj 3822c0338ffSzrj #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 3832c0338ffSzrj if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ 3842c0338ffSzrj (head)->sqh_last = &(elm)->field.sqe_next; \ 3852c0338ffSzrj (head)->sqh_first = (elm); \ 3862c0338ffSzrj } while (0) 3872c0338ffSzrj 3882c0338ffSzrj #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 3892c0338ffSzrj (elm)->field.sqe_next = NULL; \ 3902c0338ffSzrj *(head)->sqh_last = (elm); \ 3912c0338ffSzrj (head)->sqh_last = &(elm)->field.sqe_next; \ 3922c0338ffSzrj } while (0) 3932c0338ffSzrj 3942c0338ffSzrj #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 3952c0338ffSzrj if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ 3962c0338ffSzrj (head)->sqh_last = &(elm)->field.sqe_next; \ 3972c0338ffSzrj (listelm)->field.sqe_next = (elm); \ 3982c0338ffSzrj } while (0) 3992c0338ffSzrj 4002c0338ffSzrj #define SIMPLEQ_REMOVE_HEAD(head, field) do { \ 4012c0338ffSzrj if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ 4022c0338ffSzrj (head)->sqh_last = &(head)->sqh_first; \ 4032c0338ffSzrj } while (0) 4042c0338ffSzrj 4052c0338ffSzrj #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ 4062c0338ffSzrj if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \ 4072c0338ffSzrj == NULL) \ 4082c0338ffSzrj (head)->sqh_last = &(elm)->field.sqe_next; \ 4092c0338ffSzrj } while (0) 4102c0338ffSzrj 411*2c81fb9cSAntonio Huete Jimenez #define SIMPLEQ_CONCAT(head1, head2) do { \ 412*2c81fb9cSAntonio Huete Jimenez if (!SIMPLEQ_EMPTY((head2))) { \ 413*2c81fb9cSAntonio Huete Jimenez *(head1)->sqh_last = (head2)->sqh_first; \ 414*2c81fb9cSAntonio Huete Jimenez (head1)->sqh_last = (head2)->sqh_last; \ 415*2c81fb9cSAntonio Huete Jimenez SIMPLEQ_INIT((head2)); \ 416*2c81fb9cSAntonio Huete Jimenez } \ 417*2c81fb9cSAntonio Huete Jimenez } while (0) 418*2c81fb9cSAntonio Huete Jimenez 419*2c81fb9cSAntonio Huete Jimenez /* 420*2c81fb9cSAntonio Huete Jimenez * XOR Simple queue definitions. 421*2c81fb9cSAntonio Huete Jimenez */ 422*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_HEAD(name, type) \ 423*2c81fb9cSAntonio Huete Jimenez struct name { \ 424*2c81fb9cSAntonio Huete Jimenez struct type *sqx_first; /* first element */ \ 425*2c81fb9cSAntonio Huete Jimenez struct type **sqx_last; /* addr of last next element */ \ 426*2c81fb9cSAntonio Huete Jimenez unsigned long sqx_cookie; \ 427*2c81fb9cSAntonio Huete Jimenez } 428*2c81fb9cSAntonio Huete Jimenez 429*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_ENTRY(type) \ 430*2c81fb9cSAntonio Huete Jimenez struct { \ 431*2c81fb9cSAntonio Huete Jimenez struct type *sqx_next; /* next element */ \ 432*2c81fb9cSAntonio Huete Jimenez } 433*2c81fb9cSAntonio Huete Jimenez 434*2c81fb9cSAntonio Huete Jimenez /* 435*2c81fb9cSAntonio Huete Jimenez * XOR Simple queue access methods. 436*2c81fb9cSAntonio Huete Jimenez */ 437*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \ 438*2c81fb9cSAntonio Huete Jimenez (unsigned long)(ptr))) 439*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first)) 440*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_END(head) NULL 441*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head)) 442*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next)) 443*2c81fb9cSAntonio Huete Jimenez 444*2c81fb9cSAntonio Huete Jimenez 445*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_FOREACH(var, head, field) \ 446*2c81fb9cSAntonio Huete Jimenez for ((var) = XSIMPLEQ_FIRST(head); \ 447*2c81fb9cSAntonio Huete Jimenez (var) != XSIMPLEQ_END(head); \ 448*2c81fb9cSAntonio Huete Jimenez (var) = XSIMPLEQ_NEXT(head, var, field)) 449*2c81fb9cSAntonio Huete Jimenez 450*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ 451*2c81fb9cSAntonio Huete Jimenez for ((var) = XSIMPLEQ_FIRST(head); \ 452*2c81fb9cSAntonio Huete Jimenez (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \ 453*2c81fb9cSAntonio Huete Jimenez (var) = (tvar)) 454*2c81fb9cSAntonio Huete Jimenez 455*2c81fb9cSAntonio Huete Jimenez /* 456*2c81fb9cSAntonio Huete Jimenez * XOR Simple queue functions. 457*2c81fb9cSAntonio Huete Jimenez */ 458*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_INIT(head) do { \ 459*2c81fb9cSAntonio Huete Jimenez arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \ 460*2c81fb9cSAntonio Huete Jimenez (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \ 461*2c81fb9cSAntonio Huete Jimenez (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ 462*2c81fb9cSAntonio Huete Jimenez } while (0) 463*2c81fb9cSAntonio Huete Jimenez 464*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 465*2c81fb9cSAntonio Huete Jimenez if (((elm)->field.sqx_next = (head)->sqx_first) == \ 466*2c81fb9cSAntonio Huete Jimenez XSIMPLEQ_XOR(head, NULL)) \ 467*2c81fb9cSAntonio Huete Jimenez (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ 468*2c81fb9cSAntonio Huete Jimenez (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \ 469*2c81fb9cSAntonio Huete Jimenez } while (0) 470*2c81fb9cSAntonio Huete Jimenez 471*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 472*2c81fb9cSAntonio Huete Jimenez (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \ 473*2c81fb9cSAntonio Huete Jimenez *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \ 474*2c81fb9cSAntonio Huete Jimenez (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ 475*2c81fb9cSAntonio Huete Jimenez } while (0) 476*2c81fb9cSAntonio Huete Jimenez 477*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 478*2c81fb9cSAntonio Huete Jimenez if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \ 479*2c81fb9cSAntonio Huete Jimenez XSIMPLEQ_XOR(head, NULL)) \ 480*2c81fb9cSAntonio Huete Jimenez (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ 481*2c81fb9cSAntonio Huete Jimenez (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \ 482*2c81fb9cSAntonio Huete Jimenez } while (0) 483*2c81fb9cSAntonio Huete Jimenez 484*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_REMOVE_HEAD(head, field) do { \ 485*2c81fb9cSAntonio Huete Jimenez if (((head)->sqx_first = XSIMPLEQ_XOR(head, \ 486*2c81fb9cSAntonio Huete Jimenez (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \ 487*2c81fb9cSAntonio Huete Jimenez (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ 488*2c81fb9cSAntonio Huete Jimenez } while (0) 489*2c81fb9cSAntonio Huete Jimenez 490*2c81fb9cSAntonio Huete Jimenez #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ 491*2c81fb9cSAntonio Huete Jimenez if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \ 492*2c81fb9cSAntonio Huete Jimenez (elm)->field.sqx_next)->field.sqx_next) \ 493*2c81fb9cSAntonio Huete Jimenez == XSIMPLEQ_XOR(head, NULL)) \ 494*2c81fb9cSAntonio Huete Jimenez (head)->sqx_last = \ 495*2c81fb9cSAntonio Huete Jimenez XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ 496*2c81fb9cSAntonio Huete Jimenez } while (0) 497*2c81fb9cSAntonio Huete Jimenez 498*2c81fb9cSAntonio Huete Jimenez 4992c0338ffSzrj /* 5002c0338ffSzrj * Tail queue definitions. 5012c0338ffSzrj */ 5022c0338ffSzrj #define TAILQ_HEAD(name, type) \ 5032c0338ffSzrj struct name { \ 5042c0338ffSzrj struct type *tqh_first; /* first element */ \ 5052c0338ffSzrj struct type **tqh_last; /* addr of last next element */ \ 5062c0338ffSzrj } 5072c0338ffSzrj 5082c0338ffSzrj #define TAILQ_HEAD_INITIALIZER(head) \ 5092c0338ffSzrj { NULL, &(head).tqh_first } 5102c0338ffSzrj 5112c0338ffSzrj #define TAILQ_ENTRY(type) \ 5122c0338ffSzrj struct { \ 5132c0338ffSzrj struct type *tqe_next; /* next element */ \ 5142c0338ffSzrj struct type **tqe_prev; /* address of previous next element */ \ 5152c0338ffSzrj } 5162c0338ffSzrj 5172c0338ffSzrj /* 518*2c81fb9cSAntonio Huete Jimenez * Tail queue access methods. 5192c0338ffSzrj */ 5202c0338ffSzrj #define TAILQ_FIRST(head) ((head)->tqh_first) 5212c0338ffSzrj #define TAILQ_END(head) NULL 5222c0338ffSzrj #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 5232c0338ffSzrj #define TAILQ_LAST(head, headname) \ 5242c0338ffSzrj (*(((struct headname *)((head)->tqh_last))->tqh_last)) 5252c0338ffSzrj /* XXX */ 5262c0338ffSzrj #define TAILQ_PREV(elm, headname, field) \ 5272c0338ffSzrj (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 5282c0338ffSzrj #define TAILQ_EMPTY(head) \ 5292c0338ffSzrj (TAILQ_FIRST(head) == TAILQ_END(head)) 5302c0338ffSzrj 5312c0338ffSzrj #define TAILQ_FOREACH(var, head, field) \ 5322c0338ffSzrj for((var) = TAILQ_FIRST(head); \ 5332c0338ffSzrj (var) != TAILQ_END(head); \ 5342c0338ffSzrj (var) = TAILQ_NEXT(var, field)) 5352c0338ffSzrj 5362c0338ffSzrj #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 5372c0338ffSzrj for ((var) = TAILQ_FIRST(head); \ 5382c0338ffSzrj (var) != TAILQ_END(head) && \ 5392c0338ffSzrj ((tvar) = TAILQ_NEXT(var, field), 1); \ 5402c0338ffSzrj (var) = (tvar)) 5412c0338ffSzrj 5422c0338ffSzrj 5432c0338ffSzrj #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 5442c0338ffSzrj for((var) = TAILQ_LAST(head, headname); \ 5452c0338ffSzrj (var) != TAILQ_END(head); \ 5462c0338ffSzrj (var) = TAILQ_PREV(var, headname, field)) 5472c0338ffSzrj 5482c0338ffSzrj #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 5492c0338ffSzrj for ((var) = TAILQ_LAST(head, headname); \ 5502c0338ffSzrj (var) != TAILQ_END(head) && \ 5512c0338ffSzrj ((tvar) = TAILQ_PREV(var, headname, field), 1); \ 5522c0338ffSzrj (var) = (tvar)) 5532c0338ffSzrj 5542c0338ffSzrj /* 5552c0338ffSzrj * Tail queue functions. 5562c0338ffSzrj */ 5572c0338ffSzrj #define TAILQ_INIT(head) do { \ 5582c0338ffSzrj (head)->tqh_first = NULL; \ 5592c0338ffSzrj (head)->tqh_last = &(head)->tqh_first; \ 5602c0338ffSzrj } while (0) 5612c0338ffSzrj 5622c0338ffSzrj #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 5632c0338ffSzrj if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 5642c0338ffSzrj (head)->tqh_first->field.tqe_prev = \ 5652c0338ffSzrj &(elm)->field.tqe_next; \ 5662c0338ffSzrj else \ 5672c0338ffSzrj (head)->tqh_last = &(elm)->field.tqe_next; \ 5682c0338ffSzrj (head)->tqh_first = (elm); \ 5692c0338ffSzrj (elm)->field.tqe_prev = &(head)->tqh_first; \ 5702c0338ffSzrj } while (0) 5712c0338ffSzrj 5722c0338ffSzrj #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 5732c0338ffSzrj (elm)->field.tqe_next = NULL; \ 5742c0338ffSzrj (elm)->field.tqe_prev = (head)->tqh_last; \ 5752c0338ffSzrj *(head)->tqh_last = (elm); \ 5762c0338ffSzrj (head)->tqh_last = &(elm)->field.tqe_next; \ 5772c0338ffSzrj } while (0) 5782c0338ffSzrj 5792c0338ffSzrj #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 5802c0338ffSzrj if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 5812c0338ffSzrj (elm)->field.tqe_next->field.tqe_prev = \ 5822c0338ffSzrj &(elm)->field.tqe_next; \ 5832c0338ffSzrj else \ 5842c0338ffSzrj (head)->tqh_last = &(elm)->field.tqe_next; \ 5852c0338ffSzrj (listelm)->field.tqe_next = (elm); \ 5862c0338ffSzrj (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 5872c0338ffSzrj } while (0) 5882c0338ffSzrj 5892c0338ffSzrj #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 5902c0338ffSzrj (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 5912c0338ffSzrj (elm)->field.tqe_next = (listelm); \ 5922c0338ffSzrj *(listelm)->field.tqe_prev = (elm); \ 5932c0338ffSzrj (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 5942c0338ffSzrj } while (0) 5952c0338ffSzrj 5962c0338ffSzrj #define TAILQ_REMOVE(head, elm, field) do { \ 5972c0338ffSzrj if (((elm)->field.tqe_next) != NULL) \ 5982c0338ffSzrj (elm)->field.tqe_next->field.tqe_prev = \ 5992c0338ffSzrj (elm)->field.tqe_prev; \ 6002c0338ffSzrj else \ 6012c0338ffSzrj (head)->tqh_last = (elm)->field.tqe_prev; \ 6022c0338ffSzrj *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 6032c0338ffSzrj _Q_INVALIDATE((elm)->field.tqe_prev); \ 6042c0338ffSzrj _Q_INVALIDATE((elm)->field.tqe_next); \ 6052c0338ffSzrj } while (0) 6062c0338ffSzrj 6072c0338ffSzrj #define TAILQ_REPLACE(head, elm, elm2, field) do { \ 6082c0338ffSzrj if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ 6092c0338ffSzrj (elm2)->field.tqe_next->field.tqe_prev = \ 6102c0338ffSzrj &(elm2)->field.tqe_next; \ 6112c0338ffSzrj else \ 6122c0338ffSzrj (head)->tqh_last = &(elm2)->field.tqe_next; \ 6132c0338ffSzrj (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ 6142c0338ffSzrj *(elm2)->field.tqe_prev = (elm2); \ 6152c0338ffSzrj _Q_INVALIDATE((elm)->field.tqe_prev); \ 6162c0338ffSzrj _Q_INVALIDATE((elm)->field.tqe_next); \ 6172c0338ffSzrj } while (0) 6182c0338ffSzrj 61944aab0abSSascha Wildner #define TAILQ_CONCAT(head1, head2, field) do { \ 62044aab0abSSascha Wildner if (!TAILQ_EMPTY(head2)) { \ 62144aab0abSSascha Wildner *(head1)->tqh_last = (head2)->tqh_first; \ 62244aab0abSSascha Wildner (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 62344aab0abSSascha Wildner (head1)->tqh_last = (head2)->tqh_last; \ 62444aab0abSSascha Wildner TAILQ_INIT((head2)); \ 62544aab0abSSascha Wildner } \ 62644aab0abSSascha Wildner } while (0) 62744aab0abSSascha Wildner 628*2c81fb9cSAntonio Huete Jimenez #endif /* !_SYS_QUEUE_H_ */ 629