Re: [PATCH/RFH 0/3] stable priority-queue

[David Kastrup <dak@gnu.org>]

Jeff King <peff@peff.net> writes:

> As Junio and I discussed earlier in [1], this series makes the
> prio_queue struct stable with respect to object insertion (which in turn
> means we can use it to replace commit_list in more places).

I don't think that this makes sense in general since it assumes the
appropriate fallback behavior to be FIFO.  Depending on the use case, it
might be the other way round, or something else (like topology-based)
entirely.

commit_list may be unsuitable as such for intermingled addition of
unsorted and extraction of sorted elements (the general use case for
priority queues).

I see that struct commit already contains an integer field called
"index", assigned sequentially, which might conceivably be used for
tie-breaking independent from the actual prio_queue use at no extra
cost.

The resulting order will of course be somewhat arbitrary in a different
way, but at least will correspond to the order the commits have been
discovered/generated, so they should still exhibit a more topological
relation than what prio_queue does without further help.

-- 
David Kastrup