Date: Wed, 3 Jul 2002 13:46:25 -0700 From: Neal Fachan <neal@isilon.com> To: Julian Elischer <julian@elischer.org> Cc: Terry Lambert <tlambert2@mindspring.com>, Garrett Wollman <wollman@lcs.mit.edu>, Jonathan Lemon <jlemon@flugsvamp.com>, current@FreeBSD.ORG Subject: Re: additional queue macro Message-ID: <20020703134624.B95118@isilon.com> In-Reply-To: <Pine.BSF.4.21.0207021648200.97650-100000@InterJet.elischer.org>; from julian@elischer.org on Tue, Jul 02, 2002 at 04:54:43PM -0700 References: <Pine.BSF.4.21.0207021556300.97650-100000@InterJet.elischer.org> <Pine.BSF.4.21.0207021648200.97650-100000@InterJet.elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
--BOKacYhQ+x31HxR3
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
We've got local changes (which I've attached) where the name is
*_FOREACH_REMOVE. We didn't add reverse removable iterators. Also, the
temp variable is the second argument. I can't think of a way of doing it
without having the externally declare the temporary variable.
On Tue, Jul 02, 2002 at 04:54:43PM -0700, Julian Elischer wrote:
>
>
> On Tue, 2 Jul 2002, Julian Elischer wrote:
>
> Having just re-read my own mail
>
> I think I agree with jonathan now..
> I think we neeed to either:
> 1/ augment the man page giving an example of how to do
> multiple removes from a list/queue.
> 2/ Explain in detail why using XXXX_FOREACH()
> is bad for this, and showing the alternative.
> 3/ Add something to the API that makes this easy to do.
> designing the API addition is tricky. Jonathan's effort
> was quite good, though I wonder if there is any way we can get it done
> without needing the decalration of 'tmp' separatly.
> (I can't think of a way).
>
>
>
> > /*
> > * Move any threads that should be suspended from the run queue
> > * to the suspend queue.
> > */
> > TAILQ_FOREACH(from run queue) {
> > if (something) {
> > TAILQ_REMOVE(element from run queue)
> > TAILQ_INSERT_TAIL(onto suspend queue)
> > }
> > }
> >
> > Now, at first glance, the documentation suggests this should work, even
> > though we know it won't. but it doesn't crash.. it just terminates on the
> > first transfer because it reaches the end of the queue.. the suspend queue
> > that is..
>
> TAILQ_FOREACH_REMOVABLE or TAILQ_FOREACH_SAFE
> (I prefer the first) are my suggestions for the name.)
>
>
>
>
> To Unsubscribe: send mail to majordomo@FreeBSD.org
> with "unsubscribe freebsd-current" in the body of the message
--
Neal Fachan
neal@isilon.com
--BOKacYhQ+x31HxR3
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="queue.diff"
Index: share/man/man3/queue.3
===================================================================
RCS file: /usr/local/ncvs/atera/src/share/man/man3/queue.3,v
retrieving revision 1.1
diff -u -p -r1.1 queue.3
--- share/man/man3/queue.3 9 Mar 2002 02:34:15 -0000 1.1
+++ share/man/man3/queue.3 3 Jul 2002 20:46:19 -0000
@@ -1,4 +1,4 @@
-.\" Copyright (c) 1993
+tail queue Copyright (c) 1993
.\" The Regents of the University of California. All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
@@ -40,6 +40,7 @@
.Nm SLIST_ENTRY ,
.Nm SLIST_FIRST ,
.Nm SLIST_FOREACH ,
+.Nm SLIST_FOREACH_REMOVE ,
.Nm SLIST_HEAD ,
.Nm SLIST_HEAD_INITIALIZER ,
.Nm SLIST_INIT ,
@@ -52,6 +53,7 @@
.Nm STAILQ_ENTRY ,
.Nm STAILQ_FIRST ,
.Nm STAILQ_FOREACH ,
+.Nm STAILQ_FOREACH_REMOVE ,
.Nm STAILQ_HEAD ,
.Nm STAILQ_HEAD_INITIALIZER ,
.Nm STAILQ_INIT ,
@@ -66,6 +68,7 @@
.Nm LIST_ENTRY ,
.Nm LIST_FIRST ,
.Nm LIST_FOREACH ,
+.Nm LIST_FOREACH_REMOVE ,
.Nm LIST_HEAD ,
.Nm LIST_HEAD_INITIALIZER ,
.Nm LIST_INIT ,
@@ -78,6 +81,7 @@
.Nm TAILQ_ENTRY ,
.Nm TAILQ_FIRST ,
.Nm TAILQ_FOREACH ,
+.Nm TAILQ_FOREACH_REMOVE ,
.Nm TAILQ_FOREACH_REVERSE ,
.Nm TAILQ_HEAD ,
.Nm TAILQ_HEAD_INITIALIZER ,
@@ -99,6 +103,7 @@ lists and tail 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_REMOVE "TYPE *var" "TYPE *tmpvar" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
.Fn SLIST_HEAD "HEADNAME" "TYPE"
.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
.Fn SLIST_INIT "SLIST_HEAD *head"
@@ -112,6 +117,7 @@ lists and tail 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_REMOVE "TYPE *var" "TYPE *tmpvar" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
.Fn STAILQ_HEAD "HEADNAME" "TYPE"
.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
.Fn STAILQ_INIT "STAILQ_HEAD *head"
@@ -127,6 +133,7 @@ lists and tail queues
.Fn LIST_ENTRY "TYPE"
.Fn LIST_FIRST "LIST_HEAD *head"
.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
+.Fn LIST_FOREACH_REMOVE "TYPE *var" "TYPE *tmpvar" "LIST_HEAD *head" "LIST_ENTRY NAME"
.Fn LIST_HEAD "HEADNAME" "TYPE"
.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
.Fn LIST_INIT "LIST_HEAD *head"
@@ -140,6 +147,7 @@ lists and tail 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_REMOVE "TYPE *var" "TYPE *tmpvar" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
.Fn TAILQ_HEAD "HEADNAME" "TYPE"
.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
@@ -316,6 +324,24 @@ turn to
.Fa var .
.Pp
The macro
+.Nm SLIST_FOREACH_REMOVE
+traverses the list referenced by
+.Fa head
+in the forward direction, assigning each element in
+turn to
+.Fa var .
+Unlike
+.Nm SLIST_FOREACH ,
+.Fa var
+is never dereferenced after the body of the loop, making it legal to remove
+.Fa var
+from the list or to call
+.Nm free
+on
+.Fa var
+in the loop body.
+.Pp
+The macro
.Nm SLIST_INIT
initializes the list referenced by
.Fa head .
@@ -381,12 +407,16 @@ free(n3);
/* Forward traversal. */
SLIST_FOREACH(np, &head, entries)
np-> ...
-
-while (!SLIST_EMPTY(&head)) { /* List Deletion. */
+ /* List Deletion. */
+while (!SLIST_EMPTY(&head)) {
n1 = SLIST_FIRST(&head);
SLIST_REMOVE_HEAD(&head, entries);
free(n1);
}
+ /* Faster List Deletion. */
+SLIST_FOREACH_REMOVE(n1, n2, &head, entries)
+ free(n1);
+SLIST_INIT(&head);
.Ed
.Sh SINGLY-LINKED TAIL QUEUES
A singly-linked tail queue is headed by a structure defined by the
@@ -451,6 +481,24 @@ in turn to
.Fa var .
.Pp
The macro
+.Nm STAILQ_FOREACH_REMOVE
+traverses the tail queue referenced by
+.Fa head
+in the forward direction, assigning each element
+in turn to
+.Fa var .
+Unlike
+.Nm STAILQ_FOREACH ,
+.Fa var
+is never dereferenced after the body of the loop, making it legal to remove
+.Fa var
+from the tail queue or to call
+.Nm free
+on
+.Fa var
+in the loop body.
+.Pp
+The macro
.Nm STAILQ_INIT
initializes the tail queue referenced by
.Fa head .
@@ -542,6 +590,10 @@ while (n1 != NULL) {
n1 = n2;
}
STAILQ_INIT(&head);
+ /* Easier Faster List Deletion. */
+STAILQ_FOREACH_REMOVE(n1, n2, &head, entries)
+ free(n1);
+STAILQ_INIT(&head);
.Ed
.Sh LISTS
A list is headed by a structure defined by the
@@ -603,6 +655,23 @@ in the forward direction, assigning each
.Fa var .
.Pp
The macro
+.Nm LIST_FOREACH_REMOVE
+traverses the list referenced by
+.Fa head
+in the forward direction, assigning each element in turn to
+.Fa var .
+Unlike
+.Nm LIST_FOREACH ,
+.Fa var
+is never dereferenced after the body of the loop, making it legal to remove
+.Fa var
+from the list or to call
+.Nm free
+on
+.Fa var
+in the loop body.
+.Pp
+The macro
.Nm LIST_INIT
initializes the list referenced by
.Fa head .
@@ -663,19 +732,22 @@ free(n2);
/* Forward traversal. */
LIST_FOREACH(np, &head, entries)
np-> ...
-
-while (!LIST_EMPTY(&head)) { /* List Deletion. */
+ /* List Deletion. */
+while (!LIST_EMPTY(&head)) {
n1 = LIST_FIRST(&head);
LIST_REMOVE(n1, entries);
free(n1);
}
-
-n1 = LIST_FIRST(&head); /* Faster List Deletion. */
+ /* Faster List Deletion. */
+n1 = LIST_FIRST(&head);
while (n1 != NULL) {
n2 = LIST_NEXT(n1, entries);
free(n1);
n1 = n2;
}
+ /* Easier Faster List Deletion. */
+LIST_FOREACH_REMOVE(n1, n2, &head, entries)
+ free(n1);
LIST_INIT(&head);
.Ed
.Sh TAIL QUEUES
@@ -744,6 +816,23 @@ is set to
if the loop completes normally, or if there were no elements.
.Pp
The macro
+.Nm TAILQ_FOREACH_REMOVE
+traverses the tail queue referenced by
+.Fa head
+in the forward direction, assigning each element in turn to
+.Fa var .
+Unlike
+.Nm TAILQ_FOREACH ,
+.Fa var
+is never dereferenced after the body of the loop, making it legal to remove
+.Fa var
+from the tail queue or to call
+.Nm free
+on
+.Fa var
+in the loop body.
+.Pp
+The macro
.Nm TAILQ_FOREACH_REVERSE
traverses the tail queue referenced by
.Fa head
@@ -847,9 +936,17 @@ while (n1 != NULL) {
n1 = n2;
}
TAILQ_INIT(&head);
+ /* Easier Faster TailQ Deletion. */
+TAILQ_FOREACH_REMOVE(n1, n2, &head, entries)
+ free(n1);
+TAILQ_INIT(&head);
.Ed
.Sh HISTORY
The
.Nm queue
functions first appeared in
.Bx 4.4 .
+.Pp
+Isilon Systems, Inc. added the
+.Nm *_FOREACH_REVERSE
+macros.
Index: sys/sys/queue.h
===================================================================
RCS file: /usr/local/ncvs/atera/src/sys/sys/queue.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -p -r1.1 -r1.2
--- sys/sys/queue.h 9 Mar 2002 02:34:55 -0000 1.1
+++ sys/sys/queue.h 10 Mar 2002 04:16:09 -0000 1.2
@@ -92,6 +92,7 @@
* _PREV - - - +
* _LAST - - + +
* _FOREACH + + + +
+ * _FOREACH_REMOVE + + + +
* _FOREACH_REVERSE - - - +
* _INSERT_HEAD + + + +
* _INSERT_BEFORE - + - +
@@ -130,6 +131,11 @@ struct { \
(var); \
(var) = SLIST_NEXT((var), field))
+#define SLIST_FOREACH_REMOVE(var, tmpvar, head, field) \
+ for ((var) = SLIST_FIRST((head)); \
+ (var) && ((tmpvar) = SLIST_NEXT((var), field), 1); \
+ (var) = (tmpvar))
+
#define SLIST_INIT(head) do { \
SLIST_FIRST((head)) = NULL; \
} while (0)
@@ -192,6 +198,11 @@ struct { \
(var); \
(var) = STAILQ_NEXT((var), field))
+#define STAILQ_FOREACH_REMOVE(var, tmpvar, head, field) \
+ for ((var) = STAILQ_FIRST((head)); \
+ (var) && ((tmpvar) = STAILQ_NEXT((var), field), 1); \
+ (var) = (tmpvar))
+
#define STAILQ_INIT(head) do { \
STAILQ_FIRST((head)) = NULL; \
(head)->stqh_last = &STAILQ_FIRST((head)); \
@@ -278,6 +289,11 @@ struct { \
(var); \
(var) = LIST_NEXT((var), field))
+#define LIST_FOREACH_REMOVE(var, tmpvar, head, field) \
+ for ((var) = LIST_FIRST((head)); \
+ (var) && ((tmpvar) = LIST_NEXT((var), field), 1); \
+ (var) = (tmpvar))
+
#define LIST_INIT(head) do { \
LIST_FIRST((head)) = NULL; \
} while (0)
@@ -342,6 +358,11 @@ struct { \
for ((var) = TAILQ_FIRST((head)); \
(var); \
(var) = TAILQ_NEXT((var), field))
+
+#define TAILQ_FOREACH_REMOVE(var, tmpvar, head, field) \
+ for ((var) = TAILQ_FIRST((head)); \
+ (var) && ((tmpvar) = TAILQ_NEXT((var), field), 1); \
+ (var) = (tmpvar))
#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
for ((var) = TAILQ_LAST((head), headname); \
--BOKacYhQ+x31HxR3--
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20020703134624.B95118>