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