Re: [PATCH 00/22] cache cursors: an introduction

On Mon, 12 Sep 2005, Chuck Lever wrote:

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