Re: [Chicken-users] another proposal to modify runtime.c

[Alan Post]

On Wed, Sep 28, 2011 at 01:41:03PM +0200, Jörg F. Wittenberger wrote:
> I can't resist to propose another minor code improvement.
> 
> For this one I even recall where I learned the trick: early in my CS
> studies, we been taken to analyse how we could do better than the
> straight forward implementation of double linked lists.
> (Which would be the implementation of e.g., the finalizer_list
> in runtime.c)
> 
> The idea is: unlinking requires too many conditionals.
> The solution would be: you don't want to keep a pointer to the list
> elements (which in case of the empty list would be NULL) as root.
> Instead you use a static list node (thereby wasting the unused memory
> for the payload).  As end-of-list marker you don't use NULL, but
> the address of that root node.  You initialize the root nodes
> previous and next to the address of the root node.
> 
> Now you can save all those conditionals.  Unlinking is turned into
> two straight forward updates of the previous and next pointers
> handing on the corresponding fields of the node.
> 
> Saves a few line, conditional and looks IMHO more clever.
> Though I'm biased by the abovementioned history.
> 
> Find the diff attached.
> 
> /Jörg
> 
> 

I've heard this called a "dummy head" list.  I didn't think people
wrote linked list code any other way...  You use one extra cons
cell and remove all the beginning of list checks you'd otherwise
require.

I thought this part came standard.  ;-)  Good catch.  It's a trick
I've been able to use well outside of C programming.  Heck, I think
my egg, genturfahi, uses this one somewhere.

-Alan
-- 
.i ma'a lo bradi cu penmi gi'e du