On Wed, Oct 12, 2016 at 05:38:14PM +0200, Christian Couder wrote: > On Wed, Oct 12, 2016 at 3:23 AM, Jonathan Tan <jonathantanmy@xxxxxxxxxx> wrote: > > Use singly-linked lists (instead of doubly-linked lists) in trailer to > > keep track of arguments (whether implicit from configuration or explicit > > from the command line) and trailer items. > > > > This change significantly reduces the code length and simplifies the code. > > It's true that the code can be simplified a lot by using a > singly-linked list, but if we already had and used some generic > functions or macros to handle doubly-linked list, I doubt there would > be a significant simplification (as the generic code could not be > deleted in this case). We didn't have such generic macros when you wrote the trailer code originally, but we do now, in list.h (they come from the kernel's doubly-linked list implementation). I used them recently in a series and found them pretty pleasant and complete. Maybe it's worth trying the conversion here to see if it simplifies the code. > > There are now fewer pointers to be manipulated, but most trailer > > manipulations now require seeking from beginning to end, so there might > > be a slight net decrease in performance; however the number of trailers > > is usually small (10 to 15 at the most) so this should not cause a big > > impact. > > By default we append new trailers at the end of the trailer list, so a > singly-linked list is theoretically not well suited at all for > handling trailer lists. > > You say that at most there is a small number of trailers, and that may > be true indeed for the Linux kernel and most projects these days, but > I am not sure it is a good assumption to make in general. I agree. As somebody who has fixed quite a number of accidentally quadratic cases in the number of refs, width of the commit graph, etc, over the years, these things have a way of creeping up or finding pathological cases. You _can_ append to a singly linked list in O(1) if you keep a tail pointer, but I think using list.h would be even nicer. -Peff