Date: Thu, 3 Jan 2002 10:46:48 +0100 (CET) From: Harti Brandt <brandt@fokus.gmd.de> To: Matthew Dillon <dillon@apollo.backplane.com> Cc: Julian Elischer <julian@elischer.org>, Poul-Henning Kamp <phk@critter.freebsd.dk>, Stephen McKay <mckay@thehub.com.au>, John Baldwin <jhb@FreeBSD.ORG>, <cvs-all@FreeBSD.ORG>, <cvs-committers@FreeBSD.ORG>, Julian Elischer <julian@FreeBSD.ORG>, Greg Lehey <grog@FreeBSD.ORG> Subject: Re: cvs commit: src/share/man/man3 queue.3 Message-ID: <20020103103234.N7957-100000@beagle.fokus.gmd.de> In-Reply-To: <200201030919.g039J8v63350@apollo.backplane.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, 3 Jan 2002, Matthew Dillon wrote:
MD>
MD>:...
MD>:> There are types of lists/queues which doesn't naturally end with
MD>:> that condition. That is why we have the FOO_EMPTY() clause, although
MD>:> people tend to also rely on
MD>:>
MD>:> if (FOO_FIRST(...) == NULL)
MD>:> /* nothing to do */
MD>:
MD>:Since TAILQ_FIRST== NULL is a termination (it's empty)
MD>:condition (as is TAILQ_NEXT() == NULL)
MD>:it makes PERFECT sense that a completed set of iterations ends up
MD>:with the pointer being NULL.
MD>:
MD>:Sometimes I reckon you are bloody minded just for the sheer fun of it..
MD>
MD> The issue here is to extend an abstraction up to the point where
MD> the compiler can easily optimize it.
MD>
MD> Most of the lists I use are implemented circularly internally,
MD> allowing addhead, addtail, insertbefore, insertafter, and remove
MD> functions to be implemented with no conditionals. In this case
MD> the terminator is a pointer back to the list head.
MD>
MD> Now consider a MYLIST_EMPTY() macro verses a MYLIST_GETHEAD()
MD> macro. MYLIST_GETHEAD() would have to check for the terminating
MD> condition (a conditional) and return NULL if it's true and the head
MD> node if it is false. MYLIST_EMPTY() simply checks the terminating
MD> condition and returns a boolean. Now consider this code:
MD>
MD>
MD> #define MYLIST_GETHEAD(list) ((list->head == (node *)list) ? NULL : lsit->head)
MD>
MD> #define MYLIST_EMPTY(list) (list->head == (node *)list)
MD>
MD>
MD> if (MYLIST_GETHEAD(list) == NULL) {
MD> ... empty list ...
MD> }
MD>
MD> vs
MD>
MD> if (MYLIST_EMPTY(list)) {
MD> ... empty list ...
MD> }
MD>
MD> The first code block winds up generating two unoptimizable conditionals
MD> (the C compiler can't optimize the NULL case because it can't assume
MD> that the else case won't return NULL, so it cannot propogate the
MD> conditional to the higher level IF statement). Thus you wind up
MD> with two conditionals.
MD>
MD> The second code block generates one easily optimizable conditional.
MD> The MYLIST_EMPTY() conditional, returning a bool, becomes the
MD> condition used by the IF statement.
MD>
MD> So a XXX_LIST_EMPTY() macro can in fact produce much, much better
MD> code for certain types of lists, and will produce code that is no worse
MD> then XXX_LIST_HEAD() for lists that are naturally NULL terminated.
MD>
MD> This makes XXX_LIST_EMPTY() a useful macro and a useful abstraction
MD> to have.
Well the point is, that we are not talking about MYLIST_*, but about
TAILQ_FIRST. While you are certainly right if you are going to design a
general abstract list interface, we are talking here about a concrete data
structure with know behaviour. man 3 queue already contains a table of
which of the list structures give you which behaviour and the programmer
should choose the structure that fits best his needs. So documenting the
fact that *_FIRST returns NULL for those list structures for which it
does, doesn't break anything and gives the programer even more hints for
his decision. And documenting the fact that *_FOREACH leaves the pointer
NULL does the same. If you are going to implement a new structure which
breaks this, give it another name, but leave the existing structures as
they are.
If you require the programmer to write:
if (LIST_EMPTY(...))
foo;
else {
p = LIST_FIRST(...);
while (p != NULL) {
if (test(p))
break;
p = LIST_NEXT(p, ...)
}
if (p == NULL)
foo;
else
bar;
}
instead of:
LIST_FOREACH(p, ....)
if (test(p))
break;
if (p == NULL)
bar;
else
baz;
they will rather roll there own implementations.
A agree however, that *_FOREACH would better be named *_FOR.
harti
--
harti brandt, http://www.fokus.gmd.de/research/cc/cats/employees/hartmut.brandt/private
brandt@fokus.fhg.de
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe cvs-all" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20020103103234.N7957-100000>