queue.h@ 98103

Last change on this file since 98103 was 98103, checked in by vboxsync, 22 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

Line
1	/* $Id: queue.h 98103 2023-01-17 14:15:46Z vboxsync $ */
2	/** @file
3	* NAT - Queue handling.
4	*/
5
6	/*
7	* Copyright (C) 2006-2023 Oracle and/or its affiliates.
8	*
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
26	*/
27
28	/*
29	* This code is based on:
30	*
31	* Copyright (c) 1991, 1993
32	* The Regents of the University of California. All rights reserved.
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	*
58	* @(#)queue.h 8.5 (Berkeley) 8/20/94
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_
63	#define _SYS_QUEUE_H_
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	*
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 + + + +
136	*
137	*/
138	#ifdef QUEUE_MACRO_DEBUG
139	/* Store the last 2 places the queue element or head was altered */
140	struct qm_trace {
141	char * lastfile;
142	int lastline;
143	char * prevfile;
144	int prevline;
145	};
146
147	#define TRACEBUF struct qm_trace trace;
148	#define TRASHIT(x) do {(x) = (void *)-1;} while (0)
149
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__; \
155	} while (0)
156
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__; \
162	} while (0)
163
164	#else
165	#define QMD_TRACE_ELEM(elem)
166	#define QMD_TRACE_HEAD(head)
167	#define TRACEBUF
168	#define TRASHIT(x)
169	#endif /* QUEUE_MACRO_DEBUG */
170
171	/*
172	* Singly-linked List declarations.
173	*/
174	#define SLIST_HEAD(name, type) \
175	struct name { \
176	struct type slh_first; / first element */ \
177	}
178
179	#define SLIST_HEAD_INITIALIZER(head) \
180	{ NULL }
181
182	#define SLIST_ENTRY(type) \
183	struct { \
184	struct type sle_next; / next element */ \
185	}
186
187	/*
188	* Singly-linked List functions.
189	*/
190	#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
191
192	#define SLIST_FIRST(head) ((head)->slh_first)
193
194	#define SLIST_FOREACH(var, head, field) \
195	for ((var) = SLIST_FIRST((head)); \
196	(var); \
197	(var) = SLIST_NEXT((var), field))
198
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))
203
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))
208
209	#define SLIST_INIT(head) do { \
210	SLIST_FIRST((head)) = NULL; \
211	} while (0)
212
213	#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
214	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
215	SLIST_NEXT((slistelm), field) = (elm); \
216	} while (0)
217
218	#define SLIST_INSERT_HEAD(head, elm, field) do { \
219	SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
220	SLIST_FIRST((head)) = (elm); \
221	} while (0)
222
223	#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
224
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); \
237	} while (0)
238
239	#define SLIST_REMOVE_HEAD(head, field) do { \
240	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
241	} while (0)
242
243	/*
244	* Singly-linked Tail queue declarations.
245	*/
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 */ \
250	}
251
252	#define STAILQ_HEAD_INITIALIZER(head) \
253	{ NULL, &(head).stqh_first }
254
255	#define STAILQ_ENTRY(type) \
256	struct { \
257	struct type stqe_next; / next element */ \
258	}
259
260	/*
261	* Singly-linked Tail queue functions.
262	*/
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	} \
269	} while (0)
270
271	#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
272
273	#define STAILQ_FIRST(head) ((head)->stqh_first)
274
275	#define STAILQ_FOREACH(var, head, field) \
276	for((var) = STAILQ_FIRST((head)); \
277	(var); \
278	(var) = STAILQ_NEXT((var), field))
279
280
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))
285
286	#define STAILQ_INIT(head) do { \
287	STAILQ_FIRST((head)) = NULL; \
288	(head)->stqh_last = &STAILQ_FIRST((head)); \
289	} while (0)
290
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); \
295	} while (0)
296
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); \
301	} while (0)
302
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); \
307	} while (0)
308
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))))
314
315	#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
316
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); \
330	} while (0)
331
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)); \
336	} while (0)
337
338	/*
339	* List declarations.
340	*/
341	#define LIST_HEAD(name, type) \
342	struct name { \
343	struct type lh_first; / first element */ \
344	}
345
346	#define LIST_HEAD_INITIALIZER(head) \
347	{ NULL }
348
349	#define LIST_ENTRY(type) \
350	struct { \
351	struct type le_next; / next element */ \
352	struct type *le_prev; / address of previous next element */ \
353	}
354
355	/*
356	* List functions.
357	*/
358
359	#if (defined(_KERNEL) && defined(INVARIANTS))
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)); \
365	} while (0)
366
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)); \
372	} while (0)
373
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)); \
377	} while (0)
378	#else
379	#define QMD_LIST_CHECK_HEAD(head, field)
380	#define QMD_LIST_CHECK_NEXT(elm, field)
381	#define QMD_LIST_CHECK_PREV(elm, field)
382	#endif /* (_KERNEL && INVARIANTS) */
383
384	#define LIST_EMPTY(head) ((head)->lh_first == NULL)
385
386	#define LIST_FIRST(head) ((head)->lh_first)
387
388	#define LIST_FOREACH(var, head, field) \
389	for ((var) = LIST_FIRST((head)); \
390	(var); \
391	(var) = LIST_NEXT((var), field))
392
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))
397
398	#define LIST_INIT(head) do { \
399	LIST_FIRST((head)) = NULL; \
400	} while (0)
401
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); \
409	} while (0)
410
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); \
417	} while (0)
418
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)); \
425	} while (0)
426
427	#define LIST_NEXT(elm, field) ((elm)->field.le_next)
428
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); \
438	} while (0)
439
440	/*
441	* Tail queue declarations.
442	*/
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 \
448	}
449
450	#define TAILQ_HEAD_INITIALIZER(head) \
451	{ NULL, &(head).tqh_first }
452
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 \
458	}
459
460	/*
461	* Tail queue functions.
462	*/
463	#if (defined(_KERNEL) && defined(INVARIANTS))
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)); \
469	} while (0)
470
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)); \
474	} while (0)
475
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)); \
481	} while (0)
482
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)); \
486	} while (0)
487	#else
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)
492	#endif /* (_KERNEL && INVARIANTS) */
493
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	} \
503	} while (0)
504
505	#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
506
507	#define TAILQ_FIRST(head) ((head)->tqh_first)
508
509	#define TAILQ_FOREACH(var, head, field) \
510	for ((var) = TAILQ_FIRST((head)); \
511	(var); \
512	(var) = TAILQ_NEXT((var), field))
513
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))
518
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))
523
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))
528
529	#define TAILQ_INIT(head) do { \
530	TAILQ_FIRST((head)) = NULL; \
531	(head)->tqh_last = &TAILQ_FIRST((head)); \
532	QMD_TRACE_HEAD(head); \
533	} while (0)
534
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); \
548	} while (0)
549
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); \
558	} while (0)
559
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); \
571	} while (0)
572
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); \
581	} while (0)
582
583	#define TAILQ_LAST(head, headname) \
584	((((struct headname )((head)->tqh_last))->tqh_last))
585
586	#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
587
588	#define TAILQ_PREV(elm, headname, field) \
589	((((struct headname )((elm)->field.tqe_prev))->tqh_last))
590
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); \
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 {
616	struct quehead *qh_link;
617	struct quehead *qh_rlink;
618	};
619
620	#ifdef __CC_SUPPORTS___INLINE
621
622	static __inline void
623	insque(void a, void b)
624	{
625	struct quehead element = (struct quehead )a,
626	head = (struct quehead )b;
627
628	element->qh_link = head->qh_link;
629	element->qh_rlink = head;
630	head->qh_link = element;
631	element->qh_link->qh_rlink = element;
632	}
633
634	static __inline void
635	remque(void *a)
636	{
637	struct quehead element = (struct quehead )a;
638
639	element->qh_link->qh_rlink = element->qh_rlink;
640	element->qh_rlink->qh_link = element->qh_link;
641	element->qh_rlink = 0;
642	}
643
644	#else /* !__CC_SUPPORTS___INLINE */
645
646	void insque(void a, void b);
647	void remque(void *a);
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@ 98103

Download in other formats: