Re: What's cooking in git.git (Aug 2016, #02; Thu, 4)

On Fri, Aug 05, 2016 at 08:26:30AM +0000, Eric Wong wrote:

quoted

I'm not sure which mallocs you mean. I allocate one struct per node,
which seems like a requirement for a linked list. If you mean holding an
extra list struct around an existing pointer (rather than shoving the
prev/next pointers into the pointed-to- item), then yes, we could do
that. But it feels like a bit dirty, since the point of the list is
explicitly to provide an alternate ordering over an existing set of
items.

This pattern to avoid that one malloc-per-node using list_entry
(container_of) is actually a common idiom in the Linux kernel
and Userspace RCU (URCU).  Fwiw, I find it less error-prone and
easier-to-follow than the "void *"-first-element thing we do
with hashmap.

My big problem with it is that it gets confusing when a particular
struct is a member of several lists. We have had bugs in git where
a struct ended up being used in two different lists, but accidentally
using the same "next" pointer.

So you need one "list_head" for each list that your struct may be a part
of. Sometimes that's simple, but it's awkward when the code which wants
the list is different than the code which "owns" the struct. Besides
leaking concerns across modules, the struct may not want to pay the
memory price for storing pointers for all of the possible lists it could
be a member of.

For instance, I think it would be a mistake to convert the current
commit_list code to something like this.

-Peff