On Wed, Oct 12, 2016 at 05:38:14PM +0200, Christian Couder wrote:

> On Wed, Oct 12, 2016 at 3:23 AM, Jonathan Tan <jonathanta...@google.com> 
> 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

> > 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.


Reply via email to