Date: Thu, 3 Jan 2002 01:19:08 -0800 (PST) From: Matthew Dillon <dillon@apollo.backplane.com> To: Julian Elischer <julian@elischer.org> Cc: 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: <200201030919.g039J8v63350@apollo.backplane.com> References: <Pine.BSF.4.21.0201030044520.22265-100000@InterJet.elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
:...
:> There are types of lists/queues which doesn't naturally end with
:> that condition. That is why we have the FOO_EMPTY() clause, although
:> people tend to also rely on
:>
:> if (FOO_FIRST(...) == NULL)
:> /* nothing to do */
:
:Since TAILQ_FIRST== NULL is a termination (it's empty)
:condition (as is TAILQ_NEXT() == NULL)
:it makes PERFECT sense that a completed set of iterations ends up
:with the pointer being NULL.
:
:Sometimes I reckon you are bloody minded just for the sheer fun of it..
The issue here is to extend an abstraction up to the point where
the compiler can easily optimize it.
Most of the lists I use are implemented circularly internally,
allowing addhead, addtail, insertbefore, insertafter, and remove
functions to be implemented with no conditionals. In this case
the terminator is a pointer back to the list head.
Now consider a MYLIST_EMPTY() macro verses a MYLIST_GETHEAD()
macro. MYLIST_GETHEAD() would have to check for the terminating
condition (a conditional) and return NULL if it's true and the head
node if it is false. MYLIST_EMPTY() simply checks the terminating
condition and returns a boolean. Now consider this code:
#define MYLIST_GETHEAD(list) ((list->head == (node *)list) ? NULL : lsit->head)
#define MYLIST_EMPTY(list) (list->head == (node *)list)
if (MYLIST_GETHEAD(list) == NULL) {
... empty list ...
}
vs
if (MYLIST_EMPTY(list)) {
... empty list ...
}
The first code block winds up generating two unoptimizable conditionals
(the C compiler can't optimize the NULL case because it can't assume
that the else case won't return NULL, so it cannot propogate the
conditional to the higher level IF statement). Thus you wind up
with two conditionals.
The second code block generates one easily optimizable conditional.
The MYLIST_EMPTY() conditional, returning a bool, becomes the
condition used by the IF statement.
So a XXX_LIST_EMPTY() macro can in fact produce much, much better
code for certain types of lists, and will produce code that is no worse
then XXX_LIST_HEAD() for lists that are naturally NULL terminated.
This makes XXX_LIST_EMPTY() a useful macro and a useful abstraction
to have.
-Matt
Matthew Dillon
<dillon@backplane.com>
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?200201030919.g039J8v63350>