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

[Bernardo Innocenti]

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

I'm attaching another variation of mine.  This version avoids
the hack of putting two overlapping nodes in the list head
because it could trigger bugs with alias analysis with modern
compilers.

Sorry for using macros: this code was originally written for
small embedded systems, where some proprietary compilers still
can't do proper constant propagation after inlining.  Feel free
to convert everything to inline functions and relicense it as
MIT/X11 if you need.

-- 
  // Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/  http://www.develer.com/

-------------- next part --------------
A non-text attachment was scrubbed...
Name: list.h
Type: text/x-chdr
Size: 8655 bytes
Desc: not available
URL: <http://lists.x.org/archives/xorg/attachments/20060404/cd7946db/attachment.h>