<sys/queue.h>: Sync with FreeBSD

-Add _SWAP macros.
-Avoid corrupting the list or queue if _REMOVE is invoked with a
reference to the head and QUEUE_MACRO_DEBUG is defined.
-Rename _REMOVE_NEXT to _REMOVE_AFTER since the name matches the _INSERT
macros.

Obtained-from: FreeBSD

diff --git a/sys/sys/queue.h b/sys/sys/queue.h
index 2d89ceb..e13ed26 100644 (file)
--- a/sys/sys/queue.h
+++ b/sys/sys/queue.h
@@ -27,8 +27,7 @@
  * SUCH DAMAGE.
  *
  *     @(#)queue.h     8.5 (Berkeley) 8/20/94
- * $FreeBSD: src/sys/sys/queue.h,v 1.69 2008/05/22 14:40:03 ed Exp $
- * $DragonFly: src/sys/sys/queue.h,v 1.11 2008/08/28 08:42:29 hasso Exp $
+ * $FreeBSD: src/sys/sys/queue.h,v 1.74 2010/12/03 16:07:50 kib Exp $
  */
 
 #ifndef _SYS_QUEUE_H_
@@ -97,9 +96,10 @@
  * _INSERT_AFTER               +       +       +       +
  * _INSERT_TAIL                        -       -       +       +
  * _CONCAT                     -       -       +       +
+ * _REMOVE_AFTER               +       -       +       -
  * _REMOVE_HEAD                        +       -       +       -
- * _REMOVE_NEXT                        +       -       +       -
  * _REMOVE                     +       +       +       +
+ * _SWAP                       +       +       +       +
  *
  */
 #ifdef QUEUE_MACRO_DEBUG
@@ -113,6 +113,7 @@ struct qm_trace {
 
 #define        TRACEBUF        struct qm_trace trace;
 #define        TRASHIT(x)      do {(x) = (void *)-1;} while (0)
+#define        QMD_SAVELINK(name, link)        void **name = (void *)&(link)
 
 #define        QMD_TRACE_HEAD(head) do {                                       \
        (head)->trace.prevline = (head)->trace.lastline;                \
@@ -131,6 +132,7 @@ struct qm_trace {
 #else
 #define        QMD_TRACE_ELEM(elem)
 #define        QMD_TRACE_HEAD(head)
+#define        QMD_SAVELINK(name, link)
 #define        TRACEBUF
 #define        TRASHIT(x)
 #endif /* QUEUE_MACRO_DEBUG */
@@ -192,6 +194,7 @@ struct {                                                            \
 #define        SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
 
 #define        SLIST_REMOVE(head, elm, type, field) do {                       \
+       QMD_SAVELINK(oldnext, (elm)->field.sle_next);                   \
        if (SLIST_FIRST((head)) == (elm)) {                             \
                SLIST_REMOVE_HEAD((head), field);                       \
        }                                                               \
@@ -199,12 +202,12 @@ struct {                                                          \
                struct type *curelm = SLIST_FIRST((head));              \
                while (SLIST_NEXT(curelm, field) != (elm))              \
                        curelm = SLIST_NEXT(curelm, field);             \
-               SLIST_REMOVE_NEXT(head, curelm, field);                 \
+               SLIST_REMOVE_AFTER(curelm, field);                      \
        }                                                               \
-       TRASHIT((elm)->field.sle_next);                                 \
+       TRASHIT(*oldnext);                                              \
 } while (0)
 
-#define SLIST_REMOVE_NEXT(head, elm, field) do {                               \
+#define SLIST_REMOVE_AFTER(elm, field) do {                            \
        SLIST_NEXT(elm, field) =                                        \
            SLIST_NEXT(SLIST_NEXT(elm, field), field);                  \
 } while (0)
@@ -213,6 +216,12 @@ struct {                                                           \
        SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);   \
 } while (0)
 
+#define SLIST_SWAP(head1, head2, type) do {                            \
+       struct type *swap_first = SLIST_FIRST(head1);                   \
+       SLIST_FIRST(head1) = SLIST_FIRST(head2);                        \
+       SLIST_FIRST(head2) = swap_first;                                \
+} while (0)
+
 /*
  * Singly-linked Tail queue declarations.
  */
@@ -288,6 +297,7 @@ struct {                                                            \
 #define        STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
 
 #define        STAILQ_REMOVE(head, elm, type, field) do {                      \
+       QMD_SAVELINK(oldnext, (elm)->field.stqe_next);                  \
        if (STAILQ_FIRST((head)) == (elm)) {                            \
                STAILQ_REMOVE_HEAD((head), field);                      \
        }                                                               \
@@ -295,9 +305,9 @@ struct {                                                            \
                struct type *curelm = STAILQ_FIRST((head));             \
                while (STAILQ_NEXT(curelm, field) != (elm))             \
                        curelm = STAILQ_NEXT(curelm, field);            \
-               STAILQ_REMOVE_NEXT(head, curelm, field);                \
+               STAILQ_REMOVE_AFTER(head, curelm, field);               \
        }                                                               \
-       TRASHIT((elm)->field.stqe_next);                                \
+       TRASHIT(*oldnext);                                              \
 } while (0)
 
 #define        STAILQ_REMOVE_HEAD(head, field) do {                            \
