Re: [PATCH 2/3] prio-queue: add prio_queue_replace()

From: Jeff King <peff@peff.net>
Date: Jul 19, 2025, 07:02 UTC
Message-ID: <20250719070229.GF705356@coredump.intra.peff.net>
In-Reply-To: <4ed087c9-0229-4219-8cbd-55f9ee79ca35@web.de>

On Thu, Jul 17, 2025 at 11:20:53AM +0200, René Scharfe wrote:

Show 11 quoted lines

> > I thought about building this optimization into prio_queue_get(), but
> > that would require prio_queue_peek() and prio_queue_put() to be adjusted
> > as well and all prio_queue users would have to be either made aware of
> > the not-fully-heapified state, or prevented from accessing prio_queue
> > properties like .nr and .array.
> 
> Here's what that would like like.  .nr and .array elements are kept
> consistent at all times, but the root item is not in heap order after a
> prio_queue_get().  That's good enough to enumerate all prio_queue items
> like commit-reach.c::queue_has_nonstale() or
> negotiator/skipping.c::push_parent() do.

Hmm, I agree that _probably_ we'd be fine as long as .nr and .array were always consistent. It does make me feel a bit dirty to violate the heap property in a way that callers can see. I guess the argument in favor of it would be:

  - if you are directly walking over all elements, then almost all
    ordering is out the window. Yes, the root item is supposed to be the
    min, but in a heap the rest of the elements won't be sorted.

  - if you really want things in order from a heap, you'll be calling
    the get() or peek() accessors. And that gives us an opportunity to
    lazily put things in order.

I guess one alternative would be to make the array private and require some kind of foreach accessor. True struct-field privacy in C sucks. You have to hide behind a pointer, so there's runtime cost, plus iteration requires a clunky callback rather than a loop. I guess we could call it "array_" or something, and provide a foreach macro.

I dunno. I'm on the fence.

-Peff