Re: Tree/ListStore implementation

[Owen Taylor <otaylor redhat com>]

Jarek Dukat <madmaxer poczta fm> writes:

> Hi
> 
> I have a suggestion, select which one you like more:
> 1. Use double-linked list in GtkTree/ListStore implementation to keep
> data
> 2. Implement O(1) tail lookups in GSList.
> 
> I think the second option make much more sense. It won't blow GSList's
> memory ussage, and it will dramatically increase adding items to a long
> list.
> 
> I have a TreeView that shows ~20K items and creating a model takes ~2
> minutes on my Duron 800MHz when using gtk_tree_model_append() and about
> 10 seconds when applying items in reverse order and using
> gtk_tree_model_prepend(). Unfortunatelly adding in reverse order is not
> always possible. Don't you think that optimizig Tree/ListStore is worth
> using slightly more memory? If you don't want to implement O(1) tail
> lookup into GSList then please use double linked list in model
> implementation.

You can do it like this:

 GtkTreeIter *location = NULL;
 GtkTreeIter new_location;
 
 while ([more rows to insert])
 { 
   gtk_tree_store_insert_after (tree_store, &new_location, parent, location);

  [ do something with &new_location ];

   location = &new_location;
 }

The above technique is more flexible than having TreeStore
optimize a single case - what if you wanted to insert a bunch
of items in the middle of a tree view level?

GtkListStore already caches a the tail pointer so 
gtk_list_store_append() is O(1). GtkTreeStore doesn't have
a single "tail" so it can't do that easily.

(Changing how GSList or GList work is not an option. There is
a proposal to add a "GRing" with O(1) appends for future versions 
of GLib - http://bugzilla.gnome.org/show_bug.cgi?id=59431; GQueue
already exists in GLib and (with a tiny bit of extra overhead)
allows O(1) appends.)

Regards,
                                        Owen