@@ -306,12 +316,26 @@ struct {                                                          \
                (head)->stqh_last = &STAILQ_FIRST((head));              \
 } while (0)
 
-#define STAILQ_REMOVE_NEXT(head, elm, field) do {                      \
+#define STAILQ_REMOVE_AFTER(head, elm, field) do {                     \
        if ((STAILQ_NEXT(elm, field) =                                  \
             STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)      \
                (head)->stqh_last = &STAILQ_NEXT((elm), field);         \
 } while (0)
 
+#define STAILQ_SWAP(head1, head2, type) do {                           \
+       struct type *swap_first = STAILQ_FIRST(head1);                  \
+       struct type **swap_last = (head1)->stqh_last;                   \
+       STAILQ_FIRST(head1) = STAILQ_FIRST(head2);                      \
+       (head1)->stqh_last = (head2)->stqh_last;                        \
+       STAILQ_FIRST(head2) = swap_first;                               \
+       (head2)->stqh_last = swap_last;                                 \
+       if (STAILQ_EMPTY(head1))                                        \
+               (head1)->stqh_last = &STAILQ_FIRST(head1);              \
+       if (STAILQ_EMPTY(head2))                                        \
+               (head2)->stqh_last = &STAILQ_FIRST(head2);              \
+} while (0)
+
+
 /*
  * List declarations.
  */
@@ -404,14 +428,26 @@ struct {                                                          \
 #define        LIST_NEXT(elm, field)   ((elm)->field.le_next)
 
 #define        LIST_REMOVE(elm, field) do {                                    \
+       QMD_SAVELINK(oldnext, (elm)->field.le_next);                    \
+       QMD_SAVELINK(oldprev, (elm)->field.le_prev);                    \
        QMD_LIST_CHECK_NEXT(elm, field);                                \
        QMD_LIST_CHECK_PREV(elm, field);                                \
        if (LIST_NEXT((elm), field) != NULL)                            \
                LIST_NEXT((elm), field)->field.le_prev =                \
                    (elm)->field.le_prev;                               \
        *(elm)->field.le_prev = LIST_NEXT((elm), field);                \
-       TRASHIT((elm)->field.le_next);                                  \
-       TRASHIT((elm)->field.le_prev);                                  \
+       TRASHIT(*oldnext);                                              \
+       TRASHIT(*oldprev);                                              \
+} while (0)
+
+#define LIST_SWAP(head1, head2, type, field) do {                      \
+       struct type *swap_tmp = LIST_FIRST((head1));                    \
+       LIST_FIRST((head1)) = LIST_FIRST((head2));                      \
+       LIST_FIRST((head2)) = swap_tmp;                                 \
+       if ((swap_tmp = LIST_FIRST((head1))) != NULL)                   \
+               swap_tmp->field.le_prev = &LIST_FIRST((head1));         \
+       if ((swap_tmp = LIST_FIRST((head2))) != NULL)                   \
+               swap_tmp->field.le_prev = &LIST_FIRST((head2));         \
 } while (0)
 
 /*
@@ -566,6 +602,8 @@ struct {                                                            \
        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 
 #define        TAILQ_REMOVE(head, elm, field) do {                             \
+       QMD_SAVELINK(oldnext, (elm)->field.tqe_next);                   \
+       QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);                   \
        QMD_TAILQ_CHECK_NEXT(elm, field);                               \
        QMD_TAILQ_CHECK_PREV(elm, field);                               \
        if ((TAILQ_NEXT((elm), field)) != NULL)                         \
@@ -576,9 +614,26 @@ struct {                                                           \
                QMD_TRACE_HEAD(head);                                   \
        }                                                               \
        *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);              \
-       TRASHIT((elm)->field.tqe_next);                                 \
-       TRASHIT((elm)->field.tqe_prev);                                 \
+       TRASHIT(*oldnext);                                              \
+       TRASHIT(*oldprev);                                              \
        QMD_TRACE_ELEM(&(elm)->field);                                  \
 } while (0)
 
+#define TAILQ_SWAP(head1, head2, type, field) do {                     \
+       struct type *swap_first = (head1)->tqh_first;                   \
+       struct type **swap_last = (head1)->tqh_last;                    \
+       (head1)->tqh_first = (head2)->tqh_first;                        \
+       (head1)->tqh_last = (head2)->tqh_last;                          \
+       (head2)->tqh_first = swap_first;                                \
+       (head2)->tqh_last = swap_last;                                  \
+       if ((swap_first = (head1)->tqh_first) != NULL)                  \
+               swap_first->field.tqe_prev = &(head1)->tqh_first;       \
+       else                                                            \
+               (head1)->tqh_last = &(head1)->tqh_first;                \
+       if ((swap_first = (head2)->tqh_first) != NULL)                  \
+               swap_first->field.tqe_prev = &(head2)->tqh_first;       \
+       else                                                            \
+               (head2)->tqh_last = &(head2)->tqh_first;                \
+} while (0)
+
 #endif /* !_SYS_QUEUE_H_ */