1205a2804SDmitri Tikhonov/*- 2205a2804SDmitri Tikhonov * SPDX-License-Identifier: BSD-3-Clause 3205a2804SDmitri Tikhonov * 4205a2804SDmitri Tikhonov * Copyright (c) 1991, 1993 5205a2804SDmitri Tikhonov * The Regents of the University of California. All rights reserved. 6205a2804SDmitri Tikhonov * 7205a2804SDmitri Tikhonov * Redistribution and use in source and binary forms, with or without 8205a2804SDmitri Tikhonov * modification, are permitted provided that the following conditions 9205a2804SDmitri Tikhonov * are met: 10205a2804SDmitri Tikhonov * 1. Redistributions of source code must retain the above copyright 11205a2804SDmitri Tikhonov * notice, this list of conditions and the following disclaimer. 12205a2804SDmitri Tikhonov * 2. Redistributions in binary form must reproduce the above copyright 13205a2804SDmitri Tikhonov * notice, this list of conditions and the following disclaimer in the 14205a2804SDmitri Tikhonov * documentation and/or other materials provided with the distribution. 15205a2804SDmitri Tikhonov * 3. Neither the name of the University nor the names of its contributors 16205a2804SDmitri Tikhonov * may be used to endorse or promote products derived from this software 17205a2804SDmitri Tikhonov * without specific prior written permission. 18205a2804SDmitri Tikhonov * 19205a2804SDmitri Tikhonov * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20205a2804SDmitri Tikhonov * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21205a2804SDmitri Tikhonov * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22205a2804SDmitri Tikhonov * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23205a2804SDmitri Tikhonov * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24205a2804SDmitri Tikhonov * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25205a2804SDmitri Tikhonov * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26205a2804SDmitri Tikhonov * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27205a2804SDmitri Tikhonov * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28205a2804SDmitri Tikhonov * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29205a2804SDmitri Tikhonov * SUCH DAMAGE. 30205a2804SDmitri Tikhonov * 31205a2804SDmitri Tikhonov * @(#)queue.h 8.5 (Berkeley) 8/20/94 32205a2804SDmitri Tikhonov * $FreeBSD$ 33205a2804SDmitri Tikhonov */ 34205a2804SDmitri Tikhonov 35205a2804SDmitri Tikhonov#ifndef _SYS_QUEUE_H_ 36205a2804SDmitri Tikhonov#define _SYS_QUEUE_H_ 37205a2804SDmitri Tikhonov 38205a2804SDmitri Tikhonov 39205a2804SDmitri Tikhonov/* 40205a2804SDmitri Tikhonov * This file defines four types of data structures: singly-linked lists, 41205a2804SDmitri Tikhonov * singly-linked tail queues, lists and tail queues. 42205a2804SDmitri Tikhonov * 43205a2804SDmitri Tikhonov * A singly-linked list is headed by a single forward pointer. The elements 44205a2804SDmitri Tikhonov * are singly linked for minimum space and pointer manipulation overhead at 45205a2804SDmitri Tikhonov * the expense of O(n) removal for arbitrary elements. New elements can be 46205a2804SDmitri Tikhonov * added to the list after an existing element or at the head of the list. 47205a2804SDmitri Tikhonov * Elements being removed from the head of the list should use the explicit 48205a2804SDmitri Tikhonov * macro for this purpose for optimum efficiency. A singly-linked list may 49205a2804SDmitri Tikhonov * only be traversed in the forward direction. Singly-linked lists are ideal 50205a2804SDmitri Tikhonov * for applications with large datasets and few or no removals or for 51205a2804SDmitri Tikhonov * implementing a LIFO queue. 52205a2804SDmitri Tikhonov * 53205a2804SDmitri Tikhonov * A singly-linked tail queue is headed by a pair of pointers, one to the 54205a2804SDmitri Tikhonov * head of the list and the other to the tail of the list. The elements are 55205a2804SDmitri Tikhonov * singly linked for minimum space and pointer manipulation overhead at the 56205a2804SDmitri Tikhonov * expense of O(n) removal for arbitrary elements. New elements can be added 57205a2804SDmitri Tikhonov * to the list after an existing element, at the head of the list, or at the 58205a2804SDmitri Tikhonov * end of the list. Elements being removed from the head of the tail queue 59205a2804SDmitri Tikhonov * should use the explicit macro for this purpose for optimum efficiency. 60205a2804SDmitri Tikhonov * A singly-linked tail queue may only be traversed in the forward direction. 61205a2804SDmitri Tikhonov * Singly-linked tail queues are ideal for applications with large datasets 62205a2804SDmitri Tikhonov * and few or no removals or for implementing a FIFO queue. 63205a2804SDmitri Tikhonov * 64205a2804SDmitri Tikhonov * A list is headed by a single forward pointer (or an array of forward 65205a2804SDmitri Tikhonov * pointers for a hash table header). The elements are doubly linked 66205a2804SDmitri Tikhonov * so that an arbitrary element can be removed without a need to 67205a2804SDmitri Tikhonov * traverse the list. New elements can be added to the list before 68205a2804SDmitri Tikhonov * or after an existing element or at the head of the list. A list 69205a2804SDmitri Tikhonov * may be traversed in either direction. 70205a2804SDmitri Tikhonov * 71205a2804SDmitri Tikhonov * A tail queue is headed by a pair of pointers, one to the head of the 72205a2804SDmitri Tikhonov * list and the other to the tail of the list. The elements are doubly 73205a2804SDmitri Tikhonov * linked so that an arbitrary element can be removed without a need to 74205a2804SDmitri Tikhonov * traverse the list. New elements can be added to the list before or 75205a2804SDmitri Tikhonov * after an existing element, at the head of the list, or at the end of 76205a2804SDmitri Tikhonov * the list. A tail queue may be traversed in either direction. 77205a2804SDmitri Tikhonov * 78205a2804SDmitri Tikhonov * For details on the use of these macros, see the queue(3) manual page. 79205a2804SDmitri Tikhonov * 80205a2804SDmitri Tikhonov * Below is a summary of implemented functions where: 81205a2804SDmitri Tikhonov * + means the macro is available 82205a2804SDmitri Tikhonov * - means the macro is not available 83205a2804SDmitri Tikhonov * s means the macro is available but is slow (runs in O(n) time) 84205a2804SDmitri Tikhonov * 85205a2804SDmitri Tikhonov * SLIST LIST STAILQ TAILQ 86205a2804SDmitri Tikhonov * _HEAD + + + + 87205a2804SDmitri Tikhonov * _CLASS_HEAD + + + + 88205a2804SDmitri Tikhonov * _HEAD_INITIALIZER + + + + 89205a2804SDmitri Tikhonov * _ENTRY + + + + 90205a2804SDmitri Tikhonov * _CLASS_ENTRY + + + + 91205a2804SDmitri Tikhonov * _INIT + + + + 92205a2804SDmitri Tikhonov * _EMPTY + + + + 93205a2804SDmitri Tikhonov * _FIRST + + + + 94205a2804SDmitri Tikhonov * _NEXT + + + + 95205a2804SDmitri Tikhonov * _PREV - + - + 96205a2804SDmitri Tikhonov * _LAST - - + + 97205a2804SDmitri Tikhonov * _FOREACH + + + + 98205a2804SDmitri Tikhonov * _FOREACH_FROM + + + + 99205a2804SDmitri Tikhonov * _FOREACH_SAFE + + + + 100205a2804SDmitri Tikhonov * _FOREACH_FROM_SAFE + + + + 101205a2804SDmitri Tikhonov * _FOREACH_REVERSE - - - + 102205a2804SDmitri Tikhonov * _FOREACH_REVERSE_FROM - - - + 103205a2804SDmitri Tikhonov * _FOREACH_REVERSE_SAFE - - - + 104205a2804SDmitri Tikhonov * _FOREACH_REVERSE_FROM_SAFE - - - + 105205a2804SDmitri Tikhonov * _INSERT_HEAD + + + + 106205a2804SDmitri Tikhonov * _INSERT_BEFORE - + - + 107205a2804SDmitri Tikhonov * _INSERT_AFTER + + + + 108205a2804SDmitri Tikhonov * _INSERT_TAIL - - + + 109205a2804SDmitri Tikhonov * _CONCAT s s + + 110205a2804SDmitri Tikhonov * _REMOVE_AFTER + - + - 111205a2804SDmitri Tikhonov * _REMOVE_HEAD + - + - 112205a2804SDmitri Tikhonov * _REMOVE s + s + 113205a2804SDmitri Tikhonov * _SWAP + + + + 114205a2804SDmitri Tikhonov * 115205a2804SDmitri Tikhonov */ 116205a2804SDmitri Tikhonov#ifdef QUEUE_MACRO_DEBUG 117205a2804SDmitri Tikhonov#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH 118205a2804SDmitri Tikhonov#define QUEUE_MACRO_DEBUG_TRACE 119205a2804SDmitri Tikhonov#define QUEUE_MACRO_DEBUG_TRASH 120205a2804SDmitri Tikhonov#endif 121205a2804SDmitri Tikhonov 122205a2804SDmitri Tikhonov#ifdef QUEUE_MACRO_DEBUG_TRACE 123205a2804SDmitri Tikhonov/* Store the last 2 places the queue element or head was altered */ 124205a2804SDmitri Tikhonovstruct qm_trace { 125205a2804SDmitri Tikhonov unsigned long lastline; 126205a2804SDmitri Tikhonov unsigned long prevline; 127205a2804SDmitri Tikhonov const char *lastfile; 128205a2804SDmitri Tikhonov const char *prevfile; 129205a2804SDmitri Tikhonov}; 130205a2804SDmitri Tikhonov 131205a2804SDmitri Tikhonov#define TRACEBUF struct qm_trace trace; 132205a2804SDmitri Tikhonov#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } , 133205a2804SDmitri Tikhonov 134205a2804SDmitri Tikhonov#define QMD_TRACE_HEAD(head) do { \ 135205a2804SDmitri Tikhonov (head)->trace.prevline = (head)->trace.lastline; \ 136205a2804SDmitri Tikhonov (head)->trace.prevfile = (head)->trace.lastfile; \ 137205a2804SDmitri Tikhonov (head)->trace.lastline = __LINE__; \ 138205a2804SDmitri Tikhonov (head)->trace.lastfile = __FILE__; \ 139205a2804SDmitri Tikhonov} while (0) 140205a2804SDmitri Tikhonov 141205a2804SDmitri Tikhonov#define QMD_TRACE_ELEM(elem) do { \ 142205a2804SDmitri Tikhonov (elem)->trace.prevline = (elem)->trace.lastline; \ 143205a2804SDmitri Tikhonov (elem)->trace.prevfile = (elem)->trace.lastfile; \ 144205a2804SDmitri Tikhonov (elem)->trace.lastline = __LINE__; \ 145205a2804SDmitri Tikhonov (elem)->trace.lastfile = __FILE__; \ 146205a2804SDmitri Tikhonov} while (0) 147205a2804SDmitri Tikhonov 148205a2804SDmitri Tikhonov#else /* !QUEUE_MACRO_DEBUG_TRACE */ 149205a2804SDmitri Tikhonov#define QMD_TRACE_ELEM(elem) 150205a2804SDmitri Tikhonov#define QMD_TRACE_HEAD(head) 151205a2804SDmitri Tikhonov#define TRACEBUF 152205a2804SDmitri Tikhonov#define TRACEBUF_INITIALIZER 153205a2804SDmitri Tikhonov#endif /* QUEUE_MACRO_DEBUG_TRACE */ 154205a2804SDmitri Tikhonov 155205a2804SDmitri Tikhonov#ifdef QUEUE_MACRO_DEBUG_TRASH 156205a2804SDmitri Tikhonov#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 157205a2804SDmitri Tikhonov#define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1) 158205a2804SDmitri Tikhonov#else /* !QUEUE_MACRO_DEBUG_TRASH */ 159205a2804SDmitri Tikhonov#define TRASHIT(x) 160205a2804SDmitri Tikhonov#define QMD_IS_TRASHED(x) 0 161205a2804SDmitri Tikhonov#endif /* QUEUE_MACRO_DEBUG_TRASH */ 162205a2804SDmitri Tikhonov 163205a2804SDmitri Tikhonov#if defined(QUEUE_MACRO_DEBUG_TRACE) || defined(QUEUE_MACRO_DEBUG_TRASH) 164205a2804SDmitri Tikhonov#define QMD_SAVELINK(name, link) void **name = (void *)&(link) 165205a2804SDmitri Tikhonov#else /* !QUEUE_MACRO_DEBUG_TRACE && !QUEUE_MACRO_DEBUG_TRASH */ 166205a2804SDmitri Tikhonov#define QMD_SAVELINK(name, link) 167205a2804SDmitri Tikhonov#endif /* QUEUE_MACRO_DEBUG_TRACE || QUEUE_MACRO_DEBUG_TRASH */ 168205a2804SDmitri Tikhonov 169205a2804SDmitri Tikhonov#ifdef __cplusplus 170205a2804SDmitri Tikhonov/* 171205a2804SDmitri Tikhonov * In C++ there can be structure lists and class lists: 172205a2804SDmitri Tikhonov */ 173205a2804SDmitri Tikhonov#define QUEUE_TYPEOF(type) type 174205a2804SDmitri Tikhonov#else 175205a2804SDmitri Tikhonov#define QUEUE_TYPEOF(type) struct type 176205a2804SDmitri Tikhonov#endif 177205a2804SDmitri Tikhonov 178205a2804SDmitri Tikhonov/* 179205a2804SDmitri Tikhonov * Singly-linked List declarations. 180205a2804SDmitri Tikhonov */ 181205a2804SDmitri Tikhonov#define SLIST_HEAD(name, type) \ 182205a2804SDmitri Tikhonovstruct name { \ 183205a2804SDmitri Tikhonov struct type *slh_first; /* first element */ \ 184205a2804SDmitri Tikhonov} 185205a2804SDmitri Tikhonov 186205a2804SDmitri Tikhonov#define SLIST_CLASS_HEAD(name, type) \ 187205a2804SDmitri Tikhonovstruct name { \ 188205a2804SDmitri Tikhonov class type *slh_first; /* first element */ \ 189205a2804SDmitri Tikhonov} 190205a2804SDmitri Tikhonov 191205a2804SDmitri Tikhonov#define SLIST_HEAD_INITIALIZER(head) \ 192205a2804SDmitri Tikhonov { NULL } 193205a2804SDmitri Tikhonov 194205a2804SDmitri Tikhonov#define SLIST_ENTRY(type) \ 195205a2804SDmitri Tikhonovstruct { \ 196205a2804SDmitri Tikhonov struct type *sle_next; /* next element */ \ 197205a2804SDmitri Tikhonov} 198205a2804SDmitri Tikhonov 199205a2804SDmitri Tikhonov#define SLIST_CLASS_ENTRY(type) \ 200205a2804SDmitri Tikhonovstruct { \ 201205a2804SDmitri Tikhonov class type *sle_next; /* next element */ \ 202205a2804SDmitri Tikhonov} 203205a2804SDmitri Tikhonov 204205a2804SDmitri Tikhonov/* 205205a2804SDmitri Tikhonov * Singly-linked List functions. 206205a2804SDmitri Tikhonov */ 207205a2804SDmitri Tikhonov#if (defined(_KERNEL) && defined(INVARIANTS)) 208205a2804SDmitri Tikhonov#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do { \ 209205a2804SDmitri Tikhonov if (*(prevp) != (elm)) \ 210205a2804SDmitri Tikhonov panic("Bad prevptr *(%p) == %p != %p", \ 211205a2804SDmitri Tikhonov (prevp), *(prevp), (elm)); \ 212205a2804SDmitri Tikhonov} while (0) 213205a2804SDmitri Tikhonov#else 214205a2804SDmitri Tikhonov#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) 215205a2804SDmitri Tikhonov#endif 216205a2804SDmitri Tikhonov 217205a2804SDmitri Tikhonov#define SLIST_CONCAT(head1, head2, type, field) do { \ 218205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ 219205a2804SDmitri Tikhonov if (curelm == NULL) { \ 220205a2804SDmitri Tikhonov if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ 221205a2804SDmitri Tikhonov SLIST_INIT(head2); \ 222205a2804SDmitri Tikhonov } else if (SLIST_FIRST(head2) != NULL) { \ 223205a2804SDmitri Tikhonov while (SLIST_NEXT(curelm, field) != NULL) \ 224205a2804SDmitri Tikhonov curelm = SLIST_NEXT(curelm, field); \ 225205a2804SDmitri Tikhonov SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ 226205a2804SDmitri Tikhonov SLIST_INIT(head2); \ 227205a2804SDmitri Tikhonov } \ 228205a2804SDmitri Tikhonov} while (0) 229205a2804SDmitri Tikhonov 230205a2804SDmitri Tikhonov#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 231205a2804SDmitri Tikhonov 232205a2804SDmitri Tikhonov#define SLIST_FIRST(head) ((head)->slh_first) 233205a2804SDmitri Tikhonov 234205a2804SDmitri Tikhonov#define SLIST_FOREACH(var, head, field) \ 235205a2804SDmitri Tikhonov for ((var) = SLIST_FIRST((head)); \ 236205a2804SDmitri Tikhonov (var); \ 237205a2804SDmitri Tikhonov (var) = SLIST_NEXT((var), field)) 238205a2804SDmitri Tikhonov 239205a2804SDmitri Tikhonov#define SLIST_FOREACH_FROM(var, head, field) \ 240205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 241205a2804SDmitri Tikhonov (var); \ 242205a2804SDmitri Tikhonov (var) = SLIST_NEXT((var), field)) 243205a2804SDmitri Tikhonov 244205a2804SDmitri Tikhonov#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 245205a2804SDmitri Tikhonov for ((var) = SLIST_FIRST((head)); \ 246205a2804SDmitri Tikhonov (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 247205a2804SDmitri Tikhonov (var) = (tvar)) 248205a2804SDmitri Tikhonov 249205a2804SDmitri Tikhonov#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 250205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 251205a2804SDmitri Tikhonov (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 252205a2804SDmitri Tikhonov (var) = (tvar)) 253205a2804SDmitri Tikhonov 254205a2804SDmitri Tikhonov#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 255205a2804SDmitri Tikhonov for ((varp) = &SLIST_FIRST((head)); \ 256205a2804SDmitri Tikhonov ((var) = *(varp)) != NULL; \ 257205a2804SDmitri Tikhonov (varp) = &SLIST_NEXT((var), field)) 258205a2804SDmitri Tikhonov 259205a2804SDmitri Tikhonov#define SLIST_INIT(head) do { \ 260205a2804SDmitri Tikhonov SLIST_FIRST((head)) = NULL; \ 261205a2804SDmitri Tikhonov} while (0) 262205a2804SDmitri Tikhonov 263205a2804SDmitri Tikhonov#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 264205a2804SDmitri Tikhonov SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 265205a2804SDmitri Tikhonov SLIST_NEXT((slistelm), field) = (elm); \ 266205a2804SDmitri Tikhonov} while (0) 267205a2804SDmitri Tikhonov 268205a2804SDmitri Tikhonov#define SLIST_INSERT_HEAD(head, elm, field) do { \ 269205a2804SDmitri Tikhonov SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 270205a2804SDmitri Tikhonov SLIST_FIRST((head)) = (elm); \ 271205a2804SDmitri Tikhonov} while (0) 272205a2804SDmitri Tikhonov 273205a2804SDmitri Tikhonov#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 274205a2804SDmitri Tikhonov 275205a2804SDmitri Tikhonov#define SLIST_REMOVE(head, elm, type, field) do { \ 276205a2804SDmitri Tikhonov QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ 277205a2804SDmitri Tikhonov if (SLIST_FIRST((head)) == (elm)) { \ 278205a2804SDmitri Tikhonov SLIST_REMOVE_HEAD((head), field); \ 279205a2804SDmitri Tikhonov } \ 280205a2804SDmitri Tikhonov else { \ 281205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \ 282205a2804SDmitri Tikhonov while (SLIST_NEXT(curelm, field) != (elm)) \ 283205a2804SDmitri Tikhonov curelm = SLIST_NEXT(curelm, field); \ 284205a2804SDmitri Tikhonov SLIST_REMOVE_AFTER(curelm, field); \ 285205a2804SDmitri Tikhonov } \ 286205a2804SDmitri Tikhonov TRASHIT(*oldnext); \ 287205a2804SDmitri Tikhonov} while (0) 288205a2804SDmitri Tikhonov 289205a2804SDmitri Tikhonov#define SLIST_REMOVE_AFTER(elm, field) do { \ 290205a2804SDmitri Tikhonov SLIST_NEXT(elm, field) = \ 291205a2804SDmitri Tikhonov SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 292205a2804SDmitri Tikhonov} while (0) 293205a2804SDmitri Tikhonov 294205a2804SDmitri Tikhonov#define SLIST_REMOVE_HEAD(head, field) do { \ 295205a2804SDmitri Tikhonov SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 296205a2804SDmitri Tikhonov} while (0) 297205a2804SDmitri Tikhonov 298205a2804SDmitri Tikhonov#define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \ 299205a2804SDmitri Tikhonov QMD_SLIST_CHECK_PREVPTR(prevp, elm); \ 300205a2804SDmitri Tikhonov *(prevp) = SLIST_NEXT(elm, field); \ 301205a2804SDmitri Tikhonov TRASHIT((elm)->field.sle_next); \ 302205a2804SDmitri Tikhonov} while (0) 303205a2804SDmitri Tikhonov 304205a2804SDmitri Tikhonov#define SLIST_SWAP(head1, head2, type) do { \ 305205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ 306205a2804SDmitri Tikhonov SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 307205a2804SDmitri Tikhonov SLIST_FIRST(head2) = swap_first; \ 308205a2804SDmitri Tikhonov} while (0) 309205a2804SDmitri Tikhonov 310205a2804SDmitri Tikhonov/* 311205a2804SDmitri Tikhonov * Singly-linked Tail queue declarations. 312205a2804SDmitri Tikhonov */ 313205a2804SDmitri Tikhonov#define STAILQ_HEAD(name, type) \ 314205a2804SDmitri Tikhonovstruct name { \ 315205a2804SDmitri Tikhonov struct type *stqh_first;/* first element */ \ 316205a2804SDmitri Tikhonov struct type **stqh_last;/* addr of last next element */ \ 317205a2804SDmitri Tikhonov} 318205a2804SDmitri Tikhonov 319205a2804SDmitri Tikhonov#define STAILQ_CLASS_HEAD(name, type) \ 320205a2804SDmitri Tikhonovstruct name { \ 321205a2804SDmitri Tikhonov class type *stqh_first; /* first element */ \ 322205a2804SDmitri Tikhonov class type **stqh_last; /* addr of last next element */ \ 323205a2804SDmitri Tikhonov} 324205a2804SDmitri Tikhonov 325205a2804SDmitri Tikhonov#define STAILQ_HEAD_INITIALIZER(head) \ 326205a2804SDmitri Tikhonov { NULL, &(head).stqh_first } 327205a2804SDmitri Tikhonov 328205a2804SDmitri Tikhonov#define STAILQ_ENTRY(type) \ 329205a2804SDmitri Tikhonovstruct { \ 330205a2804SDmitri Tikhonov struct type *stqe_next; /* next element */ \ 331205a2804SDmitri Tikhonov} 332205a2804SDmitri Tikhonov 333205a2804SDmitri Tikhonov#define STAILQ_CLASS_ENTRY(type) \ 334205a2804SDmitri Tikhonovstruct { \ 335205a2804SDmitri Tikhonov class type *stqe_next; /* next element */ \ 336205a2804SDmitri Tikhonov} 337205a2804SDmitri Tikhonov 338205a2804SDmitri Tikhonov/* 339205a2804SDmitri Tikhonov * Singly-linked Tail queue functions. 340205a2804SDmitri Tikhonov */ 341205a2804SDmitri Tikhonov#define STAILQ_CONCAT(head1, head2) do { \ 342205a2804SDmitri Tikhonov if (!STAILQ_EMPTY((head2))) { \ 343205a2804SDmitri Tikhonov *(head1)->stqh_last = (head2)->stqh_first; \ 344205a2804SDmitri Tikhonov (head1)->stqh_last = (head2)->stqh_last; \ 345205a2804SDmitri Tikhonov STAILQ_INIT((head2)); \ 346205a2804SDmitri Tikhonov } \ 347205a2804SDmitri Tikhonov} while (0) 348205a2804SDmitri Tikhonov 349205a2804SDmitri Tikhonov#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 350205a2804SDmitri Tikhonov 351205a2804SDmitri Tikhonov#define STAILQ_FIRST(head) ((head)->stqh_first) 352205a2804SDmitri Tikhonov 353205a2804SDmitri Tikhonov#define STAILQ_FOREACH(var, head, field) \ 354205a2804SDmitri Tikhonov for((var) = STAILQ_FIRST((head)); \ 355205a2804SDmitri Tikhonov (var); \ 356205a2804SDmitri Tikhonov (var) = STAILQ_NEXT((var), field)) 357205a2804SDmitri Tikhonov 358205a2804SDmitri Tikhonov#define STAILQ_FOREACH_FROM(var, head, field) \ 359205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 360205a2804SDmitri Tikhonov (var); \ 361205a2804SDmitri Tikhonov (var) = STAILQ_NEXT((var), field)) 362205a2804SDmitri Tikhonov 363205a2804SDmitri Tikhonov#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 364205a2804SDmitri Tikhonov for ((var) = STAILQ_FIRST((head)); \ 365205a2804SDmitri Tikhonov (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 366205a2804SDmitri Tikhonov (var) = (tvar)) 367205a2804SDmitri Tikhonov 368205a2804SDmitri Tikhonov#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 369205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 370205a2804SDmitri Tikhonov (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 371205a2804SDmitri Tikhonov (var) = (tvar)) 372205a2804SDmitri Tikhonov 373205a2804SDmitri Tikhonov#define STAILQ_INIT(head) do { \ 374205a2804SDmitri Tikhonov STAILQ_FIRST((head)) = NULL; \ 375205a2804SDmitri Tikhonov (head)->stqh_last = &STAILQ_FIRST((head)); \ 376205a2804SDmitri Tikhonov} while (0) 377205a2804SDmitri Tikhonov 378205a2804SDmitri Tikhonov#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 379205a2804SDmitri Tikhonov if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 380205a2804SDmitri Tikhonov (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 381205a2804SDmitri Tikhonov STAILQ_NEXT((tqelm), field) = (elm); \ 382205a2804SDmitri Tikhonov} while (0) 383205a2804SDmitri Tikhonov 384205a2804SDmitri Tikhonov#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 385205a2804SDmitri Tikhonov if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 386205a2804SDmitri Tikhonov (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 387205a2804SDmitri Tikhonov STAILQ_FIRST((head)) = (elm); \ 388205a2804SDmitri Tikhonov} while (0) 389205a2804SDmitri Tikhonov 390205a2804SDmitri Tikhonov#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 391205a2804SDmitri Tikhonov STAILQ_NEXT((elm), field) = NULL; \ 392205a2804SDmitri Tikhonov *(head)->stqh_last = (elm); \ 393205a2804SDmitri Tikhonov (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 394205a2804SDmitri Tikhonov} while (0) 395205a2804SDmitri Tikhonov 396205a2804SDmitri Tikhonov#define STAILQ_LAST(head, type, field) \ 397205a2804SDmitri Tikhonov (STAILQ_EMPTY((head)) ? NULL : \ 398205a2804SDmitri Tikhonov __containerof((head)->stqh_last, \ 399205a2804SDmitri Tikhonov QUEUE_TYPEOF(type), field.stqe_next)) 400205a2804SDmitri Tikhonov 401205a2804SDmitri Tikhonov#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 402205a2804SDmitri Tikhonov 403205a2804SDmitri Tikhonov#define STAILQ_REMOVE(head, elm, type, field) do { \ 404205a2804SDmitri Tikhonov QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ 405205a2804SDmitri Tikhonov if (STAILQ_FIRST((head)) == (elm)) { \ 406205a2804SDmitri Tikhonov STAILQ_REMOVE_HEAD((head), field); \ 407205a2804SDmitri Tikhonov } \ 408205a2804SDmitri Tikhonov else { \ 409205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ 410205a2804SDmitri Tikhonov while (STAILQ_NEXT(curelm, field) != (elm)) \ 411205a2804SDmitri Tikhonov curelm = STAILQ_NEXT(curelm, field); \ 412205a2804SDmitri Tikhonov STAILQ_REMOVE_AFTER(head, curelm, field); \ 413205a2804SDmitri Tikhonov } \ 414205a2804SDmitri Tikhonov TRASHIT(*oldnext); \ 415205a2804SDmitri Tikhonov} while (0) 416205a2804SDmitri Tikhonov 417205a2804SDmitri Tikhonov#define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 418205a2804SDmitri Tikhonov if ((STAILQ_NEXT(elm, field) = \ 419205a2804SDmitri Tikhonov STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 420205a2804SDmitri Tikhonov (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 421205a2804SDmitri Tikhonov} while (0) 422205a2804SDmitri Tikhonov 423205a2804SDmitri Tikhonov#define STAILQ_REMOVE_HEAD(head, field) do { \ 424205a2804SDmitri Tikhonov if ((STAILQ_FIRST((head)) = \ 425205a2804SDmitri Tikhonov STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 426205a2804SDmitri Tikhonov (head)->stqh_last = &STAILQ_FIRST((head)); \ 427205a2804SDmitri Tikhonov} while (0) 428205a2804SDmitri Tikhonov 429205a2804SDmitri Tikhonov#define STAILQ_SWAP(head1, head2, type) do { \ 430205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ 431205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ 432205a2804SDmitri Tikhonov STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 433205a2804SDmitri Tikhonov (head1)->stqh_last = (head2)->stqh_last; \ 434205a2804SDmitri Tikhonov STAILQ_FIRST(head2) = swap_first; \ 435205a2804SDmitri Tikhonov (head2)->stqh_last = swap_last; \ 436205a2804SDmitri Tikhonov if (STAILQ_EMPTY(head1)) \ 437205a2804SDmitri Tikhonov (head1)->stqh_last = &STAILQ_FIRST(head1); \ 438205a2804SDmitri Tikhonov if (STAILQ_EMPTY(head2)) \ 439205a2804SDmitri Tikhonov (head2)->stqh_last = &STAILQ_FIRST(head2); \ 440205a2804SDmitri Tikhonov} while (0) 441205a2804SDmitri Tikhonov 442205a2804SDmitri Tikhonov 443205a2804SDmitri Tikhonov/* 444205a2804SDmitri Tikhonov * List declarations. 445205a2804SDmitri Tikhonov */ 446205a2804SDmitri Tikhonov#define LIST_HEAD(name, type) \ 447205a2804SDmitri Tikhonovstruct name { \ 448205a2804SDmitri Tikhonov struct type *lh_first; /* first element */ \ 449205a2804SDmitri Tikhonov} 450205a2804SDmitri Tikhonov 451205a2804SDmitri Tikhonov#define LIST_CLASS_HEAD(name, type) \ 452205a2804SDmitri Tikhonovstruct name { \ 453205a2804SDmitri Tikhonov class type *lh_first; /* first element */ \ 454205a2804SDmitri Tikhonov} 455205a2804SDmitri Tikhonov 456205a2804SDmitri Tikhonov#define LIST_HEAD_INITIALIZER(head) \ 457205a2804SDmitri Tikhonov { NULL } 458205a2804SDmitri Tikhonov 459205a2804SDmitri Tikhonov#define LIST_ENTRY(type) \ 460205a2804SDmitri Tikhonovstruct { \ 461205a2804SDmitri Tikhonov struct type *le_next; /* next element */ \ 462205a2804SDmitri Tikhonov struct type **le_prev; /* address of previous next element */ \ 463205a2804SDmitri Tikhonov} 464205a2804SDmitri Tikhonov 465205a2804SDmitri Tikhonov#define LIST_CLASS_ENTRY(type) \ 466205a2804SDmitri Tikhonovstruct { \ 467205a2804SDmitri Tikhonov class type *le_next; /* next element */ \ 468205a2804SDmitri Tikhonov class type **le_prev; /* address of previous next element */ \ 469205a2804SDmitri Tikhonov} 470205a2804SDmitri Tikhonov 471205a2804SDmitri Tikhonov/* 472205a2804SDmitri Tikhonov * List functions. 473205a2804SDmitri Tikhonov */ 474205a2804SDmitri Tikhonov 475205a2804SDmitri Tikhonov#if (defined(_KERNEL) && defined(INVARIANTS)) 476205a2804SDmitri Tikhonov/* 477205a2804SDmitri Tikhonov * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME) 478205a2804SDmitri Tikhonov * 479205a2804SDmitri Tikhonov * If the list is non-empty, validates that the first element of the list 480205a2804SDmitri Tikhonov * points back at 'head.' 481205a2804SDmitri Tikhonov */ 482205a2804SDmitri Tikhonov#define QMD_LIST_CHECK_HEAD(head, field) do { \ 483205a2804SDmitri Tikhonov if (LIST_FIRST((head)) != NULL && \ 484205a2804SDmitri Tikhonov LIST_FIRST((head))->field.le_prev != \ 485205a2804SDmitri Tikhonov &LIST_FIRST((head))) \ 486205a2804SDmitri Tikhonov panic("Bad list head %p first->prev != head", (head)); \ 487205a2804SDmitri Tikhonov} while (0) 488205a2804SDmitri Tikhonov 489205a2804SDmitri Tikhonov/* 490205a2804SDmitri Tikhonov * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME) 491205a2804SDmitri Tikhonov * 492205a2804SDmitri Tikhonov * If an element follows 'elm' in the list, validates that the next element 493205a2804SDmitri Tikhonov * points back at 'elm.' 494205a2804SDmitri Tikhonov */ 495205a2804SDmitri Tikhonov#define QMD_LIST_CHECK_NEXT(elm, field) do { \ 496205a2804SDmitri Tikhonov if (LIST_NEXT((elm), field) != NULL && \ 497205a2804SDmitri Tikhonov LIST_NEXT((elm), field)->field.le_prev != \ 498205a2804SDmitri Tikhonov &((elm)->field.le_next)) \ 499205a2804SDmitri Tikhonov panic("Bad link elm %p next->prev != elm", (elm)); \ 500205a2804SDmitri Tikhonov} while (0) 501205a2804SDmitri Tikhonov 502205a2804SDmitri Tikhonov/* 503205a2804SDmitri Tikhonov * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME) 504205a2804SDmitri Tikhonov * 505205a2804SDmitri Tikhonov * Validates that the previous element (or head of the list) points to 'elm.' 506205a2804SDmitri Tikhonov */ 507205a2804SDmitri Tikhonov#define QMD_LIST_CHECK_PREV(elm, field) do { \ 508205a2804SDmitri Tikhonov if (*(elm)->field.le_prev != (elm)) \ 509205a2804SDmitri Tikhonov panic("Bad link elm %p prev->next != elm", (elm)); \ 510205a2804SDmitri Tikhonov} while (0) 511205a2804SDmitri Tikhonov#else 512205a2804SDmitri Tikhonov#define QMD_LIST_CHECK_HEAD(head, field) 513205a2804SDmitri Tikhonov#define QMD_LIST_CHECK_NEXT(elm, field) 514205a2804SDmitri Tikhonov#define QMD_LIST_CHECK_PREV(elm, field) 515205a2804SDmitri Tikhonov#endif /* (_KERNEL && INVARIANTS) */ 516205a2804SDmitri Tikhonov 517205a2804SDmitri Tikhonov#define LIST_CONCAT(head1, head2, type, field) do { \ 518205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ 519205a2804SDmitri Tikhonov if (curelm == NULL) { \ 520205a2804SDmitri Tikhonov if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ 521205a2804SDmitri Tikhonov LIST_FIRST(head2)->field.le_prev = \ 522205a2804SDmitri Tikhonov &LIST_FIRST((head1)); \ 523205a2804SDmitri Tikhonov LIST_INIT(head2); \ 524205a2804SDmitri Tikhonov } \ 525205a2804SDmitri Tikhonov } else if (LIST_FIRST(head2) != NULL) { \ 526205a2804SDmitri Tikhonov while (LIST_NEXT(curelm, field) != NULL) \ 527205a2804SDmitri Tikhonov curelm = LIST_NEXT(curelm, field); \ 528205a2804SDmitri Tikhonov LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ 529205a2804SDmitri Tikhonov LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \ 530205a2804SDmitri Tikhonov LIST_INIT(head2); \ 531205a2804SDmitri Tikhonov } \ 532205a2804SDmitri Tikhonov} while (0) 533205a2804SDmitri Tikhonov 534205a2804SDmitri Tikhonov#define LIST_EMPTY(head) ((head)->lh_first == NULL) 535205a2804SDmitri Tikhonov 536205a2804SDmitri Tikhonov#define LIST_FIRST(head) ((head)->lh_first) 537205a2804SDmitri Tikhonov 538205a2804SDmitri Tikhonov#define LIST_FOREACH(var, head, field) \ 539205a2804SDmitri Tikhonov for ((var) = LIST_FIRST((head)); \ 540205a2804SDmitri Tikhonov (var); \ 541205a2804SDmitri Tikhonov (var) = LIST_NEXT((var), field)) 542205a2804SDmitri Tikhonov 543205a2804SDmitri Tikhonov#define LIST_FOREACH_FROM(var, head, field) \ 544205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 545205a2804SDmitri Tikhonov (var); \ 546205a2804SDmitri Tikhonov (var) = LIST_NEXT((var), field)) 547205a2804SDmitri Tikhonov 548205a2804SDmitri Tikhonov#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 549205a2804SDmitri Tikhonov for ((var) = LIST_FIRST((head)); \ 550205a2804SDmitri Tikhonov (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 551205a2804SDmitri Tikhonov (var) = (tvar)) 552205a2804SDmitri Tikhonov 553205a2804SDmitri Tikhonov#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 554205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 555205a2804SDmitri Tikhonov (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 556205a2804SDmitri Tikhonov (var) = (tvar)) 557205a2804SDmitri Tikhonov 558205a2804SDmitri Tikhonov#define LIST_INIT(head) do { \ 559205a2804SDmitri Tikhonov LIST_FIRST((head)) = NULL; \ 560205a2804SDmitri Tikhonov} while (0) 561205a2804SDmitri Tikhonov 562205a2804SDmitri Tikhonov#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 563205a2804SDmitri Tikhonov QMD_LIST_CHECK_NEXT(listelm, field); \ 564205a2804SDmitri Tikhonov if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 565205a2804SDmitri Tikhonov LIST_NEXT((listelm), field)->field.le_prev = \ 566205a2804SDmitri Tikhonov &LIST_NEXT((elm), field); \ 567205a2804SDmitri Tikhonov LIST_NEXT((listelm), field) = (elm); \ 568205a2804SDmitri Tikhonov (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 569205a2804SDmitri Tikhonov} while (0) 570205a2804SDmitri Tikhonov 571205a2804SDmitri Tikhonov#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 572205a2804SDmitri Tikhonov QMD_LIST_CHECK_PREV(listelm, field); \ 573205a2804SDmitri Tikhonov (elm)->field.le_prev = (listelm)->field.le_prev; \ 574205a2804SDmitri Tikhonov LIST_NEXT((elm), field) = (listelm); \ 575205a2804SDmitri Tikhonov *(listelm)->field.le_prev = (elm); \ 576205a2804SDmitri Tikhonov (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 577205a2804SDmitri Tikhonov} while (0) 578205a2804SDmitri Tikhonov 579205a2804SDmitri Tikhonov#define LIST_INSERT_HEAD(head, elm, field) do { \ 580205a2804SDmitri Tikhonov QMD_LIST_CHECK_HEAD((head), field); \ 581205a2804SDmitri Tikhonov if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 582205a2804SDmitri Tikhonov LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 583205a2804SDmitri Tikhonov LIST_FIRST((head)) = (elm); \ 584205a2804SDmitri Tikhonov (elm)->field.le_prev = &LIST_FIRST((head)); \ 585205a2804SDmitri Tikhonov} while (0) 586205a2804SDmitri Tikhonov 587205a2804SDmitri Tikhonov#define LIST_NEXT(elm, field) ((elm)->field.le_next) 588205a2804SDmitri Tikhonov 589205a2804SDmitri Tikhonov#define LIST_PREV(elm, head, type, field) \ 590205a2804SDmitri Tikhonov ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 591205a2804SDmitri Tikhonov __containerof((elm)->field.le_prev, \ 592205a2804SDmitri Tikhonov QUEUE_TYPEOF(type), field.le_next)) 593205a2804SDmitri Tikhonov 594205a2804SDmitri Tikhonov#define LIST_REMOVE(elm, field) do { \ 595205a2804SDmitri Tikhonov QMD_SAVELINK(oldnext, (elm)->field.le_next); \ 596205a2804SDmitri Tikhonov QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ 597205a2804SDmitri Tikhonov QMD_LIST_CHECK_NEXT(elm, field); \ 598205a2804SDmitri Tikhonov QMD_LIST_CHECK_PREV(elm, field); \ 599205a2804SDmitri Tikhonov if (LIST_NEXT((elm), field) != NULL) \ 600205a2804SDmitri Tikhonov LIST_NEXT((elm), field)->field.le_prev = \ 601205a2804SDmitri Tikhonov (elm)->field.le_prev; \ 602205a2804SDmitri Tikhonov *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 603205a2804SDmitri Tikhonov TRASHIT(*oldnext); \ 604205a2804SDmitri Tikhonov TRASHIT(*oldprev); \ 605205a2804SDmitri Tikhonov} while (0) 606205a2804SDmitri Tikhonov 607205a2804SDmitri Tikhonov#define LIST_SWAP(head1, head2, type, field) do { \ 608205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 609205a2804SDmitri Tikhonov LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 610205a2804SDmitri Tikhonov LIST_FIRST((head2)) = swap_tmp; \ 611205a2804SDmitri Tikhonov if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 612205a2804SDmitri Tikhonov swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 613205a2804SDmitri Tikhonov if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 614205a2804SDmitri Tikhonov swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 615205a2804SDmitri Tikhonov} while (0) 616205a2804SDmitri Tikhonov 617205a2804SDmitri Tikhonov/* 618205a2804SDmitri Tikhonov * Tail queue declarations. 619205a2804SDmitri Tikhonov */ 620205a2804SDmitri Tikhonov#define TAILQ_HEAD(name, type) \ 621205a2804SDmitri Tikhonovstruct name { \ 622205a2804SDmitri Tikhonov struct type *tqh_first; /* first element */ \ 623205a2804SDmitri Tikhonov struct type **tqh_last; /* addr of last next element */ \ 624205a2804SDmitri Tikhonov TRACEBUF \ 625205a2804SDmitri Tikhonov} 626205a2804SDmitri Tikhonov 627205a2804SDmitri Tikhonov#define TAILQ_CLASS_HEAD(name, type) \ 628205a2804SDmitri Tikhonovstruct name { \ 629205a2804SDmitri Tikhonov class type *tqh_first; /* first element */ \ 630205a2804SDmitri Tikhonov class type **tqh_last; /* addr of last next element */ \ 631205a2804SDmitri Tikhonov TRACEBUF \ 632205a2804SDmitri Tikhonov} 633205a2804SDmitri Tikhonov 634205a2804SDmitri Tikhonov#define TAILQ_HEAD_INITIALIZER(head) \ 635205a2804SDmitri Tikhonov { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } 636205a2804SDmitri Tikhonov 637205a2804SDmitri Tikhonov#define TAILQ_ENTRY(type) \ 638205a2804SDmitri Tikhonovstruct { \ 639205a2804SDmitri Tikhonov struct type *tqe_next; /* next element */ \ 640205a2804SDmitri Tikhonov struct type **tqe_prev; /* address of previous next element */ \ 641205a2804SDmitri Tikhonov TRACEBUF \ 642205a2804SDmitri Tikhonov} 643205a2804SDmitri Tikhonov 644205a2804SDmitri Tikhonov#define TAILQ_CLASS_ENTRY(type) \ 645205a2804SDmitri Tikhonovstruct { \ 646205a2804SDmitri Tikhonov class type *tqe_next; /* next element */ \ 647205a2804SDmitri Tikhonov class type **tqe_prev; /* address of previous next element */ \ 648205a2804SDmitri Tikhonov TRACEBUF \ 649205a2804SDmitri Tikhonov} 650205a2804SDmitri Tikhonov 651205a2804SDmitri Tikhonov/* 652205a2804SDmitri Tikhonov * Tail queue functions. 653205a2804SDmitri Tikhonov */ 654205a2804SDmitri Tikhonov#if (defined(_KERNEL) && defined(INVARIANTS)) 655205a2804SDmitri Tikhonov/* 656205a2804SDmitri Tikhonov * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 657205a2804SDmitri Tikhonov * 658205a2804SDmitri Tikhonov * If the tailq is non-empty, validates that the first element of the tailq 659205a2804SDmitri Tikhonov * points back at 'head.' 660205a2804SDmitri Tikhonov */ 661205a2804SDmitri Tikhonov#define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 662205a2804SDmitri Tikhonov if (!TAILQ_EMPTY(head) && \ 663205a2804SDmitri Tikhonov TAILQ_FIRST((head))->field.tqe_prev != \ 664205a2804SDmitri Tikhonov &TAILQ_FIRST((head))) \ 665205a2804SDmitri Tikhonov panic("Bad tailq head %p first->prev != head", (head)); \ 666205a2804SDmitri Tikhonov} while (0) 667205a2804SDmitri Tikhonov 668205a2804SDmitri Tikhonov/* 669205a2804SDmitri Tikhonov * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 670205a2804SDmitri Tikhonov * 671205a2804SDmitri Tikhonov * Validates that the tail of the tailq is a pointer to pointer to NULL. 672205a2804SDmitri Tikhonov */ 673205a2804SDmitri Tikhonov#define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 674205a2804SDmitri Tikhonov if (*(head)->tqh_last != NULL) \ 675205a2804SDmitri Tikhonov panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 676205a2804SDmitri Tikhonov} while (0) 677205a2804SDmitri Tikhonov 678205a2804SDmitri Tikhonov/* 679205a2804SDmitri Tikhonov * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME) 680205a2804SDmitri Tikhonov * 681205a2804SDmitri Tikhonov * If an element follows 'elm' in the tailq, validates that the next element 682205a2804SDmitri Tikhonov * points back at 'elm.' 683205a2804SDmitri Tikhonov */ 684205a2804SDmitri Tikhonov#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 685205a2804SDmitri Tikhonov if (TAILQ_NEXT((elm), field) != NULL && \ 686205a2804SDmitri Tikhonov TAILQ_NEXT((elm), field)->field.tqe_prev != \ 687205a2804SDmitri Tikhonov &((elm)->field.tqe_next)) \ 688205a2804SDmitri Tikhonov panic("Bad link elm %p next->prev != elm", (elm)); \ 689205a2804SDmitri Tikhonov} while (0) 690205a2804SDmitri Tikhonov 691205a2804SDmitri Tikhonov/* 692205a2804SDmitri Tikhonov * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME) 693205a2804SDmitri Tikhonov * 694205a2804SDmitri Tikhonov * Validates that the previous element (or head of the tailq) points to 'elm.' 695205a2804SDmitri Tikhonov */ 696205a2804SDmitri Tikhonov#define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 697205a2804SDmitri Tikhonov if (*(elm)->field.tqe_prev != (elm)) \ 698205a2804SDmitri Tikhonov panic("Bad link elm %p prev->next != elm", (elm)); \ 699205a2804SDmitri Tikhonov} while (0) 700205a2804SDmitri Tikhonov#else 701205a2804SDmitri Tikhonov#define QMD_TAILQ_CHECK_HEAD(head, field) 702205a2804SDmitri Tikhonov#define QMD_TAILQ_CHECK_TAIL(head, headname) 703205a2804SDmitri Tikhonov#define QMD_TAILQ_CHECK_NEXT(elm, field) 704205a2804SDmitri Tikhonov#define QMD_TAILQ_CHECK_PREV(elm, field) 705205a2804SDmitri Tikhonov#endif /* (_KERNEL && INVARIANTS) */ 706205a2804SDmitri Tikhonov 707205a2804SDmitri Tikhonov#define TAILQ_CONCAT(head1, head2, field) do { \ 708205a2804SDmitri Tikhonov if (!TAILQ_EMPTY(head2)) { \ 709205a2804SDmitri Tikhonov *(head1)->tqh_last = (head2)->tqh_first; \ 710205a2804SDmitri Tikhonov (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 711205a2804SDmitri Tikhonov (head1)->tqh_last = (head2)->tqh_last; \ 712205a2804SDmitri Tikhonov TAILQ_INIT((head2)); \ 713205a2804SDmitri Tikhonov QMD_TRACE_HEAD(head1); \ 714205a2804SDmitri Tikhonov QMD_TRACE_HEAD(head2); \ 715205a2804SDmitri Tikhonov } \ 716205a2804SDmitri Tikhonov} while (0) 717205a2804SDmitri Tikhonov 718205a2804SDmitri Tikhonov#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 719205a2804SDmitri Tikhonov 720205a2804SDmitri Tikhonov#define TAILQ_FIRST(head) ((head)->tqh_first) 721205a2804SDmitri Tikhonov 722205a2804SDmitri Tikhonov#define TAILQ_FOREACH(var, head, field) \ 723205a2804SDmitri Tikhonov for ((var) = TAILQ_FIRST((head)); \ 724205a2804SDmitri Tikhonov (var); \ 725205a2804SDmitri Tikhonov (var) = TAILQ_NEXT((var), field)) 726205a2804SDmitri Tikhonov 727205a2804SDmitri Tikhonov#define TAILQ_FOREACH_FROM(var, head, field) \ 728205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 729205a2804SDmitri Tikhonov (var); \ 730205a2804SDmitri Tikhonov (var) = TAILQ_NEXT((var), field)) 731205a2804SDmitri Tikhonov 732205a2804SDmitri Tikhonov#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 733205a2804SDmitri Tikhonov for ((var) = TAILQ_FIRST((head)); \ 734205a2804SDmitri Tikhonov (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 735205a2804SDmitri Tikhonov (var) = (tvar)) 736205a2804SDmitri Tikhonov 737205a2804SDmitri Tikhonov#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 738205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 739205a2804SDmitri Tikhonov (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 740205a2804SDmitri Tikhonov (var) = (tvar)) 741205a2804SDmitri Tikhonov 742205a2804SDmitri Tikhonov#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 743205a2804SDmitri Tikhonov for ((var) = TAILQ_LAST((head), headname); \ 744205a2804SDmitri Tikhonov (var); \ 745205a2804SDmitri Tikhonov (var) = TAILQ_PREV((var), headname, field)) 746205a2804SDmitri Tikhonov 747205a2804SDmitri Tikhonov#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 748205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 749205a2804SDmitri Tikhonov (var); \ 750205a2804SDmitri Tikhonov (var) = TAILQ_PREV((var), headname, field)) 751205a2804SDmitri Tikhonov 752205a2804SDmitri Tikhonov#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 753205a2804SDmitri Tikhonov for ((var) = TAILQ_LAST((head), headname); \ 754205a2804SDmitri Tikhonov (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 755205a2804SDmitri Tikhonov (var) = (tvar)) 756205a2804SDmitri Tikhonov 757205a2804SDmitri Tikhonov#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \ 758205a2804SDmitri Tikhonov for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 759205a2804SDmitri Tikhonov (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 760205a2804SDmitri Tikhonov (var) = (tvar)) 761205a2804SDmitri Tikhonov 762205a2804SDmitri Tikhonov#define TAILQ_INIT(head) do { \ 763205a2804SDmitri Tikhonov TAILQ_FIRST((head)) = NULL; \ 764205a2804SDmitri Tikhonov (head)->tqh_last = &TAILQ_FIRST((head)); \ 765205a2804SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 766205a2804SDmitri Tikhonov} while (0) 767205a2804SDmitri Tikhonov 768205a2804SDmitri Tikhonov#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 769205a2804SDmitri Tikhonov QMD_TAILQ_CHECK_NEXT(listelm, field); \ 770205a2804SDmitri Tikhonov if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 771205a2804SDmitri Tikhonov TAILQ_NEXT((elm), field)->field.tqe_prev = \ 772205a2804SDmitri Tikhonov &TAILQ_NEXT((elm), field); \ 773205a2804SDmitri Tikhonov else { \ 774205a2804SDmitri Tikhonov (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 775205a2804SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 776205a2804SDmitri Tikhonov } \ 777205a2804SDmitri Tikhonov TAILQ_NEXT((listelm), field) = (elm); \ 778205a2804SDmitri Tikhonov (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 779205a2804SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 780205a2804SDmitri Tikhonov QMD_TRACE_ELEM(&(listelm)->field); \ 781205a2804SDmitri Tikhonov} while (0) 782205a2804SDmitri Tikhonov 783205a2804SDmitri Tikhonov#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 784205a2804SDmitri Tikhonov QMD_TAILQ_CHECK_PREV(listelm, field); \ 785205a2804SDmitri Tikhonov (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 786205a2804SDmitri Tikhonov TAILQ_NEXT((elm), field) = (listelm); \ 787205a2804SDmitri Tikhonov *(listelm)->field.tqe_prev = (elm); \ 788205a2804SDmitri Tikhonov (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 789205a2804SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 790205a2804SDmitri Tikhonov QMD_TRACE_ELEM(&(listelm)->field); \ 791205a2804SDmitri Tikhonov} while (0) 792205a2804SDmitri Tikhonov 793205a2804SDmitri Tikhonov#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 794205a2804SDmitri Tikhonov QMD_TAILQ_CHECK_HEAD(head, field); \ 795205a2804SDmitri Tikhonov if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 796205a2804SDmitri Tikhonov TAILQ_FIRST((head))->field.tqe_prev = \ 797205a2804SDmitri Tikhonov &TAILQ_NEXT((elm), field); \ 798205a2804SDmitri Tikhonov else \ 799205a2804SDmitri Tikhonov (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 800205a2804SDmitri Tikhonov TAILQ_FIRST((head)) = (elm); \ 801205a2804SDmitri Tikhonov (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 802205a2804SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 803205a2804SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 804205a2804SDmitri Tikhonov} while (0) 805205a2804SDmitri Tikhonov 806205a2804SDmitri Tikhonov#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 807205a2804SDmitri Tikhonov QMD_TAILQ_CHECK_TAIL(head, field); \ 808205a2804SDmitri Tikhonov TAILQ_NEXT((elm), field) = NULL; \ 809205a2804SDmitri Tikhonov (elm)->field.tqe_prev = (head)->tqh_last; \ 810205a2804SDmitri Tikhonov *(head)->tqh_last = (elm); \ 811205a2804SDmitri Tikhonov (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 812205a2804SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 813205a2804SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 814205a2804SDmitri Tikhonov} while (0) 815205a2804SDmitri Tikhonov 816205a2804SDmitri Tikhonov#define TAILQ_LAST(head, headname) \ 817205a2804SDmitri Tikhonov (*(((struct headname *)((head)->tqh_last))->tqh_last)) 818205a2804SDmitri Tikhonov 819205a2804SDmitri Tikhonov#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 820205a2804SDmitri Tikhonov 821205a2804SDmitri Tikhonov#define TAILQ_PREV(elm, headname, field) \ 822205a2804SDmitri Tikhonov (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 823205a2804SDmitri Tikhonov 824205a2804SDmitri Tikhonov#define TAILQ_REMOVE(head, elm, field) do { \ 825205a2804SDmitri Tikhonov QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ 826205a2804SDmitri Tikhonov QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ 827205a2804SDmitri Tikhonov QMD_TAILQ_CHECK_NEXT(elm, field); \ 828205a2804SDmitri Tikhonov QMD_TAILQ_CHECK_PREV(elm, field); \ 829205a2804SDmitri Tikhonov if ((TAILQ_NEXT((elm), field)) != NULL) \ 830205a2804SDmitri Tikhonov TAILQ_NEXT((elm), field)->field.tqe_prev = \ 831205a2804SDmitri Tikhonov (elm)->field.tqe_prev; \ 832205a2804SDmitri Tikhonov else { \ 833205a2804SDmitri Tikhonov (head)->tqh_last = (elm)->field.tqe_prev; \ 834205a2804SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 835205a2804SDmitri Tikhonov } \ 836205a2804SDmitri Tikhonov *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 837205a2804SDmitri Tikhonov TRASHIT(*oldnext); \ 838205a2804SDmitri Tikhonov TRASHIT(*oldprev); \ 839205a2804SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 840205a2804SDmitri Tikhonov} while (0) 841205a2804SDmitri Tikhonov 842205a2804SDmitri Tikhonov#define TAILQ_SWAP(head1, head2, type, field) do { \ 843205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ 844205a2804SDmitri Tikhonov QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 845205a2804SDmitri Tikhonov (head1)->tqh_first = (head2)->tqh_first; \ 846205a2804SDmitri Tikhonov (head1)->tqh_last = (head2)->tqh_last; \ 847205a2804SDmitri Tikhonov (head2)->tqh_first = swap_first; \ 848205a2804SDmitri Tikhonov (head2)->tqh_last = swap_last; \ 849205a2804SDmitri Tikhonov if ((swap_first = (head1)->tqh_first) != NULL) \ 850205a2804SDmitri Tikhonov swap_first->field.tqe_prev = &(head1)->tqh_first; \ 851205a2804SDmitri Tikhonov else \ 852205a2804SDmitri Tikhonov (head1)->tqh_last = &(head1)->tqh_first; \ 853205a2804SDmitri Tikhonov if ((swap_first = (head2)->tqh_first) != NULL) \ 854205a2804SDmitri Tikhonov swap_first->field.tqe_prev = &(head2)->tqh_first; \ 855205a2804SDmitri Tikhonov else \ 856205a2804SDmitri Tikhonov (head2)->tqh_last = &(head2)->tqh_first; \ 857205a2804SDmitri Tikhonov} while (0) 858205a2804SDmitri Tikhonov 859205a2804SDmitri Tikhonov#endif /* !_SYS_QUEUE_H_ */ 860