10a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* $NetBSD: queue.h,v 1.4 2006/09/09 16:22:09 manu Exp $ */ 20a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 30a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 40a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Copyright (c) 1991, 1993 50a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * The Regents of the University of California. All rights reserved. 60a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 70a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Redistribution and use in source and binary forms, with or without 80a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * modification, are permitted provided that the following conditions 90a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * are met: 100a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 1. Redistributions of source code must retain the above copyright 110a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * notice, this list of conditions and the following disclaimer. 120a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 2. Redistributions in binary form must reproduce the above copyright 130a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * notice, this list of conditions and the following disclaimer in the 140a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * documentation and/or other materials provided with the distribution. 150a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 4. Neither the name of the University nor the names of its contributors 160a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * may be used to endorse or promote products derived from this software 170a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * without specific prior written permission. 180a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 190a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 200a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 210a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 220a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 230a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 240a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 250a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 260a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 270a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 280a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 290a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * SUCH DAMAGE. 300a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 310a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * @(#)queue.h 8.5 (Berkeley) 8/20/94 320a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * $FreeBSD: src/sys/sys/queue.h,v 1.58 2004/04/07 04:19:49 imp Exp $ 330a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 340a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 04/24/2004 Backport to v1.45 functionality for ipsec-tools 350a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Heiko Hund <heiko@ist.eigentlich.net> 360a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 370a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 380a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#ifndef _SYS_QUEUE_H_ 390a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define _SYS_QUEUE_H_ 400a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 410a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang//#include <sys/cdefs.h> 420a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 430a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 440a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * This file defines four types of data structures: singly-linked lists, 450a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * singly-linked tail queues, lists and tail queues. 460a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 470a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * A singly-linked list is headed by a single forward pointer. The elements 480a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * are singly linked for minimum space and pointer manipulation overhead at 490a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * the expense of O(n) removal for arbitrary elements. New elements can be 500a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * added to the list after an existing element or at the head of the list. 510a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Elements being removed from the head of the list should use the explicit 520a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * macro for this purpose for optimum efficiency. A singly-linked list may 530a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * only be traversed in the forward direction. Singly-linked lists are ideal 540a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * for applications with large datasets and few or no removals or for 550a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * implementing a LIFO queue. 560a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 570a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * A singly-linked tail queue is headed by a pair of pointers, one to the 580a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * head of the list and the other to the tail of the list. The elements are 590a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * singly linked for minimum space and pointer manipulation overhead at the 600a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * expense of O(n) removal for arbitrary elements. New elements can be added 610a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * to the list after an existing element, at the head of the list, or at the 620a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * end of the list. Elements being removed from the head of the tail queue 630a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * should use the explicit macro for this purpose for optimum efficiency. 640a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * A singly-linked tail queue may only be traversed in the forward direction. 650a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Singly-linked tail queues are ideal for applications with large datasets 660a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * and few or no removals or for implementing a FIFO queue. 670a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 680a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * A list is headed by a single forward pointer (or an array of forward 690a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * pointers for a hash table header). The elements are doubly linked 700a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * so that an arbitrary element can be removed without a need to 710a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * traverse the list. New elements can be added to the list before 720a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * or after an existing element or at the head of the list. A list 730a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * may only be traversed in the forward direction. 740a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 750a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * A tail queue is headed by a pair of pointers, one to the head of the 760a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * list and the other to the tail of the list. The elements are doubly 770a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * linked so that an arbitrary element can be removed without a need to 780a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * traverse the list. New elements can be added to the list before or 790a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * after an existing element, at the head of the list, or at the end of 800a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * the list. A tail queue may be traversed in either direction. 810a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 820a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * For details on the use of these macros, see the queue(3) manual page. 830a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 840a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 850a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * SLIST LIST STAILQ TAILQ 860a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _HEAD + + + + 870a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _HEAD_INITIALIZER + + + + 880a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _ENTRY + + + + 890a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _INIT + + + + 900a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _EMPTY + + + + 910a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _FIRST + + + + 920a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _NEXT + + + + 930a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _PREV - - - + 940a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _LAST - - + + 950a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _FOREACH + + + + 960a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _FOREACH_REVERSE - - - + 970a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _INSERT_HEAD + + + + 980a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _INSERT_BEFORE - + - + 990a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _INSERT_AFTER + + + + 1000a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _INSERT_TAIL - - + + 1010a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _REMOVE_HEAD + - + - 1020a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * _REMOVE + + + + 1030a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * 1040a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 1050a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1060a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 1070a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Singly-linked List declarations. 1080a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 1090a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_HEAD(name, type) \ 1100a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct name { \ 1110a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *slh_first; /* first element */ \ 1120a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 1130a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1140a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_HEAD_INITIALIZER(head) \ 1150a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang { NULL } 1160a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1170a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_ENTRY(type) \ 1180a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct { \ 1190a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *sle_next; /* next element */ \ 1200a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 1210a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1220a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 1230a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Singly-linked List functions. 1240a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 1250a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 1260a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1270a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_FIRST(head) ((head)->slh_first) 1280a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1290a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_FOREACH(var, head, field) \ 1300a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang for ((var) = SLIST_FIRST((head)); \ 1310a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var); \ 1320a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var) = SLIST_NEXT((var), field)) 1330a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1340a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_INIT(head) do { \ 1350a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_FIRST((head)) = NULL; \ 1360a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 1370a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1380a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 1390a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 1400a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_NEXT((slistelm), field) = (elm); \ 1410a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 1420a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1430a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_INSERT_HEAD(head, elm, field) do { \ 1440a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 1450a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_FIRST((head)) = (elm); \ 1460a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 1470a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1480a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 1490a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1500a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_REMOVE(head, elm, type, field) do { \ 1510a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if (SLIST_FIRST((head)) == (elm)) { \ 1520a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_REMOVE_HEAD((head), field); \ 1530a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang } \ 1540a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang else { \ 1550a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *curelm = SLIST_FIRST((head)); \ 1560a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang while (SLIST_NEXT(curelm, field) != (elm)) \ 1570a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang curelm = SLIST_NEXT(curelm, field); \ 1580a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_NEXT(curelm, field) = \ 1590a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 1600a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang } \ 1610a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 1620a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1630a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define SLIST_REMOVE_HEAD(head, field) do { \ 1640a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 1650a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 1660a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1670a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 1680a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Singly-linked Tail queue declarations. 1690a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 1700a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_HEAD(name, type) \ 1710a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct name { \ 1720a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *stqh_first;/* first element */ \ 1730a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type **stqh_last;/* addr of last next element */ \ 1740a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 1750a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1760a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_HEAD_INITIALIZER(head) \ 1770a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang { NULL, &(head).stqh_first } 1780a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1790a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_ENTRY(type) \ 1800a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct { \ 1810a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *stqe_next; /* next element */ \ 1820a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 1830a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1840a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 1850a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Singly-linked Tail queue functions. 1860a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 1870a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 1880a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1890a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_FIRST(head) ((head)->stqh_first) 1900a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1910a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_FOREACH(var, head, field) \ 1920a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang for((var) = STAILQ_FIRST((head)); \ 1930a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var); \ 1940a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var) = STAILQ_NEXT((var), field)) 1950a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 1960a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_INIT(head) do { \ 1970a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang STAILQ_FIRST((head)) = NULL; \ 1980a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->stqh_last = &STAILQ_FIRST((head)); \ 1990a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2000a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2010a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 2020a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 2030a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 2040a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang STAILQ_NEXT((tqelm), field) = (elm); \ 2050a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2060a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2070a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 2080a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 2090a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 2100a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang STAILQ_FIRST((head)) = (elm); \ 2110a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2120a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2130a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 2140a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang STAILQ_NEXT((elm), field) = NULL; \ 2150a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang *(head)->stqh_last = (elm); \ 2160a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 2170a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2180a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2190a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_LAST(head, type, field) \ 2200a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (STAILQ_EMPTY(head) ? \ 2210a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang NULL : \ 2220a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang ((struct type *) \ 2230a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 2240a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2250a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 2260a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2270a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_REMOVE(head, elm, type, field) do { \ 2280a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if (STAILQ_FIRST((head)) == (elm)) { \ 2290a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang STAILQ_REMOVE_HEAD(head, field); \ 2300a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang } \ 2310a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang else { \ 2320a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *curelm = STAILQ_FIRST((head)); \ 2330a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang while (STAILQ_NEXT(curelm, field) != (elm)) \ 2340a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang curelm = STAILQ_NEXT(curelm, field); \ 2350a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((STAILQ_NEXT(curelm, field) = \ 2360a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 2370a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 2380a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang } \ 2390a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2400a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2410a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_REMOVE_HEAD(head, field) do { \ 2420a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((STAILQ_FIRST((head)) = \ 2430a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 2440a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->stqh_last = &STAILQ_FIRST((head)); \ 2450a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2460a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2470a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 2480a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ 2490a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->stqh_last = &STAILQ_FIRST((head)); \ 2500a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2510a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2520a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 2530a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * List declarations. 2540a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 2550a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_HEAD(name, type) \ 2560a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct name { \ 2570a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *lh_first; /* first element */ \ 2580a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 2590a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2600a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_HEAD_INITIALIZER(head) \ 2610a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang { NULL } 2620a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2630a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_ENTRY(type) \ 2640a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct { \ 2650a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *le_next; /* next element */ \ 2660a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type **le_prev; /* address of previous next element */ \ 2670a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 2680a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2690a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 2700a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * List functions. 2710a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 2720a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2730a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_EMPTY(head) ((head)->lh_first == NULL) 2740a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2750a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_FIRST(head) ((head)->lh_first) 2760a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2770a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_FOREACH(var, head, field) \ 2780a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang for ((var) = LIST_FIRST((head)); \ 2790a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var); \ 2800a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var) = LIST_NEXT((var), field)) 2810a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2820a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_INIT(head) do { \ 2830a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang LIST_FIRST((head)) = NULL; \ 2840a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2850a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2860a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 2870a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 2880a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang LIST_NEXT((listelm), field)->field.le_prev = \ 2890a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang &LIST_NEXT((elm), field); \ 2900a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang LIST_NEXT((listelm), field) = (elm); \ 2910a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 2920a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 2930a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 2940a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 2950a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.le_prev = (listelm)->field.le_prev; \ 2960a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang LIST_NEXT((elm), field) = (listelm); \ 2970a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang *(listelm)->field.le_prev = (elm); \ 2980a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 2990a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 3000a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3010a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_INSERT_HEAD(head, elm, field) do { \ 3020a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 3030a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 3040a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang LIST_FIRST((head)) = (elm); \ 3050a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.le_prev = &LIST_FIRST((head)); \ 3060a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 3070a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3080a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_NEXT(elm, field) ((elm)->field.le_next) 3090a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3100a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define LIST_REMOVE(elm, field) do { \ 3110a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if (LIST_NEXT((elm), field) != NULL) \ 3120a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang LIST_NEXT((elm), field)->field.le_prev = \ 3130a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.le_prev; \ 3140a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 3150a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 3160a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3170a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 3180a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Tail queue declarations. 3190a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 3200a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_HEAD(name, type) \ 3210a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct name { \ 3220a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *tqh_first; /* first element */ \ 3230a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type **tqh_last; /* addr of last next element */ \ 3240a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 3250a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3260a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_HEAD_INITIALIZER(head) \ 3270a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang { NULL, &(head).tqh_first } 3280a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3290a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_ENTRY(type) \ 3300a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct { \ 3310a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type *tqe_next; /* next element */ \ 3320a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct type **tqe_prev; /* address of previous next element */ \ 3330a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 3340a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3350a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 3360a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * Tail queue functions. 3370a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 3380a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 3390a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3400a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_FIRST(head) ((head)->tqh_first) 3410a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3420a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_FOREACH(var, head, field) \ 3430a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang for ((var) = TAILQ_FIRST((head)); \ 3440a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var); \ 3450a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var) = TAILQ_NEXT((var), field)) 3460a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3470a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 3480a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang for ((var) = TAILQ_LAST((head), headname); \ 3490a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var); \ 3500a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (var) = TAILQ_PREV((var), headname, field)) 3510a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3520a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_INIT(head) do { \ 3530a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang TAILQ_FIRST((head)) = NULL; \ 3540a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->tqh_last = &TAILQ_FIRST((head)); \ 3550a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 3560a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3570a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 3580a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 3590a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang TAILQ_NEXT((elm), field)->field.tqe_prev = \ 3600a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang &TAILQ_NEXT((elm), field); \ 3610a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang else \ 3620a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 3630a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang TAILQ_NEXT((listelm), field) = (elm); \ 3640a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 3650a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 3660a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3670a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 3680a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 3690a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang TAILQ_NEXT((elm), field) = (listelm); \ 3700a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang *(listelm)->field.tqe_prev = (elm); \ 3710a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 3720a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 3730a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3740a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 3750a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 3760a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang TAILQ_FIRST((head))->field.tqe_prev = \ 3770a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang &TAILQ_NEXT((elm), field); \ 3780a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang else \ 3790a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 3800a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang TAILQ_FIRST((head)) = (elm); \ 3810a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 3820a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 3830a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3840a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 3850a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang TAILQ_NEXT((elm), field) = NULL; \ 3860a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.tqe_prev = (head)->tqh_last; \ 3870a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang *(head)->tqh_last = (elm); \ 3880a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 3890a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 3900a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3910a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_LAST(head, headname) \ 3920a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (*(((struct headname *)((head)->tqh_last))->tqh_last)) 3930a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3940a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 3950a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3960a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_PREV(elm, headname, field) \ 3970a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 3980a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 3990a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#define TAILQ_REMOVE(head, elm, field) do { \ 4000a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang if ((TAILQ_NEXT((elm), field)) != NULL) \ 4010a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang TAILQ_NEXT((elm), field)->field.tqe_prev = \ 4020a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (elm)->field.tqe_prev; \ 4030a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang else \ 4040a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang (head)->tqh_last = (elm)->field.tqe_prev; \ 4050a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 4060a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} while (0) 4070a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4080a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4090a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#ifdef _KERNEL 4100a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4110a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang/* 4120a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * XXX insque() and remque() are an old way of handling certain queues. 4130a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang * They bogusly assumes that all queue heads look alike. 4140a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang */ 4150a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4160a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstruct quehead { 4170a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct quehead *qh_link; 4180a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct quehead *qh_rlink; 4190a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang}; 4200a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4210a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#ifdef __GNUC__ 4220a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4230a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstatic __inline void 4240a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wanginsque(void *a, void *b) 4250a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang{ 4260a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct quehead *element = (struct quehead *)a, 4270a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang *head = (struct quehead *)b; 4280a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4290a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang element->qh_link = head->qh_link; 4300a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang element->qh_rlink = head; 4310a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang head->qh_link = element; 4320a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang element->qh_link->qh_rlink = element; 4330a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 4340a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4350a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangstatic __inline void 4360a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangremque(void *a) 4370a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang{ 4380a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang struct quehead *element = (struct quehead *)a; 4390a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4400a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang element->qh_link->qh_rlink = element->qh_rlink; 4410a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang element->qh_rlink->qh_link = element->qh_link; 4420a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang element->qh_rlink = 0; 4430a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang} 4440a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4450a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#else /* !__GNUC__ */ 4460a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4470a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangvoid insque __P((void *a, void *b)); 4480a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wangvoid remque __P((void *a)); 4490a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4500a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#endif /* __GNUC__ */ 4510a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4520a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#endif /* _KERNEL */ 4530a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang 4540a1907d434839af6a9cb6329bbde60b237bf53dcChung-yih Wang#endif /* !_SYS_QUEUE_H_ */ 455