14c87aefeSPatrick Mooney /*- 24c87aefeSPatrick Mooney * Copyright (c) 1991, 1993 34c87aefeSPatrick Mooney * The Regents of the University of California. All rights reserved. 44c87aefeSPatrick Mooney * 54c87aefeSPatrick Mooney * Redistribution and use in source and binary forms, with or without 64c87aefeSPatrick Mooney * modification, are permitted provided that the following conditions 74c87aefeSPatrick Mooney * are met: 84c87aefeSPatrick Mooney * 1. Redistributions of source code must retain the above copyright 94c87aefeSPatrick Mooney * notice, this list of conditions and the following disclaimer. 104c87aefeSPatrick Mooney * 2. Redistributions in binary form must reproduce the above copyright 114c87aefeSPatrick Mooney * notice, this list of conditions and the following disclaimer in the 124c87aefeSPatrick Mooney * documentation and/or other materials provided with the distribution. 134c87aefeSPatrick Mooney * 4. Neither the name of the University nor the names of its contributors 144c87aefeSPatrick Mooney * may be used to endorse or promote products derived from this software 154c87aefeSPatrick Mooney * without specific prior written permission. 164c87aefeSPatrick Mooney * 174c87aefeSPatrick Mooney * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 184c87aefeSPatrick Mooney * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 194c87aefeSPatrick Mooney * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 204c87aefeSPatrick Mooney * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 214c87aefeSPatrick Mooney * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 224c87aefeSPatrick Mooney * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 234c87aefeSPatrick Mooney * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 244c87aefeSPatrick Mooney * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 254c87aefeSPatrick Mooney * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 264c87aefeSPatrick Mooney * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 274c87aefeSPatrick Mooney * SUCH DAMAGE. 284c87aefeSPatrick Mooney * 294c87aefeSPatrick Mooney * @(#)queue.h 8.5 (Berkeley) 8/20/94 304c87aefeSPatrick Mooney * $FreeBSD$ 314c87aefeSPatrick Mooney */ 324c87aefeSPatrick Mooney 334c87aefeSPatrick Mooney #ifndef _SYS_QUEUE_H_ 344c87aefeSPatrick Mooney #define _SYS_QUEUE_H_ 354c87aefeSPatrick Mooney 364c87aefeSPatrick Mooney #include <sys/cdefs.h> 374c87aefeSPatrick Mooney 384c87aefeSPatrick Mooney /* 394c87aefeSPatrick Mooney * This file defines four types of data structures: singly-linked lists, 404c87aefeSPatrick Mooney * singly-linked tail queues, lists and tail queues. 414c87aefeSPatrick Mooney * 424c87aefeSPatrick Mooney * A singly-linked list is headed by a single forward pointer. The elements 434c87aefeSPatrick Mooney * are singly linked for minimum space and pointer manipulation overhead at 444c87aefeSPatrick Mooney * the expense of O(n) removal for arbitrary elements. New elements can be 454c87aefeSPatrick Mooney * added to the list after an existing element or at the head of the list. 464c87aefeSPatrick Mooney * Elements being removed from the head of the list should use the explicit 474c87aefeSPatrick Mooney * macro for this purpose for optimum efficiency. A singly-linked list may 484c87aefeSPatrick Mooney * only be traversed in the forward direction. Singly-linked lists are ideal 494c87aefeSPatrick Mooney * for applications with large datasets and few or no removals or for 504c87aefeSPatrick Mooney * implementing a LIFO queue. 514c87aefeSPatrick Mooney * 524c87aefeSPatrick Mooney * A singly-linked tail queue is headed by a pair of pointers, one to the 534c87aefeSPatrick Mooney * head of the list and the other to the tail of the list. The elements are 544c87aefeSPatrick Mooney * singly linked for minimum space and pointer manipulation overhead at the 554c87aefeSPatrick Mooney * expense of O(n) removal for arbitrary elements. New elements can be added 564c87aefeSPatrick Mooney * to the list after an existing element, at the head of the list, or at the 574c87aefeSPatrick Mooney * end of the list. Elements being removed from the head of the tail queue 584c87aefeSPatrick Mooney * should use the explicit macro for this purpose for optimum efficiency. 594c87aefeSPatrick Mooney * A singly-linked tail queue may only be traversed in the forward direction. 604c87aefeSPatrick Mooney * Singly-linked tail queues are ideal for applications with large datasets 614c87aefeSPatrick Mooney * and few or no removals or for implementing a FIFO queue. 624c87aefeSPatrick Mooney * 634c87aefeSPatrick Mooney * A list is headed by a single forward pointer (or an array of forward 644c87aefeSPatrick Mooney * pointers for a hash table header). The elements are doubly linked 654c87aefeSPatrick Mooney * so that an arbitrary element can be removed without a need to 664c87aefeSPatrick Mooney * traverse the list. New elements can be added to the list before 674c87aefeSPatrick Mooney * or after an existing element or at the head of the list. A list 684c87aefeSPatrick Mooney * may be traversed in either direction. 694c87aefeSPatrick Mooney * 704c87aefeSPatrick Mooney * A tail queue is headed by a pair of pointers, one to the head of the 714c87aefeSPatrick Mooney * list and the other to the tail of the list. The elements are doubly 724c87aefeSPatrick Mooney * linked so that an arbitrary element can be removed without a need to 734c87aefeSPatrick Mooney * traverse the list. New elements can be added to the list before or 744c87aefeSPatrick Mooney * after an existing element, at the head of the list, or at the end of 754c87aefeSPatrick Mooney * the list. A tail queue may be traversed in either direction. 764c87aefeSPatrick Mooney * 774c87aefeSPatrick Mooney * For details on the use of these macros, see the queue(3) manual page. 784c87aefeSPatrick Mooney * 794c87aefeSPatrick Mooney * Below is a summary of implemented functions where: 804c87aefeSPatrick Mooney * + means the macro is available 814c87aefeSPatrick Mooney * - means the macro is not available 824c87aefeSPatrick Mooney * s means the macro is available but is slow (runs in O(n) time) 834c87aefeSPatrick Mooney * 844c87aefeSPatrick Mooney * SLIST LIST STAILQ TAILQ 854c87aefeSPatrick Mooney * _HEAD + + + + 864c87aefeSPatrick Mooney * _CLASS_HEAD + + + + 874c87aefeSPatrick Mooney * _HEAD_INITIALIZER + + + + 884c87aefeSPatrick Mooney * _ENTRY + + + + 894c87aefeSPatrick Mooney * _CLASS_ENTRY + + + + 904c87aefeSPatrick Mooney * _INIT + + + + 914c87aefeSPatrick Mooney * _EMPTY + + + + 924c87aefeSPatrick Mooney * _FIRST + + + + 934c87aefeSPatrick Mooney * _NEXT + + + + 944c87aefeSPatrick Mooney * _PREV - + - + 954c87aefeSPatrick Mooney * _LAST - - + + 964c87aefeSPatrick Mooney * _FOREACH + + + + 974c87aefeSPatrick Mooney * _FOREACH_FROM + + + + 984c87aefeSPatrick Mooney * _FOREACH_SAFE + + + + 994c87aefeSPatrick Mooney * _FOREACH_FROM_SAFE + + + + 1004c87aefeSPatrick Mooney * _FOREACH_REVERSE - - - + 1014c87aefeSPatrick Mooney * _FOREACH_REVERSE_FROM - - - + 1024c87aefeSPatrick Mooney * _FOREACH_REVERSE_SAFE - - - + 1034c87aefeSPatrick Mooney * _FOREACH_REVERSE_FROM_SAFE - - - + 1044c87aefeSPatrick Mooney * _INSERT_HEAD + + + + 1054c87aefeSPatrick Mooney * _INSERT_BEFORE - + - + 1064c87aefeSPatrick Mooney * _INSERT_AFTER + + + + 1074c87aefeSPatrick Mooney * _INSERT_TAIL - - + + 1084c87aefeSPatrick Mooney * _CONCAT s s + + 1094c87aefeSPatrick Mooney * _REMOVE_AFTER + - + - 1104c87aefeSPatrick Mooney * _REMOVE_HEAD + - + - 1114c87aefeSPatrick Mooney * _REMOVE s + s + 1124c87aefeSPatrick Mooney * _SWAP + + + + 1134c87aefeSPatrick Mooney * 1144c87aefeSPatrick Mooney */ 1154c87aefeSPatrick Mooney #ifdef QUEUE_MACRO_DEBUG 1164c87aefeSPatrick Mooney /* Store the last 2 places the queue element or head was altered */ 1174c87aefeSPatrick Mooney struct qm_trace { 1184c87aefeSPatrick Mooney unsigned long lastline; 1194c87aefeSPatrick Mooney unsigned long prevline; 1204c87aefeSPatrick Mooney const char *lastfile; 1214c87aefeSPatrick Mooney const char *prevfile; 1224c87aefeSPatrick Mooney }; 1234c87aefeSPatrick Mooney 1244c87aefeSPatrick Mooney #define TRACEBUF struct qm_trace trace; 1254c87aefeSPatrick Mooney #define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } , 1264c87aefeSPatrick Mooney #define TRASHIT(x) do {(x) = (void *)-1;} while (0) 1274c87aefeSPatrick Mooney #define QMD_SAVELINK(name, link) void **name = (void *)&(link) 1284c87aefeSPatrick Mooney 1294c87aefeSPatrick Mooney #define QMD_TRACE_HEAD(head) do { \ 1304c87aefeSPatrick Mooney (head)->trace.prevline = (head)->trace.lastline; \ 1314c87aefeSPatrick Mooney (head)->trace.prevfile = (head)->trace.lastfile; \ 1324c87aefeSPatrick Mooney (head)->trace.lastline = __LINE__; \ 1334c87aefeSPatrick Mooney (head)->trace.lastfile = __FILE__; \ 1344c87aefeSPatrick Mooney } while (0) 1354c87aefeSPatrick Mooney 1364c87aefeSPatrick Mooney #define QMD_TRACE_ELEM(elem) do { \ 1374c87aefeSPatrick Mooney (elem)->trace.prevline = (elem)->trace.lastline; \ 1384c87aefeSPatrick Mooney (elem)->trace.prevfile = (elem)->trace.lastfile; \ 1394c87aefeSPatrick Mooney (elem)->trace.lastline = __LINE__; \ 1404c87aefeSPatrick Mooney (elem)->trace.lastfile = __FILE__; \ 1414c87aefeSPatrick Mooney } while (0) 1424c87aefeSPatrick Mooney 1434c87aefeSPatrick Mooney #else 1444c87aefeSPatrick Mooney #define QMD_TRACE_ELEM(elem) 1454c87aefeSPatrick Mooney #define QMD_TRACE_HEAD(head) 1464c87aefeSPatrick Mooney #define QMD_SAVELINK(name, link) 1474c87aefeSPatrick Mooney #define TRACEBUF 1484c87aefeSPatrick Mooney #define TRACEBUF_INITIALIZER 1494c87aefeSPatrick Mooney #define TRASHIT(x) 1504c87aefeSPatrick Mooney #endif /* QUEUE_MACRO_DEBUG */ 1514c87aefeSPatrick Mooney 1524c87aefeSPatrick Mooney #ifdef __cplusplus 1534c87aefeSPatrick Mooney /* 1544c87aefeSPatrick Mooney * In C++ there can be structure lists and class lists: 1554c87aefeSPatrick Mooney */ 1564c87aefeSPatrick Mooney #define QUEUE_TYPEOF(type) type 1574c87aefeSPatrick Mooney #else 1584c87aefeSPatrick Mooney #define QUEUE_TYPEOF(type) struct type 1594c87aefeSPatrick Mooney #endif 1604c87aefeSPatrick Mooney 1614c87aefeSPatrick Mooney /* 1624c87aefeSPatrick Mooney * Singly-linked List declarations. 1634c87aefeSPatrick Mooney */ 1644c87aefeSPatrick Mooney #define SLIST_HEAD(name, type) \ 1654c87aefeSPatrick Mooney struct name { \ 1664c87aefeSPatrick Mooney struct type *slh_first; /* first element */ \ 1674c87aefeSPatrick Mooney } 1684c87aefeSPatrick Mooney 1694c87aefeSPatrick Mooney #define SLIST_CLASS_HEAD(name, type) \ 1704c87aefeSPatrick Mooney struct name { \ 1714c87aefeSPatrick Mooney class type *slh_first; /* first element */ \ 1724c87aefeSPatrick Mooney } 1734c87aefeSPatrick Mooney 1744c87aefeSPatrick Mooney #define SLIST_HEAD_INITIALIZER(head) \ 1754c87aefeSPatrick Mooney { NULL } 1764c87aefeSPatrick Mooney 1774c87aefeSPatrick Mooney #define SLIST_ENTRY(type) \ 1784c87aefeSPatrick Mooney struct { \ 1794c87aefeSPatrick Mooney struct type *sle_next; /* next element */ \ 1804c87aefeSPatrick Mooney } 1814c87aefeSPatrick Mooney 1824c87aefeSPatrick Mooney #define SLIST_CLASS_ENTRY(type) \ 1834c87aefeSPatrick Mooney struct { \ 1844c87aefeSPatrick Mooney class type *sle_next; /* next element */ \ 1854c87aefeSPatrick Mooney } 1864c87aefeSPatrick Mooney 1874c87aefeSPatrick Mooney /* 1884c87aefeSPatrick Mooney * Singly-linked List functions. 1894c87aefeSPatrick Mooney */ 1904c87aefeSPatrick Mooney #define SLIST_CONCAT(head1, head2, type, field) do { \ 1914c87aefeSPatrick Mooney QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ 1924c87aefeSPatrick Mooney if (curelm == NULL) { \ 1934c87aefeSPatrick Mooney if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ 1944c87aefeSPatrick Mooney SLIST_INIT(head2); \ 1954c87aefeSPatrick Mooney } else if (SLIST_FIRST(head2) != NULL) { \ 1964c87aefeSPatrick Mooney while (SLIST_NEXT(curelm, field) != NULL) \ 1974c87aefeSPatrick Mooney curelm = SLIST_NEXT(curelm, field); \ 1984c87aefeSPatrick Mooney SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ 1994c87aefeSPatrick Mooney SLIST_INIT(head2); \ 2004c87aefeSPatrick Mooney } \ 2014c87aefeSPatrick Mooney } while (0) 2024c87aefeSPatrick Mooney 2034c87aefeSPatrick Mooney #define SLIST_EMPTY(head) ((head)->slh_first == NULL) 2044c87aefeSPatrick Mooney 2054c87aefeSPatrick Mooney #define SLIST_FIRST(head) ((head)->slh_first) 2064c87aefeSPatrick Mooney 2074c87aefeSPatrick Mooney #define SLIST_FOREACH(var, head, field) \ 2084c87aefeSPatrick Mooney for ((var) = SLIST_FIRST((head)); \ 2094c87aefeSPatrick Mooney (var); \ 2104c87aefeSPatrick Mooney (var) = SLIST_NEXT((var), field)) 2114c87aefeSPatrick Mooney 2124c87aefeSPatrick Mooney #define SLIST_FOREACH_FROM(var, head, field) \ 2134c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 2144c87aefeSPatrick Mooney (var); \ 2154c87aefeSPatrick Mooney (var) = SLIST_NEXT((var), field)) 2164c87aefeSPatrick Mooney 2174c87aefeSPatrick Mooney #define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 2184c87aefeSPatrick Mooney for ((var) = SLIST_FIRST((head)); \ 2194c87aefeSPatrick Mooney (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 2204c87aefeSPatrick Mooney (var) = (tvar)) 2214c87aefeSPatrick Mooney 2224c87aefeSPatrick Mooney #define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 2234c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 2244c87aefeSPatrick Mooney (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 2254c87aefeSPatrick Mooney (var) = (tvar)) 2264c87aefeSPatrick Mooney 2274c87aefeSPatrick Mooney #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 2284c87aefeSPatrick Mooney for ((varp) = &SLIST_FIRST((head)); \ 2294c87aefeSPatrick Mooney ((var) = *(varp)) != NULL; \ 2304c87aefeSPatrick Mooney (varp) = &SLIST_NEXT((var), field)) 2314c87aefeSPatrick Mooney 2324c87aefeSPatrick Mooney #define SLIST_INIT(head) do { \ 2334c87aefeSPatrick Mooney SLIST_FIRST((head)) = NULL; \ 2344c87aefeSPatrick Mooney } while (0) 2354c87aefeSPatrick Mooney 2364c87aefeSPatrick Mooney #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 2374c87aefeSPatrick Mooney SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 2384c87aefeSPatrick Mooney SLIST_NEXT((slistelm), field) = (elm); \ 2394c87aefeSPatrick Mooney } while (0) 2404c87aefeSPatrick Mooney 2414c87aefeSPatrick Mooney #define SLIST_INSERT_HEAD(head, elm, field) do { \ 2424c87aefeSPatrick Mooney SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 2434c87aefeSPatrick Mooney SLIST_FIRST((head)) = (elm); \ 2444c87aefeSPatrick Mooney } while (0) 2454c87aefeSPatrick Mooney 2464c87aefeSPatrick Mooney #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 2474c87aefeSPatrick Mooney 2484c87aefeSPatrick Mooney #define SLIST_REMOVE(head, elm, type, field) do { \ 2494c87aefeSPatrick Mooney QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ 2504c87aefeSPatrick Mooney if (SLIST_FIRST((head)) == (elm)) { \ 2514c87aefeSPatrick Mooney SLIST_REMOVE_HEAD((head), field); \ 2524c87aefeSPatrick Mooney } \ 2534c87aefeSPatrick Mooney else { \ 2544c87aefeSPatrick Mooney QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \ 2554c87aefeSPatrick Mooney while (SLIST_NEXT(curelm, field) != (elm)) \ 2564c87aefeSPatrick Mooney curelm = SLIST_NEXT(curelm, field); \ 2574c87aefeSPatrick Mooney SLIST_REMOVE_AFTER(curelm, field); \ 2584c87aefeSPatrick Mooney } \ 2594c87aefeSPatrick Mooney TRASHIT(*oldnext); \ 2604c87aefeSPatrick Mooney } while (0) 2614c87aefeSPatrick Mooney 2624c87aefeSPatrick Mooney #define SLIST_REMOVE_AFTER(elm, field) do { \ 2634c87aefeSPatrick Mooney SLIST_NEXT(elm, field) = \ 2644c87aefeSPatrick Mooney SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 2654c87aefeSPatrick Mooney } while (0) 2664c87aefeSPatrick Mooney 2674c87aefeSPatrick Mooney #define SLIST_REMOVE_HEAD(head, field) do { \ 2684c87aefeSPatrick Mooney SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 2694c87aefeSPatrick Mooney } while (0) 2704c87aefeSPatrick Mooney 2714c87aefeSPatrick Mooney #define SLIST_SWAP(head1, head2, type) do { \ 2724c87aefeSPatrick Mooney QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ 2734c87aefeSPatrick Mooney SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 2744c87aefeSPatrick Mooney SLIST_FIRST(head2) = swap_first; \ 2754c87aefeSPatrick Mooney } while (0) 2764c87aefeSPatrick Mooney 2774c87aefeSPatrick Mooney /* 2784c87aefeSPatrick Mooney * Singly-linked Tail queue declarations. 2794c87aefeSPatrick Mooney */ 2804c87aefeSPatrick Mooney #define STAILQ_HEAD(name, type) \ 2814c87aefeSPatrick Mooney struct name { \ 2824c87aefeSPatrick Mooney struct type *stqh_first;/* first element */ \ 2834c87aefeSPatrick Mooney struct type **stqh_last;/* addr of last next element */ \ 2844c87aefeSPatrick Mooney } 2854c87aefeSPatrick Mooney 2864c87aefeSPatrick Mooney #define STAILQ_CLASS_HEAD(name, type) \ 2874c87aefeSPatrick Mooney struct name { \ 2884c87aefeSPatrick Mooney class type *stqh_first; /* first element */ \ 2894c87aefeSPatrick Mooney class type **stqh_last; /* addr of last next element */ \ 2904c87aefeSPatrick Mooney } 2914c87aefeSPatrick Mooney 2924c87aefeSPatrick Mooney #define STAILQ_HEAD_INITIALIZER(head) \ 2934c87aefeSPatrick Mooney { NULL, &(head).stqh_first } 2944c87aefeSPatrick Mooney 2954c87aefeSPatrick Mooney #define STAILQ_ENTRY(type) \ 2964c87aefeSPatrick Mooney struct { \ 2974c87aefeSPatrick Mooney struct type *stqe_next; /* next element */ \ 2984c87aefeSPatrick Mooney } 2994c87aefeSPatrick Mooney 3004c87aefeSPatrick Mooney #define STAILQ_CLASS_ENTRY(type) \ 3014c87aefeSPatrick Mooney struct { \ 3024c87aefeSPatrick Mooney class type *stqe_next; /* next element */ \ 3034c87aefeSPatrick Mooney } 3044c87aefeSPatrick Mooney 3054c87aefeSPatrick Mooney /* 3064c87aefeSPatrick Mooney * Singly-linked Tail queue functions. 3074c87aefeSPatrick Mooney */ 3084c87aefeSPatrick Mooney #define STAILQ_CONCAT(head1, head2) do { \ 3094c87aefeSPatrick Mooney if (!STAILQ_EMPTY((head2))) { \ 3104c87aefeSPatrick Mooney *(head1)->stqh_last = (head2)->stqh_first; \ 3114c87aefeSPatrick Mooney (head1)->stqh_last = (head2)->stqh_last; \ 3124c87aefeSPatrick Mooney STAILQ_INIT((head2)); \ 3134c87aefeSPatrick Mooney } \ 3144c87aefeSPatrick Mooney } while (0) 3154c87aefeSPatrick Mooney 3164c87aefeSPatrick Mooney #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 3174c87aefeSPatrick Mooney 3184c87aefeSPatrick Mooney #define STAILQ_FIRST(head) ((head)->stqh_first) 3194c87aefeSPatrick Mooney 3204c87aefeSPatrick Mooney #define STAILQ_FOREACH(var, head, field) \ 3214c87aefeSPatrick Mooney for((var) = STAILQ_FIRST((head)); \ 3224c87aefeSPatrick Mooney (var); \ 3234c87aefeSPatrick Mooney (var) = STAILQ_NEXT((var), field)) 3244c87aefeSPatrick Mooney 3254c87aefeSPatrick Mooney #define STAILQ_FOREACH_FROM(var, head, field) \ 3264c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 3274c87aefeSPatrick Mooney (var); \ 3284c87aefeSPatrick Mooney (var) = STAILQ_NEXT((var), field)) 3294c87aefeSPatrick Mooney 3304c87aefeSPatrick Mooney #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 3314c87aefeSPatrick Mooney for ((var) = STAILQ_FIRST((head)); \ 3324c87aefeSPatrick Mooney (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 3334c87aefeSPatrick Mooney (var) = (tvar)) 3344c87aefeSPatrick Mooney 3354c87aefeSPatrick Mooney #define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 3364c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 3374c87aefeSPatrick Mooney (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 3384c87aefeSPatrick Mooney (var) = (tvar)) 3394c87aefeSPatrick Mooney 3404c87aefeSPatrick Mooney #define STAILQ_INIT(head) do { \ 3414c87aefeSPatrick Mooney STAILQ_FIRST((head)) = NULL; \ 3424c87aefeSPatrick Mooney (head)->stqh_last = &STAILQ_FIRST((head)); \ 3434c87aefeSPatrick Mooney } while (0) 3444c87aefeSPatrick Mooney 3454c87aefeSPatrick Mooney #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 3464c87aefeSPatrick Mooney if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 3474c87aefeSPatrick Mooney (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 3484c87aefeSPatrick Mooney STAILQ_NEXT((tqelm), field) = (elm); \ 3494c87aefeSPatrick Mooney } while (0) 3504c87aefeSPatrick Mooney 3514c87aefeSPatrick Mooney #define STAILQ_INSERT_HEAD(head, elm, field) do { \ 3524c87aefeSPatrick Mooney if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 3534c87aefeSPatrick Mooney (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 3544c87aefeSPatrick Mooney STAILQ_FIRST((head)) = (elm); \ 3554c87aefeSPatrick Mooney } while (0) 3564c87aefeSPatrick Mooney 3574c87aefeSPatrick Mooney #define STAILQ_INSERT_TAIL(head, elm, field) do { \ 3584c87aefeSPatrick Mooney STAILQ_NEXT((elm), field) = NULL; \ 3594c87aefeSPatrick Mooney *(head)->stqh_last = (elm); \ 3604c87aefeSPatrick Mooney (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 3614c87aefeSPatrick Mooney } while (0) 3624c87aefeSPatrick Mooney 3634c87aefeSPatrick Mooney #define STAILQ_LAST(head, type, field) \ 3644c87aefeSPatrick Mooney (STAILQ_EMPTY((head)) ? NULL : \ 3654c87aefeSPatrick Mooney __containerof((head)->stqh_last, \ 3664c87aefeSPatrick Mooney QUEUE_TYPEOF(type), field.stqe_next)) 3674c87aefeSPatrick Mooney 3684c87aefeSPatrick Mooney #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 3694c87aefeSPatrick Mooney 3704c87aefeSPatrick Mooney #define STAILQ_REMOVE(head, elm, type, field) do { \ 3714c87aefeSPatrick Mooney QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ 3724c87aefeSPatrick Mooney if (STAILQ_FIRST((head)) == (elm)) { \ 3734c87aefeSPatrick Mooney STAILQ_REMOVE_HEAD((head), field); \ 3744c87aefeSPatrick Mooney } \ 3754c87aefeSPatrick Mooney else { \ 3764c87aefeSPatrick Mooney QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ 3774c87aefeSPatrick Mooney while (STAILQ_NEXT(curelm, field) != (elm)) \ 3784c87aefeSPatrick Mooney curelm = STAILQ_NEXT(curelm, field); \ 3794c87aefeSPatrick Mooney STAILQ_REMOVE_AFTER(head, curelm, field); \ 3804c87aefeSPatrick Mooney } \ 3814c87aefeSPatrick Mooney TRASHIT(*oldnext); \ 3824c87aefeSPatrick Mooney } while (0) 3834c87aefeSPatrick Mooney 3844c87aefeSPatrick Mooney #define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 3854c87aefeSPatrick Mooney if ((STAILQ_NEXT(elm, field) = \ 3864c87aefeSPatrick Mooney STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 3874c87aefeSPatrick Mooney (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 3884c87aefeSPatrick Mooney } while (0) 3894c87aefeSPatrick Mooney 3904c87aefeSPatrick Mooney #define STAILQ_REMOVE_HEAD(head, field) do { \ 3914c87aefeSPatrick Mooney if ((STAILQ_FIRST((head)) = \ 3924c87aefeSPatrick Mooney STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 3934c87aefeSPatrick Mooney (head)->stqh_last = &STAILQ_FIRST((head)); \ 3944c87aefeSPatrick Mooney } while (0) 3954c87aefeSPatrick Mooney 3964c87aefeSPatrick Mooney #define STAILQ_SWAP(head1, head2, type) do { \ 3974c87aefeSPatrick Mooney QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ 3984c87aefeSPatrick Mooney QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ 3994c87aefeSPatrick Mooney STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 4004c87aefeSPatrick Mooney (head1)->stqh_last = (head2)->stqh_last; \ 4014c87aefeSPatrick Mooney STAILQ_FIRST(head2) = swap_first; \ 4024c87aefeSPatrick Mooney (head2)->stqh_last = swap_last; \ 4034c87aefeSPatrick Mooney if (STAILQ_EMPTY(head1)) \ 4044c87aefeSPatrick Mooney (head1)->stqh_last = &STAILQ_FIRST(head1); \ 4054c87aefeSPatrick Mooney if (STAILQ_EMPTY(head2)) \ 4064c87aefeSPatrick Mooney (head2)->stqh_last = &STAILQ_FIRST(head2); \ 4074c87aefeSPatrick Mooney } while (0) 4084c87aefeSPatrick Mooney 4094c87aefeSPatrick Mooney 4104c87aefeSPatrick Mooney /* 4114c87aefeSPatrick Mooney * List declarations. 4124c87aefeSPatrick Mooney */ 4134c87aefeSPatrick Mooney #define LIST_HEAD(name, type) \ 4144c87aefeSPatrick Mooney struct name { \ 4154c87aefeSPatrick Mooney struct type *lh_first; /* first element */ \ 4164c87aefeSPatrick Mooney } 4174c87aefeSPatrick Mooney 4184c87aefeSPatrick Mooney #define LIST_CLASS_HEAD(name, type) \ 4194c87aefeSPatrick Mooney struct name { \ 4204c87aefeSPatrick Mooney class type *lh_first; /* first element */ \ 4214c87aefeSPatrick Mooney } 4224c87aefeSPatrick Mooney 4234c87aefeSPatrick Mooney #define LIST_HEAD_INITIALIZER(head) \ 4244c87aefeSPatrick Mooney { NULL } 4254c87aefeSPatrick Mooney 4264c87aefeSPatrick Mooney #define LIST_ENTRY(type) \ 4274c87aefeSPatrick Mooney struct { \ 4284c87aefeSPatrick Mooney struct type *le_next; /* next element */ \ 4294c87aefeSPatrick Mooney struct type **le_prev; /* address of previous next element */ \ 4304c87aefeSPatrick Mooney } 4314c87aefeSPatrick Mooney 4324c87aefeSPatrick Mooney #define LIST_CLASS_ENTRY(type) \ 4334c87aefeSPatrick Mooney struct { \ 4344c87aefeSPatrick Mooney class type *le_next; /* next element */ \ 4354c87aefeSPatrick Mooney class type **le_prev; /* address of previous next element */ \ 4364c87aefeSPatrick Mooney } 4374c87aefeSPatrick Mooney 4384c87aefeSPatrick Mooney /* 4394c87aefeSPatrick Mooney * List functions. 4404c87aefeSPatrick Mooney */ 4414c87aefeSPatrick Mooney 4424c87aefeSPatrick Mooney #if (defined(_KERNEL) && defined(INVARIANTS)) 4434c87aefeSPatrick Mooney #define QMD_LIST_CHECK_HEAD(head, field) do { \ 4444c87aefeSPatrick Mooney if (LIST_FIRST((head)) != NULL && \ 4454c87aefeSPatrick Mooney LIST_FIRST((head))->field.le_prev != \ 4464c87aefeSPatrick Mooney &LIST_FIRST((head))) \ 4474c87aefeSPatrick Mooney panic("Bad list head %p first->prev != head", (head)); \ 4484c87aefeSPatrick Mooney } while (0) 4494c87aefeSPatrick Mooney 4504c87aefeSPatrick Mooney #define QMD_LIST_CHECK_NEXT(elm, field) do { \ 4514c87aefeSPatrick Mooney if (LIST_NEXT((elm), field) != NULL && \ 4524c87aefeSPatrick Mooney LIST_NEXT((elm), field)->field.le_prev != \ 4534c87aefeSPatrick Mooney &((elm)->field.le_next)) \ 4544c87aefeSPatrick Mooney panic("Bad link elm %p next->prev != elm", (elm)); \ 4554c87aefeSPatrick Mooney } while (0) 4564c87aefeSPatrick Mooney 4574c87aefeSPatrick Mooney #define QMD_LIST_CHECK_PREV(elm, field) do { \ 4584c87aefeSPatrick Mooney if (*(elm)->field.le_prev != (elm)) \ 4594c87aefeSPatrick Mooney panic("Bad link elm %p prev->next != elm", (elm)); \ 4604c87aefeSPatrick Mooney } while (0) 4614c87aefeSPatrick Mooney #else 4624c87aefeSPatrick Mooney #define QMD_LIST_CHECK_HEAD(head, field) 4634c87aefeSPatrick Mooney #define QMD_LIST_CHECK_NEXT(elm, field) 4644c87aefeSPatrick Mooney #define QMD_LIST_CHECK_PREV(elm, field) 4654c87aefeSPatrick Mooney #endif /* (_KERNEL && INVARIANTS) */ 4664c87aefeSPatrick Mooney 4674c87aefeSPatrick Mooney #define LIST_CONCAT(head1, head2, type, field) do { \ 4684c87aefeSPatrick Mooney QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ 4694c87aefeSPatrick Mooney if (curelm == NULL) { \ 4704c87aefeSPatrick Mooney if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ 4714c87aefeSPatrick Mooney LIST_FIRST(head2)->field.le_prev = \ 4724c87aefeSPatrick Mooney &LIST_FIRST((head1)); \ 4734c87aefeSPatrick Mooney LIST_INIT(head2); \ 4744c87aefeSPatrick Mooney } \ 4754c87aefeSPatrick Mooney } else if (LIST_FIRST(head2) != NULL) { \ 4764c87aefeSPatrick Mooney while (LIST_NEXT(curelm, field) != NULL) \ 4774c87aefeSPatrick Mooney curelm = LIST_NEXT(curelm, field); \ 4784c87aefeSPatrick Mooney LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ 4794c87aefeSPatrick Mooney LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \ 4804c87aefeSPatrick Mooney LIST_INIT(head2); \ 4814c87aefeSPatrick Mooney } \ 4824c87aefeSPatrick Mooney } while (0) 4834c87aefeSPatrick Mooney 4844c87aefeSPatrick Mooney #define LIST_EMPTY(head) ((head)->lh_first == NULL) 4854c87aefeSPatrick Mooney 4864c87aefeSPatrick Mooney #define LIST_FIRST(head) ((head)->lh_first) 4874c87aefeSPatrick Mooney 4884c87aefeSPatrick Mooney #define LIST_FOREACH(var, head, field) \ 4894c87aefeSPatrick Mooney for ((var) = LIST_FIRST((head)); \ 4904c87aefeSPatrick Mooney (var); \ 4914c87aefeSPatrick Mooney (var) = LIST_NEXT((var), field)) 4924c87aefeSPatrick Mooney 4934c87aefeSPatrick Mooney #define LIST_FOREACH_FROM(var, head, field) \ 4944c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 4954c87aefeSPatrick Mooney (var); \ 4964c87aefeSPatrick Mooney (var) = LIST_NEXT((var), field)) 4974c87aefeSPatrick Mooney 4984c87aefeSPatrick Mooney #define LIST_FOREACH_SAFE(var, head, field, tvar) \ 4994c87aefeSPatrick Mooney for ((var) = LIST_FIRST((head)); \ 5004c87aefeSPatrick Mooney (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 5014c87aefeSPatrick Mooney (var) = (tvar)) 5024c87aefeSPatrick Mooney 5034c87aefeSPatrick Mooney #define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 5044c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 5054c87aefeSPatrick Mooney (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 5064c87aefeSPatrick Mooney (var) = (tvar)) 5074c87aefeSPatrick Mooney 5084c87aefeSPatrick Mooney #define LIST_INIT(head) do { \ 5094c87aefeSPatrick Mooney LIST_FIRST((head)) = NULL; \ 5104c87aefeSPatrick Mooney } while (0) 5114c87aefeSPatrick Mooney 5124c87aefeSPatrick Mooney #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 5134c87aefeSPatrick Mooney QMD_LIST_CHECK_NEXT(listelm, field); \ 5144c87aefeSPatrick Mooney if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 5154c87aefeSPatrick Mooney LIST_NEXT((listelm), field)->field.le_prev = \ 5164c87aefeSPatrick Mooney &LIST_NEXT((elm), field); \ 5174c87aefeSPatrick Mooney LIST_NEXT((listelm), field) = (elm); \ 5184c87aefeSPatrick Mooney (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 5194c87aefeSPatrick Mooney } while (0) 5204c87aefeSPatrick Mooney 5214c87aefeSPatrick Mooney #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 5224c87aefeSPatrick Mooney QMD_LIST_CHECK_PREV(listelm, field); \ 5234c87aefeSPatrick Mooney (elm)->field.le_prev = (listelm)->field.le_prev; \ 5244c87aefeSPatrick Mooney LIST_NEXT((elm), field) = (listelm); \ 5254c87aefeSPatrick Mooney *(listelm)->field.le_prev = (elm); \ 5264c87aefeSPatrick Mooney (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 5274c87aefeSPatrick Mooney } while (0) 5284c87aefeSPatrick Mooney 5294c87aefeSPatrick Mooney #define LIST_INSERT_HEAD(head, elm, field) do { \ 5304c87aefeSPatrick Mooney QMD_LIST_CHECK_HEAD((head), field); \ 5314c87aefeSPatrick Mooney if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 5324c87aefeSPatrick Mooney LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 5334c87aefeSPatrick Mooney LIST_FIRST((head)) = (elm); \ 5344c87aefeSPatrick Mooney (elm)->field.le_prev = &LIST_FIRST((head)); \ 5354c87aefeSPatrick Mooney } while (0) 5364c87aefeSPatrick Mooney 5374c87aefeSPatrick Mooney #define LIST_NEXT(elm, field) ((elm)->field.le_next) 5384c87aefeSPatrick Mooney 5394c87aefeSPatrick Mooney #define LIST_PREV(elm, head, type, field) \ 5404c87aefeSPatrick Mooney ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 5414c87aefeSPatrick Mooney __containerof((elm)->field.le_prev, \ 5424c87aefeSPatrick Mooney QUEUE_TYPEOF(type), field.le_next)) 5434c87aefeSPatrick Mooney 5444c87aefeSPatrick Mooney #define LIST_REMOVE(elm, field) do { \ 5454c87aefeSPatrick Mooney QMD_SAVELINK(oldnext, (elm)->field.le_next); \ 5464c87aefeSPatrick Mooney QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ 5474c87aefeSPatrick Mooney QMD_LIST_CHECK_NEXT(elm, field); \ 5484c87aefeSPatrick Mooney QMD_LIST_CHECK_PREV(elm, field); \ 5494c87aefeSPatrick Mooney if (LIST_NEXT((elm), field) != NULL) \ 5504c87aefeSPatrick Mooney LIST_NEXT((elm), field)->field.le_prev = \ 5514c87aefeSPatrick Mooney (elm)->field.le_prev; \ 5524c87aefeSPatrick Mooney *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 5534c87aefeSPatrick Mooney TRASHIT(*oldnext); \ 5544c87aefeSPatrick Mooney TRASHIT(*oldprev); \ 5554c87aefeSPatrick Mooney } while (0) 5564c87aefeSPatrick Mooney 5574c87aefeSPatrick Mooney #define LIST_SWAP(head1, head2, type, field) do { \ 5584c87aefeSPatrick Mooney QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 5594c87aefeSPatrick Mooney LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 5604c87aefeSPatrick Mooney LIST_FIRST((head2)) = swap_tmp; \ 5614c87aefeSPatrick Mooney if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 5624c87aefeSPatrick Mooney swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 5634c87aefeSPatrick Mooney if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 5644c87aefeSPatrick Mooney swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 5654c87aefeSPatrick Mooney } while (0) 5664c87aefeSPatrick Mooney 5674c87aefeSPatrick Mooney /* 5684c87aefeSPatrick Mooney * Tail queue declarations. 5694c87aefeSPatrick Mooney */ 5704c87aefeSPatrick Mooney #define TAILQ_HEAD(name, type) \ 5714c87aefeSPatrick Mooney struct name { \ 5724c87aefeSPatrick Mooney struct type *tqh_first; /* first element */ \ 5734c87aefeSPatrick Mooney struct type **tqh_last; /* addr of last next element */ \ 5744c87aefeSPatrick Mooney TRACEBUF \ 5754c87aefeSPatrick Mooney } 5764c87aefeSPatrick Mooney 5774c87aefeSPatrick Mooney #define TAILQ_CLASS_HEAD(name, type) \ 5784c87aefeSPatrick Mooney struct name { \ 5794c87aefeSPatrick Mooney class type *tqh_first; /* first element */ \ 5804c87aefeSPatrick Mooney class type **tqh_last; /* addr of last next element */ \ 5814c87aefeSPatrick Mooney TRACEBUF \ 5824c87aefeSPatrick Mooney } 5834c87aefeSPatrick Mooney 5844c87aefeSPatrick Mooney #define TAILQ_HEAD_INITIALIZER(head) \ 5854c87aefeSPatrick Mooney { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } 5864c87aefeSPatrick Mooney 5874c87aefeSPatrick Mooney #define TAILQ_ENTRY(type) \ 5884c87aefeSPatrick Mooney struct { \ 5894c87aefeSPatrick Mooney struct type *tqe_next; /* next element */ \ 5904c87aefeSPatrick Mooney struct type **tqe_prev; /* address of previous next element */ \ 5914c87aefeSPatrick Mooney TRACEBUF \ 5924c87aefeSPatrick Mooney } 5934c87aefeSPatrick Mooney 5944c87aefeSPatrick Mooney #define TAILQ_CLASS_ENTRY(type) \ 5954c87aefeSPatrick Mooney struct { \ 5964c87aefeSPatrick Mooney class type *tqe_next; /* next element */ \ 5974c87aefeSPatrick Mooney class type **tqe_prev; /* address of previous next element */ \ 5984c87aefeSPatrick Mooney TRACEBUF \ 5994c87aefeSPatrick Mooney } 6004c87aefeSPatrick Mooney 6014c87aefeSPatrick Mooney /* 6024c87aefeSPatrick Mooney * Tail queue functions. 6034c87aefeSPatrick Mooney */ 6044c87aefeSPatrick Mooney #if (defined(_KERNEL) && defined(INVARIANTS)) 6054c87aefeSPatrick Mooney #define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 6064c87aefeSPatrick Mooney if (!TAILQ_EMPTY(head) && \ 6074c87aefeSPatrick Mooney TAILQ_FIRST((head))->field.tqe_prev != \ 6084c87aefeSPatrick Mooney &TAILQ_FIRST((head))) \ 6094c87aefeSPatrick Mooney panic("Bad tailq head %p first->prev != head", (head)); \ 6104c87aefeSPatrick Mooney } while (0) 6114c87aefeSPatrick Mooney 6124c87aefeSPatrick Mooney #define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 6134c87aefeSPatrick Mooney if (*(head)->tqh_last != NULL) \ 6144c87aefeSPatrick Mooney panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 6154c87aefeSPatrick Mooney } while (0) 6164c87aefeSPatrick Mooney 6174c87aefeSPatrick Mooney #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 6184c87aefeSPatrick Mooney if (TAILQ_NEXT((elm), field) != NULL && \ 6194c87aefeSPatrick Mooney TAILQ_NEXT((elm), field)->field.tqe_prev != \ 6204c87aefeSPatrick Mooney &((elm)->field.tqe_next)) \ 6214c87aefeSPatrick Mooney panic("Bad link elm %p next->prev != elm", (elm)); \ 6224c87aefeSPatrick Mooney } while (0) 6234c87aefeSPatrick Mooney 6244c87aefeSPatrick Mooney #define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 6254c87aefeSPatrick Mooney if (*(elm)->field.tqe_prev != (elm)) \ 6264c87aefeSPatrick Mooney panic("Bad link elm %p prev->next != elm", (elm)); \ 6274c87aefeSPatrick Mooney } while (0) 6284c87aefeSPatrick Mooney #else 6294c87aefeSPatrick Mooney #define QMD_TAILQ_CHECK_HEAD(head, field) 6304c87aefeSPatrick Mooney #define QMD_TAILQ_CHECK_TAIL(head, headname) 6314c87aefeSPatrick Mooney #define QMD_TAILQ_CHECK_NEXT(elm, field) 6324c87aefeSPatrick Mooney #define QMD_TAILQ_CHECK_PREV(elm, field) 6334c87aefeSPatrick Mooney #endif /* (_KERNEL && INVARIANTS) */ 6344c87aefeSPatrick Mooney 6354c87aefeSPatrick Mooney #define TAILQ_CONCAT(head1, head2, field) do { \ 6364c87aefeSPatrick Mooney if (!TAILQ_EMPTY(head2)) { \ 6374c87aefeSPatrick Mooney *(head1)->tqh_last = (head2)->tqh_first; \ 6384c87aefeSPatrick Mooney (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 6394c87aefeSPatrick Mooney (head1)->tqh_last = (head2)->tqh_last; \ 6404c87aefeSPatrick Mooney TAILQ_INIT((head2)); \ 6414c87aefeSPatrick Mooney QMD_TRACE_HEAD(head1); \ 6424c87aefeSPatrick Mooney QMD_TRACE_HEAD(head2); \ 6434c87aefeSPatrick Mooney } \ 6444c87aefeSPatrick Mooney } while (0) 6454c87aefeSPatrick Mooney 6464c87aefeSPatrick Mooney #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 6474c87aefeSPatrick Mooney 6484c87aefeSPatrick Mooney #define TAILQ_FIRST(head) ((head)->tqh_first) 6494c87aefeSPatrick Mooney 6504c87aefeSPatrick Mooney #define TAILQ_FOREACH(var, head, field) \ 6514c87aefeSPatrick Mooney for ((var) = TAILQ_FIRST((head)); \ 6524c87aefeSPatrick Mooney (var); \ 6534c87aefeSPatrick Mooney (var) = TAILQ_NEXT((var), field)) 6544c87aefeSPatrick Mooney 6554c87aefeSPatrick Mooney #define TAILQ_FOREACH_FROM(var, head, field) \ 6564c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 6574c87aefeSPatrick Mooney (var); \ 6584c87aefeSPatrick Mooney (var) = TAILQ_NEXT((var), field)) 6594c87aefeSPatrick Mooney 6604c87aefeSPatrick Mooney #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 6614c87aefeSPatrick Mooney for ((var) = TAILQ_FIRST((head)); \ 6624c87aefeSPatrick Mooney (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 6634c87aefeSPatrick Mooney (var) = (tvar)) 6644c87aefeSPatrick Mooney 6654c87aefeSPatrick Mooney #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 6664c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 6674c87aefeSPatrick Mooney (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 6684c87aefeSPatrick Mooney (var) = (tvar)) 6694c87aefeSPatrick Mooney 6704c87aefeSPatrick Mooney #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 6714c87aefeSPatrick Mooney for ((var) = TAILQ_LAST((head), headname); \ 6724c87aefeSPatrick Mooney (var); \ 6734c87aefeSPatrick Mooney (var) = TAILQ_PREV((var), headname, field)) 6744c87aefeSPatrick Mooney 6754c87aefeSPatrick Mooney #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 6764c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 6774c87aefeSPatrick Mooney (var); \ 6784c87aefeSPatrick Mooney (var) = TAILQ_PREV((var), headname, field)) 6794c87aefeSPatrick Mooney 6804c87aefeSPatrick Mooney #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 6814c87aefeSPatrick Mooney for ((var) = TAILQ_LAST((head), headname); \ 6824c87aefeSPatrick Mooney (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 6834c87aefeSPatrick Mooney (var) = (tvar)) 6844c87aefeSPatrick Mooney 6854c87aefeSPatrick Mooney #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \ 6864c87aefeSPatrick Mooney for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 6874c87aefeSPatrick Mooney (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 6884c87aefeSPatrick Mooney (var) = (tvar)) 6894c87aefeSPatrick Mooney 6904c87aefeSPatrick Mooney #define TAILQ_INIT(head) do { \ 6914c87aefeSPatrick Mooney TAILQ_FIRST((head)) = NULL; \ 6924c87aefeSPatrick Mooney (head)->tqh_last = &TAILQ_FIRST((head)); \ 6934c87aefeSPatrick Mooney QMD_TRACE_HEAD(head); \ 6944c87aefeSPatrick Mooney } while (0) 6954c87aefeSPatrick Mooney 6964c87aefeSPatrick Mooney #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 6974c87aefeSPatrick Mooney QMD_TAILQ_CHECK_NEXT(listelm, field); \ 6984c87aefeSPatrick Mooney if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 6994c87aefeSPatrick Mooney TAILQ_NEXT((elm), field)->field.tqe_prev = \ 7004c87aefeSPatrick Mooney &TAILQ_NEXT((elm), field); \ 7014c87aefeSPatrick Mooney else { \ 7024c87aefeSPatrick Mooney (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 7034c87aefeSPatrick Mooney QMD_TRACE_HEAD(head); \ 7044c87aefeSPatrick Mooney } \ 7054c87aefeSPatrick Mooney TAILQ_NEXT((listelm), field) = (elm); \ 7064c87aefeSPatrick Mooney (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 7074c87aefeSPatrick Mooney QMD_TRACE_ELEM(&(elm)->field); \ 7084c87aefeSPatrick Mooney QMD_TRACE_ELEM(&(listelm)->field); \ 7094c87aefeSPatrick Mooney } while (0) 7104c87aefeSPatrick Mooney 7114c87aefeSPatrick Mooney #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 7124c87aefeSPatrick Mooney QMD_TAILQ_CHECK_PREV(listelm, field); \ 7134c87aefeSPatrick Mooney (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 7144c87aefeSPatrick Mooney TAILQ_NEXT((elm), field) = (listelm); \ 7154c87aefeSPatrick Mooney *(listelm)->field.tqe_prev = (elm); \ 7164c87aefeSPatrick Mooney (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 7174c87aefeSPatrick Mooney QMD_TRACE_ELEM(&(elm)->field); \ 7184c87aefeSPatrick Mooney QMD_TRACE_ELEM(&(listelm)->field); \ 7194c87aefeSPatrick Mooney } while (0) 7204c87aefeSPatrick Mooney 7214c87aefeSPatrick Mooney #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 7224c87aefeSPatrick Mooney QMD_TAILQ_CHECK_HEAD(head, field); \ 7234c87aefeSPatrick Mooney if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 7244c87aefeSPatrick Mooney TAILQ_FIRST((head))->field.tqe_prev = \ 7254c87aefeSPatrick Mooney &TAILQ_NEXT((elm), field); \ 7264c87aefeSPatrick Mooney else \ 7274c87aefeSPatrick Mooney (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 7284c87aefeSPatrick Mooney TAILQ_FIRST((head)) = (elm); \ 7294c87aefeSPatrick Mooney (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 7304c87aefeSPatrick Mooney QMD_TRACE_HEAD(head); \ 7314c87aefeSPatrick Mooney QMD_TRACE_ELEM(&(elm)->field); \ 7324c87aefeSPatrick Mooney } while (0) 7334c87aefeSPatrick Mooney 7344c87aefeSPatrick Mooney #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 7354c87aefeSPatrick Mooney QMD_TAILQ_CHECK_TAIL(head, field); \ 7364c87aefeSPatrick Mooney TAILQ_NEXT((elm), field) = NULL; \ 7374c87aefeSPatrick Mooney (elm)->field.tqe_prev = (head)->tqh_last; \ 7384c87aefeSPatrick Mooney *(head)->tqh_last = (elm); \ 7394c87aefeSPatrick Mooney (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 7404c87aefeSPatrick Mooney QMD_TRACE_HEAD(head); \ 7414c87aefeSPatrick Mooney QMD_TRACE_ELEM(&(elm)->field); \ 7424c87aefeSPatrick Mooney } while (0) 7434c87aefeSPatrick Mooney 7444c87aefeSPatrick Mooney #define TAILQ_LAST(head, headname) \ 7454c87aefeSPatrick Mooney (*(((struct headname *)((head)->tqh_last))->tqh_last)) 7464c87aefeSPatrick Mooney 7474c87aefeSPatrick Mooney #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 7484c87aefeSPatrick Mooney 7494c87aefeSPatrick Mooney #define TAILQ_PREV(elm, headname, field) \ 7504c87aefeSPatrick Mooney (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 7514c87aefeSPatrick Mooney 7524c87aefeSPatrick Mooney #define TAILQ_REMOVE(head, elm, field) do { \ 7534c87aefeSPatrick Mooney QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ 7544c87aefeSPatrick Mooney QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ 7554c87aefeSPatrick Mooney QMD_TAILQ_CHECK_NEXT(elm, field); \ 7564c87aefeSPatrick Mooney QMD_TAILQ_CHECK_PREV(elm, field); \ 7574c87aefeSPatrick Mooney if ((TAILQ_NEXT((elm), field)) != NULL) \ 7584c87aefeSPatrick Mooney TAILQ_NEXT((elm), field)->field.tqe_prev = \ 7594c87aefeSPatrick Mooney (elm)->field.tqe_prev; \ 7604c87aefeSPatrick Mooney else { \ 7614c87aefeSPatrick Mooney (head)->tqh_last = (elm)->field.tqe_prev; \ 7624c87aefeSPatrick Mooney QMD_TRACE_HEAD(head); \ 7634c87aefeSPatrick Mooney } \ 7644c87aefeSPatrick Mooney *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 7654c87aefeSPatrick Mooney TRASHIT(*oldnext); \ 7664c87aefeSPatrick Mooney TRASHIT(*oldprev); \ 7674c87aefeSPatrick Mooney QMD_TRACE_ELEM(&(elm)->field); \ 7684c87aefeSPatrick Mooney } while (0) 7694c87aefeSPatrick Mooney 7704c87aefeSPatrick Mooney #define TAILQ_SWAP(head1, head2, type, field) do { \ 7714c87aefeSPatrick Mooney QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ 7724c87aefeSPatrick Mooney QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 7734c87aefeSPatrick Mooney (head1)->tqh_first = (head2)->tqh_first; \ 7744c87aefeSPatrick Mooney (head1)->tqh_last = (head2)->tqh_last; \ 7754c87aefeSPatrick Mooney (head2)->tqh_first = swap_first; \ 7764c87aefeSPatrick Mooney (head2)->tqh_last = swap_last; \ 7774c87aefeSPatrick Mooney if ((swap_first = (head1)->tqh_first) != NULL) \ 7784c87aefeSPatrick Mooney swap_first->field.tqe_prev = &(head1)->tqh_first; \ 7794c87aefeSPatrick Mooney else \ 7804c87aefeSPatrick Mooney (head1)->tqh_last = &(head1)->tqh_first; \ 7814c87aefeSPatrick Mooney if ((swap_first = (head2)->tqh_first) != NULL) \ 7824c87aefeSPatrick Mooney swap_first->field.tqe_prev = &(head2)->tqh_first; \ 7834c87aefeSPatrick Mooney else \ 7844c87aefeSPatrick Mooney (head2)->tqh_last = &(head2)->tqh_first; \ 7854c87aefeSPatrick Mooney } while (0) 7864c87aefeSPatrick Mooney 7874c87aefeSPatrick Mooney #endif /* !_SYS_QUEUE_H_ */ 788