queue.h@ 103068

Last change on this file since 103068 was 98103, checked in by vboxsync, 21 months ago
Copyright year updates by scm.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 29.8 KB

Rev	Line
[28449]	1	/* $Id: queue.h 98103 2023-01-17 14:15:46Z vboxsync $ */
	2	/** @file
	3	* NAT - Queue handling.
	4	*/
	5
	6	/*
[98103]	7	* Copyright (C) 2006-2023 Oracle and/or its affiliates.
[28449]	8	*
[96407]	9	* This file is part of VirtualBox base platform packages, as
	10	* available from https://www.virtualbox.org.
	11	*
	12	* This program is free software; you can redistribute it and/or
	13	* modify it under the terms of the GNU General Public License
	14	* as published by the Free Software Foundation, in version 3 of the
	15	* License.
	16	*
	17	* This program is distributed in the hope that it will be useful, but
	18	* WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	20	* General Public License for more details.
	21	*
	22	* You should have received a copy of the GNU General Public License
	23	* along with this program; if not, see <https://www.gnu.org/licenses>.
	24	*
	25	* SPDX-License-Identifier: GPL-3.0-only
[28449]	26	*/
	27
	28	/*
	29	* This code is based on:
	30	*
[14434]	31	* Copyright (c) 1991, 1993
[14470]	32	* The Regents of the University of California. All rights reserved.
[14434]	33	*
	34	* Redistribution and use in source and binary forms, with or without
	35	* modification, are permitted provided that the following conditions
	36	* are met:
	37	* 1. Redistributions of source code must retain the above copyright
	38	* notice, this list of conditions and the following disclaimer.
	39	* 2. Redistributions in binary form must reproduce the above copyright
	40	* notice, this list of conditions and the following disclaimer in the
	41	* documentation and/or other materials provided with the distribution.
	42	* 4. Neither the name of the University nor the names of its contributors
	43	* may be used to endorse or promote products derived from this software
	44	* without specific prior written permission.
	45	*
	46	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	47	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	48	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	49	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	50	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	51	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	52	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	53	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	54	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	55	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	56	* SUCH DAMAGE.
	57	*
[14470]	58	* @(#)queue.h 8.5 (Berkeley) 8/20/94
[14434]	59	* $FreeBSD: src/sys/sys/queue.h,v 1.68 2006/10/24 11:20:29 ru Exp $
	60	*/
	61
	62	#ifndef _SYS_QUEUE_H_
