Add panic_hwtf() for kernel faults
[akaros.git] / kern / include / sys / queue.h
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$
31  */
32
33 #pragma once
34
35 #include <ros/common.h>    /* for __offsetof */
36
37 /*
38  * This file defines four types of data structures: singly-linked lists,
39  * singly-linked tail queues, lists and tail queues.
40  *
41  * A singly-linked list is headed by a single forward pointer. The elements
42  * are singly linked for minimum space and pointer manipulation overhead at
43  * the expense of O(n) removal for arbitrary elements. New elements can be
44  * added to the list after an existing element or at the head of the list.
45  * Elements being removed from the head of the list should use the explicit
46  * macro for this purpose for optimum efficiency. A singly-linked list may
47  * only be traversed in the forward direction.  Singly-linked lists are ideal
48  * for applications with large datasets and few or no removals or for
49  * implementing a LIFO queue.
50  *
51  * A singly-linked tail queue is headed by a pair of pointers, one to the
52  * head of the list and the other to the tail of the list. The elements are
53  * singly linked for minimum space and pointer manipulation overhead at the
54  * expense of O(n) removal for arbitrary elements. New elements can be added
55  * to the list after an existing element, at the head of the list, or at the
56  * end of the list. Elements being removed from the head of the tail queue
57  * should use the explicit macro for this purpose for optimum efficiency.
58  * A singly-linked tail queue may only be traversed in the forward direction.
59  * Singly-linked tail queues are ideal for applications with large datasets
60  * and few or no removals or for implementing a FIFO queue.
61  *
62  * A list is headed by a single forward pointer (or an array of forward
63  * pointers for a hash table header). The elements are doubly linked
64  * so that an arbitrary element can be removed without a need to
65  * traverse the list. New elements can be added to the list before
66  * or after an existing element or at the head of the list. A list
67  * may only be traversed in the forward direction.
68  *
69  * A tail queue is headed by a pair of pointers, one to the head of the
70  * list and the other to the tail of the list. The elements are doubly
71  * linked 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 or
73  * after an existing element, at the head of the list, or at the end of
74  * the list. A tail queue may be traversed in either direction.
75  *
76  * For details on the use of these macros, see the queue(3) manual page.
77  *
78  *
79  *                              SLIST   LIST    STAILQ  TAILQ
80  * _HEAD                        +       +       +       +
81  * _HEAD_INITIALIZER            +       +       +       +
82  * _ENTRY                       +       +       +       +
83  * _INIT                        +       +       +       +
84  * _EMPTY                       +       +       +       +
85  * _FIRST                       +       +       +       +
86  * _NEXT                        +       +       +       +
87  * _PREV                        -       -       -       +
88  * _LAST                        -       -       +       +
89  * _FOREACH                     +       +       +       +
90  * _FOREACH_SAFE                +       +       +       +
91  * _FOREACH_REVERSE             -       -       -       +
92  * _FOREACH_REVERSE_SAFE        -       -       -       +
93  * _INSERT_HEAD                 +       +       +       +
94  * _INSERT_BEFORE               -       +       -       +
95  * _INSERT_AFTER                +       +       +       +
96  * _INSERT_TAIL                 -       -       +       +
97  * _CONCAT                      -       -       +       +
98  * _REMOVE_AFTER                +       -       +       -
99  * _REMOVE_HEAD                 +       -       +       -
100  * _REMOVE                      +       +       +       +
101  *
102  */
103 #ifdef QUEUE_MACRO_DEBUG
104 /* ROS has TAILQ-sized elements in a vcore, exposed to userspace via the
105  * vcoremap.  If you have QM tracing turned on, you'll mess it up. */
106 #error "Don't use sys/queue QUEUE_MACRO_DEBUG without dealing with the vcoremap"
107 /* Store the last 2 places the queue element or head was altered */
108 struct qm_trace {
109         char * lastfile;
110         int lastline;
111         char * prevfile;
112         int prevline;
113 };
114
115 #define TRACEBUF        struct qm_trace trace;
116 #define TRASHIT(x)      do {(x) = (void *)-1;} while (0)
117 #define QMD_SAVELINK(name, link)        void **name = (void *)&(link)
118
119 #define QMD_TRACE_HEAD(head) do {                                       \
120         (head)->trace.prevline = (head)->trace.lastline;                \
121         (head)->trace.prevfile = (head)->trace.lastfile;                \
122         (head)->trace.lastline = __LINE__;                              \
123         (head)->trace.lastfile = __FILE__;                              \
124 } while (0)
125
126 #define QMD_TRACE_ELEM(elem) do {                                       \
127         (elem)->trace.prevline = (elem)->trace.lastline;                \
128         (elem)->trace.prevfile = (elem)->trace.lastfile;                \
129         (elem)->trace.lastline = __LINE__;                              \
130         (elem)->trace.lastfile = __FILE__;                              \
131 } while (0)
132
133 #else
134 #define QMD_TRACE_ELEM(elem)
135 #define QMD_TRACE_HEAD(head)
136 #define QMD_SAVELINK(name, link)
137 #define TRACEBUF
138 #define TRASHIT(x)
139 #endif  /* QUEUE_MACRO_DEBUG */
140
141 /*
142  * Singly-linked List declarations.
143  */
144 #define SLIST_HEAD(name, type)                                          \
145 struct name {                                                           \
146         struct type *slh_first; /* first element */                     \
147 }
148
149 #define SLIST_HEAD_INITIALIZER(head)                                    \
150         { NULL }
151
152 #define SLIST_ENTRY(type)                                               \
153 struct {                                                                \
154         struct type *sle_next;  /* next element */                      \
155 }
156
157 /*
158  * Singly-linked List functions.
159  */
160 #define SLIST_EMPTY(head)       ((head)->slh_first == NULL)
161
162 #define SLIST_FIRST(head)       ((head)->slh_first)
163
164 #define SLIST_FOREACH(var, head, field)                                 \
165         for ((var) = SLIST_FIRST((head));                               \
166             (var);                                                      \
167             (var) = SLIST_NEXT((var), field))
168
169 #define SLIST_FOREACH_SAFE(var, head, field, tvar)                      \
170         for ((var) = SLIST_FIRST((head));                               \
171             (var) && ((tvar) = SLIST_NEXT((var), field), 1);            \
172             (var) = (tvar))
173
174 #define SLIST_FOREACH_PREVPTR(var, varp, head, field)                   \
175         for ((varp) = &SLIST_FIRST((head));                             \
176             ((var) = *(varp)) != NULL;                                  \
177             (varp) = &SLIST_NEXT((var), field))
178
179 #define SLIST_INIT(head) do {                                           \
180         SLIST_FIRST((head)) = NULL;                                     \
181 } while (0)
182
183 #define SLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
184         SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);       \
185         SLIST_NEXT((slistelm), field) = (elm);                          \
186 } while (0)
187
188 #define SLIST_INSERT_HEAD(head, elm, field) do {                        \
189         SLIST_NEXT((elm), field) = SLIST_FIRST((head));                 \
190         SLIST_FIRST((head)) = (elm);                                    \
191 } while (0)
192
193 #define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
194
195 #define SLIST_REMOVE(head, elm, type, field) do {                       \
196         QMD_SAVELINK(oldnext, (elm)->field.sle_next);                   \
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_REMOVE_AFTER(curelm, field);                      \
205         }                                                               \
206         TRASHIT(*oldnext);                                              \
207 } while (0)
208
209 #define SLIST_REMOVE_AFTER(elm, field) do {                             \
210         SLIST_NEXT(elm, field) =                                        \
211             SLIST_NEXT(SLIST_NEXT(elm, field), field);                  \
212 } while (0)
213
214 #define SLIST_REMOVE_HEAD(head, field) do {                             \
215         SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);   \
216 } while (0)
217
218 /*
219  * Singly-linked Tail queue declarations.
220  */
221 #define STAILQ_HEAD(name, type)                                         \
222 struct name {                                                           \
223         struct type *stqh_first;/* first element */                     \
224         struct type **stqh_last;/* addr of last next element */         \
225 }
226
227 #define STAILQ_HEAD_INITIALIZER(head)                                   \
228         { NULL, &(head).stqh_first }
229
230 #define STAILQ_ENTRY(type)                                              \
231 struct {                                                                \
232         struct type *stqe_next; /* next element */                      \
233 }
234
235 /*
236  * Singly-linked Tail queue functions.
237  */
238 #define STAILQ_CONCAT(head1, head2) do {                                \
239         if (!STAILQ_EMPTY((head2))) {                                   \
240                 *(head1)->stqh_last = (head2)->stqh_first;              \
241                 (head1)->stqh_last = (head2)->stqh_last;                \
242                 STAILQ_INIT((head2));                                   \
243         }                                                               \
244 } while (0)
245
246 #define STAILQ_EMPTY(head)      ((head)->stqh_first == NULL)
247
248 #define STAILQ_FIRST(head)      ((head)->stqh_first)
249
250 #define STAILQ_FOREACH(var, head, field)                                \
251         for((var) = STAILQ_FIRST((head));                               \
252            (var);                                                       \
253            (var) = STAILQ_NEXT((var), field))
254
255
256 #define STAILQ_FOREACH_SAFE(var, head, field, tvar)                     \
257         for ((var) = STAILQ_FIRST((head));                              \
258             (var) && ((tvar) = STAILQ_NEXT((var), field), 1);           \
259             (var) = (tvar))
260
261 #define STAILQ_INIT(head) do {                                          \
262         STAILQ_FIRST((head)) = NULL;                                    \
263         (head)->stqh_last = &STAILQ_FIRST((head));                      \
264 } while (0)
265
266 #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {               \
267         if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
268                 (head)->stqh_last = &STAILQ_NEXT((elm), field);         \
269         STAILQ_NEXT((tqelm), field) = (elm);                            \
270 } while (0)
271
272 #define STAILQ_INSERT_HEAD(head, elm, field) do {                       \
273         if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
274                 (head)->stqh_last = &STAILQ_NEXT((elm), field);         \
275         STAILQ_FIRST((head)) = (elm);                                   \
276 } while (0)
277
278 #define STAILQ_INSERT_TAIL(head, elm, field) do {                       \
279         STAILQ_NEXT((elm), field) = NULL;                               \
280         *(head)->stqh_last = (elm);                                     \
281         (head)->stqh_last = &STAILQ_NEXT((elm), field);                 \
282 } while (0)
283
284 #define STAILQ_LAST(head, type, field)                                  \
285         (STAILQ_EMPTY((head)) ?                                         \
286                 NULL :                                                  \
287                 ((struct type *)(void *)                                \
288                 ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
289
290 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
291
292 #define STAILQ_REMOVE(head, elm, type, field) do {                      \
293         QMD_SAVELINK(oldnext, (elm)->field.stqe_next);                  \
294         if (STAILQ_FIRST((head)) == (elm)) {                            \
295                 STAILQ_REMOVE_HEAD((head), field);                      \
296         }                                                               \
297         else {                                                          \
298                 struct type *curelm = STAILQ_FIRST((head));             \
299                 while (STAILQ_NEXT(curelm, field) != (elm))             \
300                         curelm = STAILQ_NEXT(curelm, field);            \
301                 STAILQ_REMOVE_AFTER(head, curelm, field);               \
302         }                                                               \
303         TRASHIT(*oldnext);                                              \
304 } while (0)
305
306 #define STAILQ_REMOVE_HEAD(head, field) do {                            \
307         if ((STAILQ_FIRST((head)) =                                     \
308              STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)         \
309                 (head)->stqh_last = &STAILQ_FIRST((head));              \
310 } while (0)
311
312 #define STAILQ_REMOVE_AFTER(head, elm, field) do {                      \
313         if ((STAILQ_NEXT(elm, field) =                                  \
314              STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)      \
315                 (head)->stqh_last = &STAILQ_NEXT((elm), field);         \
316 } while (0)
317
318 #define STAILQ_SWAP(head1, head2, type) do {                            \
319         struct type *swap_first = STAILQ_FIRST(head1);                  \
320         struct type **swap_last = (head1)->stqh_last;                   \
321         STAILQ_FIRST(head1) = STAILQ_FIRST(head2);                      \
322         (head1)->stqh_last = (head2)->stqh_last;                        \
323         STAILQ_FIRST(head2) = swap_first;                               \
324         (head2)->stqh_last = swap_last;                                 \
325         if (STAILQ_EMPTY(head1))                                        \
326                 (head1)->stqh_last = &STAILQ_FIRST(head1);              \
327         if (STAILQ_EMPTY(head2))                                        \
328                 (head2)->stqh_last = &STAILQ_FIRST(head2);              \
329 } while (0)
330
331
332 /*
333  * List declarations.
334  */
335 #define BSD_LIST_HEAD(name, type)                                               \
336 struct name {                                                           \
337         struct type *lh_first;  /* first element */                     \
338 }
339
340 #define BSD_LIST_HEAD_INITIALIZER(head)                                 \
341         { NULL }
342
343 #define BSD_LIST_ENTRY(type)                                            \
344 struct {                                                                \
345         struct type *le_next;   /* next element */                      \
346         struct type **le_prev;  /* address of previous next element */  \
347 }
348
349 /*
350  * List functions.
351  */
352
353 #if (defined(_KERNEL) && defined(INVARIANTS))
354 #define QMD_LIST_CHECK_HEAD(head, field) do {                           \
355         if (BSD_LIST_FIRST((head)) != NULL &&                           \
356             BSD_LIST_FIRST((head))->field.le_prev !=                    \
357              &BSD_LIST_FIRST((head)))                                   \
358                 panic("Bad list head %p first->prev != head", (head));  \
359 } while (0)
360
361 #define QMD_LIST_CHECK_NEXT(elm, field) do {                            \
362         if (BSD_LIST_NEXT((elm), field) != NULL &&                              \
363             BSD_LIST_NEXT((elm), field)->field.le_prev !=                       \
364              &((elm)->field.le_next))                                   \
365                 panic("Bad link elm %p next->prev != elm", (elm));      \
366 } while (0)
367
368 #define QMD_LIST_CHECK_PREV(elm, field) do {                            \
369         if (*(elm)->field.le_prev != (elm))                             \
370                 panic("Bad link elm %p prev->next != elm", (elm));      \
371 } while (0)
372 #else
373 #define QMD_LIST_CHECK_HEAD(head, field)
374 #define QMD_LIST_CHECK_NEXT(elm, field)
375 #define QMD_LIST_CHECK_PREV(elm, field)
376 #endif /* (_KERNEL && INVARIANTS) */
377
378 #define BSD_LIST_EMPTY(head)    ((head)->lh_first == NULL)
379
380 #define BSD_LIST_FIRST(head)    ((head)->lh_first)
381
382 #define BSD_LIST_FOREACH(var, head, field)                                      \
383         for ((var) = BSD_LIST_FIRST((head));                            \
384             (var);                                                      \
385             (var) = BSD_LIST_NEXT((var), field))
386
387 #define BSD_LIST_FOREACH_SAFE(var, head, field, tvar)                   \
388         for ((var) = BSD_LIST_FIRST((head));                            \
389             (var) && ((tvar) = BSD_LIST_NEXT((var), field), 1);         \
390             (var) = (tvar))
391
392 #define BSD_LIST_INIT(head) do {                                                \
393         BSD_LIST_FIRST((head)) = NULL;                                  \
394 } while (0)
395
396 #define BSD_LIST_INSERT_AFTER(listelm, elm, field) do {                 \
397         QMD_LIST_CHECK_NEXT(listelm, field);                            \
398         if ((BSD_LIST_NEXT((elm), field) = BSD_LIST_NEXT((listelm), field)) != NULL)\
399                 BSD_LIST_NEXT((listelm), field)->field.le_prev =                \
400                     &BSD_LIST_NEXT((elm), field);                               \
401         BSD_LIST_NEXT((listelm), field) = (elm);                                \
402         (elm)->field.le_prev = &BSD_LIST_NEXT((listelm), field);                \
403 } while (0)
404
405 #define BSD_LIST_INSERT_BEFORE(listelm, elm, field) do {                        \
406         QMD_LIST_CHECK_PREV(listelm, field);                            \
407         (elm)->field.le_prev = (listelm)->field.le_prev;                \
408         BSD_LIST_NEXT((elm), field) = (listelm);                                \
409         *(listelm)->field.le_prev = (elm);                              \
410         (listelm)->field.le_prev = &BSD_LIST_NEXT((elm), field);                \
411 } while (0)
412
413 #define BSD_LIST_INSERT_HEAD(head, elm, field) do {                             \
414         QMD_LIST_CHECK_HEAD((head), field);                             \
415         if ((BSD_LIST_NEXT((elm), field) = BSD_LIST_FIRST((head))) != NULL)     \
416                 BSD_LIST_FIRST((head))->field.le_prev = &BSD_LIST_NEXT((elm), field);\
417         BSD_LIST_FIRST((head)) = (elm);                                 \
418         (elm)->field.le_prev = &BSD_LIST_FIRST((head));                 \
419 } while (0)
420
421 #define BSD_LIST_NEXT(elm, field)       ((elm)->field.le_next)
422
423 #define BSD_LIST_PREV(elm, head, type, field)                   \
424         ((elm)->field.le_prev == &BSD_LIST_FIRST((head)) ? NULL :       \
425             container_of((elm)->field.le_prev,                  \
426             struct type, field.le_next))
427
428 #define BSD_LIST_REMOVE(elm, field) do {                                        \
429         QMD_SAVELINK(oldnext, (elm)->field.le_next);                    \
430         QMD_SAVELINK(oldprev, (elm)->field.le_prev);                    \
431         QMD_LIST_CHECK_NEXT(elm, field);                                \
432         QMD_LIST_CHECK_PREV(elm, field);                                \
433         if (BSD_LIST_NEXT((elm), field) != NULL)                                \
434                 BSD_LIST_NEXT((elm), field)->field.le_prev =            \
435                     (elm)->field.le_prev;                               \
436         *(elm)->field.le_prev = BSD_LIST_NEXT((elm), field);            \
437         TRASHIT(*oldnext);                                              \
438         TRASHIT(*oldprev);                                              \
439 } while (0)
440
441 #define BSD_LIST_SWAP(head1, head2, type, field) do {                   \
442         struct type *swap_tmp = BSD_LIST_FIRST((head1));                        \
443         BSD_LIST_FIRST((head1)) = BSD_LIST_FIRST((head2));                      \
444         BSD_LIST_FIRST((head2)) = swap_tmp;                                     \
445         if ((swap_tmp = BSD_LIST_FIRST((head1))) != NULL)                       \
446                 swap_tmp->field.le_prev = &BSD_LIST_FIRST((head1));             \
447         if ((swap_tmp = BSD_LIST_FIRST((head2))) != NULL)                       \
448                 swap_tmp->field.le_prev = &BSD_LIST_FIRST((head2));             \
449 } while (0)
450
451 /*
452  * Tail queue declarations.
453  */
454 #define TAILQ_HEAD(name, type)                                          \
455 struct name {                                                           \
456         struct type *tqh_first; /* first element */                     \
457         struct type **tqh_last; /* addr of last next element */         \
458         TRACEBUF                                                        \
459 }
460
461 #define TAILQ_HEAD_INITIALIZER(head)                                    \
462         { NULL, &(head).tqh_first }
463
464 #define TAILQ_ENTRY(type)                                               \
465 struct {                                                                \
466         struct type *tqe_next;  /* next element */                      \
467         struct type **tqe_prev; /* address of previous next element */  \
468         TRACEBUF                                                        \
469 }
470
471 /*
472  * Tail queue functions.
473  */
474 #if (defined(_KERNEL) && defined(INVARIANTS))
475 #define QMD_TAILQ_CHECK_HEAD(head, field) do {                          \
476         if (!TAILQ_EMPTY(head) &&                                       \
477             TAILQ_FIRST((head))->field.tqe_prev !=                      \
478              &TAILQ_FIRST((head)))                                      \
479                 panic("Bad tailq head %p first->prev != head", (head)); \
480 } while (0)
481
482 #define QMD_TAILQ_CHECK_TAIL(head, field) do {                          \
483         if (*(head)->tqh_last != NULL)                                  \
484                 panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head));  \
485 } while (0)
486
487 #define QMD_TAILQ_CHECK_NEXT(elm, field) do {                           \
488         if (TAILQ_NEXT((elm), field) != NULL &&                         \
489             TAILQ_NEXT((elm), field)->field.tqe_prev !=                 \
490              &((elm)->field.tqe_next))                                  \
491                 panic("Bad link elm %p next->prev != elm", (elm));      \
492 } while (0)
493
494 #define QMD_TAILQ_CHECK_PREV(elm, field) do {                           \
495         if (*(elm)->field.tqe_prev != (elm))                            \
496                 panic("Bad link elm %p prev->next != elm", (elm));      \
497 } while (0)
498 #else
499 #define QMD_TAILQ_CHECK_HEAD(head, field)
500 #define QMD_TAILQ_CHECK_TAIL(head, headname)
501 #define QMD_TAILQ_CHECK_NEXT(elm, field)
502 #define QMD_TAILQ_CHECK_PREV(elm, field)
503 #endif /* (_KERNEL && INVARIANTS) */
504
505 #define TAILQ_CONCAT(head1, head2, field) do {                          \
506         if (!TAILQ_EMPTY(head2)) {                                      \
507                 *(head1)->tqh_last = (head2)->tqh_first;                \
508                 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
509                 (head1)->tqh_last = (head2)->tqh_last;                  \
510                 TAILQ_INIT((head2));                                    \
511                 QMD_TRACE_HEAD(head1);                                  \
512                 QMD_TRACE_HEAD(head2);                                  \
513         }                                                               \
514 } while (0)
515
516 #define TAILQ_EMPTY(head)       ((head)->tqh_first == NULL)
517
518 #define TAILQ_FIRST(head)       ((head)->tqh_first)
519
520 #define TAILQ_FOREACH(var, head, field)                                 \
521         for ((var) = TAILQ_FIRST((head));                               \
522             (var);                                                      \
523             (var) = TAILQ_NEXT((var), field))
524
525 #define TAILQ_FOREACH_SAFE(var, head, field, tvar)                      \
526         for ((var) = TAILQ_FIRST((head));                               \
527             (var) && ((tvar) = TAILQ_NEXT((var), field), 1);            \
528             (var) = (tvar))
529
530 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
531         for ((var) = TAILQ_LAST((head), headname);                      \
532             (var);                                                      \
533             (var) = TAILQ_PREV((var), headname, field))
534
535 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)    \
536         for ((var) = TAILQ_LAST((head), headname);                      \
537             (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
538             (var) = (tvar))
539
540 #define TAILQ_INIT(head) do {                                           \
541         TAILQ_FIRST((head)) = NULL;                                     \
542         (head)->tqh_last = &TAILQ_FIRST((head));                        \
543         QMD_TRACE_HEAD(head);                                           \
544 } while (0)
545
546 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
547         QMD_TAILQ_CHECK_NEXT(listelm, field);                           \
548         if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
549                 TAILQ_NEXT((elm), field)->field.tqe_prev =              \
550                     &TAILQ_NEXT((elm), field);                          \
551         else {                                                          \
552                 (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
553                 QMD_TRACE_HEAD(head);                                   \
554         }                                                               \
555         TAILQ_NEXT((listelm), field) = (elm);                           \
556         (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);          \
557         QMD_TRACE_ELEM(&(elm)->field);                                  \
558         QMD_TRACE_ELEM(&listelm->field);                                \
559 } while (0)
560
561 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
562         QMD_TAILQ_CHECK_PREV(listelm, field);                           \
563         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
564         TAILQ_NEXT((elm), field) = (listelm);                           \
565         *(listelm)->field.tqe_prev = (elm);                             \
566         (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);          \
567         QMD_TRACE_ELEM(&(elm)->field);                                  \
568         QMD_TRACE_ELEM(&listelm->field);                                \
569 } while (0)
570
571 #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
572         QMD_TAILQ_CHECK_HEAD(head, field);                              \
573         if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)   \
574                 TAILQ_FIRST((head))->field.tqe_prev =                   \
575                     &TAILQ_NEXT((elm), field);                          \
576         else                                                            \
577                 (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
578         TAILQ_FIRST((head)) = (elm);                                    \
579         (elm)->field.tqe_prev = &TAILQ_FIRST((head));                   \
580         QMD_TRACE_HEAD(head);                                           \
581         QMD_TRACE_ELEM(&(elm)->field);                                  \
582 } while (0)
583
584 #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
585         QMD_TAILQ_CHECK_TAIL(head, field);                              \
586         TAILQ_NEXT((elm), field) = NULL;                                \
587         (elm)->field.tqe_prev = (head)->tqh_last;                       \
588         *(head)->tqh_last = (elm);                                      \
589         (head)->tqh_last = &TAILQ_NEXT((elm), field);                   \
590         QMD_TRACE_HEAD(head);                                           \
591         QMD_TRACE_ELEM(&(elm)->field);                                  \
592 } while (0)
593
594 #define TAILQ_LAST(head, headname)                                      \
595         (*(((struct headname *)((head)->tqh_last))->tqh_last))
596
597 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
598
599 #define TAILQ_PREV(elm, headname, field)                                \
600         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
601
602 #define TAILQ_REMOVE(head, elm, field) do {                             \
603         QMD_SAVELINK(oldnext, (elm)->field.tqe_next);                   \
604         QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);                   \
605         QMD_TAILQ_CHECK_NEXT(elm, field);                               \
606         QMD_TAILQ_CHECK_PREV(elm, field);                               \
607         if ((TAILQ_NEXT((elm), field)) != NULL)                         \
608                 TAILQ_NEXT((elm), field)->field.tqe_prev =              \
609                     (elm)->field.tqe_prev;                              \
610         else {                                                          \
611                 (head)->tqh_last = (elm)->field.tqe_prev;               \
612                 QMD_TRACE_HEAD(head);                                   \
613         }                                                               \
614         *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);              \
615         TRASHIT(*oldnext);                                              \
616         TRASHIT(*oldprev);                                              \
617         QMD_TRACE_ELEM(&(elm)->field);                                  \
618 } while (0)
619
620 #define TAILQ_SWAP(head1, head2, type, field) do {                      \
621         struct type *swap_first = (head1)->tqh_first;                   \
622         struct type **swap_last = (head1)->tqh_last;                    \
623         (head1)->tqh_first = (head2)->tqh_first;                        \
624         (head1)->tqh_last = (head2)->tqh_last;                          \
625         (head2)->tqh_first = swap_first;                                \
626         (head2)->tqh_last = swap_last;                                  \
627         if ((swap_first = (head1)->tqh_first) != NULL)                  \
628                 swap_first->field.tqe_prev = &(head1)->tqh_first;       \
629         else                                                            \
630                 (head1)->tqh_last = &(head1)->tqh_first;                \
631         if ((swap_first = (head2)->tqh_first) != NULL)                  \
632                 swap_first->field.tqe_prev = &(head2)->tqh_first;       \
633         else                                                            \
634                 (head2)->tqh_last = &(head2)->tqh_first;                \
635 } while (0)