1
2
3
4
5
6
7#ifndef _SYS_QUEUE_H_
8#define _SYS_QUEUE_H_
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88#ifdef QUEUE_MACRO_DEBUG
89#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
90#define QUEUE_MACRO_DEBUG_TRACE
91#define QUEUE_MACRO_DEBUG_TRASH
92#endif
93
94#ifdef QUEUE_MACRO_DEBUG_TRACE
95
96struct qm_trace {
97 unsigned long lastline;
98 unsigned long prevline;
99 const char *lastfile;
100 const char *prevfile;
101};
102
103#define TRACEBUF struct qm_trace trace;
104#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } ,
105
106#define QMD_TRACE_HEAD(head) do { \
107 (head)->trace.prevline = (head)->trace.lastline; \
108 (head)->trace.prevfile = (head)->trace.lastfile; \
109 (head)->trace.lastline = __LINE__; \
110 (head)->trace.lastfile = __FILE__; \
111} while (0)
112
113#define QMD_TRACE_ELEM(elem) do { \
114 (elem)->trace.prevline = (elem)->trace.lastline; \
115 (elem)->trace.prevfile = (elem)->trace.lastfile; \
116 (elem)->trace.lastline = __LINE__; \
117 (elem)->trace.lastfile = __FILE__; \
118} while (0)
119
120#else
121#define QMD_TRACE_ELEM(elem)
122#define QMD_TRACE_HEAD(head)
123#define TRACEBUF
124#define TRACEBUF_INITIALIZER
125#endif
126
127#ifdef QUEUE_MACRO_DEBUG_TRASH
128#define QMD_SAVELINK(name, link) void **name = (void *)&(link)
129#define TRASHIT(x) do {(x) = (void *)-1;} while (0)
130#define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1)
131#else
132#define QMD_SAVELINK(name, link)
133#define TRASHIT(x)
134#define QMD_IS_TRASHED(x) 0
135#endif
136
137#ifdef __cplusplus
138
139
140
141#define QUEUE_TYPEOF(type) type
142#else
143#define QUEUE_TYPEOF(type) struct type
144#endif
145
146
147
148
149#define SLIST_HEAD(name, type) \
150struct name { \
151 struct type *slh_first; \
152}
153
154#define SLIST_CLASS_HEAD(name, type) \
155struct name { \
156 class type *slh_first; \
157}
158
159#define SLIST_HEAD_INITIALIZER(head) \
160 { NULL }
161
162#define SLIST_ENTRY(type) \
163struct { \
164 struct type *sle_next; \
165}
166
167#define SLIST_CLASS_ENTRY(type) \
168struct { \
169 class type *sle_next; \
170}
171
172
173
174
175#if (defined(_KERNEL) && defined(INVARIANTS))
176#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do { \
177 if (*(prevp) != (elm)) \
178 panic("Bad prevptr *(%p) == %p != %p", \
179 (prevp), *(prevp), (elm)); \
180} while (0)
181#else
182#define QMD_SLIST_CHECK_PREVPTR(prevp, elm)
183#endif
184
185#define SLIST_CONCAT(head1, head2, type, field) do { \
186 QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \
187 if (curelm == NULL) { \
188 if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \
189 SLIST_INIT(head2); \
190 } else if (SLIST_FIRST(head2) != NULL) { \
191 while (SLIST_NEXT(curelm, field) != NULL) \
192 curelm = SLIST_NEXT(curelm, field); \
193 SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \
194 SLIST_INIT(head2); \
195 } \
196} while (0)
197
198#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
199
200#define SLIST_FIRST(head) ((head)->slh_first)
201
202#define SLIST_FOREACH(var, head, field) \
203 for ((var) = SLIST_FIRST((head)); \
204 (var); \
205 (var) = SLIST_NEXT((var), field))
206
207#define SLIST_FOREACH_FROM(var, head, field) \
208 for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
209 (var); \
210 (var) = SLIST_NEXT((var), field))
211
212#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
213 for ((var) = SLIST_FIRST((head)); \
214 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
215 (var) = (tvar))
216
217#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
218 for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
219 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
220 (var) = (tvar))
221
222#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
223 for ((varp) = &SLIST_FIRST((head)); \
224 ((var) = *(varp)) != NULL; \
225 (varp) = &SLIST_NEXT((var), field))
226
227#define SLIST_INIT(head) do { \
228 SLIST_FIRST((head)) = NULL; \
229} while (0)
230
231#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
232 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
233 SLIST_NEXT((slistelm), field) = (elm); \
234} while (0)
235
236#define SLIST_INSERT_HEAD(head, elm, field) do { \
237 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
238 SLIST_FIRST((head)) = (elm); \
239} while (0)
240
241#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
242
243#define SLIST_REMOVE(head, elm, type, field) do { \
244 QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
245 if (SLIST_FIRST((head)) == (elm)) { \
246 SLIST_REMOVE_HEAD((head), field); \
247 } \
248 else { \
249 QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \
250 while (SLIST_NEXT(curelm, field) != (elm)) \
251 curelm = SLIST_NEXT(curelm, field); \
252 SLIST_REMOVE_AFTER(curelm, field); \
253 } \
254 TRASHIT(*oldnext); \
255} while (0)
256
257#define SLIST_REMOVE_AFTER(elm, field) do { \
258 SLIST_NEXT(elm, field) = \
259 SLIST_NEXT(SLIST_NEXT(elm, field), field); \
260} while (0)
261
262#define SLIST_REMOVE_HEAD(head, field) do { \
263 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
264} while (0)
265
266#define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \
267 QMD_SLIST_CHECK_PREVPTR(prevp, elm); \
268 *(prevp) = SLIST_NEXT(elm, field); \
269 TRASHIT((elm)->field.sle_next); \
270} while (0)
271
272#define SLIST_SWAP(head1, head2, type) do { \
273 QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \
274 SLIST_FIRST(head1) = SLIST_FIRST(head2); \
275 SLIST_FIRST(head2) = swap_first; \
276} while (0)
277
278
279
280
281#define STAILQ_HEAD(name, type) \
282struct name { \
283 struct type *stqh_first; \
284 struct type **stqh_last; \
285}
286
287#define STAILQ_CLASS_HEAD(name, type) \
288struct name { \
289 class type *stqh_first; \
290 class type **stqh_last; \
291}
292
293#define STAILQ_HEAD_INITIALIZER(head) \
294 { NULL, &(head).stqh_first }
295
296#define STAILQ_ENTRY(type) \
297struct { \
298 struct type *stqe_next; \
299}
300
301#define STAILQ_CLASS_ENTRY(type) \
302struct { \
303 class type *stqe_next; \
304}
305
306
307
308
309#define STAILQ_CONCAT(head1, head2) do { \
310 if (!STAILQ_EMPTY((head2))) { \
311 *(head1)->stqh_last = (head2)->stqh_first; \
312 (head1)->stqh_last = (head2)->stqh_last; \
313 STAILQ_INIT((head2)); \
314 } \
315} while (0)
316
317#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
318
319#define STAILQ_FIRST(head) ((head)->stqh_first)
320
321#define STAILQ_FOREACH(var, head, field) \
322 for((var) = STAILQ_FIRST((head)); \
323 (var); \
324 (var) = STAILQ_NEXT((var), field))
325
326#define STAILQ_FOREACH_FROM(var, head, field) \
327 for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
328 (var); \
329 (var) = STAILQ_NEXT((var), field))
330
331#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
332 for ((var) = STAILQ_FIRST((head)); \
333 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
334 (var) = (tvar))
335
336#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
337 for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
338 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
339 (var) = (tvar))
340
341#define STAILQ_INIT(head) do { \
342 STAILQ_FIRST((head)) = NULL; \
343 (head)->stqh_last = &STAILQ_FIRST((head)); \
344} while (0)
345
346#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
347 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
348 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
349 STAILQ_NEXT((tqelm), field) = (elm); \
350} while (0)
351
352#define STAILQ_INSERT_HEAD(head, elm, field) do { \
353 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
354 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
355 STAILQ_FIRST((head)) = (elm); \
356} while (0)
357
358#define STAILQ_INSERT_TAIL(head, elm, field) do { \
359 STAILQ_NEXT((elm), field) = NULL; \
360 *(head)->stqh_last = (elm); \
361 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
362} while (0)
363
364#define STAILQ_LAST(head, type, field) \
365 (STAILQ_EMPTY((head)) ? NULL : \
366 __containerof((head)->stqh_last, \
367 QUEUE_TYPEOF(type), field.stqe_next))
368
369#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
370
371#define STAILQ_REMOVE(head, elm, type, field) do { \
372 QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
373 if (STAILQ_FIRST((head)) == (elm)) { \
374 STAILQ_REMOVE_HEAD((head), field); \
375 } \
376 else { \
377 QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \
378 while (STAILQ_NEXT(curelm, field) != (elm)) \
379 curelm = STAILQ_NEXT(curelm, field); \
380 STAILQ_REMOVE_AFTER(head, curelm, field); \
381 } \
382 TRASHIT(*oldnext); \
383} while (0)
384
385#define STAILQ_REMOVE_AFTER(head, elm, field) do { \
386 if ((STAILQ_NEXT(elm, field) = \
387 STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
388 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
389} while (0)
390
391#define STAILQ_REMOVE_HEAD(head, field) do { \
392 if ((STAILQ_FIRST((head)) = \
393 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
394 (head)->stqh_last = &STAILQ_FIRST((head)); \
395} while (0)
396
397#define STAILQ_SWAP(head1, head2, type) do { \
398 QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \
399 QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \
400 STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \
401 (head1)->stqh_last = (head2)->stqh_last; \
402 STAILQ_FIRST(head2) = swap_first; \
403 (head2)->stqh_last = swap_last; \
404 if (STAILQ_EMPTY(head1)) \
405 (head1)->stqh_last = &STAILQ_FIRST(head1); \
406 if (STAILQ_EMPTY(head2)) \
407 (head2)->stqh_last = &STAILQ_FIRST(head2); \
408} while (0)
409
410
411
412
413
414#define LIST_HEAD(name, type) \
415struct name { \
416 struct type *lh_first; \
417}
418
419#define LIST_CLASS_HEAD(name, type) \
420struct name { \
421 class type *lh_first; \
422}
423
424#define LIST_HEAD_INITIALIZER(head) \
425 { NULL }
426
427#define LIST_ENTRY(type) \
428struct { \
429 struct type *le_next; \
430 struct type **le_prev; \
431}
432
433#define LIST_CLASS_ENTRY(type) \
434struct { \
435 class type *le_next; \
436 class type **le_prev; \
437}
438
439
440
441
442
443#if (defined(_KERNEL) && defined(INVARIANTS))
444
445
446
447
448
449
450#define QMD_LIST_CHECK_HEAD(head, field) do { \
451 if (LIST_FIRST((head)) != NULL && \
452 LIST_FIRST((head))->field.le_prev != \
453 &LIST_FIRST((head))) \
454 panic("Bad list head %p first->prev != head", (head)); \
455} while (0)
456
457
458
459
460
461
462
463#define QMD_LIST_CHECK_NEXT(elm, field) do { \
464 if (LIST_NEXT((elm), field) != NULL && \
465 LIST_NEXT((elm), field)->field.le_prev != \
466 &((elm)->field.le_next)) \
467 panic("Bad link elm %p next->prev != elm", (elm)); \
468} while (0)
469
470
471
472
473
474
475#define QMD_LIST_CHECK_PREV(elm, field) do { \
476 if (*(elm)->field.le_prev != (elm)) \
477 panic("Bad link elm %p prev->next != elm", (elm)); \
478} while (0)
479#else
480#define QMD_LIST_CHECK_HEAD(head, field)
481#define QMD_LIST_CHECK_NEXT(elm, field)
482#define QMD_LIST_CHECK_PREV(elm, field)
483#endif
484
485#define LIST_CONCAT(head1, head2, type, field) do { \
486 QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \
487 if (curelm == NULL) { \
488 if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \
489 LIST_FIRST(head2)->field.le_prev = \
490 &LIST_FIRST((head1)); \
491 LIST_INIT(head2); \
492 } \
493 } else if (LIST_FIRST(head2) != NULL) { \
494 while (LIST_NEXT(curelm, field) != NULL) \
495 curelm = LIST_NEXT(curelm, field); \
496 LIST_NEXT(curelm, field) = LIST_FIRST(head2); \
497 LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
498 LIST_INIT(head2); \
499 } \
500} while (0)
501
502#define LIST_EMPTY(head) ((head)->lh_first == NULL)
503
504#define LIST_FIRST(head) ((head)->lh_first)
505
506#define LIST_FOREACH(var, head, field) \
507 for ((var) = LIST_FIRST((head)); \
508 (var); \
509 (var) = LIST_NEXT((var), field))
510
511#define LIST_FOREACH_FROM(var, head, field) \
512 for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
513 (var); \
514 (var) = LIST_NEXT((var), field))
515
516#define LIST_FOREACH_SAFE(var, head, field, tvar) \
517 for ((var) = LIST_FIRST((head)); \
518 (var) && ((tvar) = LIST_NEXT((var), field), 1); \
519 (var) = (tvar))
520
521#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
522 for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
523 (var) && ((tvar) = LIST_NEXT((var), field), 1); \
524 (var) = (tvar))
525
526#define LIST_INIT(head) do { \
527 LIST_FIRST((head)) = NULL; \
528} while (0)
529
530#define LIST_INSERT_AFTER(listelm, elm, field) do { \
531 QMD_LIST_CHECK_NEXT(listelm, field); \
532 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
533 LIST_NEXT((listelm), field)->field.le_prev = \
534 &LIST_NEXT((elm), field); \
535 LIST_NEXT((listelm), field) = (elm); \
536 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
537} while (0)
538
539#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
540 QMD_LIST_CHECK_PREV(listelm, field); \
541 (elm)->field.le_prev = (listelm)->field.le_prev; \
542 LIST_NEXT((elm), field) = (listelm); \
543 *(listelm)->field.le_prev = (elm); \
544 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
545} while (0)
546
547#define LIST_INSERT_HEAD(head, elm, field) do { \
548 QMD_LIST_CHECK_HEAD((head), field); \
549 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
550 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
551 LIST_FIRST((head)) = (elm); \
552 (elm)->field.le_prev = &LIST_FIRST((head)); \
553} while (0)
554
555#define LIST_NEXT(elm, field) ((elm)->field.le_next)
556
557#define LIST_PREV(elm, head, type, field) \
558 ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
559 __containerof((elm)->field.le_prev, \
560 QUEUE_TYPEOF(type), field.le_next))
561
562#define LIST_REMOVE(elm, field) do { \
563 QMD_SAVELINK(oldnext, (elm)->field.le_next); \
564 QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
565 QMD_LIST_CHECK_NEXT(elm, field); \
566 QMD_LIST_CHECK_PREV(elm, field); \
567 if (LIST_NEXT((elm), field) != NULL) \
568 LIST_NEXT((elm), field)->field.le_prev = \
569 (elm)->field.le_prev; \
570 *(elm)->field.le_prev = LIST_NEXT((elm), field); \
571 TRASHIT(*oldnext); \
572 TRASHIT(*oldprev); \
573} while (0)
574
575#define LIST_SWAP(head1, head2, type, field) do { \
576 QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \
577 LIST_FIRST((head1)) = LIST_FIRST((head2)); \
578 LIST_FIRST((head2)) = swap_tmp; \
579 if ((swap_tmp = LIST_FIRST((head1))) != NULL) \
580 swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
581 if ((swap_tmp = LIST_FIRST((head2))) != NULL) \
582 swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
583} while (0)
584
585
586
587
588#define TAILQ_HEAD(name, type) \
589struct name { \
590 struct type *tqh_first; \
591 struct type **tqh_last; \
592 TRACEBUF \
593}
594
595#define TAILQ_CLASS_HEAD(name, type) \
596struct name { \
597 class type *tqh_first; \
598 class type **tqh_last; \
599 TRACEBUF \
600}
601
602#define TAILQ_HEAD_INITIALIZER(head) \
603 { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
604
605#define TAILQ_ENTRY(type) \
606struct { \
607 struct type *tqe_next; \
608 struct type **tqe_prev; \
609 TRACEBUF \
610}
611
612#define TAILQ_CLASS_ENTRY(type) \
613struct { \
614 class type *tqe_next; \
615 class type **tqe_prev; \
616 TRACEBUF \
617}
618
619
620
621
622#if (defined(_KERNEL) && defined(INVARIANTS))
623
624
625
626
627
628
629#define QMD_TAILQ_CHECK_HEAD(head, field) do { \
630 if (!TAILQ_EMPTY(head) && \
631 TAILQ_FIRST((head))->field.tqe_prev != \
632 &TAILQ_FIRST((head))) \
633 panic("Bad tailq head %p first->prev != head", (head)); \
634} while (0)
635
636
637
638
639
640
641#define QMD_TAILQ_CHECK_TAIL(head, field) do { \
642 if (*(head)->tqh_last != NULL) \
643 panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
644} while (0)
645
646
647
648
649
650
651
652#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
653 if (TAILQ_NEXT((elm), field) != NULL && \
654 TAILQ_NEXT((elm), field)->field.tqe_prev != \
655 &((elm)->field.tqe_next)) \
656 panic("Bad link elm %p next->prev != elm", (elm)); \
657} while (0)
658
659
660
661
662
663
664#define QMD_TAILQ_CHECK_PREV(elm, field) do { \
665 if (*(elm)->field.tqe_prev != (elm)) \
666 panic("Bad link elm %p prev->next != elm", (elm)); \
667} while (0)
668#else
669#define QMD_TAILQ_CHECK_HEAD(head, field)
670#define QMD_TAILQ_CHECK_TAIL(head, headname)
671#define QMD_TAILQ_CHECK_NEXT(elm, field)
672#define QMD_TAILQ_CHECK_PREV(elm, field)
673#endif
674
675#define TAILQ_CONCAT(head1, head2, field) do { \
676 if (!TAILQ_EMPTY(head2)) { \
677 *(head1)->tqh_last = (head2)->tqh_first; \
678 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
679 (head1)->tqh_last = (head2)->tqh_last; \
680 TAILQ_INIT((head2)); \
681 QMD_TRACE_HEAD(head1); \
682 QMD_TRACE_HEAD(head2); \
683 } \
684} while (0)
685
686#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
687
688#define TAILQ_FIRST(head) ((head)->tqh_first)
689
690#define TAILQ_FOREACH(var, head, field) \
691 for ((var) = TAILQ_FIRST((head)); \
692 (var); \
693 (var) = TAILQ_NEXT((var), field))
694
695#define TAILQ_FOREACH_FROM(var, head, field) \
696 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
697 (var); \
698 (var) = TAILQ_NEXT((var), field))
699
700#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
701 for ((var) = TAILQ_FIRST((head)); \
702 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
703 (var) = (tvar))
704
705#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
706 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
707 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
708 (var) = (tvar))
709
710#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
711 for ((var) = TAILQ_LAST((head), headname); \
712 (var); \
713 (var) = TAILQ_PREV((var), headname, field))
714
715#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \
716 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
717 (var); \
718 (var) = TAILQ_PREV((var), headname, field))
719
720#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
721 for ((var) = TAILQ_LAST((head), headname); \
722 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
723 (var) = (tvar))
724
725#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
726 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
727 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
728 (var) = (tvar))
729
730#define TAILQ_INIT(head) do { \
731 TAILQ_FIRST((head)) = NULL; \
732 (head)->tqh_last = &TAILQ_FIRST((head)); \
733 QMD_TRACE_HEAD(head); \
734} while (0)
735
736#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
737 QMD_TAILQ_CHECK_NEXT(listelm, field); \
738 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
739 TAILQ_NEXT((elm), field)->field.tqe_prev = \
740 &TAILQ_NEXT((elm), field); \
741 else { \
742 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
743 QMD_TRACE_HEAD(head); \
744 } \
745 TAILQ_NEXT((listelm), field) = (elm); \
746 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
747 QMD_TRACE_ELEM(&(elm)->field); \
748 QMD_TRACE_ELEM(&(listelm)->field); \
749} while (0)
750
751#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
752 QMD_TAILQ_CHECK_PREV(listelm, field); \
753 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
754 TAILQ_NEXT((elm), field) = (listelm); \
755 *(listelm)->field.tqe_prev = (elm); \
756 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
757 QMD_TRACE_ELEM(&(elm)->field); \
758 QMD_TRACE_ELEM(&(listelm)->field); \
759} while (0)
760
761#define TAILQ_INSERT_HEAD(head, elm, field) do { \
762 QMD_TAILQ_CHECK_HEAD(head, field); \
763 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
764 TAILQ_FIRST((head))->field.tqe_prev = \
765 &TAILQ_NEXT((elm), field); \
766 else \
767 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
768 TAILQ_FIRST((head)) = (elm); \
769 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
770 QMD_TRACE_HEAD(head); \
771 QMD_TRACE_ELEM(&(elm)->field); \
772} while (0)
773
774#define TAILQ_INSERT_TAIL(head, elm, field) do { \
775 QMD_TAILQ_CHECK_TAIL(head, field); \
776 TAILQ_NEXT((elm), field) = NULL; \
777 (elm)->field.tqe_prev = (head)->tqh_last; \
778 *(head)->tqh_last = (elm); \
779 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
780 QMD_TRACE_HEAD(head); \
781 QMD_TRACE_ELEM(&(elm)->field); \
782} while (0)
783
784#define TAILQ_LAST(head, headname) \
785 (*(((struct headname *)((head)->tqh_last))->tqh_last))
786
787
788
789
790
791
792
793
794#define TAILQ_LAST_FAST(head, type, field) \
795 (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next))
796
797#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
798
799#define TAILQ_PREV(elm, headname, field) \
800 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
801
802#define TAILQ_PREV_FAST(elm, head, type, field) \
803 ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL : \
804 __containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next))
805
806#define TAILQ_REMOVE(head, elm, field) do { \
807 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
808 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
809 QMD_TAILQ_CHECK_NEXT(elm, field); \
810 QMD_TAILQ_CHECK_PREV(elm, field); \
811 if ((TAILQ_NEXT((elm), field)) != NULL) \
812 TAILQ_NEXT((elm), field)->field.tqe_prev = \
813 (elm)->field.tqe_prev; \
814 else { \
815 (head)->tqh_last = (elm)->field.tqe_prev; \
816 QMD_TRACE_HEAD(head); \
817 } \
818 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
819 TRASHIT(*oldnext); \
820 TRASHIT(*oldprev); \
821 QMD_TRACE_ELEM(&(elm)->field); \
822} while (0)
823
824#define TAILQ_SWAP(head1, head2, type, field) do { \
825 QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \
826 QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \
827 (head1)->tqh_first = (head2)->tqh_first; \
828 (head1)->tqh_last = (head2)->tqh_last; \
829 (head2)->tqh_first = swap_first; \
830 (head2)->tqh_last = swap_last; \
831 if ((swap_first = (head1)->tqh_first) != NULL) \
832 swap_first->field.tqe_prev = &(head1)->tqh_first; \
833 else \
834 (head1)->tqh_last = &(head1)->tqh_first; \
835 if ((swap_first = (head2)->tqh_first) != NULL) \
836 swap_first->field.tqe_prev = &(head2)->tqh_first; \
837 else \
838 (head2)->tqh_last = &(head2)->tqh_first; \
839} while (0)
840
841#endif
842