[14470]	63	#define _SYS_QUEUE_H_
[14434]	64
	65	#include <iprt/cdefs.h>
	66	#ifdef RT_OS_WINDOWS
	67	#ifdef SLIST_ENTRY
	68	/Here is a conflict with winnt.h/
	69	#undef SLIST_ENTRY
	70	#endif
	71	#endif /* RT_OS_WINDOWS */
	72
	73	/*
	74	* This file defines four types of data structures: singly-linked lists,
	75	* singly-linked tail queues, lists and tail queues.
	76	*
	77	* A singly-linked list is headed by a single forward pointer. The elements
	78	* are singly linked for minimum space and pointer manipulation overhead at
	79	* the expense of O(n) removal for arbitrary elements. New elements can be
	80	* added to the list after an existing element or at the head of the list.
	81	* Elements being removed from the head of the list should use the explicit
	82	* macro for this purpose for optimum efficiency. A singly-linked list may
	83	* only be traversed in the forward direction. Singly-linked lists are ideal
	84	* for applications with large datasets and few or no removals or for
	85	* implementing a LIFO queue.
	86	*
	87	* A singly-linked tail queue is headed by a pair of pointers, one to the
	88	* head of the list and the other to the tail of the list. The elements are
	89	* singly linked for minimum space and pointer manipulation overhead at the
	90	* expense of O(n) removal for arbitrary elements. New elements can be added
	91	* to the list after an existing element, at the head of the list, or at the
	92	* end of the list. Elements being removed from the head of the tail queue
	93	* should use the explicit macro for this purpose for optimum efficiency.
	94	* A singly-linked tail queue may only be traversed in the forward direction.
	95	* Singly-linked tail queues are ideal for applications with large datasets
	96	* and few or no removals or for implementing a FIFO queue.
	97	*
	98	* A list is headed by a single forward pointer (or an array of forward
	99	* pointers for a hash table header). The elements are doubly linked
	100	* so that an arbitrary element can be removed without a need to
	101	* traverse the list. New elements can be added to the list before
	102	* or after an existing element or at the head of the list. A list
	103	* may only be traversed in the forward direction.
	104	*
	105	* A tail queue is headed by a pair of pointers, one to the head of the
	106	* list and the other to the tail of the list. The elements are doubly
	107	* linked so that an arbitrary element can be removed without a need to
	108	* traverse the list. New elements can be added to the list before or
	109	* after an existing element, at the head of the list, or at the end of
	110	* the list. A tail queue may be traversed in either direction.
	111	*
	112	* For details on the use of these macros, see the queue(3) manual page.
	113	*
	114	*
[14470]	115	* SLIST LIST STAILQ TAILQ
	116	* _HEAD + + + +
	117	* _HEAD_INITIALIZER + + + +
	118	* _ENTRY + + + +
	119	* _INIT + + + +
	120	* _EMPTY + + + +
	121	* _FIRST + + + +
	122	* _NEXT + + + +
	123	* _PREV - - - +
	124	* _LAST - - + +
	125	* _FOREACH + + + +
	126	* _FOREACH_SAFE + + + +
	127	* _FOREACH_REVERSE - - - +
	128	* _FOREACH_REVERSE_SAFE - - - +
	129	* _INSERT_HEAD + + + +
	130	* _INSERT_BEFORE - + - +
	131	* _INSERT_AFTER + + + +
	132	* _INSERT_TAIL - - + +
	133	* _CONCAT - - + +
	134	* _REMOVE_HEAD + - + -
	135	* _REMOVE + + + +
[14434]	136	*
	137	*/
	138	#ifdef QUEUE_MACRO_DEBUG
	139	/* Store the last 2 places the queue element or head was altered */
	140	struct qm_trace {
[14470]	141	char * lastfile;
	142	int lastline;
	143	char * prevfile;
	144	int prevline;
[14434]	145	};
	146
[14470]	147	#define TRACEBUF struct qm_trace trace;
	148	#define TRASHIT(x) do {(x) = (void *)-1;} while (0)
[14434]	149
[14470]	150	#define QMD_TRACE_HEAD(head) do { \
	151	(head)->trace.prevline = (head)->trace.lastline; \
	152	(head)->trace.prevfile = (head)->trace.lastfile; \
	153	(head)->trace.lastline = __LINE__; \
	154	(head)->trace.lastfile = __FILE__; \
[14434]	155	} while (0)
	156
[14470]	157	#define QMD_TRACE_ELEM(elem) do { \
	158	(elem)->trace.prevline = (elem)->trace.lastline; \
	159	(elem)->trace.prevfile = (elem)->trace.lastfile; \
	160	(elem)->trace.lastline = __LINE__; \
	161	(elem)->trace.lastfile = __FILE__; \
[14434]	162	} while (0)
	163
	164	#else
[14470]	165	#define QMD_TRACE_ELEM(elem)
	166	#define QMD_TRACE_HEAD(head)
	167	#define TRACEBUF
	168	#define TRASHIT(x)
	169	#endif /* QUEUE_MACRO_DEBUG */
[14434]	170
	171	/*
	172	* Singly-linked List declarations.
	173	*/
[14470]	174	#define SLIST_HEAD(name, type) \
	175	struct name { \
	176	struct type slh_first; / first element */ \
[14434]	177	}
	178
[14470]	179	#define SLIST_HEAD_INITIALIZER(head) \
	180	{ NULL }
[14434]	181
[14470]	182	#define SLIST_ENTRY(type) \
	183	struct { \
	184	struct type sle_next; / next element */ \
[14434]	185	}
	186
	187	/*
	188	* Singly-linked List functions.
	189	*/
