From: Linus Torvalds <torvalds@osdl.org>
Date: Tue, 13 Sep 2005 00:17:32 GMT
Subject: Re: [PATCH 00/22] cache cursors: an introduction
Message-ID: <Pine.LNX.4.58.0509121708430.3266@g5.osdl.org>
In-Reply-To: <43261675.10905@citi.umich.edu>



On Mon, 12 Sep 2005, Chuck Lever wrote:
> 
> heh.  well, i had something like this earlier, but i know linus doesn't 
> like void *, and it was really kind of ugly.  and as you observed, it's 
> used so rarely.  so i just decided to drop it.

Iterators are _much_ nicer if you can use them in-line instead of with a 
function pointer. It makes them a hundred times more powerful, and avoids 
all the crap with trying to pass a magic argument around.

That was why I mentioned the sparse "ptrlist" implementation: the data 
structure itself may not be all that exciting, but the syntax for _using_ 
it is incredibly powerful. Much better than any other list handling 
package I've ever seen, if I do say so myself.

So check out

	kernel.org:/pub/scm/devel/sparse/sparse.git

and look at how easy it is to iterate over a list. The _true_ power is how 
you can return out of a function in the middle of the iterator, ie

	int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
	{
	        pseudo_t old;
	        FOR_EACH_PTR(list,old) {
	                if (old == pseudo)
	                        return 1;
	        } END_FOR_EACH_PTR(old);
	        return 0;
	}

(and it's type-safe too!)

Now, nested iterators may sound easy, but they aren't easy if you want to 
actually break out of them in a nested way. Try to do _this_ with a 
function pointer interface without going crazy:

	        /* Remove the pseudos from the "defines" list that are used internally */
	        FOR_EACH_PTR(ep->bbs, bb) {
	                pseudo_t def;
	                FOR_EACH_PTR(bb->defines, def) {
	                        struct basic_block *child;
	                        FOR_EACH_PTR(bb->children, child) {
	                                if (pseudo_in_list(child->needs, def))
	                                        goto is_used;
	                        } END_FOR_EACH_PTR(child);
	                        DELETE_CURRENT_PTR(def);
	is_used:
	                ;
	                } END_FOR_EACH_PTR(def);
	                PACK_PTR_LIST(&bb->defines);
	        } END_FOR_EACH_PTR(bb);

all real examples from real code that implements an almost-real compiler.

Very dense code too, btw. It's incredible how expressive these iterators 
are: I started out with a function pointer interface, and it was painful 
as _hell_ to see what was going on.

		Linus