199767f8919635c4928607450d9e0abb932109ceToomas Soome * Copyright (c) 1991, 1993
199767f8919635c4928607450d9e0abb932109ceToomas Soome * The Regents of the University of California. All rights reserved.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Redistribution and use in source and binary forms, with or without
199767f8919635c4928607450d9e0abb932109ceToomas Soome * modification, are permitted provided that the following conditions
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 1. Redistributions of source code must retain the above copyright
199767f8919635c4928607450d9e0abb932109ceToomas Soome * notice, this list of conditions and the following disclaimer.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 2. Redistributions in binary form must reproduce the above copyright
199767f8919635c4928607450d9e0abb932109ceToomas Soome * notice, this list of conditions and the following disclaimer in the
199767f8919635c4928607450d9e0abb932109ceToomas Soome * documentation and/or other materials provided with the distribution.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * 4. Neither the name of the University nor the names of its contributors
199767f8919635c4928607450d9e0abb932109ceToomas Soome * may be used to endorse or promote products derived from this software
199767f8919635c4928607450d9e0abb932109ceToomas Soome * without specific prior written permission.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
199767f8919635c4928607450d9e0abb932109ceToomas Soome * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
199767f8919635c4928607450d9e0abb932109ceToomas Soome * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
199767f8919635c4928607450d9e0abb932109ceToomas Soome * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
199767f8919635c4928607450d9e0abb932109ceToomas Soome * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
199767f8919635c4928607450d9e0abb932109ceToomas Soome * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
199767f8919635c4928607450d9e0abb932109ceToomas Soome * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
199767f8919635c4928607450d9e0abb932109ceToomas Soome * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
199767f8919635c4928607450d9e0abb932109ceToomas Soome * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
199767f8919635c4928607450d9e0abb932109ceToomas Soome * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
199767f8919635c4928607450d9e0abb932109ceToomas Soome * SUCH DAMAGE.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * @(#)queue.h 8.5 (Berkeley) 8/20/94
199767f8919635c4928607450d9e0abb932109ceToomas Soome * This file defines four types of data structures: singly-linked lists,
199767f8919635c4928607450d9e0abb932109ceToomas Soome * singly-linked tail queues, lists and tail queues.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * A singly-linked list is headed by a single forward pointer. The elements
199767f8919635c4928607450d9e0abb932109ceToomas Soome * are singly linked for minimum space and pointer manipulation overhead at
199767f8919635c4928607450d9e0abb932109ceToomas Soome * the expense of O(n) removal for arbitrary elements. New elements can be
199767f8919635c4928607450d9e0abb932109ceToomas Soome * added to the list after an existing element or at the head of the list.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Elements being removed from the head of the list should use the explicit
199767f8919635c4928607450d9e0abb932109ceToomas Soome * macro for this purpose for optimum efficiency. A singly-linked list may
199767f8919635c4928607450d9e0abb932109ceToomas Soome * only be traversed in the forward direction. Singly-linked lists are ideal
199767f8919635c4928607450d9e0abb932109ceToomas Soome * for applications with large datasets and few or no removals or for
199767f8919635c4928607450d9e0abb932109ceToomas Soome * implementing a LIFO queue.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * A singly-linked tail queue is headed by a pair of pointers, one to the
199767f8919635c4928607450d9e0abb932109ceToomas Soome * head of the list and the other to the tail of the list. The elements are
199767f8919635c4928607450d9e0abb932109ceToomas Soome * singly linked for minimum space and pointer manipulation overhead at the
199767f8919635c4928607450d9e0abb932109ceToomas Soome * expense of O(n) removal for arbitrary elements. New elements can be added
199767f8919635c4928607450d9e0abb932109ceToomas Soome * to the list after an existing element, at the head of the list, or at the
199767f8919635c4928607450d9e0abb932109ceToomas Soome * end of the list. Elements being removed from the head of the tail queue
199767f8919635c4928607450d9e0abb932109ceToomas Soome * should use the explicit macro for this purpose for optimum efficiency.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * A singly-linked tail queue may only be traversed in the forward direction.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Singly-linked tail queues are ideal for applications with large datasets
199767f8919635c4928607450d9e0abb932109ceToomas Soome * and few or no removals or for implementing a FIFO queue.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * A list is headed by a single forward pointer (or an array of forward
199767f8919635c4928607450d9e0abb932109ceToomas Soome * pointers for a hash table header). The elements are doubly linked
199767f8919635c4928607450d9e0abb932109ceToomas Soome * so that an arbitrary element can be removed without a need to
199767f8919635c4928607450d9e0abb932109ceToomas Soome * traverse the list. New elements can be added to the list before
199767f8919635c4928607450d9e0abb932109ceToomas Soome * or after an existing element or at the head of the list. A list
199767f8919635c4928607450d9e0abb932109ceToomas Soome * may be traversed in either direction.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * A tail queue is headed by a pair of pointers, one to the head of the
199767f8919635c4928607450d9e0abb932109ceToomas Soome * list and the other to the tail of the list. The elements are doubly
199767f8919635c4928607450d9e0abb932109ceToomas Soome * linked so that an arbitrary element can be removed without a need to
199767f8919635c4928607450d9e0abb932109ceToomas Soome * traverse the list. New elements can be added to the list before or
199767f8919635c4928607450d9e0abb932109ceToomas Soome * after an existing element, at the head of the list, or at the end of
199767f8919635c4928607450d9e0abb932109ceToomas Soome * the list. A tail queue may be traversed in either direction.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * For details on the use of these macros, see the queue(3) manual page.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * SLIST LIST STAILQ TAILQ
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _HEAD + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _CLASS_HEAD + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _HEAD_INITIALIZER + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _ENTRY + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _CLASS_ENTRY + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _INIT + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _EMPTY + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FIRST + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _NEXT + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _PREV - + - +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _LAST - - + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FOREACH + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FOREACH_FROM + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FOREACH_SAFE + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FOREACH_FROM_SAFE + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FOREACH_REVERSE - - - +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FOREACH_REVERSE_FROM - - - +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FOREACH_REVERSE_SAFE - - - +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _FOREACH_REVERSE_FROM_SAFE - - - +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _INSERT_HEAD + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _INSERT_BEFORE - + - +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _INSERT_AFTER + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _INSERT_TAIL - - + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _CONCAT - - + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _REMOVE_AFTER + - + -
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _REMOVE_HEAD + - + -
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _REMOVE + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome * _SWAP + + + +
199767f8919635c4928607450d9e0abb932109ceToomas Soome/* Store the last 2 places the queue element or head was altered */
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } ,
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TRASHIT(x) do {(x) = (void *)-1;} while (0)
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define QMD_SAVELINK(name, link) void **name = (void *)&(link)
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->trace.prevline = (head)->trace.lastline; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->trace.prevfile = (head)->trace.lastfile; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (elem)->trace.prevline = (elem)->trace.lastline; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (elem)->trace.prevfile = (elem)->trace.lastfile; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#endif /* QUEUE_MACRO_DEBUG */
199767f8919635c4928607450d9e0abb932109ceToomas Soome * In C++ there can be structure lists and class lists:
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Singly-linked List declarations.
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Singly-linked List functions.
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = SLIST_NEXT((var), field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define SLIST_INSERT_HEAD(head, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define SLIST_REMOVE(head, elm, type, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QMD_SAVELINK(oldnext, (elm)->field.sle_next); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Singly-linked Tail queue declarations.
199767f8919635c4928607450d9e0abb932109ceToomas Soome struct type **stqh_last;/* addr of last next element */ \
199767f8919635c4928607450d9e0abb932109ceToomas Soome class type **stqh_last; /* addr of last next element */ \
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Singly-linked Tail queue functions.
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->stqh_last = &STAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_INSERT_HEAD(head, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->stqh_last = &STAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_INSERT_TAIL(head, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->stqh_last = &STAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_REMOVE(head, elm, type, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define STAILQ_REMOVE_AFTER(head, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->stqh_last = &STAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome * List declarations.
199767f8919635c4928607450d9e0abb932109ceToomas Soome struct type **le_prev; /* address of previous next element */ \
199767f8919635c4928607450d9e0abb932109ceToomas Soome class type **le_prev; /* address of previous next element */ \
199767f8919635c4928607450d9e0abb932109ceToomas Soome * List functions.
199767f8919635c4928607450d9e0abb932109ceToomas Soome panic("Bad list head %p first->prev != head", (head)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome panic("Bad link elm %p next->prev != elm", (elm)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome panic("Bad link elm %p prev->next != elm", (elm)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#endif /* (_KERNEL && INVARIANTS) */
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define LIST_EMPTY(head) ((head)->lh_first == NULL)
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define LIST_FOREACH_SAFE(var, head, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = LIST_NEXT((var), field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : LIST_FIRST((head))); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = LIST_NEXT((var), field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define LIST_INSERT_AFTER(listelm, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
199767f8919635c4928607450d9e0abb932109ceToomas Soome (elm)->field.le_prev = &LIST_NEXT((listelm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (elm)->field.le_prev = (listelm)->field.le_prev; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define LIST_INSERT_HEAD(head, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define LIST_NEXT(elm, field) ((elm)->field.le_next)
199767f8919635c4928607450d9e0abb932109ceToomas Soome ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
199767f8919635c4928607450d9e0abb932109ceToomas Soome *(elm)->field.le_prev = LIST_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define LIST_SWAP(head1, head2, type, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((swap_tmp = LIST_FIRST((head1))) != NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome swap_tmp->field.le_prev = &LIST_FIRST((head1)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((swap_tmp = LIST_FIRST((head2))) != NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome swap_tmp->field.le_prev = &LIST_FIRST((head2)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Tail queue declarations.
199767f8919635c4928607450d9e0abb932109ceToomas Soome struct type **tqh_last; /* addr of last next element */ \
199767f8919635c4928607450d9e0abb932109ceToomas Soome class type **tqh_last; /* addr of last next element */ \
199767f8919635c4928607450d9e0abb932109ceToomas Soome { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
199767f8919635c4928607450d9e0abb932109ceToomas Soome struct type **tqe_prev; /* address of previous next element */ \
199767f8919635c4928607450d9e0abb932109ceToomas Soome class type **tqe_prev; /* address of previous next element */ \
199767f8919635c4928607450d9e0abb932109ceToomas Soome * Tail queue functions.
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define QMD_TAILQ_CHECK_HEAD(head, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome panic("Bad tailq head %p first->prev != head", (head)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define QMD_TAILQ_CHECK_TAIL(head, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome panic("Bad link elm %p next->prev != elm", (elm)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome panic("Bad link elm %p prev->next != elm", (elm)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#endif /* (_KERNEL && INVARIANTS) */
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_CONCAT(head1, head2, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->tqh_last = &TAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_INSERT_HEAD(head, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->tqh_last = &TAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_INSERT_TAIL(head, elm, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (head)->tqh_last = &TAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome (*(((struct headname *)((head)->tqh_last))->tqh_last))
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
199767f8919635c4928607450d9e0abb932109ceToomas Soome (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
199767f8919635c4928607450d9e0abb932109ceToomas Soome QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#define TAILQ_SWAP(head1, head2, type, field) do { \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((swap_first = (head1)->tqh_first) != NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome swap_first->field.tqe_prev = &(head1)->tqh_first; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome if ((swap_first = (head2)->tqh_first) != NULL) \
199767f8919635c4928607450d9e0abb932109ceToomas Soome swap_first->field.tqe_prev = &(head2)->tqh_first; \
199767f8919635c4928607450d9e0abb932109ceToomas Soome#endif /* !_SYS_QUEUE_H_ */