Mercurial > code

comparison queue.h @ 42:30499f543188

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Remove FreeBSD specific macros in queue.h
author David Demelier <markand@malikania.fr>
date Sun, 02 Oct 2011 11:26:30 +0200
parents 4212fb4b4e41
children
comparison
equal deleted inserted replaced
41:5252fa9b5cb1 42:30499f543188
177 #undef TAILQ_NEXT 177 #undef TAILQ_NEXT
178 #undef TAILQ_PREV 178 #undef TAILQ_PREV
179 #undef TAILQ_REMOVE 179 #undef TAILQ_REMOVE
180 #undef TAILQ_SWAP 180 #undef TAILQ_SWAP
181 181
182 #ifdef QUEUE_MACRO_DEBUG
183 /* Store the last 2 places the queue element or head was altered */
184 struct qm_trace {
185 char * lastfile;
186 int lastline;
187 char * prevfile;
188 int prevline;
189 };
190
191 #define TRACEBUF struct qm_trace trace;
192 #define TRASHIT(x) do {(x) = (void *)-1;} while (0)
193 #define QMD_SAVELINK(name, link) void **name = (void *)&(link)
194
195 #define QMD_TRACE_HEAD(head) do { \
196 (head)->trace.prevline = (head)->trace.lastline; \
197 (head)->trace.prevfile = (head)->trace.lastfile; \
198 (head)->trace.lastline = __LINE__; \
199 (head)->trace.lastfile = __FILE__; \
200 } while (0)
201
202 #define QMD_TRACE_ELEM(elem) do { \
203 (elem)->trace.prevline = (elem)->trace.lastline; \
204 (elem)->trace.prevfile = (elem)->trace.lastfile; \
205 (elem)->trace.lastline = __LINE__; \
206 (elem)->trace.lastfile = __FILE__; \
207 } while (0)
208
209 #else
210 #define QMD_TRACE_ELEM(elem)
211 #define QMD_TRACE_HEAD(head)
212 #define QMD_SAVELINK(name, link)
213 #define TRACEBUF
214 #define TRASHIT(x)
215 #endif /* QUEUE_MACRO_DEBUG */
216
217 /* 182 /*
218 * Singly-linked List declarations. 183 * Singly-linked List declarations.
219 */ 184 */
220 #define SLIST_HEAD(name, type) \ 185 #define SLIST_HEAD(name, type) \
221 struct name { \ 186 struct name { \
267 } while (0) 232 } while (0)
268 233
269 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 234 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
270 235
271 #define SLIST_REMOVE(head, elm, type, field) do { \ 236 #define SLIST_REMOVE(head, elm, type, field) do { \
272 QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
273 if (SLIST_FIRST((head)) == (elm)) { \ 237 if (SLIST_FIRST((head)) == (elm)) { \
274 SLIST_REMOVE_HEAD((head), field); \ 238 SLIST_REMOVE_HEAD((head), field); \
275 } \ 239 } \
276 else { \ 240 else { \
277 struct type *curelm = SLIST_FIRST((head)); \ 241 struct type *curelm = SLIST_FIRST((head)); \
278 while (SLIST_NEXT(curelm, field) != (elm)) \ 242 while (SLIST_NEXT(curelm, field) != (elm)) \
279 curelm = SLIST_NEXT(curelm, field); \ 243 curelm = SLIST_NEXT(curelm, field); \
280 SLIST_REMOVE_AFTER(curelm, field); \ 244 SLIST_REMOVE_AFTER(curelm, field); \
281 } \ 245 } \
282 TRASHIT(*oldnext); \
283 } while (0) 246 } while (0)
284 247
285 #define SLIST_REMOVE_AFTER(elm, field) do { \ 248 #define SLIST_REMOVE_AFTER(elm, field) do { \
286 SLIST_NEXT(elm, field) = \ 249 SLIST_NEXT(elm, field) = \
287 SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 250 SLIST_NEXT(SLIST_NEXT(elm, field), field); \
370 ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 333 ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
371 334
372 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 335 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
373 336
374 #define STAILQ_REMOVE(head, elm, type, field) do { \ 337 #define STAILQ_REMOVE(head, elm, type, field) do { \
375 QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
376 if (STAILQ_FIRST((head)) == (elm)) { \ 338 if (STAILQ_FIRST((head)) == (elm)) { \
377 STAILQ_REMOVE_HEAD((head), field); \ 339 STAILQ_REMOVE_HEAD((head), field); \
378 } \ 340 } \
379 else { \ 341 else { \
380 struct type *curelm = STAILQ_FIRST((head)); \ 342 struct type *curelm = STAILQ_FIRST((head)); \
381 while (STAILQ_NEXT(curelm, field) != (elm)) \ 343 while (STAILQ_NEXT(curelm, field) != (elm)) \
382 curelm = STAILQ_NEXT(curelm, field); \ 344 curelm = STAILQ_NEXT(curelm, field); \
383 STAILQ_REMOVE_AFTER(head, curelm, field); \ 345 STAILQ_REMOVE_AFTER(head, curelm, field); \
384 } \ 346 } \
385 TRASHIT(*oldnext); \
386 } while (0) 347 } while (0)
387 348
388 #define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 349 #define STAILQ_REMOVE_AFTER(head, elm, field) do { \
389 if ((STAILQ_NEXT(elm, field) = \ 350 if ((STAILQ_NEXT(elm, field) = \
390 STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 351 STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
408 (head1)->stqh_last = &STAILQ_FIRST(head1); \ 369 (head1)->stqh_last = &STAILQ_FIRST(head1); \
409 if (STAILQ_EMPTY(head2)) \ 370 if (STAILQ_EMPTY(head2)) \
410 (head2)->stqh_last = &STAILQ_FIRST(head2); \ 371 (head2)->stqh_last = &STAILQ_FIRST(head2); \
411 } while (0) 372 } while (0)
412 373
413
414 /* 374 /*
415 * List declarations. 375 * List declarations.
416 */ 376 */
417 #define LIST_HEAD(name, type) \ 377 #define LIST_HEAD(name, type) \
418 struct name { \ 378 struct name { \
430 390
431 /* 391 /*
432 * List functions. 392 * List functions.
433 */ 393 */
434 394
435 #if (defined(_KERNEL) && defined(INVARIANTS))
436 #define QMD_LIST_CHECK_HEAD(head, field) do { \
437 if (LIST_FIRST((head)) != NULL && \
438 LIST_FIRST((head))->field.le_prev != \
439 &LIST_FIRST((head))) \
440 panic("Bad list head %p first->prev != head", (head)); \
441 } while (0)
442
443 #define QMD_LIST_CHECK_NEXT(elm, field) do { \
444 if (LIST_NEXT((elm), field) != NULL && \
445 LIST_NEXT((elm), field)->field.le_prev != \
446 &((elm)->field.le_next)) \
447 panic("Bad link elm %p next->prev != elm", (elm)); \
448 } while (0)
449
450 #define QMD_LIST_CHECK_PREV(elm, field) do { \
451 if (*(elm)->field.le_prev != (elm)) \
452 panic("Bad link elm %p prev->next != elm", (elm)); \
453 } while (0)
454 #else
455 #define QMD_LIST_CHECK_HEAD(head, field)
456 #define QMD_LIST_CHECK_NEXT(elm, field)
457 #define QMD_LIST_CHECK_PREV(elm, field)
458 #endif /* (_KERNEL && INVARIANTS) */
459
460 #define LIST_EMPTY(head) ((head)->lh_first == NULL) 395 #define LIST_EMPTY(head) ((head)->lh_first == NULL)
461 396
462 #define LIST_FIRST(head) ((head)->lh_first) 397 #define LIST_FIRST(head) ((head)->lh_first)
463 398
464 #define LIST_FOREACH(var, head, field) \ 399 #define LIST_FOREACH(var, head, field) \
474 #define LIST_INIT(head) do { \ 409 #define LIST_INIT(head) do { \
475 LIST_FIRST((head)) = NULL; \ 410 LIST_FIRST((head)) = NULL; \
476 } while (0) 411 } while (0)
477 412
478 #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 413 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
479 QMD_LIST_CHECK_NEXT(listelm, field); \
480 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 414 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
481 LIST_NEXT((listelm), field)->field.le_prev = \ 415 LIST_NEXT((listelm), field)->field.le_prev = \
482 &LIST_NEXT((elm), field); \ 416 &LIST_NEXT((elm), field); \
483 LIST_NEXT((listelm), field) = (elm); \ 417 LIST_NEXT((listelm), field) = (elm); \
484 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 418 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
485 } while (0) 419 } while (0)
486 420
487 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 421 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
488 QMD_LIST_CHECK_PREV(listelm, field); \
489 (elm)->field.le_prev = (listelm)->field.le_prev; \ 422 (elm)->field.le_prev = (listelm)->field.le_prev; \
490 LIST_NEXT((elm), field) = (listelm); \ 423 LIST_NEXT((elm), field) = (listelm); \
491 *(listelm)->field.le_prev = (elm); \ 424 *(listelm)->field.le_prev = (elm); \
492 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 425 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
493 } while (0) 426 } while (0)
494 427
495 #define LIST_INSERT_HEAD(head, elm, field) do { \ 428 #define LIST_INSERT_HEAD(head, elm, field) do { \
496 QMD_LIST_CHECK_HEAD((head), field); \
497 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 429 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
498 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 430 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
499 LIST_FIRST((head)) = (elm); \ 431 LIST_FIRST((head)) = (elm); \
500 (elm)->field.le_prev = &LIST_FIRST((head)); \ 432 (elm)->field.le_prev = &LIST_FIRST((head)); \
501 } while (0) 433 } while (0)
502 434
503 #define LIST_NEXT(elm, field) ((elm)->field.le_next) 435 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
504 436
505 #define LIST_REMOVE(elm, field) do { \ 437 #define LIST_REMOVE(elm, field) do { \
506 QMD_SAVELINK(oldnext, (elm)->field.le_next); \
507 QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
508 QMD_LIST_CHECK_NEXT(elm, field); \
509 QMD_LIST_CHECK_PREV(elm, field); \
510 if (LIST_NEXT((elm), field) != NULL) \ 438 if (LIST_NEXT((elm), field) != NULL) \
511 LIST_NEXT((elm), field)->field.le_prev = \ 439 LIST_NEXT((elm), field)->field.le_prev = \
512 (elm)->field.le_prev; \ 440 (elm)->field.le_prev; \
513 *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 441 *(elm)->field.le_prev = LIST_NEXT((elm), field); \
514 TRASHIT(*oldnext); \
515 TRASHIT(*oldprev); \
516 } while (0) 442 } while (0)
517 443
518 #define LIST_SWAP(head1, head2, type, field) do { \ 444 #define LIST_SWAP(head1, head2, type, field) do { \
519 struct type *swap_tmp = LIST_FIRST((head1)); \ 445 struct type *swap_tmp = LIST_FIRST((head1)); \
520 LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 446 LIST_FIRST((head1)) = LIST_FIRST((head2)); \
530 */ 456 */
531 #define TAILQ_HEAD(name, type) \ 457 #define TAILQ_HEAD(name, type) \
532 struct name { \ 458 struct name { \
533 struct type *tqh_first; /* first element */ \ 459 struct type *tqh_first; /* first element */ \
534 struct type **tqh_last; /* addr of last next element */ \ 460 struct type **tqh_last; /* addr of last next element */ \
535 TRACEBUF \
536 } 461 }
537 462
538 #define TAILQ_HEAD_INITIALIZER(head) \ 463 #define TAILQ_HEAD_INITIALIZER(head) \
539 { NULL, &(head).tqh_first } 464 { NULL, &(head).tqh_first }
540 465
541 #define TAILQ_ENTRY(type) \ 466 #define TAILQ_ENTRY(type) \
542 struct { \ 467 struct { \
543 struct type *tqe_next; /* next element */ \ 468 struct type *tqe_next; /* next element */ \
544 struct type **tqe_prev; /* address of previous next element */ \ 469 struct type **tqe_prev; /* address of previous next element */ \
545 TRACEBUF \
546 } 470 }
547 471
548 /* 472 /*
549 * Tail queue functions. 473 * Tail queue functions.
550 */ 474 */
551 #if (defined(_KERNEL) && defined(INVARIANTS))
552 #define QMD_TAILQ_CHECK_HEAD(head, field) do { \
553 if (!TAILQ_EMPTY(head) && \
554 TAILQ_FIRST((head))->field.tqe_prev != \
555 &TAILQ_FIRST((head))) \
556 panic("Bad tailq head %p first->prev != head", (head)); \
557 } while (0)
558
559 #define QMD_TAILQ_CHECK_TAIL(head, field) do { \
560 if (*(head)->tqh_last != NULL) \
561 panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
562 } while (0)
563
564 #define QMD_TAILQ_CHECK_NEXT(elm, field) do { \
565 if (TAILQ_NEXT((elm), field) != NULL && \
566 TAILQ_NEXT((elm), field)->field.tqe_prev != \
567 &((elm)->field.tqe_next)) \
568 panic("Bad link elm %p next->prev != elm", (elm)); \
569 } while (0)
570
571 #define QMD_TAILQ_CHECK_PREV(elm, field) do { \
572 if (*(elm)->field.tqe_prev != (elm)) \
573 panic("Bad link elm %p prev->next != elm", (elm)); \
574 } while (0)
575 #else
576 #define QMD_TAILQ_CHECK_HEAD(head, field)
577 #define QMD_TAILQ_CHECK_TAIL(head, headname)
578 #define QMD_TAILQ_CHECK_NEXT(elm, field)
579 #define QMD_TAILQ_CHECK_PREV(elm, field)
580 #endif /* (_KERNEL && INVARIANTS) */
581 475
582 #define TAILQ_CONCAT(head1, head2, field) do { \ 476 #define TAILQ_CONCAT(head1, head2, field) do { \
583 if (!TAILQ_EMPTY(head2)) { \ 477 if (!TAILQ_EMPTY(head2)) { \
584 *(head1)->tqh_last = (head2)->tqh_first; \ 478 *(head1)->tqh_last = (head2)->tqh_first; \
585 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 479 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
586 (head1)->tqh_last = (head2)->tqh_last; \ 480 (head1)->tqh_last = (head2)->tqh_last; \
587 TAILQ_INIT((head2)); \ 481 TAILQ_INIT((head2)); \
588 QMD_TRACE_HEAD(head1); \
589 QMD_TRACE_HEAD(head2); \
590 } \ 482 } \
591 } while (0) 483 } while (0)
592 484
593 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 485 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
594 486
615 (var) = (tvar)) 507 (var) = (tvar))
616 508
617 #define TAILQ_INIT(head) do { \ 509 #define TAILQ_INIT(head) do { \
618 TAILQ_FIRST((head)) = NULL; \ 510 TAILQ_FIRST((head)) = NULL; \
619 (head)->tqh_last = &TAILQ_FIRST((head)); \ 511 (head)->tqh_last = &TAILQ_FIRST((head)); \
620 QMD_TRACE_HEAD(head); \
621 } while (0) 512 } while (0)
622 513
623 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 514 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
624 QMD_TAILQ_CHECK_NEXT(listelm, field); \
625 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 515 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
626 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 516 TAILQ_NEXT((elm), field)->field.tqe_prev = \
627 &TAILQ_NEXT((elm), field); \ 517 &TAILQ_NEXT((elm), field); \
628 else { \ 518 else { \
629 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 519 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
630 QMD_TRACE_HEAD(head); \
631 } \ 520 } \
632 TAILQ_NEXT((listelm), field) = (elm); \ 521 TAILQ_NEXT((listelm), field) = (elm); \
633 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 522 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
634 QMD_TRACE_ELEM(&(elm)->field); \
635 QMD_TRACE_ELEM(&listelm->field); \
636 } while (0) 523 } while (0)
637 524
638 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 525 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
639 QMD_TAILQ_CHECK_PREV(listelm, field); \
640 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 526 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
641 TAILQ_NEXT((elm), field) = (listelm); \ 527 TAILQ_NEXT((elm), field) = (listelm); \
642 *(listelm)->field.tqe_prev = (elm); \ 528 *(listelm)->field.tqe_prev = (elm); \
643 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 529 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
644 QMD_TRACE_ELEM(&(elm)->field); \
645 QMD_TRACE_ELEM(&listelm->field); \
646 } while (0) 530 } while (0)
647 531
648 #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 532 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
649 QMD_TAILQ_CHECK_HEAD(head, field); \
650 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 533 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
651 TAILQ_FIRST((head))->field.tqe_prev = \ 534 TAILQ_FIRST((head))->field.tqe_prev = \
652 &TAILQ_NEXT((elm), field); \ 535 &TAILQ_NEXT((elm), field); \
653 else \ 536 else \
654 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 537 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
655 TAILQ_FIRST((head)) = (elm); \ 538 TAILQ_FIRST((head)) = (elm); \
656 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 539 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
657 QMD_TRACE_HEAD(head); \
658 QMD_TRACE_ELEM(&(elm)->field); \
659 } while (0) 540 } while (0)
660 541
661 #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 542 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
662 QMD_TAILQ_CHECK_TAIL(head, field); \
663 TAILQ_NEXT((elm), field) = NULL; \ 543 TAILQ_NEXT((elm), field) = NULL; \
664 (elm)->field.tqe_prev = (head)->tqh_last; \ 544 (elm)->field.tqe_prev = (head)->tqh_last; \
665 *(head)->tqh_last = (elm); \ 545 *(head)->tqh_last = (elm); \
666 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 546 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
667 QMD_TRACE_HEAD(head); \
668 QMD_TRACE_ELEM(&(elm)->field); \
669 } while (0) 547 } while (0)
670 548
671 #define TAILQ_LAST(head, headname) \ 549 #define TAILQ_LAST(head, headname) \
672 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 550 (*(((struct headname *)((head)->tqh_last))->tqh_last))
673 551
675 553
676 #define TAILQ_PREV(elm, headname, field) \ 554 #define TAILQ_PREV(elm, headname, field) \
677 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 555 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
678 556
679 #define TAILQ_REMOVE(head, elm, field) do { \ 557 #define TAILQ_REMOVE(head, elm, field) do { \
680 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
681 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
682 QMD_TAILQ_CHECK_NEXT(elm, field); \
683 QMD_TAILQ_CHECK_PREV(elm, field); \
684 if ((TAILQ_NEXT((elm), field)) != NULL) \ 558 if ((TAILQ_NEXT((elm), field)) != NULL) \
685 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 559 TAILQ_NEXT((elm), field)->field.tqe_prev = \
686 (elm)->field.tqe_prev; \ 560 (elm)->field.tqe_prev; \
687 else { \ 561 else { \
688 (head)->tqh_last = (elm)->field.tqe_prev; \ 562 (head)->tqh_last = (elm)->field.tqe_prev; \
689 QMD_TRACE_HEAD(head); \
690 } \ 563 } \
691 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 564 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
692 TRASHIT(*oldnext); \
693 TRASHIT(*oldprev); \
694 QMD_TRACE_ELEM(&(elm)->field); \
695 } while (0) 565 } while (0)
696 566
697 #define TAILQ_SWAP(head1, head2, type, field) do { \ 567 #define TAILQ_SWAP(head1, head2, type, field) do { \
698 struct type *swap_first = (head1)->tqh_first; \ 568 struct type *swap_first = (head1)->tqh_first; \
699 struct type **swap_last = (head1)->tqh_last; \ 569 struct type **swap_last = (head1)->tqh_last; \