diff options
Diffstat (limited to 'main/libc-dev/sys-queue.h')
| -rw-r--r-- | main/libc-dev/sys-queue.h | 643 |
1 files changed, 371 insertions, 272 deletions
diff --git a/main/libc-dev/sys-queue.h b/main/libc-dev/sys-queue.h index 8632eb8335..99d01a55b1 100644 --- a/main/libc-dev/sys-queue.h +++ b/main/libc-dev/sys-queue.h @@ -1,4 +1,4 @@ -/* $NetBSD: queue.h,v 1.54 2013/04/10 22:22:16 christos Exp $ */ +/* $NetBSD: queue.h,v 1.68 2014/11/19 08:10:01 uebayasi Exp $ */ /* * Copyright (c) 1991, 1993 @@ -34,8 +34,6 @@ #ifndef _SYS_QUEUE_H_ #define _SYS_QUEUE_H_ -#include <stddef.h> - /* * This file defines five types of data structures: singly-linked lists, * lists, simple queues, tail queues, and circular queues. @@ -83,102 +81,24 @@ */ /* - * List definitions. - */ -#define LIST_HEAD(name, type) \ -struct name { \ - struct type *lh_first; /* first element */ \ -} - -#define LIST_HEAD_INITIALIZER(head) \ - { NULL } - -#define LIST_ENTRY(type) \ -struct { \ - struct type *le_next; /* next element */ \ - struct type **le_prev; /* address of previous next element */ \ -} - -/* - * List functions. + * Include the definition of NULL only on NetBSD because sys/null.h + * is not available elsewhere. This conditional makes the header + * portable and it can simply be dropped verbatim into any system. + * The caveat is that on other systems some other header + * must provide NULL before the macros can be used. */ -#if defined(_KERNEL) && defined(QUEUEDEBUG) -#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \ - if ((head)->lh_first && \ - (head)->lh_first->field.le_prev != &(head)->lh_first) \ - panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__); -#define QUEUEDEBUG_LIST_OP(elm, field) \ - if ((elm)->field.le_next && \ - (elm)->field.le_next->field.le_prev != \ - &(elm)->field.le_next) \ - panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\ - if (*(elm)->field.le_prev != (elm)) \ - panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__); -#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \ - (elm)->field.le_next = (void *)1L; \ - (elm)->field.le_prev = (void *)1L; -#else -#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) -#define QUEUEDEBUG_LIST_OP(elm, field) -#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) +#ifdef __NetBSD__ +#include <sys/null.h> #endif -#define LIST_INIT(head) do { \ - (head)->lh_first = LIST_END(head); \ -} while (/*CONSTCOND*/0) - -#define LIST_INSERT_AFTER(listelm, elm, field) do { \ - QUEUEDEBUG_LIST_OP((listelm), field) \ - if (((elm)->field.le_next = (listelm)->field.le_next) != \ - LIST_END(head)) \ - (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 { \ - QUEUEDEBUG_LIST_OP((listelm), field) \ - (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 { \ - QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \ - if (((elm)->field.le_next = (head)->lh_first) != LIST_END(head))\ - (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 { \ - QUEUEDEBUG_LIST_OP((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; \ - QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \ -} while (/*CONSTCOND*/0) - -#define LIST_FOREACH(var, head, field) \ - for ((var) = ((head)->lh_first); \ - (var); \ - (var) = ((var)->field.le_next)) - -#define LIST_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = LIST_FIRST((head)); \ - (var) && ((tvar) = LIST_NEXT((var), field), 1); \ - (var) = (tvar)) -/* - * List access methods. - */ -#define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head)) -#define LIST_END(head) NULL -#define LIST_FIRST(head) ((head)->lh_first) -#define LIST_NEXT(elm, field) ((elm)->field.le_next) - +#if defined(QUEUEDEBUG) +# if defined(_KERNEL) +# define QUEUEDEBUG_ABORT(...) panic(__VA_ARGS__) +# else +# include <err.h> +# define QUEUEDEBUG_ABORT(...) err(1, __VA_ARGS__) +# endif +#endif /* * Singly-linked List definitions. @@ -197,10 +117,29 @@ struct { \ } /* + * Singly-linked List access methods. + */ +#define SLIST_FIRST(head) ((head)->slh_first) +#define SLIST_END(head) NULL +#define SLIST_EMPTY(head) ((head)->slh_first == NULL) +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_FOREACH(var, head, field) \ + for((var) = (head)->slh_first; \ + (var) != SLIST_END(head); \ + (var) = (var)->field.sle_next) + +#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SLIST_FIRST((head)); \ + (var) != SLIST_END(head) && \ + ((tvar) = SLIST_NEXT((var), field), 1); \ + (var) = (tvar)) + +/* * Singly-linked List functions. */ #define SLIST_INIT(head) do { \ - (head)->slh_first = NULL; \ + (head)->slh_first = SLIST_END(head); \ } while (/*CONSTCOND*/0) #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ @@ -213,6 +152,11 @@ struct { \ (head)->slh_first = (elm); \ } while (/*CONSTCOND*/0) +#define SLIST_REMOVE_AFTER(slistelm, field) do { \ + (slistelm)->field.sle_next = \ + SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \ +} while (/*CONSTCOND*/0) + #define SLIST_REMOVE_HEAD(head, field) do { \ (head)->slh_first = (head)->slh_first->field.sle_next; \ } while (/*CONSTCOND*/0) @@ -230,119 +174,125 @@ struct { \ } \ } while (/*CONSTCOND*/0) -#define SLIST_REMOVE_AFTER(slistelm, field) do { \ - (slistelm)->field.sle_next = \ - SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \ -} while (/*CONSTCOND*/0) - -#define SLIST_FOREACH(var, head, field) \ - for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) - -#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = SLIST_FIRST((head)); \ - (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ - (var) = (tvar)) - -/* - * 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. + * List definitions. */ -#define STAILQ_HEAD(name, type) \ +#define LIST_HEAD(name, type) \ struct name { \ - struct type *stqh_first; /* first element */ \ - struct type **stqh_last; /* addr of last next element */ \ + struct type *lh_first; /* first element */ \ } -#define STAILQ_HEAD_INITIALIZER(head) \ - { NULL, &(head).stqh_first } +#define LIST_HEAD_INITIALIZER(head) \ + { NULL } -#define STAILQ_ENTRY(type) \ +#define LIST_ENTRY(type) \ struct { \ - struct type *stqe_next; /* next element */ \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ } /* - * Singly-linked Tail queue functions. + * List access methods. */ -#define STAILQ_INIT(head) do { \ - (head)->stqh_first = NULL; \ - (head)->stqh_last = &(head)->stqh_first; \ -} while (/*CONSTCOND*/0) +#define LIST_FIRST(head) ((head)->lh_first) +#define LIST_END(head) NULL +#define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head)) +#define LIST_NEXT(elm, field) ((elm)->field.le_next) -#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 LIST_FOREACH(var, head, field) \ + for ((var) = ((head)->lh_first); \ + (var) != LIST_END(head); \ + (var) = ((var)->field.le_next)) -#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 LIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = LIST_FIRST((head)); \ + (var) != LIST_END(head) && \ + ((tvar) = LIST_NEXT((var), field), 1); \ + (var) = (tvar)) -#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); \ +#define LIST_MOVE(head1, head2) do { \ + LIST_INIT((head2)); \ + if (!LIST_EMPTY((head1))) { \ + (head2)->lh_first = (head1)->lh_first; \ + LIST_INIT((head1)); \ + } \ } 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) +/* + * List functions. + */ +#if defined(QUEUEDEBUG) +#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \ + if ((head)->lh_first && \ + (head)->lh_first->field.le_prev != &(head)->lh_first) \ + QUEUEDEBUG_ABORT("LIST_INSERT_HEAD %p %s:%d", (head), \ + __FILE__, __LINE__); +#define QUEUEDEBUG_LIST_OP(elm, field) \ + if ((elm)->field.le_next && \ + (elm)->field.le_next->field.le_prev != \ + &(elm)->field.le_next) \ + QUEUEDEBUG_ABORT("LIST_* forw %p %s:%d", (elm), \ + __FILE__, __LINE__); \ + if (*(elm)->field.le_prev != (elm)) \ + QUEUEDEBUG_ABORT("LIST_* back %p %s:%d", (elm), \ + __FILE__, __LINE__); +#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \ + (elm)->field.le_next = (void *)1L; \ + (elm)->field.le_prev = (void *)1L; +#else +#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) +#define QUEUEDEBUG_LIST_OP(elm, field) +#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) +#endif -#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; \ - } \ +#define LIST_INIT(head) do { \ + (head)->lh_first = LIST_END(head); \ } while (/*CONSTCOND*/0) -#define STAILQ_FOREACH(var, head, field) \ - for ((var) = ((head)->stqh_first); \ - (var); \ - (var) = ((var)->field.stqe_next)) - -#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ - for ((var) = STAILQ_FIRST((head)); \ - (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ - (var) = (tvar)) +#define LIST_INSERT_AFTER(listelm, elm, field) do { \ + QUEUEDEBUG_LIST_OP((listelm), field) \ + if (((elm)->field.le_next = (listelm)->field.le_next) != \ + LIST_END(head)) \ + (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 STAILQ_CONCAT(head1, head2) do { \ - if (!STAILQ_EMPTY((head2))) { \ - *(head1)->stqh_last = (head2)->stqh_first; \ - (head1)->stqh_last = (head2)->stqh_last; \ - STAILQ_INIT((head2)); \ - } \ +#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ + QUEUEDEBUG_LIST_OP((listelm), field) \ + (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 STAILQ_LAST(head, type, field) \ - (STAILQ_EMPTY((head)) ? \ - NULL : \ - ((struct type *)(void *) \ - ((char *)((head)->stqh_last) - offsetof(struct type, field)))) +#define LIST_INSERT_HEAD(head, elm, field) do { \ + QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \ + if (((elm)->field.le_next = (head)->lh_first) != LIST_END(head))\ + (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ + (head)->lh_first = (elm); \ + (elm)->field.le_prev = &(head)->lh_first; \ +} while (/*CONSTCOND*/0) -/* - * 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) +#define LIST_REMOVE(elm, field) do { \ + QUEUEDEBUG_LIST_OP((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; \ + QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \ +} while (/*CONSTCOND*/0) +#define LIST_REPLACE(elm, elm2, field) do { \ + if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ + (elm2)->field.le_next->field.le_prev = \ + &(elm2)->field.le_next; \ + (elm2)->field.le_prev = (elm)->field.le_prev; \ + *(elm2)->field.le_prev = (elm2); \ + QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \ +} while (/*CONSTCOND*/0) /* * Simple queue definitions. @@ -362,6 +312,25 @@ struct { \ } /* + * Simple queue access methods. + */ +#define SIMPLEQ_FIRST(head) ((head)->sqh_first) +#define SIMPLEQ_END(head) NULL +#define SIMPLEQ_EMPTY(head) ((head)->sqh_first == SIMPLEQ_END(head)) +#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) + +#define SIMPLEQ_FOREACH(var, head, field) \ + for ((var) = ((head)->sqh_first); \ + (var) != SIMPLEQ_END(head); \ + (var) = ((var)->field.sqe_next)) + +#define SIMPLEQ_FOREACH_SAFE(var, head, field, next) \ + for ((var) = ((head)->sqh_first); \ + (var) != SIMPLEQ_END(head) && \ + ((next = ((var)->field.sqe_next)), 1); \ + (var) = (next)) + +/* * Simple queue functions. */ #define SIMPLEQ_INIT(head) do { \ @@ -392,6 +361,12 @@ struct { \ (head)->sqh_last = &(head)->sqh_first; \ } while (/*CONSTCOND*/0) +#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ + if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \ + == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ +} while (/*CONSTCOND*/0) + #define SIMPLEQ_REMOVE(head, elm, type, field) do { \ if ((head)->sqh_first == (elm)) { \ SIMPLEQ_REMOVE_HEAD((head), field); \ @@ -405,16 +380,6 @@ struct { \ } \ } while (/*CONSTCOND*/0) -#define SIMPLEQ_FOREACH(var, head, field) \ - for ((var) = ((head)->sqh_first); \ - (var); \ - (var) = ((var)->field.sqe_next)) - -#define SIMPLEQ_FOREACH_SAFE(var, head, field, next) \ - for ((var) = ((head)->sqh_first); \ - (var) && ((next = ((var)->field.sqe_next)), 1); \ - (var) = (next)) - #define SIMPLEQ_CONCAT(head1, head2) do { \ if (!SIMPLEQ_EMPTY((head2))) { \ *(head1)->sqh_last = (head2)->sqh_first; \ @@ -430,14 +395,6 @@ struct { \ ((char *)((head)->sqh_last) - offsetof(struct type, field)))) /* - * 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) \ @@ -458,28 +415,65 @@ struct { \ #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,) /* + * Tail queue access methods. + */ +#define TAILQ_FIRST(head) ((head)->tqh_first) +#define TAILQ_END(head) (NULL) +#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)) +#define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head)) + + +#define TAILQ_FOREACH(var, head, field) \ + for ((var) = ((head)->tqh_first); \ + (var) != TAILQ_END(head); \ + (var) = ((var)->field.tqe_next)) + +#define TAILQ_FOREACH_SAFE(var, head, field, next) \ + for ((var) = ((head)->tqh_first); \ + (var) != TAILQ_END(head) && \ + ((next) = TAILQ_NEXT(var, field), 1); (var) = (next)) + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\ + (var) != TAILQ_END(head); \ + (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last))) + +#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \ + for ((var) = TAILQ_LAST((head), headname); \ + (var) != TAILQ_END(head) && \ + ((prev) = TAILQ_PREV((var), headname, field), 1); (var) = (prev)) + +/* * Tail queue functions. */ -#if defined(_KERNEL) && defined(QUEUEDEBUG) +#if defined(QUEUEDEBUG) #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \ if ((head)->tqh_first && \ (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \ - panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__); + QUEUEDEBUG_ABORT("TAILQ_INSERT_HEAD %p %s:%d", (head), \ + __FILE__, __LINE__); #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \ if (*(head)->tqh_last != NULL) \ - panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__); + QUEUEDEBUG_ABORT("TAILQ_INSERT_TAIL %p %s:%d", (head), \ + __FILE__, __LINE__); #define QUEUEDEBUG_TAILQ_OP(elm, field) \ if ((elm)->field.tqe_next && \ (elm)->field.tqe_next->field.tqe_prev != \ &(elm)->field.tqe_next) \ - panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\ + QUEUEDEBUG_ABORT("TAILQ_* forw %p %s:%d", (elm), \ + __FILE__, __LINE__); \ if (*(elm)->field.tqe_prev != (elm)) \ - panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__); + QUEUEDEBUG_ABORT("TAILQ_* back %p %s:%d", (elm), \ + __FILE__, __LINE__); #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \ if ((elm)->field.tqe_next == NULL && \ (head)->tqh_last != &(elm)->field.tqe_next) \ - panic("TAILQ_PREREMOVE head %p elm %p %s:%d", \ - (head), (elm), __FILE__, __LINE__); + QUEUEDEBUG_ABORT("TAILQ_PREREMOVE head %p elm %p %s:%d",\ + (head), (elm), __FILE__, __LINE__); #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \ (elm)->field.tqe_next = (void *)1L; \ (elm)->field.tqe_prev = (void *)1L; @@ -547,25 +541,17 @@ struct { \ QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \ } while (/*CONSTCOND*/0) -#define TAILQ_FOREACH(var, head, field) \ - for ((var) = ((head)->tqh_first); \ - (var) != TAILQ_END(head); \ - (var) = ((var)->field.tqe_next)) - -#define TAILQ_FOREACH_SAFE(var, head, field, next) \ - for ((var) = ((head)->tqh_first); \ - (var) != TAILQ_END(head) && \ - ((next) = TAILQ_NEXT(var, field), 1); (var) = (next)) - -#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ - for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\ - (var) != TAILQ_END(head); \ - (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last))) - -#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \ - for ((var) = TAILQ_LAST((head), headname); \ - (var) != TAILQ_END(head) && \ - ((prev) = TAILQ_PREV((var), headname, field), 1); (var) = (prev)) +#define TAILQ_REPLACE(head, elm, elm2, field) do { \ + if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != \ + TAILQ_END(head)) \ + (elm2)->field.tqe_next->field.tqe_prev = \ + &(elm2)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm2)->field.tqe_next; \ + (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ + *(elm2)->field.tqe_prev = (elm2); \ + QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \ +} while (/*CONSTCOND*/0) #define TAILQ_CONCAT(head1, head2, field) do { \ if (!TAILQ_EMPTY(head2)) { \ @@ -577,50 +563,157 @@ struct { \ } while (/*CONSTCOND*/0) /* - * Tail queue access methods. + * Singly-linked Tail queue declarations. */ -#define TAILQ_EMPTY(head) ((head)->tqh_first == TAILQ_END(head)) -#define TAILQ_FIRST(head) ((head)->tqh_first) -#define TAILQ_END(head) (NULL) -#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) +#define STAILQ_HEAD(name, type) \ +struct name { \ + struct type *stqh_first; /* first element */ \ + struct type **stqh_last; /* addr of last next element */ \ +} -#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)) +#define STAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).stqh_first } + +#define STAILQ_ENTRY(type) \ +struct { \ + struct type *stqe_next; /* next element */ \ +} + +/* + * Singly-linked Tail queue access methods. + */ +#define STAILQ_FIRST(head) ((head)->stqh_first) +#define STAILQ_END(head) NULL +#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) +#define STAILQ_EMPTY(head) (STAILQ_FIRST(head) == STAILQ_END(head)) + +/* + * 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)) +#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = STAILQ_FIRST((head)); \ + (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ + (var) = (tvar)) + +#define STAILQ_CONCAT(head1, head2) do { \ + if (!STAILQ_EMPTY((head2))) { \ + *(head1)->stqh_last = (head2)->stqh_first; \ + (head1)->stqh_last = (head2)->stqh_last; \ + STAILQ_INIT((head2)); \ + } \ +} while (/*CONSTCOND*/0) + +#define STAILQ_LAST(head, type, field) \ + (STAILQ_EMPTY((head)) ? \ + NULL : \ + ((struct type *)(void *) \ + ((char *)((head)->stqh_last) - offsetof(struct type, field)))) + + +#ifndef _KERNEL /* - * Circular queue definitions. + * Circular queue definitions. Do not use. We still keep the macros + * for compatibility but because of pointer aliasing issues their use + * is discouraged! */ -#if defined(_KERNEL) && defined(QUEUEDEBUG) + +/* + * __launder_type(): We use this ugly hack to work around the the compiler + * noticing that two types may not alias each other and elide tests in code. + * We hit this in the CIRCLEQ macros when comparing 'struct name *' and + * 'struct type *' (see CIRCLEQ_HEAD()). Modern compilers (such as GCC + * 4.8) declare these comparisons as always false, causing the code to + * not run as designed. + * + * This hack is only to be used for comparisons and thus can be fully const. + * Do not use for assignment. + * + * If we ever choose to change the ABI of the CIRCLEQ macros, we could fix + * this by changing the head/tail sentinal values, but see the note above + * this one. + */ +static __inline const void * __launder_type(const void *); +static __inline const void * +__launder_type(const void *__x) +{ + __asm __volatile("" : "+r" (__x)); + return __x; +} + +#if defined(QUEUEDEBUG) #define QUEUEDEBUG_CIRCLEQ_HEAD(head, field) \ - if ((head)->cqh_first != (void *)(head) && \ - (head)->cqh_first->field.cqe_prev != (void *)(head)) \ - panic("CIRCLEQ head forw %p %s:%d", (head), \ + if ((head)->cqh_first != CIRCLEQ_ENDC(head) && \ + (head)->cqh_first->field.cqe_prev != CIRCLEQ_ENDC(head)) \ + QUEUEDEBUG_ABORT("CIRCLEQ head forw %p %s:%d", (head), \ __FILE__, __LINE__); \ - if ((head)->cqh_last != (void *)(head) && \ - (head)->cqh_last->field.cqe_next != (void *)(head)) \ - panic("CIRCLEQ head back %p %s:%d", (head), \ + if ((head)->cqh_last != CIRCLEQ_ENDC(head) && \ + (head)->cqh_last->field.cqe_next != CIRCLEQ_ENDC(head)) \ + QUEUEDEBUG_ABORT("CIRCLEQ head back %p %s:%d", (head), \ __FILE__, __LINE__); #define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field) \ - if ((elm)->field.cqe_next == (void *)(head)) { \ + if ((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) { \ if ((head)->cqh_last != (elm)) \ - panic("CIRCLEQ elm last %p %s:%d", (elm), \ - __FILE__, __LINE__); \ + QUEUEDEBUG_ABORT("CIRCLEQ elm last %p %s:%d", \ + (elm), __FILE__, __LINE__); \ } else { \ if ((elm)->field.cqe_next->field.cqe_prev != (elm)) \ - panic("CIRCLEQ elm forw %p %s:%d", (elm), \ - __FILE__, __LINE__); \ + QUEUEDEBUG_ABORT("CIRCLEQ elm forw %p %s:%d", \ + (elm), __FILE__, __LINE__); \ } \ - if ((elm)->field.cqe_prev == (void *)(head)) { \ + if ((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) { \ if ((head)->cqh_first != (elm)) \ - panic("CIRCLEQ elm first %p %s:%d", (elm), \ - __FILE__, __LINE__); \ + QUEUEDEBUG_ABORT("CIRCLEQ elm first %p %s:%d", \ + (elm), __FILE__, __LINE__); \ } else { \ if ((elm)->field.cqe_prev->field.cqe_next != (elm)) \ - panic("CIRCLEQ elm prev %p %s:%d", (elm), \ - __FILE__, __LINE__); \ + QUEUEDEBUG_ABORT("CIRCLEQ elm prev %p %s:%d", \ + (elm), __FILE__, __LINE__); \ } #define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field) \ (elm)->field.cqe_next = (void *)1L; \ @@ -638,7 +731,7 @@ struct name { \ } #define CIRCLEQ_HEAD_INITIALIZER(head) \ - { (void *)&head, (void *)&head } + { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } #define CIRCLEQ_ENTRY(type) \ struct { \ @@ -650,8 +743,8 @@ struct { \ * Circular queue functions. */ #define CIRCLEQ_INIT(head) do { \ - (head)->cqh_first = (void *)(head); \ - (head)->cqh_last = (void *)(head); \ + (head)->cqh_first = CIRCLEQ_END(head); \ + (head)->cqh_last = CIRCLEQ_END(head); \ } while (/*CONSTCOND*/0) #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ @@ -659,7 +752,7 @@ struct { \ QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \ (elm)->field.cqe_next = (listelm)->field.cqe_next; \ (elm)->field.cqe_prev = (listelm); \ - if ((listelm)->field.cqe_next == (void *)(head)) \ + if ((listelm)->field.cqe_next == CIRCLEQ_ENDC(head)) \ (head)->cqh_last = (elm); \ else \ (listelm)->field.cqe_next->field.cqe_prev = (elm); \ @@ -671,7 +764,7 @@ struct { \ QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field) \ (elm)->field.cqe_next = (listelm); \ (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ - if ((listelm)->field.cqe_prev == (void *)(head)) \ + if ((listelm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \ (head)->cqh_first = (elm); \ else \ (listelm)->field.cqe_prev->field.cqe_next = (elm); \ @@ -681,8 +774,8 @@ struct { \ #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \ (elm)->field.cqe_next = (head)->cqh_first; \ - (elm)->field.cqe_prev = (void *)(head); \ - if ((head)->cqh_last == (void *)(head)) \ + (elm)->field.cqe_prev = CIRCLEQ_END(head); \ + if ((head)->cqh_last == CIRCLEQ_ENDC(head)) \ (head)->cqh_last = (elm); \ else \ (head)->cqh_first->field.cqe_prev = (elm); \ @@ -691,9 +784,9 @@ struct { \ #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \ - (elm)->field.cqe_next = (void *)(head); \ + (elm)->field.cqe_next = CIRCLEQ_END(head); \ (elm)->field.cqe_prev = (head)->cqh_last; \ - if ((head)->cqh_first == (void *)(head)) \ + if ((head)->cqh_first == CIRCLEQ_ENDC(head)) \ (head)->cqh_first = (elm); \ else \ (head)->cqh_last->field.cqe_next = (elm); \ @@ -703,12 +796,12 @@ struct { \ #define CIRCLEQ_REMOVE(head, elm, field) do { \ QUEUEDEBUG_CIRCLEQ_HEAD((head), field) \ QUEUEDEBUG_CIRCLEQ_ELM((head), (elm), field) \ - if ((elm)->field.cqe_next == (void *)(head)) \ + if ((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) \ (head)->cqh_last = (elm)->field.cqe_prev; \ else \ (elm)->field.cqe_next->field.cqe_prev = \ (elm)->field.cqe_prev; \ - if ((elm)->field.cqe_prev == (void *)(head)) \ + if ((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \ (head)->cqh_first = (elm)->field.cqe_next; \ else \ (elm)->field.cqe_prev->field.cqe_next = \ @@ -718,30 +811,36 @@ struct { \ #define CIRCLEQ_FOREACH(var, head, field) \ for ((var) = ((head)->cqh_first); \ - (var) != (const void *)(head); \ + (var) != CIRCLEQ_ENDC(head); \ (var) = ((var)->field.cqe_next)) #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ for ((var) = ((head)->cqh_last); \ - (var) != (const void *)(head); \ + (var) != CIRCLEQ_ENDC(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) +/* For comparisons */ +#define CIRCLEQ_ENDC(head) (__launder_type(head)) +/* For assignments */ +#define CIRCLEQ_END(head) ((void *)(head)) #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) +#define CIRCLEQ_EMPTY(head) \ + (CIRCLEQ_FIRST(head) == CIRCLEQ_ENDC(head)) #define CIRCLEQ_LOOP_NEXT(head, elm, field) \ - (((elm)->field.cqe_next == (void *)(head)) \ + (((elm)->field.cqe_next == CIRCLEQ_ENDC(head)) \ ? ((head)->cqh_first) \ : (elm->field.cqe_next)) #define CIRCLEQ_LOOP_PREV(head, elm, field) \ - (((elm)->field.cqe_prev == (void *)(head)) \ + (((elm)->field.cqe_prev == CIRCLEQ_ENDC(head)) \ ? ((head)->cqh_last) \ : (elm->field.cqe_prev)) +#endif /* !_KERNEL */ #endif /* !_SYS_QUEUE_H_ */ |