[14470]	190	#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
[14434]	191
[14470]	192	#define SLIST_FIRST(head) ((head)->slh_first)
[14434]	193
[14470]	194	#define SLIST_FOREACH(var, head, field) \
	195	for ((var) = SLIST_FIRST((head)); \
	196	(var); \
	197	(var) = SLIST_NEXT((var), field))
[14434]	198
[14470]	199	#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
	200	for ((var) = SLIST_FIRST((head)); \
	201	(var) && ((tvar) = SLIST_NEXT((var), field), 1); \
	202	(var) = (tvar))
[14434]	203
[14470]	204	#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
	205	for ((varp) = &SLIST_FIRST((head)); \
	206	((var) = *(varp)) != NULL; \
	207	(varp) = &SLIST_NEXT((var), field))
[14434]	208
[14470]	209	#define SLIST_INIT(head) do { \
	210	SLIST_FIRST((head)) = NULL; \
[14434]	211	} while (0)
	212
[14470]	213	#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
	214	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
	215	SLIST_NEXT((slistelm), field) = (elm); \
[14434]	216	} while (0)
	217
[14470]	218	#define SLIST_INSERT_HEAD(head, elm, field) do { \
	219	SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
	220	SLIST_FIRST((head)) = (elm); \
[14434]	221	} while (0)
	222
[14470]	223	#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
[14434]	224
[14470]	225	#define SLIST_REMOVE(head, elm, type, field) do { \
	226	if (SLIST_FIRST((head)) == (elm)) { \
	227	SLIST_REMOVE_HEAD((head), field); \
	228	} \
	229	else { \
	230	struct type *curelm = SLIST_FIRST((head)); \
	231	while (SLIST_NEXT(curelm, field) != (elm)) \
	232	curelm = SLIST_NEXT(curelm, field); \
	233	SLIST_NEXT(curelm, field) = \
	234	SLIST_NEXT(SLIST_NEXT(curelm, field), field); \
	235	} \
	236	TRASHIT((elm)->field.sle_next); \
[14434]	237	} while (0)
	238
[14470]	239	#define SLIST_REMOVE_HEAD(head, field) do { \
	240	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
[14434]	241	} while (0)
	242
	243	/*
	244	* Singly-linked Tail queue declarations.
	245	*/
[14470]	246	#define STAILQ_HEAD(name, type) \
	247	struct name { \
	248	struct type stqh_first;/ first element */ \
	249	struct type *stqh_last;/ addr of last next element */ \
[14434]	250	}
	251
[14470]	252	#define STAILQ_HEAD_INITIALIZER(head) \
	253	{ NULL, &(head).stqh_first }
[14434]	254
[14470]	255	#define STAILQ_ENTRY(type) \
	256	struct { \
	257	struct type stqe_next; / next element */ \
[14434]	258	}
	259
	260	/*
	261	* Singly-linked Tail queue functions.
	262	*/
[14470]	263	#define STAILQ_CONCAT(head1, head2) do { \
	264	if (!STAILQ_EMPTY((head2))) { \
	265	*(head1)->stqh_last = (head2)->stqh_first; \
	266	(head1)->stqh_last = (head2)->stqh_last; \
	267	STAILQ_INIT((head2)); \
	268	} \
[14434]	269	} while (0)
	270
[14470]	271	#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
[14434]	272
[14470]	273	#define STAILQ_FIRST(head) ((head)->stqh_first)
[14434]	274
[14470]	275	#define STAILQ_FOREACH(var, head, field) \
	276	for((var) = STAILQ_FIRST((head)); \
	277	(var); \
	278	(var) = STAILQ_NEXT((var), field))
[14434]	279
	280
[14470]	281	#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
	282	for ((var) = STAILQ_FIRST((head)); \
	283	(var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
	284	(var) = (tvar))
[14434]	285
[14470]	286	#define STAILQ_INIT(head) do { \
	287	STAILQ_FIRST((head)) = NULL; \
	288	(head)->stqh_last = &STAILQ_FIRST((head)); \
[14434]	289	} while (0)
	290
