1226031Sstas/* $NetBSD: queue.h,v 1.38 2004/04/18 14:12:05 lukem Exp $ */ 2226031Sstas/* $Id$ */ 3226031Sstas 4226031Sstas/* 5226031Sstas * Copyright (c) 1991, 1993 6226031Sstas * The Regents of the University of California. All rights reserved. 7226031Sstas * 8226031Sstas * Redistribution and use in source and binary forms, with or without 9226031Sstas * modification, are permitted provided that the following conditions 10226031Sstas * are met: 11226031Sstas * 1. Redistributions of source code must retain the above copyright 12226031Sstas * notice, this list of conditions and the following disclaimer. 13226031Sstas * 2. Redistributions in binary form must reproduce the above copyright 14226031Sstas * notice, this list of conditions and the following disclaimer in the 15226031Sstas * documentation and/or other materials provided with the distribution. 16226031Sstas * 3. Neither the name of the University nor the names of its contributors 17226031Sstas * may be used to endorse or promote products derived from this software 18226031Sstas * without specific prior written permission. 19226031Sstas * 20226031Sstas * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21226031Sstas * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22226031Sstas * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23226031Sstas * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24226031Sstas * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25226031Sstas * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26226031Sstas * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27226031Sstas * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28226031Sstas * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29226031Sstas * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30226031Sstas * SUCH DAMAGE. 31226031Sstas * 32226031Sstas * @(#)queue.h 8.5 (Berkeley) 8/20/94 33226031Sstas */ 34226031Sstas 35226031Sstas#ifndef _HEIM_QUEUE_H_ 36226031Sstas#define _HEIM_QUEUE_H_ 37226031Sstas 38226031Sstas/* 39226031Sstas * Tail queue definitions. 40226031Sstas */ 41226031Sstas#define HEIM_TAILQ_HEAD(name, type) \ 42226031Sstasstruct name { \ 43226031Sstas struct type *tqh_first; /* first element */ \ 44226031Sstas struct type **tqh_last; /* addr of last next element */ \ 45226031Sstas} 46226031Sstas 47226031Sstas#define HEIM_TAILQ_HEAD_INITIALIZER(head) \ 48226031Sstas { NULL, &(head).tqh_first } 49226031Sstas#define HEIM_TAILQ_ENTRY(type) \ 50226031Sstasstruct { \ 51226031Sstas struct type *tqe_next; /* next element */ \ 52226031Sstas struct type **tqe_prev; /* address of previous next element */ \ 53226031Sstas} 54226031Sstas 55226031Sstas/* 56226031Sstas * Tail queue functions. 57226031Sstas */ 58226031Sstas#if defined(_KERNEL) && defined(QUEUEDEBUG) 59226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD(head, elm, field) \ 60226031Sstas if ((head)->tqh_first && \ 61226031Sstas (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \ 62226031Sstas panic("HEIM_TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__); 63226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL(head, elm, field) \ 64226031Sstas if (*(head)->tqh_last != NULL) \ 65226031Sstas panic("HEIM_TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__); 66226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_OP(elm, field) \ 67226031Sstas if ((elm)->field.tqe_next && \ 68226031Sstas (elm)->field.tqe_next->field.tqe_prev != \ 69226031Sstas &(elm)->field.tqe_next) \ 70226031Sstas panic("HEIM_TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\ 71226031Sstas if (*(elm)->field.tqe_prev != (elm)) \ 72226031Sstas panic("HEIM_TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__); 73226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_PREREMOVE(head, elm, field) \ 74226031Sstas if ((elm)->field.tqe_next == NULL && \ 75226031Sstas (head)->tqh_last != &(elm)->field.tqe_next) \ 76226031Sstas panic("HEIM_TAILQ_PREREMOVE head %p elm %p %s:%d", \ 77226031Sstas (head), (elm), __FILE__, __LINE__); 78226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE(elm, field) \ 79226031Sstas (elm)->field.tqe_next = (void *)1L; \ 80226031Sstas (elm)->field.tqe_prev = (void *)1L; 81226031Sstas#else 82226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD(head, elm, field) 83226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL(head, elm, field) 84226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_OP(elm, field) 85226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_PREREMOVE(head, elm, field) 86226031Sstas#define QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE(elm, field) 87226031Sstas#endif 88226031Sstas 89226031Sstas#define HEIM_TAILQ_INIT(head) do { \ 90226031Sstas (head)->tqh_first = NULL; \ 91226031Sstas (head)->tqh_last = &(head)->tqh_first; \ 92226031Sstas} while (/*CONSTCOND*/0) 93226031Sstas 94226031Sstas#define HEIM_TAILQ_INSERT_HEAD(head, elm, field) do { \ 95226031Sstas QUEUEDEBUG_HEIM_TAILQ_INSERT_HEAD((head), (elm), field) \ 96226031Sstas if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 97226031Sstas (head)->tqh_first->field.tqe_prev = \ 98226031Sstas &(elm)->field.tqe_next; \ 99226031Sstas else \ 100226031Sstas (head)->tqh_last = &(elm)->field.tqe_next; \ 101226031Sstas (head)->tqh_first = (elm); \ 102226031Sstas (elm)->field.tqe_prev = &(head)->tqh_first; \ 103226031Sstas} while (/*CONSTCOND*/0) 104226031Sstas 105226031Sstas#define HEIM_TAILQ_INSERT_TAIL(head, elm, field) do { \ 106226031Sstas QUEUEDEBUG_HEIM_TAILQ_INSERT_TAIL((head), (elm), field) \ 107226031Sstas (elm)->field.tqe_next = NULL; \ 108226031Sstas (elm)->field.tqe_prev = (head)->tqh_last; \ 109226031Sstas *(head)->tqh_last = (elm); \ 110226031Sstas (head)->tqh_last = &(elm)->field.tqe_next; \ 111226031Sstas} while (/*CONSTCOND*/0) 112226031Sstas 113226031Sstas#define HEIM_TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 114226031Sstas QUEUEDEBUG_HEIM_TAILQ_OP((listelm), field) \ 115226031Sstas if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 116226031Sstas (elm)->field.tqe_next->field.tqe_prev = \ 117226031Sstas &(elm)->field.tqe_next; \ 118226031Sstas else \ 119226031Sstas (head)->tqh_last = &(elm)->field.tqe_next; \ 120226031Sstas (listelm)->field.tqe_next = (elm); \ 121226031Sstas (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 122226031Sstas} while (/*CONSTCOND*/0) 123226031Sstas 124226031Sstas#define HEIM_TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 125226031Sstas QUEUEDEBUG_HEIM_TAILQ_OP((listelm), field) \ 126226031Sstas (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 127226031Sstas (elm)->field.tqe_next = (listelm); \ 128226031Sstas *(listelm)->field.tqe_prev = (elm); \ 129226031Sstas (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 130226031Sstas} while (/*CONSTCOND*/0) 131226031Sstas 132226031Sstas#define HEIM_TAILQ_REMOVE(head, elm, field) do { \ 133226031Sstas QUEUEDEBUG_HEIM_TAILQ_PREREMOVE((head), (elm), field) \ 134226031Sstas QUEUEDEBUG_HEIM_TAILQ_OP((elm), field) \ 135226031Sstas if (((elm)->field.tqe_next) != NULL) \ 136226031Sstas (elm)->field.tqe_next->field.tqe_prev = \ 137226031Sstas (elm)->field.tqe_prev; \ 138226031Sstas else \ 139226031Sstas (head)->tqh_last = (elm)->field.tqe_prev; \ 140226031Sstas *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 141226031Sstas QUEUEDEBUG_HEIM_TAILQ_POSTREMOVE((elm), field); \ 142226031Sstas} while (/*CONSTCOND*/0) 143226031Sstas 144226031Sstas#define HEIM_TAILQ_FOREACH(var, head, field) \ 145226031Sstas for ((var) = ((head)->tqh_first); \ 146226031Sstas (var); \ 147226031Sstas (var) = ((var)->field.tqe_next)) 148226031Sstas 149226031Sstas#define HEIM_TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 150226031Sstas for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \ 151226031Sstas (var); \ 152226031Sstas (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last))) 153226031Sstas 154226031Sstas/* 155226031Sstas * Tail queue access methods. 156226031Sstas */ 157226031Sstas#define HEIM_TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 158226031Sstas#define HEIM_TAILQ_FIRST(head) ((head)->tqh_first) 159226031Sstas#define HEIM_TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 160226031Sstas 161226031Sstas#define HEIM_TAILQ_LAST(head, headname) \ 162226031Sstas (*(((struct headname *)((head)->tqh_last))->tqh_last)) 163226031Sstas#define HEIM_TAILQ_PREV(elm, headname, field) \ 164226031Sstas (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 165226031Sstas 166226031Sstas 167226031Sstas#endif /* !_HEIM_QUEUE_H_ */ 168