From owner-cvs-all  Thu Jan  3  1:19:49 2002
Delivered-To: cvs-all@freebsd.org
Received: from apollo.backplane.com (apollo.backplane.com [216.240.41.2])
	by hub.freebsd.org (Postfix) with ESMTP
	id 4F04237B416; Thu,  3 Jan 2002 01:19:40 -0800 (PST)
Received: (from dillon@localhost)
	by apollo.backplane.com (8.11.6/8.9.1) id g039J8v63350;
	Thu, 3 Jan 2002 01:19:08 -0800 (PST)
	(envelope-from dillon)
Date: Thu, 3 Jan 2002 01:19:08 -0800 (PST)
From: Matthew Dillon <dillon@apollo.backplane.com>
Message-Id: <200201030919.g039J8v63350@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 
References:  <Pine.BSF.4.21.0201030044520.22265-100000@InterJet.elischer.org>
Sender: owner-cvs-all@FreeBSD.ORG
Precedence: bulk
List-ID: <cvs-all.FreeBSD.ORG>
List-Archive: <http://docs.freebsd.org/mail/> (Web Archive)
List-Help: <mailto:majordomo@FreeBSD.ORG?subject=help> (List Instructions)
List-Subscribe: <mailto:majordomo@FreeBSD.ORG?subject=subscribe%20cvs-all>
List-Unsubscribe: <mailto:majordomo@FreeBSD.ORG?subject=unsubscribe%20cvs-all>
X-Loop: FreeBSD.ORG


:...
:> 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