Hans Petter Jansson <[EMAIL PROTECTED]> writes: > I'm not sure it's correct to call it an iterator when it's just a > pointer to an internal data structure node. When a node is freed, any > iterator pointing to that node will be freed as well, and that might not > be what the user expects (e.g. she might expect it to point to the item > that takes its place). An attempt to access the iterator after its > corresponding node is removed will result in a crash, and there is also > no way to validate the iterator.
> I don't think more robust iterators are worth the overhead for this data > structure, but would you consider calling them items instead of > iterators? I think it'd avoid some confusion. Well, they are actually _more_ stable than other things we call iterators. GtkTree- and GtkTextIters become invalid as soon as you make _any_ change to the data structure. GSequenceIters only become invalid when you delete the item they point to. Also each GSequence has a special iterator, the 'end' iterator which does not point to any item in the sequence, but instead serves only as a marker. This is consistent with iterator semantics, rather than pointer semantics. Really the way you should think about a GSequence iterator is as a pointer to the *gap* between two items. I do think the docs need a detailed overview of the concepts though. > Also, the internals look slightly suboptimal in places: > > - Perhaps node_free() could be implemented recursively instead of with a > GQueue, to save heap allocations? The reason it uses GQueue for the stack is that the data structure is a splaytree which is not necessarily balanced at all at any point in time. This means freeing it recursively could in the worst case involve O(n) stack use. So I used a GQueue to avoid excessive stack load during free. It may be worthwhile replacing it with a GPtrArray to improve memory use and locality. (In retrospect using a splaytree was probably not a wise decision. A red/black tree might have been better, even though it would have a code-complexity cost in some areas). > - Allocate nodes using GSlice instead of g_new/g_free()? I'd be willing to make this change. Soren _______________________________________________ gtk-devel-list mailing list [email protected] http://mail.gnome.org/mailman/listinfo/gtk-devel-list
