queue.h revision 8876
18876Srgrimes/* 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 * 3. All advertising materials mentioning features or use of this software 141541Srgrimes * must display the following acknowledgement: 151541Srgrimes * This product includes software developed by the University of 161541Srgrimes * California, Berkeley and its contributors. 171541Srgrimes * 4. Neither the name of the University nor the names of its contributors 181541Srgrimes * may be used to endorse or promote products derived from this software 191541Srgrimes * without specific prior written permission. 201541Srgrimes * 211541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311541Srgrimes * SUCH DAMAGE. 321541Srgrimes * 331541Srgrimes * @(#)queue.h 8.4 (Berkeley) 1/4/94 348876Srgrimes * $Id: queue.h,v 1.2 1994/08/02 07:53:25 davidg Exp $ 351541Srgrimes */ 361541Srgrimes 371541Srgrimes#ifndef _SYS_QUEUE_H_ 381541Srgrimes#define _SYS_QUEUE_H_ 391541Srgrimes 401541Srgrimes/* 411541Srgrimes * This file defines three types of data structures: lists, tail queues, 421541Srgrimes * and circular queues. 431541Srgrimes * 441541Srgrimes * A list is headed by a single forward pointer (or an array of forward 451541Srgrimes * pointers for a hash table header). The elements are doubly linked 461541Srgrimes * so that an arbitrary element can be removed without a need to 471541Srgrimes * traverse the list. New elements can be added to the list after 481541Srgrimes * an existing element or at the head of the list. A list may only be 491541Srgrimes * traversed in the forward direction. 501541Srgrimes * 511541Srgrimes * A tail queue is headed by a pair of pointers, one to the head of the 521541Srgrimes * list and the other to the tail of the list. The elements are doubly 531541Srgrimes * linked so that an arbitrary element can be removed without a need to 541541Srgrimes * traverse the list. New elements can be added to the list after 551541Srgrimes * an existing element, at the head of the list, or at the end of the 561541Srgrimes * list. A tail queue may only be traversed in the forward direction. 571541Srgrimes * 581541Srgrimes * A circle queue is headed by a pair of pointers, one to the head of the 591541Srgrimes * list and the other to the tail of the list. The elements are doubly 601541Srgrimes * linked so that an arbitrary element can be removed without a need to 611541Srgrimes * traverse the list. New elements can be added to the list before or after 621541Srgrimes * an existing element, at the head of the list, or at the end of the list. 631541Srgrimes * A circle queue may be traversed in either direction, but has a more 641541Srgrimes * complex end of list detection. 651541Srgrimes * 661541Srgrimes * For details on the use of these macros, see the queue(3) manual page. 671541Srgrimes */ 681541Srgrimes 691541Srgrimes/* 701541Srgrimes * List definitions. 711541Srgrimes */ 721541Srgrimes#define LIST_HEAD(name, type) \ 731541Srgrimesstruct name { \ 741541Srgrimes struct type *lh_first; /* first element */ \ 751541Srgrimes} 761541Srgrimes 771541Srgrimes#define LIST_ENTRY(type) \ 781541Srgrimesstruct { \ 791541Srgrimes struct type *le_next; /* next element */ \ 801541Srgrimes struct type **le_prev; /* address of previous next element */ \ 811541Srgrimes} 821541Srgrimes 831541Srgrimes/* 841541Srgrimes * List functions. 851541Srgrimes */ 861541Srgrimes#define LIST_INIT(head) { \ 871541Srgrimes (head)->lh_first = NULL; \ 881541Srgrimes} 891541Srgrimes 901541Srgrimes#define LIST_INSERT_AFTER(listelm, elm, field) { \ 911541Srgrimes if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 921541Srgrimes (listelm)->field.le_next->field.le_prev = \ 931541Srgrimes &(elm)->field.le_next; \ 941541Srgrimes (listelm)->field.le_next = (elm); \ 951541Srgrimes (elm)->field.le_prev = &(listelm)->field.le_next; \ 961541Srgrimes} 971541Srgrimes 981541Srgrimes#define LIST_INSERT_HEAD(head, elm, field) { \ 991541Srgrimes if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 1001541Srgrimes (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 1011541Srgrimes (head)->lh_first = (elm); \ 1021541Srgrimes (elm)->field.le_prev = &(head)->lh_first; \ 1031541Srgrimes} 1041541Srgrimes 1051541Srgrimes#define LIST_REMOVE(elm, field) { \ 1061541Srgrimes if ((elm)->field.le_next != NULL) \ 1071541Srgrimes (elm)->field.le_next->field.le_prev = \ 1081541Srgrimes (elm)->field.le_prev; \ 1091541Srgrimes *(elm)->field.le_prev = (elm)->field.le_next; \ 1101541Srgrimes} 1111541Srgrimes 1121541Srgrimes/* 1131541Srgrimes * Tail queue definitions. 1141541Srgrimes */ 1151541Srgrimes#define TAILQ_HEAD(name, type) \ 1161541Srgrimesstruct name { \ 1171541Srgrimes struct type *tqh_first; /* first element */ \ 1181541Srgrimes struct type **tqh_last; /* addr of last next element */ \ 1191541Srgrimes} 1201541Srgrimes 1211541Srgrimes#define TAILQ_ENTRY(type) \ 1221541Srgrimesstruct { \ 1231541Srgrimes struct type *tqe_next; /* next element */ \ 1241541Srgrimes struct type **tqe_prev; /* address of previous next element */ \ 1251541Srgrimes} 1261541Srgrimes 1271541Srgrimes/* 1281541Srgrimes * Tail queue functions. 1291541Srgrimes */ 1301541Srgrimes#define TAILQ_INIT(head) { \ 1311541Srgrimes (head)->tqh_first = NULL; \ 1321541Srgrimes (head)->tqh_last = &(head)->tqh_first; \ 1331541Srgrimes} 1341541Srgrimes 1351541Srgrimes#define TAILQ_INSERT_HEAD(head, elm, field) { \ 1361541Srgrimes if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 1371541Srgrimes (elm)->field.tqe_next->field.tqe_prev = \ 1381541Srgrimes &(elm)->field.tqe_next; \ 1391541Srgrimes else \ 1401541Srgrimes (head)->tqh_last = &(elm)->field.tqe_next; \ 1411541Srgrimes (head)->tqh_first = (elm); \ 1421541Srgrimes (elm)->field.tqe_prev = &(head)->tqh_first; \ 1431541Srgrimes} 1441541Srgrimes 1451541Srgrimes#define TAILQ_INSERT_TAIL(head, elm, field) { \ 1461541Srgrimes (elm)->field.tqe_next = NULL; \ 1471541Srgrimes (elm)->field.tqe_prev = (head)->tqh_last; \ 1481541Srgrimes *(head)->tqh_last = (elm); \ 1491541Srgrimes (head)->tqh_last = &(elm)->field.tqe_next; \ 1501541Srgrimes} 1511541Srgrimes 1521541Srgrimes#define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \ 1531541Srgrimes if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 1541541Srgrimes (elm)->field.tqe_next->field.tqe_prev = \ 1551541Srgrimes &(elm)->field.tqe_next; \ 1561541Srgrimes else \ 1571541Srgrimes (head)->tqh_last = &(elm)->field.tqe_next; \ 1581541Srgrimes (listelm)->field.tqe_next = (elm); \ 1591541Srgrimes (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 1601541Srgrimes} 1611541Srgrimes 1621541Srgrimes#define TAILQ_REMOVE(head, elm, field) { \ 1631541Srgrimes if (((elm)->field.tqe_next) != NULL) \ 1641541Srgrimes (elm)->field.tqe_next->field.tqe_prev = \ 1651541Srgrimes (elm)->field.tqe_prev; \ 1661541Srgrimes else \ 1671541Srgrimes (head)->tqh_last = (elm)->field.tqe_prev; \ 1681541Srgrimes *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 1691541Srgrimes} 1701541Srgrimes 1711541Srgrimes/* 1721541Srgrimes * Circular queue definitions. 1731541Srgrimes */ 1741541Srgrimes#define CIRCLEQ_HEAD(name, type) \ 1751541Srgrimesstruct name { \ 1761541Srgrimes struct type *cqh_first; /* first element */ \ 1771541Srgrimes struct type *cqh_last; /* last element */ \ 1781541Srgrimes} 1791541Srgrimes 1801541Srgrimes#define CIRCLEQ_ENTRY(type) \ 1811541Srgrimesstruct { \ 1821541Srgrimes struct type *cqe_next; /* next element */ \ 1831541Srgrimes struct type *cqe_prev; /* previous element */ \ 1841541Srgrimes} 1851541Srgrimes 1861541Srgrimes/* 1871541Srgrimes * Circular queue functions. 1881541Srgrimes */ 1891541Srgrimes#define CIRCLEQ_INIT(head) { \ 1901541Srgrimes (head)->cqh_first = (void *)(head); \ 1911541Srgrimes (head)->cqh_last = (void *)(head); \ 1921541Srgrimes} 1931541Srgrimes 1941541Srgrimes#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \ 1951541Srgrimes (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 1961541Srgrimes (elm)->field.cqe_prev = (listelm); \ 1971541Srgrimes if ((listelm)->field.cqe_next == (void *)(head)) \ 1981541Srgrimes (head)->cqh_last = (elm); \ 1991541Srgrimes else \ 2001541Srgrimes (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 2011541Srgrimes (listelm)->field.cqe_next = (elm); \ 2021541Srgrimes} 2031541Srgrimes 2041541Srgrimes#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \ 2051541Srgrimes (elm)->field.cqe_next = (listelm); \ 2061541Srgrimes (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 2071541Srgrimes if ((listelm)->field.cqe_prev == (void *)(head)) \ 2081541Srgrimes (head)->cqh_first = (elm); \ 2091541Srgrimes else \ 2101541Srgrimes (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 2111541Srgrimes (listelm)->field.cqe_prev = (elm); \ 2121541Srgrimes} 2131541Srgrimes 2141541Srgrimes#define CIRCLEQ_INSERT_HEAD(head, elm, field) { \ 2151541Srgrimes (elm)->field.cqe_next = (head)->cqh_first; \ 2161541Srgrimes (elm)->field.cqe_prev = (void *)(head); \ 2171541Srgrimes if ((head)->cqh_last == (void *)(head)) \ 2181541Srgrimes (head)->cqh_last = (elm); \ 2191541Srgrimes else \ 2201541Srgrimes (head)->cqh_first->field.cqe_prev = (elm); \ 2211541Srgrimes (head)->cqh_first = (elm); \ 2221541Srgrimes} 2231541Srgrimes 2241541Srgrimes#define CIRCLEQ_INSERT_TAIL(head, elm, field) { \ 2251541Srgrimes (elm)->field.cqe_next = (void *)(head); \ 2261541Srgrimes (elm)->field.cqe_prev = (head)->cqh_last; \ 2271541Srgrimes if ((head)->cqh_first == (void *)(head)) \ 2281541Srgrimes (head)->cqh_first = (elm); \ 2291541Srgrimes else \ 2301541Srgrimes (head)->cqh_last->field.cqe_next = (elm); \ 2311541Srgrimes (head)->cqh_last = (elm); \ 2321541Srgrimes} 2331541Srgrimes 2341541Srgrimes#define CIRCLEQ_REMOVE(head, elm, field) { \ 2351541Srgrimes if ((elm)->field.cqe_next == (void *)(head)) \ 2361541Srgrimes (head)->cqh_last = (elm)->field.cqe_prev; \ 2371541Srgrimes else \ 2381541Srgrimes (elm)->field.cqe_next->field.cqe_prev = \ 2391541Srgrimes (elm)->field.cqe_prev; \ 2401541Srgrimes if ((elm)->field.cqe_prev == (void *)(head)) \ 2411541Srgrimes (head)->cqh_first = (elm)->field.cqe_next; \ 2421541Srgrimes else \ 2431541Srgrimes (elm)->field.cqe_prev->field.cqe_next = \ 2441541Srgrimes (elm)->field.cqe_next; \ 2451541Srgrimes} 2461541Srgrimes#endif /* !_SYS_QUEUE_H_ */ 247