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/10/sys/sys/queue.h 307534 2016-10-17 21:49:54Z mckusick $ 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 * 79307534Smckusick * Below is a summary of implemented functions where: 80307534Smckusick * + means the macro is available 81307534Smckusick * - means the macro is not available 82307534Smckusick * s means the macro is available but is slow (runs in O(n) time) 8325188Sphk * 84118904Skan * SLIST LIST STAILQ TAILQ 85118904Skan * _HEAD + + + + 86289018Shselasky * _CLASS_HEAD + + + + 87118904Skan * _HEAD_INITIALIZER + + + + 88118904Skan * _ENTRY + + + + 89289018Shselasky * _CLASS_ENTRY + + + + 90118904Skan * _INIT + + + + 91118904Skan * _EMPTY + + + + 92118904Skan * _FIRST + + + + 93118904Skan * _NEXT + + + + 94240422Sed * _PREV - + - + 95118904Skan * _LAST - - + + 96118904Skan * _FOREACH + + + + 97251887Slstewart * _FOREACH_FROM + + + + 98118904Skan * _FOREACH_SAFE + + + + 99251887Slstewart * _FOREACH_FROM_SAFE + + + + 100118904Skan * _FOREACH_REVERSE - - - + 101251887Slstewart * _FOREACH_REVERSE_FROM - - - + 102118904Skan * _FOREACH_REVERSE_SAFE - - - + 103251887Slstewart * _FOREACH_REVERSE_FROM_SAFE - - - + 104118904Skan * _INSERT_HEAD + + + + 105118904Skan * _INSERT_BEFORE - + - + 106118904Skan * _INSERT_AFTER + + + + 107118904Skan * _INSERT_TAIL - - + + 108307534Smckusick * _CONCAT s s + + 109192926Sed * _REMOVE_AFTER + - + - 110118904Skan * _REMOVE_HEAD + - + - 111307534Smckusick * _REMOVE s + s + 112221843Smdf * _SWAP + + + + 11325188Sphk * 1141541Srgrimes */ 115152590Semaste#ifdef QUEUE_MACRO_DEBUG 11699091Sjulian/* Store the last 2 places the queue element or head was altered */ 11799072Sjulianstruct qm_trace { 118246387Sglebius unsigned long lastline; 119246387Sglebius unsigned long prevline; 120246387Sglebius const char *lastfile; 121246387Sglebius const char *prevfile; 12299072Sjulian}; 1231541Srgrimes 124118904Skan#define TRACEBUF struct qm_trace trace; 125279633Shselasky#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } , 126118904Skan#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 127204106Semaste#define QMD_SAVELINK(name, link) void **name = (void *)&(link) 12899072Sjulian 129118904Skan#define QMD_TRACE_HEAD(head) do { \ 13099072Sjulian (head)->trace.prevline = (head)->trace.lastline; \ 13199072Sjulian (head)->trace.prevfile = (head)->trace.lastfile; \ 13299072Sjulian (head)->trace.lastline = __LINE__; \ 13399072Sjulian (head)->trace.lastfile = __FILE__; \ 13499072Sjulian} while (0) 13599072Sjulian 136118904Skan#define QMD_TRACE_ELEM(elem) do { \ 13799072Sjulian (elem)->trace.prevline = (elem)->trace.lastline; \ 13899072Sjulian (elem)->trace.prevfile = (elem)->trace.lastfile; \ 13999072Sjulian (elem)->trace.lastline = __LINE__; \ 14099072Sjulian (elem)->trace.lastfile = __FILE__; \ 14199072Sjulian} while (0) 14299072Sjulian 14399072Sjulian#else 144118904Skan#define QMD_TRACE_ELEM(elem) 145118904Skan#define QMD_TRACE_HEAD(head) 146204106Semaste#define QMD_SAVELINK(name, link) 147118904Skan#define TRACEBUF 148246387Sglebius#define TRACEBUF_INITIALIZER 149118904Skan#define TRASHIT(x) 15099072Sjulian#endif /* QUEUE_MACRO_DEBUG */ 15199072Sjulian 152289018Shselasky#ifdef __cplusplus 1531541Srgrimes/* 154289018Shselasky * In C++ there can be structure lists and class lists: 155289018Shselasky */ 156289018Shselasky#define QUEUE_TYPEOF(type) type 157289018Shselasky#else 158289018Shselasky#define QUEUE_TYPEOF(type) struct type 159289018Shselasky#endif 160289018Shselasky 161289018Shselasky/* 16260744Sjake * Singly-linked List declarations. 16314940Sgibbs */ 16460744Sjake#define SLIST_HEAD(name, type) \ 16514940Sgibbsstruct name { \ 16660938Sjake struct type *slh_first; /* first element */ \ 16714940Sgibbs} 16851955Sn_hibma 169289018Shselasky#define SLIST_CLASS_HEAD(name, type) \ 170289018Shselaskystruct name { \ 171289018Shselasky class type *slh_first; /* first element */ \ 172289018Shselasky} 173289018Shselasky 17460744Sjake#define SLIST_HEAD_INITIALIZER(head) \ 17551955Sn_hibma { NULL } 176118904Skan 17760744Sjake#define SLIST_ENTRY(type) \ 17814940Sgibbsstruct { \ 17960938Sjake struct type *sle_next; /* next element */ \ 18014940Sgibbs} 181118904Skan 182289018Shselasky#define SLIST_CLASS_ENTRY(type) \ 183289018Shselaskystruct { \ 184289018Shselasky class type *sle_next; /* next element */ \ 185289018Shselasky} 186289018Shselasky 18714940Sgibbs/* 18814940Sgibbs * Singly-linked List functions. 18914940Sgibbs */ 190307534Smckusick#define SLIST_CONCAT(head1, head2, type, field) do { \ 191307534Smckusick QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ 192307534Smckusick if (curelm == NULL) { \ 193307534Smckusick if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ 194307534Smckusick SLIST_INIT(head2); \ 195307534Smckusick } else if (SLIST_FIRST(head2) != NULL) { \ 196307534Smckusick while (SLIST_NEXT(curelm, field) != NULL) \ 197307534Smckusick curelm = SLIST_NEXT(curelm, field); \ 198307534Smckusick SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ 199307534Smckusick SLIST_INIT(head2); \ 200307534Smckusick } \ 201307534Smckusick} while (0) 202307534Smckusick 20321029Sphk#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 20421029Sphk 20521029Sphk#define SLIST_FIRST(head) ((head)->slh_first) 20621029Sphk 20760744Sjake#define SLIST_FOREACH(var, head, field) \ 20860744Sjake for ((var) = SLIST_FIRST((head)); \ 20960744Sjake (var); \ 21060744Sjake (var) = SLIST_NEXT((var), field)) 21128730Sphk 212251887Slstewart#define SLIST_FOREACH_FROM(var, head, field) \ 213251887Slstewart for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 214251887Slstewart (var); \ 215251887Slstewart (var) = SLIST_NEXT((var), field)) 216251887Slstewart 217118904Skan#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 218118904Skan for ((var) = SLIST_FIRST((head)); \ 219118904Skan (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 220118904Skan (var) = (tvar)) 221118904Skan 222251887Slstewart#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 223251887Slstewart for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 224251887Slstewart (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 225251887Slstewart (var) = (tvar)) 226251887Slstewart 227118904Skan#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 228101351Salfred for ((varp) = &SLIST_FIRST((head)); \ 229101351Salfred ((var) = *(varp)) != NULL; \ 230101351Salfred (varp) = &SLIST_NEXT((var), field)) 231101351Salfred 23260744Sjake#define SLIST_INIT(head) do { \ 23360744Sjake SLIST_FIRST((head)) = NULL; \ 23460744Sjake} while (0) 23514940Sgibbs 23660744Sjake#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 23760744Sjake SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 23860744Sjake SLIST_NEXT((slistelm), field) = (elm); \ 23933793Sjulian} while (0) 24014940Sgibbs 24160744Sjake#define SLIST_INSERT_HEAD(head, elm, field) do { \ 24260744Sjake SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 24360744Sjake SLIST_FIRST((head)) = (elm); \ 24433793Sjulian} while (0) 24514940Sgibbs 24660744Sjake#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 24721029Sphk 24860744Sjake#define SLIST_REMOVE(head, elm, type, field) do { \ 249204106Semaste QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ 25060744Sjake if (SLIST_FIRST((head)) == (elm)) { \ 25114940Sgibbs SLIST_REMOVE_HEAD((head), field); \ 25214940Sgibbs } \ 25314940Sgibbs else { \ 254289018Shselasky QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \ 25560744Sjake while (SLIST_NEXT(curelm, field) != (elm)) \ 25660744Sjake curelm = SLIST_NEXT(curelm, field); \ 257192926Sed SLIST_REMOVE_AFTER(curelm, field); \ 25814940Sgibbs } \ 259204106Semaste TRASHIT(*oldnext); \ 26033793Sjulian} while (0) 26114940Sgibbs 262192926Sed#define SLIST_REMOVE_AFTER(elm, field) do { \ 263179210Sed SLIST_NEXT(elm, field) = \ 264179210Sed SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 265179210Sed} while (0) 266179210Sed 26760744Sjake#define SLIST_REMOVE_HEAD(head, field) do { \ 26860744Sjake SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 26960744Sjake} while (0) 27060744Sjake 271216149Skib#define SLIST_SWAP(head1, head2, type) do { \ 272289018Shselasky QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ 273216149Skib SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 274216149Skib SLIST_FIRST(head2) = swap_first; \ 275216149Skib} while (0) 276216149Skib 27714940Sgibbs/* 27860744Sjake * Singly-linked Tail queue declarations. 27914940Sgibbs */ 28060744Sjake#define STAILQ_HEAD(name, type) \ 28114940Sgibbsstruct name { \ 28260938Sjake struct type *stqh_first;/* first element */ \ 28360938Sjake struct type **stqh_last;/* addr of last next element */ \ 28414940Sgibbs} 28514940Sgibbs 286289018Shselasky#define STAILQ_CLASS_HEAD(name, type) \ 287289018Shselaskystruct name { \ 288289018Shselasky class type *stqh_first; /* first element */ \ 289289018Shselasky class type **stqh_last; /* addr of last next element */ \ 290289018Shselasky} 291289018Shselasky 29260744Sjake#define STAILQ_HEAD_INITIALIZER(head) \ 29342359Sn_hibma { NULL, &(head).stqh_first } 29442359Sn_hibma 29560744Sjake#define STAILQ_ENTRY(type) \ 29614940Sgibbsstruct { \ 29760938Sjake struct type *stqe_next; /* next element */ \ 29814940Sgibbs} 29914940Sgibbs 300289018Shselasky#define STAILQ_CLASS_ENTRY(type) \ 301289018Shselaskystruct { \ 302289018Shselasky class type *stqe_next; /* next element */ \ 303289018Shselasky} 304289018Shselasky 30514940Sgibbs/* 30614940Sgibbs * Singly-linked Tail queue functions. 30714940Sgibbs */ 30894938Stmm#define STAILQ_CONCAT(head1, head2) do { \ 30994938Stmm if (!STAILQ_EMPTY((head2))) { \ 31094938Stmm *(head1)->stqh_last = (head2)->stqh_first; \ 31194938Stmm (head1)->stqh_last = (head2)->stqh_last; \ 31294938Stmm STAILQ_INIT((head2)); \ 31394938Stmm } \ 31494938Stmm} while (0) 31594938Stmm 31660744Sjake#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 31725188Sphk 31860744Sjake#define STAILQ_FIRST(head) ((head)->stqh_first) 31960744Sjake 32060744Sjake#define STAILQ_FOREACH(var, head, field) \ 32160744Sjake for((var) = STAILQ_FIRST((head)); \ 32260744Sjake (var); \ 32360744Sjake (var) = STAILQ_NEXT((var), field)) 32460744Sjake 325251887Slstewart#define STAILQ_FOREACH_FROM(var, head, field) \ 326251887Slstewart for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 327251887Slstewart (var); \ 328251887Slstewart (var) = STAILQ_NEXT((var), field)) 329118904Skan 330118904Skan#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 331118904Skan for ((var) = STAILQ_FIRST((head)); \ 332118904Skan (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 333118904Skan (var) = (tvar)) 334118904Skan 335251887Slstewart#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 336251887Slstewart for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 337251887Slstewart (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 338251887Slstewart (var) = (tvar)) 339251887Slstewart 34033793Sjulian#define STAILQ_INIT(head) do { \ 34160744Sjake STAILQ_FIRST((head)) = NULL; \ 34260744Sjake (head)->stqh_last = &STAILQ_FIRST((head)); \ 34333793Sjulian} while (0) 34414940Sgibbs 34560744Sjake#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 34660744Sjake if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 34760744Sjake (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 34860744Sjake STAILQ_NEXT((tqelm), field) = (elm); \ 34933793Sjulian} while (0) 35014940Sgibbs 35160744Sjake#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 35260744Sjake if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 35360744Sjake (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 35460744Sjake STAILQ_FIRST((head)) = (elm); \ 35533793Sjulian} while (0) 35614940Sgibbs 35760744Sjake#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 35860744Sjake STAILQ_NEXT((elm), field) = NULL; \ 35964198Shsu *(head)->stqh_last = (elm); \ 36060744Sjake (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 36133793Sjulian} while (0) 36214940Sgibbs 363289018Shselasky#define STAILQ_LAST(head, type, field) \ 364289018Shselasky (STAILQ_EMPTY((head)) ? NULL : \ 365289018Shselasky __containerof((head)->stqh_last, \ 366289018Shselasky QUEUE_TYPEOF(type), field.stqe_next)) 36725536Sdfr 36860744Sjake#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 36914940Sgibbs 37060744Sjake#define STAILQ_REMOVE(head, elm, type, field) do { \ 371204106Semaste QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ 37260744Sjake if (STAILQ_FIRST((head)) == (elm)) { \ 37394942Stmm STAILQ_REMOVE_HEAD((head), field); \ 37414940Sgibbs } \ 37514940Sgibbs else { \ 376289018Shselasky QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ 37760744Sjake while (STAILQ_NEXT(curelm, field) != (elm)) \ 37860744Sjake curelm = STAILQ_NEXT(curelm, field); \ 379192926Sed STAILQ_REMOVE_AFTER(head, curelm, field); \ 38014940Sgibbs } \ 381204106Semaste TRASHIT(*oldnext); \ 38233793Sjulian} while (0) 38314940Sgibbs 384221843Smdf#define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 385221843Smdf if ((STAILQ_NEXT(elm, field) = \ 386221843Smdf STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 387221843Smdf (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 388221843Smdf} while (0) 389221843Smdf 39060744Sjake#define STAILQ_REMOVE_HEAD(head, field) do { \ 39160744Sjake if ((STAILQ_FIRST((head)) = \ 39260744Sjake STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 39360744Sjake (head)->stqh_last = &STAILQ_FIRST((head)); \ 39460744Sjake} while (0) 39560744Sjake 396192908Szml#define STAILQ_SWAP(head1, head2, type) do { \ 397289018Shselasky QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ 398289018Shselasky QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ 399192908Szml STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 400192908Szml (head1)->stqh_last = (head2)->stqh_last; \ 401192908Szml STAILQ_FIRST(head2) = swap_first; \ 402192908Szml (head2)->stqh_last = swap_last; \ 403192908Szml if (STAILQ_EMPTY(head1)) \ 404192908Szml (head1)->stqh_last = &STAILQ_FIRST(head1); \ 405192908Szml if (STAILQ_EMPTY(head2)) \ 406192908Szml (head2)->stqh_last = &STAILQ_FIRST(head2); \ 407192908Szml} while (0) 408192908Szml 409192908Szml 41014940Sgibbs/* 41160744Sjake * List declarations. 4121541Srgrimes */ 41360744Sjake#define LIST_HEAD(name, type) \ 4141541Srgrimesstruct name { \ 41560938Sjake struct type *lh_first; /* first element */ \ 4161541Srgrimes} 4171541Srgrimes 418289018Shselasky#define LIST_CLASS_HEAD(name, type) \ 419289018Shselaskystruct name { \ 420289018Shselasky class type *lh_first; /* first element */ \ 421289018Shselasky} 422289018Shselasky 42360744Sjake#define LIST_HEAD_INITIALIZER(head) \ 42442359Sn_hibma { NULL } 42542359Sn_hibma 42660744Sjake#define LIST_ENTRY(type) \ 4271541Srgrimesstruct { \ 42860938Sjake struct type *le_next; /* next element */ \ 42960938Sjake struct type **le_prev; /* address of previous next element */ \ 4301541Srgrimes} 4311541Srgrimes 432289018Shselasky#define LIST_CLASS_ENTRY(type) \ 433289018Shselaskystruct { \ 434289018Shselasky class type *le_next; /* next element */ \ 435289018Shselasky class type **le_prev; /* address of previous next element */ \ 436289018Shselasky} 437289018Shselasky 4381541Srgrimes/* 4391541Srgrimes * List functions. 4401541Srgrimes */ 44125188Sphk 442158929Semaste#if (defined(_KERNEL) && defined(INVARIANTS)) 443152590Semaste#define QMD_LIST_CHECK_HEAD(head, field) do { \ 444152590Semaste if (LIST_FIRST((head)) != NULL && \ 445152590Semaste LIST_FIRST((head))->field.le_prev != \ 446152590Semaste &LIST_FIRST((head))) \ 447152590Semaste panic("Bad list head %p first->prev != head", (head)); \ 448152590Semaste} while (0) 449152590Semaste 450152590Semaste#define QMD_LIST_CHECK_NEXT(elm, field) do { \ 451152590Semaste if (LIST_NEXT((elm), field) != NULL && \ 452152590Semaste LIST_NEXT((elm), field)->field.le_prev != \ 453152590Semaste &((elm)->field.le_next)) \ 454152590Semaste panic("Bad link elm %p next->prev != elm", (elm)); \ 455152590Semaste} while (0) 456152590Semaste 457152590Semaste#define QMD_LIST_CHECK_PREV(elm, field) do { \ 458152590Semaste if (*(elm)->field.le_prev != (elm)) \ 459152590Semaste panic("Bad link elm %p prev->next != elm", (elm)); \ 460152590Semaste} while (0) 461152590Semaste#else 462152590Semaste#define QMD_LIST_CHECK_HEAD(head, field) 463152590Semaste#define QMD_LIST_CHECK_NEXT(elm, field) 464152590Semaste#define QMD_LIST_CHECK_PREV(elm, field) 465158929Semaste#endif /* (_KERNEL && INVARIANTS) */ 466152590Semaste 467307534Smckusick#define LIST_CONCAT(head1, head2, type, field) do { \ 468307534Smckusick QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ 469307534Smckusick if (curelm == NULL) { \ 470307534Smckusick if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ 471307534Smckusick LIST_FIRST(head2)->field.le_prev = \ 472307534Smckusick &LIST_FIRST((head1)); \ 473307534Smckusick LIST_INIT(head2); \ 474307534Smckusick } \ 475307534Smckusick } else if (LIST_FIRST(head2) != NULL) { \ 476307534Smckusick while (LIST_NEXT(curelm, field) != NULL) \ 477307534Smckusick curelm = LIST_NEXT(curelm, field); \ 478307534Smckusick LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ 479307534Smckusick LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \ 480307534Smckusick LIST_INIT(head2); \ 481307534Smckusick } \ 482307534Smckusick} while (0) 483307534Smckusick 48460744Sjake#define LIST_EMPTY(head) ((head)->lh_first == NULL) 48525188Sphk 48660744Sjake#define LIST_FIRST(head) ((head)->lh_first) 48724935Sphk 48860744Sjake#define LIST_FOREACH(var, head, field) \ 48960744Sjake for ((var) = LIST_FIRST((head)); \ 49060744Sjake (var); \ 49160744Sjake (var) = LIST_NEXT((var), field)) 49224935Sphk 493251887Slstewart#define LIST_FOREACH_FROM(var, head, field) \ 494251887Slstewart for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 495251887Slstewart (var); \ 496251887Slstewart (var) = LIST_NEXT((var), field)) 497251887Slstewart 498118904Skan#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 499118904Skan for ((var) = LIST_FIRST((head)); \ 500118904Skan (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 501118904Skan (var) = (tvar)) 502118876Sbmilekic 503251887Slstewart#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 504251887Slstewart for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 505251887Slstewart (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 506251887Slstewart (var) = (tvar)) 507251887Slstewart 50833793Sjulian#define LIST_INIT(head) do { \ 50960744Sjake LIST_FIRST((head)) = NULL; \ 51033793Sjulian} while (0) 5111541Srgrimes 51260744Sjake#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 513152590Semaste QMD_LIST_CHECK_NEXT(listelm, field); \ 51460744Sjake if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 51560744Sjake LIST_NEXT((listelm), field)->field.le_prev = \ 51660744Sjake &LIST_NEXT((elm), field); \ 51760744Sjake LIST_NEXT((listelm), field) = (elm); \ 51860744Sjake (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 51933793Sjulian} while (0) 5201541Srgrimes 52160744Sjake#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 522152590Semaste QMD_LIST_CHECK_PREV(listelm, field); \ 52313697Sgibbs (elm)->field.le_prev = (listelm)->field.le_prev; \ 52460744Sjake LIST_NEXT((elm), field) = (listelm); \ 52513697Sgibbs *(listelm)->field.le_prev = (elm); \ 52660744Sjake (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 52733793Sjulian} while (0) 52813697Sgibbs 52960744Sjake#define LIST_INSERT_HEAD(head, elm, field) do { \ 530152590Semaste QMD_LIST_CHECK_HEAD((head), field); \ 53160744Sjake if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 53260744Sjake LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 53360744Sjake LIST_FIRST((head)) = (elm); \ 53460744Sjake (elm)->field.le_prev = &LIST_FIRST((head)); \ 53533793Sjulian} while (0) 5361541Srgrimes 53760744Sjake#define LIST_NEXT(elm, field) ((elm)->field.le_next) 53824935Sphk 539289018Shselasky#define LIST_PREV(elm, head, type, field) \ 540289018Shselasky ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 541289018Shselasky __containerof((elm)->field.le_prev, \ 542289018Shselasky QUEUE_TYPEOF(type), field.le_next)) 543240422Sed 54460744Sjake#define LIST_REMOVE(elm, field) do { \ 545204106Semaste QMD_SAVELINK(oldnext, (elm)->field.le_next); \ 546204106Semaste QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ 547152590Semaste QMD_LIST_CHECK_NEXT(elm, field); \ 548152590Semaste QMD_LIST_CHECK_PREV(elm, field); \ 54960744Sjake if (LIST_NEXT((elm), field) != NULL) \ 55060744Sjake LIST_NEXT((elm), field)->field.le_prev = \ 5511541Srgrimes (elm)->field.le_prev; \ 55260744Sjake *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 553204106Semaste TRASHIT(*oldnext); \ 554204106Semaste TRASHIT(*oldprev); \ 55533793Sjulian} while (0) 5561541Srgrimes 557192908Szml#define LIST_SWAP(head1, head2, type, field) do { \ 558289018Shselasky QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 559192908Szml LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 560192908Szml LIST_FIRST((head2)) = swap_tmp; \ 561192908Szml if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 562192908Szml swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 563192908Szml if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 564192908Szml swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 565192908Szml} while (0) 566192908Szml 5671541Srgrimes/* 56860744Sjake * Tail queue declarations. 5691541Srgrimes */ 57060744Sjake#define TAILQ_HEAD(name, type) \ 5711541Srgrimesstruct name { \ 57260938Sjake struct type *tqh_first; /* first element */ \ 57360938Sjake struct type **tqh_last; /* addr of last next element */ \ 57499072Sjulian TRACEBUF \ 5751541Srgrimes} 5761541Srgrimes 577289018Shselasky#define TAILQ_CLASS_HEAD(name, type) \ 578289018Shselaskystruct name { \ 579289018Shselasky class type *tqh_first; /* first element */ \ 580289018Shselasky class type **tqh_last; /* addr of last next element */ \ 581289018Shselasky TRACEBUF \ 582289018Shselasky} 583289018Shselasky 58460744Sjake#define TAILQ_HEAD_INITIALIZER(head) \ 585246387Sglebius { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } 58629683Sgibbs 58760744Sjake#define TAILQ_ENTRY(type) \ 5881541Srgrimesstruct { \ 58960938Sjake struct type *tqe_next; /* next element */ \ 59060938Sjake struct type **tqe_prev; /* address of previous next element */ \ 59199072Sjulian TRACEBUF \ 5921541Srgrimes} 5931541Srgrimes 594289018Shselasky#define TAILQ_CLASS_ENTRY(type) \ 595289018Shselaskystruct { \ 596289018Shselasky class type *tqe_next; /* next element */ \ 597289018Shselasky class type **tqe_prev; /* address of previous next element */ \ 598289018Shselasky TRACEBUF \ 599289018Shselasky} 600289018Shselasky 6011541Srgrimes/* 6021541Srgrimes * Tail queue functions. 6031541Srgrimes */ 604158963Semaste#if (defined(_KERNEL) && defined(INVARIANTS)) 605158963Semaste#define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 606158963Semaste if (!TAILQ_EMPTY(head) && \ 607158963Semaste TAILQ_FIRST((head))->field.tqe_prev != \ 608158963Semaste &TAILQ_FIRST((head))) \ 609158963Semaste panic("Bad tailq head %p first->prev != head", (head)); \ 610158963Semaste} while (0) 611158963Semaste 612158963Semaste#define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 613158963Semaste if (*(head)->tqh_last != NULL) \ 614158963Semaste panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 615158963Semaste} while (0) 616158963Semaste 617158963Semaste#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 618158963Semaste if (TAILQ_NEXT((elm), field) != NULL && \ 619158963Semaste TAILQ_NEXT((elm), field)->field.tqe_prev != \ 620158963Semaste &((elm)->field.tqe_next)) \ 621158963Semaste panic("Bad link elm %p next->prev != elm", (elm)); \ 622158963Semaste} while (0) 623158963Semaste 624158963Semaste#define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 625158963Semaste if (*(elm)->field.tqe_prev != (elm)) \ 626158963Semaste panic("Bad link elm %p prev->next != elm", (elm)); \ 627158963Semaste} while (0) 628158963Semaste#else 629158963Semaste#define QMD_TAILQ_CHECK_HEAD(head, field) 630158963Semaste#define QMD_TAILQ_CHECK_TAIL(head, headname) 631158963Semaste#define QMD_TAILQ_CHECK_NEXT(elm, field) 632158963Semaste#define QMD_TAILQ_CHECK_PREV(elm, field) 633158963Semaste#endif /* (_KERNEL && INVARIANTS) */ 634158963Semaste 63594938Stmm#define TAILQ_CONCAT(head1, head2, field) do { \ 63694938Stmm if (!TAILQ_EMPTY(head2)) { \ 63794938Stmm *(head1)->tqh_last = (head2)->tqh_first; \ 63894938Stmm (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 63994938Stmm (head1)->tqh_last = (head2)->tqh_last; \ 64094938Stmm TAILQ_INIT((head2)); \ 641148844Sphk QMD_TRACE_HEAD(head1); \ 64299072Sjulian QMD_TRACE_HEAD(head2); \ 64394938Stmm } \ 64494938Stmm} while (0) 64594938Stmm 64660744Sjake#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 64715138Sphk 64860744Sjake#define TAILQ_FIRST(head) ((head)->tqh_first) 64925188Sphk 65060744Sjake#define TAILQ_FOREACH(var, head, field) \ 65160744Sjake for ((var) = TAILQ_FIRST((head)); \ 65260744Sjake (var); \ 65360744Sjake (var) = TAILQ_NEXT((var), field)) 65460744Sjake 655251887Slstewart#define TAILQ_FOREACH_FROM(var, head, field) \ 656251887Slstewart for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 657251887Slstewart (var); \ 658251887Slstewart (var) = TAILQ_NEXT((var), field)) 659251887Slstewart 660118904Skan#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 661118904Skan for ((var) = TAILQ_FIRST((head)); \ 662118904Skan (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 663118904Skan (var) = (tvar)) 664118904Skan 665251887Slstewart#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 666251887Slstewart for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 667251887Slstewart (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 668251887Slstewart (var) = (tvar)) 669251887Slstewart 67060744Sjake#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 67159861Sarchie for ((var) = TAILQ_LAST((head), headname); \ 67260744Sjake (var); \ 67360744Sjake (var) = TAILQ_PREV((var), headname, field)) 67459861Sarchie 675251887Slstewart#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 676251887Slstewart for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 677251887Slstewart (var); \ 678251887Slstewart (var) = TAILQ_PREV((var), headname, field)) 679251887Slstewart 680118904Skan#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 681118904Skan for ((var) = TAILQ_LAST((head), headname); \ 682118904Skan (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 683118904Skan (var) = (tvar)) 684118904Skan 685251887Slstewart#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \ 686251887Slstewart for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 687251887Slstewart (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 688251887Slstewart (var) = (tvar)) 689251887Slstewart 69033793Sjulian#define TAILQ_INIT(head) do { \ 69160744Sjake TAILQ_FIRST((head)) = NULL; \ 69260744Sjake (head)->tqh_last = &TAILQ_FIRST((head)); \ 69399072Sjulian QMD_TRACE_HEAD(head); \ 69433793Sjulian} while (0) 6951541Srgrimes 69660744Sjake#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 697158963Semaste QMD_TAILQ_CHECK_NEXT(listelm, field); \ 69860744Sjake if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 69960744Sjake TAILQ_NEXT((elm), field)->field.tqe_prev = \ 70060744Sjake &TAILQ_NEXT((elm), field); \ 70199072Sjulian else { \ 70260744Sjake (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 70399072Sjulian QMD_TRACE_HEAD(head); \ 70499072Sjulian } \ 70560744Sjake TAILQ_NEXT((listelm), field) = (elm); \ 70660744Sjake (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 70799072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 708279633Shselasky QMD_TRACE_ELEM(&(listelm)->field); \ 70933793Sjulian} while (0) 7101541Srgrimes 71160744Sjake#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 712158963Semaste QMD_TAILQ_CHECK_PREV(listelm, field); \ 71360744Sjake (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 71460744Sjake TAILQ_NEXT((elm), field) = (listelm); \ 71560744Sjake *(listelm)->field.tqe_prev = (elm); \ 71660744Sjake (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 71799072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 718279633Shselasky QMD_TRACE_ELEM(&(listelm)->field); \ 71933793Sjulian} while (0) 7201541Srgrimes 72160744Sjake#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 722158963Semaste QMD_TAILQ_CHECK_HEAD(head, field); \ 72360744Sjake if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 72460744Sjake TAILQ_FIRST((head))->field.tqe_prev = \ 72560744Sjake &TAILQ_NEXT((elm), field); \ 7261541Srgrimes else \ 72760744Sjake (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 72860744Sjake TAILQ_FIRST((head)) = (elm); \ 72960744Sjake (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 73099072Sjulian QMD_TRACE_HEAD(head); \ 73199072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 73233793Sjulian} while (0) 7331541Srgrimes 73460744Sjake#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 735158963Semaste QMD_TAILQ_CHECK_TAIL(head, field); \ 73660744Sjake TAILQ_NEXT((elm), field) = NULL; \ 73760744Sjake (elm)->field.tqe_prev = (head)->tqh_last; \ 73860744Sjake *(head)->tqh_last = (elm); \ 73960744Sjake (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 74099072Sjulian QMD_TRACE_HEAD(head); \ 74199072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 74233793Sjulian} while (0) 74313697Sgibbs 74460744Sjake#define TAILQ_LAST(head, headname) \ 74560744Sjake (*(((struct headname *)((head)->tqh_last))->tqh_last)) 74660744Sjake 74760744Sjake#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 74860744Sjake 74960744Sjake#define TAILQ_PREV(elm, headname, field) \ 75060744Sjake (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 75160744Sjake 75260744Sjake#define TAILQ_REMOVE(head, elm, field) do { \ 753204106Semaste QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ 754204106Semaste QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ 755158963Semaste QMD_TAILQ_CHECK_NEXT(elm, field); \ 756158963Semaste QMD_TAILQ_CHECK_PREV(elm, field); \ 75760744Sjake if ((TAILQ_NEXT((elm), field)) != NULL) \ 75860744Sjake TAILQ_NEXT((elm), field)->field.tqe_prev = \ 7591541Srgrimes (elm)->field.tqe_prev; \ 76099072Sjulian else { \ 7611541Srgrimes (head)->tqh_last = (elm)->field.tqe_prev; \ 76299072Sjulian QMD_TRACE_HEAD(head); \ 76399072Sjulian } \ 76460744Sjake *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 765204106Semaste TRASHIT(*oldnext); \ 766204106Semaste TRASHIT(*oldprev); \ 76799072Sjulian QMD_TRACE_ELEM(&(elm)->field); \ 76833793Sjulian} while (0) 7691541Srgrimes 770192908Szml#define TAILQ_SWAP(head1, head2, type, field) do { \ 771289018Shselasky QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ 772289018Shselasky QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 773192908Szml (head1)->tqh_first = (head2)->tqh_first; \ 774192908Szml (head1)->tqh_last = (head2)->tqh_last; \ 775192908Szml (head2)->tqh_first = swap_first; \ 776192908Szml (head2)->tqh_last = swap_last; \ 777192908Szml if ((swap_first = (head1)->tqh_first) != NULL) \ 778192908Szml swap_first->field.tqe_prev = &(head1)->tqh_first; \ 779192908Szml else \ 780192908Szml (head1)->tqh_last = &(head1)->tqh_first; \ 781192908Szml if ((swap_first = (head2)->tqh_first) != NULL) \ 782192908Szml swap_first->field.tqe_prev = &(head2)->tqh_first; \ 783192908Szml else \ 784192908Szml (head2)->tqh_last = &(head2)->tqh_first; \ 785192908Szml} while (0) 786192908Szml 78712592Sbde#endif /* !_SYS_QUEUE_H_ */ 788