[14470]	291	#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
	292	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
	293	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
	294	STAILQ_NEXT((tqelm), field) = (elm); \
[14434]	295	} while (0)
	296
[14470]	297	#define STAILQ_INSERT_HEAD(head, elm, field) do { \
	298	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
	299	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
	300	STAILQ_FIRST((head)) = (elm); \
[14434]	301	} while (0)
	302
[14470]	303	#define STAILQ_INSERT_TAIL(head, elm, field) do { \
	304	STAILQ_NEXT((elm), field) = NULL; \
	305	*(head)->stqh_last = (elm); \
	306	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
[14434]	307	} while (0)
	308
[14470]	309	#define STAILQ_LAST(head, type, field) \
	310	(STAILQ_EMPTY((head)) ? \
	311	NULL : \
	312	((struct type )(void ) \
	313	((char *)((head)->stqh_last) - __offsetof(struct type, field))))
[14434]	314
[14470]	315	#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
[14434]	316
[14470]	317	#define STAILQ_REMOVE(head, elm, type, field) do { \
	318	if (STAILQ_FIRST((head)) == (elm)) { \
	319	STAILQ_REMOVE_HEAD((head), field); \
	320	} \
	321	else { \
	322	struct type *curelm = STAILQ_FIRST((head)); \
	323	while (STAILQ_NEXT(curelm, field) != (elm)) \
	324	curelm = STAILQ_NEXT(curelm, field); \
	325	if ((STAILQ_NEXT(curelm, field) = \
	326	STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
	327	(head)->stqh_last = &STAILQ_NEXT((curelm), field);\
	328	} \
	329	TRASHIT((elm)->field.stqe_next); \
[14434]	330	} while (0)
	331
[14470]	332	#define STAILQ_REMOVE_HEAD(head, field) do { \
	333	if ((STAILQ_FIRST((head)) = \
	334	STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
	335	(head)->stqh_last = &STAILQ_FIRST((head)); \
[14434]	336	} while (0)
	337
	338	/*
	339	* List declarations.
	340	*/
[14470]	341	#define LIST_HEAD(name, type) \
	342	struct name { \
	343	struct type lh_first; / first element */ \
[14434]	344	}
	345
[14470]	346	#define LIST_HEAD_INITIALIZER(head) \
	347	{ NULL }
[14434]	348
[14470]	349	#define LIST_ENTRY(type) \
	350	struct { \
	351	struct type le_next; / next element */ \
	352	struct type *le_prev; / address of previous next element */ \
[14434]	353	}
	354
	355	/*
	356	* List functions.
	357	*/
	358
	359	#if (defined(_KERNEL) && defined(INVARIANTS))
[14470]	360	#define QMD_LIST_CHECK_HEAD(head, field) do { \
	361	if (LIST_FIRST((head)) != NULL && \
	362	LIST_FIRST((head))->field.le_prev != \
	363	&LIST_FIRST((head))) \
	364	panic("Bad list head %p first->prev != head", (head)); \
[14434]	365	} while (0)
	366
[14470]	367	#define QMD_LIST_CHECK_NEXT(elm, field) do { \
	368	if (LIST_NEXT((elm), field) != NULL && \
	369	LIST_NEXT((elm), field)->field.le_prev != \
	370	&((elm)->field.le_next)) \
	371	panic("Bad link elm %p next->prev != elm", (elm)); \
[14434]	372	} while (0)
	373
[14470]	374	#define QMD_LIST_CHECK_PREV(elm, field) do { \
	375	if (*(elm)->field.le_prev != (elm)) \
	376	panic("Bad link elm %p prev->next != elm", (elm)); \
[14434]	377	} while (0)
	378	#else
[14470]	379	#define QMD_LIST_CHECK_HEAD(head, field)
	380	#define QMD_LIST_CHECK_NEXT(elm, field)
	381	#define QMD_LIST_CHECK_PREV(elm, field)
