Sync sys/queue.h with FreeBSD:
authorPeter Avalos <pavalos@theshell.com>
Sun, 15 Mar 2009 06:58:33 +0000 (20:58 -1000)
committerPeter Avalos <pavalos@theshell.com>
Tue, 7 Apr 2009 07:09:45 +0000 (21:09 -1000)
* Introduce REMOVE_NEXT() macro's for SLIST and STAILQ.

* Add sanity checking for QUEUE(3) TAILQs and LISTs under
INVARIANTS.  Races may lead to list corruption, which can be
difficult to unravel in a post-mortem analysis.  These checks verify
that the prev and next pointers are consistent when inserting or
removing elements, thus catching any corruption earlier.

* Use TRASHIT to break LIST and SLIST link pointers on element removal.

* Add more _FOREACH_MUTABLEs. Note: FreeBSD and NetBSD call these _SAFE,
but _MUTABLE is a better name, so that's what we're using.

* Add a macro for SLIST traversal 'SLIST_FOREACH_PREVPTR',
this macro keeps a pointer to the previous element's next
pointer to allow for search and O(1) removal.

* Remove CIRCLEQs and replace them with TAILQs.

share/man/man3/queue.3
sys/dev/crypto/ubsec/ubsec.c
sys/dev/drm/drm_drv.c
sys/kern/subr_rman.c
sys/netgraph/ppp/ng_ppp.c
sys/sys/queue.h
sys/sys/rman.h

index 04623f4..b465f84 100644 (file)
 .\" SUCH DAMAGE.
 .\"
 .\"    @(#)queue.3     8.2 (Berkeley) 1/24/94
-.\" $FreeBSD: src/share/man/man3/queue.3,v 1.15.2.7 2001/12/18 10:09:02 ru Exp $
+.\" $FreeBSD: src/share/man/man3/queue.3,v 1.42 2008/05/22 14:40:03 ed Exp $
 .\" $DragonFly: src/share/man/man3/queue.3,v 1.8 2008/10/17 12:41:38 swildner Exp $
 .\"
-.Dd August 28, 2008
+.Dd March, 14, 2009
 .Dt QUEUE 3
 .Os
 .Sh NAME
@@ -41,6 +41,7 @@
 .Nm SLIST_ENTRY ,
 .Nm SLIST_FIRST ,
 .Nm SLIST_FOREACH ,
+.Nm SLIST_FOREACH_MUTABLE ,
 .Nm SLIST_HEAD ,
 .Nm SLIST_HEAD_INITIALIZER ,
 .Nm SLIST_INIT ,
@@ -48,6 +49,7 @@
 .Nm SLIST_INSERT_HEAD ,
 .Nm SLIST_NEXT ,
 .Nm SLIST_REMOVE_HEAD ,
+.Nm SLIST_REMOVE_NEXT ,
 .Nm SLIST_REMOVE ,
 .Nm STAILQ_CONCAT ,
 .Nm STAILQ_EMPTY ,
@@ -64,6 +66,7 @@
 .Nm STAILQ_LAST ,
 .Nm STAILQ_NEXT ,
 .Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_REMOVE_NEXT ,
 .Nm STAILQ_REMOVE ,
 .Nm LIST_EMPTY ,
 .Nm LIST_ENTRY ,
@@ -83,9 +86,9 @@
 .Nm TAILQ_ENTRY ,
 .Nm TAILQ_FIRST ,
 .Nm TAILQ_FOREACH ,
-.Nm TAILQ_FOREACH_SAFE ,
 .Nm TAILQ_FOREACH_MUTABLE ,
 .Nm TAILQ_FOREACH_REVERSE ,
+.Nm TAILQ_FOREACH_REVERSE_MUTABLE ,
 .Nm TAILQ_HEAD ,
 .Nm TAILQ_HEAD_INITIALIZER ,
 .Nm TAILQ_INIT ,
 .Nm TAILQ_LAST ,
 .Nm TAILQ_NEXT ,
 .Nm TAILQ_PREV ,
-.Nm TAILQ_REMOVE ,
-.Nm CIRCLEQ_EMPTY ,
-.Nm CIRCLEQ_ENTRY ,
-.Nm CIRCLEQ_FIRST ,
-.Nm CIRCLEQ_FOREACH ,
-.Nm CIRCLEQ_FOREACH_REVERSE ,
-.Nm CIRCLEQ_HEAD ,
-.Nm CIRCLEQ_HEAD_INITIALIZER ,
-.Nm CIRCLEQ_INIT ,
-.Nm CIRCLEQ_INSERT_AFTER ,
-.Nm CIRCLEQ_INSERT_BEFORE ,
-.Nm CIRCLEQ_INSERT_HEAD ,
-.Nm CIRCLEQ_INSERT_TAIL ,
-.Nm CIRCLEQ_LAST ,
-.Nm CIRCLEQ_NEXT ,
-.Nm CIRCLEQ_PREV ,
-.Nm CIRCLEQ_REMOVE
+.Nm TAILQ_REMOVE
 .Nd implementations of singly-linked lists, singly-linked tail queues,
-lists, tail queues, and circular queues
+lists and tail queues
 .Sh SYNOPSIS
 .In sys/queue.h
 .\"
@@ -122,6 +109,7 @@ lists, tail queues, and circular queues
 .Fn SLIST_ENTRY "TYPE"
 .Fn SLIST_FIRST "SLIST_HEAD *head"
 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_FOREACH_MUTABLE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
 .Fn SLIST_HEAD "HEADNAME" "TYPE"
 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
 .Fn SLIST_INIT "SLIST_HEAD *head"
@@ -129,6 +117,7 @@ lists, tail queues, and circular queues
 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_REMOVE_NEXT "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
 .\"
 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
@@ -136,7 +125,7 @@ lists, tail queues, and circular queues
 .Fn STAILQ_ENTRY "TYPE"
 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
-.Fn STAILQ_FOREACH_MUTABLE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE * temp_var"
+.Fn STAILQ_FOREACH_MUTABLE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
 .Fn STAILQ_INIT "STAILQ_HEAD *head"
@@ -146,6 +135,7 @@ lists, tail queues, and circular queues
 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
+.Fn STAILQ_REMOVE_NEXT "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
 .\"
 .Fn LIST_EMPTY "LIST_HEAD *head"
@@ -167,9 +157,9 @@ lists, tail queues, and circular queues
 .Fn TAILQ_ENTRY "TYPE"
 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
-.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 .Fn TAILQ_FOREACH_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
+.Fn TAILQ_FOREACH_REVERSE_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
 .Fn TAILQ_INIT "TAILQ_HEAD *head"
@@ -182,27 +172,10 @@ lists, tail queues, and circular queues
 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 .\"
-.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
-.Fn CIRCLEQ_ENTRY "TYPE"
-.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
-.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
-.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
-.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
-.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
-.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
-.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
-.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
-.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
-.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
-.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
-.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
-.Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
-.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
 .Sh DESCRIPTION
-These macros define and operate on five types of data structures:
-singly-linked lists, singly-linked tail queues, lists, tail queues,
-and circular queues.
-All five structures support the following functionality:
+These macros define and operate on four types of data structures:
+singly-linked lists, singly-linked tail queues, lists, and tail queues.
+All four structures support the following functionality:
 .Bl -enum -compact -offset indent
 .It
 Insertion of a new entry at the head of the list.
@@ -211,21 +184,29 @@ Insertion of a new entry after any element in the list.
 .It
 O(1) removal of an entry from the head of the list.
 .It
-O(n) removal of any entry in the list.
-.It
 Forward traversal through the list.
 .El
 .Pp
-Singly-linked lists are the simplest of the five data structures
+O(n) removal of any entry in the list.
+Singly-linked lists are the simplest of the four data structures
 and support only the above functionality.
 Singly-linked lists are ideal for applications with large datasets
 and few or no removals,
 or for implementing a LIFO queue.
+Singly-linked lists add the following functionality:
+.Bl -enum -compact -offset indent
+.It
+O(n) removal of any entry in the list.
+.El
 .Pp
 Singly-linked tail queues add the following functionality:
 .Bl -enum -compact -offset indent
 .It
 Entries can be added at the end of a list.
+.It
+O(n) removal of any entry in the list.
+.It
+They may be concatenated.
 .El
 However:
 .Bl -enum -compact -offset indent
@@ -242,8 +223,8 @@ Singly-linked tailqs are ideal for applications with large datasets and
 few or no removals,
 or for implementing a FIFO queue.
 .Pp
-All doubly linked types of data structures (lists, tail queues, and circle
-queues) additionally allow:
+All doubly linked types of data structures (lists and tail queues)
+additionally allow:
 .Bl -enum -compact -offset indent
 .It
 Insertion of a new entry before any element in the list.
@@ -268,6 +249,8 @@ Tail queues add the following functionality:
 Entries can be added at the end of a list.
 .It
 They may be traversed backwards, from tail to head.
+.It
+They may be concatenated.
 .El
 However:
 .Bl -enum -compact -offset indent
@@ -280,26 +263,6 @@ Code size is about 15% greater and operations run about 20% slower
 than singly-linked lists.
 .El
 .Pp
