00001 #ifndef _SYS_QUEUE_H_
00002 #define _SYS_QUEUE_H_
00003
00004 #ifdef QUEUE_MACRO_DEBUG
00005
00006 struct qm_trace {
00007 char *lastfile;
00008 int lastline;
00009 char *prevfile;
00010 int prevline;
00011 };
00012
00013 #define TRACEBUF struct qm_trace trace;
00014 #define TRASHIT(x) do {(x) = (void *)-1;} while (0)
00015
00016 #define QMD_TRACE_HEAD(head) do { \
00017 (head)->trace.prevline = (head)->trace.lastline; \
00018 (head)->trace.prevfile = (head)->trace.lastfile; \
00019 (head)->trace.lastline = __LINE__; \
00020 (head)->trace.lastfile = __FILE__; \
00021 } while (0)
00022
00023 #define QMD_TRACE_ELEM(elem) do { \
00024 (elem)->trace.prevline = (elem)->trace.lastline; \
00025 (elem)->trace.prevfile = (elem)->trace.lastfile; \
00026 (elem)->trace.lastline = __LINE__; \
00027 (elem)->trace.lastfile = __FILE__; \
00028 } while (0)
00029
00030 #else
00031 #define QMD_TRACE_ELEM(elem)
00032 #define QMD_TRACE_HEAD(head)
00033 #define TRACEBUF
00034 #define TRASHIT(x)
00035 #endif
00036
00037
00038
00039
00040 #define SLIST_HEAD(name, type) \
00041 struct name { \
00042 struct type *slh_first; \
00043 }
00044
00045 #define SLIST_HEAD_INITIALIZER(head) \
00046 { NULL }
00047
00048 #define SLIST_ENTRY(type) \
00049 struct { \
00050 struct type *sle_next; \
00051 }
00052
00053
00054
00055
00056 #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
00057
00058 #define SLIST_FIRST(head) ((head)->slh_first)
00059
00060 #define SLIST_FOREACH(var, head, field) \
00061 for ((var) = SLIST_FIRST((head)); \
00062 (var); \
00063 (var) = SLIST_NEXT((var), field))
00064
00065 #define SLIST_FOREACH_SAFE(var, head, field, tvar) \
00066 for ((var) = SLIST_FIRST((head)); \
00067 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
00068 (var) = (tvar))
00069
00070 #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
00071 for ((varp) = &SLIST_FIRST((head)); \
00072 ((var) = *(varp)) != NULL; \
00073 (varp) = &SLIST_NEXT((var), field))
00074
00075 #define SLIST_INIT(head) do { \
00076 SLIST_FIRST((head)) = NULL; \
00077 } while (0)
00078
00079 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
00080 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
00081 SLIST_NEXT((slistelm), field) = (elm); \
00082 } while (0)
00083
00084 #define SLIST_INSERT_HEAD(head, elm, field) do { \
00085 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
00086 SLIST_FIRST((head)) = (elm); \
00087 } while (0)
00088
00089 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
00090
00091 #define SLIST_REMOVE(head, elm, type, field) do { \
00092 if (SLIST_FIRST((head)) == (elm)) { \
00093 SLIST_REMOVE_HEAD((head), field); \
00094 } \
00095 else { \
00096 struct type *curelm = SLIST_FIRST((head)); \
00097 while (SLIST_NEXT(curelm, field) != (elm)) \
00098 curelm = SLIST_NEXT(curelm, field); \
00099 SLIST_NEXT(curelm, field) = \
00100 SLIST_NEXT(SLIST_NEXT(curelm, field), field); \
00101 } \
00102 TRASHIT((elm)->field.sle_next); \
00103 } while (0)
00104
00105 #define SLIST_REMOVE_HEAD(head, field) do { \
00106 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
00107 } while (0)
00108
00109
00110
00111
00112 #define STAILQ_HEAD(name, type) \
00113 struct name { \
00114 struct type *stqh_first; \
00115 struct type **stqh_last; \
00116 }
00117
00118 #define STAILQ_HEAD_INITIALIZER(head) \
00119 { NULL, &(head).stqh_first }
00120
00121 #define STAILQ_ENTRY(type) \
00122 struct { \
00123 struct type *stqe_next; \
00124 }
00125
00126
00127
00128
00129 #define STAILQ_CONCAT(head1, head2) do { \
00130 if (!STAILQ_EMPTY((head2))) { \
00131 *(head1)->stqh_last = (head2)->stqh_first; \
00132 (head1)->stqh_last = (head2)->stqh_last; \
00133 STAILQ_INIT((head2)); \
00134 } \
00135 } while (0)
00136
00137 #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
00138
00139 #define STAILQ_FIRST(head) ((head)->stqh_first)
00140
00141 #define STAILQ_FOREACH(var, head, field) \
00142 for((var) = STAILQ_FIRST((head)); \
00143 (var); \
00144 (var) = STAILQ_NEXT((var), field))
00145
00146
00147 #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
00148 for ((var) = STAILQ_FIRST((head)); \
00149 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
00150 (var) = (tvar))
00151
00152 #define STAILQ_INIT(head) do { \
00153 STAILQ_FIRST((head)) = NULL; \
00154 (head)->stqh_last = &STAILQ_FIRST((head)); \
00155 } while (0)
00156
00157 #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
00158 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
00159 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
00160 STAILQ_NEXT((tqelm), field) = (elm); \
00161 } while (0)
00162
00163 #define STAILQ_INSERT_HEAD(head, elm, field) do { \
00164 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
00165 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
00166 STAILQ_FIRST((head)) = (elm); \
00167 } while (0)
00168
00169 #define STAILQ_INSERT_TAIL(head, elm, field) do { \
00170 STAILQ_NEXT((elm), field) = NULL; \
00171 *(head)->stqh_last = (elm); \
00172 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
00173 } while (0)
00174
00175 #define STAILQ_LAST(head, type, field) \
00176 (STAILQ_EMPTY((head)) ? \
00177 NULL : \
00178 ((struct type *)(void *) \
00179 ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
00180
00181 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
00182
00183 #define STAILQ_REMOVE(head, elm, type, field) do { \
00184 if (STAILQ_FIRST((head)) == (elm)) { \
00185 STAILQ_REMOVE_HEAD((head), field); \
00186 } \
00187 else { \
00188 struct type *curelm = STAILQ_FIRST((head)); \
00189 while (STAILQ_NEXT(curelm, field) != (elm)) \
00190 curelm = STAILQ_NEXT(curelm, field); \
00191 if ((STAILQ_NEXT(curelm, field) = \
00192 STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
00193 (head)->stqh_last = &STAILQ_NEXT((curelm), field);\
00194 } \
00195 TRASHIT((elm)->field.stqe_next); \
00196 } while (0)
00197
00198 #define STAILQ_REMOVE_HEAD(head, field) do { \
00199 if ((STAILQ_FIRST((head)) = \
00200 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
00201 (head)->stqh_last = &STAILQ_FIRST((head)); \
00202 } while (0)
00203
00204 #define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
00205 if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
00206 (head)->stqh_last = &STAILQ_FIRST((head)); \
00207 } while (0)
00208
00209
00210
00211
00212 #define LIST_HEAD(name, type) \
00213 struct name { \
00214 struct type *lh_first; \
00215 }
00216
00217 #define LIST_HEAD_INITIALIZER(head) \
00218 { NULL }
00219
00220 #define LIST_ENTRY(type) \
00221 struct { \
00222 struct type *le_next; \
00223 struct type **le_prev; \
00224 }
00225
00226
00227
00228
00229
00230 #if (defined(_KERNEL) && defined(INVARIANTS)) || defined(QUEUE_MACRO_DEBUG)
00231 #define QMD_LIST_CHECK_HEAD(head, field) do { \
00232 if (LIST_FIRST((head)) != NULL && \
00233 LIST_FIRST((head))->field.le_prev != \
00234 &LIST_FIRST((head))) \
00235 panic("Bad list head %p first->prev != head", (head)); \
00236 } while (0)
00237
00238 #define QMD_LIST_CHECK_NEXT(elm, field) do { \
00239 if (LIST_NEXT((elm), field) != NULL && \
00240 LIST_NEXT((elm), field)->field.le_prev != \
00241 &((elm)->field.le_next)) \
00242 panic("Bad link elm %p next->prev != elm", (elm)); \
00243 } while (0)
00244
00245 #define QMD_LIST_CHECK_PREV(elm, field) do { \
00246 if (*(elm)->field.le_prev != (elm)) \
00247 panic("Bad link elm %p prev->next != elm", (elm)); \
00248 } while (0)
00249 #else
00250 #define QMD_LIST_CHECK_HEAD(head, field)
00251 #define QMD_LIST_CHECK_NEXT(elm, field)
00252 #define QMD_LIST_CHECK_PREV(elm, field)
00253 #endif
00254
00255 #define LIST_EMPTY(head) ((head)->lh_first == NULL)
00256
00257 #define LIST_FIRST(head) ((head)->lh_first)
00258
00259 #define LIST_FOREACH(var, head, field) \
00260 for ((var) = LIST_FIRST((head)); \
00261 (var); \
00262 (var) = LIST_NEXT((var), field))
00263
00264 #define LIST_FOREACH_SAFE(var, head, field, tvar) \
00265 for ((var) = LIST_FIRST((head)); \
00266 (var) && ((tvar) = LIST_NEXT((var), field), 1); \
00267 (var) = (tvar))
00268
00269 #define LIST_INIT(head) do { \
00270 LIST_FIRST((head)) = NULL; \
00271 } while (0)
00272
00273 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
00274 QMD_LIST_CHECK_NEXT(listelm, field); \
00275 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
00276 LIST_NEXT((listelm), field)->field.le_prev = \
00277 &LIST_NEXT((elm), field); \
00278 LIST_NEXT((listelm), field) = (elm); \
00279 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
00280 } while (0)
00281
00282 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
00283 QMD_LIST_CHECK_PREV(listelm, field); \
00284 (elm)->field.le_prev = (listelm)->field.le_prev; \
00285 LIST_NEXT((elm), field) = (listelm); \
00286 *(listelm)->field.le_prev = (elm); \
00287 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
00288 } while (0)
00289
00290 #define LIST_INSERT_HEAD(head, elm, field) do { \
00291 QMD_LIST_CHECK_HEAD((head), field); \
00292 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
00293 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
00294 LIST_FIRST((head)) = (elm); \
00295 (elm)->field.le_prev = &LIST_FIRST((head)); \
00296 } while (0)
00297
00298 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
00299
00300 #define LIST_REMOVE(elm, field) do { \
00301 QMD_LIST_CHECK_NEXT(elm, field); \
00302 QMD_LIST_CHECK_PREV(elm, field); \
00303 if (LIST_NEXT((elm), field) != NULL) \
00304 LIST_NEXT((elm), field)->field.le_prev = \
00305 (elm)->field.le_prev; \
00306 *(elm)->field.le_prev = LIST_NEXT((elm), field); \
00307 TRASHIT((elm)->field.le_next); \
00308 TRASHIT((elm)->field.le_prev); \
00309 } while (0)
00310
00311
00312
00313
00314 #define TAILQ_HEAD(name, type) \
00315 struct name { \
00316 struct type *tqh_first; \
00317 struct type **tqh_last; \
00318 TRACEBUF \
00319 }
00320
00321 #define TAILQ_HEAD_INITIALIZER(head) \
00322 { NULL, &(head).tqh_first }
00323
00324 #define TAILQ_ENTRY(type) \
00325 struct { \
00326 struct type *tqe_next; \
00327 struct type **tqe_prev; \
00328 TRACEBUF \
00329 }
00330
00331
00332
00333
00334 #define TAILQ_CONCAT(head1, head2, field) do { \
00335 if (!TAILQ_EMPTY(head2)) { \
00336 *(head1)->tqh_last = (head2)->tqh_first; \
00337 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
00338 (head1)->tqh_last = (head2)->tqh_last; \
00339 TAILQ_INIT((head2)); \
00340 QMD_TRACE_HEAD(head1); \
00341 QMD_TRACE_HEAD(head2); \
00342 } \
00343 } while (0)
00344
00345 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
00346
00347 #define TAILQ_FIRST(head) ((head)->tqh_first)
00348
00349 #define TAILQ_FOREACH(var, head, field) \
00350 for ((var) = TAILQ_FIRST((head)); \
00351 (var); \
00352 (var) = TAILQ_NEXT((var), field))
00353
00354 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
00355 for ((var) = TAILQ_FIRST((head)); \
00356 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
00357 (var) = (tvar))
00358
00359 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
00360 for ((var) = TAILQ_LAST((head), headname); \
00361 (var); \
00362 (var) = TAILQ_PREV((var), headname, field))
00363
00364 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
00365 for ((var) = TAILQ_LAST((head), headname); \
00366 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
00367 (var) = (tvar))
00368
00369 #define TAILQ_INIT(head) do { \
00370 TAILQ_FIRST((head)) = NULL; \
00371 (head)->tqh_last = &TAILQ_FIRST((head)); \
00372 QMD_TRACE_HEAD(head); \
00373 } while (0)
00374
00375 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
00376 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
00377 TAILQ_NEXT((elm), field)->field.tqe_prev = \
00378 &TAILQ_NEXT((elm), field); \
00379 else { \
00380 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
00381 QMD_TRACE_HEAD(head); \
00382 } \
00383 TAILQ_NEXT((listelm), field) = (elm); \
00384 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
00385 QMD_TRACE_ELEM(&(elm)->field); \
00386 QMD_TRACE_ELEM(&listelm->field); \
00387 } while (0)
00388
00389 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
00390 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
00391 TAILQ_NEXT((elm), field) = (listelm); \
00392 *(listelm)->field.tqe_prev = (elm); \
00393 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
00394 QMD_TRACE_ELEM(&(elm)->field); \
00395 QMD_TRACE_ELEM(&listelm->field); \
00396 } while (0)
00397
00398 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
00399 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
00400 TAILQ_FIRST((head))->field.tqe_prev = \
00401 &TAILQ_NEXT((elm), field); \
00402 else \
00403 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
00404 TAILQ_FIRST((head)) = (elm); \
00405 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
00406 QMD_TRACE_HEAD(head); \
00407 QMD_TRACE_ELEM(&(elm)->field); \
00408 } while (0)
00409
00410 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
00411 TAILQ_NEXT((elm), field) = NULL; \
00412 (elm)->field.tqe_prev = (head)->tqh_last; \
00413 *(head)->tqh_last = (elm); \
00414 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
00415 QMD_TRACE_HEAD(head); \
00416 QMD_TRACE_ELEM(&(elm)->field); \
00417 } while (0)
00418
00419 #define TAILQ_LAST(head, headname) \
00420 (*(((struct headname *)((head)->tqh_last))->tqh_last))
00421
00422 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
00423
00424 #define TAILQ_PREV(elm, headname, field) \
00425 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
00426
00427 #define TAILQ_REMOVE(head, elm, field) do { \
00428 if ((TAILQ_NEXT((elm), field)) != NULL) \
00429 TAILQ_NEXT((elm), field)->field.tqe_prev = \
00430 (elm)->field.tqe_prev; \
00431 else { \
00432 (head)->tqh_last = (elm)->field.tqe_prev; \
00433 QMD_TRACE_HEAD(head); \
00434 } \
00435 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
00436 TRASHIT((elm)->field.tqe_next); \
00437 TRASHIT((elm)->field.tqe_prev); \
00438 QMD_TRACE_ELEM(&(elm)->field); \
00439 } while (0)
00440
00441
00442
00443
00444 #define CIRCLEQ_HEAD(name, type) \
00445 struct name { \
00446 struct type *cqh_first; \
00447 struct type *cqh_last; \
00448 }
00449
00450 #define CIRCLEQ_ENTRY(type) \
00451 struct { \
00452 struct type *cqe_next; \
00453 struct type *cqe_prev; \
00454 }
00455
00456
00457
00458
00459 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
00460
00461 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
00462
00463 #define CIRCLEQ_FOREACH(var, head, field) \
00464 for((var) = (head)->cqh_first; \
00465 (var) != (void *)(head); \
00466 (var) = (var)->field.cqe_next)
00467
00468 #define CIRCLEQ_INIT(head) do { \
00469 (head)->cqh_first = (void *)(head); \
00470 (head)->cqh_last = (void *)(head); \
00471 } while (0)
00472
00473 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
00474 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
00475 (elm)->field.cqe_prev = (listelm); \
00476 if ((listelm)->field.cqe_next == (void *)(head)) \
00477 (head)->cqh_last = (elm); \
00478 else \
00479 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
00480 (listelm)->field.cqe_next = (elm); \
00481 } while (0)
00482
00483 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
00484 (elm)->field.cqe_next = (listelm); \
00485 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
00486 if ((listelm)->field.cqe_prev == (void *)(head)) \
00487 (head)->cqh_first = (elm); \
00488 else \
00489 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
00490 (listelm)->field.cqe_prev = (elm); \
00491 } while (0)
00492
00493 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
00494 (elm)->field.cqe_next = (head)->cqh_first; \
00495 (elm)->field.cqe_prev = (void *)(head); \
00496 if ((head)->cqh_last == (void *)(head)) \
00497 (head)->cqh_last = (elm); \
00498 else \
00499 (head)->cqh_first->field.cqe_prev = (elm); \
00500 (head)->cqh_first = (elm); \
00501 } while (0)
00502
00503 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
00504 (elm)->field.cqe_next = (void *)(head); \
00505 (elm)->field.cqe_prev = (head)->cqh_last; \
00506 if ((head)->cqh_first == (void *)(head)) \
00507 (head)->cqh_first = (elm); \
00508 else \
00509 (head)->cqh_last->field.cqe_next = (elm); \
00510 (head)->cqh_last = (elm); \
00511 } while (0)
00512
00513 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
00514
00515 #define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
00516
00517 #define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
00518
00519 #define CIRCLEQ_REMOVE(head, elm, field) do { \
00520 if ((elm)->field.cqe_next == (void *)(head)) \
00521 (head)->cqh_last = (elm)->field.cqe_prev; \
00522 else \
00523 (elm)->field.cqe_next->field.cqe_prev = \
00524 (elm)->field.cqe_prev; \
00525 if ((elm)->field.cqe_prev == (void *)(head)) \
00526 (head)->cqh_first = (elm)->field.cqe_next; \
00527 else \
00528 (elm)->field.cqe_prev->field.cqe_next = \
00529 (elm)->field.cqe_next; \
00530 } while (0)
00531
00532 #endif