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

[Carsten Haitzler (The Rasterman)]

On Tue, 04 Apr 2006 01:01:25 +0200 Bernardo Innocenti <bernie at develer.com>
babbled:

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

i've never forgotten - to date, and so i've never worried about it.

> The strength of Amiga-style intrusive lists are simplicity,
> efficiency and robustness (no memory allocations = no failure).

i have another list internally that puts the list elements in the head of the
object using it - but this limits the object to living in 1 list only. other
lists that REFERENCE the object need an alloc one way or the other.

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

sure - i do that. i simply provided a generic list impl that looks & feels very
much like g_lists for the purpose of providing an existing debugged
implementation of a data struct that was needed. :)

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


-- 
------------- Codito, ergo sum - "I code, therefore I am" --------------
The Rasterman (Carsten Haitzler)    raster at rasterman.com
裸好多
Tokyo, Japan (東京 日本)