g_list_append performance bug

Bill Gribble grib@linuxdevel.com
02 Apr 2002 07:57:07 -0600


On Tue, 2001-12-04 at 10:02, Linas Vepstas wrote:
> My gut reaction is 'that is the stupidest thing I ever heard,
> what's the point of a doubly linked list if you can't find the tail 
> instantly?'  Isn't this a glib bug?  Did anyone try to report this 
> as a glib bug?  What did the glib people say about it? ???

No, I don't think it's a bug.  'Fixing' it would break basic operations
you can do on a GList : iterating forward and backward to the end of the
list, for example.  Since GLists don't have a special "head" structure
and aren't usually circular, the beginning of the list is noted by a
NULL prev pointer and the end by a NULL next.

Keep in mind that there's no distinction between a "list" and a "list
item" with GLists.  The only way to add a tail pointer without a new
structure type to be the "list head" is to make the list circular, and
then you can't iterate over it because you won't know where the end is. 
If you say you want to keep NULL next at the end but not NULL prev at
the beginning, then you still lose the ability to iterate in reverse,
which is sort of the point of a doubly linked list.  And you would lose
the ability to distinguish between a normal linked list and a circular
linked list, which are sometimes useful and can be implemented using the
current GList. 

The idea with GLists is that if you want a head and tail pointer, you
maintain and update them in the application.  

> I suppose someone would take my head off if I just went into the 
> cvs tree, and fixed it there ... 

Pretty likely, since it would break *everything* :)  It's just not that
big a deal to build the list backwards and reverse it; Lisp programmers
have been doing that as second nature since the dawn of time. 

b.g.