160727d8bSWarner Losh /*- 251369649SPedro F. Giffuni * SPDX-License-Identifier: BSD-3-Clause 351369649SPedro F. Giffuni * 4df8bae1dSRodney W. Grimes * Copyright (c) 1991, 1993 5df8bae1dSRodney W. Grimes * The Regents of the University of California. All rights reserved. 6df8bae1dSRodney W. Grimes * 7df8bae1dSRodney W. Grimes * Redistribution and use in source and binary forms, with or without 8df8bae1dSRodney W. Grimes * modification, are permitted provided that the following conditions 9df8bae1dSRodney W. Grimes * are met: 10df8bae1dSRodney W. Grimes * 1. Redistributions of source code must retain the above copyright 11df8bae1dSRodney W. Grimes * notice, this list of conditions and the following disclaimer. 12df8bae1dSRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright 13df8bae1dSRodney W. Grimes * notice, this list of conditions and the following disclaimer in the 14df8bae1dSRodney W. Grimes * documentation and/or other materials provided with the distribution. 15fbbd9655SWarner Losh * 3. Neither the name of the University nor the names of its contributors 16df8bae1dSRodney W. Grimes * may be used to endorse or promote products derived from this software 17df8bae1dSRodney W. Grimes * without specific prior written permission. 18df8bae1dSRodney W. Grimes * 19df8bae1dSRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20df8bae1dSRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21df8bae1dSRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22df8bae1dSRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23df8bae1dSRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24df8bae1dSRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25df8bae1dSRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26df8bae1dSRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27df8bae1dSRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28df8bae1dSRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29df8bae1dSRodney W. Grimes * SUCH DAMAGE. 30df8bae1dSRodney W. Grimes */ 31df8bae1dSRodney W. Grimes 32df8bae1dSRodney W. Grimes #ifndef _SYS_QUEUE_H_ 33df8bae1dSRodney W. Grimes #define _SYS_QUEUE_H_ 34df8bae1dSRodney W. Grimes 35ba5fe510SMike Barcroft #include <sys/cdefs.h> 3646aa3347SPoul-Henning Kamp 37df8bae1dSRodney W. Grimes /* 389144eed4SSheldon Hearn * This file defines four types of data structures: singly-linked lists, 399144eed4SSheldon Hearn * singly-linked tail queues, lists and tail queues. 40088b8b1dSJustin T. Gibbs * 41088b8b1dSJustin T. Gibbs * A singly-linked list is headed by a single forward pointer. The elements 42088b8b1dSJustin T. Gibbs * are singly linked for minimum space and pointer manipulation overhead at 43088b8b1dSJustin T. Gibbs * the expense of O(n) removal for arbitrary elements. New elements can be 44088b8b1dSJustin T. Gibbs * added to the list after an existing element or at the head of the list. 45088b8b1dSJustin T. Gibbs * Elements being removed from the head of the list should use the explicit 46088b8b1dSJustin T. Gibbs * macro for this purpose for optimum efficiency. A singly-linked list may 47088b8b1dSJustin T. Gibbs * only be traversed in the forward direction. Singly-linked lists are ideal 48088b8b1dSJustin T. Gibbs * for applications with large datasets and few or no removals or for 49088b8b1dSJustin T. Gibbs * implementing a LIFO queue. 50088b8b1dSJustin T. Gibbs * 51088b8b1dSJustin T. Gibbs * A singly-linked tail queue is headed by a pair of pointers, one to the 52088b8b1dSJustin T. Gibbs * head of the list and the other to the tail of the list. The elements are 53088b8b1dSJustin T. Gibbs * singly linked for minimum space and pointer manipulation overhead at the 54088b8b1dSJustin T. Gibbs * expense of O(n) removal for arbitrary elements. New elements can be added 55088b8b1dSJustin T. Gibbs * to the list after an existing element, at the head of the list, or at the 56088b8b1dSJustin T. Gibbs * end of the list. Elements being removed from the head of the tail queue 57088b8b1dSJustin T. Gibbs * should use the explicit macro for this purpose for optimum efficiency. 58088b8b1dSJustin T. Gibbs * A singly-linked tail queue may only be traversed in the forward direction. 59088b8b1dSJustin T. Gibbs * Singly-linked tail queues are ideal for applications with large datasets 60088b8b1dSJustin T. Gibbs * and few or no removals or for implementing a FIFO queue. 61df8bae1dSRodney W. Grimes * 62df8bae1dSRodney W. Grimes * A list is headed by a single forward pointer (or an array of forward 63df8bae1dSRodney W. Grimes * pointers for a hash table header). The elements are doubly linked 64df8bae1dSRodney W. Grimes * so that an arbitrary element can be removed without a need to 6583edfd3eSJeffrey Hsu * traverse the list. New elements can be added to the list before 6683edfd3eSJeffrey Hsu * or after an existing element or at the head of the list. A list 674170b083SEd Schouten * may be traversed in either direction. 68df8bae1dSRodney W. Grimes * 69df8bae1dSRodney W. Grimes * A tail queue is headed by a pair of pointers, one to the head of the 70df8bae1dSRodney W. Grimes * list and the other to the tail of the list. The elements are doubly 71df8bae1dSRodney W. Grimes * linked so that an arbitrary element can be removed without a need to 7283edfd3eSJeffrey Hsu * traverse the list. New elements can be added to the list before or 7383edfd3eSJeffrey Hsu * after an existing element, at the head of the list, or at the end of 742be85d6dSArchie Cobbs * the list. A tail queue may be traversed in either direction. 75df8bae1dSRodney W. Grimes * 76df8bae1dSRodney W. Grimes * For details on the use of these macros, see the queue(3) manual page. 777594bf01SPoul-Henning Kamp * 7865d31997SKirk McKusick * Below is a summary of implemented functions where: 7965d31997SKirk McKusick * + means the macro is available 8065d31997SKirk McKusick * - means the macro is not available 8165d31997SKirk McKusick * s means the macro is available but is slow (runs in O(n) time) 827594bf01SPoul-Henning Kamp * 8324b85d18SPoul-Henning Kamp * SLIST LIST STAILQ TAILQ 8424b85d18SPoul-Henning Kamp * _HEAD + + + + 8538b622e1SHans Petter Selasky * _CLASS_HEAD + + + + 8624b85d18SPoul-Henning Kamp * _HEAD_INITIALIZER + + + + 8724b85d18SPoul-Henning Kamp * _ENTRY + + + + 8838b622e1SHans Petter Selasky * _CLASS_ENTRY + + + + 8924b85d18SPoul-Henning Kamp * _INIT + + + + 9024b85d18SPoul-Henning Kamp * _EMPTY + + + + 918d55837dSAlex Richardson * _END + + + + 9224b85d18SPoul-Henning Kamp * _FIRST + + + + 9324b85d18SPoul-Henning Kamp * _NEXT + + + + 944170b083SEd Schouten * _PREV - + - + 9524b85d18SPoul-Henning Kamp * _LAST - - + + 9689e560f4SRandall Stewart * _LAST_FAST - - - + 9724b85d18SPoul-Henning Kamp * _FOREACH + + + + 987ecb4019SLawrence Stewart * _FOREACH_FROM + + + + 992724bce2SAlexander Kabaev * _FOREACH_SAFE + + + + 1007ecb4019SLawrence Stewart * _FOREACH_FROM_SAFE + + + + 10124b85d18SPoul-Henning Kamp * _FOREACH_REVERSE - - - + 1027ecb4019SLawrence Stewart * _FOREACH_REVERSE_FROM - - - + 1032724bce2SAlexander Kabaev * _FOREACH_REVERSE_SAFE - - - + 1047ecb4019SLawrence Stewart * _FOREACH_REVERSE_FROM_SAFE - - - + 10524b85d18SPoul-Henning Kamp * _INSERT_HEAD + + + + 10624b85d18SPoul-Henning Kamp * _INSERT_BEFORE - + - + 10724b85d18SPoul-Henning Kamp * _INSERT_AFTER + + + + 10824b85d18SPoul-Henning Kamp * _INSERT_TAIL - - + + 10965d31997SKirk McKusick * _CONCAT s s + + 1103d98b75bSEd Schouten * _REMOVE_AFTER + - + - 11179fafc09SColin Percival * _REMOVE_HEAD + + + + 11265d31997SKirk McKusick * _REMOVE s + s + 1137f479deeSDag-Erling Smørgrav * _REPLACE - + - + 114359295cdSMatthew D Fleming * _SWAP + + + + 1157594bf01SPoul-Henning Kamp * 116df8bae1dSRodney W. Grimes */ 117054ff3beSEd Maste #ifdef QUEUE_MACRO_DEBUG 11806b93667SConrad Meyer #warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH 11906b93667SConrad Meyer #define QUEUE_MACRO_DEBUG_TRACE 12006b93667SConrad Meyer #define QUEUE_MACRO_DEBUG_TRASH 12106b93667SConrad Meyer #endif 12206b93667SConrad Meyer 12306b93667SConrad Meyer #ifdef QUEUE_MACRO_DEBUG_TRACE 1243b3afe10SJulian Elischer /* Store the last 2 places the queue element or head was altered */ 125e602ba25SJulian Elischer struct qm_trace { 1265fb0e927SGleb Smirnoff unsigned long lastline; 1275fb0e927SGleb Smirnoff unsigned long prevline; 1285fb0e927SGleb Smirnoff const char *lastfile; 1295fb0e927SGleb Smirnoff const char *prevfile; 130e602ba25SJulian Elischer }; 131e602ba25SJulian Elischer 132e602ba25SJulian Elischer #define TRACEBUF struct qm_trace trace; 1339090a24aSHans Petter Selasky #define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } , 134e602ba25SJulian Elischer 135e602ba25SJulian Elischer #define QMD_TRACE_HEAD(head) do { \ 136e602ba25SJulian Elischer (head)->trace.prevline = (head)->trace.lastline; \ 137e602ba25SJulian Elischer (head)->trace.prevfile = (head)->trace.lastfile; \ 138e602ba25SJulian Elischer (head)->trace.lastline = __LINE__; \ 139e602ba25SJulian Elischer (head)->trace.lastfile = __FILE__; \ 140e602ba25SJulian Elischer } while (0) 141e602ba25SJulian Elischer 142e602ba25SJulian Elischer #define QMD_TRACE_ELEM(elem) do { \ 143e602ba25SJulian Elischer (elem)->trace.prevline = (elem)->trace.lastline; \ 144e602ba25SJulian Elischer (elem)->trace.prevfile = (elem)->trace.lastfile; \ 145e602ba25SJulian Elischer (elem)->trace.lastline = __LINE__; \ 146e602ba25SJulian Elischer (elem)->trace.lastfile = __FILE__; \ 147e602ba25SJulian Elischer } while (0) 148e602ba25SJulian Elischer 14906b93667SConrad Meyer #else /* !QUEUE_MACRO_DEBUG_TRACE */ 150e602ba25SJulian Elischer #define QMD_TRACE_ELEM(elem) 151e602ba25SJulian Elischer #define QMD_TRACE_HEAD(head) 152e602ba25SJulian Elischer #define TRACEBUF 1535fb0e927SGleb Smirnoff #define TRACEBUF_INITIALIZER 15406b93667SConrad Meyer #endif /* QUEUE_MACRO_DEBUG_TRACE */ 15506b93667SConrad Meyer 15606b93667SConrad Meyer #ifdef QUEUE_MACRO_DEBUG_TRASH 157ee7e6f67SGleb Smirnoff #define QMD_SAVELINK(name, link) void **name = (void *)&(link) 15806b93667SConrad Meyer #define TRASHIT(x) do {(x) = (void *)-1;} while (0) 15906b93667SConrad Meyer #define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1) 16006b93667SConrad Meyer #else /* !QUEUE_MACRO_DEBUG_TRASH */ 161ee7e6f67SGleb Smirnoff #define QMD_SAVELINK(name, link) 162443fd6daSJulian Elischer #define TRASHIT(x) 16306b93667SConrad Meyer #define QMD_IS_TRASHED(x) 0 16406b93667SConrad Meyer #endif /* QUEUE_MACRO_DEBUG_TRASH */ 16506b93667SConrad Meyer 16638b622e1SHans Petter Selasky #ifdef __cplusplus 16738b622e1SHans Petter Selasky /* 16838b622e1SHans Petter Selasky * In C++ there can be structure lists and class lists: 16938b622e1SHans Petter Selasky */ 17038b622e1SHans Petter Selasky #define QUEUE_TYPEOF(type) type 17138b622e1SHans Petter Selasky #else 17238b622e1SHans Petter Selasky #define QUEUE_TYPEOF(type) struct type 17338b622e1SHans Petter Selasky #endif 17438b622e1SHans Petter Selasky 175df8bae1dSRodney W. Grimes /* 17657ebe415SJake Burkholder * Singly-linked List declarations. 177088b8b1dSJustin T. Gibbs */ 178088b8b1dSJustin T. Gibbs #define SLIST_HEAD(name, type) \ 179088b8b1dSJustin T. Gibbs struct name { \ 180e3975643SJake Burkholder struct type *slh_first; /* first element */ \ 181088b8b1dSJustin T. Gibbs } 182921e109fSNick Hibma 18338b622e1SHans Petter Selasky #define SLIST_CLASS_HEAD(name, type) \ 18438b622e1SHans Petter Selasky struct name { \ 18538b622e1SHans Petter Selasky class type *slh_first; /* first element */ \ 18638b622e1SHans Petter Selasky } 18738b622e1SHans Petter Selasky 188921e109fSNick Hibma #define SLIST_HEAD_INITIALIZER(head) \ 189921e109fSNick Hibma { NULL } 190088b8b1dSJustin T. Gibbs 191088b8b1dSJustin T. Gibbs #define SLIST_ENTRY(type) \ 192088b8b1dSJustin T. Gibbs struct { \ 193e3975643SJake Burkholder struct type *sle_next; /* next element */ \ 194088b8b1dSJustin T. Gibbs } 195088b8b1dSJustin T. Gibbs 19638b622e1SHans Petter Selasky #define SLIST_CLASS_ENTRY(type) \ 19738b622e1SHans Petter Selasky struct { \ 19838b622e1SHans Petter Selasky class type *sle_next; /* next element */ \ 19938b622e1SHans Petter Selasky } 20038b622e1SHans Petter Selasky 201088b8b1dSJustin T. Gibbs /* 202088b8b1dSJustin T. Gibbs * Singly-linked List functions. 203088b8b1dSJustin T. Gibbs */ 20406b93667SConrad Meyer #if (defined(_KERNEL) && defined(INVARIANTS)) 20506b93667SConrad Meyer #define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do { \ 20606b93667SConrad Meyer if (*(prevp) != (elm)) \ 20706b93667SConrad Meyer panic("Bad prevptr *(%p) == %p != %p", \ 20806b93667SConrad Meyer (prevp), *(prevp), (elm)); \ 20906b93667SConrad Meyer } while (0) 21006b93667SConrad Meyer #else 21106b93667SConrad Meyer #define QMD_SLIST_CHECK_PREVPTR(prevp, elm) 21206b93667SConrad Meyer #endif 21306b93667SConrad Meyer 21465d31997SKirk McKusick #define SLIST_CONCAT(head1, head2, type, field) do { \ 21565d31997SKirk McKusick QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ 21665d31997SKirk McKusick if (curelm == NULL) { \ 21765d31997SKirk McKusick if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ 21865d31997SKirk McKusick SLIST_INIT(head2); \ 21965d31997SKirk McKusick } else if (SLIST_FIRST(head2) != NULL) { \ 22065d31997SKirk McKusick while (SLIST_NEXT(curelm, field) != NULL) \ 22165d31997SKirk McKusick curelm = SLIST_NEXT(curelm, field); \ 22265d31997SKirk McKusick SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ 22365d31997SKirk McKusick SLIST_INIT(head2); \ 22465d31997SKirk McKusick } \ 22565d31997SKirk McKusick } while (0) 22665d31997SKirk McKusick 227fbc578d4SPoul-Henning Kamp #define SLIST_EMPTY(head) ((head)->slh_first == NULL) 228fbc578d4SPoul-Henning Kamp 229fbc578d4SPoul-Henning Kamp #define SLIST_FIRST(head) ((head)->slh_first) 230fbc578d4SPoul-Henning Kamp 23149f219aeSPoul-Henning Kamp #define SLIST_FOREACH(var, head, field) \ 23257ebe415SJake Burkholder for ((var) = SLIST_FIRST((head)); \ 23357ebe415SJake Burkholder (var); \ 23457ebe415SJake Burkholder (var) = SLIST_NEXT((var), field)) 23549f219aeSPoul-Henning Kamp 2367ecb4019SLawrence Stewart #define SLIST_FOREACH_FROM(var, head, field) \ 2377ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 2387ecb4019SLawrence Stewart (var); \ 2397ecb4019SLawrence Stewart (var) = SLIST_NEXT((var), field)) 2407ecb4019SLawrence Stewart 2412724bce2SAlexander Kabaev #define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 2422724bce2SAlexander Kabaev for ((var) = SLIST_FIRST((head)); \ 2432724bce2SAlexander Kabaev (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 2442724bce2SAlexander Kabaev (var) = (tvar)) 2452724bce2SAlexander Kabaev 2467ecb4019SLawrence Stewart #define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 2477ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 2487ecb4019SLawrence Stewart (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 2497ecb4019SLawrence Stewart (var) = (tvar)) 2507ecb4019SLawrence Stewart 251a4be7ce2SAlfred Perlstein #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 252a4be7ce2SAlfred Perlstein for ((varp) = &SLIST_FIRST((head)); \ 253a4be7ce2SAlfred Perlstein ((var) = *(varp)) != NULL; \ 254a4be7ce2SAlfred Perlstein (varp) = &SLIST_NEXT((var), field)) 255a4be7ce2SAlfred Perlstein 25657ebe415SJake Burkholder #define SLIST_INIT(head) do { \ 25757ebe415SJake Burkholder SLIST_FIRST((head)) = NULL; \ 25857ebe415SJake Burkholder } while (0) 259088b8b1dSJustin T. Gibbs 26017e2cf15SJulian Elischer #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 26157ebe415SJake Burkholder SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 26257ebe415SJake Burkholder SLIST_NEXT((slistelm), field) = (elm); \ 26317e2cf15SJulian Elischer } while (0) 264088b8b1dSJustin T. Gibbs 26517e2cf15SJulian Elischer #define SLIST_INSERT_HEAD(head, elm, field) do { \ 26657ebe415SJake Burkholder SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 26757ebe415SJake Burkholder SLIST_FIRST((head)) = (elm); \ 26817e2cf15SJulian Elischer } while (0) 269088b8b1dSJustin T. Gibbs 270fbc578d4SPoul-Henning Kamp #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 271fbc578d4SPoul-Henning Kamp 27217e2cf15SJulian Elischer #define SLIST_REMOVE(head, elm, type, field) do { \ 27357ebe415SJake Burkholder if (SLIST_FIRST((head)) == (elm)) { \ 274088b8b1dSJustin T. Gibbs SLIST_REMOVE_HEAD((head), field); \ 275088b8b1dSJustin T. Gibbs } \ 276088b8b1dSJustin T. Gibbs else { \ 27738b622e1SHans Petter Selasky QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \ 27857ebe415SJake Burkholder while (SLIST_NEXT(curelm, field) != (elm)) \ 27957ebe415SJake Burkholder curelm = SLIST_NEXT(curelm, field); \ 2803d98b75bSEd Schouten SLIST_REMOVE_AFTER(curelm, field); \ 281088b8b1dSJustin T. Gibbs } \ 28217e2cf15SJulian Elischer } while (0) 283088b8b1dSJustin T. Gibbs 2843d98b75bSEd Schouten #define SLIST_REMOVE_AFTER(elm, field) do { \ 2855dab06a0SAndriy Gapon QMD_SAVELINK(oldnext, SLIST_NEXT(elm, field)->field.sle_next); \ 286e2fd72deSEd Schouten SLIST_NEXT(elm, field) = \ 287e2fd72deSEd Schouten SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 2885dab06a0SAndriy Gapon TRASHIT(*oldnext); \ 289e2fd72deSEd Schouten } while (0) 290e2fd72deSEd Schouten 29157ebe415SJake Burkholder #define SLIST_REMOVE_HEAD(head, field) do { \ 2925dab06a0SAndriy Gapon QMD_SAVELINK(oldnext, SLIST_FIRST(head)->field.sle_next); \ 29357ebe415SJake Burkholder SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 2945dab06a0SAndriy Gapon TRASHIT(*oldnext); \ 29557ebe415SJake Burkholder } while (0) 29657ebe415SJake Burkholder 29706b93667SConrad Meyer #define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \ 29806b93667SConrad Meyer QMD_SLIST_CHECK_PREVPTR(prevp, elm); \ 29906b93667SConrad Meyer *(prevp) = SLIST_NEXT(elm, field); \ 30006b93667SConrad Meyer TRASHIT((elm)->field.sle_next); \ 30106b93667SConrad Meyer } while (0) 30206b93667SConrad Meyer 3034ac7bee8SKonstantin Belousov #define SLIST_SWAP(head1, head2, type) do { \ 30438b622e1SHans Petter Selasky QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ 3054ac7bee8SKonstantin Belousov SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 3064ac7bee8SKonstantin Belousov SLIST_FIRST(head2) = swap_first; \ 3074ac7bee8SKonstantin Belousov } while (0) 3084ac7bee8SKonstantin Belousov 3098d55837dSAlex Richardson #define SLIST_END(head) NULL 3108d55837dSAlex Richardson 311088b8b1dSJustin T. Gibbs /* 31257ebe415SJake Burkholder * Singly-linked Tail queue declarations. 313088b8b1dSJustin T. Gibbs */ 314088b8b1dSJustin T. Gibbs #define STAILQ_HEAD(name, type) \ 315088b8b1dSJustin T. Gibbs struct name { \ 316e3975643SJake Burkholder struct type *stqh_first;/* first element */ \ 317e3975643SJake Burkholder struct type **stqh_last;/* addr of last next element */ \ 318088b8b1dSJustin T. Gibbs } 319088b8b1dSJustin T. Gibbs 32038b622e1SHans Petter Selasky #define STAILQ_CLASS_HEAD(name, type) \ 32138b622e1SHans Petter Selasky struct name { \ 32238b622e1SHans Petter Selasky class type *stqh_first; /* first element */ \ 32338b622e1SHans Petter Selasky class type **stqh_last; /* addr of last next element */ \ 32438b622e1SHans Petter Selasky } 32538b622e1SHans Petter Selasky 326f6b387c2SNick Hibma #define STAILQ_HEAD_INITIALIZER(head) \ 327f6b387c2SNick Hibma { NULL, &(head).stqh_first } 328f6b387c2SNick Hibma 329088b8b1dSJustin T. Gibbs #define STAILQ_ENTRY(type) \ 330088b8b1dSJustin T. Gibbs struct { \ 331e3975643SJake Burkholder struct type *stqe_next; /* next element */ \ 332088b8b1dSJustin T. Gibbs } 333088b8b1dSJustin T. Gibbs 33438b622e1SHans Petter Selasky #define STAILQ_CLASS_ENTRY(type) \ 33538b622e1SHans Petter Selasky struct { \ 33638b622e1SHans Petter Selasky class type *stqe_next; /* next element */ \ 33738b622e1SHans Petter Selasky } 33838b622e1SHans Petter Selasky 339088b8b1dSJustin T. Gibbs /* 340088b8b1dSJustin T. Gibbs * Singly-linked Tail queue functions. 341088b8b1dSJustin T. Gibbs */ 342421a9d04SThomas Moestl #define STAILQ_CONCAT(head1, head2) do { \ 343421a9d04SThomas Moestl if (!STAILQ_EMPTY((head2))) { \ 344421a9d04SThomas Moestl *(head1)->stqh_last = (head2)->stqh_first; \ 345421a9d04SThomas Moestl (head1)->stqh_last = (head2)->stqh_last; \ 346421a9d04SThomas Moestl STAILQ_INIT((head2)); \ 347421a9d04SThomas Moestl } \ 348421a9d04SThomas Moestl } while (0) 349421a9d04SThomas Moestl 3507594bf01SPoul-Henning Kamp #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 3517594bf01SPoul-Henning Kamp 3525bd588ccSDoug Rabson #define STAILQ_FIRST(head) ((head)->stqh_first) 3535bd588ccSDoug Rabson 354a2c07ebfSJohn Polstra #define STAILQ_FOREACH(var, head, field) \ 35557ebe415SJake Burkholder for((var) = STAILQ_FIRST((head)); \ 35657ebe415SJake Burkholder (var); \ 35757ebe415SJake Burkholder (var) = STAILQ_NEXT((var), field)) 358a2c07ebfSJohn Polstra 3597ecb4019SLawrence Stewart #define STAILQ_FOREACH_FROM(var, head, field) \ 3607ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 3617ecb4019SLawrence Stewart (var); \ 3627ecb4019SLawrence Stewart (var) = STAILQ_NEXT((var), field)) 3632724bce2SAlexander Kabaev 3642724bce2SAlexander Kabaev #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 3652724bce2SAlexander Kabaev for ((var) = STAILQ_FIRST((head)); \ 3662724bce2SAlexander Kabaev (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 3672724bce2SAlexander Kabaev (var) = (tvar)) 3682724bce2SAlexander Kabaev 3697ecb4019SLawrence Stewart #define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 3707ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 3717ecb4019SLawrence Stewart (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 3727ecb4019SLawrence Stewart (var) = (tvar)) 3737ecb4019SLawrence Stewart 37457ebe415SJake Burkholder #define STAILQ_INIT(head) do { \ 37557ebe415SJake Burkholder STAILQ_FIRST((head)) = NULL; \ 37657ebe415SJake Burkholder (head)->stqh_last = &STAILQ_FIRST((head)); \ 37717e2cf15SJulian Elischer } while (0) 378088b8b1dSJustin T. Gibbs 37917e2cf15SJulian Elischer #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 38057ebe415SJake Burkholder if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 38157ebe415SJake Burkholder (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 38257ebe415SJake Burkholder STAILQ_NEXT((tqelm), field) = (elm); \ 38317e2cf15SJulian Elischer } while (0) 384088b8b1dSJustin T. Gibbs 38557ebe415SJake Burkholder #define STAILQ_INSERT_HEAD(head, elm, field) do { \ 38657ebe415SJake Burkholder if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 38757ebe415SJake Burkholder (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 38857ebe415SJake Burkholder STAILQ_FIRST((head)) = (elm); \ 38957ebe415SJake Burkholder } while (0) 39057ebe415SJake Burkholder 39157ebe415SJake Burkholder #define STAILQ_INSERT_TAIL(head, elm, field) do { \ 39257ebe415SJake Burkholder STAILQ_NEXT((elm), field) = NULL; \ 3935434d3f7SJeffrey Hsu *(head)->stqh_last = (elm); \ 39457ebe415SJake Burkholder (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 39557ebe415SJake Burkholder } while (0) 39657ebe415SJake Burkholder 3975434d3f7SJeffrey Hsu #define STAILQ_LAST(head, type, field) \ 3985b5d7684SEd Schouten (STAILQ_EMPTY((head)) ? NULL : \ 39938b622e1SHans Petter Selasky __containerof((head)->stqh_last, \ 40038b622e1SHans Petter Selasky QUEUE_TYPEOF(type), field.stqe_next)) 40157ebe415SJake Burkholder 4025bd588ccSDoug Rabson #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 4035bd588ccSDoug Rabson 40417e2cf15SJulian Elischer #define STAILQ_REMOVE(head, elm, type, field) do { \ 405ad542210SEd Maste QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ 40657ebe415SJake Burkholder if (STAILQ_FIRST((head)) == (elm)) { \ 40770abba50SThomas Moestl STAILQ_REMOVE_HEAD((head), field); \ 408088b8b1dSJustin T. Gibbs } \ 409088b8b1dSJustin T. Gibbs else { \ 41038b622e1SHans Petter Selasky QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ 41157ebe415SJake Burkholder while (STAILQ_NEXT(curelm, field) != (elm)) \ 41257ebe415SJake Burkholder curelm = STAILQ_NEXT(curelm, field); \ 4133d98b75bSEd Schouten STAILQ_REMOVE_AFTER(head, curelm, field); \ 414088b8b1dSJustin T. Gibbs } \ 415ad542210SEd Maste TRASHIT(*oldnext); \ 41617e2cf15SJulian Elischer } while (0) 417088b8b1dSJustin T. Gibbs 4183d98b75bSEd Schouten #define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 419e2fd72deSEd Schouten if ((STAILQ_NEXT(elm, field) = \ 420e2fd72deSEd Schouten STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 421e2fd72deSEd Schouten (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 422e2fd72deSEd Schouten } while (0) 423e2fd72deSEd Schouten 424359295cdSMatthew D Fleming #define STAILQ_REMOVE_HEAD(head, field) do { \ 425359295cdSMatthew D Fleming if ((STAILQ_FIRST((head)) = \ 426359295cdSMatthew D Fleming STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 427359295cdSMatthew D Fleming (head)->stqh_last = &STAILQ_FIRST((head)); \ 428359295cdSMatthew D Fleming } while (0) 429359295cdSMatthew D Fleming 430cfeb7489SZachary Loafman #define STAILQ_SWAP(head1, head2, type) do { \ 43138b622e1SHans Petter Selasky QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ 43238b622e1SHans Petter Selasky QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ 433cfeb7489SZachary Loafman STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 434cfeb7489SZachary Loafman (head1)->stqh_last = (head2)->stqh_last; \ 435cfeb7489SZachary Loafman STAILQ_FIRST(head2) = swap_first; \ 436cfeb7489SZachary Loafman (head2)->stqh_last = swap_last; \ 437cfeb7489SZachary Loafman if (STAILQ_EMPTY(head1)) \ 438cfeb7489SZachary Loafman (head1)->stqh_last = &STAILQ_FIRST(head1); \ 439cfeb7489SZachary Loafman if (STAILQ_EMPTY(head2)) \ 440cfeb7489SZachary Loafman (head2)->stqh_last = &STAILQ_FIRST(head2); \ 441cfeb7489SZachary Loafman } while (0) 442cfeb7489SZachary Loafman 4438d55837dSAlex Richardson #define STAILQ_END(head) NULL 4448d55837dSAlex Richardson 4458d55837dSAlex Richardson 446088b8b1dSJustin T. Gibbs /* 44757ebe415SJake Burkholder * List declarations. 448df8bae1dSRodney W. Grimes */ 449df8bae1dSRodney W. Grimes #define LIST_HEAD(name, type) \ 450df8bae1dSRodney W. Grimes struct name { \ 451e3975643SJake Burkholder struct type *lh_first; /* first element */ \ 452df8bae1dSRodney W. Grimes } 453df8bae1dSRodney W. Grimes 45438b622e1SHans Petter Selasky #define LIST_CLASS_HEAD(name, type) \ 45538b622e1SHans Petter Selasky struct name { \ 45638b622e1SHans Petter Selasky class type *lh_first; /* first element */ \ 45738b622e1SHans Petter Selasky } 45838b622e1SHans Petter Selasky 459f81f9185SNick Hibma #define LIST_HEAD_INITIALIZER(head) \ 460f6b387c2SNick Hibma { NULL } 461f6b387c2SNick Hibma 462df8bae1dSRodney W. Grimes #define LIST_ENTRY(type) \ 463df8bae1dSRodney W. Grimes struct { \ 464e3975643SJake Burkholder struct type *le_next; /* next element */ \ 465e3975643SJake Burkholder struct type **le_prev; /* address of previous next element */ \ 466df8bae1dSRodney W. Grimes } 467df8bae1dSRodney W. Grimes 46838b622e1SHans Petter Selasky #define LIST_CLASS_ENTRY(type) \ 46938b622e1SHans Petter Selasky struct { \ 47038b622e1SHans Petter Selasky class type *le_next; /* next element */ \ 47138b622e1SHans Petter Selasky class type **le_prev; /* address of previous next element */ \ 47238b622e1SHans Petter Selasky } 47338b622e1SHans Petter Selasky 474df8bae1dSRodney W. Grimes /* 475df8bae1dSRodney W. Grimes * List functions. 476df8bae1dSRodney W. Grimes */ 4777594bf01SPoul-Henning Kamp 4781b861e4aSEd Maste #if (defined(_KERNEL) && defined(INVARIANTS)) 479a0329fb4SConrad Meyer /* 480a0329fb4SConrad Meyer * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME) 481a0329fb4SConrad Meyer * 482a0329fb4SConrad Meyer * If the list is non-empty, validates that the first element of the list 483a0329fb4SConrad Meyer * points back at 'head.' 484a0329fb4SConrad Meyer */ 485054ff3beSEd Maste #define QMD_LIST_CHECK_HEAD(head, field) do { \ 486054ff3beSEd Maste if (LIST_FIRST((head)) != NULL && \ 487054ff3beSEd Maste LIST_FIRST((head))->field.le_prev != \ 488054ff3beSEd Maste &LIST_FIRST((head))) \ 489054ff3beSEd Maste panic("Bad list head %p first->prev != head", (head)); \ 490054ff3beSEd Maste } while (0) 491054ff3beSEd Maste 492a0329fb4SConrad Meyer /* 493a0329fb4SConrad Meyer * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME) 494a0329fb4SConrad Meyer * 495a0329fb4SConrad Meyer * If an element follows 'elm' in the list, validates that the next element 496a0329fb4SConrad Meyer * points back at 'elm.' 497a0329fb4SConrad Meyer */ 498054ff3beSEd Maste #define QMD_LIST_CHECK_NEXT(elm, field) do { \ 499054ff3beSEd Maste if (LIST_NEXT((elm), field) != NULL && \ 500054ff3beSEd Maste LIST_NEXT((elm), field)->field.le_prev != \ 501054ff3beSEd Maste &((elm)->field.le_next)) \ 502054ff3beSEd Maste panic("Bad link elm %p next->prev != elm", (elm)); \ 503054ff3beSEd Maste } while (0) 504054ff3beSEd Maste 505a0329fb4SConrad Meyer /* 506a0329fb4SConrad Meyer * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME) 507a0329fb4SConrad Meyer * 508a0329fb4SConrad Meyer * Validates that the previous element (or head of the list) points to 'elm.' 509a0329fb4SConrad Meyer */ 510054ff3beSEd Maste #define QMD_LIST_CHECK_PREV(elm, field) do { \ 511054ff3beSEd Maste if (*(elm)->field.le_prev != (elm)) \ 512054ff3beSEd Maste panic("Bad link elm %p prev->next != elm", (elm)); \ 513054ff3beSEd Maste } while (0) 514054ff3beSEd Maste #else 515054ff3beSEd Maste #define QMD_LIST_CHECK_HEAD(head, field) 516054ff3beSEd Maste #define QMD_LIST_CHECK_NEXT(elm, field) 517054ff3beSEd Maste #define QMD_LIST_CHECK_PREV(elm, field) 5181b861e4aSEd Maste #endif /* (_KERNEL && INVARIANTS) */ 519054ff3beSEd Maste 52065d31997SKirk McKusick #define LIST_CONCAT(head1, head2, type, field) do { \ 52165d31997SKirk McKusick QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ 52265d31997SKirk McKusick if (curelm == NULL) { \ 52365d31997SKirk McKusick if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ 52465d31997SKirk McKusick LIST_FIRST(head2)->field.le_prev = \ 52565d31997SKirk McKusick &LIST_FIRST((head1)); \ 52665d31997SKirk McKusick LIST_INIT(head2); \ 52765d31997SKirk McKusick } \ 52865d31997SKirk McKusick } else if (LIST_FIRST(head2) != NULL) { \ 52965d31997SKirk McKusick while (LIST_NEXT(curelm, field) != NULL) \ 53065d31997SKirk McKusick curelm = LIST_NEXT(curelm, field); \ 53165d31997SKirk McKusick LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ 53265d31997SKirk McKusick LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field);\ 53365d31997SKirk McKusick LIST_INIT(head2); \ 53465d31997SKirk McKusick } \ 53565d31997SKirk McKusick } while (0) 53665d31997SKirk McKusick 5377594bf01SPoul-Henning Kamp #define LIST_EMPTY(head) ((head)->lh_first == NULL) 5387594bf01SPoul-Henning Kamp 5390b5fe378SPoul-Henning Kamp #define LIST_FIRST(head) ((head)->lh_first) 5400b5fe378SPoul-Henning Kamp 5410b5fe378SPoul-Henning Kamp #define LIST_FOREACH(var, head, field) \ 54257ebe415SJake Burkholder for ((var) = LIST_FIRST((head)); \ 54357ebe415SJake Burkholder (var); \ 54457ebe415SJake Burkholder (var) = LIST_NEXT((var), field)) 5450b5fe378SPoul-Henning Kamp 5467ecb4019SLawrence Stewart #define LIST_FOREACH_FROM(var, head, field) \ 5477ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 5487ecb4019SLawrence Stewart (var); \ 5497ecb4019SLawrence Stewart (var) = LIST_NEXT((var), field)) 5507ecb4019SLawrence Stewart 5510373e754SBosko Milekic #define LIST_FOREACH_SAFE(var, head, field, tvar) \ 5522724bce2SAlexander Kabaev for ((var) = LIST_FIRST((head)); \ 5532724bce2SAlexander Kabaev (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 5542724bce2SAlexander Kabaev (var) = (tvar)) 5550373e754SBosko Milekic 5567ecb4019SLawrence Stewart #define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 5577ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 5587ecb4019SLawrence Stewart (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 5597ecb4019SLawrence Stewart (var) = (tvar)) 5607ecb4019SLawrence Stewart 56117e2cf15SJulian Elischer #define LIST_INIT(head) do { \ 56257ebe415SJake Burkholder LIST_FIRST((head)) = NULL; \ 56317e2cf15SJulian Elischer } while (0) 564df8bae1dSRodney W. Grimes 56517e2cf15SJulian Elischer #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 566054ff3beSEd Maste QMD_LIST_CHECK_NEXT(listelm, field); \ 56757ebe415SJake Burkholder if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 56857ebe415SJake Burkholder LIST_NEXT((listelm), field)->field.le_prev = \ 56957ebe415SJake Burkholder &LIST_NEXT((elm), field); \ 57057ebe415SJake Burkholder LIST_NEXT((listelm), field) = (elm); \ 57157ebe415SJake Burkholder (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 57217e2cf15SJulian Elischer } while (0) 573df8bae1dSRodney W. Grimes 57417e2cf15SJulian Elischer #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 575054ff3beSEd Maste QMD_LIST_CHECK_PREV(listelm, field); \ 5767db797deSJustin T. Gibbs (elm)->field.le_prev = (listelm)->field.le_prev; \ 57757ebe415SJake Burkholder LIST_NEXT((elm), field) = (listelm); \ 5787db797deSJustin T. Gibbs *(listelm)->field.le_prev = (elm); \ 57957ebe415SJake Burkholder (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 58017e2cf15SJulian Elischer } while (0) 5817db797deSJustin T. Gibbs 58217e2cf15SJulian Elischer #define LIST_INSERT_HEAD(head, elm, field) do { \ 583054ff3beSEd Maste QMD_LIST_CHECK_HEAD((head), field); \ 58457ebe415SJake Burkholder if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 58557ebe415SJake Burkholder LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 58657ebe415SJake Burkholder LIST_FIRST((head)) = (elm); \ 58757ebe415SJake Burkholder (elm)->field.le_prev = &LIST_FIRST((head)); \ 58817e2cf15SJulian Elischer } while (0) 589df8bae1dSRodney W. Grimes 5900b5fe378SPoul-Henning Kamp #define LIST_NEXT(elm, field) ((elm)->field.le_next) 5910b5fe378SPoul-Henning Kamp 5924170b083SEd Schouten #define LIST_PREV(elm, head, type, field) \ 5935b5d7684SEd Schouten ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 59438b622e1SHans Petter Selasky __containerof((elm)->field.le_prev, \ 59538b622e1SHans Petter Selasky QUEUE_TYPEOF(type), field.le_next)) 5964170b083SEd Schouten 59779fafc09SColin Percival #define LIST_REMOVE_HEAD(head, field) \ 59879fafc09SColin Percival LIST_REMOVE(LIST_FIRST(head), field) 59979fafc09SColin Percival 60017e2cf15SJulian Elischer #define LIST_REMOVE(elm, field) do { \ 601ad542210SEd Maste QMD_SAVELINK(oldnext, (elm)->field.le_next); \ 602ad542210SEd Maste QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ 603054ff3beSEd Maste QMD_LIST_CHECK_NEXT(elm, field); \ 604054ff3beSEd Maste QMD_LIST_CHECK_PREV(elm, field); \ 60557ebe415SJake Burkholder if (LIST_NEXT((elm), field) != NULL) \ 60657ebe415SJake Burkholder LIST_NEXT((elm), field)->field.le_prev = \ 607df8bae1dSRodney W. Grimes (elm)->field.le_prev; \ 60857ebe415SJake Burkholder *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 609ad542210SEd Maste TRASHIT(*oldnext); \ 610ad542210SEd Maste TRASHIT(*oldprev); \ 61117e2cf15SJulian Elischer } while (0) 612df8bae1dSRodney W. Grimes 6137f479deeSDag-Erling Smørgrav #define LIST_REPLACE(elm, elm2, field) do { \ 6147f479deeSDag-Erling Smørgrav QMD_SAVELINK(oldnext, (elm)->field.le_next); \ 6157f479deeSDag-Erling Smørgrav QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ 6167f479deeSDag-Erling Smørgrav QMD_LIST_CHECK_NEXT(elm, field); \ 6177f479deeSDag-Erling Smørgrav QMD_LIST_CHECK_PREV(elm, field); \ 6187f479deeSDag-Erling Smørgrav LIST_NEXT((elm2), field) = LIST_NEXT((elm), field); \ 6197f479deeSDag-Erling Smørgrav if (LIST_NEXT((elm2), field) != NULL) \ 6207f479deeSDag-Erling Smørgrav LIST_NEXT((elm2), field)->field.le_prev = \ 6217f479deeSDag-Erling Smørgrav &(elm2)->field.le_next; \ 6227f479deeSDag-Erling Smørgrav (elm2)->field.le_prev = (elm)->field.le_prev; \ 6237f479deeSDag-Erling Smørgrav *(elm2)->field.le_prev = (elm2); \ 6247f479deeSDag-Erling Smørgrav TRASHIT(*oldnext); \ 6257f479deeSDag-Erling Smørgrav TRASHIT(*oldprev); \ 6267f479deeSDag-Erling Smørgrav } while (0) 6277f479deeSDag-Erling Smørgrav 628cfeb7489SZachary Loafman #define LIST_SWAP(head1, head2, type, field) do { \ 62938b622e1SHans Petter Selasky QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 630cfeb7489SZachary Loafman LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 631cfeb7489SZachary Loafman LIST_FIRST((head2)) = swap_tmp; \ 632cfeb7489SZachary Loafman if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 633cfeb7489SZachary Loafman swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 634cfeb7489SZachary Loafman if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 635cfeb7489SZachary Loafman swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 636cfeb7489SZachary Loafman } while (0) 637cfeb7489SZachary Loafman 6388d55837dSAlex Richardson #define LIST_END(head) NULL 6398d55837dSAlex Richardson 640df8bae1dSRodney W. Grimes /* 64157ebe415SJake Burkholder * Tail queue declarations. 642df8bae1dSRodney W. Grimes */ 643df8bae1dSRodney W. Grimes #define TAILQ_HEAD(name, type) \ 644df8bae1dSRodney W. Grimes struct name { \ 645e3975643SJake Burkholder struct type *tqh_first; /* first element */ \ 646e3975643SJake Burkholder struct type **tqh_last; /* addr of last next element */ \ 647e602ba25SJulian Elischer TRACEBUF \ 648df8bae1dSRodney W. Grimes } 649df8bae1dSRodney W. Grimes 65038b622e1SHans Petter Selasky #define TAILQ_CLASS_HEAD(name, type) \ 65138b622e1SHans Petter Selasky struct name { \ 65238b622e1SHans Petter Selasky class type *tqh_first; /* first element */ \ 65338b622e1SHans Petter Selasky class type **tqh_last; /* addr of last next element */ \ 65438b622e1SHans Petter Selasky TRACEBUF \ 65538b622e1SHans Petter Selasky } 65638b622e1SHans Petter Selasky 6575957b261SJustin T. Gibbs #define TAILQ_HEAD_INITIALIZER(head) \ 6585fb0e927SGleb Smirnoff { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } 6595957b261SJustin T. Gibbs 660df8bae1dSRodney W. Grimes #define TAILQ_ENTRY(type) \ 661df8bae1dSRodney W. Grimes struct { \ 662e3975643SJake Burkholder struct type *tqe_next; /* next element */ \ 663e3975643SJake Burkholder struct type **tqe_prev; /* address of previous next element */ \ 664e602ba25SJulian Elischer TRACEBUF \ 665df8bae1dSRodney W. Grimes } 666df8bae1dSRodney W. Grimes 66738b622e1SHans Petter Selasky #define TAILQ_CLASS_ENTRY(type) \ 66838b622e1SHans Petter Selasky struct { \ 66938b622e1SHans Petter Selasky class type *tqe_next; /* next element */ \ 67038b622e1SHans Petter Selasky class type **tqe_prev; /* address of previous next element */ \ 67138b622e1SHans Petter Selasky TRACEBUF \ 67238b622e1SHans Petter Selasky } 67338b622e1SHans Petter Selasky 674df8bae1dSRodney W. Grimes /* 675df8bae1dSRodney W. Grimes * Tail queue functions. 676df8bae1dSRodney W. Grimes */ 677af8d1678SEd Maste #if (defined(_KERNEL) && defined(INVARIANTS)) 678a0329fb4SConrad Meyer /* 679a0329fb4SConrad Meyer * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 680a0329fb4SConrad Meyer * 681a0329fb4SConrad Meyer * If the tailq is non-empty, validates that the first element of the tailq 682a0329fb4SConrad Meyer * points back at 'head.' 683a0329fb4SConrad Meyer */ 684af8d1678SEd Maste #define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 685af8d1678SEd Maste if (!TAILQ_EMPTY(head) && \ 686af8d1678SEd Maste TAILQ_FIRST((head))->field.tqe_prev != \ 687af8d1678SEd Maste &TAILQ_FIRST((head))) \ 688af8d1678SEd Maste panic("Bad tailq head %p first->prev != head", (head)); \ 689af8d1678SEd Maste } while (0) 690af8d1678SEd Maste 691a0329fb4SConrad Meyer /* 692a0329fb4SConrad Meyer * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 693a0329fb4SConrad Meyer * 694a0329fb4SConrad Meyer * Validates that the tail of the tailq is a pointer to pointer to NULL. 695a0329fb4SConrad Meyer */ 696af8d1678SEd Maste #define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 697af8d1678SEd Maste if (*(head)->tqh_last != NULL) \ 698af8d1678SEd Maste panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 699af8d1678SEd Maste } while (0) 700af8d1678SEd Maste 701a0329fb4SConrad Meyer /* 702a0329fb4SConrad Meyer * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME) 703a0329fb4SConrad Meyer * 704a0329fb4SConrad Meyer * If an element follows 'elm' in the tailq, validates that the next element 705a0329fb4SConrad Meyer * points back at 'elm.' 706a0329fb4SConrad Meyer */ 707af8d1678SEd Maste #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 708af8d1678SEd Maste if (TAILQ_NEXT((elm), field) != NULL && \ 709af8d1678SEd Maste TAILQ_NEXT((elm), field)->field.tqe_prev != \ 710af8d1678SEd Maste &((elm)->field.tqe_next)) \ 711af8d1678SEd Maste panic("Bad link elm %p next->prev != elm", (elm)); \ 712af8d1678SEd Maste } while (0) 713af8d1678SEd Maste 714a0329fb4SConrad Meyer /* 715a0329fb4SConrad Meyer * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME) 716a0329fb4SConrad Meyer * 717a0329fb4SConrad Meyer * Validates that the previous element (or head of the tailq) points to 'elm.' 718a0329fb4SConrad Meyer */ 719af8d1678SEd Maste #define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 720af8d1678SEd Maste if (*(elm)->field.tqe_prev != (elm)) \ 721af8d1678SEd Maste panic("Bad link elm %p prev->next != elm", (elm)); \ 722af8d1678SEd Maste } while (0) 723af8d1678SEd Maste #else 724af8d1678SEd Maste #define QMD_TAILQ_CHECK_HEAD(head, field) 725af8d1678SEd Maste #define QMD_TAILQ_CHECK_TAIL(head, headname) 726af8d1678SEd Maste #define QMD_TAILQ_CHECK_NEXT(elm, field) 727af8d1678SEd Maste #define QMD_TAILQ_CHECK_PREV(elm, field) 728af8d1678SEd Maste #endif /* (_KERNEL && INVARIANTS) */ 729af8d1678SEd Maste 730421a9d04SThomas Moestl #define TAILQ_CONCAT(head1, head2, field) do { \ 731421a9d04SThomas Moestl if (!TAILQ_EMPTY(head2)) { \ 732421a9d04SThomas Moestl *(head1)->tqh_last = (head2)->tqh_first; \ 733421a9d04SThomas Moestl (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 734421a9d04SThomas Moestl (head1)->tqh_last = (head2)->tqh_last; \ 735421a9d04SThomas Moestl TAILQ_INIT((head2)); \ 736e622e227SPoul-Henning Kamp QMD_TRACE_HEAD(head1); \ 737e602ba25SJulian Elischer QMD_TRACE_HEAD(head2); \ 738421a9d04SThomas Moestl } \ 739421a9d04SThomas Moestl } while (0) 740421a9d04SThomas Moestl 741d19287f2SPoul-Henning Kamp #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 742d19287f2SPoul-Henning Kamp 74357ebe415SJake Burkholder #define TAILQ_FIRST(head) ((head)->tqh_first) 74457ebe415SJake Burkholder 7457594bf01SPoul-Henning Kamp #define TAILQ_FOREACH(var, head, field) \ 74657ebe415SJake Burkholder for ((var) = TAILQ_FIRST((head)); \ 74757ebe415SJake Burkholder (var); \ 74857ebe415SJake Burkholder (var) = TAILQ_NEXT((var), field)) 7497594bf01SPoul-Henning Kamp 7507ecb4019SLawrence Stewart #define TAILQ_FOREACH_FROM(var, head, field) \ 7517ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 7527ecb4019SLawrence Stewart (var); \ 7537ecb4019SLawrence Stewart (var) = TAILQ_NEXT((var), field)) 7547ecb4019SLawrence Stewart 7552724bce2SAlexander Kabaev #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 7562724bce2SAlexander Kabaev for ((var) = TAILQ_FIRST((head)); \ 7572724bce2SAlexander Kabaev (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 7582724bce2SAlexander Kabaev (var) = (tvar)) 7592724bce2SAlexander Kabaev 7607ecb4019SLawrence Stewart #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 7617ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 7627ecb4019SLawrence Stewart (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 7637ecb4019SLawrence Stewart (var) = (tvar)) 7647ecb4019SLawrence Stewart 7652be85d6dSArchie Cobbs #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 7662be85d6dSArchie Cobbs for ((var) = TAILQ_LAST((head), headname); \ 7672be85d6dSArchie Cobbs (var); \ 7682be85d6dSArchie Cobbs (var) = TAILQ_PREV((var), headname, field)) 7692be85d6dSArchie Cobbs 7707ecb4019SLawrence Stewart #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 7717ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 7727ecb4019SLawrence Stewart (var); \ 7737ecb4019SLawrence Stewart (var) = TAILQ_PREV((var), headname, field)) 7747ecb4019SLawrence Stewart 7752724bce2SAlexander Kabaev #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 7762724bce2SAlexander Kabaev for ((var) = TAILQ_LAST((head), headname); \ 7772724bce2SAlexander Kabaev (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 7782724bce2SAlexander Kabaev (var) = (tvar)) 7792724bce2SAlexander Kabaev 7807ecb4019SLawrence Stewart #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar)\ 7817ecb4019SLawrence Stewart for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 7827ecb4019SLawrence Stewart (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 7837ecb4019SLawrence Stewart (var) = (tvar)) 7847ecb4019SLawrence Stewart 78557ebe415SJake Burkholder #define TAILQ_INIT(head) do { \ 78657ebe415SJake Burkholder TAILQ_FIRST((head)) = NULL; \ 78757ebe415SJake Burkholder (head)->tqh_last = &TAILQ_FIRST((head)); \ 788e602ba25SJulian Elischer QMD_TRACE_HEAD(head); \ 78957ebe415SJake Burkholder } while (0) 79057ebe415SJake Burkholder 79157ebe415SJake Burkholder #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 792af8d1678SEd Maste QMD_TAILQ_CHECK_NEXT(listelm, field); \ 79357ebe415SJake Burkholder if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 79457ebe415SJake Burkholder TAILQ_NEXT((elm), field)->field.tqe_prev = \ 79557ebe415SJake Burkholder &TAILQ_NEXT((elm), field); \ 796e602ba25SJulian Elischer else { \ 79757ebe415SJake Burkholder (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 798e602ba25SJulian Elischer QMD_TRACE_HEAD(head); \ 799e602ba25SJulian Elischer } \ 80057ebe415SJake Burkholder TAILQ_NEXT((listelm), field) = (elm); \ 80157ebe415SJake Burkholder (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 802e602ba25SJulian Elischer QMD_TRACE_ELEM(&(elm)->field); \ 80373e12bc9SHans Petter Selasky QMD_TRACE_ELEM(&(listelm)->field); \ 80457ebe415SJake Burkholder } while (0) 80557ebe415SJake Burkholder 80657ebe415SJake Burkholder #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 807af8d1678SEd Maste QMD_TAILQ_CHECK_PREV(listelm, field); \ 80857ebe415SJake Burkholder (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 80957ebe415SJake Burkholder TAILQ_NEXT((elm), field) = (listelm); \ 81057ebe415SJake Burkholder *(listelm)->field.tqe_prev = (elm); \ 81157ebe415SJake Burkholder (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 812e602ba25SJulian Elischer QMD_TRACE_ELEM(&(elm)->field); \ 81373e12bc9SHans Petter Selasky QMD_TRACE_ELEM(&(listelm)->field); \ 81457ebe415SJake Burkholder } while (0) 81557ebe415SJake Burkholder 81657ebe415SJake Burkholder #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 817af8d1678SEd Maste QMD_TAILQ_CHECK_HEAD(head, field); \ 81857ebe415SJake Burkholder if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 81957ebe415SJake Burkholder TAILQ_FIRST((head))->field.tqe_prev = \ 82057ebe415SJake Burkholder &TAILQ_NEXT((elm), field); \ 82157ebe415SJake Burkholder else \ 82257ebe415SJake Burkholder (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 82357ebe415SJake Burkholder TAILQ_FIRST((head)) = (elm); \ 82457ebe415SJake Burkholder (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 825e602ba25SJulian Elischer QMD_TRACE_HEAD(head); \ 826e602ba25SJulian Elischer QMD_TRACE_ELEM(&(elm)->field); \ 82757ebe415SJake Burkholder } while (0) 82857ebe415SJake Burkholder 82957ebe415SJake Burkholder #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 830af8d1678SEd Maste QMD_TAILQ_CHECK_TAIL(head, field); \ 83157ebe415SJake Burkholder TAILQ_NEXT((elm), field) = NULL; \ 83257ebe415SJake Burkholder (elm)->field.tqe_prev = (head)->tqh_last; \ 83357ebe415SJake Burkholder *(head)->tqh_last = (elm); \ 83457ebe415SJake Burkholder (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 835e602ba25SJulian Elischer QMD_TRACE_HEAD(head); \ 836e602ba25SJulian Elischer QMD_TRACE_ELEM(&(elm)->field); \ 83757ebe415SJake Burkholder } while (0) 838d19287f2SPoul-Henning Kamp 83917e2cf15SJulian Elischer #define TAILQ_LAST(head, headname) \ 84017e2cf15SJulian Elischer (*(((struct headname *)((head)->tqh_last))->tqh_last)) 841d19287f2SPoul-Henning Kamp 84289e560f4SRandall Stewart /* 84389e560f4SRandall Stewart * The FAST function is fast in that it causes no data access other 84489e560f4SRandall Stewart * then the access to the head. The standard LAST function above 84589e560f4SRandall Stewart * will cause a data access of both the element you want and 84689e560f4SRandall Stewart * the previous element. FAST is very useful for instances when 84789e560f4SRandall Stewart * you may want to prefetch the last data element. 84889e560f4SRandall Stewart */ 84989e560f4SRandall Stewart #define TAILQ_LAST_FAST(head, type, field) \ 85089e560f4SRandall Stewart (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next)) 85189e560f4SRandall Stewart 852b18bfc3dSJohn Dyson #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 853b18bfc3dSJohn Dyson 85417e2cf15SJulian Elischer #define TAILQ_PREV(elm, headname, field) \ 85517e2cf15SJulian Elischer (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 856d19287f2SPoul-Henning Kamp 857f91aa773SAlexander Motin #define TAILQ_PREV_FAST(elm, head, type, field) \ 858f91aa773SAlexander Motin ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL : \ 859f91aa773SAlexander Motin __containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next)) 860f91aa773SAlexander Motin 86179fafc09SColin Percival #define TAILQ_REMOVE_HEAD(head, field) \ 86279fafc09SColin Percival TAILQ_REMOVE(head, TAILQ_FIRST(head), field) 86379fafc09SColin Percival 86417e2cf15SJulian Elischer #define TAILQ_REMOVE(head, elm, field) do { \ 865ad542210SEd Maste QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ 866ad542210SEd Maste QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ 867af8d1678SEd Maste QMD_TAILQ_CHECK_NEXT(elm, field); \ 868af8d1678SEd Maste QMD_TAILQ_CHECK_PREV(elm, field); \ 86957ebe415SJake Burkholder if ((TAILQ_NEXT((elm), field)) != NULL) \ 87057ebe415SJake Burkholder TAILQ_NEXT((elm), field)->field.tqe_prev = \ 871df8bae1dSRodney W. Grimes (elm)->field.tqe_prev; \ 872e602ba25SJulian Elischer else { \ 873df8bae1dSRodney W. Grimes (head)->tqh_last = (elm)->field.tqe_prev; \ 874e602ba25SJulian Elischer QMD_TRACE_HEAD(head); \ 875e602ba25SJulian Elischer } \ 87657ebe415SJake Burkholder *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 877ad542210SEd Maste TRASHIT(*oldnext); \ 878ad542210SEd Maste TRASHIT(*oldprev); \ 879e602ba25SJulian Elischer QMD_TRACE_ELEM(&(elm)->field); \ 88017e2cf15SJulian Elischer } while (0) 881df8bae1dSRodney W. Grimes 8827f479deeSDag-Erling Smørgrav #define TAILQ_REPLACE(head, elm, elm2, field) do { \ 8837f479deeSDag-Erling Smørgrav QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ 8847f479deeSDag-Erling Smørgrav QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ 8857f479deeSDag-Erling Smørgrav QMD_TAILQ_CHECK_NEXT(elm, field); \ 8867f479deeSDag-Erling Smørgrav QMD_TAILQ_CHECK_PREV(elm, field); \ 8877f479deeSDag-Erling Smørgrav TAILQ_NEXT((elm2), field) = TAILQ_NEXT((elm), field); \ 8887f479deeSDag-Erling Smørgrav if (TAILQ_NEXT((elm2), field) != TAILQ_END(head)) \ 8897f479deeSDag-Erling Smørgrav TAILQ_NEXT((elm2), field)->field.tqe_prev = \ 8907f479deeSDag-Erling Smørgrav &(elm2)->field.tqe_next; \ 8917f479deeSDag-Erling Smørgrav else \ 8927f479deeSDag-Erling Smørgrav (head)->tqh_last = &(elm2)->field.tqe_next; \ 8937f479deeSDag-Erling Smørgrav (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ 8947f479deeSDag-Erling Smørgrav *(elm2)->field.tqe_prev = (elm2); \ 8957f479deeSDag-Erling Smørgrav TRASHIT(*oldnext); \ 8967f479deeSDag-Erling Smørgrav TRASHIT(*oldprev); \ 8977f479deeSDag-Erling Smørgrav QMD_TRACE_ELEM(&(elm)->field); \ 8987f479deeSDag-Erling Smørgrav } while (0) 8997f479deeSDag-Erling Smørgrav 900cfeb7489SZachary Loafman #define TAILQ_SWAP(head1, head2, type, field) do { \ 90138b622e1SHans Petter Selasky QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ 90238b622e1SHans Petter Selasky QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 903cfeb7489SZachary Loafman (head1)->tqh_first = (head2)->tqh_first; \ 904cfeb7489SZachary Loafman (head1)->tqh_last = (head2)->tqh_last; \ 905cfeb7489SZachary Loafman (head2)->tqh_first = swap_first; \ 906cfeb7489SZachary Loafman (head2)->tqh_last = swap_last; \ 907cfeb7489SZachary Loafman if ((swap_first = (head1)->tqh_first) != NULL) \ 908cfeb7489SZachary Loafman swap_first->field.tqe_prev = &(head1)->tqh_first; \ 909cfeb7489SZachary Loafman else \ 910cfeb7489SZachary Loafman (head1)->tqh_last = &(head1)->tqh_first; \ 911cfeb7489SZachary Loafman if ((swap_first = (head2)->tqh_first) != NULL) \ 912cfeb7489SZachary Loafman swap_first->field.tqe_prev = &(head2)->tqh_first; \ 913cfeb7489SZachary Loafman else \ 914cfeb7489SZachary Loafman (head2)->tqh_last = &(head2)->tqh_first; \ 915cfeb7489SZachary Loafman } while (0) 916cfeb7489SZachary Loafman 9178d55837dSAlex Richardson #define TAILQ_END(head) NULL 9188d55837dSAlex Richardson 919df8bae1dSRodney W. Grimes #endif /* !_SYS_QUEUE_H_ */ 920