175ce1599SDmitri Tikhonov/*- 275ce1599SDmitri Tikhonov * SPDX-License-Identifier: BSD-3-Clause 375ce1599SDmitri Tikhonov * 475ce1599SDmitri Tikhonov * Copyright (c) 1991, 1993 575ce1599SDmitri Tikhonov * The Regents of the University of California. All rights reserved. 675ce1599SDmitri Tikhonov * 775ce1599SDmitri Tikhonov * Redistribution and use in source and binary forms, with or without 875ce1599SDmitri Tikhonov * modification, are permitted provided that the following conditions 975ce1599SDmitri Tikhonov * are met: 1075ce1599SDmitri Tikhonov * 1. Redistributions of source code must retain the above copyright 1175ce1599SDmitri Tikhonov * notice, this list of conditions and the following disclaimer. 1275ce1599SDmitri Tikhonov * 2. Redistributions in binary form must reproduce the above copyright 1375ce1599SDmitri Tikhonov * notice, this list of conditions and the following disclaimer in the 1475ce1599SDmitri Tikhonov * documentation and/or other materials provided with the distribution. 1575ce1599SDmitri Tikhonov * 3. Neither the name of the University nor the names of its contributors 1675ce1599SDmitri Tikhonov * may be used to endorse or promote products derived from this software 1775ce1599SDmitri Tikhonov * without specific prior written permission. 1875ce1599SDmitri Tikhonov * 1975ce1599SDmitri Tikhonov * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2075ce1599SDmitri Tikhonov * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2175ce1599SDmitri Tikhonov * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2275ce1599SDmitri Tikhonov * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2375ce1599SDmitri Tikhonov * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2475ce1599SDmitri Tikhonov * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2575ce1599SDmitri Tikhonov * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2675ce1599SDmitri Tikhonov * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2775ce1599SDmitri Tikhonov * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2875ce1599SDmitri Tikhonov * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2975ce1599SDmitri Tikhonov * SUCH DAMAGE. 3075ce1599SDmitri Tikhonov * 3175ce1599SDmitri Tikhonov * @(#)queue.h 8.5 (Berkeley) 8/20/94 3275ce1599SDmitri Tikhonov * $FreeBSD$ 3375ce1599SDmitri Tikhonov */ 3475ce1599SDmitri Tikhonov 3575ce1599SDmitri Tikhonov#ifndef _SYS_QUEUE_H_ 3675ce1599SDmitri Tikhonov#define _SYS_QUEUE_H_ 3775ce1599SDmitri Tikhonov 3875ce1599SDmitri Tikhonov 3975ce1599SDmitri Tikhonov/* 4075ce1599SDmitri Tikhonov * This file defines four types of data structures: singly-linked lists, 4175ce1599SDmitri Tikhonov * singly-linked tail queues, lists and tail queues. 4275ce1599SDmitri Tikhonov * 4375ce1599SDmitri Tikhonov * A singly-linked list is headed by a single forward pointer. The elements 4475ce1599SDmitri Tikhonov * are singly linked for minimum space and pointer manipulation overhead at 4575ce1599SDmitri Tikhonov * the expense of O(n) removal for arbitrary elements. New elements can be 4675ce1599SDmitri Tikhonov * added to the list after an existing element or at the head of the list. 4775ce1599SDmitri Tikhonov * Elements being removed from the head of the list should use the explicit 4875ce1599SDmitri Tikhonov * macro for this purpose for optimum efficiency. A singly-linked list may 4975ce1599SDmitri Tikhonov * only be traversed in the forward direction. Singly-linked lists are ideal 5075ce1599SDmitri Tikhonov * for applications with large datasets and few or no removals or for 5175ce1599SDmitri Tikhonov * implementing a LIFO queue. 5275ce1599SDmitri Tikhonov * 5375ce1599SDmitri Tikhonov * A singly-linked tail queue is headed by a pair of pointers, one to the 5475ce1599SDmitri Tikhonov * head of the list and the other to the tail of the list. The elements are 5575ce1599SDmitri Tikhonov * singly linked for minimum space and pointer manipulation overhead at the 5675ce1599SDmitri Tikhonov * expense of O(n) removal for arbitrary elements. New elements can be added 5775ce1599SDmitri Tikhonov * to the list after an existing element, at the head of the list, or at the 5875ce1599SDmitri Tikhonov * end of the list. Elements being removed from the head of the tail queue 5975ce1599SDmitri Tikhonov * should use the explicit macro for this purpose for optimum efficiency. 6075ce1599SDmitri Tikhonov * A singly-linked tail queue may only be traversed in the forward direction. 6175ce1599SDmitri Tikhonov * Singly-linked tail queues are ideal for applications with large datasets 6275ce1599SDmitri Tikhonov * and few or no removals or for implementing a FIFO queue. 6375ce1599SDmitri Tikhonov * 6475ce1599SDmitri Tikhonov * A list is headed by a single forward pointer (or an array of forward 6575ce1599SDmitri Tikhonov * pointers for a hash table header). The elements are doubly linked 6675ce1599SDmitri Tikhonov * so that an arbitrary element can be removed without a need to 6775ce1599SDmitri Tikhonov * traverse the list. New elements can be added to the list before 6875ce1599SDmitri Tikhonov * or after an existing element or at the head of the list. A list 6975ce1599SDmitri Tikhonov * may be traversed in either direction. 7075ce1599SDmitri Tikhonov * 7175ce1599SDmitri Tikhonov * A tail queue is headed by a pair of pointers, one to the head of the 7275ce1599SDmitri Tikhonov * list and the other to the tail of the list. The elements are doubly 7375ce1599SDmitri Tikhonov * linked so that an arbitrary element can be removed without a need to 7475ce1599SDmitri Tikhonov * traverse the list. New elements can be added to the list before or 7575ce1599SDmitri Tikhonov * after an existing element, at the head of the list, or at the end of 7675ce1599SDmitri Tikhonov * the list. A tail queue may be traversed in either direction. 7775ce1599SDmitri Tikhonov * 7875ce1599SDmitri Tikhonov * For details on the use of these macros, see the queue(3) manual page. 7975ce1599SDmitri Tikhonov * 8075ce1599SDmitri Tikhonov * Below is a summary of implemented functions where: 8175ce1599SDmitri Tikhonov * + means the macro is available 8275ce1599SDmitri Tikhonov * - means the macro is not available 8375ce1599SDmitri Tikhonov * s means the macro is available but is slow (runs in O(n) time) 8475ce1599SDmitri Tikhonov * 8575ce1599SDmitri Tikhonov * SLIST LIST STAILQ TAILQ 8675ce1599SDmitri Tikhonov * _HEAD + + + + 8775ce1599SDmitri Tikhonov * _CLASS_HEAD + + + + 8875ce1599SDmitri Tikhonov * _HEAD_INITIALIZER + + + + 8975ce1599SDmitri Tikhonov * _ENTRY + + + + 9075ce1599SDmitri Tikhonov * _CLASS_ENTRY + + + + 9175ce1599SDmitri Tikhonov * _INIT + + + + 9275ce1599SDmitri Tikhonov * _EMPTY + + + + 9375ce1599SDmitri Tikhonov * _FIRST + + + + 9475ce1599SDmitri Tikhonov * _NEXT + + + + 9575ce1599SDmitri Tikhonov * _PREV - + - + 9675ce1599SDmitri Tikhonov * _LAST - - + + 9775ce1599SDmitri Tikhonov * _FOREACH + + + + 9875ce1599SDmitri Tikhonov * _FOREACH_FROM + + + + 9975ce1599SDmitri Tikhonov * _FOREACH_SAFE + + + + 10075ce1599SDmitri Tikhonov * _FOREACH_FROM_SAFE + + + + 10175ce1599SDmitri Tikhonov * _FOREACH_REVERSE - - - + 10275ce1599SDmitri Tikhonov * _FOREACH_REVERSE_FROM - - - + 10375ce1599SDmitri Tikhonov * _FOREACH_REVERSE_SAFE - - - + 10475ce1599SDmitri Tikhonov * _FOREACH_REVERSE_FROM_SAFE - - - + 10575ce1599SDmitri Tikhonov * _INSERT_HEAD + + + + 10675ce1599SDmitri Tikhonov * _INSERT_BEFORE - + - + 10775ce1599SDmitri Tikhonov * _INSERT_AFTER + + + + 10875ce1599SDmitri Tikhonov * _INSERT_TAIL - - + + 10975ce1599SDmitri Tikhonov * _CONCAT s s + + 11075ce1599SDmitri Tikhonov * _REMOVE_AFTER + - + - 11175ce1599SDmitri Tikhonov * _REMOVE_HEAD + - + - 11275ce1599SDmitri Tikhonov * _REMOVE s + s + 11375ce1599SDmitri Tikhonov * _SWAP + + + + 11475ce1599SDmitri Tikhonov * 11575ce1599SDmitri Tikhonov */ 11675ce1599SDmitri Tikhonov#ifdef QUEUE_MACRO_DEBUG 11775ce1599SDmitri Tikhonov#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH 11875ce1599SDmitri Tikhonov#define QUEUE_MACRO_DEBUG_TRACE 11975ce1599SDmitri Tikhonov#define QUEUE_MACRO_DEBUG_TRASH 12075ce1599SDmitri Tikhonov#endif 12175ce1599SDmitri Tikhonov 12275ce1599SDmitri Tikhonov#ifdef QUEUE_MACRO_DEBUG_TRACE 12375ce1599SDmitri Tikhonov/* Store the last 2 places the queue element or head was altered */ 12475ce1599SDmitri Tikhonovstruct qm_trace { 12575ce1599SDmitri Tikhonov unsigned long lastline; 12675ce1599SDmitri Tikhonov unsigned long prevline; 12775ce1599SDmitri Tikhonov const char *lastfile; 12875ce1599SDmitri Tikhonov const char *prevfile; 12975ce1599SDmitri Tikhonov}; 13075ce1599SDmitri Tikhonov 13175ce1599SDmitri Tikhonov#define TRACEBUF struct qm_trace trace; 13275ce1599SDmitri Tikhonov#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } , 13375ce1599SDmitri Tikhonov 13475ce1599SDmitri Tikhonov#define QMD_TRACE_HEAD(head) do { \ 13575ce1599SDmitri Tikhonov (head)->trace.prevline = (head)->trace.lastline; \ 13675ce1599SDmitri Tikhonov (head)->trace.prevfile = (head)->trace.lastfile; \ 13775ce1599SDmitri Tikhonov (head)->trace.lastline = __LINE__; \ 13875ce1599SDmitri Tikhonov (head)->trace.lastfile = __FILE__; \ 13975ce1599SDmitri Tikhonov} while (0) 14075ce1599SDmitri Tikhonov 14175ce1599SDmitri Tikhonov#define QMD_TRACE_ELEM(elem) do { \ 14275ce1599SDmitri Tikhonov (elem)->trace.prevline = (elem)->trace.lastline; \ 14375ce1599SDmitri Tikhonov (elem)->trace.prevfile = (elem)->trace.lastfile; \ 14475ce1599SDmitri Tikhonov (elem)->trace.lastline = __LINE__; \ 14575ce1599SDmitri Tikhonov (elem)->trace.lastfile = __FILE__; \ 14675ce1599SDmitri Tikhonov} while (0) 14775ce1599SDmitri Tikhonov 14875ce1599SDmitri Tikhonov#else /* !QUEUE_MACRO_DEBUG_TRACE */ 14975ce1599SDmitri Tikhonov#define QMD_TRACE_ELEM(elem) 15075ce1599SDmitri Tikhonov#define QMD_TRACE_HEAD(head) 15175ce1599SDmitri Tikhonov#define TRACEBUF 15275ce1599SDmitri Tikhonov#define TRACEBUF_INITIALIZER 15375ce1599SDmitri Tikhonov#endif /* QUEUE_MACRO_DEBUG_TRACE */ 15475ce1599SDmitri Tikhonov 15575ce1599SDmitri Tikhonov#ifdef QUEUE_MACRO_DEBUG_TRASH 15675ce1599SDmitri Tikhonov#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 15775ce1599SDmitri Tikhonov#define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1) 15875ce1599SDmitri Tikhonov#else /* !QUEUE_MACRO_DEBUG_TRASH */ 15975ce1599SDmitri Tikhonov#define TRASHIT(x) 16075ce1599SDmitri Tikhonov#define QMD_IS_TRASHED(x) 0 16175ce1599SDmitri Tikhonov#endif /* QUEUE_MACRO_DEBUG_TRASH */ 16275ce1599SDmitri Tikhonov 16375ce1599SDmitri Tikhonov#if defined(QUEUE_MACRO_DEBUG_TRACE) || defined(QUEUE_MACRO_DEBUG_TRASH) 16475ce1599SDmitri Tikhonov#define QMD_SAVELINK(name, link) void **name = (void *)&(link) 16575ce1599SDmitri Tikhonov#else /* !QUEUE_MACRO_DEBUG_TRACE && !QUEUE_MACRO_DEBUG_TRASH */ 16675ce1599SDmitri Tikhonov#define QMD_SAVELINK(name, link) 16775ce1599SDmitri Tikhonov#endif /* QUEUE_MACRO_DEBUG_TRACE || QUEUE_MACRO_DEBUG_TRASH */ 16875ce1599SDmitri Tikhonov 16975ce1599SDmitri Tikhonov#ifdef __cplusplus 17075ce1599SDmitri Tikhonov/* 17175ce1599SDmitri Tikhonov * In C++ there can be structure lists and class lists: 17275ce1599SDmitri Tikhonov */ 17375ce1599SDmitri Tikhonov#define QUEUE_TYPEOF(type) type 17475ce1599SDmitri Tikhonov#else 17575ce1599SDmitri Tikhonov#define QUEUE_TYPEOF(type) struct type 17675ce1599SDmitri Tikhonov#endif 17775ce1599SDmitri Tikhonov 17875ce1599SDmitri Tikhonov/* 17975ce1599SDmitri Tikhonov * Singly-linked List declarations. 18075ce1599SDmitri Tikhonov */ 18175ce1599SDmitri Tikhonov#define SLIST_HEAD(name, type) \ 18275ce1599SDmitri Tikhonovstruct name { \ 18375ce1599SDmitri Tikhonov struct type *slh_first; /* first element */ \ 18475ce1599SDmitri Tikhonov} 18575ce1599SDmitri Tikhonov 18675ce1599SDmitri Tikhonov#define SLIST_CLASS_HEAD(name, type) \ 18775ce1599SDmitri Tikhonovstruct name { \ 18875ce1599SDmitri Tikhonov class type *slh_first; /* first element */ \ 18975ce1599SDmitri Tikhonov} 19075ce1599SDmitri Tikhonov 19175ce1599SDmitri Tikhonov#define SLIST_HEAD_INITIALIZER(head) \ 19275ce1599SDmitri Tikhonov { NULL } 19375ce1599SDmitri Tikhonov 19475ce1599SDmitri Tikhonov#define SLIST_ENTRY(type) \ 19575ce1599SDmitri Tikhonovstruct { \ 19675ce1599SDmitri Tikhonov struct type *sle_next; /* next element */ \ 19775ce1599SDmitri Tikhonov} 19875ce1599SDmitri Tikhonov 19975ce1599SDmitri Tikhonov#define SLIST_CLASS_ENTRY(type) \ 20075ce1599SDmitri Tikhonovstruct { \ 20175ce1599SDmitri Tikhonov class type *sle_next; /* next element */ \ 20275ce1599SDmitri Tikhonov} 20375ce1599SDmitri Tikhonov 20475ce1599SDmitri Tikhonov/* 20575ce1599SDmitri Tikhonov * Singly-linked List functions. 20675ce1599SDmitri Tikhonov */ 20775ce1599SDmitri Tikhonov#if (defined(_KERNEL) && defined(INVARIANTS)) 20875ce1599SDmitri Tikhonov#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do { \ 20975ce1599SDmitri Tikhonov if (*(prevp) != (elm)) \ 21075ce1599SDmitri Tikhonov panic("Bad prevptr *(%p) == %p != %p", \ 21175ce1599SDmitri Tikhonov (prevp), *(prevp), (elm)); \ 21275ce1599SDmitri Tikhonov} while (0) 21375ce1599SDmitri Tikhonov#else 21475ce1599SDmitri Tikhonov#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) 21575ce1599SDmitri Tikhonov#endif 21675ce1599SDmitri Tikhonov 21775ce1599SDmitri Tikhonov#define SLIST_CONCAT(head1, head2, type, field) do { \ 21875ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ 21975ce1599SDmitri Tikhonov if (curelm == NULL) { \ 22075ce1599SDmitri Tikhonov if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ 22175ce1599SDmitri Tikhonov SLIST_INIT(head2); \ 22275ce1599SDmitri Tikhonov } else if (SLIST_FIRST(head2) != NULL) { \ 22375ce1599SDmitri Tikhonov while (SLIST_NEXT(curelm, field) != NULL) \ 22475ce1599SDmitri Tikhonov curelm = SLIST_NEXT(curelm, field); \ 22575ce1599SDmitri Tikhonov SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ 22675ce1599SDmitri Tikhonov SLIST_INIT(head2); \ 22775ce1599SDmitri Tikhonov } \ 22875ce1599SDmitri Tikhonov} while (0) 22975ce1599SDmitri Tikhonov 23075ce1599SDmitri Tikhonov#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 23175ce1599SDmitri Tikhonov 23275ce1599SDmitri Tikhonov#define SLIST_FIRST(head) ((head)->slh_first) 23375ce1599SDmitri Tikhonov 23475ce1599SDmitri Tikhonov#define SLIST_FOREACH(var, head, field) \ 23575ce1599SDmitri Tikhonov for ((var) = SLIST_FIRST((head)); \ 23675ce1599SDmitri Tikhonov (var); \ 23775ce1599SDmitri Tikhonov (var) = SLIST_NEXT((var), field)) 23875ce1599SDmitri Tikhonov 23975ce1599SDmitri Tikhonov#define SLIST_FOREACH_FROM(var, head, field) \ 24075ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 24175ce1599SDmitri Tikhonov (var); \ 24275ce1599SDmitri Tikhonov (var) = SLIST_NEXT((var), field)) 24375ce1599SDmitri Tikhonov 24475ce1599SDmitri Tikhonov#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 24575ce1599SDmitri Tikhonov for ((var) = SLIST_FIRST((head)); \ 24675ce1599SDmitri Tikhonov (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 24775ce1599SDmitri Tikhonov (var) = (tvar)) 24875ce1599SDmitri Tikhonov 24975ce1599SDmitri Tikhonov#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 25075ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 25175ce1599SDmitri Tikhonov (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 25275ce1599SDmitri Tikhonov (var) = (tvar)) 25375ce1599SDmitri Tikhonov 25475ce1599SDmitri Tikhonov#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 25575ce1599SDmitri Tikhonov for ((varp) = &SLIST_FIRST((head)); \ 25675ce1599SDmitri Tikhonov ((var) = *(varp)) != NULL; \ 25775ce1599SDmitri Tikhonov (varp) = &SLIST_NEXT((var), field)) 25875ce1599SDmitri Tikhonov 25975ce1599SDmitri Tikhonov#define SLIST_INIT(head) do { \ 26075ce1599SDmitri Tikhonov SLIST_FIRST((head)) = NULL; \ 26175ce1599SDmitri Tikhonov} while (0) 26275ce1599SDmitri Tikhonov 26375ce1599SDmitri Tikhonov#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 26475ce1599SDmitri Tikhonov SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 26575ce1599SDmitri Tikhonov SLIST_NEXT((slistelm), field) = (elm); \ 26675ce1599SDmitri Tikhonov} while (0) 26775ce1599SDmitri Tikhonov 26875ce1599SDmitri Tikhonov#define SLIST_INSERT_HEAD(head, elm, field) do { \ 26975ce1599SDmitri Tikhonov SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 27075ce1599SDmitri Tikhonov SLIST_FIRST((head)) = (elm); \ 27175ce1599SDmitri Tikhonov} while (0) 27275ce1599SDmitri Tikhonov 27375ce1599SDmitri Tikhonov#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 27475ce1599SDmitri Tikhonov 27575ce1599SDmitri Tikhonov#define SLIST_REMOVE(head, elm, type, field) do { \ 27675ce1599SDmitri Tikhonov QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ 27775ce1599SDmitri Tikhonov if (SLIST_FIRST((head)) == (elm)) { \ 27875ce1599SDmitri Tikhonov SLIST_REMOVE_HEAD((head), field); \ 27975ce1599SDmitri Tikhonov } \ 28075ce1599SDmitri Tikhonov else { \ 28175ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \ 28275ce1599SDmitri Tikhonov while (SLIST_NEXT(curelm, field) != (elm)) \ 28375ce1599SDmitri Tikhonov curelm = SLIST_NEXT(curelm, field); \ 28475ce1599SDmitri Tikhonov SLIST_REMOVE_AFTER(curelm, field); \ 28575ce1599SDmitri Tikhonov } \ 28675ce1599SDmitri Tikhonov TRASHIT(*oldnext); \ 28775ce1599SDmitri Tikhonov} while (0) 28875ce1599SDmitri Tikhonov 28975ce1599SDmitri Tikhonov#define SLIST_REMOVE_AFTER(elm, field) do { \ 29075ce1599SDmitri Tikhonov SLIST_NEXT(elm, field) = \ 29175ce1599SDmitri Tikhonov SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 29275ce1599SDmitri Tikhonov} while (0) 29375ce1599SDmitri Tikhonov 29475ce1599SDmitri Tikhonov#define SLIST_REMOVE_HEAD(head, field) do { \ 29575ce1599SDmitri Tikhonov SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 29675ce1599SDmitri Tikhonov} while (0) 29775ce1599SDmitri Tikhonov 29875ce1599SDmitri Tikhonov#define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \ 29975ce1599SDmitri Tikhonov QMD_SLIST_CHECK_PREVPTR(prevp, elm); \ 30075ce1599SDmitri Tikhonov *(prevp) = SLIST_NEXT(elm, field); \ 30175ce1599SDmitri Tikhonov TRASHIT((elm)->field.sle_next); \ 30275ce1599SDmitri Tikhonov} while (0) 30375ce1599SDmitri Tikhonov 30475ce1599SDmitri Tikhonov#define SLIST_SWAP(head1, head2, type) do { \ 30575ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ 30675ce1599SDmitri Tikhonov SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 30775ce1599SDmitri Tikhonov SLIST_FIRST(head2) = swap_first; \ 30875ce1599SDmitri Tikhonov} while (0) 30975ce1599SDmitri Tikhonov 31075ce1599SDmitri Tikhonov/* 31175ce1599SDmitri Tikhonov * Singly-linked Tail queue declarations. 31275ce1599SDmitri Tikhonov */ 31375ce1599SDmitri Tikhonov#define STAILQ_HEAD(name, type) \ 31475ce1599SDmitri Tikhonovstruct name { \ 31575ce1599SDmitri Tikhonov struct type *stqh_first;/* first element */ \ 31675ce1599SDmitri Tikhonov struct type **stqh_last;/* addr of last next element */ \ 31775ce1599SDmitri Tikhonov} 31875ce1599SDmitri Tikhonov 31975ce1599SDmitri Tikhonov#define STAILQ_CLASS_HEAD(name, type) \ 32075ce1599SDmitri Tikhonovstruct name { \ 32175ce1599SDmitri Tikhonov class type *stqh_first; /* first element */ \ 32275ce1599SDmitri Tikhonov class type **stqh_last; /* addr of last next element */ \ 32375ce1599SDmitri Tikhonov} 32475ce1599SDmitri Tikhonov 32575ce1599SDmitri Tikhonov#define STAILQ_HEAD_INITIALIZER(head) \ 32675ce1599SDmitri Tikhonov { NULL, &(head).stqh_first } 32775ce1599SDmitri Tikhonov 32875ce1599SDmitri Tikhonov#define STAILQ_ENTRY(type) \ 32975ce1599SDmitri Tikhonovstruct { \ 33075ce1599SDmitri Tikhonov struct type *stqe_next; /* next element */ \ 33175ce1599SDmitri Tikhonov} 33275ce1599SDmitri Tikhonov 33375ce1599SDmitri Tikhonov#define STAILQ_CLASS_ENTRY(type) \ 33475ce1599SDmitri Tikhonovstruct { \ 33575ce1599SDmitri Tikhonov class type *stqe_next; /* next element */ \ 33675ce1599SDmitri Tikhonov} 33775ce1599SDmitri Tikhonov 33875ce1599SDmitri Tikhonov/* 33975ce1599SDmitri Tikhonov * Singly-linked Tail queue functions. 34075ce1599SDmitri Tikhonov */ 34175ce1599SDmitri Tikhonov#define STAILQ_CONCAT(head1, head2) do { \ 34275ce1599SDmitri Tikhonov if (!STAILQ_EMPTY((head2))) { \ 34375ce1599SDmitri Tikhonov *(head1)->stqh_last = (head2)->stqh_first; \ 34475ce1599SDmitri Tikhonov (head1)->stqh_last = (head2)->stqh_last; \ 34575ce1599SDmitri Tikhonov STAILQ_INIT((head2)); \ 34675ce1599SDmitri Tikhonov } \ 34775ce1599SDmitri Tikhonov} while (0) 34875ce1599SDmitri Tikhonov 34975ce1599SDmitri Tikhonov#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 35075ce1599SDmitri Tikhonov 35175ce1599SDmitri Tikhonov#define STAILQ_FIRST(head) ((head)->stqh_first) 35275ce1599SDmitri Tikhonov 35375ce1599SDmitri Tikhonov#define STAILQ_FOREACH(var, head, field) \ 35475ce1599SDmitri Tikhonov for((var) = STAILQ_FIRST((head)); \ 35575ce1599SDmitri Tikhonov (var); \ 35675ce1599SDmitri Tikhonov (var) = STAILQ_NEXT((var), field)) 35775ce1599SDmitri Tikhonov 35875ce1599SDmitri Tikhonov#define STAILQ_FOREACH_FROM(var, head, field) \ 35975ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 36075ce1599SDmitri Tikhonov (var); \ 36175ce1599SDmitri Tikhonov (var) = STAILQ_NEXT((var), field)) 36275ce1599SDmitri Tikhonov 36375ce1599SDmitri Tikhonov#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 36475ce1599SDmitri Tikhonov for ((var) = STAILQ_FIRST((head)); \ 36575ce1599SDmitri Tikhonov (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 36675ce1599SDmitri Tikhonov (var) = (tvar)) 36775ce1599SDmitri Tikhonov 36875ce1599SDmitri Tikhonov#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 36975ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 37075ce1599SDmitri Tikhonov (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 37175ce1599SDmitri Tikhonov (var) = (tvar)) 37275ce1599SDmitri Tikhonov 37375ce1599SDmitri Tikhonov#define STAILQ_INIT(head) do { \ 37475ce1599SDmitri Tikhonov STAILQ_FIRST((head)) = NULL; \ 37575ce1599SDmitri Tikhonov (head)->stqh_last = &STAILQ_FIRST((head)); \ 37675ce1599SDmitri Tikhonov} while (0) 37775ce1599SDmitri Tikhonov 37875ce1599SDmitri Tikhonov#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 37975ce1599SDmitri Tikhonov if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 38075ce1599SDmitri Tikhonov (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 38175ce1599SDmitri Tikhonov STAILQ_NEXT((tqelm), field) = (elm); \ 38275ce1599SDmitri Tikhonov} while (0) 38375ce1599SDmitri Tikhonov 38475ce1599SDmitri Tikhonov#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 38575ce1599SDmitri Tikhonov if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 38675ce1599SDmitri Tikhonov (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 38775ce1599SDmitri Tikhonov STAILQ_FIRST((head)) = (elm); \ 38875ce1599SDmitri Tikhonov} while (0) 38975ce1599SDmitri Tikhonov 39075ce1599SDmitri Tikhonov#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 39175ce1599SDmitri Tikhonov STAILQ_NEXT((elm), field) = NULL; \ 39275ce1599SDmitri Tikhonov *(head)->stqh_last = (elm); \ 39375ce1599SDmitri Tikhonov (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 39475ce1599SDmitri Tikhonov} while (0) 39575ce1599SDmitri Tikhonov 39675ce1599SDmitri Tikhonov#define STAILQ_LAST(head, type, field) \ 39775ce1599SDmitri Tikhonov (STAILQ_EMPTY((head)) ? NULL : \ 39875ce1599SDmitri Tikhonov __containerof((head)->stqh_last, \ 39975ce1599SDmitri Tikhonov QUEUE_TYPEOF(type), field.stqe_next)) 40075ce1599SDmitri Tikhonov 40175ce1599SDmitri Tikhonov#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 40275ce1599SDmitri Tikhonov 40375ce1599SDmitri Tikhonov#define STAILQ_REMOVE(head, elm, type, field) do { \ 40475ce1599SDmitri Tikhonov QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ 40575ce1599SDmitri Tikhonov if (STAILQ_FIRST((head)) == (elm)) { \ 40675ce1599SDmitri Tikhonov STAILQ_REMOVE_HEAD((head), field); \ 40775ce1599SDmitri Tikhonov } \ 40875ce1599SDmitri Tikhonov else { \ 40975ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ 41075ce1599SDmitri Tikhonov while (STAILQ_NEXT(curelm, field) != (elm)) \ 41175ce1599SDmitri Tikhonov curelm = STAILQ_NEXT(curelm, field); \ 41275ce1599SDmitri Tikhonov STAILQ_REMOVE_AFTER(head, curelm, field); \ 41375ce1599SDmitri Tikhonov } \ 41475ce1599SDmitri Tikhonov TRASHIT(*oldnext); \ 41575ce1599SDmitri Tikhonov} while (0) 41675ce1599SDmitri Tikhonov 41775ce1599SDmitri Tikhonov#define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 41875ce1599SDmitri Tikhonov if ((STAILQ_NEXT(elm, field) = \ 41975ce1599SDmitri Tikhonov STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 42075ce1599SDmitri Tikhonov (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 42175ce1599SDmitri Tikhonov} while (0) 42275ce1599SDmitri Tikhonov 42375ce1599SDmitri Tikhonov#define STAILQ_REMOVE_HEAD(head, field) do { \ 42475ce1599SDmitri Tikhonov if ((STAILQ_FIRST((head)) = \ 42575ce1599SDmitri Tikhonov STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 42675ce1599SDmitri Tikhonov (head)->stqh_last = &STAILQ_FIRST((head)); \ 42775ce1599SDmitri Tikhonov} while (0) 42875ce1599SDmitri Tikhonov 42975ce1599SDmitri Tikhonov#define STAILQ_SWAP(head1, head2, type) do { \ 43075ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ 43175ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ 43275ce1599SDmitri Tikhonov STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 43375ce1599SDmitri Tikhonov (head1)->stqh_last = (head2)->stqh_last; \ 43475ce1599SDmitri Tikhonov STAILQ_FIRST(head2) = swap_first; \ 43575ce1599SDmitri Tikhonov (head2)->stqh_last = swap_last; \ 43675ce1599SDmitri Tikhonov if (STAILQ_EMPTY(head1)) \ 43775ce1599SDmitri Tikhonov (head1)->stqh_last = &STAILQ_FIRST(head1); \ 43875ce1599SDmitri Tikhonov if (STAILQ_EMPTY(head2)) \ 43975ce1599SDmitri Tikhonov (head2)->stqh_last = &STAILQ_FIRST(head2); \ 44075ce1599SDmitri Tikhonov} while (0) 44175ce1599SDmitri Tikhonov 44275ce1599SDmitri Tikhonov 44375ce1599SDmitri Tikhonov/* 44475ce1599SDmitri Tikhonov * List declarations. 44575ce1599SDmitri Tikhonov */ 44675ce1599SDmitri Tikhonov#define LIST_HEAD(name, type) \ 44775ce1599SDmitri Tikhonovstruct name { \ 44875ce1599SDmitri Tikhonov struct type *lh_first; /* first element */ \ 44975ce1599SDmitri Tikhonov} 45075ce1599SDmitri Tikhonov 45175ce1599SDmitri Tikhonov#define LIST_CLASS_HEAD(name, type) \ 45275ce1599SDmitri Tikhonovstruct name { \ 45375ce1599SDmitri Tikhonov class type *lh_first; /* first element */ \ 45475ce1599SDmitri Tikhonov} 45575ce1599SDmitri Tikhonov 45675ce1599SDmitri Tikhonov#define LIST_HEAD_INITIALIZER(head) \ 45775ce1599SDmitri Tikhonov { NULL } 45875ce1599SDmitri Tikhonov 45975ce1599SDmitri Tikhonov#define LIST_ENTRY(type) \ 46075ce1599SDmitri Tikhonovstruct { \ 46175ce1599SDmitri Tikhonov struct type *le_next; /* next element */ \ 46275ce1599SDmitri Tikhonov struct type **le_prev; /* address of previous next element */ \ 46375ce1599SDmitri Tikhonov} 46475ce1599SDmitri Tikhonov 46575ce1599SDmitri Tikhonov#define LIST_CLASS_ENTRY(type) \ 46675ce1599SDmitri Tikhonovstruct { \ 46775ce1599SDmitri Tikhonov class type *le_next; /* next element */ \ 46875ce1599SDmitri Tikhonov class type **le_prev; /* address of previous next element */ \ 46975ce1599SDmitri Tikhonov} 47075ce1599SDmitri Tikhonov 47175ce1599SDmitri Tikhonov/* 47275ce1599SDmitri Tikhonov * List functions. 47375ce1599SDmitri Tikhonov */ 47475ce1599SDmitri Tikhonov 47575ce1599SDmitri Tikhonov#if (defined(_KERNEL) && defined(INVARIANTS)) 47675ce1599SDmitri Tikhonov/* 47775ce1599SDmitri Tikhonov * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME) 47875ce1599SDmitri Tikhonov * 47975ce1599SDmitri Tikhonov * If the list is non-empty, validates that the first element of the list 48075ce1599SDmitri Tikhonov * points back at 'head.' 48175ce1599SDmitri Tikhonov */ 48275ce1599SDmitri Tikhonov#define QMD_LIST_CHECK_HEAD(head, field) do { \ 48375ce1599SDmitri Tikhonov if (LIST_FIRST((head)) != NULL && \ 48475ce1599SDmitri Tikhonov LIST_FIRST((head))->field.le_prev != \ 48575ce1599SDmitri Tikhonov &LIST_FIRST((head))) \ 48675ce1599SDmitri Tikhonov panic("Bad list head %p first->prev != head", (head)); \ 48775ce1599SDmitri Tikhonov} while (0) 48875ce1599SDmitri Tikhonov 48975ce1599SDmitri Tikhonov/* 49075ce1599SDmitri Tikhonov * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME) 49175ce1599SDmitri Tikhonov * 49275ce1599SDmitri Tikhonov * If an element follows 'elm' in the list, validates that the next element 49375ce1599SDmitri Tikhonov * points back at 'elm.' 49475ce1599SDmitri Tikhonov */ 49575ce1599SDmitri Tikhonov#define QMD_LIST_CHECK_NEXT(elm, field) do { \ 49675ce1599SDmitri Tikhonov if (LIST_NEXT((elm), field) != NULL && \ 49775ce1599SDmitri Tikhonov LIST_NEXT((elm), field)->field.le_prev != \ 49875ce1599SDmitri Tikhonov &((elm)->field.le_next)) \ 49975ce1599SDmitri Tikhonov panic("Bad link elm %p next->prev != elm", (elm)); \ 50075ce1599SDmitri Tikhonov} while (0) 50175ce1599SDmitri Tikhonov 50275ce1599SDmitri Tikhonov/* 50375ce1599SDmitri Tikhonov * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME) 50475ce1599SDmitri Tikhonov * 50575ce1599SDmitri Tikhonov * Validates that the previous element (or head of the list) points to 'elm.' 50675ce1599SDmitri Tikhonov */ 50775ce1599SDmitri Tikhonov#define QMD_LIST_CHECK_PREV(elm, field) do { \ 50875ce1599SDmitri Tikhonov if (*(elm)->field.le_prev != (elm)) \ 50975ce1599SDmitri Tikhonov panic("Bad link elm %p prev->next != elm", (elm)); \ 51075ce1599SDmitri Tikhonov} while (0) 51175ce1599SDmitri Tikhonov#else 51275ce1599SDmitri Tikhonov#define QMD_LIST_CHECK_HEAD(head, field) 51375ce1599SDmitri Tikhonov#define QMD_LIST_CHECK_NEXT(elm, field) 51475ce1599SDmitri Tikhonov#define QMD_LIST_CHECK_PREV(elm, field) 51575ce1599SDmitri Tikhonov#endif /* (_KERNEL && INVARIANTS) */ 51675ce1599SDmitri Tikhonov 51775ce1599SDmitri Tikhonov#define LIST_CONCAT(head1, head2, type, field) do { \ 51875ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ 51975ce1599SDmitri Tikhonov if (curelm == NULL) { \ 52075ce1599SDmitri Tikhonov if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ 52175ce1599SDmitri Tikhonov LIST_FIRST(head2)->field.le_prev = \ 52275ce1599SDmitri Tikhonov &LIST_FIRST((head1)); \ 52375ce1599SDmitri Tikhonov LIST_INIT(head2); \ 52475ce1599SDmitri Tikhonov } \ 52575ce1599SDmitri Tikhonov } else if (LIST_FIRST(head2) != NULL) { \ 52675ce1599SDmitri Tikhonov while (LIST_NEXT(curelm, field) != NULL) \ 52775ce1599SDmitri Tikhonov curelm = LIST_NEXT(curelm, field); \ 52875ce1599SDmitri Tikhonov LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ 52975ce1599SDmitri Tikhonov LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \ 53075ce1599SDmitri Tikhonov LIST_INIT(head2); \ 53175ce1599SDmitri Tikhonov } \ 53275ce1599SDmitri Tikhonov} while (0) 53375ce1599SDmitri Tikhonov 53475ce1599SDmitri Tikhonov#define LIST_EMPTY(head) ((head)->lh_first == NULL) 53575ce1599SDmitri Tikhonov 53675ce1599SDmitri Tikhonov#define LIST_FIRST(head) ((head)->lh_first) 53775ce1599SDmitri Tikhonov 53875ce1599SDmitri Tikhonov#define LIST_FOREACH(var, head, field) \ 53975ce1599SDmitri Tikhonov for ((var) = LIST_FIRST((head)); \ 54075ce1599SDmitri Tikhonov (var); \ 54175ce1599SDmitri Tikhonov (var) = LIST_NEXT((var), field)) 54275ce1599SDmitri Tikhonov 54375ce1599SDmitri Tikhonov#define LIST_FOREACH_FROM(var, head, field) \ 54475ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 54575ce1599SDmitri Tikhonov (var); \ 54675ce1599SDmitri Tikhonov (var) = LIST_NEXT((var), field)) 54775ce1599SDmitri Tikhonov 54875ce1599SDmitri Tikhonov#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 54975ce1599SDmitri Tikhonov for ((var) = LIST_FIRST((head)); \ 55075ce1599SDmitri Tikhonov (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 55175ce1599SDmitri Tikhonov (var) = (tvar)) 55275ce1599SDmitri Tikhonov 55375ce1599SDmitri Tikhonov#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 55475ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 55575ce1599SDmitri Tikhonov (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 55675ce1599SDmitri Tikhonov (var) = (tvar)) 55775ce1599SDmitri Tikhonov 55875ce1599SDmitri Tikhonov#define LIST_INIT(head) do { \ 55975ce1599SDmitri Tikhonov LIST_FIRST((head)) = NULL; \ 56075ce1599SDmitri Tikhonov} while (0) 56175ce1599SDmitri Tikhonov 56275ce1599SDmitri Tikhonov#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 56375ce1599SDmitri Tikhonov QMD_LIST_CHECK_NEXT(listelm, field); \ 56475ce1599SDmitri Tikhonov if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 56575ce1599SDmitri Tikhonov LIST_NEXT((listelm), field)->field.le_prev = \ 56675ce1599SDmitri Tikhonov &LIST_NEXT((elm), field); \ 56775ce1599SDmitri Tikhonov LIST_NEXT((listelm), field) = (elm); \ 56875ce1599SDmitri Tikhonov (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 56975ce1599SDmitri Tikhonov} while (0) 57075ce1599SDmitri Tikhonov 57175ce1599SDmitri Tikhonov#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 57275ce1599SDmitri Tikhonov QMD_LIST_CHECK_PREV(listelm, field); \ 57375ce1599SDmitri Tikhonov (elm)->field.le_prev = (listelm)->field.le_prev; \ 57475ce1599SDmitri Tikhonov LIST_NEXT((elm), field) = (listelm); \ 57575ce1599SDmitri Tikhonov *(listelm)->field.le_prev = (elm); \ 57675ce1599SDmitri Tikhonov (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 57775ce1599SDmitri Tikhonov} while (0) 57875ce1599SDmitri Tikhonov 57975ce1599SDmitri Tikhonov#define LIST_INSERT_HEAD(head, elm, field) do { \ 58075ce1599SDmitri Tikhonov QMD_LIST_CHECK_HEAD((head), field); \ 58175ce1599SDmitri Tikhonov if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 58275ce1599SDmitri Tikhonov LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 58375ce1599SDmitri Tikhonov LIST_FIRST((head)) = (elm); \ 58475ce1599SDmitri Tikhonov (elm)->field.le_prev = &LIST_FIRST((head)); \ 58575ce1599SDmitri Tikhonov} while (0) 58675ce1599SDmitri Tikhonov 58775ce1599SDmitri Tikhonov#define LIST_NEXT(elm, field) ((elm)->field.le_next) 58875ce1599SDmitri Tikhonov 58975ce1599SDmitri Tikhonov#define LIST_PREV(elm, head, type, field) \ 59075ce1599SDmitri Tikhonov ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 59175ce1599SDmitri Tikhonov __containerof((elm)->field.le_prev, \ 59275ce1599SDmitri Tikhonov QUEUE_TYPEOF(type), field.le_next)) 59375ce1599SDmitri Tikhonov 59475ce1599SDmitri Tikhonov#define LIST_REMOVE(elm, field) do { \ 59575ce1599SDmitri Tikhonov QMD_SAVELINK(oldnext, (elm)->field.le_next); \ 59675ce1599SDmitri Tikhonov QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ 59775ce1599SDmitri Tikhonov QMD_LIST_CHECK_NEXT(elm, field); \ 59875ce1599SDmitri Tikhonov QMD_LIST_CHECK_PREV(elm, field); \ 59975ce1599SDmitri Tikhonov if (LIST_NEXT((elm), field) != NULL) \ 60075ce1599SDmitri Tikhonov LIST_NEXT((elm), field)->field.le_prev = \ 60175ce1599SDmitri Tikhonov (elm)->field.le_prev; \ 60275ce1599SDmitri Tikhonov *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 60375ce1599SDmitri Tikhonov TRASHIT(*oldnext); \ 60475ce1599SDmitri Tikhonov TRASHIT(*oldprev); \ 60575ce1599SDmitri Tikhonov} while (0) 60675ce1599SDmitri Tikhonov 60775ce1599SDmitri Tikhonov#define LIST_SWAP(head1, head2, type, field) do { \ 60875ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 60975ce1599SDmitri Tikhonov LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 61075ce1599SDmitri Tikhonov LIST_FIRST((head2)) = swap_tmp; \ 61175ce1599SDmitri Tikhonov if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 61275ce1599SDmitri Tikhonov swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 61375ce1599SDmitri Tikhonov if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 61475ce1599SDmitri Tikhonov swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 61575ce1599SDmitri Tikhonov} while (0) 61675ce1599SDmitri Tikhonov 61775ce1599SDmitri Tikhonov/* 61875ce1599SDmitri Tikhonov * Tail queue declarations. 61975ce1599SDmitri Tikhonov */ 62075ce1599SDmitri Tikhonov#define TAILQ_HEAD(name, type) \ 62175ce1599SDmitri Tikhonovstruct name { \ 62275ce1599SDmitri Tikhonov struct type *tqh_first; /* first element */ \ 62375ce1599SDmitri Tikhonov struct type **tqh_last; /* addr of last next element */ \ 62475ce1599SDmitri Tikhonov TRACEBUF \ 62575ce1599SDmitri Tikhonov} 62675ce1599SDmitri Tikhonov 62775ce1599SDmitri Tikhonov#define TAILQ_CLASS_HEAD(name, type) \ 62875ce1599SDmitri Tikhonovstruct name { \ 62975ce1599SDmitri Tikhonov class type *tqh_first; /* first element */ \ 63075ce1599SDmitri Tikhonov class type **tqh_last; /* addr of last next element */ \ 63175ce1599SDmitri Tikhonov TRACEBUF \ 63275ce1599SDmitri Tikhonov} 63375ce1599SDmitri Tikhonov 63475ce1599SDmitri Tikhonov#define TAILQ_HEAD_INITIALIZER(head) \ 63575ce1599SDmitri Tikhonov { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } 63675ce1599SDmitri Tikhonov 63775ce1599SDmitri Tikhonov#define TAILQ_ENTRY(type) \ 63875ce1599SDmitri Tikhonovstruct { \ 63975ce1599SDmitri Tikhonov struct type *tqe_next; /* next element */ \ 64075ce1599SDmitri Tikhonov struct type **tqe_prev; /* address of previous next element */ \ 64175ce1599SDmitri Tikhonov TRACEBUF \ 64275ce1599SDmitri Tikhonov} 64375ce1599SDmitri Tikhonov 64475ce1599SDmitri Tikhonov#define TAILQ_CLASS_ENTRY(type) \ 64575ce1599SDmitri Tikhonovstruct { \ 64675ce1599SDmitri Tikhonov class type *tqe_next; /* next element */ \ 64775ce1599SDmitri Tikhonov class type **tqe_prev; /* address of previous next element */ \ 64875ce1599SDmitri Tikhonov TRACEBUF \ 64975ce1599SDmitri Tikhonov} 65075ce1599SDmitri Tikhonov 65175ce1599SDmitri Tikhonov/* 65275ce1599SDmitri Tikhonov * Tail queue functions. 65375ce1599SDmitri Tikhonov */ 65475ce1599SDmitri Tikhonov#if (defined(_KERNEL) && defined(INVARIANTS)) 65575ce1599SDmitri Tikhonov/* 65675ce1599SDmitri Tikhonov * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 65775ce1599SDmitri Tikhonov * 65875ce1599SDmitri Tikhonov * If the tailq is non-empty, validates that the first element of the tailq 65975ce1599SDmitri Tikhonov * points back at 'head.' 66075ce1599SDmitri Tikhonov */ 66175ce1599SDmitri Tikhonov#define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 66275ce1599SDmitri Tikhonov if (!TAILQ_EMPTY(head) && \ 66375ce1599SDmitri Tikhonov TAILQ_FIRST((head))->field.tqe_prev != \ 66475ce1599SDmitri Tikhonov &TAILQ_FIRST((head))) \ 66575ce1599SDmitri Tikhonov panic("Bad tailq head %p first->prev != head", (head)); \ 66675ce1599SDmitri Tikhonov} while (0) 66775ce1599SDmitri Tikhonov 66875ce1599SDmitri Tikhonov/* 66975ce1599SDmitri Tikhonov * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 67075ce1599SDmitri Tikhonov * 67175ce1599SDmitri Tikhonov * Validates that the tail of the tailq is a pointer to pointer to NULL. 67275ce1599SDmitri Tikhonov */ 67375ce1599SDmitri Tikhonov#define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 67475ce1599SDmitri Tikhonov if (*(head)->tqh_last != NULL) \ 67575ce1599SDmitri Tikhonov panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 67675ce1599SDmitri Tikhonov} while (0) 67775ce1599SDmitri Tikhonov 67875ce1599SDmitri Tikhonov/* 67975ce1599SDmitri Tikhonov * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME) 68075ce1599SDmitri Tikhonov * 68175ce1599SDmitri Tikhonov * If an element follows 'elm' in the tailq, validates that the next element 68275ce1599SDmitri Tikhonov * points back at 'elm.' 68375ce1599SDmitri Tikhonov */ 68475ce1599SDmitri Tikhonov#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 68575ce1599SDmitri Tikhonov if (TAILQ_NEXT((elm), field) != NULL && \ 68675ce1599SDmitri Tikhonov TAILQ_NEXT((elm), field)->field.tqe_prev != \ 68775ce1599SDmitri Tikhonov &((elm)->field.tqe_next)) \ 68875ce1599SDmitri Tikhonov panic("Bad link elm %p next->prev != elm", (elm)); \ 68975ce1599SDmitri Tikhonov} while (0) 69075ce1599SDmitri Tikhonov 69175ce1599SDmitri Tikhonov/* 69275ce1599SDmitri Tikhonov * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME) 69375ce1599SDmitri Tikhonov * 69475ce1599SDmitri Tikhonov * Validates that the previous element (or head of the tailq) points to 'elm.' 69575ce1599SDmitri Tikhonov */ 69675ce1599SDmitri Tikhonov#define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 69775ce1599SDmitri Tikhonov if (*(elm)->field.tqe_prev != (elm)) \ 69875ce1599SDmitri Tikhonov panic("Bad link elm %p prev->next != elm", (elm)); \ 69975ce1599SDmitri Tikhonov} while (0) 70075ce1599SDmitri Tikhonov#else 70175ce1599SDmitri Tikhonov#define QMD_TAILQ_CHECK_HEAD(head, field) 70275ce1599SDmitri Tikhonov#define QMD_TAILQ_CHECK_TAIL(head, headname) 70375ce1599SDmitri Tikhonov#define QMD_TAILQ_CHECK_NEXT(elm, field) 70475ce1599SDmitri Tikhonov#define QMD_TAILQ_CHECK_PREV(elm, field) 70575ce1599SDmitri Tikhonov#endif /* (_KERNEL && INVARIANTS) */ 70675ce1599SDmitri Tikhonov 70775ce1599SDmitri Tikhonov#define TAILQ_CONCAT(head1, head2, field) do { \ 70875ce1599SDmitri Tikhonov if (!TAILQ_EMPTY(head2)) { \ 70975ce1599SDmitri Tikhonov *(head1)->tqh_last = (head2)->tqh_first; \ 71075ce1599SDmitri Tikhonov (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 71175ce1599SDmitri Tikhonov (head1)->tqh_last = (head2)->tqh_last; \ 71275ce1599SDmitri Tikhonov TAILQ_INIT((head2)); \ 71375ce1599SDmitri Tikhonov QMD_TRACE_HEAD(head1); \ 71475ce1599SDmitri Tikhonov QMD_TRACE_HEAD(head2); \ 71575ce1599SDmitri Tikhonov } \ 71675ce1599SDmitri Tikhonov} while (0) 71775ce1599SDmitri Tikhonov 71875ce1599SDmitri Tikhonov#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 71975ce1599SDmitri Tikhonov 72075ce1599SDmitri Tikhonov#define TAILQ_FIRST(head) ((head)->tqh_first) 72175ce1599SDmitri Tikhonov 72275ce1599SDmitri Tikhonov#define TAILQ_FOREACH(var, head, field) \ 72375ce1599SDmitri Tikhonov for ((var) = TAILQ_FIRST((head)); \ 72475ce1599SDmitri Tikhonov (var); \ 72575ce1599SDmitri Tikhonov (var) = TAILQ_NEXT((var), field)) 72675ce1599SDmitri Tikhonov 72775ce1599SDmitri Tikhonov#define TAILQ_FOREACH_FROM(var, head, field) \ 72875ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 72975ce1599SDmitri Tikhonov (var); \ 73075ce1599SDmitri Tikhonov (var) = TAILQ_NEXT((var), field)) 73175ce1599SDmitri Tikhonov 73275ce1599SDmitri Tikhonov#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 73375ce1599SDmitri Tikhonov for ((var) = TAILQ_FIRST((head)); \ 73475ce1599SDmitri Tikhonov (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 73575ce1599SDmitri Tikhonov (var) = (tvar)) 73675ce1599SDmitri Tikhonov 73775ce1599SDmitri Tikhonov#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 73875ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 73975ce1599SDmitri Tikhonov (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 74075ce1599SDmitri Tikhonov (var) = (tvar)) 74175ce1599SDmitri Tikhonov 74275ce1599SDmitri Tikhonov#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 74375ce1599SDmitri Tikhonov for ((var) = TAILQ_LAST((head), headname); \ 74475ce1599SDmitri Tikhonov (var); \ 74575ce1599SDmitri Tikhonov (var) = TAILQ_PREV((var), headname, field)) 74675ce1599SDmitri Tikhonov 74775ce1599SDmitri Tikhonov#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 74875ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 74975ce1599SDmitri Tikhonov (var); \ 75075ce1599SDmitri Tikhonov (var) = TAILQ_PREV((var), headname, field)) 75175ce1599SDmitri Tikhonov 75275ce1599SDmitri Tikhonov#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 75375ce1599SDmitri Tikhonov for ((var) = TAILQ_LAST((head), headname); \ 75475ce1599SDmitri Tikhonov (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 75575ce1599SDmitri Tikhonov (var) = (tvar)) 75675ce1599SDmitri Tikhonov 75775ce1599SDmitri Tikhonov#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \ 75875ce1599SDmitri Tikhonov for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 75975ce1599SDmitri Tikhonov (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 76075ce1599SDmitri Tikhonov (var) = (tvar)) 76175ce1599SDmitri Tikhonov 76275ce1599SDmitri Tikhonov#define TAILQ_INIT(head) do { \ 76375ce1599SDmitri Tikhonov TAILQ_FIRST((head)) = NULL; \ 76475ce1599SDmitri Tikhonov (head)->tqh_last = &TAILQ_FIRST((head)); \ 76575ce1599SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 76675ce1599SDmitri Tikhonov} while (0) 76775ce1599SDmitri Tikhonov 76875ce1599SDmitri Tikhonov#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 76975ce1599SDmitri Tikhonov QMD_TAILQ_CHECK_NEXT(listelm, field); \ 77075ce1599SDmitri Tikhonov if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 77175ce1599SDmitri Tikhonov TAILQ_NEXT((elm), field)->field.tqe_prev = \ 77275ce1599SDmitri Tikhonov &TAILQ_NEXT((elm), field); \ 77375ce1599SDmitri Tikhonov else { \ 77475ce1599SDmitri Tikhonov (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 77575ce1599SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 77675ce1599SDmitri Tikhonov } \ 77775ce1599SDmitri Tikhonov TAILQ_NEXT((listelm), field) = (elm); \ 77875ce1599SDmitri Tikhonov (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 77975ce1599SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 78075ce1599SDmitri Tikhonov QMD_TRACE_ELEM(&(listelm)->field); \ 78175ce1599SDmitri Tikhonov} while (0) 78275ce1599SDmitri Tikhonov 78375ce1599SDmitri Tikhonov#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 78475ce1599SDmitri Tikhonov QMD_TAILQ_CHECK_PREV(listelm, field); \ 78575ce1599SDmitri Tikhonov (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 78675ce1599SDmitri Tikhonov TAILQ_NEXT((elm), field) = (listelm); \ 78775ce1599SDmitri Tikhonov *(listelm)->field.tqe_prev = (elm); \ 78875ce1599SDmitri Tikhonov (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 78975ce1599SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 79075ce1599SDmitri Tikhonov QMD_TRACE_ELEM(&(listelm)->field); \ 79175ce1599SDmitri Tikhonov} while (0) 79275ce1599SDmitri Tikhonov 79375ce1599SDmitri Tikhonov#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 79475ce1599SDmitri Tikhonov QMD_TAILQ_CHECK_HEAD(head, field); \ 79575ce1599SDmitri Tikhonov if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 79675ce1599SDmitri Tikhonov TAILQ_FIRST((head))->field.tqe_prev = \ 79775ce1599SDmitri Tikhonov &TAILQ_NEXT((elm), field); \ 79875ce1599SDmitri Tikhonov else \ 79975ce1599SDmitri Tikhonov (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 80075ce1599SDmitri Tikhonov TAILQ_FIRST((head)) = (elm); \ 80175ce1599SDmitri Tikhonov (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 80275ce1599SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 80375ce1599SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 80475ce1599SDmitri Tikhonov} while (0) 80575ce1599SDmitri Tikhonov 80675ce1599SDmitri Tikhonov#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 80775ce1599SDmitri Tikhonov QMD_TAILQ_CHECK_TAIL(head, field); \ 80875ce1599SDmitri Tikhonov TAILQ_NEXT((elm), field) = NULL; \ 80975ce1599SDmitri Tikhonov (elm)->field.tqe_prev = (head)->tqh_last; \ 81075ce1599SDmitri Tikhonov *(head)->tqh_last = (elm); \ 81175ce1599SDmitri Tikhonov (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 81275ce1599SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 81375ce1599SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 81475ce1599SDmitri Tikhonov} while (0) 81575ce1599SDmitri Tikhonov 81675ce1599SDmitri Tikhonov#define TAILQ_LAST(head, headname) \ 81775ce1599SDmitri Tikhonov (*(((struct headname *)((head)->tqh_last))->tqh_last)) 81875ce1599SDmitri Tikhonov 81975ce1599SDmitri Tikhonov#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 82075ce1599SDmitri Tikhonov 82175ce1599SDmitri Tikhonov#define TAILQ_PREV(elm, headname, field) \ 82275ce1599SDmitri Tikhonov (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 82375ce1599SDmitri Tikhonov 82475ce1599SDmitri Tikhonov#define TAILQ_REMOVE(head, elm, field) do { \ 82575ce1599SDmitri Tikhonov QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ 82675ce1599SDmitri Tikhonov QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ 82775ce1599SDmitri Tikhonov QMD_TAILQ_CHECK_NEXT(elm, field); \ 82875ce1599SDmitri Tikhonov QMD_TAILQ_CHECK_PREV(elm, field); \ 82975ce1599SDmitri Tikhonov if ((TAILQ_NEXT((elm), field)) != NULL) \ 83075ce1599SDmitri Tikhonov TAILQ_NEXT((elm), field)->field.tqe_prev = \ 83175ce1599SDmitri Tikhonov (elm)->field.tqe_prev; \ 83275ce1599SDmitri Tikhonov else { \ 83375ce1599SDmitri Tikhonov (head)->tqh_last = (elm)->field.tqe_prev; \ 83475ce1599SDmitri Tikhonov QMD_TRACE_HEAD(head); \ 83575ce1599SDmitri Tikhonov } \ 83675ce1599SDmitri Tikhonov *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 83775ce1599SDmitri Tikhonov TRASHIT(*oldnext); \ 83875ce1599SDmitri Tikhonov TRASHIT(*oldprev); \ 83975ce1599SDmitri Tikhonov QMD_TRACE_ELEM(&(elm)->field); \ 84075ce1599SDmitri Tikhonov} while (0) 84175ce1599SDmitri Tikhonov 84275ce1599SDmitri Tikhonov#define TAILQ_SWAP(head1, head2, type, field) do { \ 84375ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ 84475ce1599SDmitri Tikhonov QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 84575ce1599SDmitri Tikhonov (head1)->tqh_first = (head2)->tqh_first; \ 84675ce1599SDmitri Tikhonov (head1)->tqh_last = (head2)->tqh_last; \ 84775ce1599SDmitri Tikhonov (head2)->tqh_first = swap_first; \ 84875ce1599SDmitri Tikhonov (head2)->tqh_last = swap_last; \ 84975ce1599SDmitri Tikhonov if ((swap_first = (head1)->tqh_first) != NULL) \ 85075ce1599SDmitri Tikhonov swap_first->field.tqe_prev = &(head1)->tqh_first; \ 85175ce1599SDmitri Tikhonov else \ 85275ce1599SDmitri Tikhonov (head1)->tqh_last = &(head1)->tqh_first; \ 85375ce1599SDmitri Tikhonov if ((swap_first = (head2)->tqh_first) != NULL) \ 85475ce1599SDmitri Tikhonov swap_first->field.tqe_prev = &(head2)->tqh_first; \ 85575ce1599SDmitri Tikhonov else \ 85675ce1599SDmitri Tikhonov (head2)->tqh_last = &(head2)->tqh_first; \ 85775ce1599SDmitri Tikhonov} while (0) 85875ce1599SDmitri Tikhonov 85975ce1599SDmitri Tikhonov#endif /* !_SYS_QUEUE_H_ */ 860