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 _______________________________________________ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users