From: Duncan Coutts <duncan.coutts@wo...>  20051126 17:19:09

On Sat, 20051126 at 12:43 +0000, Axel Simon wrote: > On Sat, 20051126 at 11:58 +0000, Duncan Coutts wrote: > > There is one difficulty in the implementation which is a memory > > management issue. The GtkTreeIter values are just stack allocated values > > and so we cannot know when they are no longer used, so we can't put > > references to Haskell values (rg StablePtrs) into them, or if we do, we > > must remember them so we can free them later. I'm still trying to figure > > out the best way of dealing with this. > > I suppose the TreeIter should really only contain an integer index into > the Haskell data structure. That is exactly what Owen Taylor suggested: http://mail.gnome.org/archives/languagebindings/2005November/msg00004.html > The way it could work is that we find some sort of enumeration of the > underlying data structure. For a plain list implemented by an array it > would just be the array index. Yep. > For a tree constructed by an list of lists, it could be the element > position of the flattended list. The disadvantage of this scheme is > that we need to force the user to make his/her data structure an > instance of class Ix, which is not always trivial. Yeah the indexing for trees is not so easy. Doing a depth first indexing scheme would negate the advantages of calculating the tree on demand (eg think of a very deep directory structure). We actually have 32 * 3 bits to play with and possibly 32 more if we don't think we need the stamp: struct GtkTreeIter { gint stamp; gpointer user_data; gpointer user_data2; gpointer user_data3; }; One idea for an indexing system goes like this: Use bits to denote a position in the tree by binary search at each level in the tree. For example if you have 8 items in the top level of the tree then you can index them with 3 bits. Then you move to the next level of the tree and use more bits. It does put a lower maximum depth of the tree than the depth first (flattening) indexing but it doesn't require the whole of the tree to be evaluated or traversed to find the item. So it gives log time lookup. Eg suppose we had a tree with 8 items at every level in the tree, then we have a maximum depth of 32 (= 32 * 3 / log_2 8). Actually it's slightly worse than that because you need to distinguish when a index stops. That is you need to distinguish stopping at the node itself or going on to it's children. That can be done by calling the node itself the 0'th index of it's children. So instead of getting 8 children into 3 bits you can only have 7 because the 0th one means stopping at the parent node. Or something like that. I'm not sure if that's a reasonable limitation of the indexing. I suppose I could find out by seeing what is the maximum number of bits I need to index every file on my hard drive. > This only works since TreeIters are invalid once the model changes. Yes, that is fine. We do not need to support persistent iterators. Duncan 