[PATCH] Implement doubly-linked list

[Rob Landley]

On Thursday 01 June 2006 2:18 pm, Yann E. MORIN wrote:
> On Thursday 01 June 2006 050, Rob Landley wrote:
> > On Wednesday 31 May 2006 6:22 pm, Yann E. MORIN wrote:
> > > Here is at last my implementation of doubly-linked lists.
> >
> > What uses do you have in mind for this?
>
> Well, it seems some applets makes use of doubly-linked lists. At least
> modprobe and ed do. Maybe others as well. See these two messages:
> http://www.busybox.net/lists/busybox/2006-May/021645.html
> http://www.busybox.net/lists/busybox/2006-May/021661.html

I'm offline right now (catching up with email on another interminable 
Pittsburgh bus ride), but ed can still be removed and I haven't looked at 
modprobe.

You can do anything with a singly linked list you can with a doubly linked 
one, it's just slower in places.  But neither applet has any speed-critical 
sections I'm aware of...

> What annoys me is that some applets makes use of linked lists, and each has
> its own implementation. Gathering (singly- or doubly-) linked list
> management in a common place seems sensible to me, so that one does'nt have
> to re-invent the wheel every time. And because it is a good candidate for
> code size reduction as well.

Code size reduction yay.  Penalizing existing applets, not yay.

> > It's an extra 4 bytes per node, plus the code to deal with it.  Having
> > _both_ singly and doubly linked lists makes little sense, but having
> > things that only need singly linked lists be doubly linked makes little
> > sense either...
>
> Yes I do agree. What would be the best practice?
>  - only doubly-linked lists for all:
>       -> a 4-byte impact at run-time per node
>       -> a small impact in code size (35 bytes)
>  - both types of lists:
>       -> no run-time impact, as nodes are the strict necessary size.
>       -> a bigger, but not huge, impact on code size.

3) Rewrite the doubly linked list bits to use singly linked lists?

I don't even know what's involved yet, but if I get some time I'll take a 
look.

> > llist_get_front() will segfault if *head is NULL.
>
> Shame on me. Note for tonight: bed time is 10PM, no later. :-]

Oh I've done worse.  This is normal review. :)

> > -		free(*head);
> > +		if (ENABLE_FEATURE_CLEAN_UP)
> > +			free(*head);
> > We don't know who's calling us, it could be something long-running
> > (httpd?  Or possibly what httpd _should_ be doing?)  Thus the free isn't
> > optional.
>
> That was not my understanding of FEATURE_CLEAN_UP. I didn't understand that
> we should take into conideration wether the applet was blindly fast (ls)
> or long-running (httpd). But that makes sense.

It's more a question of "when is leaking ok?"  ls -lR can actually be a bad 
place for making a free optional, because we don't know how big a filesystem 
we're going to operate on.  If you ls -lR a big nfs mount on a small embedded 
system, you shouldn't trigger the OOM killer.

But if you know you're allocating a finite amount of memory and you know when 
it goes away if you don't free it, explicitly freeing it can become optional 
to save code size.

> > And yeah, I finally found the chunk you were referring to and it's a case
> > of the variable being #ifdefed out and the code barfing on an undeclared
> > variable before it gets as far as dead code elimination.  The two
> > techniques don't mix...
>
> Yep. Sounds so blatently obvious when you explain things! :-)
>
> So what next?

Let's hold off on this cleanup until the 1.3 timeframe.  Possibly having 
doubly linked list infrastructure is a good thing, but I want to identify 
more users and make sure they can't easily be rewritten to use our existing 
lists.  (There are all sorts of singly linked list users who aren't using 
llist_t, I've converted a couple recently...)

> Regars,
> Yann E. MORIN.

Rob
-- 
Never bet against the cheap plastic solution.