Re: EggSequence

[Soeren Sandmann <sandmann daimi au dk>]

Hans Petter Jansson <hpj novell com> 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