Re: implementing custom GtkTreeModels for language bindings

[Duncan Coutts <duncan coutts worc ox ac uk>]

On Sat, 2005-11-26 at 19:07 +0100, Hans Oesterholt-Dijkema wrote:
> Owen Taylor schreef:
> 
> >On Fri, 2005-11-25 at 16:12 +0000, Duncan Coutts wrote:
> >>All,
> >>
> >>Language bindings want to be able to implement the GtkTreeModel
> >>interface. Unfortunately this is rather hard without causing a space
> >>leak.
> >>
> >>The issue is that to implement a the GtkTreeModel interface you must
> >>fill in GtkTreeIter structures. These are typically stack allocated and
> >>do not need to be explicitly freed. As a consequence it is not possible
> >>to track resources that are referenced by GtkTreeIters.

> > The simplest fix for this is to to use iters that don't reference
> > resources - put 1-3 integers into the iterator instead of a pointer.
> > It's easy to see how to do this for a flat model. A little trickier
> > for a tree, but there are various possibilities ... 

> I had no problems at all implementing a GtkTreeModel for mzgtk2 (which 
> implements a list that gets its data via function callbacks).

Yes a list is not too hard since you can just store an integer as the
index in the GtkTreeIter user_data field.

The trickier one as Owen points out is a tree model.

One tree indexing scheme is depth first, but this requires that the
whole tree up to a node be evaluated just to be able to find the node's
index. This would obviously not be good for say a model based on a file
system.

Another indexing system is to use bits to index each level of the tree.
So for example a tree with just 8 nodes in it takes log_2 8 = 3 bits to
index. And then if any of those nodes have child nodes then we use the
next few bits to index those nodes. So for example a tree with a path in
it that has 10 entries at each level then in 96 bits we could index a
tree 24 layers deep (96bit / 4bits per layer). Obviously we can only
index shallower trees if there are more nodes at any level.

>From an initial experiment however I think this might be a reasonable
limit on the indexing. I wrote a little utility to find the maximum
number of bits required to index a file system. I can index the 40GB of
data on my machine which contains over 1.2 million files using 78 bits.
That's reasonably comfortably within the 96 bits available. And if
necessary we could probably steal a few bits from the stamp field.

So if we can index a whole hard drive, that's probably comfortably
larger than the size of trees we might want to display in a GtkTreeView.

This indexing system works in log time in the size of the tree.

Owen might have had something cleverer in mind. 

> If you want to have the sources of the model, I can send you them.

That would be an interesting reference point actually. Thank you.

Duncan