Jeff King <peff@xxxxxxxx> wrote: > On Fri, Aug 05, 2016 at 08:02:31AM +0000, Eric Wong wrote: > > > > I just introduced another doubly-linked list in [1]. It adds some MRU > > > features on top of the list, but it could in theory be built on top of a > > > generic doubly-linked list. > > > > Yes, and you'd be avoiding the extra mallocs and be able to use > > list_entry (aka `container_of`) so it could be faster, too. > > 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. > It also doesn't make a big difference for my use case. All I really care > about is the speed of delete-from-middle-and-insert-at-front, which is > trivially O(1) and involves no mallocs. > > > I was thinking packed_git could also be a doubly-linked list > > anyways since it would allow easier removal of unlinked pack > > entries. My use case would be long-running "cat-file --batch" > > processes being able to detect unlinked packs after someone > > else runs GC. > > We never remove packed_git structs, but it is not because of the list > data structure. We may be holding open mmaps to packs that are deleted > and continue using them. And in some cases other code may even hold > pointers to our packed_git structs. So you'd have to figure out some > memory ownership questions first. Yes, it's easier to replace a running process once in a while :) -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html