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

From: Jeff King <[email-masked]>
Date: Sat, 19 Jul 2025 03:02:29 -0400

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

> > 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