GNOME.org
 

Re: [PATCH] GIterator

Joel Becker wrote:


Iterators for GLib and GObject
First, I would like to say that I would really like to see something like this in glib. Once they are available, you find all kinds of uses for them. Some things that seemed difficult become trivial and easy to read with a good iterator implementation.
In python, they just added iterator support to the language in 2.2 (you could implement iterators before hand but in 2.2, things like the for loop are implemented in terms of iterators). They also added support for generators, which provide a convenient way to create iterators, but they are not really applicable to this proposal (and they can't really be implemented in C without some stack fiddling).
Also, iterators are very simple to use (and usually almost as easy to code). Unlike loops such as gtk_container_foreach() where you need to structure your code to fit into the container's loop, an iterator leaves the user in charge of program flow. They can stop the iteration any time they want (simply by not asking for any more elements, and destroying the iterator).
If you do destroy an iterator before going all the way through the sequence, the remaining elements need not be calculated (which can be quite useful when iterating over a sequence whose elements are are expensive to calculate, or infinite sequences). 




	OK, here are my thoughts on iterators for GLib.
	First, a couple of terms.  I am discussing iterators as Python
or Java use them.  My original code was based on Java's Enumeration
interface, and is now based loosely on the Iterator interface.  Python
iterators behave similarly.  When I speak of an iterator "user," I do
not mean a person implementing an iterator.  That person I refer to as
the "implementor."  The point of an iterator is that the person
retrieving an iterator from a provided API (the "user") does not have
any idea how it is implemented.  They only know the access functions for
iterators.  If this isn't clear, hopefully it will become more clear as
this document progresses ;-)
In my opinion, keeping the iterator interfaces as simple as possible is a good idea. If things are too complex, no one will implement iterators and the API won't be very useful. I think having single pass, non-copyable iterators that are dynamically allocated is the way to go. This is similar to what python provides and if I understood danielk correctly, matches one of the C++ iterator interfaces. This means the iterator implementor need only implement the following callbacks: 

   * get_next(): get the next value from the iterator
   * has_more(): whether there are more values in the sequence.
   * destroy_notify(): clean up any resources the iterator allocated.
If a particular iterator wants to support copying, etc, it can easily provide functions for doing so. In most cases you don't need to copy iterators (just create a new one). 


	I got going on this from the great debate about returning static
versus allocated constructs.  The discussion mostly revolved around
returning static strings vs g_strdup()ing them.  The subject of
allocated vs static GList returns was brought up but not really
discussed.  At the time, various GTK+ API returned GLists, and they
varied whether you were required to free the list.  We've improved that
a lot now, thank heavens.
	In providing an iterator structure, I generally had the
following goals in mind:

o The implementor should have flexible control over how the iterator
 behaves.
o People linking libgobject should be able to take advantage of GValue.
o There should be usable iterators for people only linking libglib.
o The interface should be similar whether GValue is being used or
 not.

	I looked at trying to use the same exact API for GValue and
non-GValue iterators, but it ended up being non-obvious how to do it
cleanly.  The generic use is:

--8<--------------------------------------------------------------
iter = foo_something_iterate(foo);
while (g_iterator_has_more(iter))
{
   item = (FooItem *)g_iterator_get_next(iter);
   do_something(item);
}
g_iterator_free(iter);

v_iter = foo_something_else_iterate(foo);
while (g_value_iterator_has_more(v_iter);
{
   g_value_iterator_get_next(v_iter, &gvalue);
   do_something_else(gvalue);
}
g_value_iterator_free(v_iter);
-->8--------------------------------------------------------------
Looks like a convenient API. I could easily wrap an arbitrary GValueIterator as a Python iterator for pygtk, and write a GIterator/GValueIterator that returned the values from a python iterator. 



       I've also added some nice convenience functions to do things
like iterate GLists and create a GValueIterator from a GIterator.  As
a side effect of the implementation, "generators" ala python are also
quite possible.  There is an example of a generator in testglib.c.
I talked with Joel on IRC, and this is a bit of a misunderstanding on the term generator. You would need to allocate a new stack for the generator, and probably play some setjmp()/longjmp() hacks to implement one (it might be a bit easier using a cothread library though). 


	Three patches are attached.  They are all against GLib HEAD.
The first (glib-2.0.3-giterator-00-iterator-core.patch) provides the
core GIterator data structure.  The second
(glib-2.0.3-iterator-10-giterator-funcs.patch) provides various
convenience functions to other parts of GLib.  The third
(glib-2.0.3-iterator-20-giterator-gvalue.patch) adds GValueIterator.
These patches are also in Bugzilla against the Bug ID #83729.
	Please have a look at this.  Folks who are interested, please
make your interest known.  I'm open to any and all feedback.
	I myself use a variation of the GIterator code in three
different projects and I enjoy the flexibility it provides.  I think it
would be a useful addition to GLib.
Yep, it would be good to see something like this in glib. Providing some standard iterators (such as iterate over GList, etc) should help people move existing code over to interfaces that use iterators, while still being able to switch over to a more efficient implementation later on. 

James.

--
Email: james daa com au              | Linux.conf.au 2003 Call for Papers out
WWW:   http://www.daa.com.au/~james/ |   http://conf.linux.org.au/cfp.html
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]