From owner-cvs-all Thu Jan 3 1:51:39 2002 Delivered-To: cvs-all@freebsd.org Received: from mailhub.fokus.gmd.de (mailhub.fokus.gmd.de [193.174.154.14]) by hub.freebsd.org (Postfix) with ESMTP id 54CAB37B419; Thu, 3 Jan 2002 01:47:24 -0800 (PST) Received: from beagle (beagle [193.175.132.100]) by mailhub.fokus.gmd.de (8.11.6/8.11.6) with ESMTP id g039kmh04107; Thu, 3 Jan 2002 10:46:48 +0100 (MET) Date: Thu, 3 Jan 2002 10:46:48 +0100 (CET) From: Harti Brandt To: Matthew Dillon Cc: Julian Elischer , Poul-Henning Kamp , Stephen McKay , John Baldwin , , , Julian Elischer , Greg Lehey Subject: Re: cvs commit: src/share/man/man3 queue.3 In-Reply-To: <200201030919.g039J8v63350@apollo.backplane.com> Message-ID: <20020103103234.N7957-100000@beagle.fokus.gmd.de> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-cvs-all@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG 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