[14434]	382	#endif /* (_KERNEL && INVARIANTS) */
	383
[14470]	384	#define LIST_EMPTY(head) ((head)->lh_first == NULL)
[14434]	385
[14470]	386	#define LIST_FIRST(head) ((head)->lh_first)
[14434]	387
[14470]	388	#define LIST_FOREACH(var, head, field) \
	389	for ((var) = LIST_FIRST((head)); \
	390	(var); \
	391	(var) = LIST_NEXT((var), field))
[14434]	392
[14470]	393	#define LIST_FOREACH_SAFE(var, head, field, tvar) \
	394	for ((var) = LIST_FIRST((head)); \
	395	(var) && ((tvar) = LIST_NEXT((var), field), 1); \
	396	(var) = (tvar))
[14434]	397
[14470]	398	#define LIST_INIT(head) do { \
	399	LIST_FIRST((head)) = NULL; \
[14434]	400	} while (0)
	401
[14470]	402	#define LIST_INSERT_AFTER(listelm, elm, field) do { \
	403	QMD_LIST_CHECK_NEXT(listelm, field); \
	404	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
	405	LIST_NEXT((listelm), field)->field.le_prev = \
	406	&LIST_NEXT((elm), field); \
	407	LIST_NEXT((listelm), field) = (elm); \
	408	(elm)->field.le_prev = &LIST_NEXT((listelm), field); \
[14434]	409	} while (0)
	410
[14470]	411	#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
	412	QMD_LIST_CHECK_PREV(listelm, field); \
	413	(elm)->field.le_prev = (listelm)->field.le_prev; \
	414	LIST_NEXT((elm), field) = (listelm); \
	415	*(listelm)->field.le_prev = (elm); \
	416	(listelm)->field.le_prev = &LIST_NEXT((elm), field); \
[14434]	417	} while (0)
	418
[14470]	419	#define LIST_INSERT_HEAD(head, elm, field) do { \
	420	QMD_LIST_CHECK_HEAD((head), field); \
	421	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
	422	LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
	423	LIST_FIRST((head)) = (elm); \
	424	(elm)->field.le_prev = &LIST_FIRST((head)); \
[14434]	425	} while (0)
	426
[14470]	427	#define LIST_NEXT(elm, field) ((elm)->field.le_next)
[14434]	428
[14470]	429	#define LIST_REMOVE(elm, field) do { \
	430	QMD_LIST_CHECK_NEXT(elm, field); \
	431	QMD_LIST_CHECK_PREV(elm, field); \
	432	if (LIST_NEXT((elm), field) != NULL) \
	433	LIST_NEXT((elm), field)->field.le_prev = \
	434	(elm)->field.le_prev; \
	435	*(elm)->field.le_prev = LIST_NEXT((elm), field); \
	436	TRASHIT((elm)->field.le_next); \
	437	TRASHIT((elm)->field.le_prev); \
[14434]	438	} while (0)
	439
	440	/*
	441	* Tail queue declarations.
	442	*/
[14470]	443	#define TAILQ_HEAD(name, type) \
	444	struct name { \
	445	struct type tqh_first; / first element */ \
	446	struct type *tqh_last; / addr of last next element */ \
	447	TRACEBUF \
[14434]	448	}
	449
[14470]	450	#define TAILQ_HEAD_INITIALIZER(head) \
	451	{ NULL, &(head).tqh_first }
[14434]	452
[14470]	453	#define TAILQ_ENTRY(type) \
	454	struct { \
	455	struct type tqe_next; / next element */ \
	456	struct type *tqe_prev; / address of previous next element */ \
	457	TRACEBUF \
[14434]	458	}
	459
	460	/*
	461	* Tail queue functions.
	462	*/
	463	#if (defined(_KERNEL) && defined(INVARIANTS))
[14470]	464	#define QMD_TAILQ_CHECK_HEAD(head, field) do { \
	465	if (!TAILQ_EMPTY(head) && \
	466	TAILQ_FIRST((head))->field.tqe_prev != \
	467	&TAILQ_FIRST((head))) \
	468	panic("Bad tailq head %p first->prev != head", (head)); \
