queue.h@ 34244

Last change on this file since 34244 was 28800, checked in by vboxsync, 15 years ago
Automated rebranding to Oracle copyright/license strings via filemuncher
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 29.5 KB

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

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

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

Download in other formats: