1139825Simp/*- 21541Srgrimes * Copyright (c) 1991, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * 51541Srgrimes * Redistribution and use in source and binary forms, with or without 61541Srgrimes * modification, are permitted provided that the following conditions 71541Srgrimes * are met: 81541Srgrimes * 1. Redistributions of source code must retain the above copyright 91541Srgrimes * notice, this list of conditions and the following disclaimer. 101541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer in the 121541Srgrimes * documentation and/or other materials provided with the distribution. 131541Srgrimes * 4. Neither the name of the University nor the names of its contributors 141541Srgrimes * may be used to endorse or promote products derived from this software 151541Srgrimes * without specific prior written permission. 161541Srgrimes * 171541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271541Srgrimes * SUCH DAMAGE. 281541Srgrimes * 2914492Shsu * @(#)queue.h 8.5 (Berkeley) 8/20/94 3050477Speter * $FreeBSD: stable/11/sys/sys/queue.h 354405 2019-11-06 18:02:18Z mav $ 311541Srgrimes */ 321541Srgrimes 3312592Sbde#ifndef _SYS_QUEUE_H_ 341541Srgrimes#define _SYS_QUEUE_H_ 351541Srgrimes 3699594Smike#include <sys/cdefs.h> 3767708Sphk 381541Srgrimes/* 3987651Ssheldonh * This file defines four types of data structures: singly-linked lists, 4087651Ssheldonh * singly-linked tail queues, lists and tail queues. 411541Srgrimes * 4214940Sgibbs * A singly-linked list is headed by a single forward pointer. The elements 4314940Sgibbs * are singly linked for minimum space and pointer manipulation overhead at 4414940Sgibbs * the expense of O(n) removal for arbitrary elements. New elements can be 4514940Sgibbs * added to the list after an existing element or at the head of the list. 4614940Sgibbs * Elements being removed from the head of the list should use the explicit 4714940Sgibbs * macro for this purpose for optimum efficiency. A singly-linked list may 4814940Sgibbs * only be traversed in the forward direction. Singly-linked lists are ideal 4914940Sgibbs * for applications with large datasets and few or no removals or for 5014940Sgibbs * implementing a LIFO queue. 5114940Sgibbs * 5214940Sgibbs * A singly-linked tail queue is headed by a pair of pointers, one to the 5314940Sgibbs * head of the list and the other to the tail of the list. The elements are 5414940Sgibbs * singly linked for minimum space and pointer manipulation overhead at the 5514940Sgibbs * expense of O(n) removal for arbitrary elements. New elements can be added 5614940Sgibbs * to the list after an existing element, at the head of the list, or at the 5714940Sgibbs * end of the list. Elements being removed from the head of the tail queue 5814940Sgibbs * should use the explicit macro for this purpose for optimum efficiency. 5914940Sgibbs * A singly-linked tail queue may only be traversed in the forward direction. 6014940Sgibbs * Singly-linked tail queues are ideal for applications with large datasets 6114940Sgibbs * and few or no removals or for implementing a FIFO queue. 6214940Sgibbs * 631541Srgrimes * A list is headed by a single forward pointer (or an array of forward 641541Srgrimes * pointers for a hash table header). The elements are doubly linked 651541Srgrimes * so that an arbitrary element can be removed without a need to 6614492Shsu * traverse the list. New elements can be added to the list before 6714492Shsu * or after an existing element or at the head of the list. A list 68240422Sed * may be traversed in either direction. 691541Srgrimes * 701541Srgrimes * A tail queue is headed by a pair of pointers, one to the head of the 711541Srgrimes * list and the other to the tail of the list. The elements are doubly 721541Srgrimes * linked so that an arbitrary element can be removed without a need to 7314492Shsu * traverse the list. New elements can be added to the list before or 7414492Shsu * after an existing element, at the head of the list, or at the end of 7559861Sarchie * the list. A tail queue may be traversed in either direction. 761541Srgrimes * 771541Srgrimes * For details on the use of these macros, see the queue(3) manual page. 7825188Sphk * 79307533Smckusick * Below is a summary of implemented functions where: 80307533Smckusick * + means the macro is available 81307533Smckusick * - means the macro is not available 82307533Smckusick * s means the macro is available but is slow (runs in O(n) time) 8325188Sphk * 84118904Skan * SLIST LIST STAILQ TAILQ 85118904Skan * _HEAD + + + + 86284915Shselasky * _CLASS_HEAD + + + + 87118904Skan * _HEAD_INITIALIZER + + + + 88118904Skan * _ENTRY + + + + 89284915Shselasky * _CLASS_ENTRY + + + + 90118904Skan * _INIT + + + + 91118904Skan * _EMPTY + + + + 92118904Skan * _FIRST + + + + 93118904Skan * _NEXT + + + + 94240422Sed * _PREV - + - + 95118904Skan * _LAST - - + + 96344511Stuexen * _LAST_FAST - - - + 97118904Skan * _FOREACH + + + + 98251887Slstewart * _FOREACH_FROM + + + + 99118904Skan * _FOREACH_SAFE + + + + 100251887Slstewart * _FOREACH_FROM_SAFE + + + + 101118904Skan * _FOREACH_REVERSE - - - + 102251887Slstewart * _FOREACH_REVERSE_FROM - - - + 103118904Skan * _FOREACH_REVERSE_SAFE - - - + 104251887Slstewart * _FOREACH_REVERSE_FROM_SAFE - - - + 105118904Skan * _INSERT_HEAD + + + + 106118904Skan * _INSERT_BEFORE - + - + 107118904Skan * _INSERT_AFTER + + + + 108118904Skan * _INSERT_TAIL - - + + 109307533Smckusick * _CONCAT s s + + 110192926Sed * _REMOVE_AFTER + - + - 111118904Skan * _REMOVE_HEAD + - + - 112307533Smckusick * _REMOVE s + s + 113221843Smdf * _SWAP + + + + 11425188Sphk * 1151541Srgrimes */ 116152590Semaste#ifdef QUEUE_MACRO_DEBUG 11799091Sjulian/* Store the last 2 places the queue element or head was altered */ 11899072Sjulianstruct qm_trace { 119246387Sglebius unsigned long lastline; 120246387Sglebius unsigned long prevline; 121246387Sglebius const char *lastfile; 122246387Sglebius const char *prevfile; 12399072Sjulian}; 1241541Srgrimes 125118904Skan#define TRACEBUF struct qm_trace trace; 126279241Shselasky#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } , 127118904Skan#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 128204106Semaste#define QMD_SAVELINK(name, link) void **name = (void *)&(link) 12999072Sjulian 130118904Skan#define QMD_TRACE_HEAD(head) do { \ 13199072Sjulian (head)->trace.prevline = (head)->trace.lastline; \ 13299072Sjulian (head)->trace.prevfile = (head)->trace.lastfile; \ 13399072Sjulian (head)->trace.lastline = __LINE__; \ 13499072Sjulian (head)->trace.lastfile = __FILE__; \ 13599072Sjulian} while (0) 13699072Sjulian 137118904Skan#define QMD_TRACE_ELEM(elem) do { \ 13899072Sjulian (elem)->trace.prevline = (elem)->trace.lastline; \ 13999072Sjulian (elem)->trace.prevfile = (elem)->trace.lastfile; \ 14099072Sjulian (elem)->trace.lastline = __LINE__; \ 14199072Sjulian (elem)->trace.lastfile = __FILE__; \ 14299072Sjulian} while (0) 14399072Sjulian 14499072Sjulian#else 145118904Skan#define QMD_TRACE_ELEM(elem) 146118904Skan#define QMD_TRACE_HEAD(head) 147204106Semaste#define QMD_SAVELINK(name, link) 148118904Skan#define TRACEBUF 149246387Sglebius#define TRACEBUF_INITIALIZER 150118904Skan#define TRASHIT(x) 15199072Sjulian#endif /* QUEUE_MACRO_DEBUG */ 15299072Sjulian 153284915Shselasky#ifdef __cplusplus 1541541Srgrimes/* 155284915Shselasky * In C++ there can be structure lists and class lists: 156284915Shselasky */ 157284915Shselasky#define QUEUE_TYPEOF(type) type 158284915Shselasky#else 159284915Shselasky#define QUEUE_TYPEOF(type) struct type 160284915Shselasky#endif 161284915Shselasky 162284915Shselasky/* 16360744Sjake * Singly-linked List declarations. 16414940Sgibbs */ 16560744Sjake#define SLIST_HEAD(name, type) \ 16614940Sgibbsstruct name { \ 16760938Sjake struct type *slh_first; /* first element */ \ 16814940Sgibbs} 16951955Sn_hibma 170284915Shselasky#define SLIST_CLASS_HEAD(name, type) \ 171284915Shselaskystruct name { \ 172284915Shselasky class type *slh_first; /* first element */ \ 173284915Shselasky} 174284915Shselasky 17560744Sjake#define SLIST_HEAD_INITIALIZER(head) \ 17651955Sn_hibma { NULL } 177118904Skan 17860744Sjake#define SLIST_ENTRY(type) \ 17914940Sgibbsstruct { \ 18060938Sjake struct type *sle_next; /* next element */ \ 18114940Sgibbs} 182118904Skan 183284915Shselasky#define SLIST_CLASS_ENTRY(type) \ 184284915Shselaskystruct { \ 185284915Shselasky class type *sle_next; /* next element */ \ 186284915Shselasky} 187284915Shselasky 18814940Sgibbs/* 18914940Sgibbs * Singly-linked List functions. 19014940Sgibbs */ 191307533Smckusick#define SLIST_CONCAT(head1, head2, type, field) do { \ 192307533Smckusick QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ 193307533Smckusick if (curelm == NULL) { \ 194307533Smckusick if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ 195307533Smckusick SLIST_INIT(head2); \ 196307533Smckusick } else if (SLIST_FIRST(head2) != NULL) { \ 197307533Smckusick while (SLIST_NEXT(curelm, field) != NULL) \ 198307533Smckusick curelm = SLIST_NEXT(curelm, field); \ 199307533Smckusick SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ 200307533Smckusick SLIST_INIT(head2); \ 201307533Smckusick } \ 202307533Smckusick} while (0) 203307533Smckusick 20421029Sphk#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 20521029Sphk 20621029Sphk#define SLIST_FIRST(head) ((head)->slh_first) 20721029Sphk 20860744Sjake#define SLIST_FOREACH(var, head, field) \ 20960744Sjake for ((var) = SLIST_FIRST((head)); \ 21060744Sjake (var); \ 21160744Sjake (var) = SLIST_NEXT((var), field)) 21228730Sphk 213251887Slstewart#define SLIST_FOREACH_FROM(var, head, field) \ 214251887Slstewart for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 215251887Slstewart (var); \ 216251887Slstewart (var) = SLIST_NEXT((var), field)) 217251887Slstewart 218118904Skan#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 219118904Skan for ((var) = SLIST_FIRST((head)); \ 220118904Skan (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 221118904Skan (var) = (tvar)) 222118904Skan 223251887Slstewart#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 224251887Slstewart for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 225251887Slstewart (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 226251887Slstewart (var) = (tvar)) 227251887Slstewart 228118904Skan#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 229101351Salfred for ((varp) = &SLIST_FIRST((head)); \ 230101351Salfred ((var) = *(varp)) != NULL; \ 231101351Salfred (varp) = &SLIST_NEXT((var), field)) 232101351Salfred 23360744Sjake#define SLIST_INIT(head) do { \ 23460744Sjake SLIST_FIRST((head)) = NULL; \ 23560744Sjake} while (0) 23614940Sgibbs 23760744Sjake#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 23860744Sjake SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 23960744Sjake SLIST_NEXT((slistelm), field) = (elm); \ 24033793Sjulian} while (0) 24114940Sgibbs 24260744Sjake#define SLIST_INSERT_HEAD(head, elm, field) do { \ 24360744Sjake SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 24460744Sjake SLIST_FIRST((head)) = (elm); \ 24533793Sjulian} while (0) 24614940Sgibbs 24760744Sjake#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 24821029Sphk 24960744Sjake#define SLIST_REMOVE(head, elm, type, field) do { \ 250204106Semaste QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ 25160744Sjake if (SLIST_FIRST((head)) == (elm)) { \ 25214940Sgibbs SLIST_REMOVE_HEAD((head), field); \ 25314940Sgibbs } \ 25414940Sgibbs else { \ 255284915Shselasky QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \ 25660744Sjake while (SLIST_NEXT(curelm, field) != (elm)) \ 25760744Sjake curelm = SLIST_NEXT(curelm, field); \ 258192926Sed SLIST_REMOVE_AFTER(curelm, field); \ 25914940Sgibbs } \ 260204106Semaste TRASHIT(*oldnext); \ 26133793Sjulian} while (0) 26214940Sgibbs 263192926Sed#define SLIST_REMOVE_AFTER(elm, field) do { \ 264179210Sed SLIST_NEXT(elm, field) = \ 265179210Sed SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 266179210Sed} while (0) 267179210Sed 26860744Sjake#define SLIST_REMOVE_HEAD(head, field) do { \ 26960744Sjake SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 27060744Sjake} while (0) 27160744Sjake 272216149Skib#define SLIST_SWAP(head1, head2, type) do { \ 273284915Shselasky QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ 274216149Skib SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 275216149Skib SLIST_FIRST(head2) = swap_first; \ 276216149Skib} while (0) 277216149Skib 27814940Sgibbs/* 27960744Sjake * Singly-linked Tail queue declarations. 28014940Sgibbs */ 28160744Sjake#define STAILQ_HEAD(name, type) \ 28214940Sgibbsstruct name { \ 28360938Sjake struct type *stqh_first;/* first element */ \ 28460938Sjake struct type **stqh_last;/* addr of last next element */ \ 28514940Sgibbs} 28614940Sgibbs 287284915Shselasky#define STAILQ_CLASS_HEAD(name, type) \ 288284915Shselaskystruct name { \ 289284915Shselasky class type *stqh_first; /* first element */ \ 290284915Shselasky class type **stqh_last; /* addr of last next element */ \ 291284915Shselasky} 292284915Shselasky 29360744Sjake#define STAILQ_HEAD_INITIALIZER(head) \ 29442359Sn_hibma { NULL, &(head).stqh_first } 29542359Sn_hibma 29660744Sjake#define STAILQ_ENTRY(type) \ 29714940Sgibbsstruct { \ 29860938Sjake struct type *stqe_next; /* next element */ \ 29914940Sgibbs} 30014940Sgibbs 301284915Shselasky#define STAILQ_CLASS_ENTRY(type) \ 302284915Shselaskystruct { \ 303284915Shselasky class type *stqe_next; /* next element */ \ 304284915Shselasky} 305284915Shselasky 30614940Sgibbs/* 30714940Sgibbs * Singly-linked Tail queue functions. 30814940Sgibbs */ 30994938Stmm#define STAILQ_CONCAT(head1, head2) do { \ 31094938Stmm if (!STAILQ_EMPTY((head2))) { \ 31194938Stmm *(head1)->stqh_last = (head2)->stqh_first; \ 31294938Stmm (head1)->stqh_last = (head2)->stqh_last; \ 31394938Stmm STAILQ_INIT((head2)); \ 31494938Stmm } \ 31594938Stmm} while (0) 31694938Stmm 31760744Sjake#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 31825188Sphk 31960744Sjake#define STAILQ_FIRST(head) ((head)->stqh_first) 32060744Sjake 32160744Sjake#define STAILQ_FOREACH(var, head, field) \ 32260744Sjake for((var) = STAILQ_FIRST((head)); \ 32360744Sjake (var); \ 32460744Sjake (var) = STAILQ_NEXT((var), field)) 32560744Sjake 326251887Slstewart#define STAILQ_FOREACH_FROM(var, head, field) \ 327251887Slstewart for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 328251887Slstewart (var); \ 329251887Slstewart (var) = STAILQ_NEXT((var), field)) 330118904Skan 331118904Skan#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 332118904Skan for ((var) = STAILQ_FIRST((head)); \ 333118904Skan (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 334118904Skan (var) = (tvar)) 335118904Skan 336251887Slstewart#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 337251887Slstewart for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 338251887Slstewart (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 339251887Slstewart (var) = (tvar)) 340251887Slstewart 34133793Sjulian#define STAILQ_INIT(head) do { \ 34260744Sjake STAILQ_FIRST((head)) = NULL; \ 34360744Sjake (head)->stqh_last = &STAILQ_FIRST((head)); \ 34433793Sjulian} while (0) 34514940Sgibbs 34660744Sjake#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 34760744Sjake if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 34860744Sjake (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 34960744Sjake STAILQ_NEXT((tqelm), field) = (elm); \ 35033793Sjulian} while (0) 35114940Sgibbs 35260744Sjake#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 35360744Sjake if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 35460744Sjake (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 35560744Sjake STAILQ_FIRST((head)) = (elm); \ 35633793Sjulian} while (0) 35714940Sgibbs 35860744Sjake#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 35960744Sjake STAILQ_NEXT((elm), field) = NULL; \ 36064198Shsu *(head)->stqh_last = (elm); \ 36160744Sjake (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 36233793Sjulian} while (0) 36314940Sgibbs 364284915Shselasky#define STAILQ_LAST(head, type, field) \ 365284915Shselasky (STAILQ_EMPTY((head)) ? NULL : \ 366284915Shselasky __containerof((head)->stqh_last, \ 367284915Shselasky QUEUE_TYPEOF(type), field.stqe_next)) 36825536Sdfr 36960744Sjake#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 37014940Sgibbs 37160744Sjake#define STAILQ_REMOVE(head, elm, type, field) do { \ 372204106Semaste QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ 37360744Sjake if (STAILQ_FIRST((head)) == (elm)) { \ 37494942Stmm STAILQ_REMOVE_HEAD((head), field); \ 37514940Sgibbs } \ 37614940Sgibbs else { \ 377284915Shselasky QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ 37860744Sjake while (STAILQ_NEXT(curelm, field) != (elm)) \ 37960744Sjake curelm = STAILQ_NEXT(curelm, field); \ 380192926Sed STAILQ_REMOVE_AFTER(head, curelm, field); \ 38114940Sgibbs } \ 382204106Semaste TRASHIT(*oldnext); \ 38333793Sjulian} while (0) 38414940Sgibbs 385221843Smdf#define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 386221843Smdf if ((STAILQ_NEXT(elm, field) = \ 387221843Smdf STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 388221843Smdf (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 389221843Smdf} while (0) 390221843Smdf 39160744Sjake#define STAILQ_REMOVE_HEAD(head, field) do { \ 39260744Sjake if ((STAILQ_FIRST((head)) = \ 39360744Sjake STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 39460744Sjake (head)->stqh_last = &STAILQ_FIRST((head)); \ 39560744Sjake} while (0) 39660744Sjake 397192908Szml#define STAILQ_SWAP(head1, head2, type) do { \ 398284915Shselasky QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ 399284915Shselasky QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ 400192908Szml STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 401192908Szml (head1)->stqh_last = (head2)->stqh_last; \ 402192908Szml STAILQ_FIRST(head2) = swap_first; \ 403192908Szml (head2)->stqh_last = swap_last; \ 404192908Szml if (STAILQ_EMPTY(head1)) \ 405192908Szml (head1)->stqh_last = &STAILQ_FIRST(head1); \ 406192908Szml if (STAILQ_EMPTY(head2)) \ 407192908Szml (head2)->stqh_last = &STAILQ_FIRST(head2); \ 408192908Szml} while (0) 409192908Szml 410192908Szml 41114940Sgibbs/* 41260744Sjake * List declarations. 4131541Srgrimes */ 41460744Sjake#define LIST_HEAD(name, type) \ 4151541Srgrimesstruct name { \ 41660938Sjake struct type *lh_first; /* first element */ \ 4171541Srgrimes} 4181541Srgrimes 419284915Shselasky#define LIST_CLASS_HEAD(name, type) \ 420284915Shselaskystruct name { \ 421284915Shselasky class type *lh_first; /* first element */ \ 422284915Shselasky} 423284915Shselasky 42460744Sjake#define LIST_HEAD_INITIALIZER(head) \ 42542359Sn_hibma { NULL } 42642359Sn_hibma 42760744Sjake#define LIST_ENTRY(type) \ 4281541Srgrimesstruct { \ 42960938Sjake struct type *le_next; /* next element */ \ 43060938Sjake struct type **le_prev; /* address of previous next element */ \ 4311541Srgrimes} 4321541Srgrimes 433284915Shselasky#define LIST_CLASS_ENTRY(type) \ 434284915Shselaskystruct { \ 435284915Shselasky class type *le_next; /* next element */ \ 436284915Shselasky class type **le_prev; /* address of previous next element */ \ 437284915Shselasky} 438284915Shselasky 4391541Srgrimes/* 4401541Srgrimes * List functions. 4411541Srgrimes */ 44225188Sphk 443158929Semaste#if (defined(_KERNEL) && defined(INVARIANTS)) 444152590Semaste#define QMD_LIST_CHECK_HEAD(head, field) do { \ 445152590Semaste if (LIST_FIRST((head)) != NULL && \ 446152590Semaste LIST_FIRST((head))->field.le_prev != \ 447152590Semaste &LIST_FIRST((head))) \ 448152590Semaste panic("Bad list head %p first->prev != head", (head)); \ 449152590Semaste} while (0) 450152590Semaste 451152590Semaste#define QMD_LIST_CHECK_NEXT(elm, field) do { \ 452152590Semaste if (LIST_NEXT((elm), field) != NULL && \ 453152590Semaste LIST_NEXT((elm), field)->field.le_prev != \ 454152590Semaste &((elm)->field.le_next)) \ 455152590Semaste panic("Bad link elm %p next->prev != elm", (elm)); \ 456152590Semaste} while (0) 457152590Semaste 458152590Semaste#define QMD_LIST_CHECK_PREV(elm, field) do { \ 459152590Semaste if (*(elm)->field.le_prev != (elm)) \ 460152590Semaste panic("Bad link elm %p prev->next != elm", (elm)); \ 461152590Semaste} while (0) 462152590Semaste#else 463152590Semaste#define QMD_LIST_CHECK_HEAD(head, field) 464152590Semaste#define QMD_LIST_CHECK_NEXT(elm, field) 465152590Semaste#define QMD_LIST_CHECK_PREV(elm, field) 466158929Semaste#endif /* (_KERNEL && INVARIANTS) */ 467152590Semaste 468307533Smckusick#define LIST_CONCAT(head1, head2, type, field) do { \ 469307533Smckusick QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ 470307533Smckusick if (curelm == NULL) { \ 471307533Smckusick if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ 472307533Smckusick LIST_FIRST(head2)->field.le_prev = \ 473307533Smckusick &LIST_FIRST((head1)); \ 474307533Smckusick LIST_INIT(head2); \ 475307533Smckusick } \ 476307533Smckusick } else if (LIST_FIRST(head2) != NULL) { \ 477307533Smckusick while (LIST_NEXT(curelm, field) != NULL) \ 478307533Smckusick curelm = LIST_NEXT(curelm, field); \ 479307533Smckusick LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ 480307533Smckusick LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \ 481307533Smckusick LIST_INIT(head2); \ 482307533Smckusick } \ 483307533Smckusick} while (0) 484307533Smckusick 48560744Sjake#define LIST_EMPTY(head) ((head)->lh_first == NULL) 48625188Sphk 48760744Sjake#define LIST_FIRST(head) ((head)->lh_first) 48824935Sphk 48960744Sjake#define LIST_FOREACH(var, head, field) \ 49060744Sjake for ((var) = LIST_FIRST((head)); \ 49160744Sjake (var); \ 49260744Sjake (var) = LIST_NEXT((var), field)) 49324935Sphk 494251887Slstewart#define LIST_FOREACH_FROM(var, head, field) \ 495251887Slstewart for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 496251887Slstewart (var); \ 497251887Slstewart (var) = LIST_NEXT((var), field)) 498251887Slstewart 499118904Skan#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 500118904Skan for ((var) = LIST_FIRST((head)); \ 501118904Skan (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 502118904Skan (var) = (tvar)) 503118876Sbmilekic 504251887Slstewart#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 505251887Slstewart for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 506251887Slstewart (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 507251887Slstewart (var) = (tvar)) 508251887Slstewart 50933793Sjulian#define LIST_INIT(head) do { \ 51060744Sjake LIST_FIRST((head)) = NULL; \ 51133793Sjulian} while (0) 5121541Srgrimes 51360744Sjake#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 514152590Semaste QMD_LIST_CHECK_NEXT(listelm, field); \ 51560744Sjake if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 51660744Sjake LIST_NEXT((listelm), field)->field.le_prev = \ 51760744Sjake &LIST_NEXT((elm), field); \ 51860744Sjake LIST_NEXT((listelm), field) = (elm); \ 51960744Sjake (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 52033793Sjulian} while (0) 5211541Srgrimes 52260744Sjake#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 523152590Semaste QMD_LIST_CHECK_PREV(listelm, field); \ 52413697Sgibbs (elm)->field.le_prev = (listelm)->field.le_prev; \ 52560744Sjake LIST_NEXT((elm), field) = (listelm); \ 52613697Sgibbs *(listelm)->field.le_prev = (elm); \ 52760744Sjake (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 52833793Sjulian} while (0) 52913697Sgibbs 53060744Sjake#define LIST_INSERT_HEAD(head, elm, field) do { \ 531152590Semaste QMD_LIST_CHECK_HEAD((head), field); \ 53260744Sjake if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 53360744Sjake LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 53460744Sjake LIST_FIRST((head)) = (elm); \ 53560744Sjake (elm)->field.le_prev = &LIST_FIRST((head)); \ 53633793Sjulian} while (0) 5371541Srgrimes 53860744Sjake#define LIST_NEXT(elm, field) ((elm)->field.le_next) 53924935Sphk 540284915Shselasky#define LIST_PREV(elm, head, type, field) \ 541284915Shselasky ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 542284915Shselasky __containerof((elm)->field.le_prev, \ 543284915Shselasky QUEUE_TYPEOF(type), field.le_next)) 544240422Sed 54560744Sjake#define LIST_REMOVE(elm, field) do { \ 546204106Semaste QMD_SAVELINK(oldnext, (elm)->field.le_next); \ 547204106Semaste QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ 548152590Semaste QMD_LIST_CHECK_NEXT(elm, field); \ 549152590Semaste QMD_LIST_CHECK_PREV(elm, field); \ 55060744Sjake if (LIST_NEXT((elm), field) != NULL) \ 55160744Sjake LIST_NEXT((elm), field)->field.le_prev = \ 5521541Srgrimes (elm)->field.le_prev; \ 55360744Sjake *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 554204106Semaste TRASHIT(*oldnext); \ 555204106Semaste TRASHIT(*oldprev); \ 55633793Sjulian} while (0) 5571541Srgrimes 558192908Szml#define LIST_SWAP(head1, head2, type, field) do { \ 559284915Shselasky QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 560192908Szml LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 561192908Szml LIST_FIRST((head2)) = swap_tmp; \ 562192908Szml if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 563192908Szml swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 564192908Szml if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 565192908Szml swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 566192908Szml} while (0) 567192908Szml 5681541Srgrimes/* 56960744Sjake * Tail queue declarations. 5701541Srgrimes */ 57160744Sjake#define TAILQ_HEAD(name, type) \ 5721541Srgrimesstruct name { \ 57360938Sjake struct type *tqh_first; /* first element */ \ 57460938Sjake struct type **tqh_last; /* addr of last next element */ \ 57599072Sjulian TRACEBUF \ 5761541Srgrimes} 5771541Srgrimes 578284915Shselasky#define TAILQ_CLASS_HEAD(name, type) \ 579284915Shselaskystruct name { \ 580284915Shselasky class type *tqh_first; /* first element */ \ 581284915Shselasky class type **tqh_last; /* addr of last next element */ \ 582284915Shselasky TRACEBUF \ 583284915Shselasky} 584284915Shselasky 58560744Sjake#define TAILQ_HEAD_INITIALIZER(head) \ 586246387Sglebius { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } 58729683Sgibbs 58860744Sjake#define TAILQ_ENTRY(type) \ 5891541Srgrimesstruct { \ 59060938Sjake struct type *tqe_next; /* next element */ \ 59160938Sjake struct type **tqe_prev; /* address of previous next element */ \ 59299072Sjulian TRACEBUF \ 5931541Srgrimes} 5941541Srgrimes 595284915Shselasky#define TAILQ_CLASS_ENTRY(type) \ 596284915Shselaskystruct { \ 597284915Shselasky class type *tqe_next; /* next element */ \ 598284915Shselasky class type **tqe_prev; /* address of previous next element */ \ 599284915Shselasky TRACEBUF \ 600284915Shselasky} 601284915Shselasky 6021541Srgrimes/* 6031541Srgrimes * Tail queue functions. 6041541Srgrimes */ 605158963Semaste#if (defined(_KERNEL) && defined(INVARIANTS)) 606158963Semaste#define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 607158963Semaste if (!TAILQ_EMPTY(head) && \ 608158963Semaste TAILQ_FIRST((head))->field.tqe_prev != \ 609158963Semaste &TAILQ_FIRST((head))) \ 610158963Semaste panic("Bad tailq head %p first->prev != head", (head)); \ 611158963Semaste} while (0) 612158963Semaste 613158963Semaste#define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 614158963Semaste if (*(head)->tqh_last != NULL) \ 615158963Semaste panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 616158963Semaste} while (0) 617158963Semaste 618158963Semaste#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 619158963Semaste if (TAILQ_NEXT((elm), field) != NULL && \ 620158963Semaste TAILQ_NEXT((elm), field)->field.tqe_prev != \ 621158963Semaste &((elm)->field.tqe_next)) \ 622158963Semaste panic("Bad link elm %p next->prev != elm", (elm)); \ 623158963Semaste} while (0) 624158963Semaste 625158963Semaste#define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 626158963Semaste if (*(elm)->field.tqe_prev != (elm)) \ 627158963Semaste panic("Bad link elm %p prev->next != elm", (elm)); \ 628158963Semaste} while (0) 629158963Semaste#else 630158963Semaste#define QMD_TAILQ_CHECK_HEAD(head, field) 631158963Semaste#define QMD_TAILQ_CHECK_TAIL(head, headname) 632158963Semaste#define QMD_TAILQ_CHECK_NEXT(elm, field) 633158963Semaste#define QMD_TAILQ_CHECK_PREV(elm, field) 634158963Semaste#endif /* (_KERNEL && INVARIANTS) */ 635158963Semaste 63694938Stmm#define TAILQ_CONCAT(head1, head2, field) do { \ 63794938Stmm if (!TAILQ_EMPTY(head2)) { \ 63894938Stmm *(head1)->tqh_last = (head2)->tqh_first; \ 63994938Stmm (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 64094938Stmm (head1)->tqh_last = (head2)->tqh_last; \ 64194938Stmm TAILQ_INIT((head2)); \ 642148844Sphk QMD_TRACE_HEAD(head1); \ 64399072Sjulian QMD_TRACE_HEAD(head2); \ 64494938Stmm } \ 64594938Stmm} while (0) 64694938Stmm 64760744Sjake#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 64815138Sphk 64960744Sjake#define TAILQ_FIRST(head) ((head)->tqh_first) 65025188Sphk 65160744Sjake#define TAILQ_FOREACH(var, head, field) \ 65260744Sjake for ((var) = TAILQ_FIRST((head)); \ 65360744Sjake (var); \ 65460744Sjake (var) = TAILQ_NEXT((var), field)) 65560744Sjake 656251887Slstewart#define TAILQ_FOREACH_FROM(var, head, field) \ 657251887Slstewart for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 658251887Slstewart (var); \ 659251887Slstewart (var) = TAILQ_NEXT((var), field)) 660251887Slstewart 661118904Skan#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 662118904Skan for ((var) = TAILQ_FIRST((head)); \ 663118904Skan (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 664118904Skan (var) = (tvar)) 665118904Skan 666251887Slstewart#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 667251887Slstewart for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 668251887Slstewart (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 669251887Slstewart (var) = (tvar)) 670251887Slstewart 67160744Sjake#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 67259861Sarchie for ((var) = TAILQ_LAST((head), headname); \ 67360744Sjake (var); \ 67460744Sjake (var) = TAILQ_PREV((var), headname, field)) 67559861Sarchie 676251887Slstewart#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 677251887Slstewart for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 678251887Slstewart (var); \ 679251887Slstewart (var) = TAILQ_PREV((var), headname, field)) 680251887Slstewart 681118904Skan#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 682118904Skan for ((var) = TAILQ_LAST((head), headname); \ 683118904Skan (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 684118904Skan (var) = (tvar)) 685118904Skan 686251887Slstewart#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \ 687251887Slstewart for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 688251887Slstewart (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 689251887Slstewart (var) = (tvar)) 690251887Slstewart 69133793Sjulian#define TAILQ_INIT(head) do { \ 69260744Sjake TAILQ_FIRST((head)) = NULL; \ 69360744Sjake (head)->tqh_last = &TAILQ_FIRST((head)); \ 69499072Sjulian QMD_TRACE_HEAD(head); \ 69533793Sjulian} while (0) 6961541Srgrimes 69760744Sjake#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 698158963Semaste QMD_TAILQ_CHECK_NEXT(listelm, field); \ 69960744Sjake if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 70060744Sjake TAILQ_NEXT((elm), field)->field.tqe_prev = \ 70160744Sjake &TAILQ_NEXT((elm), field); \ 70299072Sjulian else { \ 70360744Sjake (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 70499072Sjulian QMD_TRACE_HEAD(head); \ 70599072Sjulian } \ 70660744Sjake TAILQ_NEXT((listelm), field) = (elm); \ 70760744Sjake (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 70899072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 709279242Shselasky QMD_TRACE_ELEM(&(listelm)->field); \ 71033793Sjulian} while (0) 7111541Srgrimes 71260744Sjake#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 713158963Semaste QMD_TAILQ_CHECK_PREV(listelm, field); \ 71460744Sjake (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 71560744Sjake TAILQ_NEXT((elm), field) = (listelm); \ 71660744Sjake *(listelm)->field.tqe_prev = (elm); \ 71760744Sjake (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 71899072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 719279242Shselasky QMD_TRACE_ELEM(&(listelm)->field); \ 72033793Sjulian} while (0) 7211541Srgrimes 72260744Sjake#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 723158963Semaste QMD_TAILQ_CHECK_HEAD(head, field); \ 72460744Sjake if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 72560744Sjake TAILQ_FIRST((head))->field.tqe_prev = \ 72660744Sjake &TAILQ_NEXT((elm), field); \ 7271541Srgrimes else \ 72860744Sjake (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 72960744Sjake TAILQ_FIRST((head)) = (elm); \ 73060744Sjake (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 73199072Sjulian QMD_TRACE_HEAD(head); \ 73299072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 73333793Sjulian} while (0) 7341541Srgrimes 73560744Sjake#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 736158963Semaste QMD_TAILQ_CHECK_TAIL(head, field); \ 73760744Sjake TAILQ_NEXT((elm), field) = NULL; \ 73860744Sjake (elm)->field.tqe_prev = (head)->tqh_last; \ 73960744Sjake *(head)->tqh_last = (elm); \ 74060744Sjake (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 74199072Sjulian QMD_TRACE_HEAD(head); \ 74299072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 74333793Sjulian} while (0) 74413697Sgibbs 74560744Sjake#define TAILQ_LAST(head, headname) \ 74660744Sjake (*(((struct headname *)((head)->tqh_last))->tqh_last)) 74760744Sjake 748344511Stuexen/* 749344511Stuexen * The FAST function is fast in that it causes no data access other 750344511Stuexen * then the access to the head. The standard LAST function above 751344511Stuexen * will cause a data access of both the element you want and 752344511Stuexen * the previous element. FAST is very useful for instances when 753344511Stuexen * you may want to prefetch the last data element. 754344511Stuexen */ 755344511Stuexen#define TAILQ_LAST_FAST(head, type, field) \ 756344511Stuexen (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next)) 757344511Stuexen 75860744Sjake#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 75960744Sjake 76060744Sjake#define TAILQ_PREV(elm, headname, field) \ 76160744Sjake (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 76260744Sjake 763354405Smav#define TAILQ_PREV_FAST(elm, head, type, field) \ 764354405Smav ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL : \ 765354405Smav __containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next)) 766354405Smav 76760744Sjake#define TAILQ_REMOVE(head, elm, field) do { \ 768204106Semaste QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ 769204106Semaste QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ 770158963Semaste QMD_TAILQ_CHECK_NEXT(elm, field); \ 771158963Semaste QMD_TAILQ_CHECK_PREV(elm, field); \ 77260744Sjake if ((TAILQ_NEXT((elm), field)) != NULL) \ 77360744Sjake TAILQ_NEXT((elm), field)->field.tqe_prev = \ 7741541Srgrimes (elm)->field.tqe_prev; \ 77599072Sjulian else { \ 7761541Srgrimes (head)->tqh_last = (elm)->field.tqe_prev; \ 77799072Sjulian QMD_TRACE_HEAD(head); \ 77899072Sjulian } \ 77960744Sjake *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 780204106Semaste TRASHIT(*oldnext); \ 781204106Semaste TRASHIT(*oldprev); \ 78299072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 78333793Sjulian} while (0) 7841541Srgrimes 785192908Szml#define TAILQ_SWAP(head1, head2, type, field) do { \ 786284915Shselasky QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ 787284915Shselasky QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 788192908Szml (head1)->tqh_first = (head2)->tqh_first; \ 789192908Szml (head1)->tqh_last = (head2)->tqh_last; \ 790192908Szml (head2)->tqh_first = swap_first; \ 791192908Szml (head2)->tqh_last = swap_last; \ 792192908Szml if ((swap_first = (head1)->tqh_first) != NULL) \ 793192908Szml swap_first->field.tqe_prev = &(head1)->tqh_first; \ 794192908Szml else \ 795192908Szml (head1)->tqh_last = &(head1)->tqh_first; \ 796192908Szml if ((swap_first = (head2)->tqh_first) != NULL) \ 797192908Szml swap_first->field.tqe_prev = &(head2)->tqh_first; \ 798192908Szml else \ 799192908Szml (head2)->tqh_last = &(head2)->tqh_first; \ 800192908Szml} while (0) 801192908Szml 80212592Sbde#endif /* !_SYS_QUEUE_H_ */ 803