Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

queue.h @ 444

Last change on this file since 444 was 444, checked in by satin@…, 6 years ago
add newlib,libalmos-mkh, restructure shared_syscalls.h and mini-libc
File size: 29.1 KB

Line
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	* 3. 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$
31	*/
32
33	#ifndef _SYS_QUEUE_H_
34	#define _SYS_QUEUE_H_
35
36	#include <sys/cdefs.h>
37
38	/*
39	* This file defines four types of data structures: singly-linked lists,
40	* singly-linked tail queues, lists and tail queues.
41	*
42	* A singly-linked list is headed by a single forward pointer. The elements
43	* are singly linked for minimum space and pointer manipulation overhead at
44	* the expense of O(n) removal for arbitrary elements. New elements can be
45	* added to the list after an existing element or at the head of the list.
46	* Elements being removed from the head of the list should use the explicit
47	* macro for this purpose for optimum efficiency. A singly-linked list may
48	* only be traversed in the forward direction. Singly-linked lists are ideal
49	* for applications with large datasets and few or no removals or for
50	* implementing a LIFO queue.
51	*
52	* A singly-linked tail queue is headed by a pair of pointers, one to the
53	* head of the list and the other to the tail of the list. The elements are
54	* singly linked for minimum space and pointer manipulation overhead at the
55	* expense of O(n) removal for arbitrary elements. New elements can be added
56	* to the list after an existing element, at the head of the list, or at the
57	* end of the list. Elements being removed from the head of the tail queue
58	* should use the explicit macro for this purpose for optimum efficiency.
59	* A singly-linked tail queue may only be traversed in the forward direction.
60	* Singly-linked tail queues are ideal for applications with large datasets
61	* and few or no removals or for implementing a FIFO queue.
62	*
63	* A list is headed by a single forward pointer (or an array of forward
64	* pointers for a hash table header). The elements are doubly linked
65	* so that an arbitrary element can be removed without a need to
66	* traverse the list. New elements can be added to the list before
67	* or after an existing element or at the head of the list. A list
68	* may be traversed in either direction.
69	*
70	* A tail queue is headed by a pair of pointers, one to the head of the
71	* list and the other to the tail of the list. The elements are doubly
72	* linked so that an arbitrary element can be removed without a need to
73	* traverse the list. New elements can be added to the list before or
74	* after an existing element, at the head of the list, or at the end of
75	* the list. A tail queue may be traversed in either direction.
76	*
77	* For details on the use of these macros, see the queue(3) manual page.
78	*
79	* Below is a summary of implemented functions where:
80	* + means the macro is available
81	* - means the macro is not available
82	* s means the macro is available but is slow (runs in O(n) time)
83	*
84	* SLIST LIST STAILQ TAILQ
85	* _HEAD + + + +
86	* _CLASS_HEAD + + + +
87	* _HEAD_INITIALIZER + + + +
88	* _ENTRY + + + +
89	* _CLASS_ENTRY + + + +
90	* _INIT + + + +
91	* _EMPTY + + + +
92	* _FIRST + + + +
93	* _NEXT + + + +
94	* _PREV - + - +
95	* _LAST - - + +
96	* _FOREACH + + + +
97	* _FOREACH_FROM + + + +
98	* _FOREACH_SAFE + + + +
99	* _FOREACH_FROM_SAFE + + + +
100	* _FOREACH_REVERSE - - - +
101	* _FOREACH_REVERSE_FROM - - - +
102	* _FOREACH_REVERSE_SAFE - - - +
103	* _FOREACH_REVERSE_FROM_SAFE - - - +
104	* _INSERT_HEAD + + + +
105	* _INSERT_BEFORE - + - +
106	* _INSERT_AFTER + + + +
107	* _INSERT_TAIL - - + +
108	* _CONCAT s s + +
109	* _REMOVE_AFTER + - + -
110	* _REMOVE_HEAD + - + -
111	* _REMOVE s + s +
112	* _SWAP + + + +
113	*
114	*/
115	#ifdef QUEUE_MACRO_DEBUG
116	#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
117	#define QUEUE_MACRO_DEBUG_TRACE
118	#define QUEUE_MACRO_DEBUG_TRASH
119	#endif
120
121	#ifdef QUEUE_MACRO_DEBUG_TRACE
122	/* Store the last 2 places the queue element or head was altered */
123	struct qm_trace {
124	unsigned long lastline;
125	unsigned long prevline;
126	const char *lastfile;
127	const char *prevfile;
128	};
129
130	#define TRACEBUF struct qm_trace trace;
131	#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } ,
132
133	#define QMD_TRACE_HEAD(head) do { \
134	(head)->trace.prevline = (head)->trace.lastline; \
135	(head)->trace.prevfile = (head)->trace.lastfile; \
136	(head)->trace.lastline = __LINE__; \
137	(head)->trace.lastfile = __FILE__; \
138	} while (0)
139
140	#define QMD_TRACE_ELEM(elem) do { \
141	(elem)->trace.prevline = (elem)->trace.lastline; \
142	(elem)->trace.prevfile = (elem)->trace.lastfile; \
143	(elem)->trace.lastline = __LINE__; \
144	(elem)->trace.lastfile = __FILE__; \
145	} while (0)
146
147	#else /* !QUEUE_MACRO_DEBUG_TRACE */
148	#define QMD_TRACE_ELEM(elem)
149	#define QMD_TRACE_HEAD(head)
150	#define TRACEBUF
151	#define TRACEBUF_INITIALIZER
152	#endif /* QUEUE_MACRO_DEBUG_TRACE */
153
154	#ifdef QUEUE_MACRO_DEBUG_TRASH
155	#define TRASHIT(x) do {(x) = (void *)-1;} while (0)
156	#define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1)
157	#else /* !QUEUE_MACRO_DEBUG_TRASH */
158	#define TRASHIT(x)
159	#define QMD_IS_TRASHED(x) 0
160	#endif /* QUEUE_MACRO_DEBUG_TRASH */
161
162	#if defined(QUEUE_MACRO_DEBUG_TRACE) \|\| defined(QUEUE_MACRO_DEBUG_TRASH)
163	#define QMD_SAVELINK(name, link) void *name = (void )&(link)
164	#else /* !QUEUE_MACRO_DEBUG_TRACE && !QUEUE_MACRO_DEBUG_TRASH */
165	#define QMD_SAVELINK(name, link)
166	#endif /* QUEUE_MACRO_DEBUG_TRACE \|\| QUEUE_MACRO_DEBUG_TRASH */
167
168	#ifdef __cplusplus
169	/*
170	* In C++ there can be structure lists and class lists:
171	*/
172	#define QUEUE_TYPEOF(type) type
173	#else
174	#define QUEUE_TYPEOF(type) struct type
175	#endif
176
177	/*
178	* Singly-linked List declarations.
179	*/
180	#define SLIST_HEAD(name, type) \
181	struct name { \
182	struct type slh_first; / first element */ \
183	}
184
185	#define SLIST_CLASS_HEAD(name, type) \
186	struct name { \
187	class type slh_first; / first element */ \
188	}
189
190	#define SLIST_HEAD_INITIALIZER(head) \
191	{ NULL }
192
193	#define SLIST_ENTRY(type) \
194	struct { \
195	struct type sle_next; / next element */ \
196	}
197
198	#define SLIST_CLASS_ENTRY(type) \
199	struct { \
200	class type sle_next; / next element */ \
201	}
202
203	/*
204	* Singly-linked List functions.
205	*/
206	#if (defined(_KERNEL) && defined(INVARIANTS))
207	#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do { \
208	if (*(prevp) != (elm)) \
209	panic("Bad prevptr *(%p) == %p != %p", \
210	(prevp), *(prevp), (elm)); \
211	} while (0)
212	#else
213	#define QMD_SLIST_CHECK_PREVPTR(prevp, elm)
214	#endif
215
216	#define SLIST_CONCAT(head1, head2, type, field) do { \
217	QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \
218	if (curelm == NULL) { \
219	if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \
220	SLIST_INIT(head2); \
221	} else if (SLIST_FIRST(head2) != NULL) { \
222	while (SLIST_NEXT(curelm, field) != NULL) \
223	curelm = SLIST_NEXT(curelm, field); \
224	SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \
225	SLIST_INIT(head2); \
226	} \
227	} while (0)
228
229	#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
230
231	#define SLIST_FIRST(head) ((head)->slh_first)
232
233	#define SLIST_FOREACH(var, head, field) \
234	for ((var) = SLIST_FIRST((head)); \
235	(var); \
236	(var) = SLIST_NEXT((var), field))
237
238	#define SLIST_FOREACH_FROM(var, head, field) \
239	for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
240	(var); \
241	(var) = SLIST_NEXT((var), field))
242
243	#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
244	for ((var) = SLIST_FIRST((head)); \
245	(var) && ((tvar) = SLIST_NEXT((var), field), 1); \
246	(var) = (tvar))
247
248	#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
249	for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
250	(var) && ((tvar) = SLIST_NEXT((var), field), 1); \
251	(var) = (tvar))
252
253	#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
254	for ((varp) = &SLIST_FIRST((head)); \
255	((var) = *(varp)) != NULL; \
256	(varp) = &SLIST_NEXT((var), field))
257
258	#define SLIST_INIT(head) do { \
259	SLIST_FIRST((head)) = NULL; \
260	} while (0)
261
262	#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
263	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
264	SLIST_NEXT((slistelm), field) = (elm); \
265	} while (0)
266
267	#define SLIST_INSERT_HEAD(head, elm, field) do { \
268	SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
269	SLIST_FIRST((head)) = (elm); \
270	} while (0)
271
272	#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
273
274	#define SLIST_REMOVE(head, elm, type, field) do { \
275	QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
276	if (SLIST_FIRST((head)) == (elm)) { \
277	SLIST_REMOVE_HEAD((head), field); \
278	} \
279	else { \
280	QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \
281	while (SLIST_NEXT(curelm, field) != (elm)) \
282	curelm = SLIST_NEXT(curelm, field); \
283	SLIST_REMOVE_AFTER(curelm, field); \
284	} \
285	TRASHIT(*oldnext); \
286	} while (0)
287
288	#define SLIST_REMOVE_AFTER(elm, field) do { \
289	SLIST_NEXT(elm, field) = \
290	SLIST_NEXT(SLIST_NEXT(elm, field), field); \
291	} while (0)
292
293	#define SLIST_REMOVE_HEAD(head, field) do { \
294	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
295	} while (0)
296
297	#define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \
298	QMD_SLIST_CHECK_PREVPTR(prevp, elm); \
299	*(prevp) = SLIST_NEXT(elm, field); \
300	TRASHIT((elm)->field.sle_next); \
301	} while (0)
302
303	#define SLIST_SWAP(head1, head2, type) do { \
304	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \
305	SLIST_FIRST(head1) = SLIST_FIRST(head2); \
306	SLIST_FIRST(head2) = swap_first; \
307	} while (0)
308
309	/*
310	* Singly-linked Tail queue declarations.
311	*/
312	#define STAILQ_HEAD(name, type) \
313	struct name { \
314	struct type stqh_first;/ first element */ \
315	struct type *stqh_last;/ addr of last next element */ \
316	}
317
318	#define STAILQ_CLASS_HEAD(name, type) \
319	struct name { \
320	class type stqh_first; / first element */ \
321	class type *stqh_last; / addr of last next element */ \
322	}
323
324	#define STAILQ_HEAD_INITIALIZER(head) \
325	{ NULL, &(head).stqh_first }
326
327	#define STAILQ_ENTRY(type) \
328	struct { \
329	struct type stqe_next; / next element */ \
330	}
331
332	#define STAILQ_CLASS_ENTRY(type) \
333	struct { \
334	class type stqe_next; / next element */ \
335	}
336
337	/*
338	* Singly-linked Tail queue functions.
339	*/
340	#define STAILQ_CONCAT(head1, head2) do { \
341	if (!STAILQ_EMPTY((head2))) { \
342	*(head1)->stqh_last = (head2)->stqh_first; \
343	(head1)->stqh_last = (head2)->stqh_last; \
344	STAILQ_INIT((head2)); \
345	} \
346	} while (0)
347
348	#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
349
350	#define STAILQ_FIRST(head) ((head)->stqh_first)
351
352	#define STAILQ_FOREACH(var, head, field) \
353	for((var) = STAILQ_FIRST((head)); \
354	(var); \
355	(var) = STAILQ_NEXT((var), field))
356
357	#define STAILQ_FOREACH_FROM(var, head, field) \
358	for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
359	(var); \
360	(var) = STAILQ_NEXT((var), field))
361
362	#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
363	for ((var) = STAILQ_FIRST((head)); \
364	(var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
365	(var) = (tvar))
366
367	#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
368	for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
369	(var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
370	(var) = (tvar))
371
372	#define STAILQ_INIT(head) do { \
373	STAILQ_FIRST((head)) = NULL; \
374	(head)->stqh_last = &STAILQ_FIRST((head)); \
375	} while (0)
376
377	#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
378	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
379	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
380	STAILQ_NEXT((tqelm), field) = (elm); \
381	} while (0)
382
383	#define STAILQ_INSERT_HEAD(head, elm, field) do { \
384	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
385	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
386	STAILQ_FIRST((head)) = (elm); \
387	} while (0)
388
389	#define STAILQ_INSERT_TAIL(head, elm, field) do { \
390	STAILQ_NEXT((elm), field) = NULL; \
391	*(head)->stqh_last = (elm); \
392	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
393	} while (0)
394
395	#define STAILQ_LAST(head, type, field) \
396	(STAILQ_EMPTY((head)) ? NULL : \
397	__containerof((head)->stqh_last, \
398	QUEUE_TYPEOF(type), field.stqe_next))
399
400	#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
401
402	#define STAILQ_REMOVE(head, elm, type, field) do { \
403	QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
404	if (STAILQ_FIRST((head)) == (elm)) { \
405	STAILQ_REMOVE_HEAD((head), field); \
406	} \
407	else { \
408	QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \
409	while (STAILQ_NEXT(curelm, field) != (elm)) \
410	curelm = STAILQ_NEXT(curelm, field); \
411	STAILQ_REMOVE_AFTER(head, curelm, field); \
412	} \
413	TRASHIT(*oldnext); \
414	} while (0)
415
416	#define STAILQ_REMOVE_AFTER(head, elm, field) do { \
417	if ((STAILQ_NEXT(elm, field) = \
418	STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
419	(head)->stqh_last = &STAILQ_NEXT((elm), field); \
420	} while (0)
421
422	#define STAILQ_REMOVE_HEAD(head, field) do { \
423	if ((STAILQ_FIRST((head)) = \
424	STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
425	(head)->stqh_last = &STAILQ_FIRST((head)); \
426	} while (0)
427
428	#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
429	if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
430	(head)->stqh_last = &STAILQ_FIRST((head)); \
431	} while (0)
432
433	#define STAILQ_SWAP(head1, head2, type) do { \
434	QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \
435	QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \
436	STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
437	(head1)->stqh_last = (head2)->stqh_last; \
438	STAILQ_FIRST(head2) = swap_first; \
439	(head2)->stqh_last = swap_last; \
440	if (STAILQ_EMPTY(head1)) \
441	(head1)->stqh_last = &STAILQ_FIRST(head1); \
442	if (STAILQ_EMPTY(head2)) \
443	(head2)->stqh_last = &STAILQ_FIRST(head2); \
444	} while (0)
445
446
447	/*
448	* List declarations.
449	*/
450	#define LIST_HEAD(name, type) \
451	struct name { \
452	struct type lh_first; / first element */ \
453	}
454
455	#define LIST_CLASS_HEAD(name, type) \
456	struct name { \
457	class type lh_first; / first element */ \
458	}
459
460	#define LIST_HEAD_INITIALIZER(head) \
461	{ NULL }
462
463	#define LIST_ENTRY(type) \
464	struct { \
465	struct type le_next; / next element */ \
466	struct type *le_prev; / address of previous next element */ \
467	}
468
469	#define LIST_CLASS_ENTRY(type) \
470	struct { \
471	class type le_next; / next element */ \
472	class type *le_prev; / address of previous next element */ \
473	}
474
475	/*
476	* List functions.
477	*/
478
479	#if (defined(_KERNEL) && defined(INVARIANTS))
480	/*
481	* QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME)
482	*
483	* If the list is non-empty, validates that the first element of the list
484	* points back at 'head.'
485	*/
486	#define QMD_LIST_CHECK_HEAD(head, field) do { \
487	if (LIST_FIRST((head)) != NULL && \
488	LIST_FIRST((head))->field.le_prev != \
489	&LIST_FIRST((head))) \
490	panic("Bad list head %p first->prev != head", (head)); \
491	} while (0)
492
493	/*
494	* QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME)
495	*
496	* If an element follows 'elm' in the list, validates that the next element
497	* points back at 'elm.'
498	*/
499	#define QMD_LIST_CHECK_NEXT(elm, field) do { \
500	if (LIST_NEXT((elm), field) != NULL && \
501	LIST_NEXT((elm), field)->field.le_prev != \
502	&((elm)->field.le_next)) \
503	panic("Bad link elm %p next->prev != elm", (elm)); \
504	} while (0)
505
506	/*
507	* QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME)
508	*
509	* Validates that the previous element (or head of the list) points to 'elm.'
510	*/
511	#define QMD_LIST_CHECK_PREV(elm, field) do { \
512	if (*(elm)->field.le_prev != (elm)) \
513	panic("Bad link elm %p prev->next != elm", (elm)); \
514	} while (0)
515	#else
516	#define QMD_LIST_CHECK_HEAD(head, field)
517	#define QMD_LIST_CHECK_NEXT(elm, field)
518	#define QMD_LIST_CHECK_PREV(elm, field)
519	#endif /* (_KERNEL && INVARIANTS) */
520
521	#define LIST_CONCAT(head1, head2, type, field) do { \
522	QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \
523	if (curelm == NULL) { \
524	if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \
525	LIST_FIRST(head2)->field.le_prev = \
526	&LIST_FIRST((head1)); \
527	LIST_INIT(head2); \
528	} \
529	} else if (LIST_FIRST(head2) != NULL) { \
530	while (LIST_NEXT(curelm, field) != NULL) \
531	curelm = LIST_NEXT(curelm, field); \
532	LIST_NEXT(curelm, field) = LIST_FIRST(head2); \
533	LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
534	LIST_INIT(head2); \
535	} \
536	} while (0)
537
538	#define LIST_EMPTY(head) ((head)->lh_first == NULL)
539
540	#define LIST_FIRST(head) ((head)->lh_first)
541
542	#define LIST_FOREACH(var, head, field) \
543	for ((var) = LIST_FIRST((head)); \
544	(var); \
545	(var) = LIST_NEXT((var), field))
546
547	#define LIST_FOREACH_FROM(var, head, field) \
548	for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
549	(var); \
550	(var) = LIST_NEXT((var), field))
551
552	#define LIST_FOREACH_SAFE(var, head, field, tvar) \
553	for ((var) = LIST_FIRST((head)); \
554	(var) && ((tvar) = LIST_NEXT((var), field), 1); \
555	(var) = (tvar))
556
557	#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
558	for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
559	(var) && ((tvar) = LIST_NEXT((var), field), 1); \
560	(var) = (tvar))
561
562	#define LIST_INIT(head) do { \
563	LIST_FIRST((head)) = NULL; \
564	} while (0)
565
566	#define LIST_INSERT_AFTER(listelm, elm, field) do { \
567	QMD_LIST_CHECK_NEXT(listelm, field); \
568	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
569	LIST_NEXT((listelm), field)->field.le_prev = \
570	&LIST_NEXT((elm), field); \
571	LIST_NEXT((listelm), field) = (elm); \
572	(elm)->field.le_prev = &LIST_NEXT((listelm), field); \
573	} while (0)
574
575	#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
576	QMD_LIST_CHECK_PREV(listelm, field); \
577	(elm)->field.le_prev = (listelm)->field.le_prev; \
578	LIST_NEXT((elm), field) = (listelm); \
579	*(listelm)->field.le_prev = (elm); \
580	(listelm)->field.le_prev = &LIST_NEXT((elm), field); \
581	} while (0)
582
583	#define LIST_INSERT_HEAD(head, elm, field) do { \
584	QMD_LIST_CHECK_HEAD((head), field); \
585	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
586	LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
587	LIST_FIRST((head)) = (elm); \
588	(elm)->field.le_prev = &LIST_FIRST((head)); \
589	} while (0)
590
591	#define LIST_NEXT(elm, field) ((elm)->field.le_next)
592
593	#define LIST_PREV(elm, head, type, field) \
594	((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
595	__containerof((elm)->field.le_prev, \
596	QUEUE_TYPEOF(type), field.le_next))
597
598	#define LIST_REMOVE(elm, field) do { \
599	QMD_SAVELINK(oldnext, (elm)->field.le_next); \
600	QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
601	QMD_LIST_CHECK_NEXT(elm, field); \
602	QMD_LIST_CHECK_PREV(elm, field); \
603	if (LIST_NEXT((elm), field) != NULL) \
604	LIST_NEXT((elm), field)->field.le_prev = \
605	(elm)->field.le_prev; \
606	*(elm)->field.le_prev = LIST_NEXT((elm), field); \
607	TRASHIT(*oldnext); \
608	TRASHIT(*oldprev); \
609	} while (0)
610
611	#define LIST_SWAP(head1, head2, type, field) do { \
612	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \
613	LIST_FIRST((head1)) = LIST_FIRST((head2)); \
614	LIST_FIRST((head2)) = swap_tmp; \
615	if ((swap_tmp = LIST_FIRST((head1))) != NULL) \
616	swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
617	if ((swap_tmp = LIST_FIRST((head2))) != NULL) \
618	swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
619	} while (0)
620
621	/*
622	* Tail queue declarations.
623	*/
624	#define TAILQ_HEAD(name, type) \
625	struct name { \
626	struct type tqh_first; / first element */ \
627	struct type *tqh_last; / addr of last next element */ \
628	TRACEBUF \
629	}
630
631	#define TAILQ_CLASS_HEAD(name, type) \
632	struct name { \
633	class type tqh_first; / first element */ \
634	class type *tqh_last; / addr of last next element */ \
635	TRACEBUF \
636	}
637
638	#define TAILQ_HEAD_INITIALIZER(head) \
639	{ NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
640
641	#define TAILQ_ENTRY(type) \
642	struct { \
643	struct type tqe_next; / next element */ \
644	struct type *tqe_prev; / address of previous next element */ \
645	TRACEBUF \
646	}
647
648	#define TAILQ_CLASS_ENTRY(type) \
649	struct { \
650	class type tqe_next; / next element */ \
651	class type *tqe_prev; / address of previous next element */ \
652	TRACEBUF \
653	}
654
655	/*
656	* Tail queue functions.
657	*/
658	#if (defined(_KERNEL) && defined(INVARIANTS))
659	/*
660	* QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
661	*
662	* If the tailq is non-empty, validates that the first element of the tailq
663	* points back at 'head.'
664	*/
665	#define QMD_TAILQ_CHECK_HEAD(head, field) do { \
666	if (!TAILQ_EMPTY(head) && \
667	TAILQ_FIRST((head))->field.tqe_prev != \
668	&TAILQ_FIRST((head))) \
669	panic("Bad tailq head %p first->prev != head", (head)); \
670	} while (0)
671
672	/*
673	* QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
674	*
675	* Validates that the tail of the tailq is a pointer to pointer to NULL.
676	*/
677	#define QMD_TAILQ_CHECK_TAIL(head, field) do { \
678	if (*(head)->tqh_last != NULL) \
679	panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
680	} while (0)
681
682	/*
683	* QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME)
684	*
685	* If an element follows 'elm' in the tailq, validates that the next element
686	* points back at 'elm.'
687	*/
688	#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
689	if (TAILQ_NEXT((elm), field) != NULL && \
690	TAILQ_NEXT((elm), field)->field.tqe_prev != \
691	&((elm)->field.tqe_next)) \
692	panic("Bad link elm %p next->prev != elm", (elm)); \
693	} while (0)
694
695	/*
696	* QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME)
697	*
698	* Validates that the previous element (or head of the tailq) points to 'elm.'
699	*/
700	#define QMD_TAILQ_CHECK_PREV(elm, field) do { \
701	if (*(elm)->field.tqe_prev != (elm)) \
702	panic("Bad link elm %p prev->next != elm", (elm)); \
703	} while (0)
704	#else
705	#define QMD_TAILQ_CHECK_HEAD(head, field)
706	#define QMD_TAILQ_CHECK_TAIL(head, headname)
707	#define QMD_TAILQ_CHECK_NEXT(elm, field)
708	#define QMD_TAILQ_CHECK_PREV(elm, field)
709	#endif /* (_KERNEL && INVARIANTS) */
710
711	#define TAILQ_CONCAT(head1, head2, field) do { \
712	if (!TAILQ_EMPTY(head2)) { \
713	*(head1)->tqh_last = (head2)->tqh_first; \
714	(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
715	(head1)->tqh_last = (head2)->tqh_last; \
716	TAILQ_INIT((head2)); \
717	QMD_TRACE_HEAD(head1); \
718	QMD_TRACE_HEAD(head2); \
719	} \
720	} while (0)
721
722	#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
723
724	#define TAILQ_FIRST(head) ((head)->tqh_first)
725
726	#define TAILQ_FOREACH(var, head, field) \
727	for ((var) = TAILQ_FIRST((head)); \
728	(var); \
729	(var) = TAILQ_NEXT((var), field))
730
731	#define TAILQ_FOREACH_FROM(var, head, field) \
732	for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
733	(var); \
734	(var) = TAILQ_NEXT((var), field))
735
736	#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
737	for ((var) = TAILQ_FIRST((head)); \
738	(var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
739	(var) = (tvar))
740
741	#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
742	for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
743	(var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
744	(var) = (tvar))
745
746	#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
747	for ((var) = TAILQ_LAST((head), headname); \
748	(var); \
749	(var) = TAILQ_PREV((var), headname, field))
750
751	#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \
752	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
753	(var); \
754	(var) = TAILQ_PREV((var), headname, field))
755
756	#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
757	for ((var) = TAILQ_LAST((head), headname); \
758	(var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
759	(var) = (tvar))
760
761	#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
762	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
763	(var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
764	(var) = (tvar))
765
766	#define TAILQ_INIT(head) do { \
767	TAILQ_FIRST((head)) = NULL; \
768	(head)->tqh_last = &TAILQ_FIRST((head)); \
769	QMD_TRACE_HEAD(head); \
770	} while (0)
771
772	#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
773	QMD_TAILQ_CHECK_NEXT(listelm, field); \
774	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
775	TAILQ_NEXT((elm), field)->field.tqe_prev = \
776	&TAILQ_NEXT((elm), field); \
777	else { \
778	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
779	QMD_TRACE_HEAD(head); \
780	} \
781	TAILQ_NEXT((listelm), field) = (elm); \
782	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
783	QMD_TRACE_ELEM(&(elm)->field); \
784	QMD_TRACE_ELEM(&(listelm)->field); \
785	} while (0)
786
787	#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
788	QMD_TAILQ_CHECK_PREV(listelm, field); \
789	(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
790	TAILQ_NEXT((elm), field) = (listelm); \
791	*(listelm)->field.tqe_prev = (elm); \
792	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
793	QMD_TRACE_ELEM(&(elm)->field); \
794	QMD_TRACE_ELEM(&(listelm)->field); \
795	} while (0)
796
797	#define TAILQ_INSERT_HEAD(head, elm, field) do { \
798	QMD_TAILQ_CHECK_HEAD(head, field); \
799	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
800	TAILQ_FIRST((head))->field.tqe_prev = \
801	&TAILQ_NEXT((elm), field); \
802	else \
803	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
804	TAILQ_FIRST((head)) = (elm); \
805	(elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
806	QMD_TRACE_HEAD(head); \
807	QMD_TRACE_ELEM(&(elm)->field); \
808	} while (0)
809
810	#define TAILQ_INSERT_TAIL(head, elm, field) do { \
811	QMD_TAILQ_CHECK_TAIL(head, field); \
812	TAILQ_NEXT((elm), field) = NULL; \
813	(elm)->field.tqe_prev = (head)->tqh_last; \
814	*(head)->tqh_last = (elm); \
815	(head)->tqh_last = &TAILQ_NEXT((elm), field); \
816	QMD_TRACE_HEAD(head); \
817	QMD_TRACE_ELEM(&(elm)->field); \
818	} while (0)
819
820	#define TAILQ_LAST(head, headname) \
821	((((struct headname )((head)->tqh_last))->tqh_last))
822
823	#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
824
825	#define TAILQ_PREV(elm, headname, field) \
826	((((struct headname )((elm)->field.tqe_prev))->tqh_last))
827
828	#define TAILQ_REMOVE(head, elm, field) do { \
829	QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
830	QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
831	QMD_TAILQ_CHECK_NEXT(elm, field); \
832	QMD_TAILQ_CHECK_PREV(elm, field); \
833	if ((TAILQ_NEXT((elm), field)) != NULL) \
834	TAILQ_NEXT((elm), field)->field.tqe_prev = \
835	(elm)->field.tqe_prev; \
836	else { \
837	(head)->tqh_last = (elm)->field.tqe_prev; \
838	QMD_TRACE_HEAD(head); \
839	} \
840	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
841	TRASHIT(*oldnext); \
842	TRASHIT(*oldprev); \
843	QMD_TRACE_ELEM(&(elm)->field); \
844	} while (0)
845
846	#define TAILQ_SWAP(head1, head2, type, field) do { \
847	QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \
848	QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \
849	(head1)->tqh_first = (head2)->tqh_first; \
850	(head1)->tqh_last = (head2)->tqh_last; \
851	(head2)->tqh_first = swap_first; \
852	(head2)->tqh_last = swap_last; \
853	if ((swap_first = (head1)->tqh_first) != NULL) \
854	swap_first->field.tqe_prev = &(head1)->tqh_first; \
855	else \
856	(head1)->tqh_last = &(head1)->tqh_first; \
857	if ((swap_first = (head2)->tqh_first) != NULL) \
858	swap_first->field.tqe_prev = &(head2)->tqh_first; \
859	else \
860	(head2)->tqh_last = &(head2)->tqh_first; \
861	} while (0)
862
863	#ifdef _KERNEL
864
865	/*
866	* XXX insque() and remque() are an old way of handling certain queues.
867	* They bogusly assumes that all queue heads look alike.
868	*/
869
870	struct quehead {
871	struct quehead *qh_link;
872	struct quehead *qh_rlink;
873	};
874
875	#ifdef __GNUC__
876
877	static __inline void
878	insque(void a, void b)
879	{
880	struct quehead element = (struct quehead )a,
881	head = (struct quehead )b;
882
883	element->qh_link = head->qh_link;
884	element->qh_rlink = head;
885	head->qh_link = element;
886	element->qh_link->qh_rlink = element;
887	}
888
889	static __inline void
890	remque(void *a)
891	{
892	struct quehead element = (struct quehead )a;
893
894	element->qh_link->qh_rlink = element->qh_rlink;
895	element->qh_rlink->qh_link = element->qh_link;
896	element->qh_rlink = 0;
897	}
898
899	#else /* !__GNUC__ */
900
901	void insque(void a, void b);
902	void remque(void *a);
903
904	#endif /* __GNUC__ */
905
906	#endif /* _KERNEL */
907
908	#endif /* !_SYS_QUEUE_H_ */

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

Context Navigation

source: trunk/libs/newlib/src/newlib/libc/include/sys/queue.h @ 444

Download in other formats: