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

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.

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

Reply via email to