[PATCH] Implement doubly-linked list

[Rob Landley]

On Monday 05 June 2006 2:43 pm, Yann E. MORIN wrote:
> > > Yes I do agree. What would be the best practice?
>
> [--SNIP--]
>
> > 3) Rewrite the doubly linked list bits to use singly linked lists?
>
> Yep, but that would require more functions (or macros?) to easily get to
> the previous element without each time hand-rolling-back the list.

Not brain surgery either.  Something like...

llist_t *llist_prev(llist_t **list_head, llist_t *this)
{
  llist_t *prev=*llist_head;
  while (prev && prev->link != this) prev = prev->link;
  return prev;
}

Not the world's most efficient code, but it's very small.  I'm trying to 
figure out whether it's worth the extra test to avoid traversing the whole 
list for the last entry...

> > I don't even know what's involved yet, but if I get some time I'll take a
> > look.
>
> Your enlighten regard on this would be indeed appreciated! At least some
> global directions as to what is wanted/needed.

Doubly linked lists are _always_ a performance hack.  The question is, do we 
have anything that cares enough?  I haven't seen an example yet...

> > > > 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. :)
>
> Oh, you didn't, did you? Behold! The maintainer is not almighty! Hehe!
> :-)))

All the time.  Recently, we have:

http://busybox.net/downloads/patches/svn-15207.patch
And
http://busybox.net/downloads/patches/svn-15171.patch


> [--SNIP: FEATURE_CLEAN_UP explanations--]
>
> Again, it sounds so obvious once said this way!

I've been programming since I was 12 years old.  I've seen just about all the 
common mistakes because I've _made_ them, at least once...

> > 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...)
>
> A job I've started, but which is extremely time-consuming...

Join the club. :)

> I'll share my 
> list as soon as it is in a shape suitable for discussion. For now, I've
> identified 29 applets using linked lists, totalling 43 linked lists (all
> sorts, singly- or doubly-linked, plain structures, size-and-void*, ...),
> not counting e2fsprogs, shells and devfsd. But the job isn't yet finished,
> I've only searched for something called 'next' !!!

One thing I've been sort of pondering is whether we can teach our current 
llist_t infrastructure to use structures that have a next pointer as their 
first element.  In _theory_ we can typecast any structure that starts with a 
next pointer to llist_t, and it should work for traversing said next pointer.  
(The compiler is _not_ allowed to reorder structure members, and we told it 
not to insert any unnecessary padding.)

I'm not sure how it would work out.  Where would it benefit?  Is it worth the 
trouble?  Hasn't gone beyond the vague idea at this point...

Possibly we should teach _every_ list data structure to have its allocation be 
inline instead of a data pointer.  (With a wrapper to strdup strings, which 
is a common thing to do.)  It would save memory, and it would save 
allocations which fragment memory.

Dunno.

> Once I've managed a more complete listing of lists, I'll list what kind of
> lists are used, how many times, etc... and post for comments.
>
> But I agree that will have to wait for the 1.3.x timeframe!
>
> Regards,
> Yann E. MORIN.

Rob
-- 
Never bet against the cheap plastic solution.