Re: EggSequence

[Hans Petter Jansson <hpj novell com>]

On Sun, 2007-01-28 at 01:50 +0100, Soeren Sandmann wrote:
> Hans Petter Jansson <hpj novell com> writes:

> > 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.

Fair enough.

> 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).

Could we change the implementation (say, to RBT) without introducing API
changes, in case it turns out to be a performance problem later? If not,
I'd rather it be changed before we commit to it.

-- 
Hans Petter