13b97a967SRobert Watson /*- 23b97a967SRobert Watson * Copyright (c) 1991, 1993 33b97a967SRobert Watson * The Regents of the University of California. All rights reserved. 43b97a967SRobert Watson * 53b97a967SRobert Watson * Redistribution and use in source and binary forms, with or without 63b97a967SRobert Watson * modification, are permitted provided that the following conditions 73b97a967SRobert Watson * are met: 83b97a967SRobert Watson * 1. Redistributions of source code must retain the above copyright 93b97a967SRobert Watson * notice, this list of conditions and the following disclaimer. 103b97a967SRobert Watson * 2. Redistributions in binary form must reproduce the above copyright 113b97a967SRobert Watson * notice, this list of conditions and the following disclaimer in the 123b97a967SRobert Watson * documentation and/or other materials provided with the distribution. 13*fbbd9655SWarner Losh * 3. Neither the name of the University nor the names of its contributors 143b97a967SRobert Watson * may be used to endorse or promote products derived from this software 153b97a967SRobert Watson * without specific prior written permission. 163b97a967SRobert Watson * 173b97a967SRobert Watson * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 183b97a967SRobert Watson * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 193b97a967SRobert Watson * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 203b97a967SRobert Watson * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 213b97a967SRobert Watson * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 223b97a967SRobert Watson * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 233b97a967SRobert Watson * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 243b97a967SRobert Watson * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 253b97a967SRobert Watson * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 263b97a967SRobert Watson * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 273b97a967SRobert Watson * SUCH DAMAGE. 283b97a967SRobert Watson * 293b97a967SRobert Watson * @(#)queue.h 8.5 (Berkeley) 8/20/94 303b97a967SRobert Watson * 313b97a967SRobert Watson * Derived from FreeBSD src/sys/sys/queue.h:1.63. 323b97a967SRobert Watson */ 333b97a967SRobert Watson 343b97a967SRobert Watson #ifndef _COMPAT_QUEUE_H_ 353b97a967SRobert Watson #define _COMPAT_QUEUE_H_ 363b97a967SRobert Watson 373b97a967SRobert Watson #include <sys/cdefs.h> 383b97a967SRobert Watson 393b97a967SRobert Watson /* 403b97a967SRobert Watson * This file defines four types of data structures: singly-linked lists, 413b97a967SRobert Watson * singly-linked tail queues, lists and tail queues. 423b97a967SRobert Watson * 433b97a967SRobert Watson * A singly-linked list is headed by a single forward pointer. The elements 443b97a967SRobert Watson * are singly linked for minimum space and pointer manipulation overhead at 453b97a967SRobert Watson * the expense of O(n) removal for arbitrary elements. New elements can be 463b97a967SRobert Watson * added to the list after an existing element or at the head of the list. 473b97a967SRobert Watson * Elements being removed from the head of the list should use the explicit 483b97a967SRobert Watson * macro for this purpose for optimum efficiency. A singly-linked list may 493b97a967SRobert Watson * only be traversed in the forward direction. Singly-linked lists are ideal 503b97a967SRobert Watson * for applications with large datasets and few or no removals or for 513b97a967SRobert Watson * implementing a LIFO queue. 523b97a967SRobert Watson * 533b97a967SRobert Watson * A singly-linked tail queue is headed by a pair of pointers, one to the 543b97a967SRobert Watson * head of the list and the other to the tail of the list. The elements are 553b97a967SRobert Watson * singly linked for minimum space and pointer manipulation overhead at the 563b97a967SRobert Watson * expense of O(n) removal for arbitrary elements. New elements can be added 573b97a967SRobert Watson * to the list after an existing element, at the head of the list, or at the 583b97a967SRobert Watson * end of the list. Elements being removed from the head of the tail queue 593b97a967SRobert Watson * should use the explicit macro for this purpose for optimum efficiency. 603b97a967SRobert Watson * A singly-linked tail queue may only be traversed in the forward direction. 613b97a967SRobert Watson * Singly-linked tail queues are ideal for applications with large datasets 623b97a967SRobert Watson * and few or no removals or for implementing a FIFO queue. 633b97a967SRobert Watson * 643b97a967SRobert Watson * A list is headed by a single forward pointer (or an array of forward 653b97a967SRobert Watson * pointers for a hash table header). The elements are doubly linked 663b97a967SRobert Watson * so that an arbitrary element can be removed without a need to 673b97a967SRobert Watson * traverse the list. New elements can be added to the list before 683b97a967SRobert Watson * or after an existing element or at the head of the list. A list 693b97a967SRobert Watson * may only be traversed in the forward direction. 703b97a967SRobert Watson * 713b97a967SRobert Watson * A tail queue is headed by a pair of pointers, one to the head of the 723b97a967SRobert Watson * list and the other to the tail of the list. The elements are doubly 733b97a967SRobert Watson * linked so that an arbitrary element can be removed without a need to 743b97a967SRobert Watson * traverse the list. New elements can be added to the list before or 753b97a967SRobert Watson * after an existing element, at the head of the list, or at the end of 763b97a967SRobert Watson * the list. A tail queue may be traversed in either direction. 773b97a967SRobert Watson * 783b97a967SRobert Watson * For details on the use of these macros, see the queue(3) manual page. 793b97a967SRobert Watson * 803b97a967SRobert Watson * 813b97a967SRobert Watson * SLIST LIST STAILQ TAILQ 823b97a967SRobert Watson * _HEAD + + + + 833b97a967SRobert Watson * _HEAD_INITIALIZER + + + + 843b97a967SRobert Watson * _ENTRY + + + + 853b97a967SRobert Watson * _INIT + + + + 863b97a967SRobert Watson * _EMPTY + + + + 873b97a967SRobert Watson * _FIRST + + + + 883b97a967SRobert Watson * _NEXT + + + + 893b97a967SRobert Watson * _PREV - - - + 903b97a967SRobert Watson * _LAST - - + + 913b97a967SRobert Watson * _FOREACH + + + + 923b97a967SRobert Watson * _FOREACH_SAFE + + + + 933b97a967SRobert Watson * _FOREACH_REVERSE - - - + 943b97a967SRobert Watson * _FOREACH_REVERSE_SAFE - - - + 953b97a967SRobert Watson * _INSERT_HEAD + + + + 963b97a967SRobert Watson * _INSERT_BEFORE - + - + 973b97a967SRobert Watson * _INSERT_AFTER + + + + 983b97a967SRobert Watson * _INSERT_TAIL - - + + 993b97a967SRobert Watson * _CONCAT - - + + 1003b97a967SRobert Watson * _REMOVE_HEAD + - + - 1013b97a967SRobert Watson * _REMOVE + + + + 1023b97a967SRobert Watson * 1033b97a967SRobert Watson */ 1043b97a967SRobert Watson #ifdef QUEUE_MACRO_DEBUG 1053b97a967SRobert Watson /* Store the last 2 places the queue element or head was altered */ 1063b97a967SRobert Watson struct qm_trace { 1073b97a967SRobert Watson char * lastfile; 1083b97a967SRobert Watson int lastline; 1093b97a967SRobert Watson char * prevfile; 1103b97a967SRobert Watson int prevline; 1113b97a967SRobert Watson }; 1123b97a967SRobert Watson 1133b97a967SRobert Watson #define TRACEBUF struct qm_trace trace; 1143b97a967SRobert Watson #define TRASHIT(x) do {(x) = (void *)-1;} while (0) 1153b97a967SRobert Watson 1163b97a967SRobert Watson #define QMD_TRACE_HEAD(head) do { \ 1173b97a967SRobert Watson (head)->trace.prevline = (head)->trace.lastline; \ 1183b97a967SRobert Watson (head)->trace.prevfile = (head)->trace.lastfile; \ 1193b97a967SRobert Watson (head)->trace.lastline = __LINE__; \ 1203b97a967SRobert Watson (head)->trace.lastfile = __FILE__; \ 1213b97a967SRobert Watson } while (0) 1223b97a967SRobert Watson 1233b97a967SRobert Watson #define QMD_TRACE_ELEM(elem) do { \ 1243b97a967SRobert Watson (elem)->trace.prevline = (elem)->trace.lastline; \ 1253b97a967SRobert Watson (elem)->trace.prevfile = (elem)->trace.lastfile; \ 1263b97a967SRobert Watson (elem)->trace.lastline = __LINE__; \ 1273b97a967SRobert Watson (elem)->trace.lastfile = __FILE__; \ 1283b97a967SRobert Watson } while (0) 1293b97a967SRobert Watson 1303b97a967SRobert Watson #else 1313b97a967SRobert Watson #define QMD_TRACE_ELEM(elem) 1323b97a967SRobert Watson #define QMD_TRACE_HEAD(head) 1333b97a967SRobert Watson #define TRACEBUF 1343b97a967SRobert Watson #define TRASHIT(x) 1353b97a967SRobert Watson #endif /* QUEUE_MACRO_DEBUG */ 1363b97a967SRobert Watson 1373b97a967SRobert Watson /* 1383b97a967SRobert Watson * Singly-linked List declarations. 1393b97a967SRobert Watson */ 1403b97a967SRobert Watson #define SLIST_HEAD(name, type) \ 1413b97a967SRobert Watson struct name { \ 1423b97a967SRobert Watson struct type *slh_first; /* first element */ \ 1433b97a967SRobert Watson } 1443b97a967SRobert Watson 1453b97a967SRobert Watson #define SLIST_HEAD_INITIALIZER(head) \ 1463b97a967SRobert Watson { NULL } 1473b97a967SRobert Watson 1483b97a967SRobert Watson #define SLIST_ENTRY(type) \ 1493b97a967SRobert Watson struct { \ 1503b97a967SRobert Watson struct type *sle_next; /* next element */ \ 1513b97a967SRobert Watson } 1523b97a967SRobert Watson 1533b97a967SRobert Watson /* 1543b97a967SRobert Watson * Singly-linked List functions. 1553b97a967SRobert Watson */ 1563b97a967SRobert Watson #define SLIST_EMPTY(head) ((head)->slh_first == NULL) 1573b97a967SRobert Watson 1583b97a967SRobert Watson #define SLIST_FIRST(head) ((head)->slh_first) 1593b97a967SRobert Watson 1603b97a967SRobert Watson #define SLIST_FOREACH(var, head, field) \ 1613b97a967SRobert Watson for ((var) = SLIST_FIRST((head)); \ 1623b97a967SRobert Watson (var); \ 1633b97a967SRobert Watson (var) = SLIST_NEXT((var), field)) 1643b97a967SRobert Watson 1653b97a967SRobert Watson #define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 1663b97a967SRobert Watson for ((var) = SLIST_FIRST((head)); \ 1673b97a967SRobert Watson (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 1683b97a967SRobert Watson (var) = (tvar)) 1693b97a967SRobert Watson 1703b97a967SRobert Watson #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 1713b97a967SRobert Watson for ((varp) = &SLIST_FIRST((head)); \ 1723b97a967SRobert Watson ((var) = *(varp)) != NULL; \ 1733b97a967SRobert Watson (varp) = &SLIST_NEXT((var), field)) 1743b97a967SRobert Watson 1753b97a967SRobert Watson #define SLIST_INIT(head) do { \ 1763b97a967SRobert Watson SLIST_FIRST((head)) = NULL; \ 1773b97a967SRobert Watson } while (0) 1783b97a967SRobert Watson 1793b97a967SRobert Watson #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 1803b97a967SRobert Watson SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 1813b97a967SRobert Watson SLIST_NEXT((slistelm), field) = (elm); \ 1823b97a967SRobert Watson } while (0) 1833b97a967SRobert Watson 1843b97a967SRobert Watson #define SLIST_INSERT_HEAD(head, elm, field) do { \ 1853b97a967SRobert Watson SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 1863b97a967SRobert Watson SLIST_FIRST((head)) = (elm); \ 1873b97a967SRobert Watson } while (0) 1883b97a967SRobert Watson 1893b97a967SRobert Watson #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 1903b97a967SRobert Watson 1913b97a967SRobert Watson #define SLIST_REMOVE(head, elm, type, field) do { \ 1923b97a967SRobert Watson if (SLIST_FIRST((head)) == (elm)) { \ 1933b97a967SRobert Watson SLIST_REMOVE_HEAD((head), field); \ 1943b97a967SRobert Watson } \ 1953b97a967SRobert Watson else { \ 1963b97a967SRobert Watson struct type *curelm = SLIST_FIRST((head)); \ 1973b97a967SRobert Watson while (SLIST_NEXT(curelm, field) != (elm)) \ 1983b97a967SRobert Watson curelm = SLIST_NEXT(curelm, field); \ 1993b97a967SRobert Watson SLIST_NEXT(curelm, field) = \ 2003b97a967SRobert Watson SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 2013b97a967SRobert Watson } \ 2023b97a967SRobert Watson TRASHIT((elm)->field.sle_next); \ 2033b97a967SRobert Watson } while (0) 2043b97a967SRobert Watson 2053b97a967SRobert Watson #define SLIST_REMOVE_HEAD(head, field) do { \ 2063b97a967SRobert Watson SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 2073b97a967SRobert Watson } while (0) 2083b97a967SRobert Watson 2093b97a967SRobert Watson /* 2103b97a967SRobert Watson * Singly-linked Tail queue declarations. 2113b97a967SRobert Watson */ 2123b97a967SRobert Watson #define STAILQ_HEAD(name, type) \ 2133b97a967SRobert Watson struct name { \ 2143b97a967SRobert Watson struct type *stqh_first;/* first element */ \ 2153b97a967SRobert Watson struct type **stqh_last;/* addr of last next element */ \ 2163b97a967SRobert Watson } 2173b97a967SRobert Watson 2183b97a967SRobert Watson #define STAILQ_HEAD_INITIALIZER(head) \ 2193b97a967SRobert Watson { NULL, &(head).stqh_first } 2203b97a967SRobert Watson 2213b97a967SRobert Watson #define STAILQ_ENTRY(type) \ 2223b97a967SRobert Watson struct { \ 2233b97a967SRobert Watson struct type *stqe_next; /* next element */ \ 2243b97a967SRobert Watson } 2253b97a967SRobert Watson 2263b97a967SRobert Watson /* 2273b97a967SRobert Watson * Singly-linked Tail queue functions. 2283b97a967SRobert Watson */ 2293b97a967SRobert Watson #define STAILQ_CONCAT(head1, head2) do { \ 2303b97a967SRobert Watson if (!STAILQ_EMPTY((head2))) { \ 2313b97a967SRobert Watson *(head1)->stqh_last = (head2)->stqh_first; \ 2323b97a967SRobert Watson (head1)->stqh_last = (head2)->stqh_last; \ 2333b97a967SRobert Watson STAILQ_INIT((head2)); \ 2343b97a967SRobert Watson } \ 2353b97a967SRobert Watson } while (0) 2363b97a967SRobert Watson 2373b97a967SRobert Watson #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 2383b97a967SRobert Watson 2393b97a967SRobert Watson #define STAILQ_FIRST(head) ((head)->stqh_first) 2403b97a967SRobert Watson 2413b97a967SRobert Watson #define STAILQ_FOREACH(var, head, field) \ 2423b97a967SRobert Watson for((var) = STAILQ_FIRST((head)); \ 2433b97a967SRobert Watson (var); \ 2443b97a967SRobert Watson (var) = STAILQ_NEXT((var), field)) 2453b97a967SRobert Watson 2463b97a967SRobert Watson 2473b97a967SRobert Watson #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 2483b97a967SRobert Watson for ((var) = STAILQ_FIRST((head)); \ 2493b97a967SRobert Watson (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 2503b97a967SRobert Watson (var) = (tvar)) 2513b97a967SRobert Watson 2523b97a967SRobert Watson #define STAILQ_INIT(head) do { \ 2533b97a967SRobert Watson STAILQ_FIRST((head)) = NULL; \ 2543b97a967SRobert Watson (head)->stqh_last = &STAILQ_FIRST((head)); \ 2553b97a967SRobert Watson } while (0) 2563b97a967SRobert Watson 2573b97a967SRobert Watson #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 2583b97a967SRobert Watson if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 2593b97a967SRobert Watson (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 2603b97a967SRobert Watson STAILQ_NEXT((tqelm), field) = (elm); \ 2613b97a967SRobert Watson } while (0) 2623b97a967SRobert Watson 2633b97a967SRobert Watson #define STAILQ_INSERT_HEAD(head, elm, field) do { \ 2643b97a967SRobert Watson if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 2653b97a967SRobert Watson (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 2663b97a967SRobert Watson STAILQ_FIRST((head)) = (elm); \ 2673b97a967SRobert Watson } while (0) 2683b97a967SRobert Watson 2693b97a967SRobert Watson #define STAILQ_INSERT_TAIL(head, elm, field) do { \ 2703b97a967SRobert Watson STAILQ_NEXT((elm), field) = NULL; \ 2713b97a967SRobert Watson *(head)->stqh_last = (elm); \ 2723b97a967SRobert Watson (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 2733b97a967SRobert Watson } while (0) 2743b97a967SRobert Watson 2753b97a967SRobert Watson #define STAILQ_LAST(head, type, field) \ 2763b97a967SRobert Watson (STAILQ_EMPTY((head)) ? \ 2773b97a967SRobert Watson NULL : \ 2783b97a967SRobert Watson ((struct type *) \ 2793b97a967SRobert Watson ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 2803b97a967SRobert Watson 2813b97a967SRobert Watson #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 2823b97a967SRobert Watson 2833b97a967SRobert Watson #define STAILQ_REMOVE(head, elm, type, field) do { \ 2843b97a967SRobert Watson if (STAILQ_FIRST((head)) == (elm)) { \ 2853b97a967SRobert Watson STAILQ_REMOVE_HEAD((head), field); \ 2863b97a967SRobert Watson } \ 2873b97a967SRobert Watson else { \ 2883b97a967SRobert Watson struct type *curelm = STAILQ_FIRST((head)); \ 2893b97a967SRobert Watson while (STAILQ_NEXT(curelm, field) != (elm)) \ 2903b97a967SRobert Watson curelm = STAILQ_NEXT(curelm, field); \ 2913b97a967SRobert Watson if ((STAILQ_NEXT(curelm, field) = \ 2923b97a967SRobert Watson STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 2933b97a967SRobert Watson (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 2943b97a967SRobert Watson } \ 2953b97a967SRobert Watson TRASHIT((elm)->field.stqe_next); \ 2963b97a967SRobert Watson } while (0) 2973b97a967SRobert Watson 2983b97a967SRobert Watson #define STAILQ_REMOVE_HEAD(head, field) do { \ 2993b97a967SRobert Watson if ((STAILQ_FIRST((head)) = \ 3003b97a967SRobert Watson STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 3013b97a967SRobert Watson (head)->stqh_last = &STAILQ_FIRST((head)); \ 3023b97a967SRobert Watson } while (0) 3033b97a967SRobert Watson 3043b97a967SRobert Watson #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 3053b97a967SRobert Watson if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ 3063b97a967SRobert Watson (head)->stqh_last = &STAILQ_FIRST((head)); \ 3073b97a967SRobert Watson } while (0) 3083b97a967SRobert Watson 3093b97a967SRobert Watson /* 3103b97a967SRobert Watson * List declarations. 3113b97a967SRobert Watson */ 3123b97a967SRobert Watson #define LIST_HEAD(name, type) \ 3133b97a967SRobert Watson struct name { \ 3143b97a967SRobert Watson struct type *lh_first; /* first element */ \ 3153b97a967SRobert Watson } 3163b97a967SRobert Watson 3173b97a967SRobert Watson #define LIST_HEAD_INITIALIZER(head) \ 3183b97a967SRobert Watson { NULL } 3193b97a967SRobert Watson 3203b97a967SRobert Watson #define LIST_ENTRY(type) \ 3213b97a967SRobert Watson struct { \ 3223b97a967SRobert Watson struct type *le_next; /* next element */ \ 3233b97a967SRobert Watson struct type **le_prev; /* address of previous next element */ \ 3243b97a967SRobert Watson } 3253b97a967SRobert Watson 3263b97a967SRobert Watson /* 3273b97a967SRobert Watson * List functions. 3283b97a967SRobert Watson */ 3293b97a967SRobert Watson 3303b97a967SRobert Watson #if (defined(_KERNEL) && defined(INVARIANTS)) || defined(QUEUE_MACRO_DEBUG) 3313b97a967SRobert Watson #define QMD_LIST_CHECK_HEAD(head, field) do { \ 3323b97a967SRobert Watson if (LIST_FIRST((head)) != NULL && \ 3333b97a967SRobert Watson LIST_FIRST((head))->field.le_prev != \ 3343b97a967SRobert Watson &LIST_FIRST((head))) \ 3353b97a967SRobert Watson panic("Bad list head %p first->prev != head", (head)); \ 3363b97a967SRobert Watson } while (0) 3373b97a967SRobert Watson 3383b97a967SRobert Watson #define QMD_LIST_CHECK_NEXT(elm, field) do { \ 3393b97a967SRobert Watson if (LIST_NEXT((elm), field) != NULL && \ 3403b97a967SRobert Watson LIST_NEXT((elm), field)->field.le_prev != \ 3413b97a967SRobert Watson &((elm)->field.le_next)) \ 3423b97a967SRobert Watson panic("Bad link elm %p next->prev != elm", (elm)); \ 3433b97a967SRobert Watson } while (0) 3443b97a967SRobert Watson 3453b97a967SRobert Watson #define QMD_LIST_CHECK_PREV(elm, field) do { \ 3463b97a967SRobert Watson if (*(elm)->field.le_prev != (elm)) \ 3473b97a967SRobert Watson panic("Bad link elm %p prev->next != elm", (elm)); \ 3483b97a967SRobert Watson } while (0) 3493b97a967SRobert Watson #else 3503b97a967SRobert Watson #define QMD_LIST_CHECK_HEAD(head, field) 3513b97a967SRobert Watson #define QMD_LIST_CHECK_NEXT(elm, field) 3523b97a967SRobert Watson #define QMD_LIST_CHECK_PREV(elm, field) 3533b97a967SRobert Watson #endif /* (_KERNEL && INVARIANTS) || QUEUE_MACRO_DEBUG */ 3543b97a967SRobert Watson 3553b97a967SRobert Watson #define LIST_EMPTY(head) ((head)->lh_first == NULL) 3563b97a967SRobert Watson 3573b97a967SRobert Watson #define LIST_FIRST(head) ((head)->lh_first) 3583b97a967SRobert Watson 3593b97a967SRobert Watson #define LIST_FOREACH(var, head, field) \ 3603b97a967SRobert Watson for ((var) = LIST_FIRST((head)); \ 3613b97a967SRobert Watson (var); \ 3623b97a967SRobert Watson (var) = LIST_NEXT((var), field)) 3633b97a967SRobert Watson 3643b97a967SRobert Watson #define LIST_FOREACH_SAFE(var, head, field, tvar) \ 3653b97a967SRobert Watson for ((var) = LIST_FIRST((head)); \ 3663b97a967SRobert Watson (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 3673b97a967SRobert Watson (var) = (tvar)) 3683b97a967SRobert Watson 3693b97a967SRobert Watson #define LIST_INIT(head) do { \ 3703b97a967SRobert Watson LIST_FIRST((head)) = NULL; \ 3713b97a967SRobert Watson } while (0) 3723b97a967SRobert Watson 3733b97a967SRobert Watson #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 3743b97a967SRobert Watson QMD_LIST_CHECK_NEXT(listelm, field); \ 3753b97a967SRobert Watson if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 3763b97a967SRobert Watson LIST_NEXT((listelm), field)->field.le_prev = \ 3773b97a967SRobert Watson &LIST_NEXT((elm), field); \ 3783b97a967SRobert Watson LIST_NEXT((listelm), field) = (elm); \ 3793b97a967SRobert Watson (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 3803b97a967SRobert Watson } while (0) 3813b97a967SRobert Watson 3823b97a967SRobert Watson #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 3833b97a967SRobert Watson QMD_LIST_CHECK_PREV(listelm, field); \ 3843b97a967SRobert Watson (elm)->field.le_prev = (listelm)->field.le_prev; \ 3853b97a967SRobert Watson LIST_NEXT((elm), field) = (listelm); \ 3863b97a967SRobert Watson *(listelm)->field.le_prev = (elm); \ 3873b97a967SRobert Watson (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 3883b97a967SRobert Watson } while (0) 3893b97a967SRobert Watson 3903b97a967SRobert Watson #define LIST_INSERT_HEAD(head, elm, field) do { \ 3913b97a967SRobert Watson QMD_LIST_CHECK_HEAD((head), field); \ 3923b97a967SRobert Watson if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 3933b97a967SRobert Watson LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 3943b97a967SRobert Watson LIST_FIRST((head)) = (elm); \ 3953b97a967SRobert Watson (elm)->field.le_prev = &LIST_FIRST((head)); \ 3963b97a967SRobert Watson } while (0) 3973b97a967SRobert Watson 3983b97a967SRobert Watson #define LIST_NEXT(elm, field) ((elm)->field.le_next) 3993b97a967SRobert Watson 4003b97a967SRobert Watson #define LIST_REMOVE(elm, field) do { \ 4013b97a967SRobert Watson QMD_LIST_CHECK_NEXT(elm, field); \ 4023b97a967SRobert Watson QMD_LIST_CHECK_PREV(elm, field); \ 4033b97a967SRobert Watson if (LIST_NEXT((elm), field) != NULL) \ 4043b97a967SRobert Watson LIST_NEXT((elm), field)->field.le_prev = \ 4053b97a967SRobert Watson (elm)->field.le_prev; \ 4063b97a967SRobert Watson *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 4073b97a967SRobert Watson TRASHIT((elm)->field.le_next); \ 4083b97a967SRobert Watson TRASHIT((elm)->field.le_prev); \ 4093b97a967SRobert Watson } while (0) 4103b97a967SRobert Watson 4113b97a967SRobert Watson /* 4123b97a967SRobert Watson * Tail queue declarations. 4133b97a967SRobert Watson */ 4143b97a967SRobert Watson #define TAILQ_HEAD(name, type) \ 4153b97a967SRobert Watson struct name { \ 4163b97a967SRobert Watson struct type *tqh_first; /* first element */ \ 4173b97a967SRobert Watson struct type **tqh_last; /* addr of last next element */ \ 4183b97a967SRobert Watson TRACEBUF \ 4193b97a967SRobert Watson } 4203b97a967SRobert Watson 4213b97a967SRobert Watson #define TAILQ_HEAD_INITIALIZER(head) \ 4223b97a967SRobert Watson { NULL, &(head).tqh_first } 4233b97a967SRobert Watson 4243b97a967SRobert Watson #define TAILQ_ENTRY(type) \ 4253b97a967SRobert Watson struct { \ 4263b97a967SRobert Watson struct type *tqe_next; /* next element */ \ 4273b97a967SRobert Watson struct type **tqe_prev; /* address of previous next element */ \ 4283b97a967SRobert Watson TRACEBUF \ 4293b97a967SRobert Watson } 4303b97a967SRobert Watson 4313b97a967SRobert Watson /* 4323b97a967SRobert Watson * Tail queue functions. 4333b97a967SRobert Watson */ 4343b97a967SRobert Watson #define TAILQ_CONCAT(head1, head2, field) do { \ 4353b97a967SRobert Watson if (!TAILQ_EMPTY(head2)) { \ 4363b97a967SRobert Watson *(head1)->tqh_last = (head2)->tqh_first; \ 4373b97a967SRobert Watson (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 4383b97a967SRobert Watson (head1)->tqh_last = (head2)->tqh_last; \ 4393b97a967SRobert Watson TAILQ_INIT((head2)); \ 4403b97a967SRobert Watson QMD_TRACE_HEAD(head1); \ 4413b97a967SRobert Watson QMD_TRACE_HEAD(head2); \ 4423b97a967SRobert Watson } \ 4433b97a967SRobert Watson } while (0) 4443b97a967SRobert Watson 4453b97a967SRobert Watson #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 4463b97a967SRobert Watson 4473b97a967SRobert Watson #define TAILQ_FIRST(head) ((head)->tqh_first) 4483b97a967SRobert Watson 4493b97a967SRobert Watson #define TAILQ_FOREACH(var, head, field) \ 4503b97a967SRobert Watson for ((var) = TAILQ_FIRST((head)); \ 4513b97a967SRobert Watson (var); \ 4523b97a967SRobert Watson (var) = TAILQ_NEXT((var), field)) 4533b97a967SRobert Watson 4543b97a967SRobert Watson #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 4553b97a967SRobert Watson for ((var) = TAILQ_FIRST((head)); \ 4563b97a967SRobert Watson (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 4573b97a967SRobert Watson (var) = (tvar)) 4583b97a967SRobert Watson 4593b97a967SRobert Watson #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 4603b97a967SRobert Watson for ((var) = TAILQ_LAST((head), headname); \ 4613b97a967SRobert Watson (var); \ 4623b97a967SRobert Watson (var) = TAILQ_PREV((var), headname, field)) 4633b97a967SRobert Watson 4643b97a967SRobert Watson #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 4653b97a967SRobert Watson for ((var) = TAILQ_LAST((head), headname); \ 4663b97a967SRobert Watson (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 4673b97a967SRobert Watson (var) = (tvar)) 4683b97a967SRobert Watson 4693b97a967SRobert Watson #define TAILQ_INIT(head) do { \ 4703b97a967SRobert Watson TAILQ_FIRST((head)) = NULL; \ 4713b97a967SRobert Watson (head)->tqh_last = &TAILQ_FIRST((head)); \ 4723b97a967SRobert Watson QMD_TRACE_HEAD(head); \ 4733b97a967SRobert Watson } while (0) 4743b97a967SRobert Watson 4753b97a967SRobert Watson #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 4763b97a967SRobert Watson if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 4773b97a967SRobert Watson TAILQ_NEXT((elm), field)->field.tqe_prev = \ 4783b97a967SRobert Watson &TAILQ_NEXT((elm), field); \ 4793b97a967SRobert Watson else { \ 4803b97a967SRobert Watson (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 4813b97a967SRobert Watson QMD_TRACE_HEAD(head); \ 4823b97a967SRobert Watson } \ 4833b97a967SRobert Watson TAILQ_NEXT((listelm), field) = (elm); \ 4843b97a967SRobert Watson (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 4853b97a967SRobert Watson QMD_TRACE_ELEM(&(elm)->field); \ 4863b97a967SRobert Watson QMD_TRACE_ELEM(&listelm->field); \ 4873b97a967SRobert Watson } while (0) 4883b97a967SRobert Watson 4893b97a967SRobert Watson #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 4903b97a967SRobert Watson (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 4913b97a967SRobert Watson TAILQ_NEXT((elm), field) = (listelm); \ 4923b97a967SRobert Watson *(listelm)->field.tqe_prev = (elm); \ 4933b97a967SRobert Watson (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 4943b97a967SRobert Watson QMD_TRACE_ELEM(&(elm)->field); \ 4953b97a967SRobert Watson QMD_TRACE_ELEM(&listelm->field); \ 4963b97a967SRobert Watson } while (0) 4973b97a967SRobert Watson 4983b97a967SRobert Watson #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 4993b97a967SRobert Watson if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 5003b97a967SRobert Watson TAILQ_FIRST((head))->field.tqe_prev = \ 5013b97a967SRobert Watson &TAILQ_NEXT((elm), field); \ 5023b97a967SRobert Watson else \ 5033b97a967SRobert Watson (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 5043b97a967SRobert Watson TAILQ_FIRST((head)) = (elm); \ 5053b97a967SRobert Watson (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 5063b97a967SRobert Watson QMD_TRACE_HEAD(head); \ 5073b97a967SRobert Watson QMD_TRACE_ELEM(&(elm)->field); \ 5083b97a967SRobert Watson } while (0) 5093b97a967SRobert Watson 5103b97a967SRobert Watson #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 5113b97a967SRobert Watson TAILQ_NEXT((elm), field) = NULL; \ 5123b97a967SRobert Watson (elm)->field.tqe_prev = (head)->tqh_last; \ 5133b97a967SRobert Watson *(head)->tqh_last = (elm); \ 5143b97a967SRobert Watson (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 5153b97a967SRobert Watson QMD_TRACE_HEAD(head); \ 5163b97a967SRobert Watson QMD_TRACE_ELEM(&(elm)->field); \ 5173b97a967SRobert Watson } while (0) 5183b97a967SRobert Watson 5193b97a967SRobert Watson #define TAILQ_LAST(head, headname) \ 5203b97a967SRobert Watson (*(((struct headname *)((head)->tqh_last))->tqh_last)) 5213b97a967SRobert Watson 5223b97a967SRobert Watson #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 5233b97a967SRobert Watson 5243b97a967SRobert Watson #define TAILQ_PREV(elm, headname, field) \ 5253b97a967SRobert Watson (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 5263b97a967SRobert Watson 5273b97a967SRobert Watson #define TAILQ_REMOVE(head, elm, field) do { \ 5283b97a967SRobert Watson if ((TAILQ_NEXT((elm), field)) != NULL) \ 5293b97a967SRobert Watson TAILQ_NEXT((elm), field)->field.tqe_prev = \ 5303b97a967SRobert Watson (elm)->field.tqe_prev; \ 5313b97a967SRobert Watson else { \ 5323b97a967SRobert Watson (head)->tqh_last = (elm)->field.tqe_prev; \ 5333b97a967SRobert Watson QMD_TRACE_HEAD(head); \ 5343b97a967SRobert Watson } \ 5353b97a967SRobert Watson *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 5363b97a967SRobert Watson TRASHIT((elm)->field.tqe_next); \ 5373b97a967SRobert Watson TRASHIT((elm)->field.tqe_prev); \ 5383b97a967SRobert Watson QMD_TRACE_ELEM(&(elm)->field); \ 5393b97a967SRobert Watson } while (0) 5403b97a967SRobert Watson 5413b97a967SRobert Watson #endif /* !_COMPAT_QUEUE_H_ */ 542