[14434]	469	} while (0)
	470
[14470]	471	#define QMD_TAILQ_CHECK_TAIL(head, field) do { \
	472	if (*(head)->tqh_last != NULL) \
	473	panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
[14434]	474	} while (0)
	475
[14470]	476	#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
	477	if (TAILQ_NEXT((elm), field) != NULL && \
	478	TAILQ_NEXT((elm), field)->field.tqe_prev != \
	479	&((elm)->field.tqe_next)) \
	480	panic("Bad link elm %p next->prev != elm", (elm)); \
[14434]	481	} while (0)
	482
[14470]	483	#define QMD_TAILQ_CHECK_PREV(elm, field) do { \
	484	if (*(elm)->field.tqe_prev != (elm)) \
	485	panic("Bad link elm %p prev->next != elm", (elm)); \
[14434]	486	} while (0)
	487	#else
[14470]	488	#define QMD_TAILQ_CHECK_HEAD(head, field)
	489	#define QMD_TAILQ_CHECK_TAIL(head, headname)
	490	#define QMD_TAILQ_CHECK_NEXT(elm, field)
	491	#define QMD_TAILQ_CHECK_PREV(elm, field)
[14434]	492	#endif /* (_KERNEL && INVARIANTS) */
	493
[14470]	494	#define TAILQ_CONCAT(head1, head2, field) do { \
	495	if (!TAILQ_EMPTY(head2)) { \
	496	*(head1)->tqh_last = (head2)->tqh_first; \
	497	(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
	498	(head1)->tqh_last = (head2)->tqh_last; \
	499	TAILQ_INIT((head2)); \
	500	QMD_TRACE_HEAD(head1); \
	501	QMD_TRACE_HEAD(head2); \
	502	} \
[14434]	503	} while (0)
	504
[14470]	505	#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
[14434]	506
[14470]	507	#define TAILQ_FIRST(head) ((head)->tqh_first)
[14434]	508
[14470]	509	#define TAILQ_FOREACH(var, head, field) \
	510	for ((var) = TAILQ_FIRST((head)); \
	511	(var); \
	512	(var) = TAILQ_NEXT((var), field))
[14434]	513
[14470]	514	#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
	515	for ((var) = TAILQ_FIRST((head)); \
	516	(var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
	517	(var) = (tvar))
[14434]	518
[14470]	519	#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
	520	for ((var) = TAILQ_LAST((head), headname); \
	521	(var); \
	522	(var) = TAILQ_PREV((var), headname, field))
[14434]	523
[14470]	524	#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
	525	for ((var) = TAILQ_LAST((head), headname); \
	526	(var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
	527	(var) = (tvar))
[14434]	528
[14470]	529	#define TAILQ_INIT(head) do { \
	530	TAILQ_FIRST((head)) = NULL; \
	531	(head)->tqh_last = &TAILQ_FIRST((head)); \
	532	QMD_TRACE_HEAD(head); \
[14434]	533	} while (0)
	534
[14470]	535	#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
	536	QMD_TAILQ_CHECK_NEXT(listelm, field); \
	537	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
	538	TAILQ_NEXT((elm), field)->field.tqe_prev = \
	539	&TAILQ_NEXT((elm), field); \
	540	else { \
	541	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
	542	QMD_TRACE_HEAD(head); \
	543	} \
	544	TAILQ_NEXT((listelm), field) = (elm); \
	545	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
	546	QMD_TRACE_ELEM(&(elm)->field); \
	547	QMD_TRACE_ELEM(&listelm->field); \
[14434]	548	} while (0)
	549
[14470]	550	#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
	551	QMD_TAILQ_CHECK_PREV(listelm, field); \
	552	(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
	553	TAILQ_NEXT((elm), field) = (listelm); \
	554	*(listelm)->field.tqe_prev = (elm); \
	555	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
	556	QMD_TRACE_ELEM(&(elm)->field); \
	557	QMD_TRACE_ELEM(&listelm->field); \
[14434]	558	} while (0)
	559
