From owner-freebsd-current Wed Jul 3 17:16:48 2002 Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.FreeBSD.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 3826B37B400 for ; Wed, 3 Jul 2002 17:16:33 -0700 (PDT) Received: from isilon.com (isilon.com [65.101.129.58]) by mx1.FreeBSD.org (Postfix) with SMTP id 8CAB143E4A for ; Wed, 3 Jul 2002 17:16:32 -0700 (PDT) (envelope-from neal@isilon.com) Received: (qmail 96342 invoked by uid 1001); 4 Jul 2002 00:13:51 -0000 Date: Wed, 3 Jul 2002 13:46:25 -0700 From: Neal Fachan To: Julian Elischer Cc: Terry Lambert , Garrett Wollman , Jonathan Lemon , current@FreeBSD.ORG Subject: Re: additional queue macro Message-ID: <20020703134624.B95118@isilon.com> References: Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="BOKacYhQ+x31HxR3" Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: ; from julian@elischer.org on Tue, Jul 02, 2002 at 04:54:43PM -0700 Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG --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