On Fri, Aug 05, 2016 at 08:26:30AM +0000, Eric Wong wrote: > > 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
