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

From: David Kastrup <dak@gnu.org>
Date: Jul 14, 2014, 11:02 UTC
Message-ID: <87tx6k5hjz.fsf@fencepost.gnu.org>
In-Reply-To: <20140714054021.GA4422@sigill.intra.peff.net>

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