-Circular queues add the following functionality:
-.Bl -enum -compact -offset indent
-.It
-Entries can be added at the end of a list.
-.It
-They may be traversed backwards, from tail to head.
-.El
-However:
-.Bl -enum -compact -offset indent
-.It
-All list insertions and removals must specify the head of the list.
-.It
-Each head entry requires two pointers rather than one.
-.It
-The termination condition for traversal is more complex.
-.It
-Code size is about 40% greater and operations run about 45% slower
-than lists.
-.El
-.Pp
 In the macro definitions,
 .Fa TYPE
 is the name of a user defined structure,
@@ -307,9 +270,8 @@ that must contain a field of type
 .Li SLIST_ENTRY ,
 .Li STAILQ_ENTRY ,
 .Li LIST_ENTRY ,
-.Li TAILQ_ENTRY ,
 or
-.Li CIRCLEQ_ENTRY ,
+.Li TAILQ_ENTRY ,
 named
 .Fa NAME .
 The argument
@@ -319,9 +281,8 @@ using the macros
 .Li SLIST_HEAD ,
 .Li STAILQ_HEAD ,
 .Li LIST_HEAD ,
-.Li TAILQ_HEAD ,
 or
-.Li CIRCLEQ_HEAD .
+.Li TAILQ_HEAD .
 See the examples below for further explanation of how these
 macros are used.
 .Sh SINGLY-LINKED LISTS
@@ -384,6 +345,20 @@ turn to
 .Fa var .
 .Pp
 The macro
+.Nm SLIST_FOREACH_MUTABLE
+traverses the list referenced by
+.Fa head
+in the forward direction, assigning each element in
+turn to
+.Fa var .
+However, unlike
+.Fn SLIST_FOREACH
+here it is permitted to both remove
+.Fa var
+as well as free it from within the loop safely without interfering with the
+traversal.
+.Pp
+The macro
 .Nm SLIST_INIT
 initializes the list referenced by
 .Fa head .
@@ -417,6 +392,14 @@ this macro instead of the generic
 macro.
 .Pp
 The macro
+.Nm SLIST_REMOVE_NEXT
+removes the element after
+.Fa elm
+from the list. Unlike
+.Fa SLIST_REMOVE ,
+this macro does not traverse the entire list.
+.Pp
+The macro
 .Nm SLIST_REMOVE
 removes the element
 .Fa elm
@@ -449,6 +432,13 @@ free(n3);
                                        /* Forward traversal. */
 SLIST_FOREACH(np, &head, entries)
        np-> ...
+                                       /* Safe forward traversal. */
+SLIST_FOREACH_MUTABLE(np, &head, entries, np_temp) {
+       np->do_stuff();
+       ...
+       SLIST_REMOVE(&head, np, entry, entries);
+       free(np);
+}
 
 while (!SLIST_EMPTY(&head)) {          /* List Deletion. */
        n1 = SLIST_FIRST(&head);
@@ -534,7 +524,7 @@ in the forward direction, assigning each element
 in turn to
 .Fa var .
 However, unlike
-.Fa STAILQ_FOREACH
+.Fn STAILQ_FOREACH
 here it is permitted to both remove
 .Fa var
 as well as free it from within the loop safely without interfering with the
@@ -567,7 +557,8 @@ after the element
 The macro
 .Nm STAILQ_LAST
 returns the last item on the tail queue.
-If the tail queue is empty the return value is undefined.
+If the tail queue is empty the return value is
+.Dv NULL .
 .Pp
 The macro
 .Nm STAILQ_NEXT
@@ -583,6 +574,14 @@ use this macro explicitly rather than the generic
 macro.
 .Pp
 The macro
+.Nm STAILQ_REMOVE_NEXT
+removes the element after
+.Fa elm
+from the tail queue. Unlike
+.Fa STAILQ_REMOVE ,
+this macro does not traverse the entire tail queue.
+.Pp
+The macro
 .Nm STAILQ_REMOVE
 removes the element
 .Fa elm
@@ -618,6 +617,13 @@ free(n3);
                                        /* Forward traversal. */
 STAILQ_FOREACH(np, &head, entries)
        np-> ...
+                                       /* Safe forward traversal. */
+STAILQ_FOREACH_MUTABLE(np, &head, entries, np_temp) {
+       np->do_stuff();
+       ...
+       STAILQ_REMOVE(&head, np, entry, entries);
+       free(np);
+}
                                        /* TailQ Deletion. */
 while (!STAILQ_EMPTY(&head)) {
        n1 = STAILQ_FIRST(&head);
@@ -698,11 +704,12 @@ traverses the list referenced by
 .Fa head
 in the forward direction, assigning each element in turn to
 .Fa var .
-Unlike
-.Nm LIST_FOREACH ,
-it is permitted to remove
+However, unlike
+.Fn LIST_FOREACH
+here it is permitted to both remove
 .Fa var
-from the list without interfering with the traversal.
+as well as free it from within the loop safely without interfering with the
+traversal.
 .Pp
 The macro
 .Nm LIST_INIT
@@ -747,7 +754,7 @@ struct entry {
        ...
        LIST_ENTRY(entry) entries;      /* List. */
        ...
-} *n1, *n2, *n3, *np;
+} *n1, *n2, *n3, *np, *np_temp;
 
 LIST_INIT(&head);                      /* Initialize the list. */
 
@@ -766,6 +773,14 @@ free(n2);
 LIST_FOREACH(np, &head, entries)
        np-> ...
 
+                                       /* Safe forward traversal. */
+LIST_FOREACH_MUTABLE(np, &head, entries, np_temp) {
+       np->do_stuff();
+       ...
+       LIST_REMOVE(np, entries);
+       free(np);
+}
+
 while (!LIST_EMPTY(&head)) {           /* List Deletion. */
        n1 = LIST_FIRST(&head);
        LIST_REMOVE(n1, entries);
@@ -848,18 +863,10 @@ traverses the tail queue referenced by
 .Fa head
 in the forward direction, assigning each element in turn to
 .Fa var .
-.Pp
-The macro
-.Nm TAILQ_FOREACH_MUTABLE
-traverses the tail queue referenced by
-.Fa head
-in the forward direction, assigning each element in turn to
-.Fa var .
-Unlike
-.Nm TAILQ_FOREACH ,
-it is permitted to remove
 .Fa var
-from the tail queue without interfering with the traversal.
+is set to
+.Dv NULL
+if the loop completes normally, or if there were no elements.
 .Pp
 The macro
 .Nm TAILQ_FOREACH_REVERSE
@@ -868,16 +875,20 @@ traverses the tail queue referenced by
 in the reverse direction, assigning each element in turn to
 .Fa var .
 .Pp
-The macro
-.Nm TAILQ_FOREACH_SAFE
-traverses the list referenced by
+The macros
+.Nm TAILQ_FOREACH_MUTABLE
+and
+.Nm TAILQ_FOREACH_REVERSE_MUTABLE
+traverse the list referenced by
 .Fa head
-in the forward direction,
+in the forward or reverse direction respectively,
 assigning each element in turn to
 .Fa var .
-However, unlike its unsafe counterpart,
-.Nm TAILQ_FOREACH_SAVE
-permits to both remove
+However, unlike their unsafe counterparts,
+.Nm TAILQ_FOREACH
+and
+.Nm TAILQ_FOREACH_REVERSE
+permit to both remove
 .Fa var
 as well as free it from within the loop safely without interfering with the
 traversal.
@@ -916,7 +927,8 @@ before the element
 The macro
 .Nm TAILQ_LAST
 returns the last item on the tail queue.
-If the tail queue is empty the return value is undefined.
+If the tail queue is empty the return value is
+.Dv NULL .
 .Pp
 The macro
 .Nm TAILQ_NEXT
@@ -963,7 +975,7 @@ free(n2);
 TAILQ_FOREACH(np, &head, entries)
        np-> ...
                                        /* Safe forward traversal. */
-TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
+TAILQ_FOREACH_MUTABLE(np, &head, entries, np_temp) {
        np->do_stuff();
        ...
        TAILQ_REMOVE(&head, np, entries);
@@ -987,169 +999,6 @@ while (n1 != NULL) {
 }
 TAILQ_INIT(&head);
 .Ed
-.Sh CIRCULAR QUEUES
-A circular queue is headed by a structure defined by the
-.Nm CIRCLEQ_HEAD
-macro.
-This structure contains a pair of pointers,
-one to the first element in the circular queue and the other to the
-last element in the circular queue.
-The elements are doubly linked so that an arbitrary element can be
-removed without traversing the queue.
-New elements can be added to the queue after an existing element,
-before an existing element, at the head of the queue, or at the end
-of the queue.
-A
-.Fa CIRCLEQ_HEAD
-structure is declared as follows:
-.Bd -literal -offset indent
-CIRCLEQ_HEAD(HEADNAME, TYPE) head;
-.Ed
-.Pp
-where
-.Li HEADNAME
-is the name of the structure to be defined, and
-.Li TYPE
-is the type of the elements to be linked into the circular queue.
-A pointer to the head of the circular queue can later be declared as:
-.Bd -literal -offset indent
-struct HEADNAME *headp;
-.Ed
-.Pp
-(The names
-.Li head
-and
-.Li headp
-are user selectable.)
-.Pp
-The macro
-.Nm CIRCLEQ_HEAD_INITIALIZER
-evaluates to an initializer for the circle queue
-.Fa head .
-.Pp
-The macro
-.Nm CIRCLEQ_EMPTY
-evaluates to true if there are no items on the circle queue.
-.Pp
-The macro
-.Nm CIRCLEQ_ENTRY
-declares a structure that connects the elements in
-the circular queue.
-.Pp
-The macro
-.Nm CIRCLEQ_FIRST
-returns the first item on the circle queue.
-.Pp
-The macro
-.Nm CICRLEQ_FOREACH
-traverses the circle queue referenced by
-.Fa head
-in the forward direction, assigning each element in turn to
-.Fa var .
-.Pp
-The macro
-.Nm CICRLEQ_FOREACH_REVERSE
-traverses the circle queue referenced by
-.Fa head
-in the reverse direction, assigning each element in turn to
-.Fa var .
-.Pp
-The macro
-.Nm CIRCLEQ_INIT
-initializes the circular queue referenced by
-.Fa head .
-.Pp
-The macro
-.Nm CIRCLEQ_INSERT_HEAD
-inserts the new element
-.Fa elm
-at the head of the circular queue.
-.Pp
-The macro
-.Nm CIRCLEQ_INSERT_TAIL
-inserts the new element
-.Fa elm
-at the end of the circular queue.
-.Pp
-The macro
-.Nm CIRCLEQ_INSERT_AFTER
-inserts the new element
-.Fa elm
-after the element
-.Fa listelm .
-.Pp
-The macro
-.Nm CIRCLEQ_INSERT_BEFORE
-inserts the new element
-.Fa elm
-before the element
-.Fa listelm .
-.Pp
-The macro
-.Nm CIRCLEQ_LAST
-returns the last item on the circle queue.
-.Pp
-The macro
-.Nm CIRCLEQ_NEXT
-returns the next item on the circle queue.
-.Pp
-The macro
-.Nm CIRCLEQ_PREV
-returns the previous item on the circle queue.
-.Pp
-The macro
-.Nm CIRCLEQ_REMOVE
-removes the element
-.Fa elm
-from the circular queue.
-.Sh CIRCULAR QUEUE EXAMPLE
-.Bd -literal
-CIRCLEQ_HEAD(circlehead, entry) head =
-    CIRCLEQ_HEAD_INITIALIZER(head);
-struct circlehead *headp;              /* Circular queue head. */
-struct entry {
-       ...
-       CIRCLEQ_ENTRY(entry) entries;   /* Circular queue. */
-       ...
-} *n1, *n2, *np;
-
-CIRCLEQ_INIT(&head);                   /* Initialize the circular queue. */
-
-n1 = malloc(sizeof(struct entry));     /* Insert at the head. */
-CIRCLEQ_INSERT_HEAD(&head, n1, entries);
-
-n1 = malloc(sizeof(struct entry));     /* Insert at the tail. */
-CIRCLEQ_INSERT_TAIL(&head, n1, entries);
-
-n2 = malloc(sizeof(struct entry));     /* Insert after. */
-CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
-
-n2 = malloc(sizeof(struct entry));     /* Insert before. */
-CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
-
-CIRCLEQ_REMOVE(&head, n1, entries);    /* Deletion. */
-free(n1);
-                                       /* Forward traversal. */
-CIRCLEQ_FOREACH(np, &head, entries)
-       np-> ...
-                                       /* Reverse traversal. */
-CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
-       np-> ...
-                                       /* CircleQ Deletion. */
-while (CIRCLEQ_FIRST(&head) != (void *)&head) {
-       n1 = CIRCLEQ_HEAD(&head);
-       CIRCLEQ_REMOVE(&head, n1, entries);
-       free(n1);
-}
-                                       /* Faster CircleQ Deletion. */
-n1 = CIRCLEQ_FIRST(&head);
-while (n1 != (void *)&head) {
-       n2 = CIRCLEQ_NEXT(n1, entries);
-       free(n1);
-       n1 = n2;
-}
-CIRCLEQ_INIT(&head);
-.Ed
 .Sh HISTORY
 The
 .Nm queue
index f26d7b7..eab7705 100644 (file)
@@ -81,7 +81,7 @@
 #define        SIMPLEQ_INSERT_TAIL     STAILQ_INSERT_TAIL
 #define        SIMPLEQ_EMPTY           STAILQ_EMPTY
 #define        SIMPLEQ_FIRST           STAILQ_FIRST
-#define        SIMPLEQ_REMOVE_HEAD     STAILQ_REMOVE_HEAD_UNTIL
+#define        SIMPLEQ_REMOVE_HEAD     STAILQ_REMOVE_HEAD
 #define        SIMPLEQ_FOREACH         STAILQ_FOREACH
 /* ditto for endian.h */
 #define        letoh16(x)              le16toh(x)
@@ -512,7 +512,7 @@ ubsec_detach(device_t dev)
                struct ubsec_q *q;
 
                q = SIMPLEQ_FIRST(&sc->sc_freequeue);
-               SIMPLEQ_REMOVE_HEAD(&sc->sc_freequeue, q, q_next);
+               SIMPLEQ_REMOVE_HEAD(&sc->sc_freequeue, q_next);
                ubsec_dma_free(sc, &q->q_dma->d_alloc);
                kfree(q, M_DEVBUF);
        }
@@ -609,7 +609,7 @@ ubsec_intr(void *arg)
                        if ((dmap->d_dma->d_mcr.mcr_flags & htole16(UBS_MCR_DONE)) == 0)
                                break;
 
-                       SIMPLEQ_REMOVE_HEAD(&sc->sc_qchip, q, q_next);
+                       SIMPLEQ_REMOVE_HEAD(&sc->sc_qchip, q_next);
 
                        npkts = q->q_nstacked_mcrs;
                        sc->sc_nqchip -= 1+npkts;
@@ -656,7 +656,7 @@ ubsec_intr(void *arg)
                                    BUS_DMASYNC_PREREAD|BUS_DMASYNC_PREWRITE);
                                break;
                        }
