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
