GNOME Bugzilla – Bug 169285
Add iterators to GTree
Last modified: 2011-02-18 16:14:11 UTC
It should be possible to modify a tree while you are traversiing the nodes. With the patch i am submitting, GTree is converted to a threaded tree, that means that the pointers of the leaf nodes instead of beeing null's point to next and previous nodes (see http://www.stanford.edu/~blp/avl/libavl.html/Threads.html). Nothing of what can be currently done with GTree is changed, with no API or ABI change. A new GTreeNode opaque structure is introduced to serve as iterator, and iterators are never invalidated when an element is added, and if an element is removed are invalidated only the iterators pointing to that element. 5 new functions are introduced to work with iterators. The following is a code sample: gconstpointer k,v; GTreeNode *it,*it2; it = g_tree_find(tree,GINT_TO_POINTER (27),&k,&v,G_GREAT_EQ); it2 = g_tree_find(tree,GINT_TO_POINTER (98),NULL,NULL,G_GREATER); while(it && it!=it2) { if( ((int)k) % 7 == 0) { gconstpointer oldk = k; it=g_tree_next(it,&k,&v); /* remove after incrementing the iterator */ g_tree_remove(tree,oldk); } else it=g_tree_next(it,&k,&v); } I am marking the request as small feature, even if GTree are a bit reworked and maybe it should be marked as medium feature. I am submitting the patch in the next message.
Created attachment 38296 [details] [review] convert GTree to threaded tree This is a patch to glib 2.6.2 with my previous patches foreach_range and clear_node applied. If you want a direct patch to 2.6.2 just tell me.
Created attachment 38371 [details] gtree.c rewritten Here is the c file of the rewritten implementation. I am not sending a diff because the source is quite different.
Created attachment 38372 [details] gtree.h rewritten Here is the header. Just replace glib-2.6.2/glib/gree.[ch] with the attached files.
Created attachment 38373 [details] bench.c (small benchmark) This is a small benchmark.
Created attachment 38397 [details] gtree.c rewritten Update: - balance is no more a bitfield, thus making the new code 3x faster then the old one. - g_tree_height is now O(log n) istead then O(n) (!). - added my name in the beginning. - estetic changes to please the Glib team :-)
Created attachment 38398 [details] gtree.h rewritten Updated header.
Here is a sample using the latest code, much simpler. the GTreeNode structure is exported, but only the 'key' member (read-only) and the 'value' member (read-write). See gtree.h for how private members are protected. Note that the code, instead of g_tree_remove, uses the new g_tree_remove_node that is quite faster because doesn't have to call the comparison function. Here is the code sample: GTreeNode *it,*it2; it = g_tree_find_node(tree, GINT_TO_POINTER(27), G_GREAT_EQ); it2 = g_tree_find_node(tree, GINT_TO_POINTER(98), G_GREATER); while( it && it!=it2 ) { if( ((int)it->key) % 7 == 0) it = g_tree_remove_node( tree, it, FALSE ); else it = g_tree_next_node( tree, it ); }
Created attachment 38413 [details] gtree.c rewritten - added a node counter in the GTree, so that g_tree_nnodes is now O(1). - cleanup and remove some old functions. - other very minor optimizations.
Created attachment 38456 [details] gtree.c rewritten - fixed a bug in g_tree_find_node - added g_tree_steal_all. - added g_tree_steal_node and made possible to g_tree_remove_node to return a reference to the previous node.
Created attachment 38457 [details] gtree.h rewritten and here is the header.
Created attachment 46471 [details] gtree.c rewritten and fixed :-) Argh! I had to fix a majog bug in the remove node function! It should be working now... please note that this file is still relative to glib 2.6.3, and doesn't apply cleanly to glib 2.6.4 (because of some __IA_ linker alias...)
Created attachment 46499 [details] gtree.c ok Ok, this is the fix applied to the right file and ok for 2.6.4 :-)
As Owen commented on irc, we would need a comprehensive set of GTree tests before applying this patch.
Unlikely to make 2.8 at this point.
I have committed a bunch of additional tree tests to cvs HEAD now. A number of comments on the patch: 1) I would like to see it split up into separate patches for a) converting gtree.c to a non-recursive threaded tree implementation b) adding new api (iterators, and related functions) 2) You can implement this without maintaining the node_type field. In every place where you access node_type, you also have the parent node around, so you can simple calculate the node_type information as parent->left == node. 3) Since the main advantage of threading is for in-order-iteration, shouldn't you patch g_tree_foreach to take advantage of it ? The patch below does that. 4) Some style things: - put a space between if( - indent opening { - for the iterators, we don't normally do conditional struct definitions like that. Either make it opaque and add accessors for the public fields, or expose all fields and mark the private ones by a /*< private >*/ comment. I'll attach a patch for 1a) against cvs HEAD, that passes the new tests in tree-test.
Created attachment 57046 [details] [review] convert to threaded tree without adding api
2006-01-14 Matthias Clasen <mclasen@redhat.com> * glib/gtree.c: Replace the simple recursive implementation by a nonrecursive, threaded implementation by Maurizio Monge. (#169285)
Retitling to clarify whats left to do here.
I didn't really review this, but I did glance over the patch, and to me it looks like g_tree_node_next() isn't quite correct: It assumes that the 'next' nodes will always be somewhere below the node, which is not true. A node with no children will have its parent as next for example, but g_tree_node() will return NULL in that case.
Soeren, its a threaded tree now, which means that next always points to the next node if there is one.
*** This bug has been marked as a duplicate of bug 578873 ***