-                       SIMPLEQ_REMOVE_HEAD(&sc->sc_qchip2, q2, q_next);
+                       SIMPLEQ_REMOVE_HEAD(&sc->sc_qchip2, q_next);
                        ubsec_callback2(sc, q2);
                        /*
                         * Don't send any more packet to chip if there has been
@@ -754,7 +754,7 @@ ubsec_feed(struct ubsec_softc *sc)
 #endif /* UBSEC_DEBUG */
 
        q = SIMPLEQ_FIRST(&sc->sc_queue);
-       SIMPLEQ_REMOVE_HEAD(&sc->sc_queue, q, q_next);
+       SIMPLEQ_REMOVE_HEAD(&sc->sc_queue, q_next);
        --sc->sc_nqueue;
 
        bus_dmamap_sync(sc->sc_dmat, q->q_src_map, BUS_DMASYNC_PREWRITE);
@@ -770,7 +770,7 @@ ubsec_feed(struct ubsec_softc *sc)
                if (q2->q_dst_map != NULL)
                        bus_dmamap_sync(sc->sc_dmat, q2->q_dst_map,
                            BUS_DMASYNC_PREREAD);
-               SIMPLEQ_REMOVE_HEAD(&sc->sc_queue, q2, q_next);
+               SIMPLEQ_REMOVE_HEAD(&sc->sc_queue, q_next);
                --sc->sc_nqueue;
 
                v = (void*)(((char *)&q2->q_dma->d_dma->d_mcr) + sizeof(struct ubsec_mcr) -
@@ -806,7 +806,7 @@ feed1:
                      q, (u_int32_t)vtophys(&q->q_dma->d_dma->d_mcr),
                      stat);
 #endif /* UBSEC_DEBUG */
-       SIMPLEQ_REMOVE_HEAD(&sc->sc_queue, q, q_next);
+       SIMPLEQ_REMOVE_HEAD(&sc->sc_queue, q_next);
        --sc->sc_nqueue;
        SIMPLEQ_INSERT_TAIL(&sc->sc_qchip, q, q_next);
        sc->sc_nqchip++;
@@ -1024,7 +1024,7 @@ ubsec_process(void *arg, struct cryptop *crp, int hint)
                return (ERESTART);
        }
        q = SIMPLEQ_FIRST(&sc->sc_freequeue);
-       SIMPLEQ_REMOVE_HEAD(&sc->sc_freequeue, q, q_next);
+       SIMPLEQ_REMOVE_HEAD(&sc->sc_freequeue, q_next);
        crit_exit();
 
        dmap = q->q_dma; /* Save dma pointer */
@@ -1648,7 +1648,7 @@ ubsec_feed2(struct ubsec_softc *sc)
                ubsec_dma_sync(&q->q_ctx, BUS_DMASYNC_PREWRITE);
 
                WRITE_REG(sc, BS_MCR2, q->q_mcr.dma_paddr);
-               SIMPLEQ_REMOVE_HEAD(&sc->sc_queue2, q, q_next);
+               SIMPLEQ_REMOVE_HEAD(&sc->sc_queue2, q_next);
                --sc->sc_nqueue2;
                SIMPLEQ_INSERT_TAIL(&sc->sc_qchip2, q, q_next);
        }
