queue.h@ 22206

最後變更在這個檔案從22206是 21292,由 vboxsync 提交於 15 年前
svn:eol-style native
屬性 svn:eol-style 設為 `native`
檔案大小: 28.9 KB

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

注意: 瀏覽 TracBrowser 來幫助您使用儲存庫瀏覽器

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

以其他格式下載: