1d65182f1818d1c19e6f3866ab6e68a262fad5185hbono@chromium.org/* 245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * <sys/queue.h> implementation for systems that don't have it. 345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Copyright (c) 1991, 1993 545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * The Regents of the University of California. All rights reserved. 645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Redistribution and use in source and binary forms, with or without 845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * modification, are permitted provided that the following conditions 945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * are met: 1045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 1. Redistributions of source code must retain the above copyright 1145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * notice, this list of conditions and the following disclaimer. 1245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 2. Redistributions in binary form must reproduce the above copyright 1345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * notice, this list of conditions and the following disclaimer in the 1445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * documentation and/or other materials provided with the distribution. 1545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 3. Neither the name of the University nor the names of its contributors 1645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * may be used to endorse or promote products derived from this software 1745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * without specific prior written permission. 1845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 1945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * SUCH DAMAGE. 3045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 3145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * @(#)queue.h 8.5 (Berkeley) 8/20/94 3245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * $FreeBSD: src/sys/sys/queue.h,v 1.32.2.4 2001/03/31 03:33:39 hsu Exp $ 3345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 3445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 3545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifndef SYS_QUEUE_H 3645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SYS_QUEUE_H 3745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 3845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 3945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * This file defines four types of data structures: singly-linked lists, 4045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * singly-linked tail queues, lists and tail queues. 4145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 4245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * A singly-linked list is headed by a single forward pointer. The elements 4345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * are singly linked for minimum space and pointer manipulation overhead at 4445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * the expense of O(n) removal for arbitrary elements. New elements can be 4545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * added to the list after an existing element or at the head of the list. 4645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Elements being removed from the head of the list should use the explicit 4745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * macro for this purpose for optimum efficiency. A singly-linked list may 4845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * only be traversed in the forward direction. Singly-linked lists are ideal 4945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * for applications with large datasets and few or no removals or for 5045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * implementing a LIFO queue. 5145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 5245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * A singly-linked tail queue is headed by a pair of pointers, one to the 5345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * head of the list and the other to the tail of the list. The elements are 5445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * singly linked for minimum space and pointer manipulation overhead at the 5545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * expense of O(n) removal for arbitrary elements. New elements can be added 5645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * to the list after an existing element, at the head of the list, or at the 5745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * end of the list. Elements being removed from the head of the tail queue 5845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * should use the explicit macro for this purpose for optimum efficiency. 5945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * A singly-linked tail queue may only be traversed in the forward direction. 6045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Singly-linked tail queues are ideal for applications with large datasets 6145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * and few or no removals or for implementing a FIFO queue. 6245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 6345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * A list is headed by a single forward pointer (or an array of forward 6445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * pointers for a hash table header). The elements are doubly linked 6545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * so that an arbitrary element can be removed without a need to 6645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * traverse the list. New elements can be added to the list before 6745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * or after an existing element or at the head of the list. A list 6845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * may only be traversed in the forward direction. 6945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 7045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * A tail queue is headed by a pair of pointers, one to the head of the 7145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * list and the other to the tail of the list. The elements are doubly 7245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * linked so that an arbitrary element can be removed without a need to 7345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * traverse the list. New elements can be added to the list before or 7445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * after an existing element, at the head of the list, or at the end of 7545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * the list. A tail queue may be traversed in either direction. 7645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 7745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * For details on the use of these macros, see the queue(3) manual page. 7845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 7945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 8045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * SLIST LIST STAILQ TAILQ 8145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _HEAD + + + + 8245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _HEAD_INITIALIZER + + + + 8345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _ENTRY + + + + 8445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _INIT + + + + 8545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _EMPTY + + + + 8645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _FIRST + + + + 8745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _NEXT + + + + 8845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _PREV - - - + 8945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _LAST - - + + 9045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _FOREACH + + + + 9145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _FOREACH_SAFE + + + + 9245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _FOREACH_REVERSE - - - + 9345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _FOREACH_REVERSE_SAFE - - - + 9445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _INSERT_HEAD + + + + 9545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _INSERT_BEFORE - + - + 9645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _INSERT_AFTER + + + + 9745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _INSERT_TAIL - - + + 9845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _CONCAT - - + + 9945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _REMOVE_HEAD + - + - 10045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * _REMOVE + + + + 10145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 10245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 10345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 10445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 10545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Singly-linked List declarations. 10645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 10745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_HEAD(name, type) \ 10845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstruct name { \ 10945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *slh_first; /* first element */ \ 11045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 11145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 11245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_HEAD_INITIALIZER(head) \ 11345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org { NULL } 11445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 11545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_ENTRY(type) \ 11645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstruct { \ 11745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *sle_next; /* next element */ \ 11845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 11945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 12045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 12145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Singly-linked List functions. 12245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 12345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 12445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 12545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_FIRST(head) ((head)->slh_first) 12645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 12745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_FOREACH(var, head, field) \ 12845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = SLIST_FIRST((head)); \ 12945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var); \ 13045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = SLIST_NEXT((var), field)) 13145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 13245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 13345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = SLIST_FIRST((head)); \ 13445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 13545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = (tvar)) 13645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 13745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 13845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((varp) = &SLIST_FIRST((head)); \ 13945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org ((var) = *(varp)) != NULL; \ 14045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (varp) = &SLIST_NEXT((var), field)) 14145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 14245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_INIT(head) do { \ 14345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_FIRST((head)) = NULL; \ 14445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 14545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 14645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 14745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 14845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_NEXT((slistelm), field) = (elm); \ 14945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 15045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 15145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_INSERT_HEAD(head, elm, field) do { \ 15245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 15345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_FIRST((head)) = (elm); \ 15445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 15545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 15645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 15745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 15845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_REMOVE(head, elm, type, field) do { \ 15945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (SLIST_FIRST((head)) == (elm)) { \ 16045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_REMOVE_HEAD((head), field); \ 16145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } \ 16245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else { \ 16345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *curelm = SLIST_FIRST((head)); \ 16445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while (SLIST_NEXT(curelm, field) != (elm)) \ 16545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org curelm = SLIST_NEXT(curelm, field); \ 16645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_NEXT(curelm, field) = \ 16745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 16845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } \ 16945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 17045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 17145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define SLIST_REMOVE_HEAD(head, field) do { \ 17245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 17345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 17445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 17545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 17645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Singly-linked Tail queue declarations. 17745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 17845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_HEAD(name, type) \ 17945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstruct name { \ 18045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *stqh_first;/* first element */ \ 18145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type **stqh_last;/* addr of last next element */ \ 18245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 18345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 18445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_HEAD_INITIALIZER(head) \ 18545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org { NULL, &(head).stqh_first } 18645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 18745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_ENTRY(type) \ 18845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstruct { \ 18945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *stqe_next; /* next element */ \ 19045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 19145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 19245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 19345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Singly-linked Tail queue functions. 19445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 19545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_CONCAT(head1, head2) do { \ 19645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (!STAILQ_EMPTY((head2))) { \ 19745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *(head1)->stqh_last = (head2)->stqh_first; \ 19845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head1)->stqh_last = (head2)->stqh_last; \ 19945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org STAILQ_INIT((head2)); \ 20045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } \ 20145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 20245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 20345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 20445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 20545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_FIRST(head) ((head)->stqh_first) 20645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 20745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_FOREACH(var, head, field) \ 20845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for((var) = STAILQ_FIRST((head)); \ 20945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var); \ 21045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = STAILQ_NEXT((var), field)) 21145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 21245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 21345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 21445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = STAILQ_FIRST((head)); \ 21545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 21645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = (tvar)) 21745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 21845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_INIT(head) do { \ 21945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org STAILQ_FIRST((head)) = NULL; \ 22045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->stqh_last = &STAILQ_FIRST((head)); \ 22145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 22245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 22345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 22445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 22545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 22645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org STAILQ_NEXT((tqelm), field) = (elm); \ 22745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 22845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 22945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 23045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 23145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 23245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org STAILQ_FIRST((head)) = (elm); \ 23345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 23445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 23545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 23645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org STAILQ_NEXT((elm), field) = NULL; \ 23745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *(head)->stqh_last = (elm); \ 23845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 23945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 24045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 24145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_LAST(head, type, field) \ 24245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (STAILQ_EMPTY((head)) ? \ 24345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org NULL : \ 24445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org ((struct type *) \ 24545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org ((char *)((head)->stqh_last) - offsetof(struct type, field)))) 24645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 24745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 24845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 24945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_REMOVE(head, elm, type, field) do { \ 25045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (STAILQ_FIRST((head)) == (elm)) { \ 25145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org STAILQ_REMOVE_HEAD((head), field); \ 25245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } \ 25345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else { \ 25445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *curelm = STAILQ_FIRST((head)); \ 25545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while (STAILQ_NEXT(curelm, field) != (elm)) \ 25645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org curelm = STAILQ_NEXT(curelm, field); \ 25745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((STAILQ_NEXT(curelm, field) = \ 25845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 25945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 26045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } \ 26145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 26245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 26345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_REMOVE_HEAD(head, field) do { \ 26445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((STAILQ_FIRST((head)) = \ 26545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 26645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->stqh_last = &STAILQ_FIRST((head)); \ 26745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 26845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 26945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 27045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ 27145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->stqh_last = &STAILQ_FIRST((head)); \ 27245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 27345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 27445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 27545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * List declarations. 27645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 27745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_HEAD(name, type) \ 27845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstruct name { \ 27945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *lh_first; /* first element */ \ 28045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 28145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 28245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_HEAD_INITIALIZER(head) \ 28345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org { NULL } 28445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 28545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_ENTRY(type) \ 28645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstruct { \ 28745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *le_next; /* next element */ \ 28845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type **le_prev; /* address of previous next element */ \ 28945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 29045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 29145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 29245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * List functions. 29345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 29445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 29545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_EMPTY(head) ((head)->lh_first == NULL) 29645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 29745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_FIRST(head) ((head)->lh_first) 29845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 29945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_FOREACH(var, head, field) \ 30045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = LIST_FIRST((head)); \ 30145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var); \ 30245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = LIST_NEXT((var), field)) 30345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 30445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 30545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = LIST_FIRST((head)); \ 30645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 30745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = (tvar)) 30845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 30945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_INIT(head) do { \ 31045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LIST_FIRST((head)) = NULL; \ 31145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 31245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 31345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 31445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 31545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LIST_NEXT((listelm), field)->field.le_prev = \ 31645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org &LIST_NEXT((elm), field); \ 31745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LIST_NEXT((listelm), field) = (elm); \ 31845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 31945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 32045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 32145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 32245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.le_prev = (listelm)->field.le_prev; \ 32345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LIST_NEXT((elm), field) = (listelm); \ 32445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *(listelm)->field.le_prev = (elm); \ 32545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 32645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 32745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 32845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_INSERT_HEAD(head, elm, field) do { \ 32945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 33045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 33145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LIST_FIRST((head)) = (elm); \ 33245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.le_prev = &LIST_FIRST((head)); \ 33345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 33445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 33545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_NEXT(elm, field) ((elm)->field.le_next) 33645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 33745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define LIST_REMOVE(elm, field) do { \ 33845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (LIST_NEXT((elm), field) != NULL) \ 33945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org LIST_NEXT((elm), field)->field.le_prev = \ 34045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.le_prev; \ 34145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 34245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 34345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 34445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 34545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Tail queue declarations. 34645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 34745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_HEAD(name, type) \ 34845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstruct name { \ 34945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *tqh_first; /* first element */ \ 35045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type **tqh_last; /* addr of last next element */ \ 35145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 35245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 35345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_HEAD_INITIALIZER(head) \ 35445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org { NULL, &(head).tqh_first } 35545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 35645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_ENTRY(type) \ 35745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgstruct { \ 35845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type *tqe_next; /* next element */ \ 35945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org struct type **tqe_prev; /* address of previous next element */ \ 36045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 36145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 36245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 36345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Tail queue functions. 36445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 36545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_CONCAT(head1, head2, field) do { \ 36645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if (!TAILQ_EMPTY(head2)) { \ 36745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *(head1)->tqh_last = (head2)->tqh_first; \ 36845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 36945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head1)->tqh_last = (head2)->tqh_last; \ 37045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_INIT((head2)); \ 37145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } \ 37245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 37345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 37445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 37545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 37645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_FIRST(head) ((head)->tqh_first) 37745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 37845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_FOREACH(var, head, field) \ 37945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = TAILQ_FIRST((head)); \ 38045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var); \ 38145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = TAILQ_NEXT((var), field)) 38245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 38345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 38445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = TAILQ_FIRST((head)); \ 38545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 38645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = (tvar)) 38745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 38845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 38945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = TAILQ_LAST((head), headname); \ 39045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var); \ 39145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = TAILQ_PREV((var), headname, field)) 39245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 39345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 39445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for ((var) = TAILQ_LAST((head), headname); \ 39545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 39645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (var) = (tvar)) 39745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 39845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_INIT(head) do { \ 39945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_FIRST((head)) = NULL; \ 40045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->tqh_last = &TAILQ_FIRST((head)); \ 40145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 40245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 40345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 40445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 40545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_NEXT((elm), field)->field.tqe_prev = \ 40645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org &TAILQ_NEXT((elm), field); \ 40745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else { \ 40845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 40945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } \ 41045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_NEXT((listelm), field) = (elm); \ 41145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 41245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 41345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 41445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 41545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 41645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_NEXT((elm), field) = (listelm); \ 41745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *(listelm)->field.tqe_prev = (elm); \ 41845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 41945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 42045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 42145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 42245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 42345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_FIRST((head))->field.tqe_prev = \ 42445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org &TAILQ_NEXT((elm), field); \ 42545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else \ 42645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 42745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_FIRST((head)) = (elm); \ 42845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 42945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 43045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 43145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 43245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_NEXT((elm), field) = NULL; \ 43345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.tqe_prev = (head)->tqh_last; \ 43445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *(head)->tqh_last = (elm); \ 43545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 43645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 43745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 43845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_LAST(head, headname) \ 43945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (*(((struct headname *)((head)->tqh_last))->tqh_last)) 44045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 44145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 44245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 44345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_PREV(elm, headname, field) \ 44445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 44545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 44645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define TAILQ_REMOVE(head, elm, field) do { \ 44745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org if ((TAILQ_NEXT((elm), field)) != NULL) \ 44845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org TAILQ_NEXT((elm), field)->field.tqe_prev = \ 44945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (elm)->field.tqe_prev; \ 45045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org else { \ 45145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (head)->tqh_last = (elm)->field.tqe_prev; \ 45245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } \ 45345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 45445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} while (0) 45545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 45645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif /* !SYS_QUEUE_H */ 457