@@ -1972,7 +1972,7 @@ ubsec_cleanchip(struct ubsec_softc *sc)
 
        while (!SIMPLEQ_EMPTY(&sc->sc_qchip)) {
                q = SIMPLEQ_FIRST(&sc->sc_qchip);
-               SIMPLEQ_REMOVE_HEAD(&sc->sc_qchip, q, q_next);
+               SIMPLEQ_REMOVE_HEAD(&sc->sc_qchip, q_next);
                ubsec_free_q(sc, q);
        }
        sc->sc_nqchip = 0;
@@ -2097,7 +2097,7 @@ ubsec_kprocess(void *arg, struct cryptkop *krp, int hint)
                struct ubsec_q2 *q;
 
                q = SIMPLEQ_FIRST(&sc->sc_q2free);
-               SIMPLEQ_REMOVE_HEAD(&sc->sc_q2free, q, q_next);
+               SIMPLEQ_REMOVE_HEAD(&sc->sc_q2free, q_next);
                ubsec_kfree(sc, q);
        }
 
index 482990b..fab7805 100644 (file)
@@ -397,7 +397,7 @@ static int drm_lastclose(struct drm_device *dev)
                dev->sg = NULL;
        }
 
-       TAILQ_FOREACH_SAFE(map, &dev->maplist, link, mapsave) {
+       TAILQ_FOREACH_MUTABLE(map, &dev->maplist, link, mapsave) {
                if (!(map->flags & _DRM_DRIVER))
                        drm_rmmap(dev, map);
        }
index 933d134..2ff224f 100644 (file)
@@ -83,8 +83,6 @@ static        int int_rman_activate_resource(struct rman *rm, struct resource *r,
 static int int_rman_deactivate_resource(struct resource *r);
 static int int_rman_release_resource(struct rman *rm, struct resource *r);
 
-#define        CIRCLEQ_TERMCOND(var, head)     (var == (void *)&(head))
-
 int
 rman_init(struct rman *rm)
 {
@@ -102,7 +100,7 @@ rman_init(struct rman *rm)
        if (rm->rm_type == RMAN_GAUGE)
                panic("implement RMAN_GAUGE");
 
-       CIRCLEQ_INIT(&rm->rm_list);
+       TAILQ_INIT(&rm->rm_list);
        rm->rm_slock = kmalloc(sizeof *rm->rm_slock, M_RMAN, M_NOWAIT);
        if (rm->rm_slock == NULL)
                return ENOMEM;
@@ -137,16 +135,15 @@ rman_manage_region(struct rman *rm, u_long start, u_long end)
        r->r_rm = rm;
 
        lwkt_gettoken(&ilock, rm->rm_slock);
-       for (s = CIRCLEQ_FIRST(&rm->rm_list);   
-            !CIRCLEQ_TERMCOND(s, rm->rm_list) && s->r_end < r->r_start;
-            s = CIRCLEQ_NEXT(s, r_link))
+       for (s = TAILQ_FIRST(&rm->rm_list);
+            s && s->r_end < r->r_start;
+            s = TAILQ_NEXT(s, r_link))
                ;
 
-       if (CIRCLEQ_TERMCOND(s, rm->rm_list)) {
-               CIRCLEQ_INSERT_TAIL(&rm->rm_list, r, r_link);
-       } else {
-               CIRCLEQ_INSERT_BEFORE(&rm->rm_list, s, r, r_link);
-       }
+       if (s == NULL)
+               TAILQ_INSERT_TAIL(&rm->rm_list, r, r_link);
+       else
+               TAILQ_INSERT_BEFORE(s, r, r_link);
 
        lwkt_reltoken(&ilock);
        return 0;
@@ -159,7 +156,7 @@ rman_fini(struct rman *rm)
        lwkt_tokref ilock;
 
        lwkt_gettoken(&ilock, rm->rm_slock);
-       CIRCLEQ_FOREACH(r, &rm->rm_list, r_link) {
+       TAILQ_FOREACH(r, &rm->rm_list, r_link) {
                if (r->r_flags & RF_ALLOCATED) {
                        lwkt_reltoken(&ilock);
                        return EBUSY;
@@ -170,9 +167,9 @@ rman_fini(struct rman *rm)
         * There really should only be one of these if we are in this
         * state and the code is working properly, but it can't hurt.
         */
-       while (!CIRCLEQ_EMPTY(&rm->rm_list)) {
-               r = CIRCLEQ_FIRST(&rm->rm_list);
-               CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
+       while (!TAILQ_EMPTY(&rm->rm_list)) {
+               r = TAILQ_FIRST(&rm->rm_list);
+               TAILQ_REMOVE(&rm->rm_list, r, r_link);
                kfree(r, M_RMAN);
        }
        lwkt_reltoken(&ilock);
@@ -205,12 +202,12 @@ rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
 
        lwkt_gettoken(&ilock, rm->rm_slock);
 
-       for (r = CIRCLEQ_FIRST(&rm->rm_list); 
-            !CIRCLEQ_TERMCOND(r, rm->rm_list) && r->r_end < start;
-            r = CIRCLEQ_NEXT(r, r_link))
+       for (r = TAILQ_FIRST(&rm->rm_list);
+            r && r->r_end < start;
+            r = TAILQ_NEXT(r, r_link))
                ;
 
-       if (CIRCLEQ_TERMCOND(r, rm->rm_list)) {
+       if (r == NULL) {
                DPRINTF(("could not find a region\n"));
                goto out;
        }
@@ -218,8 +215,7 @@ rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
        /*
         * First try to find an acceptable totally-unshared region.
         */
-       for (s = r; !CIRCLEQ_TERMCOND(s, rm->rm_list);
-            s = CIRCLEQ_NEXT(s, r_link)) {
+       for (s = r; s; s = TAILQ_NEXT(s, r_link)) {
                DPRINTF(("considering [%#lx, %#lx]\n", s->r_start, s->r_end));
                if (s->r_start > end) {
                        DPRINTF(("s->r_start (%#lx) > end (%#lx)\n",
@@ -291,9 +287,9 @@ rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
                                r->r_sharehead = 0;
                                r->r_rm = rm;
                                s->r_end = rv->r_start - 1;
-                               CIRCLEQ_INSERT_AFTER(&rm->rm_list, s, rv,
+                               TAILQ_INSERT_AFTER(&rm->rm_list, s, rv,
                                                     r_link);
-                               CIRCLEQ_INSERT_AFTER(&rm->rm_list, rv, r,
+                               TAILQ_INSERT_AFTER(&rm->rm_list, rv, r,
                                                     r_link);
                        } else if (s->r_start == rv->r_start) {
                                DPRINTF(("allocating from the beginning\n"));
@@ -301,15 +297,14 @@ rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
                                 * We are allocating at the beginning.
                                 */
                                s->r_start = rv->r_end + 1;
-                               CIRCLEQ_INSERT_BEFORE(&rm->rm_list, s, rv,
-                                                     r_link);
+                               TAILQ_INSERT_BEFORE(s, rv, r_link);
                        } else {
                                DPRINTF(("allocating at the end\n"));
                                /*
                                 * We are allocating at the end.
                                 */
                                s->r_end = rv->r_start - 1;
-                               CIRCLEQ_INSERT_AFTER(&rm->rm_list, s, rv,
+                               TAILQ_INSERT_AFTER(&rm->rm_list, s, rv,
                                                     r_link);
                        }
                        goto out;
@@ -328,8 +323,7 @@ rman_reserve_resource(struct rman *rm, u_long start, u_long end, u_long count,
        if ((flags & (RF_SHAREABLE | RF_TIMESHARE)) == 0)
                goto out;
 
-       for (s = r; !CIRCLEQ_TERMCOND(s, rm->rm_list);
-            s = CIRCLEQ_NEXT(s, r_link)) {
+       for (s = r; s; s = TAILQ_NEXT(s, r_link)) {
                if (s->r_start > end)
                        break;
                if ((s->r_flags & flags) != flags)
@@ -528,8 +522,8 @@ int_rman_release_resource(struct rman *rm, struct resource *r)
                s = LIST_FIRST(r->r_sharehead);
                if (r->r_flags & RF_FIRSTSHARE) {
                        s->r_flags |= RF_FIRSTSHARE;
-                       CIRCLEQ_INSERT_BEFORE(&rm->rm_list, r, s, r_link);
-                       CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
+                       TAILQ_INSERT_BEFORE(r, s, r_link);
+                       TAILQ_REMOVE(&rm->rm_list, r, r_link);
                }
 
                /*
@@ -548,32 +542,30 @@ int_rman_release_resource(struct rman *rm, struct resource *r)
         * Look at the adjacent resources in the list and see if our
         * segment can be merged with any of them.
         */
-       s = CIRCLEQ_PREV(r, r_link);
-       t = CIRCLEQ_NEXT(r, r_link);
+       s = TAILQ_PREV(r, resource_head, r_link);
+       t = TAILQ_NEXT(r, r_link);
 
-       if (s != (void *)&rm->rm_list && (s->r_flags & RF_ALLOCATED) == 0
-           && t != (void *)&rm->rm_list && (t->r_flags & RF_ALLOCATED) == 0) {
+       if (s != NULL && (s->r_flags & RF_ALLOCATED) == 0
+           && t != NULL && (t->r_flags & RF_ALLOCATED) == 0) {
                /*
                 * Merge all three segments.
                 */
                s->r_end = t->r_end;
-               CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
-               CIRCLEQ_REMOVE(&rm->rm_list, t, r_link);
+               TAILQ_REMOVE(&rm->rm_list, r, r_link);
+               TAILQ_REMOVE(&rm->rm_list, t, r_link);
                kfree(t, M_RMAN);
-       } else if (s != (void *)&rm->rm_list
-                  && (s->r_flags & RF_ALLOCATED) == 0) {
+       } else if (s != NULL && (s->r_flags & RF_ALLOCATED) == 0) {
                /*
                 * Merge previous segment with ours.
                 */
                s->r_end = r->r_end;
-               CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
-       } else if (t != (void *)&rm->rm_list
-                  && (t->r_flags & RF_ALLOCATED) == 0) {
+               TAILQ_REMOVE(&rm->rm_list, r, r_link);
+       } else if (t != NULL && (t->r_flags & RF_ALLOCATED) == 0) {
                /*
                 * Merge next segment with ours.
                 */
                t->r_start = r->r_start;
-               CIRCLEQ_REMOVE(&rm->rm_list, r, r_link);
+               TAILQ_REMOVE(&rm->rm_list, r, r_link);
        } else {
                /*
                 * At this point, we know there is nothing we
@@ -678,7 +670,7 @@ sysctl_rman(SYSCTL_HANDLER_ARGS)
        /*
         * Find the indexed resource and return it.
         */
-       CIRCLEQ_FOREACH(res, &rm->rm_list, r_link) {
+       TAILQ_FOREACH(res, &rm->rm_list, r_link) {
                if (res_idx-- == 0) {
                        ures.r_handle = (uintptr_t)res;
                        ures.r_parent = (uintptr_t)res->r_rm;
index e0e30c7..7b09d6b 100644 (file)
@@ -136,7 +136,7 @@ struct ng_ppp_frag {
        struct timeval                  timestamp;      /* time of reception */
        struct mbuf                     *data;          /* Fragment data */
        meta_p                          meta;           /* Fragment meta */
-       CIRCLEQ_ENTRY(ng_ppp_frag)      f_qent;         /* Fragment queue */
+       TAILQ_ENTRY(ng_ppp_frag)        f_qent;         /* Fragment queue */
 };
 
 /* We use integer indicies to refer to the non-link hooks */
@@ -200,7 +200,7 @@ struct ng_ppp_private {
        int                     activeLinks[NG_PPP_MAX_LINKS];  /* indicies */
        u_int                   lastLink;               /* for round robin */
        hook_p                  hooks[HOOK_INDEX_MAX];  /* non-link hooks */
-       CIRCLEQ_HEAD(ng_ppp_fraglist, ng_ppp_frag)      /* fragment queue */
+       TAILQ_HEAD(ng_ppp_fraglist, ng_ppp_frag)        /* fragment queue */
                                frags;
        int                     qlen;                   /* fraq queue length */
        struct callout          fragTimer;              /* fraq queue check */
@@ -397,7 +397,7 @@ ng_ppp_constructor(node_p *nodep)
        (*nodep)->private = priv;
 
        /* Initialize state */
-       CIRCLEQ_INIT(&priv->frags);
+       TAILQ_INIT(&priv->frags);
        for (i = 0; i < NG_PPP_MAX_LINKS; i++)
                priv->links[i].seq = MP_NOSEQ;
        callout_init(&priv->fragTimer);
@@ -1142,10 +1142,10 @@ ng_ppp_mp_input(node_p node, int linkNum, struct mbuf *m, meta_p meta)
 
        /* Add fragment to queue, which is sorted by sequence number */
        inserted = 0;
-       CIRCLEQ_FOREACH_REVERSE(qent, &priv->frags, f_qent) {
+       TAILQ_FOREACH_REVERSE(qent, &priv->frags, ng_ppp_fraglist, f_qent) {
                diff = MP_RECV_SEQ_DIFF(priv, frag->seq, qent->seq);
                if (diff > 0) {
-                       CIRCLEQ_INSERT_AFTER(&priv->frags, qent, frag, f_qent);
+                       TAILQ_INSERT_AFTER(&priv->frags, qent, frag, f_qent);
                        inserted = 1;
                        break;
                } else if (diff == 0) {      /* should never happen! */
@@ -1156,7 +1156,7 @@ ng_ppp_mp_input(node_p node, int linkNum, struct mbuf *m, meta_p meta)
                }
        }
        if (!inserted)
-               CIRCLEQ_INSERT_HEAD(&priv->frags, frag, f_qent);
+               TAILQ_INSERT_HEAD(&priv->frags, frag, f_qent);
        priv->qlen++;
 
        /* Process the queue */
@@ -1175,18 +1175,18 @@ ng_ppp_check_packet(node_p node)
        struct ng_ppp_frag *qent, *qnext;
 
        /* Check for empty queue */
-       if (CIRCLEQ_EMPTY(&priv->frags))
+       if (TAILQ_EMPTY(&priv->frags))
                return (0);
 
        /* Check first fragment is the start of a deliverable packet */
-       qent = CIRCLEQ_FIRST(&priv->frags);
+       qent = TAILQ_FIRST(&priv->frags);
        if (!qent->first || MP_RECV_SEQ_DIFF(priv, qent->seq, priv->mseq) > 1)
                return (0);
 
        /* Check that all the fragments are there */
        while (!qent->last) {
-               qnext = CIRCLEQ_NEXT(qent, f_qent);
-               if (qnext == (void *)&priv->frags)      /* end of queue */
+               qnext = TAILQ_NEXT(qent, f_qent);
+               if (qnext == NULL)      /* end of queue */
                        return (0);
                if (qnext->seq != MP_NEXT_RECV_SEQ(priv, qent->seq))
                        return (0);
@@ -1208,14 +1208,14 @@ ng_ppp_get_packet(node_p node, struct mbuf **mp, meta_p *metap)
        struct ng_ppp_frag *qent, *qnext;
        struct mbuf *m = NULL, *tail;
 
-       qent = CIRCLEQ_FIRST(&priv->frags);
-       KASSERT(!CIRCLEQ_EMPTY(&priv->frags) && qent->first,
+       qent = TAILQ_FIRST(&priv->frags);
+       KASSERT(!TAILQ_EMPTY(&priv->frags) && qent->first,
            ("%s: no packet", __func__));
        for (tail = NULL; qent != NULL; qent = qnext) {
-               qnext = CIRCLEQ_NEXT(qent, f_qent);
-               KASSERT(!CIRCLEQ_EMPTY(&priv->frags),
+               qnext = TAILQ_NEXT(qent, f_qent);
+               KASSERT(!TAILQ_EMPTY(&priv->frags),
                    ("%s: empty q", __func__));
-               CIRCLEQ_REMOVE(&priv->frags, qent, f_qent);
+               TAILQ_REMOVE(&priv->frags, qent, f_qent);
                if (tail == NULL) {
                        tail = m = qent->data;
                        *metap = qent->meta;    /* inherit first frag's meta */
@@ -1251,15 +1251,15 @@ ng_ppp_frag_trim(node_p node)
                int dead = 0;
 
                /* If queue is empty, we're done */
-               if (CIRCLEQ_EMPTY(&priv->frags))
+               if (TAILQ_EMPTY(&priv->frags))
                        break;
 
                /* Determine whether first fragment can ever be completed */
-               CIRCLEQ_FOREACH(qent, &priv->frags, f_qent) {
+               TAILQ_FOREACH(qent, &priv->frags, f_qent) {
                        if (MP_RECV_SEQ_DIFF(priv, qent->seq, priv->mseq) >= 0)
                                break;
-                       qnext = CIRCLEQ_NEXT(qent, f_qent);
-                       KASSERT(qnext != (void*)&priv->frags,
+                       qnext = TAILQ_NEXT(qent, f_qent);
+                       KASSERT(qnext != NULL,
                            ("%s: last frag < MSEQ?", __func__));
                        if (qnext->seq != MP_NEXT_RECV_SEQ(priv, qent->seq)
                            || qent->last || qnext->first) {
@@ -1271,11 +1271,11 @@ ng_ppp_frag_trim(node_p node)
                        break;
 
                /* Remove fragment and all others in the same packet */
-               while ((qent = CIRCLEQ_FIRST(&priv->frags)) != qnext) {
-                       KASSERT(!CIRCLEQ_EMPTY(&priv->frags),
+               while ((qent = TAILQ_FIRST(&priv->frags)) != qnext) {
+                       KASSERT(!TAILQ_EMPTY(&priv->frags),
                            ("%s: empty q", __func__));
                        priv->bundleStats.dropFragments++;
-                       CIRCLEQ_REMOVE(&priv->frags, qent, f_qent);
+                       TAILQ_REMOVE(&priv->frags, qent, f_qent);
                        NG_FREE_DATA(qent->data, qent->meta);
                        FREE(qent, M_NETGRAPH);
                        priv->qlen--;
@@ -1318,9 +1318,9 @@ ng_ppp_frag_process(node_p node)
                int i;
 
                /* Get oldest fragment */
-               KASSERT(!CIRCLEQ_EMPTY(&priv->frags),
+               KASSERT(!TAILQ_EMPTY(&priv->frags),
                    ("%s: empty q", __func__));
-               qent = CIRCLEQ_FIRST(&priv->frags);
+               qent = TAILQ_FIRST(&priv->frags);
 
                /* Bump MSEQ if necessary */
                if (MP_RECV_SEQ_DIFF(priv, priv->mseq, qent->seq) < 0) {
@@ -1337,7 +1337,7 @@ ng_ppp_frag_process(node_p node)
 
                /* Drop it */
                priv->bundleStats.dropFragments++;
-               CIRCLEQ_REMOVE(&priv->frags, qent, f_qent);
+               TAILQ_REMOVE(&priv->frags, qent, f_qent);
                NG_FREE_DATA(qent->data, qent->meta);
                FREE(qent, M_NETGRAPH);
                priv->qlen--;
@@ -1377,13 +1377,13 @@ ng_ppp_frag_checkstale(node_p node)
        while (1) {
 
                /* If queue is empty, we're done */
-               if (CIRCLEQ_EMPTY(&priv->frags))
+               if (TAILQ_EMPTY(&priv->frags))
                        break;
 
                /* Find the first complete packet in the queue */
                beg = end = NULL;
-               seq = CIRCLEQ_FIRST(&priv->frags)->seq;
-               CIRCLEQ_FOREACH(qent, &priv->frags, f_qent) {
+               seq = TAILQ_FIRST(&priv->frags)->seq;
+               TAILQ_FOREACH(qent, &priv->frags, f_qent) {
                        if (qent->first)
                                beg = qent;
                        else if (qent->seq != seq)
@@ -1410,11 +1410,11 @@ ng_ppp_frag_checkstale(node_p node)
                        break;
 
                /* Throw away junk fragments in front of the completed packet */
-               while ((qent = CIRCLEQ_FIRST(&priv->frags)) != beg) {
-                       KASSERT(!CIRCLEQ_EMPTY(&priv->frags),
+               while ((qent = TAILQ_FIRST(&priv->frags)) != beg) {
+                       KASSERT(!TAILQ_EMPTY(&priv->frags),
                            ("%s: empty q", __func__));
                        priv->bundleStats.dropFragments++;
-                       CIRCLEQ_REMOVE(&priv->frags, qent, f_qent);
+                       TAILQ_REMOVE(&priv->frags, qent, f_qent);
                        NG_FREE_DATA(qent->data, qent->meta);
                        FREE(qent, M_NETGRAPH);
                        priv->qlen--;
@@ -2003,13 +2003,12 @@ ng_ppp_frag_reset(node_p node)
        const priv_p priv = node->private;
        struct ng_ppp_frag *qent, *qnext;
 
-       for (qent = CIRCLEQ_FIRST(&priv->frags);
-           qent != (void *)&priv->frags; qent = qnext) {
-               qnext = CIRCLEQ_NEXT(qent, f_qent);
+       for (qent = TAILQ_FIRST(&priv->frags); qent; qent = qnext) {
+               qnext = TAILQ_NEXT(qent, f_qent);
                NG_FREE_DATA(qent->data, qent->meta);
                FREE(qent, M_NETGRAPH);
        }
-       CIRCLEQ_INIT(&priv->frags);
+       TAILQ_INIT(&priv->frags);
        priv->qlen = 0;
 }
 
index c9761ce..c7171fe 100644 (file)
@@ -1,4 +1,4 @@
-/*
+/*-
  * Copyright (c) 1991, 1993
  *     The Regents of the University of California.  All rights reserved.
  *
  * 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. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *     This product includes software developed by the University of
- *     California, Berkeley and 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.
  * SUCH DAMAGE.
  *
  *     @(#)queue.h     8.5 (Berkeley) 8/20/94
- * $FreeBSD: src/sys/sys/queue.h,v 1.32.2.7 2002/04/17 14:21:02 des Exp $
+ * $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 $
  */
 
 #ifndef _SYS_QUEUE_H_
 #define        _SYS_QUEUE_H_
 
-#ifndef _MACHINE_STDINT_H_
-#include <machine/stdint.h>    /* for __offsetof */
-#endif
+#include <sys/cdefs.h>
 
 /*
- * This file defines five types of data structures: singly-linked lists,
- * singly-linked tail queues, lists, tail queues, and circular queues.
+ * This file defines four types of data structures: singly-linked lists,
+ * singly-linked tail queues, lists and tail 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
  * 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.
  *
- * 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
- * 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 circle queue may be traversed in either direction, but has a more
- * complex end of list detection.
- *
  * For details on the use of these macros, see the queue(3) manual page.
  *
  *
- *                     SLIST   LIST    STAILQ  TAILQ   CIRCLEQ
- * _HEAD               +       +       +       +       +
- * _HEAD_INITIALIZER   +       +       +       +       +
- * _ENTRY              +       +       +       +       +
- * _INIT               +       +       +       +       +
- * _EMPTY              +       +       +       +       +
- * _FIRST              +       +       +       +       +
- * _NEXT               +       +       +       +       +
- * _PREV               -       -       -       +       +
- * _LAST               -       -       +       +       +
- * _FOREACH            +       +       +       +       +
- * _FOREACH_MUTABLE    -       +       +       +       -
- * _FOREACH_REVERSE    -       -       -       +       +
- * _INSERT_HEAD                +       +       +       +       +
- * _INSERT_BEFORE      -       +       -       +       +
- * _INSERT_AFTER       +       +       +       +       +
- * _INSERT_TAIL                -       -       +       +       +
- * _CONCAT             -       -       +       +       -
- * _REMOVE_HEAD                +       -       +       -       -
- * _REMOVE             +       +       +       +       +
+ *                             SLIST   LIST    STAILQ  TAILQ
+ * _HEAD                       +       +       +       +
+ * _HEAD_INITIALIZER           +       +       +       +
+ * _ENTRY                      +       +       +       +
+ * _INIT                       +       +       +       +
+ * _EMPTY                      +       +       +       +
+ * _FIRST                      +       +       +       +
+ * _NEXT                       +       +       +       +
+ * _PREV                       -       -       -       +
+ * _LAST                       -       -       +       +
+ * _FOREACH                    +       +       +       +
+ * _FOREACH_MUTABLE            +       +       +       +
+ * _FOREACH_REVERSE            -       -       -       +
+ * _FOREACH_REVERSE_MUTABLE    -       -       -       +
+ * _INSERT_HEAD                        +       +       +       +
+ * _INSERT_BEFORE              -       +       -       +
+ * _INSERT_AFTER               +       +       +       +
+ * _INSERT_TAIL                        -       -       +       +
+ * _CONCAT                     -       -       +       +
+ * _REMOVE_HEAD                        +       -       +       -
+ * _REMOVE_NEXT                        +       -       +       -
+ * _REMOVE                     +       +       +       +
  *
  */
+#ifdef QUEUE_MACRO_DEBUG
+/* Store the last 2 places the queue element or head was altered */
+struct qm_trace {
+       char    *lastfile;
+       int      lastline;
+       char    *prevfile;
+       int      prevline;
+};
+
+#define        TRACEBUF        struct qm_trace trace;
+#define        TRASHIT(x)      do {(x) = (void *)-1;} while (0)
+
+#define        QMD_TRACE_HEAD(head) do {                                       \
+       (head)->trace.prevline = (head)->trace.lastline;                \
+       (head)->trace.prevfile = (head)->trace.lastfile;                \
+       (head)->trace.lastline = __LINE__;                              \
+       (head)->trace.lastfile = __FILE__;                              \
+} while (0)
+
+#define        QMD_TRACE_ELEM(elem) do {                                       \
+       (elem)->trace.prevline = (elem)->trace.lastline;                \
+       (elem)->trace.prevfile = (elem)->trace.lastfile;                \
+       (elem)->trace.lastline = __LINE__;                              \
+       (elem)->trace.lastfile = __FILE__;                              \
+} while (0)
+
+#else
+#define        QMD_TRACE_ELEM(elem)
+#define        QMD_TRACE_HEAD(head)
+#define        TRACEBUF
+#define        TRASHIT(x)
+#endif /* QUEUE_MACRO_DEBUG */
 
 /*
  * Singly-linked List declarations.
@@ -125,14 +145,14 @@ struct name {                                                             \
 
 #define        SLIST_HEAD_INITIALIZER(head)                                    \
        { NULL }
+
 #define        SLIST_ENTRY(type)                                               \
 struct {                                                               \
        struct type *sle_next;  /* next element */                      \
 }
 
-#define SLIST_ENTRY_INITIALIZER        { NULL }
+#define        SLIST_ENTRY_INITIALIZER { NULL }
+
 /*
  * Singly-linked List functions.
  */
@@ -145,6 +165,16 @@ struct {                                                           \
            (var);                                                      \
            (var) = SLIST_NEXT((var), field))
 
+#define        SLIST_FOREACH_MUTABLE(var, head, field, tvar)                   \
+       for ((var) = SLIST_FIRST((head));                               \
+           (var) && ((tvar) = SLIST_NEXT((var), field), 1);            \
+           (var) = (tvar))
+
+#define        SLIST_FOREACH_PREVPTR(var, varp, head, field)                   \
+       for ((varp) = &SLIST_FIRST((head));                             \
+           ((var) = *(varp)) != NULL;                                  \
+           (varp) = &SLIST_NEXT((var), field))
+
 #define        SLIST_INIT(head) do {                                           \
        SLIST_FIRST((head)) = NULL;                                     \
 } while (0)
@@ -169,9 +199,14 @@ struct {                                                           \
                struct type *curelm = SLIST_FIRST((head));              \
                while (SLIST_NEXT(curelm, field) != (elm))              \
                        curelm = SLIST_NEXT(curelm, field);             \
-               SLIST_NEXT(curelm, field) =                             \
-                   SLIST_NEXT(SLIST_NEXT(curelm, field), field);       \
+               SLIST_REMOVE_NEXT(head, curelm, field);                 \
        }                                                               \
+       TRASHIT((elm)->field.sle_next);                                 \
+} while (0)
+
+#define SLIST_REMOVE_NEXT(head, elm, field) do {                               \
+       SLIST_NEXT(elm, field) =                                        \
+           SLIST_NEXT(SLIST_NEXT(elm, field), field);                  \
 } while (0)
 
 #define        SLIST_REMOVE_HEAD(head, field) do {                             \
@@ -215,7 +250,8 @@ struct {                                                            \
           (var);                                                       \
           (var) = STAILQ_NEXT((var), field))
 
-#define STAILQ_FOREACH_MUTABLE(var, head, field, tvar)                 \
+
+#define        STAILQ_FOREACH_MUTABLE(var, head, field, tvar)                  \
        for ((var) = STAILQ_FIRST((head));                              \
            (var) && ((tvar) = STAILQ_NEXT((var), field), 1);           \
            (var) = (tvar))
@@ -244,25 +280,24 @@ struct {                                                          \
 } while (0)
 
 #define        STAILQ_LAST(head, type, field)                                  \
-       (STAILQ_EMPTY(head) ?                                           \
+       (STAILQ_EMPTY((head)) ?                                         \
                NULL :                                                  \
-               ((struct type *)                                        \
+               ((struct type *)(void *)                                \
                ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
 
 #define        STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
 
 #define        STAILQ_REMOVE(head, elm, type, field) do {                      \
        if (STAILQ_FIRST((head)) == (elm)) {                            \
-               STAILQ_REMOVE_HEAD(head, field);                        \
+               STAILQ_REMOVE_HEAD((head), field);                      \
        }                                                               \
        else {                                                          \
                struct type *curelm = STAILQ_FIRST((head));             \
                while (STAILQ_NEXT(curelm, field) != (elm))             \
                        curelm = STAILQ_NEXT(curelm, field);            \
-               if ((STAILQ_NEXT(curelm, field) =                       \
-                    STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
-                       (head)->stqh_last = &STAILQ_NEXT((curelm), field);\
+               STAILQ_REMOVE_NEXT(head, curelm, field);                \
        }                                                               \
+       TRASHIT((elm)->field.stqe_next);                                \
 } while (0)
 
 #define        STAILQ_REMOVE_HEAD(head, field) do {                            \
@@ -271,9 +306,10 @@ struct {                                                           \
                (head)->stqh_last = &STAILQ_FIRST((head));              \
 } while (0)
 
-#define        STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {                 \
-       if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
-               (head)->stqh_last = &STAILQ_FIRST((head));              \
+#define STAILQ_REMOVE_NEXT(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)
 
 /*
@@ -297,6 +333,31 @@ struct {                                                           \
  * List functions.
  */
 
+#if (defined(_KERNEL) && defined(INVARIANTS))
+#define        QMD_LIST_CHECK_HEAD(head, field) do {                           \
+       if (LIST_FIRST((head)) != NULL &&                               \
+           LIST_FIRST((head))->field.le_prev !=                        \
+            &LIST_FIRST((head)))                                       \
+               panic("Bad list head %p first->prev != head", (head));  \
+} while (0)
+
+#define        QMD_LIST_CHECK_NEXT(elm, field) do {                            \
+       if (LIST_NEXT((elm), field) != NULL &&                          \
+           LIST_NEXT((elm), field)->field.le_prev !=                   \
+            &((elm)->field.le_next))                                   \
+               panic("Bad link elm %p next->prev != elm", (elm));      \
+} while (0)
+
+#define        QMD_LIST_CHECK_PREV(elm, field) do {                            \
+       if (*(elm)->field.le_prev != (elm))                             \
+               panic("Bad link elm %p prev->next != elm", (elm));      \
+} while (0)
+#else
+#define        QMD_LIST_CHECK_HEAD(head, field)
+#define        QMD_LIST_CHECK_NEXT(elm, field)
+#define        QMD_LIST_CHECK_PREV(elm, field)
+#endif /* (_KERNEL && INVARIANTS) */
+
 #define        LIST_EMPTY(head)        ((head)->lh_first == NULL)
 
 #define        LIST_FIRST(head)        ((head)->lh_first)
@@ -306,16 +367,17 @@ struct {                                                          \
            (var);                                                      \
            (var) = LIST_NEXT((var), field))
 
-#define        LIST_FOREACH_MUTABLE(var, head, field, nvar)                    \
+#define        LIST_FOREACH_MUTABLE(var, head, field, tvar)                    \
        for ((var) = LIST_FIRST((head));                                \
-            (var) && ((nvar) = LIST_NEXT((var), field), 1);            \
-            (var) = (nvar))
+           (var) && ((tvar) = LIST_NEXT((var), field), 1);             \
+           (var) = (tvar))
 
 #define        LIST_INIT(head) do {                                            \
        LIST_FIRST((head)) = NULL;                                      \
 } while (0)
 
 #define        LIST_INSERT_AFTER(listelm, elm, field) do {                     \
+       QMD_LIST_CHECK_NEXT(listelm, field);                            \
        if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
                LIST_NEXT((listelm), field)->field.le_prev =            \
                    &LIST_NEXT((elm), field);                           \
@@ -324,6 +386,7 @@ struct {                                                            \
 } while (0)
 
 #define        LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
+       QMD_LIST_CHECK_PREV(listelm, field);                            \
        (elm)->field.le_prev = (listelm)->field.le_prev;                \
        LIST_NEXT((elm), field) = (listelm);                            \
        *(listelm)->field.le_prev = (elm);                              \
@@ -331,6 +394,7 @@ struct {                                                            \
 } while (0)
 
 #define        LIST_INSERT_HEAD(head, elm, field) do {                         \
+       QMD_LIST_CHECK_HEAD((head), field);                             \
        if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)     \
                LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
        LIST_FIRST((head)) = (elm);                                     \
@@ -340,10 +404,14 @@ struct {                                                          \
 #define        LIST_NEXT(elm, field)   ((elm)->field.le_next)
 
 #define        LIST_REMOVE(elm, field) do {                                    \
+       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);                                  \
 } while (0)
 
 /*
@@ -353,6 +421,7 @@ struct {                                                            \
 struct name {                                                          \
        struct type *tqh_first; /* first element */                     \
        struct type **tqh_last; /* addr of last next element */         \
+       TRACEBUF                                                        \
 }
 
 #define        TAILQ_HEAD_INITIALIZER(head)                                    \
@@ -362,17 +431,51 @@ struct name {                                                             \
 struct {                                                               \
        struct type *tqe_next;  /* next element */                      \
        struct type **tqe_prev; /* address of previous next element */  \
+       TRACEBUF                                                        \
 }
 
 /*
  * Tail queue functions.
  */
+#if (defined(_KERNEL) && defined(INVARIANTS))
+#define        QMD_TAILQ_CHECK_HEAD(head, field) do {                          \
+       if (!TAILQ_EMPTY(head) &&                                       \
+           TAILQ_FIRST((head))->field.tqe_prev !=                      \
+            &TAILQ_FIRST((head)))                                      \
+               panic("Bad tailq head %p first->prev != head", (head)); \
+} while (0)
+
+#define        QMD_TAILQ_CHECK_TAIL(head, field) do {                          \
+       if (*(head)->tqh_last != NULL)                                  \
+               panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head));  \
+} while (0)
+
+#define        QMD_TAILQ_CHECK_NEXT(elm, field) do {                           \
+       if (TAILQ_NEXT((elm), field) != NULL &&                         \
+           TAILQ_NEXT((elm), field)->field.tqe_prev !=                 \
+            &((elm)->field.tqe_next))                                  \
+               panic("Bad link elm %p next->prev != elm", (elm));      \
+} while (0)
+
+#define        QMD_TAILQ_CHECK_PREV(elm, field) do {                           \
+       if (*(elm)->field.tqe_prev != (elm))                            \
+               panic("Bad link elm %p prev->next != elm", (elm));      \
+} while (0)
+#else
+#define        QMD_TAILQ_CHECK_HEAD(head, field)
+#define        QMD_TAILQ_CHECK_TAIL(head, headname)
+#define        QMD_TAILQ_CHECK_NEXT(elm, field)
+#define        QMD_TAILQ_CHECK_PREV(elm, field)
+#endif /* (_KERNEL && INVARIANTS) */
+
 #define        TAILQ_CONCAT(head1, head2, field) do {                          \
        if (!TAILQ_EMPTY(head2)) {                                      \
                *(head1)->tqh_last = (head2)->tqh_first;                \
                (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
                (head1)->tqh_last = (head2)->tqh_last;                  \
                TAILQ_INIT((head2));                                    \
+               QMD_TRACE_HEAD(head1);                                  \
+               QMD_TRACE_HEAD(head2);                                  \
        }                                                               \
 } while (0)
 
@@ -385,45 +488,54 @@ struct {                                                          \
            (var);                                                      \
            (var) = TAILQ_NEXT((var), field))
 
-#define        TAILQ_FOREACH_SAFE(var, head, field, tvar)                      \
+#define        TAILQ_FOREACH_MUTABLE(var, head, field, tvar)                   \
        for ((var) = TAILQ_FIRST((head));                               \
            (var) && ((tvar) = TAILQ_NEXT((var), field), 1);            \
            (var) = (tvar))
 
-
 #define        TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
        for ((var) = TAILQ_LAST((head), headname);                      \
            (var);                                                      \
            (var) = TAILQ_PREV((var), headname, field))
 
-#define        TAILQ_FOREACH_MUTABLE(var, head, field, nvar)                   \
-       for ((var) = TAILQ_FIRST((head));                               \
-            (var) && ((nvar) = TAILQ_NEXT((var), field), (var));       \
-            (var) = (nvar))
+#define        TAILQ_FOREACH_REVERSE_MUTABLE(var, head, headname, field, tvar) \
+       for ((var) = TAILQ_LAST((head), headname);                      \
+           (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);  \
+           (var) = (tvar))
 
 #define        TAILQ_INIT(head) do {                                           \
        TAILQ_FIRST((head)) = NULL;                                     \
        (head)->tqh_last = &TAILQ_FIRST((head));                        \
+       QMD_TRACE_HEAD(head);                                           \
 } while (0)
 
 #define        TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
+       QMD_TAILQ_CHECK_NEXT(listelm, field);                           \
        if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
                TAILQ_NEXT((elm), field)->field.tqe_prev =              \
                    &TAILQ_NEXT((elm), field);                          \
-       else                                                            \
+       else {                                                          \
                (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
+               QMD_TRACE_HEAD(head);                                   \
+       }                                                               \
        TAILQ_NEXT((listelm), field) = (elm);                           \
        (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);          \
+       QMD_TRACE_ELEM(&(elm)->field);                                  \
+       QMD_TRACE_ELEM(&listelm->field);                                \
 } while (0)
 
 #define        TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
+       QMD_TAILQ_CHECK_PREV(listelm, field);                           \
        (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
        TAILQ_NEXT((elm), field) = (listelm);                           \
        *(listelm)->field.tqe_prev = (elm);                             \
        (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);          \
+       QMD_TRACE_ELEM(&(elm)->field);                                  \
+       QMD_TRACE_ELEM(&listelm->field);                                \
 } while (0)
 
 #define        TAILQ_INSERT_HEAD(head, elm, field) do {                        \
+       QMD_TAILQ_CHECK_HEAD(head, field);                              \
        if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)   \
                TAILQ_FIRST((head))->field.tqe_prev =                   \
                    &TAILQ_NEXT((elm), field);                          \
@@ -431,13 +543,18 @@ struct {                                                          \
                (head)->tqh_last = &TAILQ_NEXT((elm), field);           \
        TAILQ_FIRST((head)) = (elm);                                    \
        (elm)->field.tqe_prev = &TAILQ_FIRST((head));                   \
+       QMD_TRACE_HEAD(head);                                           \
+       QMD_TRACE_ELEM(&(elm)->field);                                  \
 } while (0)
 
 #define        TAILQ_INSERT_TAIL(head, elm, field) do {                        \
+       QMD_TAILQ_CHECK_TAIL(head, field);                              \
        TAILQ_NEXT((elm), field) = NULL;                                \
        (elm)->field.tqe_prev = (head)->tqh_last;                       \
        *(head)->tqh_last = (elm);                                      \
        (head)->tqh_last = &TAILQ_NEXT((elm), field);                   \
+       QMD_TRACE_HEAD(head);                                           \
+       QMD_TRACE_ELEM(&(elm)->field);                                  \
 } while (0)
 
 #define        TAILQ_LAST(head, headname)                                      \
@@ -449,112 +566,21 @@ struct {                                                         \
        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 
 #define        TAILQ_REMOVE(head, elm, field) do {                             \
+       QMD_TAILQ_CHECK_NEXT(elm, field);                               \
+       QMD_TAILQ_CHECK_PREV(elm, field);                               \
        if ((TAILQ_NEXT((elm), field)) != NULL)                         \
                TAILQ_NEXT((elm), field)->field.tqe_prev =              \
                    (elm)->field.tqe_prev;                              \
-       else                                                            \
+       else {                                                          \
                (head)->tqh_last = (elm)->field.tqe_prev;               \
+               QMD_TRACE_HEAD(head);                                   \
+       }                                                               \
        *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);              \
+       TRASHIT((elm)->field.tqe_next);                                 \
+       TRASHIT((elm)->field.tqe_prev);                                 \
+       QMD_TRACE_ELEM(&(elm)->field);                                  \
 } while (0)
 
-/*
- * Circular queue declarations.
- */
-#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)                                             \
-struct {                                                               \
-       struct type *cqe_next;          /* next element */              \
-       struct type *cqe_prev;          /* previous element */          \
-}
-
-/*
- * Circular queue functions.
- */
-#define        CIRCLEQ_EMPTY(head)     ((head)->cqh_first == (void *)(head))
-
-#define        CIRCLEQ_FIRST(head)     ((head)->cqh_first)
-
-#define        CIRCLEQ_FOREACH(var, head, field)                               \
-       for ((var) = CIRCLEQ_FIRST((head));                             \
-           (var) != (void *)(head) || ((var) = NULL);                  \
-           (var) = CIRCLEQ_NEXT((var), field))
-
-#define        CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
-       for ((var) = CIRCLEQ_LAST((head));                              \
-           (var) != (void *)(head) || ((var) = NULL);                  \
-           (var) = CIRCLEQ_PREV((var), field))
-
-#define        CIRCLEQ_INIT(head) do {                                         \
-       CIRCLEQ_FIRST((head)) = (void *)(head);                         \
-       CIRCLEQ_LAST((head)) = (void *)(head);                          \
-} while (0)
-
-#define        CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
-       CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field);    \
-       CIRCLEQ_PREV((elm), field) = (listelm);                         \
-       if (CIRCLEQ_NEXT((listelm), field) == (void *)(head))           \
-               CIRCLEQ_LAST((head)) = (elm);                           \
-       else                                                            \
-               CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\
-       CIRCLEQ_NEXT((listelm), field) = (elm);                         \
-} while (0)
-
-#define        CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
-       CIRCLEQ_NEXT((elm), field) = (listelm);                         \
-       CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field);    \
-       if (CIRCLEQ_PREV((listelm), field) == (void *)(head))           \
-               CIRCLEQ_FIRST((head)) = (elm);                          \
-       else                                                            \
-               CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\
-       CIRCLEQ_PREV((listelm), field) = (elm);                         \
-} while (0)
-
-#define        CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
-       CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head));             \
-       CIRCLEQ_PREV((elm), field) = (void *)(head);                    \
-       if (CIRCLEQ_LAST((head)) == (void *)(head))                     \
-               CIRCLEQ_LAST((head)) = (elm);                           \
-       else                                                            \
-               CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm);     \
-       CIRCLEQ_FIRST((head)) = (elm);                                  \
-} while (0)
-
-#define        CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
-       CIRCLEQ_NEXT((elm), field) = (void *)(head);                    \
-       CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head));              \
-       if (CIRCLEQ_FIRST((head)) == (void *)(head))                    \
-               CIRCLEQ_FIRST((head)) = (elm);                          \
-       else                                                            \
-               CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm);      \
-       CIRCLEQ_LAST((head)) = (elm);                                   \
-} while (0)
-
-#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_REMOVE(head, elm, field) do {                           \
-       if (CIRCLEQ_NEXT((elm), field) == (void *)(head))               \
-               CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field);      \
-       else                                                            \
-               CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) =       \
-                   CIRCLEQ_PREV((elm), field);                         \
-       if (CIRCLEQ_PREV((elm), field) == (void *)(head))               \
-               CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field);     \
-       else                                                            \
-               CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) =       \
-                   CIRCLEQ_NEXT((elm), field);                         \
-} while (0)
 
 #ifdef _KERNEL
 
@@ -568,7 +594,7 @@ struct quehead {
        struct quehead *qh_rlink;
 };
 
-#ifdef __GNUC__
+#ifdef __GNUC__
 
 static __inline void
 insque(void *a, void *b)
@@ -594,8 +620,8 @@ remque(void *a)
 
 #else /* !__GNUC__ */
 
-void   insque (void *a, void *b);
-void   remque (void *a);
+void   insque(void *a, void *b);
+void   remque(void *a);
 
 #endif /* __GNUC__ */
 
index 67ba8b5..441ddb6 100644 (file)
@@ -95,9 +95,9 @@ struct u_rman {
  * address space).  That is also why the indices are defined to have type
  * `unsigned long' -- that being the largest integral type in Standard C.
  */
-CIRCLEQ_HEAD(resource_head, resource);
+TAILQ_HEAD(resource_head, resource);
 struct resource {
-       CIRCLEQ_ENTRY(resource) r_link;
+       TAILQ_ENTRY(resource)   r_link;
        LIST_ENTRY(resource)    r_sharelink;
        LIST_HEAD(, resource)   *r_sharehead;
        u_long  r_start;        /* index of the first entry in this resource */