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