queue.h revision 70469
178556Sobrien/* 278556Sobrien * Copyright (c) 1991, 1993 378556Sobrien * The Regents of the University of California. All rights reserved. 478556Sobrien * 578556Sobrien * Redistribution and use in source and binary forms, with or without 678556Sobrien * modification, are permitted provided that the following conditions 7167974Sdelphij * are met: 8167974Sdelphij * 1. Redistributions of source code must retain the above copyright 9167974Sdelphij * notice, this list of conditions and the following disclaimer. 1078556Sobrien * 2. Redistributions in binary form must reproduce the above copyright 11215041Sobrien * notice, this list of conditions and the following disclaimer in the 12215041Sobrien * documentation and/or other materials provided with the distribution. 1378556Sobrien * 3. All advertising materials mentioning features or use of this software 14167974Sdelphij * must display the following acknowledgement: 15167974Sdelphij * This product includes software developed by the University of 1678556Sobrien * California, Berkeley and its contributors. 17167974Sdelphij * 4. Neither the name of the University nor the names of its contributors 18167974Sdelphij * may be used to endorse or promote products derived from this software 19167974Sdelphij * without specific prior written permission. 2078556Sobrien * 2178556Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2278556Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2378556Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2478556Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2578556Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2678556Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2778556Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2878556Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2978556Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3078556Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3178556Sobrien * SUCH DAMAGE. 3278556Sobrien * 3378556Sobrien * @(#)queue.h 8.5 (Berkeley) 8/20/94 3478556Sobrien * $FreeBSD: head/sys/sys/queue.h 70469 2000-12-29 09:55:40Z phk $ 3578556Sobrien */ 3678556Sobrien 3778556Sobrien#ifndef _SYS_QUEUE_H_ 3878556Sobrien#define _SYS_QUEUE_H_ 3978556Sobrien 4078556Sobrien#include <machine/ansi.h> /* for __offsetof */ 4178556Sobrien 4278556Sobrien/* 4378556Sobrien * This file defines five types of data structures: singly-linked lists, 4478556Sobrien * singly-linked tail queues, lists, tail queues, and circular queues. 4578556Sobrien * 4678556Sobrien * A singly-linked list is headed by a single forward pointer. The elements 4778556Sobrien * are singly linked for minimum space and pointer manipulation overhead at 4878556Sobrien * the expense of O(n) removal for arbitrary elements. New elements can be 4978556Sobrien * added to the list after an existing element or at the head of the list. 5078556Sobrien * Elements being removed from the head of the list should use the explicit 5178556Sobrien * macro for this purpose for optimum efficiency. A singly-linked list may 5278556Sobrien * only be traversed in the forward direction. Singly-linked lists are ideal 5378556Sobrien * for applications with large datasets and few or no removals or for 5478556Sobrien * implementing a LIFO queue. 5578556Sobrien * 5678556Sobrien * A singly-linked tail queue is headed by a pair of pointers, one to the 5778556Sobrien * head of the list and the other to the tail of the list. The elements are 5878556Sobrien * singly linked for minimum space and pointer manipulation overhead at the 5978556Sobrien * expense of O(n) removal for arbitrary elements. New elements can be added 6078556Sobrien * to the list after an existing element, at the head of the list, or at the 6178556Sobrien * end of the list. Elements being removed from the head of the tail queue 6278556Sobrien * should use the explicit macro for this purpose for optimum efficiency. 6378556Sobrien * A singly-linked tail queue may only be traversed in the forward direction. 6478556Sobrien * Singly-linked tail queues are ideal for applications with large datasets 6578556Sobrien * and few or no removals or for implementing a FIFO queue. 6678556Sobrien * 6778556Sobrien * A list is headed by a single forward pointer (or an array of forward 6878556Sobrien * pointers for a hash table header). The elements are doubly linked 6978556Sobrien * so that an arbitrary element can be removed without a need to 7078556Sobrien * traverse the list. New elements can be added to the list before 7178556Sobrien * or after an existing element or at the head of the list. A list 7278556Sobrien * may only be traversed in the forward direction. 7378556Sobrien * 7478556Sobrien * A tail queue is headed by a pair of pointers, one to the head of the 7578556Sobrien * list and the other to the tail of the list. The elements are doubly 7678556Sobrien * linked so that an arbitrary element can be removed without a need to 7778556Sobrien * traverse the list. New elements can be added to the list before or 7878556Sobrien * after an existing element, at the head of the list, or at the end of 7978556Sobrien * the list. A tail queue may be traversed in either direction. 8078556Sobrien * 8178556Sobrien * For details on the use of these macros, see the queue(3) manual page. 8278556Sobrien * 8378556Sobrien * 8478556Sobrien * SLIST LIST STAILQ TAILQ 8578556Sobrien * _HEAD + + + + 8678556Sobrien * _HEAD_INITIALIZER + + + + 8778556Sobrien * _ENTRY + + + + 8878556Sobrien * _INIT + + + + 8978556Sobrien * _EMPTY + + + + 9078556Sobrien * _FIRST + + + + 9178556Sobrien * _NEXT + + + + 9278556Sobrien * _PREV - - - + 9378556Sobrien * _LAST - - + + 9478556Sobrien * _FOREACH + + + + 9578556Sobrien * _FOREACH_REVERSE - - - + 9678556Sobrien * _INSERT_HEAD + + + + 9778556Sobrien * _INSERT_BEFORE - + - + 9878556Sobrien * _INSERT_AFTER + + + + 9978556Sobrien * _INSERT_TAIL - - + + 10078556Sobrien * _REMOVE_HEAD + - + - 10178556Sobrien * _REMOVE + + + + 10278556Sobrien * 10378556Sobrien */ 10478556Sobrien 10578556Sobrien/* 10678556Sobrien * Singly-linked List declarations. 10778556Sobrien */ 10878556Sobrien#define SLIST_HEAD(name, type) \ 10978556Sobrienstruct name { \ 11078556Sobrien struct type *slh_first; /* first element */ \ 11178556Sobrien} 11278556Sobrien 11378556Sobrien#define SLIST_HEAD_INITIALIZER(head) \ 11478556Sobrien { NULL } 11578556Sobrien 11678556Sobrien#define SLIST_ENTRY(type) \ 11778556Sobrienstruct { \ 11878556Sobrien struct type *sle_next; /* next element */ \ 11978556Sobrien} 12078556Sobrien 12178556Sobrien/* 12278556Sobrien * Singly-linked List functions. 12378556Sobrien */ 12478556Sobrien#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 12578556Sobrien 12678556Sobrien#define SLIST_FIRST(head) ((head)->slh_first) 12778556Sobrien 12878556Sobrien#define SLIST_FOREACH(var, head, field) \ 12978556Sobrien for ((var) = SLIST_FIRST((head)); \ 13078556Sobrien (var); \ 13178556Sobrien (var) = SLIST_NEXT((var), field)) 13278556Sobrien 13378556Sobrien#define SLIST_INIT(head) do { \ 13478556Sobrien SLIST_FIRST((head)) = NULL; \ 13578556Sobrien} while (0) 13678556Sobrien 13778556Sobrien#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 13878556Sobrien SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 13978556Sobrien SLIST_NEXT((slistelm), field) = (elm); \ 14078556Sobrien} while (0) 14178556Sobrien 14278556Sobrien#define SLIST_INSERT_HEAD(head, elm, field) do { \ 14378556Sobrien SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 14478556Sobrien SLIST_FIRST((head)) = (elm); \ 14578556Sobrien} while (0) 14678556Sobrien 14778556Sobrien#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 14878556Sobrien 14978556Sobrien#define SLIST_REMOVE(head, elm, type, field) do { \ 15078556Sobrien if (SLIST_FIRST((head)) == (elm)) { \ 15178556Sobrien SLIST_REMOVE_HEAD((head), field); \ 15278556Sobrien } \ 15378556Sobrien else { \ 15478556Sobrien struct type *curelm = SLIST_FIRST((head)); \ 15578556Sobrien while (SLIST_NEXT(curelm, field) != (elm)) \ 15678556Sobrien curelm = SLIST_NEXT(curelm, field); \ 15778556Sobrien SLIST_NEXT(curelm, field) = \ 15878556Sobrien SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 15978556Sobrien } \ 16078556Sobrien} while (0) 16178556Sobrien 16278556Sobrien#define SLIST_REMOVE_HEAD(head, field) do { \ 16378556Sobrien SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 16478556Sobrien} while (0) 16578556Sobrien 16678556Sobrien/* 16778556Sobrien * Singly-linked Tail queue declarations. 16878556Sobrien */ 16978556Sobrien#define STAILQ_HEAD(name, type) \ 17078556Sobrienstruct name { \ 17178556Sobrien struct type *stqh_first;/* first element */ \ 17278556Sobrien struct type **stqh_last;/* addr of last next element */ \ 17378556Sobrien} 17478556Sobrien 17578556Sobrien#define STAILQ_HEAD_INITIALIZER(head) \ 17678556Sobrien { NULL, &(head).stqh_first } 17778556Sobrien 17878556Sobrien#define STAILQ_ENTRY(type) \ 17978556Sobrienstruct { \ 18078556Sobrien struct type *stqe_next; /* next element */ \ 18178556Sobrien} 18278556Sobrien 18378556Sobrien/* 18478556Sobrien * Singly-linked Tail queue functions. 18578556Sobrien */ 18678556Sobrien#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 18778556Sobrien 18878556Sobrien#define STAILQ_FIRST(head) ((head)->stqh_first) 18978556Sobrien 19078556Sobrien#define STAILQ_FOREACH(var, head, field) \ 19178556Sobrien for((var) = STAILQ_FIRST((head)); \ 19278556Sobrien (var); \ 19378556Sobrien (var) = STAILQ_NEXT((var), field)) 19478556Sobrien 19578556Sobrien#define STAILQ_INIT(head) do { \ 19678556Sobrien STAILQ_FIRST((head)) = NULL; \ 19778556Sobrien (head)->stqh_last = &STAILQ_FIRST((head)); \ 19890067Ssobomax} while (0) 19978556Sobrien 20078556Sobrien#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 20190067Ssobomax if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 20278556Sobrien (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 20378556Sobrien STAILQ_NEXT((tqelm), field) = (elm); \ 20490067Ssobomax} while (0) 20578556Sobrien 20678556Sobrien#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 20790067Ssobomax if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 20890067Ssobomax (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 20990067Ssobomax STAILQ_FIRST((head)) = (elm); \ 21078556Sobrien} while (0) 21178556Sobrien 21278556Sobrien#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 21378556Sobrien STAILQ_NEXT((elm), field) = NULL; \ 21478556Sobrien *(head)->stqh_last = (elm); \ 21578556Sobrien (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 21678556Sobrien} while (0) 21778556Sobrien 21878556Sobrien#define STAILQ_LAST(head, type, field) \ 21978556Sobrien (STAILQ_EMPTY(head) ? \ 22078556Sobrien NULL : \ 22178556Sobrien ((struct type *) \ 22278556Sobrien ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 22378556Sobrien 22478556Sobrien#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 22578556Sobrien 22678556Sobrien#define STAILQ_REMOVE(head, elm, type, field) do { \ 22778556Sobrien if (STAILQ_FIRST((head)) == (elm)) { \ 22878556Sobrien STAILQ_REMOVE_HEAD(head, field); \ 22978556Sobrien } \ 23078556Sobrien else { \ 23178556Sobrien struct type *curelm = STAILQ_FIRST((head)); \ 23278556Sobrien while (STAILQ_NEXT(curelm, field) != (elm)) \ 23378556Sobrien curelm = STAILQ_NEXT(curelm, field); \ 23478556Sobrien if ((STAILQ_NEXT(curelm, field) = \ 23578556Sobrien STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 23678556Sobrien (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 23778556Sobrien } \ 23878556Sobrien} while (0) 23978556Sobrien 24078556Sobrien#define STAILQ_REMOVE_HEAD(head, field) do { \ 24178556Sobrien if ((STAILQ_FIRST((head)) = \ 24278556Sobrien STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 24378556Sobrien (head)->stqh_last = &STAILQ_FIRST((head)); \ 24478556Sobrien} while (0) 24578556Sobrien 24678556Sobrien#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 24778556Sobrien if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ 24878556Sobrien (head)->stqh_last = &STAILQ_FIRST((head)); \ 24978556Sobrien} while (0) 25078556Sobrien 25178556Sobrien/* 25278556Sobrien * List declarations. 25378556Sobrien */ 25478556Sobrien#define LIST_HEAD(name, type) \ 25578556Sobrienstruct name { \ 25678556Sobrien struct type *lh_first; /* first element */ \ 25778556Sobrien} 25878556Sobrien 25978556Sobrien#define LIST_HEAD_INITIALIZER(head) \ 26078556Sobrien { NULL } 26178556Sobrien 26278556Sobrien#define LIST_ENTRY(type) \ 26378556Sobrienstruct { \ 26478556Sobrien struct type *le_next; /* next element */ \ 26578556Sobrien struct type **le_prev; /* address of previous next element */ \ 26678556Sobrien} 26778556Sobrien 26878556Sobrien/* 26978556Sobrien * List functions. 27078556Sobrien */ 27178556Sobrien 27278556Sobrien#define LIST_EMPTY(head) ((head)->lh_first == NULL) 27378556Sobrien 27478556Sobrien#define LIST_FIRST(head) ((head)->lh_first) 27578556Sobrien 27678556Sobrien#define LIST_FOREACH(var, head, field) \ 27778556Sobrien for ((var) = LIST_FIRST((head)); \ 27878556Sobrien (var); \ 27978556Sobrien (var) = LIST_NEXT((var), field)) 28078556Sobrien 28178556Sobrien#define LIST_INIT(head) do { \ 28278556Sobrien LIST_FIRST((head)) = NULL; \ 28378556Sobrien} while (0) 28478556Sobrien 28578556Sobrien#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 28678556Sobrien if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 28778556Sobrien LIST_NEXT((listelm), field)->field.le_prev = \ 28878556Sobrien &LIST_NEXT((elm), field); \ 28978556Sobrien LIST_NEXT((listelm), field) = (elm); \ 29078556Sobrien (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 29178556Sobrien} while (0) 29278556Sobrien 29378556Sobrien#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 29478556Sobrien (elm)->field.le_prev = (listelm)->field.le_prev; \ 29578556Sobrien LIST_NEXT((elm), field) = (listelm); \ 29678556Sobrien *(listelm)->field.le_prev = (elm); \ 29778556Sobrien (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 29878556Sobrien} while (0) 29978556Sobrien 30078556Sobrien#define LIST_INSERT_HEAD(head, elm, field) do { \ 30178556Sobrien if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 30278556Sobrien LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 30378556Sobrien LIST_FIRST((head)) = (elm); \ 30478556Sobrien (elm)->field.le_prev = &LIST_FIRST((head)); \ 30578556Sobrien} while (0) 30678556Sobrien 30778556Sobrien#define LIST_NEXT(elm, field) ((elm)->field.le_next) 30878556Sobrien 30978556Sobrien#define LIST_REMOVE(elm, field) do { \ 31078556Sobrien if (LIST_NEXT((elm), field) != NULL) \ 31178556Sobrien LIST_NEXT((elm), field)->field.le_prev = \ 31278556Sobrien (elm)->field.le_prev; \ 31378556Sobrien *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 31478556Sobrien} while (0) 31578556Sobrien 31678556Sobrien/* 31778556Sobrien * Tail queue declarations. 31878556Sobrien */ 31978556Sobrien#define TAILQ_HEAD(name, type) \ 32078556Sobrienstruct name { \ 32178556Sobrien struct type *tqh_first; /* first element */ \ 32278556Sobrien struct type **tqh_last; /* addr of last next element */ \ 32378556Sobrien} 32478556Sobrien 32578556Sobrien#define TAILQ_HEAD_INITIALIZER(head) \ 32678556Sobrien { NULL, &(head).tqh_first } 32778556Sobrien 32878556Sobrien#define TAILQ_ENTRY(type) \ 32978556Sobrienstruct { \ 33078556Sobrien struct type *tqe_next; /* next element */ \ 33178556Sobrien struct type **tqe_prev; /* address of previous next element */ \ 33278556Sobrien} 33378556Sobrien 33478556Sobrien/* 33578556Sobrien * Tail queue functions. 33678556Sobrien */ 33778556Sobrien#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 33878556Sobrien 33978556Sobrien#define TAILQ_FIRST(head) ((head)->tqh_first) 34078556Sobrien 34178556Sobrien#define TAILQ_FOREACH(var, head, field) \ 34278556Sobrien for ((var) = TAILQ_FIRST((head)); \ 34378556Sobrien (var); \ 34478556Sobrien (var) = TAILQ_NEXT((var), field)) 34578556Sobrien 34678556Sobrien#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 34778556Sobrien for ((var) = TAILQ_LAST((head), headname); \ 34878556Sobrien (var); \ 34978556Sobrien (var) = TAILQ_PREV((var), headname, field)) 35078556Sobrien 35178556Sobrien#define TAILQ_INIT(head) do { \ 35278556Sobrien TAILQ_FIRST((head)) = NULL; \ 35378556Sobrien (head)->tqh_last = &TAILQ_FIRST((head)); \ 35478556Sobrien} while (0) 35578556Sobrien 35678556Sobrien#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 35778556Sobrien if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 35878556Sobrien TAILQ_NEXT((elm), field)->field.tqe_prev = \ 35978556Sobrien &TAILQ_NEXT((elm), field); \ 36078556Sobrien else \ 36178556Sobrien (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 36278556Sobrien TAILQ_NEXT((listelm), field) = (elm); \ 36378556Sobrien (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 36478556Sobrien} while (0) 36578556Sobrien 36678556Sobrien#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 36778556Sobrien (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 36878556Sobrien TAILQ_NEXT((elm), field) = (listelm); \ 36978556Sobrien *(listelm)->field.tqe_prev = (elm); \ 37078556Sobrien (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 37178556Sobrien} while (0) 37278556Sobrien 37378556Sobrien#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 37478556Sobrien if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 37578556Sobrien TAILQ_FIRST((head))->field.tqe_prev = \ 37678556Sobrien &TAILQ_NEXT((elm), field); \ 37778556Sobrien else \ 37878556Sobrien (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 37978556Sobrien TAILQ_FIRST((head)) = (elm); \ 38078556Sobrien (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 38178556Sobrien} while (0) 38278556Sobrien 38378556Sobrien#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 384212901Scperciva TAILQ_NEXT((elm), field) = NULL; \ 385212901Scperciva (elm)->field.tqe_prev = (head)->tqh_last; \ 386212901Scperciva *(head)->tqh_last = (elm); \ 387212901Scperciva (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 388212901Scperciva} while (0) 389212901Scperciva 390212901Scperciva#define TAILQ_LAST(head, headname) \ 39178556Sobrien (*(((struct headname *)((head)->tqh_last))->tqh_last)) 39278556Sobrien 39378556Sobrien#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 39478556Sobrien 39578556Sobrien#define TAILQ_PREV(elm, headname, field) \ 39678556Sobrien (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 39778556Sobrien 39878556Sobrien#define TAILQ_REMOVE(head, elm, field) do { \ 39978556Sobrien if ((TAILQ_NEXT((elm), field)) != NULL) \ 40078556Sobrien TAILQ_NEXT((elm), field)->field.tqe_prev = \ 40178556Sobrien (elm)->field.tqe_prev; \ 40278556Sobrien else \ 40378556Sobrien (head)->tqh_last = (elm)->field.tqe_prev; \ 40478556Sobrien *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 40578556Sobrien} while (0) 40678556Sobrien 40778556Sobrien 40878556Sobrien#ifdef _KERNEL 40978556Sobrien 41078556Sobrien/* 41178556Sobrien * XXX insque() and remque() are an old way of handling certain queues. 41278556Sobrien * They bogusly assumes that all queue heads look alike. 41378556Sobrien */ 41478556Sobrien 41578556Sobrienstruct quehead { 41678556Sobrien struct quehead *qh_link; 41778556Sobrien struct quehead *qh_rlink; 41878556Sobrien}; 41978556Sobrien 42078556Sobrien#ifdef __GNUC__ 42178556Sobrien 42278556Sobrienstatic __inline void 42378556Sobrieninsque(void *a, void *b) 42478556Sobrien{ 42578556Sobrien struct quehead *element = a, *head = b; 42678556Sobrien 42778556Sobrien element->qh_link = head->qh_link; 42878556Sobrien element->qh_rlink = head; 42978556Sobrien head->qh_link = element; 43078556Sobrien element->qh_link->qh_rlink = element; 43178556Sobrien} 43278556Sobrien 43378556Sobrienstatic __inline void 43478556Sobrienremque(void *a) 43578556Sobrien{ 43678556Sobrien struct quehead *element = a; 43778556Sobrien 43878556Sobrien element->qh_link->qh_rlink = element->qh_rlink; 43978556Sobrien element->qh_rlink->qh_link = element->qh_link; 44078556Sobrien element->qh_rlink = 0; 44178556Sobrien} 44278556Sobrien 44378556Sobrien#else /* !__GNUC__ */ 44478556Sobrien 44578556Sobrienvoid insque __P((void *a, void *b)); 44678556Sobrienvoid remque __P((void *a)); 44778556Sobrien 44878556Sobrien#endif /* __GNUC__ */ 44978556Sobrien 45078556Sobrien#endif /* _KERNEL */ 45178556Sobrien 45278556Sobrien#endif /* !_SYS_QUEUE_H_ */ 45378556Sobrien