Re: EggSequence

[Hans Petter Jansson <hpj novell com>]

On Sat, 2007-01-27 at 03:01 +0100, Soeren Sandmann wrote:

> A long time ago I wrote GSequence for the purpose of speeding up
> Nautilus, which at the time was spending large amounts of maintaining
> sorted lists of file. GSequence is a data structure that implements
> the API of a list, but represents it internally as a balanced binary
> tree. This allows things like g_sequence_insert_sorted() to run in
> time O(log n) instead of O(n).

I really like it. It looks easy to use for simple cases and flexible for
more complex uses. The API is pretty clear. +1 vote for GLib inclusion.

> The datastructure is accessed through iterators. These are stable
> across all manipulations of the sequence, Ie., you can have an
> iterator point to an item, then sort the sequence, and the iterator
> will still point to the same item whereever it ends up.

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.

Also, the internals look slightly suboptimal in places:

- Perhaps node_free() could be implemented recursively instead of with a
GQueue, to save heap allocations?
- Allocate nodes using GSlice instead of g_new/g_free()?

That can be taken care of later, though.

-- 
Hans Petter