11590Srgrimes/*- 21590Srgrimes * Copyright (c) 1991, 1993 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * Redistribution and use in source and binary forms, with or without 61590Srgrimes * modification, are permitted provided that the following conditions 71590Srgrimes * are met: 81590Srgrimes * 1. Redistributions of source code must retain the above copyright 91590Srgrimes * notice, this list of conditions and the following disclaimer. 101590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111590Srgrimes * notice, this list of conditions and the following disclaimer in the 121590Srgrimes * documentation and/or other materials provided with the distribution. 131590Srgrimes * 4. Neither the name of the University nor the names of its contributors 141590Srgrimes * may be used to endorse or promote products derived from this software 151590Srgrimes * without specific prior written permission. 161590Srgrimes * 171590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271590Srgrimes * SUCH DAMAGE. 281590Srgrimes * 291590Srgrimes * @(#)queue.h 8.5 (Berkeley) 8/20/94 301590Srgrimes * $FreeBSD$ 3127953Scharnier * 321590Srgrimes * $FreeBSD$ 331590Srgrimes */ 341590Srgrimes 351590Srgrimes#ifndef _QUEUE_H_ 361590Srgrimes#define _QUEUE_H_ 3795618Smarkm 381590Srgrimes#undef __offsetof 391590Srgrimes#define __offsetof(type, field) ((size_t)(&((type *)0)->field)) 401590Srgrimes 411590Srgrimes/* 421590Srgrimes * Singly-linked Tail queue declarations. 431590Srgrimes */ 441590Srgrimes#undef STAILQ_HEAD 451590Srgrimes#define STAILQ_HEAD(name, type) \ 4695618Smarkmstruct name { \ 4795618Smarkm struct type *stqh_first;/* first element */ \ 4895618Smarkm struct type **stqh_last;/* addr of last next element */ \ 4927953Scharnier} 501590Srgrimes 51218411Sjh#undef STAILQ_HEAD_INITIALIZER 521590Srgrimes#define STAILQ_HEAD_INITIALIZER(head) \ 531590Srgrimes { NULL, &(head).stqh_first } 5433648Sjb 551590Srgrimes#undef STAILQ_ENTRY 561590Srgrimes#define STAILQ_ENTRY(type) \ 571590Srgrimesstruct { \ 581590Srgrimes struct type *stqe_next; /* next element */ \ 591590Srgrimes} 601590Srgrimes 611590Srgrimes#undef STAILQ_EMPTY 621590Srgrimes#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 631590Srgrimes 641590Srgrimes#undef STAILQ_FIRST 651590Srgrimes#define STAILQ_FIRST(head) ((head)->stqh_first) 661590Srgrimes 671590Srgrimes#undef STAILQ_FOREACH 681590Srgrimes#define STAILQ_FOREACH(var, head, field) \ 691590Srgrimes for((var) = STAILQ_FIRST((head)); \ 701590Srgrimes (var); \ 711590Srgrimes (var) = STAILQ_NEXT((var), field)) 721590Srgrimes 731590Srgrimes#undef STAILQ_FOREACH_SAFE 741590Srgrimes#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 751590Srgrimes for ((var) = STAILQ_FIRST((head)); \ 761590Srgrimes (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 771590Srgrimes (var) = (tvar)) 781590Srgrimes 791590Srgrimes#undef STAILQ_INIT 801590Srgrimes#define STAILQ_INIT(head) do { \ 811590Srgrimes STAILQ_FIRST((head)) = NULL; \ 821590Srgrimes (head)->stqh_last = &STAILQ_FIRST((head)); \ 831590Srgrimes} while (0) 841590Srgrimes 851590Srgrimes#undef STAILQ_INSERT_AFTER 86145617Srobert#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 871590Srgrimes if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 881590Srgrimes (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 891590Srgrimes STAILQ_NEXT((tqelm), field) = (elm); \ 901590Srgrimes} while (0) 9195618Smarkm 921590Srgrimes#undef STAILQ_INSERT_HEAD 931590Srgrimes#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 9492921Simp if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 9592921Simp (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 9692921Simp STAILQ_FIRST((head)) = (elm); \ 9792921Simp} while (0) 9892921Simp 9992921Simp#undef STAILQ_INSERT_TAIL 10092921Simp#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 10192921Simp STAILQ_NEXT((elm), field) = NULL; \ 10292921Simp *(head)->stqh_last = (elm); \ 10392921Simp (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 1041590Srgrimes} while (0) 10583303Sru 10683303Sru#undef STAILQ_LAST 10783303Sru#define STAILQ_LAST(head, type, field) \ 10883303Sru (STAILQ_EMPTY((head)) ? \ 10983303Sru NULL : \ 1101590Srgrimes ((struct type *)(void *) \ 11195618Smarkm ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 1121590Srgrimes 1131590Srgrimes#undef STAILQ_NEXT 1141590Srgrimes#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 1151590Srgrimes 1161590Srgrimes#undef STAILQ_REMOVE 1171590Srgrimes#define STAILQ_REMOVE(head, elm, type, field) do { \ 1181590Srgrimes if (STAILQ_FIRST((head)) == (elm)) { \ 1191590Srgrimes STAILQ_REMOVE_HEAD((head), field); \ 1201590Srgrimes } \ 1211590Srgrimes else { \ 1221590Srgrimes struct type *curelm = STAILQ_FIRST((head)); \ 1231590Srgrimes while (STAILQ_NEXT(curelm, field) != (elm)) \ 1241590Srgrimes curelm = STAILQ_NEXT(curelm, field); \ 12595618Smarkm if ((STAILQ_NEXT(curelm, field) = \ 1261590Srgrimes STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 12795618Smarkm (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 12895618Smarkm } \ 12983303Sru} while (0) 130218410Sjh 1311590Srgrimes#undef STAILQ_REMOVE_HEAD 1321590Srgrimes#define STAILQ_REMOVE_HEAD(head, field) do { \ 1331590Srgrimes if ((STAILQ_FIRST((head)) = \ 1341590Srgrimes STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 1351590Srgrimes (head)->stqh_last = &STAILQ_FIRST((head)); \ 136218410Sjh} while (0) 1371590Srgrimes 1381590Srgrimes#undef STAILQ_REMOVE_HEAD_UNTIL 139218410Sjh#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 140218410Sjh if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ 1411590Srgrimes (head)->stqh_last = &STAILQ_FIRST((head)); \ 1421590Srgrimes} while (0) 1431590Srgrimes 1441590Srgrimes/* 1451590Srgrimes * List declarations. 1461590Srgrimes */ 1471590Srgrimes#undef LIST_HEAD 1481590Srgrimes#define LIST_HEAD(name, type) \ 1491590Srgrimesstruct name { \ 1501590Srgrimes struct type *lh_first; /* first element */ \ 1511590Srgrimes} 1521590Srgrimes 1531590Srgrimes#undef LIST_HEAD_INITIALIZER 1541590Srgrimes#define LIST_HEAD_INITIALIZER(head) \ 1551590Srgrimes { NULL } 1561590Srgrimes 1571590Srgrimes#undef LIST_ENTRY 15883303Sru#define LIST_ENTRY(type) \ 15983303Srustruct { \ 1601590Srgrimes struct type *le_next; /* next element */ \ 1611590Srgrimes struct type **le_prev; /* address of previous next element */ \ 1621590Srgrimes} 1631590Srgrimes 1641590Srgrimes/* 1651590Srgrimes * List functions. 1661590Srgrimes */ 1671590Srgrimes 1681590Srgrimes#undef LIST_EMPTY 16995618Smarkm#define LIST_EMPTY(head) ((head)->lh_first == NULL) 1701590Srgrimes 1711590Srgrimes#undef LIST_FIRST 1721590Srgrimes#define LIST_FIRST(head) ((head)->lh_first) 1731590Srgrimes 1741590Srgrimes#undef LIST_FOREACH 1751590Srgrimes#define LIST_FOREACH(var, head, field) \ 1761590Srgrimes for ((var) = LIST_FIRST((head)); \ 17783303Sru (var); \ 1781590Srgrimes (var) = LIST_NEXT((var), field)) 1791590Srgrimes 1801590Srgrimes#undef LIST_FOREACH_SAFE 1811590Srgrimes#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 18283303Sru for ((var) = LIST_FIRST((head)); \ 18395618Smarkm (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 18483303Sru (var) = (tvar)) 18583303Sru 1861590Srgrimes#undef LIST_INIT 1871590Srgrimes#define LIST_INIT(head) do { \ 1881590Srgrimes LIST_FIRST((head)) = NULL; \ 1891590Srgrimes} while (0) 1901590Srgrimes 1911590Srgrimes#undef LIST_INSERT_AFTER 1921590Srgrimes#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 19395618Smarkm if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 1941590Srgrimes LIST_NEXT((listelm), field)->field.le_prev = \ 19595618Smarkm &LIST_NEXT((elm), field); \ 19695618Smarkm LIST_NEXT((listelm), field) = (elm); \ 1971590Srgrimes (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 1981590Srgrimes} while (0) 1991590Srgrimes 2001590Srgrimes#undef LIST_INSERT_BEFORE 2011590Srgrimes#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 2021590Srgrimes (elm)->field.le_prev = (listelm)->field.le_prev; \ 2031590Srgrimes LIST_NEXT((elm), field) = (listelm); \ 2041590Srgrimes *(listelm)->field.le_prev = (elm); \ 2051590Srgrimes (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 20615909Sjoerg} while (0) 20715909Sjoerg 20815909Sjoerg#undef LIST_INSERT_HEAD 20915909Sjoerg#define LIST_INSERT_HEAD(head, elm, field) do { \ 2101590Srgrimes if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 2111590Srgrimes LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 2121590Srgrimes LIST_FIRST((head)) = (elm); \ 2131590Srgrimes (elm)->field.le_prev = &LIST_FIRST((head)); \ 2141590Srgrimes} while (0) 21595618Smarkm 2161590Srgrimes#undef LIST_NEXT 21795618Smarkm#define LIST_NEXT(elm, field) ((elm)->field.le_next) 21895618Smarkm 2191590Srgrimes#undef LIST_REMOVE 2201590Srgrimes#define LIST_REMOVE(elm, field) do { \ 2211590Srgrimes if (LIST_NEXT((elm), field) != NULL) \ 2221590Srgrimes LIST_NEXT((elm), field)->field.le_prev = \ 2231590Srgrimes (elm)->field.le_prev; \ 2241590Srgrimes *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 2251590Srgrimes} while (0) 2261590Srgrimes 2271590Srgrimes#endif /* !_QUEUE_H_ */ 2281590Srgrimes