Better lists? (Was: glib dependency for the X Server)

[Michel Dänzer]

On Tue, 2006-04-04 at 01:01 +0200, Bernardo Innocenti wrote:
> Ian Romanick wrote:
> 
> > Carsten Haitzler (The Rasterman) wrote:
> >> struct _XD_List /** A linked list node */
> >> {
> >>    void    *data; /**< Pointer to list element payload */
> >>    XD_List *next; /**< Next member in the list */
> >>    XD_List *prev; /**< Previous member in the list */
> >>    void    *accounting; /**< Private list accounting info - don't touch */
> >> };
> > 
> > What's disappointing here is that having the do NULL pointer checks on
> > list element pointers was solved 20 years ago on the Amiga.
> 
> I was almost going to say the same...  Are we the only ones who
> find the glib list API so clumsy and error prone?  The only time
> I used them I've spent quite some time debugging memory corruption
> bugs caused by subtle mistakes like forgetting to re-assign the
> list head in glib.
> 
> The strength of Amiga-style intrusive lists are simplicity,
> efficiency and robustness (no memory allocations = no failure).
> The downside is that you need to add nodes inside your data
> structures.  If you need to link a structure into several
> lists at the same time, you'll have to use tricks such as
> container_of() to recover the pointer to the original
> structure (no big deal, really).

As much admiration as I have for the Amiga lists (having started my
Linux and X adventure on my good old APUS Amiga 1200 after more than a
decade of using Amiga OS), I recently read somewhere (most likely on
LWN, possibly referencing LKML) that doubly linked lists have very bad
performance characteristics on current machines. I'm not sure that's
relevant in this case, but I wanted to point it out.


-- 
Earthling Michel Dänzer      |     Debian (powerpc), X and DRI developer
Libre software enthusiast    |   http://svcs.affero.net/rm.php?r=daenzer