sys/sys/queue.h

44  * added to the list after an existing element or at the head of the list.
45  * Elements being removed from the head of the list should use the explicit
52  * head of the list and the other to the tail of the list. The elements are
55  * to the list after an existing element, at the head of the list, or at the
56  * end of the list. Elements being removed from the head of the tail queue
66  * or after an existing element or at the head of the list. A list
69  * A tail queue is headed by a pair of pointers, one to the head of the
73  * after an existing element, at the head of the list, or at the end of
124 /* Store the last 2 places the queue element or head was altered */
135 #define	QMD_TRACE_HEAD(head) do {					\
136 	(head)->trace.prevline = (head)->trace.lastline;		\
137 	(head)->trace.prevfile = (head)->trace.lastfile;		\
138 	(head)->trace.lastline = __LINE__;				\
139 	(head)->trace.lastfile = __FILE__;				\
151 #define	QMD_TRACE_HEAD(head)
188 #define	SLIST_HEAD_INITIALIZER(head)					\
227 #define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
229 #define	SLIST_FIRST(head)	((head)->slh_first)
231 #define	SLIST_FOREACH(var, head, field)					\
232 	for ((var) = SLIST_FIRST((head));				\
236 #define	SLIST_FOREACH_FROM(var, head, field)				\
237 	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
241 #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
242 	for ((var) = SLIST_FIRST((head));				\
246 #define	SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
247 	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
251 #define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
252 	for ((varp) = &SLIST_FIRST((head));				\
256 #define	SLIST_INIT(head) do {						\
257 	SLIST_FIRST((head)) = NULL;					\
265 #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
266 	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
267 	SLIST_FIRST((head)) = (elm);					\
272 #define	SLIST_REMOVE(head, elm, type, field) do {			\
273 	if (SLIST_FIRST((head)) == (elm)) {				\
274 		SLIST_REMOVE_HEAD((head), field);			\
277 		QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head);		\
291 #define	SLIST_REMOVE_HEAD(head, field) do {				\
292 	QMD_SAVELINK(oldnext, SLIST_FIRST(head)->field.sle_next);	\
293 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
309 #define	SLIST_END(head)		NULL
326 #define	STAILQ_HEAD_INITIALIZER(head)					\
327 	{ NULL, &(head).stqh_first }
350 #define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
352 #define	STAILQ_FIRST(head)	((head)->stqh_first)
354 #define	STAILQ_FOREACH(var, head, field)				\
355 	for((var) = STAILQ_FIRST((head));				\
359 #define	STAILQ_FOREACH_FROM(var, head, field)				\
360 	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
364 #define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
365 	for ((var) = STAILQ_FIRST((head));				\
369 #define	STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
370 	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
374 #define	STAILQ_INIT(head) do {						\
375 	STAILQ_FIRST((head)) = NULL;					\
376 	(head)->stqh_last = &STAILQ_FIRST((head));			\
379 #define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
381 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
385 #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
386 	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
387 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
388 	STAILQ_FIRST((head)) = (elm);					\
391 #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
393 	*(head)->stqh_last = (elm);					\
394 	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
397 #define	STAILQ_LAST(head, type, field)					\
398 	(STAILQ_EMPTY((head)) ? NULL :					\
399 	    __containerof((head)->stqh_last,				\
404 #define	STAILQ_REMOVE(head, elm, type, field) do {			\
406 	if (STAILQ_FIRST((head)) == (elm)) {				\
407 		STAILQ_REMOVE_HEAD((head), field);			\
410 		QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head);	\
413 		STAILQ_REMOVE_AFTER(head, curelm, field);		\
418 #define STAILQ_REMOVE_AFTER(head, elm, field) do {			\
421 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
424 #define	STAILQ_REMOVE_HEAD(head, field) do {				\
425 	if ((STAILQ_FIRST((head)) =					\
426 	     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
427 		(head)->stqh_last = &STAILQ_FIRST((head));		\
443 #define	STAILQ_END(head)	NULL
459 #define	LIST_HEAD_INITIALIZER(head)					\
480  * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME)
483  * points back at 'head.'
485 #define	QMD_LIST_CHECK_HEAD(head, field) do {				\
486 	if (LIST_FIRST((head)) != NULL &&				\
487 	    LIST_FIRST((head))->field.le_prev !=			\
488 	     &LIST_FIRST((head)))					\
489 		panic("Bad list head %p first->prev != head", (head));	\
508  * Validates that the previous element (or head of the list) points to 'elm.'
515 #define	QMD_LIST_CHECK_HEAD(head, field)
537 #define	LIST_EMPTY(head)	((head)->lh_first == NULL)
539 #define	LIST_FIRST(head)	((head)->lh_first)
541 #define	LIST_FOREACH(var, head, field)					\
542 	for ((var) = LIST_FIRST((head));				\
546 #define	LIST_FOREACH_FROM(var, head, field)				\
547 	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
551 #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
552 	for ((var) = LIST_FIRST((head));				\
556 #define	LIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
557 	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
561 #define	LIST_INIT(head) do {						\
562 	LIST_FIRST((head)) = NULL;					\
582 #define	LIST_INSERT_HEAD(head, elm, field) do {				\
583 	QMD_LIST_CHECK_HEAD((head), field);				\
584 	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
585 		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
586 	LIST_FIRST((head)) = (elm);					\
587 	(elm)->field.le_prev = &LIST_FIRST((head));			\
592 #define	LIST_PREV(elm, head, type, field)				\
593 	((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL :		\
597 #define LIST_REMOVE_HEAD(head, field)					\
598 	LIST_REMOVE(LIST_FIRST(head), field)
638 #define	LIST_END(head)	NULL
657 #define	TAILQ_HEAD_INITIALIZER(head)					\
658 	{ NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
679  * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
682  * points back at 'head.'
684 #define	QMD_TAILQ_CHECK_HEAD(head, field) do {				\
685 	if (!TAILQ_EMPTY(head) &&					\
686 	    TAILQ_FIRST((head))->field.tqe_prev !=			\
687 	     &TAILQ_FIRST((head)))					\
688 		panic("Bad tailq head %p first->prev != head", (head));	\
692  * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
696 #define	QMD_TAILQ_CHECK_TAIL(head, field) do {				\
697 	if (*(head)->tqh_last != NULL)					\
698 		panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head));	\
717  * Validates that the previous element (or head of the tailq) points to 'elm.'
724 #define	QMD_TAILQ_CHECK_HEAD(head, field)
725 #define	QMD_TAILQ_CHECK_TAIL(head, headname)
741 #define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)
743 #define	TAILQ_FIRST(head)	((head)->tqh_first)
745 #define	TAILQ_FOREACH(var, head, field)					\
746 	for ((var) = TAILQ_FIRST((head));				\
750 #define	TAILQ_FOREACH_FROM(var, head, field)				\
751 	for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));		\
755 #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
756 	for ((var) = TAILQ_FIRST((head));				\
760 #define	TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)			\
761 	for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));		\
765 #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
766 	for ((var) = TAILQ_LAST((head), headname);			\
770 #define	TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)		\
771 	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));	\
775 #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
776 	for ((var) = TAILQ_LAST((head), headname);			\
780 #define	TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar)\
781 	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));	\
785 #define	TAILQ_INIT(head) do {						\
786 	TAILQ_FIRST((head)) = NULL;					\
787 	(head)->tqh_last = &TAILQ_FIRST((head));			\
788 	QMD_TRACE_HEAD(head);						\
791 #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
797 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
798 		QMD_TRACE_HEAD(head);					\
816 #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
817 	QMD_TAILQ_CHECK_HEAD(head, field);				\
818 	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
819 		TAILQ_FIRST((head))->field.tqe_prev =			\
822 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
823 	TAILQ_FIRST((head)) = (elm);					\
824 	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
825 	QMD_TRACE_HEAD(head);						\
829 #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
830 	QMD_TAILQ_CHECK_TAIL(head, field);				\
832 	(elm)->field.tqe_prev = (head)->tqh_last;			\
833 	*(head)->tqh_last = (elm);					\
834 	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
835 	QMD_TRACE_HEAD(head);						\
839 #define	TAILQ_LAST(head, headname)					\
840 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
844  * then the access to the head. The standard LAST function above
849 #define	TAILQ_LAST_FAST(head, type, field)				\
850     (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next))
857 #define	TAILQ_PREV_FAST(elm, head, type, field)				\
858     ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL :		\
861 #define TAILQ_REMOVE_HEAD(head, field)					\
862 	TAILQ_REMOVE(head, TAILQ_FIRST(head), field)
864 #define	TAILQ_REMOVE(head, elm, field) do {				\
873 		(head)->tqh_last = (elm)->field.tqe_prev;		\
874 		QMD_TRACE_HEAD(head);					\
882 #define TAILQ_REPLACE(head, elm, elm2, field) do {			\
888 	if (TAILQ_NEXT((elm2), field) != TAILQ_END(head))		\
892                 (head)->tqh_last = &(elm2)->field.tqe_next;		\
917 #define	TAILQ_END(head)		NULL