[PATCH] Implement doubly-linked list
Yann E. MORIN
yann.morin.1998 at anciens.enib.fr
Thu Jun 1 18:18:41 UTC 2006
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
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.
> 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.
> > ---
> > + USE_FEATURE_DLLIST (
[--SNIP code portion--]
> > Because if I use "if (ENABLE_FEATURE_DLLIST) " then gcc barfs on the next
> > line. Comments?
> You gave me three patches and didn't say which one had the hunk you were
> talking about.
Sorry, I thought it was clear enough I was speaking of the third patch.
> +extern ATTRIBUTE_ALWAYS_INLINE void *llist_get_front(llist_t **elm);
> Ok, _how_? This is a declaration but not a definition. The body of the code
> ain't here. The body is in a separate .c file that is compiled by itself to
> make a .o file. What's supposed to inline it, the linker? (Unless nobody
> outside of llist.c is ever going to call it...)
I should go to bed earlier... You're absolutely right. My bad. Bahhhhh!
> Besides, we should let gcc make the inlining decisions. Programmers have a
> history of sucking at this, over time.
I was thinking of this, but wanted to be sure. Bah...
> llist_get_front() will segfault if *head is NULL.
Shame on me. Note for tonight: bed time is 10PM, no later. :-]
> - 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.
> +#ifdef CONFIG_FEATURE_DLLIST
> + struct llist_s *prev;
> +#endif
> A) That's the sort of thing USE() macros are for.
> B) When the existence of variables is #ifdefed out, the code that plays with
[--SNIP--]
> 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?
Regars,
Yann E. MORIN.
--
.-----------------.--------------------.------------------.--------------------.
| Yann E. MORIN | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +0/33 662376056 | Software Designer | \ / CAMPAIGN | ^ |
| --==< °_° >==-- °---.----------------: X AGAINST | /e\ There is no |
| web: ymorin.free.fr | SETI at home 3808 | / \ HTML MAIL | """ conspiracy. |
°---------------------°----------------°------------------°--------------------°
More information about the busybox
mailing list