g_list_append performance bug

[Havoc Pennington]

linas@linas.org (Linas Vepstas) writes: 
> But there's a problem with that!  glib does not give you an O(1) way
> of being able to maintain the pointer to the tail!  It can't be done!
> There is no way to maintain the tail pointer in your application, except
> by searching for it, which makes it totally pointless to maintain a
> tail pointer! 

Yeah, it can be done. There's even an example in my book someplace.
 
> The point is that no sane double-linked list is ever implenmented in
> this way.  Its just not normal; glib is just plain crippled.   Its 
> current design offers no advantages that I can think of, and has 
> disadvantages compared to 'normal' doubly-linked list designs.

GLib was originally written by people who liked Lisp. ;-) Remember
that Gimp was scriptable in Guile and all that stuff.

> Anf finally, a fix can be made that is not likely to impact most
> users of glist ...

That's not really good enough; we'd need a fix that definitely would
not impact any of them.

The 2.2 plan is to introduce a "circular list" data type called GRing
or something. Add implementation suggestions here:
  http://bugzilla.gnome.org/show_bug.cgi?id=59431

If you mail suggestions today they'll be lost by the time someone's
actually doing this, so get them stuck to the bug.

Havoc