Rev 4874 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 4874 | Rev 4921 | ||
---|---|---|---|
Line 1... | Line 1... | ||
1 | /* |
1 | /*- |
2 | * Copyright (c) 1991, 1993 |
2 | * Copyright (c) 1991, 1993 |
3 | * The Regents of the University of California. All rights reserved. |
3 | * The Regents of the University of California. All rights reserved. |
4 | * |
4 | * |
5 | * Redistribution and use in source and binary forms, with or without |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions |
6 | * modification, are permitted provided that the following conditions |
Line 8... | Line 8... | ||
8 | * 1. Redistributions of source code must retain the above copyright |
8 | * 1. Redistributions of source code must retain the above copyright |
9 | * notice, this list of conditions and the following disclaimer. |
9 | * notice, this list of conditions and the following disclaimer. |
10 | * 2. Redistributions in binary form must reproduce the above copyright |
10 | * 2. Redistributions in binary form must reproduce the above copyright |
11 | * notice, this list of conditions and the following disclaimer in the |
11 | * notice, this list of conditions and the following disclaimer in the |
12 | * documentation and/or other materials provided with the distribution. |
12 | * documentation and/or other materials provided with the distribution. |
13 | * 3. All advertising materials mentioning features or use of this software |
- | |
14 | * must display the following acknowledgement: |
- | |
15 | * This product includes software developed by the University of |
- | |
16 | * California, Berkeley and its contributors. |
- | |
17 | * 4. Neither the name of the University nor the names of its contributors |
13 | * 4. Neither the name of the University nor the names of its contributors |
18 | * may be used to endorse or promote products derived from this software |
14 | * may be used to endorse or promote products derived from this software |
19 | * without specific prior written permission. |
15 | * without specific prior written permission. |
20 | * |
16 | * |
21 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
17 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
Line 29... | Line 25... | ||
29 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
25 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
30 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
26 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
31 | * SUCH DAMAGE. |
27 | * SUCH DAMAGE. |
32 | * |
28 | * |
33 | * @(#)queue.h 8.5 (Berkeley) 8/20/94 |
29 | * @(#)queue.h 8.5 (Berkeley) 8/20/94 |
34 | * $FreeBSD: src/sys/sys/queue.h,v 1.48 2002/04/17 14:00:37 tmm Exp $ |
30 | * $FreeBSD$ |
35 | */ |
31 | */ |
Line 36... | Line 32... | ||
36 | 32 | ||
37 | #ifndef _SYS_QUEUE_H_ |
33 | #ifndef _SYS_QUEUE_H_ |
Line 38... | Line 34... | ||
38 | #define _SYS_QUEUE_H_ |
34 | #define _SYS_QUEUE_H_ |
Line 39... | Line 35... | ||
39 | 35 | ||
40 | #include |
36 | #include |
41 | 37 | ||
42 | /* |
38 | /* |
Line 67... | Line 63... | ||
67 | * A list is headed by a single forward pointer (or an array of forward |
63 | * 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 |
64 | * pointers for a hash table header). The elements are doubly linked |
69 | * so that an arbitrary element can be removed without a need to |
65 | * 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 |
66 | * 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 |
67 | * or after an existing element or at the head of the list. A list |
72 | * may only be traversed in the forward direction. |
68 | * may be traversed in either direction. |
73 | * |
69 | * |
74 | * A tail queue is headed by a pair of pointers, one to the head of the |
70 | * 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 |
71 | * 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 |
72 | * 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 |
73 | * traverse the list. New elements can be added to the list before or |
Line 87... | Line 83... | ||
87 | * _ENTRY + + + + |
83 | * _ENTRY + + + + |
88 | * _INIT + + + + |
84 | * _INIT + + + + |
89 | * _EMPTY + + + + |
85 | * _EMPTY + + + + |
90 | * _FIRST + + + + |
86 | * _FIRST + + + + |
91 | * _NEXT + + + + |
87 | * _NEXT + + + + |
92 | * _PREV - - - + |
88 | * _PREV - + - + |
93 | * _LAST - - + + |
89 | * _LAST - - + + |
94 | * _FOREACH + + + + |
90 | * _FOREACH + + + + |
- | 91 | * _FOREACH_SAFE + + + + |
|
95 | * _FOREACH_REVERSE - - - + |
92 | * _FOREACH_REVERSE - - - + |
- | 93 | * _FOREACH_REVERSE_SAFE - - - + |
|
96 | * _INSERT_HEAD + + + + |
94 | * _INSERT_HEAD + + + + |
97 | * _INSERT_BEFORE - + - + |
95 | * _INSERT_BEFORE - + - + |
98 | * _INSERT_AFTER + + + + |
96 | * _INSERT_AFTER + + + + |
99 | * _INSERT_TAIL - - + + |
97 | * _INSERT_TAIL - - + + |
100 | * _CONCAT - - + + |
98 | * _CONCAT - - + + |
- | 99 | * _REMOVE_AFTER + - + - |
|
101 | * _REMOVE_HEAD + - + - |
100 | * _REMOVE_HEAD + - + - |
102 | * _REMOVE + + + + |
101 | * _REMOVE + + + + |
- | 102 | * _SWAP + + + + |
|
103 | * |
103 | * |
104 | */ |
104 | */ |
- | 105 | #ifdef QUEUE_MACRO_DEBUG |
|
- | 106 | /* Store the last 2 places the queue element or head was altered */ |
|
- | 107 | struct qm_trace { |
|
- | 108 | unsigned long lastline; |
|
- | 109 | unsigned long prevline; |
|
- | 110 | const char *lastfile; |
|
- | 111 | const char *prevfile; |
|
- | 112 | }; |
|
- | 113 | ||
- | 114 | #define TRACEBUF struct qm_trace trace; |
|
- | 115 | #define TRACEBUF_INITIALIZER { __FILE__, __LINE__, NULL, 0 } , |
|
- | 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 TRACEBUF_INITIALIZER |
|
- | 139 | #define TRASHIT(x) |
|
- | 140 | #endif /* QUEUE_MACRO_DEBUG */ |
|
Line 105... | Line 141... | ||
105 | 141 | ||
106 | /* |
142 | /* |
107 | * Singly-linked List declarations. |
143 | * Singly-linked List declarations. |
108 | */ |
144 | */ |
Line 129... | Line 165... | ||
129 | #define SLIST_FOREACH(var, head, field) \ |
165 | #define SLIST_FOREACH(var, head, field) \ |
130 | for ((var) = SLIST_FIRST((head)); \ |
166 | for ((var) = SLIST_FIRST((head)); \ |
131 | (var); \ |
167 | (var); \ |
132 | (var) = SLIST_NEXT((var), field)) |
168 | (var) = SLIST_NEXT((var), field)) |
Line -... | Line 169... | ||
- | 169 | ||
- | 170 | #define SLIST_FOREACH_SAFE(var, head, field, tvar) \ |
|
- | 171 | for ((var) = SLIST_FIRST((head)); \ |
|
- | 172 | (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ |
|
- | 173 | (var) = (tvar)) |
|
- | 174 | ||
- | 175 | #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ |
|
- | 176 | for ((varp) = &SLIST_FIRST((head)); \ |
|
- | 177 | ((var) = *(varp)) != NULL; \ |
|
- | 178 | (varp) = &SLIST_NEXT((var), field)) |
|
133 | 179 | ||
134 | #define SLIST_INIT(head) do { \ |
180 | #define SLIST_INIT(head) do { \ |
135 | SLIST_FIRST((head)) = NULL; \ |
181 | SLIST_FIRST((head)) = NULL; \ |
Line 136... | Line 182... | ||
136 | } while (0) |
182 | } while (0) |
Line 146... | Line 192... | ||
146 | } while (0) |
192 | } while (0) |
Line 147... | Line 193... | ||
147 | 193 | ||
Line 148... | Line 194... | ||
148 | #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) |
194 | #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) |
- | 195 | ||
149 | 196 | #define SLIST_REMOVE(head, elm, type, field) do { \ |
|
150 | #define SLIST_REMOVE(head, elm, type, field) do { \ |
197 | QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ |
151 | if (SLIST_FIRST((head)) == (elm)) { \ |
198 | if (SLIST_FIRST((head)) == (elm)) { \ |
152 | SLIST_REMOVE_HEAD((head), field); \ |
199 | SLIST_REMOVE_HEAD((head), field); \ |
153 | } \ |
200 | } \ |
154 | else { \ |
201 | else { \ |
155 | struct type *curelm = SLIST_FIRST((head)); \ |
202 | struct type *curelm = SLIST_FIRST((head)); \ |
156 | while (SLIST_NEXT(curelm, field) != (elm)) \ |
203 | while (SLIST_NEXT(curelm, field) != (elm)) \ |
157 | curelm = SLIST_NEXT(curelm, field); \ |
- | |
158 | SLIST_NEXT(curelm, field) = \ |
204 | curelm = SLIST_NEXT(curelm, field); \ |
- | 205 | SLIST_REMOVE_AFTER(curelm, field); \ |
|
- | 206 | } \ |
|
- | 207 | TRASHIT(*oldnext); \ |
|
- | 208 | } while (0) |
|
- | 209 | ||
- | 210 | #define SLIST_REMOVE_AFTER(elm, field) do { \ |
|
159 | SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ |
211 | SLIST_NEXT(elm, field) = \ |
Line 160... | Line 212... | ||
160 | } \ |
212 | SLIST_NEXT(SLIST_NEXT(elm, field), field); \ |
161 | } while (0) |
213 | } while (0) |
162 | 214 | ||
Line -... | Line 215... | ||
- | 215 | #define SLIST_REMOVE_HEAD(head, field) do { \ |
|
- | 216 | SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ |
|
- | 217 | } while (0) |
|
- | 218 | ||
- | 219 | #define SLIST_SWAP(head1, head2, type) do { \ |
|
- | 220 | struct type *swap_first = SLIST_FIRST(head1); \ |
|
163 | #define SLIST_REMOVE_HEAD(head, field) do { \ |
221 | SLIST_FIRST(head1) = SLIST_FIRST(head2); \ |
164 | SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ |
222 | SLIST_FIRST(head2) = swap_first; \ |
165 | } while (0) |
223 | } while (0) |
166 | 224 | ||
167 | /* |
225 | /* |
Line 199... | Line 257... | ||
199 | #define STAILQ_FOREACH(var, head, field) \ |
257 | #define STAILQ_FOREACH(var, head, field) \ |
200 | for((var) = STAILQ_FIRST((head)); \ |
258 | for((var) = STAILQ_FIRST((head)); \ |
201 | (var); \ |
259 | (var); \ |
202 | (var) = STAILQ_NEXT((var), field)) |
260 | (var) = STAILQ_NEXT((var), field)) |
Line -... | Line 261... | ||
- | 261 | ||
- | 262 | ||
- | 263 | #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ |
|
- | 264 | for ((var) = STAILQ_FIRST((head)); \ |
|
- | 265 | (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ |
|
- | 266 | (var) = (tvar)) |
|
203 | 267 | ||
204 | #define STAILQ_INIT(head) do { \ |
268 | #define STAILQ_INIT(head) do { \ |
205 | STAILQ_FIRST((head)) = NULL; \ |
269 | STAILQ_FIRST((head)) = NULL; \ |
206 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
270 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
Line 223... | Line 287... | ||
223 | *(head)->stqh_last = (elm); \ |
287 | *(head)->stqh_last = (elm); \ |
224 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
288 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
225 | } while (0) |
289 | } while (0) |
Line 226... | Line 290... | ||
226 | 290 | ||
227 | #define STAILQ_LAST(head, type, field) \ |
291 | #define STAILQ_LAST(head, type, field) \ |
228 | (STAILQ_EMPTY((head)) ? \ |
- | |
229 | NULL : \ |
- | |
230 | ((struct type *) \ |
292 | (STAILQ_EMPTY((head)) ? NULL : \ |
Line 231... | Line 293... | ||
231 | ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) |
293 | __containerof((head)->stqh_last, struct type, field.stqe_next)) |
Line 232... | Line 294... | ||
232 | 294 | ||
- | 295 | #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) |
|
233 | #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) |
296 | |
234 | 297 | #define STAILQ_REMOVE(head, elm, type, field) do { \ |
|
235 | #define STAILQ_REMOVE(head, elm, type, field) do { \ |
298 | QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ |
236 | if (STAILQ_FIRST((head)) == (elm)) { \ |
299 | if (STAILQ_FIRST((head)) == (elm)) { \ |
237 | STAILQ_REMOVE_HEAD((head), field); \ |
300 | STAILQ_REMOVE_HEAD((head), field); \ |
238 | } \ |
301 | } \ |
239 | else { \ |
302 | else { \ |
240 | struct type *curelm = STAILQ_FIRST((head)); \ |
303 | struct type *curelm = STAILQ_FIRST((head)); \ |
241 | while (STAILQ_NEXT(curelm, field) != (elm)) \ |
- | |
242 | curelm = STAILQ_NEXT(curelm, field); \ |
- | |
243 | if ((STAILQ_NEXT(curelm, field) = \ |
304 | while (STAILQ_NEXT(curelm, field) != (elm)) \ |
- | 305 | curelm = STAILQ_NEXT(curelm, field); \ |
|
- | 306 | STAILQ_REMOVE_AFTER(head, curelm, field); \ |
|
- | 307 | } \ |
|
- | 308 | TRASHIT(*oldnext); \ |
|
- | 309 | } while (0) |
|
- | 310 | ||
- | 311 | #define STAILQ_REMOVE_AFTER(head, elm, field) do { \ |
|
244 | STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ |
312 | if ((STAILQ_NEXT(elm, field) = \ |
Line 245... | Line 313... | ||
245 | (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ |
313 | STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ |
246 | } \ |
314 | (head)->stqh_last = &STAILQ_NEXT((elm), field); \ |
247 | } while (0) |
315 | } while (0) |
Line 255... | Line 323... | ||
255 | #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ |
323 | #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ |
256 | if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ |
324 | if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ |
257 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
325 | (head)->stqh_last = &STAILQ_FIRST((head)); \ |
258 | } while (0) |
326 | } while (0) |
Line -... | Line 327... | ||
- | 327 | ||
- | 328 | #define STAILQ_SWAP(head1, head2, type) do { \ |
|
- | 329 | struct type *swap_first = STAILQ_FIRST(head1); \ |
|
- | 330 | struct type **swap_last = (head1)->stqh_last; \ |
|
- | 331 | STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ |
|
- | 332 | (head1)->stqh_last = (head2)->stqh_last; \ |
|
- | 333 | STAILQ_FIRST(head2) = swap_first; \ |
|
- | 334 | (head2)->stqh_last = swap_last; \ |
|
- | 335 | if (STAILQ_EMPTY(head1)) \ |
|
- | 336 | (head1)->stqh_last = &STAILQ_FIRST(head1); \ |
|
- | 337 | if (STAILQ_EMPTY(head2)) \ |
|
- | 338 | (head2)->stqh_last = &STAILQ_FIRST(head2); \ |
|
- | 339 | } while (0) |
|
- | 340 | ||
259 | 341 | ||
260 | /* |
342 | /* |
261 | * List declarations. |
343 | * List declarations. |
262 | */ |
344 | */ |
263 | #define LIST_HEAD(name, type) \ |
345 | #define LIST_HEAD(name, type) \ |
Line 276... | Line 358... | ||
276 | 358 | ||
277 | /* |
359 | /* |
278 | * List functions. |
360 | * List functions. |
Line -... | Line 361... | ||
- | 361 | */ |
|
- | 362 | ||
- | 363 | #if (defined(_KERNEL) && defined(INVARIANTS)) |
|
- | 364 | #define QMD_LIST_CHECK_HEAD(head, field) do { \ |
|
- | 365 | if (LIST_FIRST((head)) != NULL && \ |
|
- | 366 | LIST_FIRST((head))->field.le_prev != \ |
|
- | 367 | &LIST_FIRST((head))) \ |
|
- | 368 | panic("Bad list head %p first->prev != head", (head)); \ |
|
- | 369 | } while (0) |
|
- | 370 | ||
- | 371 | #define QMD_LIST_CHECK_NEXT(elm, field) do { \ |
|
- | 372 | if (LIST_NEXT((elm), field) != NULL && \ |
|
- | 373 | LIST_NEXT((elm), field)->field.le_prev != \ |
|
- | 374 | &((elm)->field.le_next)) \ |
|
- | 375 | panic("Bad link elm %p next->prev != elm", (elm)); \ |
|
- | 376 | } while (0) |
|
- | 377 | ||
- | 378 | #define QMD_LIST_CHECK_PREV(elm, field) do { \ |
|
- | 379 | if (*(elm)->field.le_prev != (elm)) \ |
|
- | 380 | panic("Bad link elm %p prev->next != elm", (elm)); \ |
|
- | 381 | } while (0) |
|
- | 382 | #else |
|
- | 383 | #define QMD_LIST_CHECK_HEAD(head, field) |
|
- | 384 | #define QMD_LIST_CHECK_NEXT(elm, field) |
|
- | 385 | #define QMD_LIST_CHECK_PREV(elm, field) |
|
279 | */ |
386 | #endif /* (_KERNEL && INVARIANTS) */ |
Line 280... | Line 387... | ||
280 | 387 | ||
Line 281... | Line 388... | ||
281 | #define LIST_EMPTY(head) ((head)->lh_first == NULL) |
388 | #define LIST_EMPTY(head) ((head)->lh_first == NULL) |
282 | 389 | ||
283 | #define LIST_FIRST(head) ((head)->lh_first) |
390 | #define LIST_FIRST(head) ((head)->lh_first) |
284 | 391 | ||
Line -... | Line 392... | ||
- | 392 | #define LIST_FOREACH(var, head, field) \ |
|
- | 393 | for ((var) = LIST_FIRST((head)); \ |
|
- | 394 | (var); \ |
|
- | 395 | (var) = LIST_NEXT((var), field)) |
|
- | 396 | ||
285 | #define LIST_FOREACH(var, head, field) \ |
397 | #define LIST_FOREACH_SAFE(var, head, field, tvar) \ |
286 | for ((var) = LIST_FIRST((head)); \ |
398 | for ((var) = LIST_FIRST((head)); \ |
287 | (var); \ |
399 | (var) && ((tvar) = LIST_NEXT((var), field), 1); \ |
Line 288... | Line 400... | ||
288 | (var) = LIST_NEXT((var), field)) |
400 | (var) = (tvar)) |
- | 401 | ||
289 | 402 | #define LIST_INIT(head) do { \ |
|
290 | #define LIST_INIT(head) do { \ |
403 | LIST_FIRST((head)) = NULL; \ |
291 | LIST_FIRST((head)) = NULL; \ |
404 | } while (0) |
292 | } while (0) |
405 | |
293 | 406 | #define LIST_INSERT_AFTER(listelm, elm, field) do { \ |
|
294 | #define LIST_INSERT_AFTER(listelm, elm, field) do { \ |
407 | QMD_LIST_CHECK_NEXT(listelm, field); \ |
Line 295... | Line 408... | ||
295 | if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ |
408 | if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ |
- | 409 | LIST_NEXT((listelm), field)->field.le_prev = \ |
|
296 | LIST_NEXT((listelm), field)->field.le_prev = \ |
410 | &LIST_NEXT((elm), field); \ |
297 | &LIST_NEXT((elm), field); \ |
411 | LIST_NEXT((listelm), field) = (elm); \ |
298 | LIST_NEXT((listelm), field) = (elm); \ |
412 | (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ |
299 | (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ |
413 | } while (0) |
300 | } while (0) |
414 | |
Line 301... | Line 415... | ||
301 | 415 | #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ |
|
- | 416 | QMD_LIST_CHECK_PREV(listelm, field); \ |
|
302 | #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ |
417 | (elm)->field.le_prev = (listelm)->field.le_prev; \ |
303 | (elm)->field.le_prev = (listelm)->field.le_prev; \ |
418 | LIST_NEXT((elm), field) = (listelm); \ |
304 | LIST_NEXT((elm), field) = (listelm); \ |
419 | *(listelm)->field.le_prev = (elm); \ |
305 | *(listelm)->field.le_prev = (elm); \ |
420 | (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ |
306 | (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ |
421 | } while (0) |
Line 307... | Line 422... | ||
307 | } while (0) |
422 | |
Line -... | Line 423... | ||
- | 423 | #define LIST_INSERT_HEAD(head, elm, field) do { \ |
|
- | 424 | QMD_LIST_CHECK_HEAD((head), field); \ |
|
- | 425 | if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ |
|
- | 426 | LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ |
|
308 | 427 | LIST_FIRST((head)) = (elm); \ |
|
- | 428 | (elm)->field.le_prev = &LIST_FIRST((head)); \ |
|
- | 429 | } while (0) |
|
- | 430 | ||
- | 431 | #define LIST_NEXT(elm, field) ((elm)->field.le_next) |
|
309 | #define LIST_INSERT_HEAD(head, elm, field) do { \ |
432 | |
310 | if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ |
433 | #define LIST_PREV(elm, head, type, field) \ |
311 | LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ |
434 | ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ |
312 | LIST_FIRST((head)) = (elm); \ |
435 | __containerof((elm)->field.le_prev, struct type, field.le_next)) |
- | 436 | ||
- | 437 | #define LIST_REMOVE(elm, field) do { \ |
|
- | 438 | QMD_SAVELINK(oldnext, (elm)->field.le_next); \ |
|
- | 439 | QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ |
|
- | 440 | QMD_LIST_CHECK_NEXT(elm, field); \ |
|
- | 441 | QMD_LIST_CHECK_PREV(elm, field); \ |
|
- | 442 | if (LIST_NEXT((elm), field) != NULL) \ |
|
- | 443 | LIST_NEXT((elm), field)->field.le_prev = \ |
|
- | 444 | (elm)->field.le_prev; \ |
|
- | 445 | *(elm)->field.le_prev = LIST_NEXT((elm), field); \ |
|
- | 446 | TRASHIT(*oldnext); \ |
|
- | 447 | TRASHIT(*oldprev); \ |
|
313 | (elm)->field.le_prev = &LIST_FIRST((head)); \ |
448 | } while (0) |
Line 314... | Line 449... | ||
314 | } while (0) |
449 | |
315 | 450 | #define LIST_SWAP(head1, head2, type, field) do { \ |
|
316 | #define LIST_NEXT(elm, field) ((elm)->field.le_next) |
451 | struct type *swap_tmp = LIST_FIRST((head1)); \ |
317 | 452 | LIST_FIRST((head1)) = LIST_FIRST((head2)); \ |
|
318 | #define LIST_REMOVE(elm, field) do { \ |
453 | LIST_FIRST((head2)) = swap_tmp; \ |
319 | if (LIST_NEXT((elm), field) != NULL) \ |
454 | if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ |
320 | LIST_NEXT((elm), field)->field.le_prev = \ |
455 | swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ |
- | 456 | if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ |
|
321 | (elm)->field.le_prev; \ |
457 | swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ |
Line 322... | Line 458... | ||
322 | *(elm)->field.le_prev = LIST_NEXT((elm), field); \ |
458 | } while (0) |
323 | } while (0) |
459 | |
Line 324... | Line 460... | ||
324 | 460 | /* |
|
325 | /* |
461 | * Tail queue declarations. |
326 | * Tail queue declarations. |
462 | */ |
327 | */ |
463 | #define TAILQ_HEAD(name, type) \ |
- | 464 | struct name { \ |
|
328 | #define TAILQ_HEAD(name, type) \ |
465 | struct type *tqh_first; /* first element */ \ |
Line 329... | Line 466... | ||
329 | struct name { \ |
466 | struct type **tqh_last; /* addr of last next element */ \ |
330 | struct type *tqh_first; /* first element */ \ |
467 | TRACEBUF \ |
331 | struct type **tqh_last; /* addr of last next element */ \ |
468 | } |
- | 469 | ||
- | 470 | #define TAILQ_HEAD_INITIALIZER(head) \ |
|
- | 471 | { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } |
|
- | 472 | ||
- | 473 | #define TAILQ_ENTRY(type) \ |
|
- | 474 | struct { \ |
|
- | 475 | struct type *tqe_next; /* next element */ \ |
|
- | 476 | struct type **tqe_prev; /* address of previous next element */ \ |
|
- | 477 | TRACEBUF \ |
|
- | 478 | } |
|
- | 479 | ||
- | 480 | /* |
|
- | 481 | * Tail queue functions. |
|
- | 482 | */ |
|
- | 483 | #if (defined(_KERNEL) && defined(INVARIANTS)) |
|
- | 484 | #define QMD_TAILQ_CHECK_HEAD(head, field) do { \ |
|
- | 485 | if (!TAILQ_EMPTY(head) && \ |
|
- | 486 | TAILQ_FIRST((head))->field.tqe_prev != \ |
|
- | 487 | &TAILQ_FIRST((head))) \ |
|
- | 488 | panic("Bad tailq head %p first->prev != head", (head)); \ |
|
- | 489 | } while (0) |
|
- | 490 | ||
- | 491 | #define QMD_TAILQ_CHECK_TAIL(head, field) do { \ |
|
- | 492 | if (*(head)->tqh_last != NULL) \ |
|
- | 493 | panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ |
|
- | 494 | } while (0) |
|
- | 495 | ||
- | 496 | #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ |
|
- | 497 | if (TAILQ_NEXT((elm), field) != NULL && \ |
|
- | 498 | TAILQ_NEXT((elm), field)->field.tqe_prev != \ |
|
- | 499 | &((elm)->field.tqe_next)) \ |
|
332 | } |
500 | panic("Bad link elm %p next->prev != elm", (elm)); \ |
333 | 501 | } while (0) |
|
334 | #define TAILQ_HEAD_INITIALIZER(head) \ |
502 | |
335 | { NULL, &(head).tqh_first } |
503 | #define QMD_TAILQ_CHECK_PREV(elm, field) do { \ |
336 | 504 | if (*(elm)->field.tqe_prev != (elm)) \ |
|
337 | #define TAILQ_ENTRY(type) \ |
505 | panic("Bad link elm %p prev->next != elm", (elm)); \ |
- | 506 | } while (0) |
|
- | 507 | #else |
|
338 | struct { \ |
508 | #define QMD_TAILQ_CHECK_HEAD(head, field) |
339 | struct type *tqe_next; /* next element */ \ |
509 | #define QMD_TAILQ_CHECK_TAIL(head, headname) |
Line 340... | Line 510... | ||
340 | struct type **tqe_prev; /* address of previous next element */ \ |
510 | #define QMD_TAILQ_CHECK_NEXT(elm, field) |
Line 359... | Line 529... | ||
359 | #define TAILQ_FOREACH(var, head, field) \ |
529 | #define TAILQ_FOREACH(var, head, field) \ |
360 | for ((var) = TAILQ_FIRST((head)); \ |
530 | for ((var) = TAILQ_FIRST((head)); \ |
361 | (var); \ |
531 | (var); \ |
362 | (var) = TAILQ_NEXT((var), field)) |
532 | (var) = TAILQ_NEXT((var), field)) |
Line -... | Line 533... | ||
- | 533 | ||
- | 534 | #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ |
|
- | 535 | for ((var) = TAILQ_FIRST((head)); \ |
|
- | 536 | (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ |
|
- | 537 | (var) = (tvar)) |
|
363 | 538 | ||
364 | #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ |
539 | #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ |
365 | for ((var) = TAILQ_LAST((head), headname); \ |
540 | for ((var) = TAILQ_LAST((head), headname); \ |
366 | (var); \ |
541 | (var); \ |
Line -... | Line 542... | ||
- | 542 | (var) = TAILQ_PREV((var), headname, field)) |
|
- | 543 | ||
- | 544 | #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ |
|
- | 545 | for ((var) = TAILQ_LAST((head), headname); \ |
|
- | 546 | (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ |
|
367 | (var) = TAILQ_PREV((var), headname, field)) |
547 | (var) = (tvar)) |
368 | 548 | ||
369 | #define TAILQ_INIT(head) do { \ |
549 | #define TAILQ_INIT(head) do { \ |
- | 550 | TAILQ_FIRST((head)) = NULL; \ |
|
370 | TAILQ_FIRST((head)) = NULL; \ |
551 | (head)->tqh_last = &TAILQ_FIRST((head)); \ |
Line 371... | Line 552... | ||
371 | (head)->tqh_last = &TAILQ_FIRST((head)); \ |
552 | QMD_TRACE_HEAD(head); \ |
- | 553 | } while (0) |
|
372 | } while (0) |
554 | |
373 | 555 | #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ |
|
374 | #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ |
556 | QMD_TAILQ_CHECK_NEXT(listelm, field); \ |
375 | if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ |
557 | if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ |
376 | TAILQ_NEXT((elm), field)->field.tqe_prev = \ |
558 | TAILQ_NEXT((elm), field)->field.tqe_prev = \ |
- | 559 | &TAILQ_NEXT((elm), field); \ |
|
- | 560 | else { \ |
|
377 | &TAILQ_NEXT((elm), field); \ |
561 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
378 | else \ |
562 | QMD_TRACE_HEAD(head); \ |
- | 563 | } \ |
|
- | 564 | TAILQ_NEXT((listelm), field) = (elm); \ |
|
379 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
565 | (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ |
Line 380... | Line 566... | ||
380 | TAILQ_NEXT((listelm), field) = (elm); \ |
566 | QMD_TRACE_ELEM(&(elm)->field); \ |
- | 567 | QMD_TRACE_ELEM(&listelm->field); \ |
|
381 | (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ |
568 | } while (0) |
382 | } while (0) |
569 | |
383 | 570 | #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ |
|
384 | #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ |
571 | QMD_TAILQ_CHECK_PREV(listelm, field); \ |
- | 572 | (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ |
|
- | 573 | TAILQ_NEXT((elm), field) = (listelm); \ |
|
385 | (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ |
574 | *(listelm)->field.tqe_prev = (elm); \ |
Line 386... | Line 575... | ||
386 | TAILQ_NEXT((elm), field) = (listelm); \ |
575 | (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ |
- | 576 | QMD_TRACE_ELEM(&(elm)->field); \ |
|
387 | *(listelm)->field.tqe_prev = (elm); \ |
577 | QMD_TRACE_ELEM(&listelm->field); \ |
388 | (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ |
578 | } while (0) |
389 | } while (0) |
579 | |
390 | 580 | #define TAILQ_INSERT_HEAD(head, elm, field) do { \ |
|
391 | #define TAILQ_INSERT_HEAD(head, elm, field) do { \ |
581 | QMD_TAILQ_CHECK_HEAD(head, field); \ |
392 | if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ |
582 | if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ |
393 | TAILQ_FIRST((head))->field.tqe_prev = \ |
583 | TAILQ_FIRST((head))->field.tqe_prev = \ |
- | 584 | &TAILQ_NEXT((elm), field); \ |
|
- | 585 | else \ |
|
394 | &TAILQ_NEXT((elm), field); \ |
586 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
Line 395... | Line 587... | ||
395 | else \ |
587 | TAILQ_FIRST((head)) = (elm); \ |
- | 588 | (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ |
|
396 | (head)->tqh_last = &TAILQ_NEXT((elm), field); \ |
589 | QMD_TRACE_HEAD(head); \ |
397 | TAILQ_FIRST((head)) = (elm); \ |
590 | QMD_TRACE_ELEM(&(elm)->field); \ |
398 | (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ |
591 | } while (0) |
399 | } while (0) |
592 | |
- | 593 | #define TAILQ_INSERT_TAIL(head, elm, field) do { \ |
|
- | 594 | QMD_TAILQ_CHECK_TAIL(head, field); \ |
|
400 | 595 | TAILQ_NEXT((elm), field) = NULL; \ |
|
Line 401... | Line 596... | ||
401 | #define TAILQ_INSERT_TAIL(head, elm, field) do { \ |
596 | (elm)->field.tqe_prev = (head)->tqh_last; \ |
402 | TAILQ_NEXT((elm), field) = NULL; \ |
597 | *(head)->tqh_last = (elm); \ |
Line 412... | Line 607... | ||
412 | 607 | ||
413 | #define TAILQ_PREV(elm, headname, field) \ |
608 | #define TAILQ_PREV(elm, headname, field) \ |
Line 414... | Line 609... | ||
414 | (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) |
609 | (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) |
- | 610 | ||
- | 611 | #define TAILQ_REMOVE(head, elm, field) do { \ |
|
- | 612 | QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ |
|
- | 613 | QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ |
|
415 | 614 | QMD_TAILQ_CHECK_NEXT(elm, field); \ |
|
416 | #define TAILQ_REMOVE(head, elm, field) do { \ |
615 | QMD_TAILQ_CHECK_PREV(elm, field); \ |
417 | if ((TAILQ_NEXT((elm), field)) != NULL) \ |
616 | if ((TAILQ_NEXT((elm), field)) != NULL) \ |
418 | TAILQ_NEXT((elm), field)->field.tqe_prev = \ |
617 | TAILQ_NEXT((elm), field)->field.tqe_prev = \ |
419 | (elm)->field.tqe_prev; \ |
618 | (elm)->field.tqe_prev; \ |
- | 619 | else { \ |
|
- | 620 | (head)->tqh_last = (elm)->field.tqe_prev; \ |
|
420 | else \ |
621 | QMD_TRACE_HEAD(head); \ |
- | 622 | } \ |
|
- | 623 | *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ |
|
- | 624 | TRASHIT(*oldnext); \ |
|
421 | (head)->tqh_last = (elm)->field.tqe_prev; \ |
625 | TRASHIT(*oldprev); \ |
Line -... | Line 626... | ||
- | 626 | QMD_TRACE_ELEM(&(elm)->field); \ |
|
- | 627 | } while (0) |
|
- | 628 | ||
- | 629 | #define TAILQ_SWAP(head1, head2, type, field) do { \ |
|
- | 630 | struct type *swap_first = (head1)->tqh_first; \ |
|
- | 631 | struct type **swap_last = (head1)->tqh_last; \ |
|
- | 632 | (head1)->tqh_first = (head2)->tqh_first; \ |
|
- | 633 | (head1)->tqh_last = (head2)->tqh_last; \ |
|
- | 634 | (head2)->tqh_first = swap_first; \ |
|
- | 635 | (head2)->tqh_last = swap_last; \ |
|
- | 636 | if ((swap_first = (head1)->tqh_first) != NULL) \ |
|
- | 637 | swap_first->field.tqe_prev = &(head1)->tqh_first; \ |
|
- | 638 | else \ |
|
- | 639 | (head1)->tqh_last = &(head1)->tqh_first; \ |
|
- | 640 | if ((swap_first = (head2)->tqh_first) != NULL) \ |
|
- | 641 | swap_first->field.tqe_prev = &(head2)->tqh_first; \ |
|
Line 422... | Line 642... | ||
422 | *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ |
642 | else \ |
Line 423... | Line 643... | ||
423 | } while (0) |
643 | (head2)->tqh_last = &(head2)->tqh_first; \ |
424 | 644 | } while (0) |