diff options
Diffstat (limited to 'misc/sys/queue.h')
| -rw-r--r-- | misc/sys/queue.h | 420 |
1 files changed, 52 insertions, 368 deletions
diff --git a/misc/sys/queue.h b/misc/sys/queue.h index b0e6b38c19..5b6e2a0a23 100644 --- a/misc/sys/queue.h +++ b/misc/sys/queue.h @@ -10,7 +10,7 @@ * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. - * 3. Neither the name of the University nor the names of its contributors + * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * @@ -26,46 +26,29 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * - * @(#)queue.h 8.5 (Berkeley) 8/20/94 + * @(#)queue.h 8.3 (Berkeley) 12/13/93 */ -#ifndef _SYS_QUEUE_H_ -#define _SYS_QUEUE_H_ +#ifndef _SYS_QUEUE_H +#define _SYS_QUEUE_H 1 /* - * This file defines five types of data structures: singly-linked lists, - * lists, simple queues, tail queues, and circular queues. - * - * A singly-linked list is headed by a single forward pointer. The - * elements are singly linked for minimum space and pointer manipulation - * overhead at the expense of O(n) removal for arbitrary elements. New - * elements can be added to the list after an existing element or at the - * head of the list. Elements being removed from the head of the list - * should use the explicit macro for this purpose for optimum - * efficiency. A singly-linked list may only be traversed in the forward - * direction. Singly-linked lists are ideal for applications with large - * datasets and few or no removals or for implementing a LIFO queue. + * This file defines three types of data structures: lists, tail queues, + * and circular queues. * * A list is headed by a single forward pointer (or an array of forward * pointers for a hash table header). The elements are doubly linked * so that an arbitrary element can be removed without a need to - * traverse the list. New elements can be added to the list before - * or after an existing element or at the head of the list. A list - * may only be traversed in the forward direction. - * - * A simple queue is headed by a pair of pointers, one the head of the - * list and the other to the tail of the list. The elements are singly - * linked to save space, so elements can only be removed from the - * head of the list. New elements can be added to the list after - * an existing element, at the head of the list, or at the end of the - * list. A simple queue may only be traversed in the forward direction. + * traverse the list. New elements can be added to the list after + * an existing element or at the head of the list. A list may only be + * traversed in the forward direction. * * A tail queue is headed by a pair of pointers, one to the head of the * list and the other to the tail of the list. The elements are doubly * linked so that an arbitrary element can be removed without a need to - * traverse the list. New elements can be added to the list before or - * after an existing element, at the head of the list, or at the end of - * the list. A tail queue may be traversed in either direction. + * traverse the list. New elements can be added to the list after + * an existing element, at the head of the list, or at the end of the + * list. A tail queue may only be traversed in the forward direction. * * A circle queue is headed by a pair of pointers, one to the head of the * list and the other to the tail of the list. The elements are doubly @@ -81,15 +64,12 @@ /* * List definitions. */ -#define LIST_HEAD(name, type) \ +#define LIST_HEAD(name, type) \ struct name { \ struct type *lh_first; /* first element */ \ } -#define LIST_HEAD_INITIALIZER(head) \ - { NULL } - -#define LIST_ENTRY(type) \ +#define LIST_ENTRY(type) \ struct { \ struct type *le_next; /* next element */ \ struct type **le_prev; /* address of previous next element */ \ @@ -98,307 +78,73 @@ struct { \ /* * List functions. */ -#define LIST_INIT(head) do { \ +#define LIST_INIT(head) { \ (head)->lh_first = NULL; \ -} while (/*CONSTCOND*/0) +} -#define LIST_INSERT_AFTER(listelm, elm, field) do { \ +#define LIST_INSERT_AFTER(listelm, elm, field) { \ if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ (listelm)->field.le_next->field.le_prev = \ &(elm)->field.le_next; \ (listelm)->field.le_next = (elm); \ (elm)->field.le_prev = &(listelm)->field.le_next; \ -} while (/*CONSTCOND*/0) - -#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ - (elm)->field.le_prev = (listelm)->field.le_prev; \ - (elm)->field.le_next = (listelm); \ - *(listelm)->field.le_prev = (elm); \ - (listelm)->field.le_prev = &(elm)->field.le_next; \ -} while (/*CONSTCOND*/0) +} -#define LIST_INSERT_HEAD(head, elm, field) do { \ +#define LIST_INSERT_HEAD(head, elm, field) { \ if (((elm)->field.le_next = (head)->lh_first) != NULL) \ (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ (head)->lh_first = (elm); \ (elm)->field.le_prev = &(head)->lh_first; \ -} while (/*CONSTCOND*/0) +} -#define LIST_REMOVE(elm, field) do { \ +#define LIST_REMOVE(elm, field) { \ if ((elm)->field.le_next != NULL) \ (elm)->field.le_next->field.le_prev = \ (elm)->field.le_prev; \ *(elm)->field.le_prev = (elm)->field.le_next; \ -} while (/*CONSTCOND*/0) - -#define LIST_FOREACH(var, head, field) \ - for ((var) = ((head)->lh_first); \ - (var); \ - (var) = ((var)->field.le_next)) - -/* - * List access methods. - */ -#define LIST_EMPTY(head) ((head)->lh_first == NULL) -#define LIST_FIRST(head) ((head)->lh_first) -#define LIST_NEXT(elm, field) ((elm)->field.le_next) - - -/* - * Singly-linked List definitions. - */ -#define SLIST_HEAD(name, type) \ -struct name { \ - struct type *slh_first; /* first element */ \ -} - -#define SLIST_HEAD_INITIALIZER(head) \ - { NULL } - -#define SLIST_ENTRY(type) \ -struct { \ - struct type *sle_next; /* next element */ \ -} - -/* - * Singly-linked List functions. - */ -#define SLIST_INIT(head) do { \ - (head)->slh_first = NULL; \ -} while (/*CONSTCOND*/0) - -#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ - (elm)->field.sle_next = (slistelm)->field.sle_next; \ - (slistelm)->field.sle_next = (elm); \ -} while (/*CONSTCOND*/0) - -#define SLIST_INSERT_HEAD(head, elm, field) do { \ - (elm)->field.sle_next = (head)->slh_first; \ - (head)->slh_first = (elm); \ -} while (/*CONSTCOND*/0) - -#define SLIST_REMOVE_HEAD(head, field) do { \ - (head)->slh_first = (head)->slh_first->field.sle_next; \ -} while (/*CONSTCOND*/0) - -#define SLIST_REMOVE(head, elm, type, field) do { \ - if ((head)->slh_first == (elm)) { \ - SLIST_REMOVE_HEAD((head), field); \ - } \ - else { \ - struct type *curelm = (head)->slh_first; \ - while(curelm->field.sle_next != (elm)) \ - curelm = curelm->field.sle_next; \ - curelm->field.sle_next = \ - curelm->field.sle_next->field.sle_next; \ - } \ -} while (/*CONSTCOND*/0) - -#define SLIST_FOREACH(var, head, field) \ - for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) - -/* - * Singly-linked List access methods. - */ -#define SLIST_EMPTY(head) ((head)->slh_first == NULL) -#define SLIST_FIRST(head) ((head)->slh_first) -#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) - - -/* - * Singly-linked Tail queue declarations. - */ -#define STAILQ_HEAD(name, type) \ -struct name { \ - struct type *stqh_first; /* first element */ \ - struct type **stqh_last; /* addr of last next element */ \ -} - -#define STAILQ_HEAD_INITIALIZER(head) \ - { NULL, &(head).stqh_first } - -#define STAILQ_ENTRY(type) \ -struct { \ - struct type *stqe_next; /* next element */ \ -} - -/* - * Singly-linked Tail queue functions. - */ -#define STAILQ_INIT(head) do { \ - (head)->stqh_first = NULL; \ - (head)->stqh_last = &(head)->stqh_first; \ -} while (/*CONSTCOND*/0) - -#define STAILQ_INSERT_HEAD(head, elm, field) do { \ - if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ - (head)->stqh_last = &(elm)->field.stqe_next; \ - (head)->stqh_first = (elm); \ -} while (/*CONSTCOND*/0) - -#define STAILQ_INSERT_TAIL(head, elm, field) do { \ - (elm)->field.stqe_next = NULL; \ - *(head)->stqh_last = (elm); \ - (head)->stqh_last = &(elm)->field.stqe_next; \ -} while (/*CONSTCOND*/0) - -#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ - if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\ - (head)->stqh_last = &(elm)->field.stqe_next; \ - (listelm)->field.stqe_next = (elm); \ -} while (/*CONSTCOND*/0) - -#define STAILQ_REMOVE_HEAD(head, field) do { \ - if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \ - (head)->stqh_last = &(head)->stqh_first; \ -} while (/*CONSTCOND*/0) - -#define STAILQ_REMOVE(head, elm, type, field) do { \ - if ((head)->stqh_first == (elm)) { \ - STAILQ_REMOVE_HEAD((head), field); \ - } else { \ - struct type *curelm = (head)->stqh_first; \ - while (curelm->field.stqe_next != (elm)) \ - curelm = curelm->field.stqe_next; \ - if ((curelm->field.stqe_next = \ - curelm->field.stqe_next->field.stqe_next) == NULL) \ - (head)->stqh_last = &(curelm)->field.stqe_next; \ - } \ -} while (/*CONSTCOND*/0) - -#define STAILQ_FOREACH(var, head, field) \ - for ((var) = ((head)->stqh_first); \ - (var); \ - (var) = ((var)->field.stqe_next)) - -/* - * Singly-linked Tail queue access methods. - */ -#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) -#define STAILQ_FIRST(head) ((head)->stqh_first) -#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) - - -/* - * Simple queue definitions. - */ -#define SIMPLEQ_HEAD(name, type) \ -struct name { \ - struct type *sqh_first; /* first element */ \ - struct type **sqh_last; /* addr of last next element */ \ -} - -#define SIMPLEQ_HEAD_INITIALIZER(head) \ - { NULL, &(head).sqh_first } - -#define SIMPLEQ_ENTRY(type) \ -struct { \ - struct type *sqe_next; /* next element */ \ } /* - * Simple queue functions. - */ -#define SIMPLEQ_INIT(head) do { \ - (head)->sqh_first = NULL; \ - (head)->sqh_last = &(head)->sqh_first; \ -} while (/*CONSTCOND*/0) - -#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ - if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ - (head)->sqh_last = &(elm)->field.sqe_next; \ - (head)->sqh_first = (elm); \ -} while (/*CONSTCOND*/0) - -#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ - (elm)->field.sqe_next = NULL; \ - *(head)->sqh_last = (elm); \ - (head)->sqh_last = &(elm)->field.sqe_next; \ -} while (/*CONSTCOND*/0) - -#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ - if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ - (head)->sqh_last = &(elm)->field.sqe_next; \ - (listelm)->field.sqe_next = (elm); \ -} while (/*CONSTCOND*/0) - -#define SIMPLEQ_REMOVE_HEAD(head, field) do { \ - if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ - (head)->sqh_last = &(head)->sqh_first; \ -} while (/*CONSTCOND*/0) - -#define SIMPLEQ_REMOVE(head, elm, type, field) do { \ - if ((head)->sqh_first == (elm)) { \ - SIMPLEQ_REMOVE_HEAD((head), field); \ - } else { \ - struct type *curelm = (head)->sqh_first; \ - while (curelm->field.sqe_next != (elm)) \ - curelm = curelm->field.sqe_next; \ - if ((curelm->field.sqe_next = \ - curelm->field.sqe_next->field.sqe_next) == NULL) \ - (head)->sqh_last = &(curelm)->field.sqe_next; \ - } \ -} while (/*CONSTCOND*/0) - -#define SIMPLEQ_FOREACH(var, head, field) \ - for ((var) = ((head)->sqh_first); \ - (var); \ - (var) = ((var)->field.sqe_next)) - -/* - * Simple queue access methods. - */ -#define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL) -#define SIMPLEQ_FIRST(head) ((head)->sqh_first) -#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) - - -/* * Tail queue definitions. */ -#define _TAILQ_HEAD(name, type, qual) \ +#define TAILQ_HEAD(name, type) \ struct name { \ - qual type *tqh_first; /* first element */ \ - qual type *qual *tqh_last; /* addr of last next element */ \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ } -#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,) - -#define TAILQ_HEAD_INITIALIZER(head) \ - { NULL, &(head).tqh_first } -#define _TAILQ_ENTRY(type, qual) \ +#define TAILQ_ENTRY(type) \ struct { \ - qual type *tqe_next; /* next element */ \ - qual type *qual *tqe_prev; /* address of previous next element */\ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ } -#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,) /* * Tail queue functions. */ -#define TAILQ_INIT(head) do { \ +#define TAILQ_INIT(head) { \ (head)->tqh_first = NULL; \ (head)->tqh_last = &(head)->tqh_first; \ -} while (/*CONSTCOND*/0) +} -#define TAILQ_INSERT_HEAD(head, elm, field) do { \ +#define TAILQ_INSERT_HEAD(head, elm, field) { \ if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ - (head)->tqh_first->field.tqe_prev = \ + (elm)->field.tqe_next->field.tqe_prev = \ &(elm)->field.tqe_next; \ else \ (head)->tqh_last = &(elm)->field.tqe_next; \ (head)->tqh_first = (elm); \ (elm)->field.tqe_prev = &(head)->tqh_first; \ -} while (/*CONSTCOND*/0) +} -#define TAILQ_INSERT_TAIL(head, elm, field) do { \ +#define TAILQ_INSERT_TAIL(head, elm, field) { \ (elm)->field.tqe_next = NULL; \ (elm)->field.tqe_prev = (head)->tqh_last; \ *(head)->tqh_last = (elm); \ (head)->tqh_last = &(elm)->field.tqe_next; \ -} while (/*CONSTCOND*/0) +} -#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) { \ if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ (elm)->field.tqe_next->field.tqe_prev = \ &(elm)->field.tqe_next; \ @@ -406,60 +152,27 @@ struct { \ (head)->tqh_last = &(elm)->field.tqe_next; \ (listelm)->field.tqe_next = (elm); \ (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ -} while (/*CONSTCOND*/0) - -#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ - (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ - (elm)->field.tqe_next = (listelm); \ - *(listelm)->field.tqe_prev = (elm); \ - (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ -} while (/*CONSTCOND*/0) +} -#define TAILQ_REMOVE(head, elm, field) do { \ +#define TAILQ_REMOVE(head, elm, field) { \ if (((elm)->field.tqe_next) != NULL) \ (elm)->field.tqe_next->field.tqe_prev = \ (elm)->field.tqe_prev; \ else \ (head)->tqh_last = (elm)->field.tqe_prev; \ *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ -} while (/*CONSTCOND*/0) - -#define TAILQ_FOREACH(var, head, field) \ - for ((var) = ((head)->tqh_first); \ - (var); \ - (var) = ((var)->field.tqe_next)) - -#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ - for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \ - (var); \ - (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last))) - -/* - * Tail queue access methods. - */ -#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) -#define TAILQ_FIRST(head) ((head)->tqh_first) -#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) - -#define TAILQ_LAST(head, headname) \ - (*(((struct headname *)((head)->tqh_last))->tqh_last)) -#define TAILQ_PREV(elm, headname, field) \ - (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) - +} /* * Circular queue definitions. */ -#define CIRCLEQ_HEAD(name, type) \ +#define CIRCLEQ_HEAD(name, type) \ struct name { \ struct type *cqh_first; /* first element */ \ struct type *cqh_last; /* last element */ \ } -#define CIRCLEQ_HEAD_INITIALIZER(head) \ - { (void *)&head, (void *)&head } - -#define CIRCLEQ_ENTRY(type) \ +#define CIRCLEQ_ENTRY(type) \ struct { \ struct type *cqe_next; /* next element */ \ struct type *cqe_prev; /* previous element */ \ @@ -468,12 +181,12 @@ struct { \ /* * Circular queue functions. */ -#define CIRCLEQ_INIT(head) do { \ +#define CIRCLEQ_INIT(head) { \ (head)->cqh_first = (void *)(head); \ (head)->cqh_last = (void *)(head); \ -} while (/*CONSTCOND*/0) +} -#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ +#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) { \ (elm)->field.cqe_next = (listelm)->field.cqe_next; \ (elm)->field.cqe_prev = (listelm); \ if ((listelm)->field.cqe_next == (void *)(head)) \ @@ -481,9 +194,9 @@ struct { \ else \ (listelm)->field.cqe_next->field.cqe_prev = (elm); \ (listelm)->field.cqe_next = (elm); \ -} while (/*CONSTCOND*/0) +} -#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ +#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) { \ (elm)->field.cqe_next = (listelm); \ (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ if ((listelm)->field.cqe_prev == (void *)(head)) \ @@ -491,9 +204,9 @@ struct { \ else \ (listelm)->field.cqe_prev->field.cqe_next = (elm); \ (listelm)->field.cqe_prev = (elm); \ -} while (/*CONSTCOND*/0) +} -#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ +#define CIRCLEQ_INSERT_HEAD(head, elm, field) { \ (elm)->field.cqe_next = (head)->cqh_first; \ (elm)->field.cqe_prev = (void *)(head); \ if ((head)->cqh_last == (void *)(head)) \ @@ -501,9 +214,9 @@ struct { \ else \ (head)->cqh_first->field.cqe_prev = (elm); \ (head)->cqh_first = (elm); \ -} while (/*CONSTCOND*/0) +} -#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ +#define CIRCLEQ_INSERT_TAIL(head, elm, field) { \ (elm)->field.cqe_next = (void *)(head); \ (elm)->field.cqe_prev = (head)->cqh_last; \ if ((head)->cqh_first == (void *)(head)) \ @@ -511,9 +224,9 @@ struct { \ else \ (head)->cqh_last->field.cqe_next = (elm); \ (head)->cqh_last = (elm); \ -} while (/*CONSTCOND*/0) +} -#define CIRCLEQ_REMOVE(head, elm, field) do { \ +#define CIRCLEQ_REMOVE(head, elm, field) { \ if ((elm)->field.cqe_next == (void *)(head)) \ (head)->cqh_last = (elm)->field.cqe_prev; \ else \ @@ -524,34 +237,5 @@ struct { \ else \ (elm)->field.cqe_prev->field.cqe_next = \ (elm)->field.cqe_next; \ -} while (/*CONSTCOND*/0) - -#define CIRCLEQ_FOREACH(var, head, field) \ - for ((var) = ((head)->cqh_first); \ - (var) != (const void *)(head); \ - (var) = ((var)->field.cqe_next)) - -#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ - for ((var) = ((head)->cqh_last); \ - (var) != (const void *)(head); \ - (var) = ((var)->field.cqe_prev)) - -/* - * Circular queue access methods. - */ -#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) -#define CIRCLEQ_FIRST(head) ((head)->cqh_first) -#define CIRCLEQ_LAST(head) ((head)->cqh_last) -#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) -#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) - -#define CIRCLEQ_LOOP_NEXT(head, elm, field) \ - (((elm)->field.cqe_next == (void *)(head)) \ - ? ((head)->cqh_first) \ - : (elm->field.cqe_next)) -#define CIRCLEQ_LOOP_PREV(head, elm, field) \ - (((elm)->field.cqe_prev == (void *)(head)) \ - ? ((head)->cqh_last) \ - : (elm->field.cqe_prev)) - +} #endif /* sys/queue.h */ |