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: releng/11.0/sys/sys/queue.h 284915 2015-06-28 21:06:45Z hselasky $
31: */
32:
33: #ifndef _SYS_QUEUE_H_
34: #define _SYS_QUEUE_H_
35:
36: #include "config.h"
37:
38: #ifdef HAVE_SYS_CDEFS_H
39: #include <sys/cdefs.h>
40: #endif
41:
42: /*
43: * This file defines four types of data structures: singly-linked lists,
44: * singly-linked tail queues, lists and tail queues.
45: *
46: * A singly-linked list is headed by a single forward pointer. The elements
47: * are singly linked for minimum space and pointer manipulation overhead at
48: * the expense of O(n) removal for arbitrary elements. New elements can be
49: * added to the list after an existing element or at the head of the list.
50: * Elements being removed from the head of the list should use the explicit
51: * macro for this purpose for optimum efficiency. A singly-linked list may
52: * only be traversed in the forward direction. Singly-linked lists are ideal
53: * for applications with large datasets and few or no removals or for
54: * implementing a LIFO queue.
55: *
56: * A singly-linked tail queue is headed by a pair of pointers, one to the
57: * head of the list and the other to the tail of the list. The elements are
58: * singly linked for minimum space and pointer manipulation overhead at the
59: * expense of O(n) removal for arbitrary elements. New elements can be added
60: * to the list after an existing element, at the head of the list, or at the
61: * end of the list. Elements being removed from the head of the tail queue
62: * should use the explicit macro for this purpose for optimum efficiency.
63: * A singly-linked tail queue may only be traversed in the forward direction.
64: * Singly-linked tail queues are ideal for applications with large datasets
65: * and few or no removals or for implementing a FIFO queue.
66: *
67: * A list is headed by a single forward pointer (or an array of forward
68: * pointers for a hash table header). The elements are doubly linked
69: * so that an arbitrary element can be removed without a need to
70: * traverse the list. New elements can be added to the list before
71: * or after an existing element or at the head of the list. A list
72: * may be traversed in either direction.
73: *
74: * A tail queue is headed by a pair of pointers, one to the head of the
75: * list and the other to the tail of the list. The elements are doubly
76: * linked so that an arbitrary element can be removed without a need to
77: * traverse the list. New elements can be added to the list before or
78: * after an existing element, at the head of the list, or at the end of
79: * the list. A tail queue may be traversed in either direction.
80: *
81: * For details on the use of these macros, see the queue(3) manual page.
82: *
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 - - + +
109: * _REMOVE_AFTER + - + -
110: * _REMOVE_HEAD + - + -
111: * _REMOVE + + + +
112: * _SWAP + + + +
113: *
114: */
115: #ifdef QUEUE_MACRO_DEBUG
116: /* Store the last 2 places the queue element or head was altered */
117: struct qm_trace {
118: unsigned long lastline;
119: unsigned long prevline;
120: const char *lastfile;
121: const char *prevfile;
122: };
123:
124: #define TRACEBUF struct qm_trace trace;
125: #define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } ,
126: #define TRASHIT(x) do {(x) = (void *)-1;} while (0)
127: #define QMD_SAVELINK(name, link) void **name = (void *)&(link)
128:
129: #define QMD_TRACE_HEAD(head) do { \
130: (head)->trace.prevline = (head)->trace.lastline; \
131: (head)->trace.prevfile = (head)->trace.lastfile; \
132: (head)->trace.lastline = __LINE__; \
133: (head)->trace.lastfile = __FILE__; \
134: } while (0)
135:
136: #define QMD_TRACE_ELEM(elem) do { \
137: (elem)->trace.prevline = (elem)->trace.lastline; \
138: (elem)->trace.prevfile = (elem)->trace.lastfile; \
139: (elem)->trace.lastline = __LINE__; \
140: (elem)->trace.lastfile = __FILE__; \
141: } while (0)
142:
143: #else
144: #define QMD_TRACE_ELEM(elem)
145: #define QMD_TRACE_HEAD(head)
146: #define QMD_SAVELINK(name, link)
147: #define TRACEBUF
148: #define TRACEBUF_INITIALIZER
149: #define TRASHIT(x)
150: #endif /* QUEUE_MACRO_DEBUG */
151:
152: #ifdef __cplusplus
153: /*
154: * In C++ there can be structure lists and class lists:
155: */
156: #define QUEUE_TYPEOF(type) type
157: #else
158: #define QUEUE_TYPEOF(type) struct type
159: #endif
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_CLASS_HEAD(name, type) \
170: struct name { \
171: class type *slh_first; /* first element */ \
172: }
173:
174: #define SLIST_HEAD_INITIALIZER(head) \
175: { NULL }
176:
177: #define SLIST_ENTRY(type) \
178: struct { \
179: struct type *sle_next; /* next element */ \
180: }
181:
182: #define SLIST_CLASS_ENTRY(type) \
183: struct { \
184: class 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_FROM(var, head, field) \
200: for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
201: (var); \
202: (var) = SLIST_NEXT((var), field))
203:
204: #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
205: for ((var) = SLIST_FIRST((head)); \
206: (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
207: (var) = (tvar))
208:
209: #define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
210: for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
211: (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
212: (var) = (tvar))
213:
214: #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
215: for ((varp) = &SLIST_FIRST((head)); \
216: ((var) = *(varp)) != NULL; \
217: (varp) = &SLIST_NEXT((var), field))
218:
219: #define SLIST_INIT(head) do { \
220: SLIST_FIRST((head)) = NULL; \
221: } while (0)
222:
223: #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
224: SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
225: SLIST_NEXT((slistelm), field) = (elm); \
226: } while (0)
227:
228: #define SLIST_INSERT_HEAD(head, elm, field) do { \
229: SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
230: SLIST_FIRST((head)) = (elm); \
231: } while (0)
232:
233: #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
234:
235: #define SLIST_REMOVE(head, elm, type, field) do { \
236: QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
237: if (SLIST_FIRST((head)) == (elm)) { \
238: SLIST_REMOVE_HEAD((head), field); \
239: } \
240: else { \
241: QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \
242: while (SLIST_NEXT(curelm, field) != (elm)) \
243: curelm = SLIST_NEXT(curelm, field); \
244: SLIST_REMOVE_AFTER(curelm, field); \
245: } \
246: TRASHIT(*oldnext); \
247: } while (0)
248:
249: #define SLIST_REMOVE_AFTER(elm, field) do { \
250: SLIST_NEXT(elm, field) = \
251: SLIST_NEXT(SLIST_NEXT(elm, field), field); \
252: } while (0)
253:
254: #define SLIST_REMOVE_HEAD(head, field) do { \
255: SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
256: } while (0)
257:
258: #define SLIST_SWAP(head1, head2, type) do { \
259: QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \
260: SLIST_FIRST(head1) = SLIST_FIRST(head2); \
261: SLIST_FIRST(head2) = swap_first; \
262: } while (0)
263:
264: /*
265: * Singly-linked Tail queue declarations.
266: */
267: #define STAILQ_HEAD(name, type) \
268: struct name { \
269: struct type *stqh_first;/* first element */ \
270: struct type **stqh_last;/* addr of last next element */ \
271: }
272:
273: #define STAILQ_CLASS_HEAD(name, type) \
274: struct name { \
275: class type *stqh_first; /* first element */ \
276: class type **stqh_last; /* addr of last next element */ \
277: }
278:
279: #define STAILQ_HEAD_INITIALIZER(head) \
280: { NULL, &(head).stqh_first }
281:
282: #define STAILQ_ENTRY(type) \
283: struct { \
284: struct type *stqe_next; /* next element */ \
285: }
286:
287: #define STAILQ_CLASS_ENTRY(type) \
288: struct { \
289: class type *stqe_next; /* next element */ \
290: }
291:
292: /*
293: * Singly-linked Tail queue functions.
294: */
295: #define STAILQ_CONCAT(head1, head2) do { \
296: if (!STAILQ_EMPTY((head2))) { \
297: *(head1)->stqh_last = (head2)->stqh_first; \
298: (head1)->stqh_last = (head2)->stqh_last; \
299: STAILQ_INIT((head2)); \
300: } \
301: } while (0)
302:
303: #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
304:
305: #define STAILQ_FIRST(head) ((head)->stqh_first)
306:
307: #define STAILQ_FOREACH(var, head, field) \
308: for ((var) = STAILQ_FIRST((head)); \
309: (var); \
310: (var) = STAILQ_NEXT((var), field))
311:
312: #define STAILQ_FOREACH_FROM(var, head, field) \
313: for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
314: (var); \
315: (var) = STAILQ_NEXT((var), field))
316:
317: #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
318: for ((var) = STAILQ_FIRST((head)); \
319: (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
320: (var) = (tvar))
321:
322: #define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
323: for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
324: (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
325: (var) = (tvar))
326:
327: #define STAILQ_INIT(head) do { \
328: STAILQ_FIRST((head)) = NULL; \
329: (head)->stqh_last = &STAILQ_FIRST((head)); \
330: } while (0)
331:
332: #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
333: if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
334: (head)->stqh_last = &STAILQ_NEXT((elm), field); \
335: STAILQ_NEXT((tqelm), field) = (elm); \
336: } while (0)
337:
338: #define STAILQ_INSERT_HEAD(head, elm, field) do { \
339: if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
340: (head)->stqh_last = &STAILQ_NEXT((elm), field); \
341: STAILQ_FIRST((head)) = (elm); \
342: } while (0)
343:
344: #define STAILQ_INSERT_TAIL(head, elm, field) do { \
345: STAILQ_NEXT((elm), field) = NULL; \
346: *(head)->stqh_last = (elm); \
347: (head)->stqh_last = &STAILQ_NEXT((elm), field); \
348: } while (0)
349:
350: #define STAILQ_LAST(head, type, field) \
351: (STAILQ_EMPTY((head)) ? NULL : \
352: __containerof((head)->stqh_last, \
353: QUEUE_TYPEOF(type), field.stqe_next))
354:
355: #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
356:
357: #define STAILQ_REMOVE(head, elm, type, field) do { \
358: QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
359: if (STAILQ_FIRST((head)) == (elm)) { \
360: STAILQ_REMOVE_HEAD((head), field); \
361: } \
362: else { \
363: QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \
364: while (STAILQ_NEXT(curelm, field) != (elm)) \
365: curelm = STAILQ_NEXT(curelm, field); \
366: STAILQ_REMOVE_AFTER(head, curelm, field); \
367: } \
368: TRASHIT(*oldnext); \
369: } while (0)
370:
371: #define STAILQ_REMOVE_AFTER(head, elm, field) do { \
372: if ((STAILQ_NEXT(elm, field) = \
373: STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
374: (head)->stqh_last = &STAILQ_NEXT((elm), field); \
375: } while (0)
376:
377: #define STAILQ_REMOVE_HEAD(head, field) do { \
378: if ((STAILQ_FIRST((head)) = \
379: STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
380: (head)->stqh_last = &STAILQ_FIRST((head)); \
381: } while (0)
382:
383: #define STAILQ_SWAP(head1, head2, type) do { \
384: QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \
385: QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \
386: STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
387: (head1)->stqh_last = (head2)->stqh_last; \
388: STAILQ_FIRST(head2) = swap_first; \
389: (head2)->stqh_last = swap_last; \
390: if (STAILQ_EMPTY(head1)) \
391: (head1)->stqh_last = &STAILQ_FIRST(head1); \
392: if (STAILQ_EMPTY(head2)) \
393: (head2)->stqh_last = &STAILQ_FIRST(head2); \
394: } while (0)
395:
396:
397: /*
398: * List declarations.
399: */
400: #define LIST_HEAD(name, type) \
401: struct name { \
402: struct type *lh_first; /* first element */ \
403: }
404:
405: #define LIST_CLASS_HEAD(name, type) \
406: struct name { \
407: class type *lh_first; /* first element */ \
408: }
409:
410: #define LIST_HEAD_INITIALIZER(head) \
411: { NULL }
412:
413: #define LIST_ENTRY(type) \
414: struct { \
415: struct type *le_next; /* next element */ \
416: struct type **le_prev; /* address of previous next element */ \
417: }
418:
419: #define LIST_CLASS_ENTRY(type) \
420: struct { \
421: class type *le_next; /* next element */ \
422: class type **le_prev; /* address of previous next element */ \
423: }
424:
425: /*
426: * List functions.
427: */
428:
429: #if (defined(_KERNEL) && defined(INVARIANTS))
430: #define QMD_LIST_CHECK_HEAD(head, field) do { \
431: if (LIST_FIRST((head)) != NULL && \
432: LIST_FIRST((head))->field.le_prev != \
433: &LIST_FIRST((head))) \
434: panic("Bad list head %p first->prev != head", (head)); \
435: } while (0)
436:
437: #define QMD_LIST_CHECK_NEXT(elm, field) do { \
438: if (LIST_NEXT((elm), field) != NULL && \
439: LIST_NEXT((elm), field)->field.le_prev != \
440: &((elm)->field.le_next)) \
441: panic("Bad link elm %p next->prev != elm", (elm)); \
442: } while (0)
443:
444: #define QMD_LIST_CHECK_PREV(elm, field) do { \
445: if (*(elm)->field.le_prev != (elm)) \
446: panic("Bad link elm %p prev->next != elm", (elm)); \
447: } while (0)
448: #else
449: #define QMD_LIST_CHECK_HEAD(head, field)
450: #define QMD_LIST_CHECK_NEXT(elm, field)
451: #define QMD_LIST_CHECK_PREV(elm, field)
452: #endif /* (_KERNEL && INVARIANTS) */
453:
454: #define LIST_EMPTY(head) ((head)->lh_first == NULL)
455:
456: #define LIST_FIRST(head) ((head)->lh_first)
457:
458: #define LIST_FOREACH(var, head, field) \
459: for ((var) = LIST_FIRST((head)); \
460: (var); \
461: (var) = LIST_NEXT((var), field))
462:
463: #define LIST_FOREACH_FROM(var, head, field) \
464: for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
465: (var); \
466: (var) = LIST_NEXT((var), field))
467:
468: #define LIST_FOREACH_SAFE(var, head, field, tvar) \
469: for ((var) = LIST_FIRST((head)); \
470: (var) && ((tvar) = LIST_NEXT((var), field), 1); \
471: (var) = (tvar))
472:
473: #define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
474: for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
475: (var) && ((tvar) = LIST_NEXT((var), field), 1); \
476: (var) = (tvar))
477:
478: #define LIST_INIT(head) do { \
479: LIST_FIRST((head)) = NULL; \
480: } while (0)
481:
482: #define LIST_INSERT_AFTER(listelm, elm, field) do { \
483: QMD_LIST_CHECK_NEXT(listelm, field); \
484: if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
485: LIST_NEXT((listelm), field)->field.le_prev = \
486: &LIST_NEXT((elm), field); \
487: LIST_NEXT((listelm), field) = (elm); \
488: (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
489: } while (0)
490:
491: #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
492: QMD_LIST_CHECK_PREV(listelm, field); \
493: (elm)->field.le_prev = (listelm)->field.le_prev; \
494: LIST_NEXT((elm), field) = (listelm); \
495: *(listelm)->field.le_prev = (elm); \
496: (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
497: } while (0)
498:
499: #define LIST_INSERT_HEAD(head, elm, field) do { \
500: QMD_LIST_CHECK_HEAD((head), field); \
501: if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
502: LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
503: LIST_FIRST((head)) = (elm); \
504: (elm)->field.le_prev = &LIST_FIRST((head)); \
505: } while (0)
506:
507: #define LIST_NEXT(elm, field) ((elm)->field.le_next)
508:
509: #define LIST_PREV(elm, head, type, field) \
510: ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
511: __containerof((elm)->field.le_prev, \
512: QUEUE_TYPEOF(type), field.le_next))
513:
514: #define LIST_REMOVE(elm, field) do { \
515: QMD_SAVELINK(oldnext, (elm)->field.le_next); \
516: QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
517: QMD_LIST_CHECK_NEXT(elm, field); \
518: QMD_LIST_CHECK_PREV(elm, field); \
519: if (LIST_NEXT((elm), field) != NULL) \
520: LIST_NEXT((elm), field)->field.le_prev = \
521: (elm)->field.le_prev; \
522: *(elm)->field.le_prev = LIST_NEXT((elm), field); \
523: TRASHIT(*oldnext); \
524: TRASHIT(*oldprev); \
525: } while (0)
526:
527: #define LIST_SWAP(head1, head2, type, field) do { \
528: QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \
529: LIST_FIRST((head1)) = LIST_FIRST((head2)); \
530: LIST_FIRST((head2)) = swap_tmp; \
531: if ((swap_tmp = LIST_FIRST((head1))) != NULL) \
532: swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
533: if ((swap_tmp = LIST_FIRST((head2))) != NULL) \
534: swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
535: } while (0)
536:
537: /*
538: * Tail queue declarations.
539: */
540: #define TAILQ_HEAD(name, type) \
541: struct name { \
542: struct type *tqh_first; /* first element */ \
543: struct type **tqh_last; /* addr of last next element */ \
544: TRACEBUF \
545: }
546:
547: #define TAILQ_CLASS_HEAD(name, type) \
548: struct name { \
549: class type *tqh_first; /* first element */ \
550: class type **tqh_last; /* addr of last next element */ \
551: TRACEBUF \
552: }
553:
554: #define TAILQ_HEAD_INITIALIZER(head) \
555: { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
556:
557: #define TAILQ_ENTRY(type) \
558: struct { \
559: struct type *tqe_next; /* next element */ \
560: struct type **tqe_prev; /* address of previous next element */ \
561: TRACEBUF \
562: }
563:
564: #define TAILQ_CLASS_ENTRY(type) \
565: struct { \
566: class type *tqe_next; /* next element */ \
567: class type **tqe_prev; /* address of previous next element */ \
568: TRACEBUF \
569: }
570:
571: /*
572: * Tail queue functions.
573: */
574: #if (defined(_KERNEL) && defined(INVARIANTS))
575: #define QMD_TAILQ_CHECK_HEAD(head, field) do { \
576: if (!TAILQ_EMPTY(head) && \
577: TAILQ_FIRST((head))->field.tqe_prev != \
578: &TAILQ_FIRST((head))) \
579: panic("Bad tailq head %p first->prev != head", (head)); \
580: } while (0)
581:
582: #define QMD_TAILQ_CHECK_TAIL(head, field) do { \
583: if (*(head)->tqh_last != NULL) \
584: panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
585: } while (0)
586:
587: #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
588: if (TAILQ_NEXT((elm), field) != NULL && \
589: TAILQ_NEXT((elm), field)->field.tqe_prev != \
590: &((elm)->field.tqe_next)) \
591: panic("Bad link elm %p next->prev != elm", (elm)); \
592: } while (0)
593:
594: #define QMD_TAILQ_CHECK_PREV(elm, field) do { \
595: if (*(elm)->field.tqe_prev != (elm)) \
596: panic("Bad link elm %p prev->next != elm", (elm)); \
597: } while (0)
598: #else
599: #define QMD_TAILQ_CHECK_HEAD(head, field)
600: #define QMD_TAILQ_CHECK_TAIL(head, headname)
601: #define QMD_TAILQ_CHECK_NEXT(elm, field)
602: #define QMD_TAILQ_CHECK_PREV(elm, field)
603: #endif /* (_KERNEL && INVARIANTS) */
604:
605: #define TAILQ_CONCAT(head1, head2, field) do { \
606: if (!TAILQ_EMPTY(head2)) { \
607: *(head1)->tqh_last = (head2)->tqh_first; \
608: (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
609: (head1)->tqh_last = (head2)->tqh_last; \
610: TAILQ_INIT((head2)); \
611: QMD_TRACE_HEAD(head1); \
612: QMD_TRACE_HEAD(head2); \
613: } \
614: } while (0)
615:
616: #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
617:
618: #define TAILQ_FIRST(head) ((head)->tqh_first)
619:
620: #define TAILQ_FOREACH(var, head, field) \
621: for ((var) = TAILQ_FIRST((head)); \
622: (var); \
623: (var) = TAILQ_NEXT((var), field))
624:
625: #define TAILQ_FOREACH_FROM(var, head, field) \
626: for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
627: (var); \
628: (var) = TAILQ_NEXT((var), field))
629:
630: #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
631: for ((var) = TAILQ_FIRST((head)); \
632: (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
633: (var) = (tvar))
634:
635: #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
636: for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
637: (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
638: (var) = (tvar))
639:
640: #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
641: for ((var) = TAILQ_LAST((head), headname); \
642: (var); \
643: (var) = TAILQ_PREV((var), headname, field))
644:
645: #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \
646: for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
647: (var); \
648: (var) = TAILQ_PREV((var), headname, field))
649:
650: #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
651: for ((var) = TAILQ_LAST((head), headname); \
652: (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
653: (var) = (tvar))
654:
655: #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
656: for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
657: (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
658: (var) = (tvar))
659:
660: #define TAILQ_INIT(head) do { \
661: TAILQ_FIRST((head)) = NULL; \
662: (head)->tqh_last = &TAILQ_FIRST((head)); \
663: QMD_TRACE_HEAD(head); \
664: } while (0)
665:
666: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
667: QMD_TAILQ_CHECK_NEXT(listelm, field); \
668: if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
669: TAILQ_NEXT((elm), field)->field.tqe_prev = \
670: &TAILQ_NEXT((elm), field); \
671: else { \
672: (head)->tqh_last = &TAILQ_NEXT((elm), field); \
673: QMD_TRACE_HEAD(head); \
674: } \
675: TAILQ_NEXT((listelm), field) = (elm); \
676: (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
677: QMD_TRACE_ELEM(&(elm)->field); \
678: QMD_TRACE_ELEM(&(listelm)->field); \
679: } while (0)
680:
681: #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
682: QMD_TAILQ_CHECK_PREV(listelm, field); \
683: (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
684: TAILQ_NEXT((elm), field) = (listelm); \
685: *(listelm)->field.tqe_prev = (elm); \
686: (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
687: QMD_TRACE_ELEM(&(elm)->field); \
688: QMD_TRACE_ELEM(&(listelm)->field); \
689: } while (0)
690:
691: #define TAILQ_INSERT_HEAD(head, elm, field) do { \
692: QMD_TAILQ_CHECK_HEAD(head, field); \
693: if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
694: TAILQ_FIRST((head))->field.tqe_prev = \
695: &TAILQ_NEXT((elm), field); \
696: else \
697: (head)->tqh_last = &TAILQ_NEXT((elm), field); \
698: TAILQ_FIRST((head)) = (elm); \
699: (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
700: QMD_TRACE_HEAD(head); \
701: QMD_TRACE_ELEM(&(elm)->field); \
702: } while (0)
703:
704: #define TAILQ_INSERT_TAIL(head, elm, field) do { \
705: QMD_TAILQ_CHECK_TAIL(head, field); \
706: TAILQ_NEXT((elm), field) = NULL; \
707: (elm)->field.tqe_prev = (head)->tqh_last; \
708: *(head)->tqh_last = (elm); \
709: (head)->tqh_last = &TAILQ_NEXT((elm), field); \
710: QMD_TRACE_HEAD(head); \
711: QMD_TRACE_ELEM(&(elm)->field); \
712: } while (0)
713:
714: #define TAILQ_LAST(head, headname) \
715: (*(((struct headname *)((head)->tqh_last))->tqh_last))
716:
717: #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
718:
719: #define TAILQ_PREV(elm, headname, field) \
720: (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
721:
722: #define TAILQ_REMOVE(head, elm, field) do { \
723: QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
724: QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
725: QMD_TAILQ_CHECK_NEXT(elm, field); \
726: QMD_TAILQ_CHECK_PREV(elm, field); \
727: if ((TAILQ_NEXT((elm), field)) != NULL) \
728: TAILQ_NEXT((elm), field)->field.tqe_prev = \
729: (elm)->field.tqe_prev; \
730: else { \
731: (head)->tqh_last = (elm)->field.tqe_prev; \
732: QMD_TRACE_HEAD(head); \
733: } \
734: *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
735: TRASHIT(*oldnext); \
736: TRASHIT(*oldprev); \
737: QMD_TRACE_ELEM(&(elm)->field); \
738: } while (0)
739:
740: #define TAILQ_SWAP(head1, head2, type, field) do { \
741: QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \
742: QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \
743: (head1)->tqh_first = (head2)->tqh_first; \
744: (head1)->tqh_last = (head2)->tqh_last; \
745: (head2)->tqh_first = swap_first; \
746: (head2)->tqh_last = swap_last; \
747: if ((swap_first = (head1)->tqh_first) != NULL) \
748: swap_first->field.tqe_prev = &(head1)->tqh_first; \
749: else \
750: (head1)->tqh_last = &(head1)->tqh_first; \
751: if ((swap_first = (head2)->tqh_first) != NULL) \
752: swap_first->field.tqe_prev = &(head2)->tqh_first; \
753: else \
754: (head2)->tqh_last = &(head2)->tqh_first; \
755: } while (0)
756:
757: #endif /* !_SYS_QUEUE_H_ */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to queue.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / mtr / portability