Lines Matching +full:runs +full:- +full:on
1 /*-
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
39 * This file defines four types of data structures: singly-linked lists,
40 * singly-linked tail queues, lists and tail queues.
42 * A singly-linked list is headed by a single forward pointer. The elements
47 * macro for this purpose for optimum efficiency. A singly-linked list may
48 * only be traversed in the forward direction. Singly-linked lists are ideal
52 * A singly-linked tail queue is headed by a pair of pointers, one to the
59 * A singly-linked tail queue may only be traversed in the forward direction.
60 * Singly-linked tail queues are ideal for applications with large datasets
77 * For details on the use of these macros, see the queue(3) manual page.
81 * - means the macro is not available
82 * s means the macro is available but is slow (runs in O(n) time)
94 * _PREV - + - +
95 * _LAST - - + +
96 * _LAST_FAST - - - +
101 * _FOREACH_REVERSE - - - +
102 * _FOREACH_REVERSE_FROM - - - +
103 * _FOREACH_REVERSE_SAFE - - - +
104 * _FOREACH_REVERSE_FROM_SAFE - - - +
106 * _INSERT_BEFORE - + - +
108 * _INSERT_TAIL - - + +
110 * _REMOVE_AFTER + - + -
111 * _REMOVE_HEAD + - + -
135 (head)->trace.prevline = (head)->trace.lastline; \
136 (head)->trace.prevfile = (head)->trace.lastfile; \
137 (head)->trace.lastline = __LINE__; \
138 (head)->trace.lastfile = __FILE__; \
142 (elem)->trace.prevline = (elem)->trace.lastline; \
143 (elem)->trace.prevfile = (elem)->trace.lastfile; \
144 (elem)->trace.lastline = __LINE__; \
145 (elem)->trace.lastfile = __FILE__; \
156 #define TRASHIT(x) do {(x) = (void *)-1;} while (0)
157 #define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1)
179 * Singly-linked List declarations.
205 * Singly-linked List functions.
230 #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
232 #define SLIST_FIRST(head) ((head)->slh_first)
273 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
276 QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
301 TRASHIT((elm)->field.sle_next); \
311 * Singly-linked Tail queue declarations.
339 * Singly-linked Tail queue functions.
343 *(head1)->stqh_last = (head2)->stqh_first; \
344 (head1)->stqh_last = (head2)->stqh_last; \
349 #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
351 #define STAILQ_FIRST(head) ((head)->stqh_first)
375 (head)->stqh_last = &STAILQ_FIRST((head)); \
380 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
386 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
392 *(head)->stqh_last = (elm); \
393 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
398 __containerof((head)->stqh_last, \
401 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
404 QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
420 (head)->stqh_last = &STAILQ_NEXT((elm), field); \
426 (head)->stqh_last = &STAILQ_FIRST((head)); \
431 (head)->stqh_last = &STAILQ_FIRST((head)); \
436 QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \
438 (head1)->stqh_last = (head2)->stqh_last; \
440 (head2)->stqh_last = swap_last; \
442 (head1)->stqh_last = &STAILQ_FIRST(head1); \
444 (head2)->stqh_last = &STAILQ_FIRST(head2); \
484 * If the list is non-empty, validates that the first element of the list
489 LIST_FIRST((head))->field.le_prev != \
491 panic("Bad list head %p first->prev != head", (head)); \
502 LIST_NEXT((elm), field)->field.le_prev != \
503 &((elm)->field.le_next)) \
504 panic("Bad link elm %p next->prev != elm", (elm)); \
513 if (*(elm)->field.le_prev != (elm)) \
514 panic("Bad link elm %p prev->next != elm", (elm)); \
526 LIST_FIRST(head2)->field.le_prev = \
534 LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
539 #define LIST_EMPTY(head) ((head)->lh_first == NULL)
541 #define LIST_FIRST(head) ((head)->lh_first)
570 LIST_NEXT((listelm), field)->field.le_prev = \
573 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
578 (elm)->field.le_prev = (listelm)->field.le_prev; \
580 *(listelm)->field.le_prev = (elm); \
581 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
587 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
589 (elm)->field.le_prev = &LIST_FIRST((head)); \
592 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
595 ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
596 __containerof((elm)->field.le_prev, \
600 QMD_SAVELINK(oldnext, (elm)->field.le_next); \
601 QMD_SAVELINK(oldprev, (elm)->field.le_prev); \
605 LIST_NEXT((elm), field)->field.le_prev = \
606 (elm)->field.le_prev; \
607 *(elm)->field.le_prev = LIST_NEXT((elm), field); \
617 swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
619 swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
663 * If the tailq is non-empty, validates that the first element of the tailq
668 TAILQ_FIRST((head))->field.tqe_prev != \
670 panic("Bad tailq head %p first->prev != head", (head)); \
679 if (*(head)->tqh_last != NULL) \
680 panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
691 TAILQ_NEXT((elm), field)->field.tqe_prev != \
692 &((elm)->field.tqe_next)) \
693 panic("Bad link elm %p next->prev != elm", (elm)); \
702 if (*(elm)->field.tqe_prev != (elm)) \
703 panic("Bad link elm %p prev->next != elm", (elm)); \
714 *(head1)->tqh_last = (head2)->tqh_first; \
715 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
716 (head1)->tqh_last = (head2)->tqh_last; \
723 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
725 #define TAILQ_FIRST(head) ((head)->tqh_first)
769 (head)->tqh_last = &TAILQ_FIRST((head)); \
776 TAILQ_NEXT((elm), field)->field.tqe_prev = \
779 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
783 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
784 QMD_TRACE_ELEM(&(elm)->field); \
785 QMD_TRACE_ELEM(&(listelm)->field); \
790 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
792 *(listelm)->field.tqe_prev = (elm); \
793 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
794 QMD_TRACE_ELEM(&(elm)->field); \
795 QMD_TRACE_ELEM(&(listelm)->field); \
801 TAILQ_FIRST((head))->field.tqe_prev = \
804 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
806 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
808 QMD_TRACE_ELEM(&(elm)->field); \
814 (elm)->field.tqe_prev = (head)->tqh_last; \
815 *(head)->tqh_last = (elm); \
816 (head)->tqh_last = &TAILQ_NEXT((elm), field); \
818 QMD_TRACE_ELEM(&(elm)->field); \
822 (*(((struct headname *)((head)->tqh_last))->tqh_last))
832 (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next))
834 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
837 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
840 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
841 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
845 TAILQ_NEXT((elm), field)->field.tqe_prev = \
846 (elm)->field.tqe_prev; \
848 (head)->tqh_last = (elm)->field.tqe_prev; \
851 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
854 QMD_TRACE_ELEM(&(elm)->field); \
858 QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \
859 QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \
860 (head1)->tqh_first = (head2)->tqh_first; \
861 (head1)->tqh_last = (head2)->tqh_last; \
862 (head2)->tqh_first = swap_first; \
863 (head2)->tqh_last = swap_last; \
864 if ((swap_first = (head1)->tqh_first) != NULL) \
865 swap_first->field.tqe_prev = &(head1)->tqh_first; \
867 (head1)->tqh_last = &(head1)->tqh_first; \
868 if ((swap_first = (head2)->tqh_first) != NULL) \
869 swap_first->field.tqe_prev = &(head2)->tqh_first; \
871 (head2)->tqh_last = &(head2)->tqh_first; \
894 element->qh_link = head->qh_link; in insque()
895 element->qh_rlink = head; in insque()
896 head->qh_link = element; in insque()
897 element->qh_link->qh_rlink = element; in insque()
905 element->qh_link->qh_rlink = element->qh_rlink; in remque()
906 element->qh_rlink->qh_link = element->qh_link; in remque()
907 element->qh_rlink = 0; in remque()