[14470]	560	#define TAILQ_INSERT_HEAD(head, elm, field) do { \
	561	QMD_TAILQ_CHECK_HEAD(head, field); \
	562	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
	563	TAILQ_FIRST((head))->field.tqe_prev = \
	564	&TAILQ_NEXT((elm), field); \
	565	else \
	566	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
	567	TAILQ_FIRST((head)) = (elm); \
	568	(elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
	569	QMD_TRACE_HEAD(head); \
	570	QMD_TRACE_ELEM(&(elm)->field); \
[14434]	571	} while (0)
	572
[14470]	573	#define TAILQ_INSERT_TAIL(head, elm, field) do { \
	574	QMD_TAILQ_CHECK_TAIL(head, field); \
	575	TAILQ_NEXT((elm), field) = NULL; \
	576	(elm)->field.tqe_prev = (head)->tqh_last; \
	577	*(head)->tqh_last = (elm); \
	578	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
	579	QMD_TRACE_HEAD(head); \
	580	QMD_TRACE_ELEM(&(elm)->field); \
[14434]	581	} while (0)
	582
[14470]	583	#define TAILQ_LAST(head, headname) \
	584	((((struct headname )((head)->tqh_last))->tqh_last))
[14434]	585
[14470]	586	#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
[14434]	587
[14470]	588	#define TAILQ_PREV(elm, headname, field) \
	589	((((struct headname )((elm)->field.tqe_prev))->tqh_last))
[14434]	590
[14470]	591	#define TAILQ_REMOVE(head, elm, field) do { \
	592	QMD_TAILQ_CHECK_NEXT(elm, field); \
	593	QMD_TAILQ_CHECK_PREV(elm, field); \
	594	if ((TAILQ_NEXT((elm), field)) != NULL) \
	595	TAILQ_NEXT((elm), field)->field.tqe_prev = \
	596	(elm)->field.tqe_prev; \
	597	else { \
	598	(head)->tqh_last = (elm)->field.tqe_prev; \
	599	QMD_TRACE_HEAD(head); \
	600	} \
	601	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
	602	TRASHIT((elm)->field.tqe_next); \
	603	TRASHIT((elm)->field.tqe_prev); \
	604	QMD_TRACE_ELEM(&(elm)->field); \
[14434]	605	} while (0)
	606
	607
	608	#ifdef _KERNEL
	609
	610	/*
	611	* XXX insque() and remque() are an old way of handling certain queues.
	612	* They bogusly assumes that all queue heads look alike.
	613	*/
	614
	615	struct quehead {
[14470]	616	struct quehead *qh_link;
	617	struct quehead *qh_rlink;
[14434]	618	};
	619
	620	#ifdef __CC_SUPPORTS___INLINE
	621
	622	static __inline void
	623	insque(void a, void b)
	624	{
[14470]	625	struct quehead element = (struct quehead )a,
	626	head = (struct quehead )b;
[14434]	627
[14470]	628	element->qh_link = head->qh_link;
	629	element->qh_rlink = head;
	630	head->qh_link = element;
	631	element->qh_link->qh_rlink = element;
[14434]	632	}
	633
	634	static __inline void
	635	remque(void *a)
	636	{
[14470]	637	struct quehead element = (struct quehead )a;
[14434]	638
[14470]	639	element->qh_link->qh_rlink = element->qh_rlink;
	640	element->qh_rlink->qh_link = element->qh_link;
	641	element->qh_rlink = 0;
[14434]	642	}
	643
	644	#else /* !__CC_SUPPORTS___INLINE */
	645
[14470]	646	void insque(void a, void b);
	647	void remque(void *a);
[14434]	648
	649	#endif /* __CC_SUPPORTS___INLINE */
	650
	651	#endif /* _KERNEL */
	652
	653	#endif /* !_SYS_QUEUE_H_ */

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/Devices/Network/slirp/queue.h@ 103068

Download in other formats: