17c478bd9Sstevel@tonic-gate /* BSDI $Id: queue.h,v 2.4 1996/07/02 13:22:11 bostic Exp $ */ 27c478bd9Sstevel@tonic-gate 3*2a8bcb4eSToomas Soome /* 47c478bd9Sstevel@tonic-gate * Copyright (c) 1991, 1993 57c478bd9Sstevel@tonic-gate * The Regents of the University of California. All rights reserved. 67c478bd9Sstevel@tonic-gate * 77c478bd9Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without 87c478bd9Sstevel@tonic-gate * modification, are permitted provided that the following conditions 97c478bd9Sstevel@tonic-gate * are met: 107c478bd9Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright 117c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer. 127c478bd9Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright 137c478bd9Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the 147c478bd9Sstevel@tonic-gate * documentation and/or other materials provided with the distribution. 157c478bd9Sstevel@tonic-gate * 3. All advertising materials mentioning features or use of this software 167c478bd9Sstevel@tonic-gate * must display the following acknowledgement: 177c478bd9Sstevel@tonic-gate * This product includes software developed by the University of 187c478bd9Sstevel@tonic-gate * California, Berkeley and its contributors. 197c478bd9Sstevel@tonic-gate * 4. Neither the name of the University nor the names of its contributors 207c478bd9Sstevel@tonic-gate * may be used to endorse or promote products derived from this software 217c478bd9Sstevel@tonic-gate * without specific prior written permission. 227c478bd9Sstevel@tonic-gate * 237c478bd9Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 247c478bd9Sstevel@tonic-gate * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 257c478bd9Sstevel@tonic-gate * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 267c478bd9Sstevel@tonic-gate * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 277c478bd9Sstevel@tonic-gate * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 287c478bd9Sstevel@tonic-gate * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 297c478bd9Sstevel@tonic-gate * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 307c478bd9Sstevel@tonic-gate * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 317c478bd9Sstevel@tonic-gate * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 327c478bd9Sstevel@tonic-gate * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 337c478bd9Sstevel@tonic-gate * SUCH DAMAGE. 347c478bd9Sstevel@tonic-gate * 357c478bd9Sstevel@tonic-gate * @(#)queue.h 8.5 (Berkeley) 8/20/94 367c478bd9Sstevel@tonic-gate * %W% (Sun) %G% 377c478bd9Sstevel@tonic-gate */ 387c478bd9Sstevel@tonic-gate /* 397c478bd9Sstevel@tonic-gate * Copyright (c) 1998 by Sun Microsystems, Inc. 407c478bd9Sstevel@tonic-gate * All rights reserved. 417c478bd9Sstevel@tonic-gate */ 427c478bd9Sstevel@tonic-gate 437c478bd9Sstevel@tonic-gate #ifndef _SYS_QUEUE_H_ 447c478bd9Sstevel@tonic-gate #define _SYS_QUEUE_H_ 457c478bd9Sstevel@tonic-gate 467c478bd9Sstevel@tonic-gate /* 477c478bd9Sstevel@tonic-gate * This file defines three types of data structures: lists, tail queues, 487c478bd9Sstevel@tonic-gate * and circular queues. 497c478bd9Sstevel@tonic-gate * 507c478bd9Sstevel@tonic-gate * A list is headed by a single forward pointer (or an array of forward 517c478bd9Sstevel@tonic-gate * pointers for a hash table header). The elements are doubly linked 527c478bd9Sstevel@tonic-gate * so that an arbitrary element can be removed without a need to 537c478bd9Sstevel@tonic-gate * traverse the list. New elements can be added to the list before 547c478bd9Sstevel@tonic-gate * or after an existing element or at the head of the list. A list 557c478bd9Sstevel@tonic-gate * may only be traversed in the forward direction. 567c478bd9Sstevel@tonic-gate * 577c478bd9Sstevel@tonic-gate * A tail queue is headed by a pair of pointers, one to the head of the 587c478bd9Sstevel@tonic-gate * list and the other to the tail of the list. The elements are doubly 597c478bd9Sstevel@tonic-gate * linked so that an arbitrary element can be removed without a need to 607c478bd9Sstevel@tonic-gate * traverse the list. New elements can be added to the list before or 617c478bd9Sstevel@tonic-gate * after an existing element, at the head of the list, or at the end of 627c478bd9Sstevel@tonic-gate * the list. A tail queue may only be traversed in the forward direction. 637c478bd9Sstevel@tonic-gate * 647c478bd9Sstevel@tonic-gate * A circle queue is headed by a pair of pointers, one to the head of the 657c478bd9Sstevel@tonic-gate * list and the other to the tail of the list. The elements are doubly 667c478bd9Sstevel@tonic-gate * linked so that an arbitrary element can be removed without a need to 677c478bd9Sstevel@tonic-gate * traverse the list. New elements can be added to the list before or after 687c478bd9Sstevel@tonic-gate * an existing element, at the head of the list, or at the end of the list. 697c478bd9Sstevel@tonic-gate * A circle queue may be traversed in either direction, but has a more 707c478bd9Sstevel@tonic-gate * complex end of list detection. 717c478bd9Sstevel@tonic-gate * 727c478bd9Sstevel@tonic-gate * For details on the use of these macros, see the queue(3) manual page. 737c478bd9Sstevel@tonic-gate */ 747c478bd9Sstevel@tonic-gate 757c478bd9Sstevel@tonic-gate /* 767c478bd9Sstevel@tonic-gate * List definitions. 777c478bd9Sstevel@tonic-gate */ 787c478bd9Sstevel@tonic-gate #define LIST_HEAD(name, type) \ 797c478bd9Sstevel@tonic-gate struct name { \ 807c478bd9Sstevel@tonic-gate struct type *lh_first; /* first element */ \ 817c478bd9Sstevel@tonic-gate } 827c478bd9Sstevel@tonic-gate 837c478bd9Sstevel@tonic-gate #define LIST_ENTRY(type) \ 847c478bd9Sstevel@tonic-gate struct { \ 857c478bd9Sstevel@tonic-gate struct type *le_next; /* next element */ \ 867c478bd9Sstevel@tonic-gate struct type **le_prev; /* address of previous next element */ \ 877c478bd9Sstevel@tonic-gate } 887c478bd9Sstevel@tonic-gate 897c478bd9Sstevel@tonic-gate #define LIST_FIRST(head) ((head)->lh_first) 907c478bd9Sstevel@tonic-gate #define LIST_NEXT(elm, field) ((elm)->field.le_next) 917c478bd9Sstevel@tonic-gate #define LIST_END(head) NULL 927c478bd9Sstevel@tonic-gate 937c478bd9Sstevel@tonic-gate /* 947c478bd9Sstevel@tonic-gate * List functions. 957c478bd9Sstevel@tonic-gate */ 967c478bd9Sstevel@tonic-gate #define LIST_INIT(head) { \ 977c478bd9Sstevel@tonic-gate (head)->lh_first = NULL; \ 987c478bd9Sstevel@tonic-gate } 997c478bd9Sstevel@tonic-gate 1007c478bd9Sstevel@tonic-gate #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 1017c478bd9Sstevel@tonic-gate if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 1027c478bd9Sstevel@tonic-gate (listelm)->field.le_next->field.le_prev = \ 1037c478bd9Sstevel@tonic-gate &(elm)->field.le_next; \ 1047c478bd9Sstevel@tonic-gate (listelm)->field.le_next = (elm); \ 1057c478bd9Sstevel@tonic-gate (elm)->field.le_prev = &(listelm)->field.le_next; \ 1067c478bd9Sstevel@tonic-gate } while (0) 1077c478bd9Sstevel@tonic-gate 1087c478bd9Sstevel@tonic-gate #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 1097c478bd9Sstevel@tonic-gate (elm)->field.le_prev = (listelm)->field.le_prev; \ 1107c478bd9Sstevel@tonic-gate (elm)->field.le_next = (listelm); \ 1117c478bd9Sstevel@tonic-gate *(listelm)->field.le_prev = (elm); \ 1127c478bd9Sstevel@tonic-gate (listelm)->field.le_prev = &(elm)->field.le_next; \ 1137c478bd9Sstevel@tonic-gate } while (0) 1147c478bd9Sstevel@tonic-gate 1157c478bd9Sstevel@tonic-gate #define LIST_INSERT_HEAD(head, elm, field) do { \ 1167c478bd9Sstevel@tonic-gate if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 1177c478bd9Sstevel@tonic-gate (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 1187c478bd9Sstevel@tonic-gate (head)->lh_first = (elm); \ 1197c478bd9Sstevel@tonic-gate (elm)->field.le_prev = &(head)->lh_first; \ 1207c478bd9Sstevel@tonic-gate } while (0) 1217c478bd9Sstevel@tonic-gate 1227c478bd9Sstevel@tonic-gate #define LIST_REMOVE(elm, field) do { \ 1237c478bd9Sstevel@tonic-gate if ((elm)->field.le_next != NULL) \ 1247c478bd9Sstevel@tonic-gate (elm)->field.le_next->field.le_prev = \ 1257c478bd9Sstevel@tonic-gate (elm)->field.le_prev; \ 1267c478bd9Sstevel@tonic-gate *(elm)->field.le_prev = (elm)->field.le_next; \ 1277c478bd9Sstevel@tonic-gate } while (0) 1287c478bd9Sstevel@tonic-gate 1297c478bd9Sstevel@tonic-gate /* 1307c478bd9Sstevel@tonic-gate * Tail queue definitions. 1317c478bd9Sstevel@tonic-gate */ 1327c478bd9Sstevel@tonic-gate #define TAILQ_HEAD(name, type) \ 1337c478bd9Sstevel@tonic-gate struct name { \ 1347c478bd9Sstevel@tonic-gate struct type *tqh_first; /* first element */ \ 1357c478bd9Sstevel@tonic-gate struct type **tqh_last; /* addr of last next element */ \ 1367c478bd9Sstevel@tonic-gate } 1377c478bd9Sstevel@tonic-gate 1387c478bd9Sstevel@tonic-gate #define TAILQ_ENTRY(type) \ 1397c478bd9Sstevel@tonic-gate struct { \ 1407c478bd9Sstevel@tonic-gate struct type *tqe_next; /* next element */ \ 1417c478bd9Sstevel@tonic-gate struct type **tqe_prev; /* address of previous next element */ \ 1427c478bd9Sstevel@tonic-gate } 1437c478bd9Sstevel@tonic-gate 1447c478bd9Sstevel@tonic-gate #define TAILQ_FIRST(head) ((head)->tqh_first) 1457c478bd9Sstevel@tonic-gate #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 1467c478bd9Sstevel@tonic-gate #define TAILQ_END(head) NULL 1477c478bd9Sstevel@tonic-gate 1487c478bd9Sstevel@tonic-gate /* 1497c478bd9Sstevel@tonic-gate * Tail queue functions. 1507c478bd9Sstevel@tonic-gate */ 1517c478bd9Sstevel@tonic-gate #define TAILQ_INIT(head) do { \ 1527c478bd9Sstevel@tonic-gate (head)->tqh_first = NULL; \ 1537c478bd9Sstevel@tonic-gate (head)->tqh_last = &(head)->tqh_first; \ 1547c478bd9Sstevel@tonic-gate } while (0) 1557c478bd9Sstevel@tonic-gate 1567c478bd9Sstevel@tonic-gate #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 1577c478bd9Sstevel@tonic-gate if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 1587c478bd9Sstevel@tonic-gate (head)->tqh_first->field.tqe_prev = \ 1597c478bd9Sstevel@tonic-gate &(elm)->field.tqe_next; \ 1607c478bd9Sstevel@tonic-gate else \ 1617c478bd9Sstevel@tonic-gate (head)->tqh_last = &(elm)->field.tqe_next; \ 1627c478bd9Sstevel@tonic-gate (head)->tqh_first = (elm); \ 1637c478bd9Sstevel@tonic-gate (elm)->field.tqe_prev = &(head)->tqh_first; \ 1647c478bd9Sstevel@tonic-gate } while (0) 1657c478bd9Sstevel@tonic-gate 1667c478bd9Sstevel@tonic-gate #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 1677c478bd9Sstevel@tonic-gate (elm)->field.tqe_next = NULL; \ 1687c478bd9Sstevel@tonic-gate (elm)->field.tqe_prev = (head)->tqh_last; \ 1697c478bd9Sstevel@tonic-gate *(head)->tqh_last = (elm); \ 1707c478bd9Sstevel@tonic-gate (head)->tqh_last = &(elm)->field.tqe_next; \ 1717c478bd9Sstevel@tonic-gate } while (0) 1727c478bd9Sstevel@tonic-gate 1737c478bd9Sstevel@tonic-gate #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 1747c478bd9Sstevel@tonic-gate if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 1757c478bd9Sstevel@tonic-gate (elm)->field.tqe_next->field.tqe_prev = \ 1767c478bd9Sstevel@tonic-gate &(elm)->field.tqe_next; \ 1777c478bd9Sstevel@tonic-gate else \ 1787c478bd9Sstevel@tonic-gate (head)->tqh_last = &(elm)->field.tqe_next; \ 1797c478bd9Sstevel@tonic-gate (listelm)->field.tqe_next = (elm); \ 1807c478bd9Sstevel@tonic-gate (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 1817c478bd9Sstevel@tonic-gate } while (0) 1827c478bd9Sstevel@tonic-gate 1837c478bd9Sstevel@tonic-gate #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 1847c478bd9Sstevel@tonic-gate (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 1857c478bd9Sstevel@tonic-gate (elm)->field.tqe_next = (listelm); \ 1867c478bd9Sstevel@tonic-gate *(listelm)->field.tqe_prev = (elm); \ 1877c478bd9Sstevel@tonic-gate (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 1887c478bd9Sstevel@tonic-gate } while (0) 1897c478bd9Sstevel@tonic-gate 1907c478bd9Sstevel@tonic-gate #define TAILQ_REMOVE(head, elm, field) do { \ 1917c478bd9Sstevel@tonic-gate if (((elm)->field.tqe_next) != NULL) \ 1927c478bd9Sstevel@tonic-gate (elm)->field.tqe_next->field.tqe_prev = \ 1937c478bd9Sstevel@tonic-gate (elm)->field.tqe_prev; \ 1947c478bd9Sstevel@tonic-gate else \ 1957c478bd9Sstevel@tonic-gate (head)->tqh_last = (elm)->field.tqe_prev; \ 1967c478bd9Sstevel@tonic-gate *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 1977c478bd9Sstevel@tonic-gate } while (0) 1987c478bd9Sstevel@tonic-gate 1997c478bd9Sstevel@tonic-gate /* 2007c478bd9Sstevel@tonic-gate * Circular queue definitions. 2017c478bd9Sstevel@tonic-gate */ 2027c478bd9Sstevel@tonic-gate #define CIRCLEQ_HEAD(name, type) \ 2037c478bd9Sstevel@tonic-gate struct name { \ 2047c478bd9Sstevel@tonic-gate struct type *cqh_first; /* first element */ \ 2057c478bd9Sstevel@tonic-gate struct type *cqh_last; /* last element */ \ 2067c478bd9Sstevel@tonic-gate } 2077c478bd9Sstevel@tonic-gate 2087c478bd9Sstevel@tonic-gate #define CIRCLEQ_ENTRY(type) \ 2097c478bd9Sstevel@tonic-gate struct { \ 2107c478bd9Sstevel@tonic-gate struct type *cqe_next; /* next element */ \ 2117c478bd9Sstevel@tonic-gate struct type *cqe_prev; /* previous element */ \ 2127c478bd9Sstevel@tonic-gate } 2137c478bd9Sstevel@tonic-gate 2147c478bd9Sstevel@tonic-gate #define CIRCLEQ_FIRST(head) ((head)->cqh_first) 2157c478bd9Sstevel@tonic-gate #define CIRCLEQ_LAST(head) ((head)->cqh_last) 2167c478bd9Sstevel@tonic-gate #define CIRCLEQ_END(head) ((void *)(head)) 2177c478bd9Sstevel@tonic-gate #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 2187c478bd9Sstevel@tonic-gate #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 2197c478bd9Sstevel@tonic-gate 2207c478bd9Sstevel@tonic-gate /* 2217c478bd9Sstevel@tonic-gate * Circular queue functions. 2227c478bd9Sstevel@tonic-gate */ 2237c478bd9Sstevel@tonic-gate #define CIRCLEQ_INIT(head) do { \ 2247c478bd9Sstevel@tonic-gate (head)->cqh_first = (void *)(head); \ 2257c478bd9Sstevel@tonic-gate (head)->cqh_last = (void *)(head); \ 2267c478bd9Sstevel@tonic-gate } while (0) 2277c478bd9Sstevel@tonic-gate 2287c478bd9Sstevel@tonic-gate #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 2297c478bd9Sstevel@tonic-gate (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 2307c478bd9Sstevel@tonic-gate (elm)->field.cqe_prev = (listelm); \ 2317c478bd9Sstevel@tonic-gate if ((listelm)->field.cqe_next == (void *)(head)) \ 2327c478bd9Sstevel@tonic-gate (head)->cqh_last = (elm); \ 2337c478bd9Sstevel@tonic-gate else \ 2347c478bd9Sstevel@tonic-gate (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 2357c478bd9Sstevel@tonic-gate (listelm)->field.cqe_next = (elm); \ 2367c478bd9Sstevel@tonic-gate } while (0) 2377c478bd9Sstevel@tonic-gate 2387c478bd9Sstevel@tonic-gate #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 2397c478bd9Sstevel@tonic-gate (elm)->field.cqe_next = (listelm); \ 2407c478bd9Sstevel@tonic-gate (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 2417c478bd9Sstevel@tonic-gate if ((listelm)->field.cqe_prev == (void *)(head)) \ 2427c478bd9Sstevel@tonic-gate (head)->cqh_first = (elm); \ 2437c478bd9Sstevel@tonic-gate else \ 2447c478bd9Sstevel@tonic-gate (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 2457c478bd9Sstevel@tonic-gate (listelm)->field.cqe_prev = (elm); \ 2467c478bd9Sstevel@tonic-gate } while (0) 2477c478bd9Sstevel@tonic-gate 2487c478bd9Sstevel@tonic-gate #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 2497c478bd9Sstevel@tonic-gate (elm)->field.cqe_next = (head)->cqh_first; \ 2507c478bd9Sstevel@tonic-gate (elm)->field.cqe_prev = (void *)(head); \ 2517c478bd9Sstevel@tonic-gate if ((head)->cqh_last == (void *)(head)) \ 2527c478bd9Sstevel@tonic-gate (head)->cqh_last = (elm); \ 2537c478bd9Sstevel@tonic-gate else \ 2547c478bd9Sstevel@tonic-gate (head)->cqh_first->field.cqe_prev = (elm); \ 2557c478bd9Sstevel@tonic-gate (head)->cqh_first = (elm); \ 2567c478bd9Sstevel@tonic-gate } while (0) 2577c478bd9Sstevel@tonic-gate 2587c478bd9Sstevel@tonic-gate #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 2597c478bd9Sstevel@tonic-gate (elm)->field.cqe_next = (void *)(head); \ 2607c478bd9Sstevel@tonic-gate (elm)->field.cqe_prev = (head)->cqh_last; \ 2617c478bd9Sstevel@tonic-gate if ((head)->cqh_first == (void *)(head)) \ 2627c478bd9Sstevel@tonic-gate (head)->cqh_first = (elm); \ 2637c478bd9Sstevel@tonic-gate else \ 2647c478bd9Sstevel@tonic-gate (head)->cqh_last->field.cqe_next = (elm); \ 2657c478bd9Sstevel@tonic-gate (head)->cqh_last = (elm); \ 2667c478bd9Sstevel@tonic-gate } while (0) 2677c478bd9Sstevel@tonic-gate 2687c478bd9Sstevel@tonic-gate #define CIRCLEQ_REMOVE(head, elm, field) do { \ 2697c478bd9Sstevel@tonic-gate if ((elm)->field.cqe_next == (void *)(head)) \ 2707c478bd9Sstevel@tonic-gate (head)->cqh_last = (elm)->field.cqe_prev; \ 2717c478bd9Sstevel@tonic-gate else \ 2727c478bd9Sstevel@tonic-gate (elm)->field.cqe_next->field.cqe_prev = \ 2737c478bd9Sstevel@tonic-gate (elm)->field.cqe_prev; \ 2747c478bd9Sstevel@tonic-gate if ((elm)->field.cqe_prev == (void *)(head)) \ 2757c478bd9Sstevel@tonic-gate (head)->cqh_first = (elm)->field.cqe_next; \ 2767c478bd9Sstevel@tonic-gate else \ 2777c478bd9Sstevel@tonic-gate (elm)->field.cqe_prev->field.cqe_next = \ 2787c478bd9Sstevel@tonic-gate (elm)->field.cqe_next; \ 2797c478bd9Sstevel@tonic-gate } while (0) 2807c478bd9Sstevel@tonic-gate #endif /* !_SYS_QUEUE_H_ */ 281