Jeff King <> writes:

> It may be worth looking again for other places to use this over
> commit_list, but even the caller you are introducing here justifies its
> presence.

The next candidate is paint-down-to-common, probably.

> Also, I wrote some basic tests to cover the priority queue as a unit. I
> can rebase them on your commit if you are interested.

It would be great.

> A few comments on the code itself:
>> +void commit_queue_put(struct commit_queue *queue, struct commit *commit)
> Is it worth making this "struct commit *" a void pointer, and handling
> arbitrary items in our priority queue? The compare function should be
> the only thing that dereferences them.
> I do not have any non-commit priority queue use in mind, but I do not
> think it adds any complexity in this case.

I didn't either (and still I don't think of one), but I agree that
the implementation can be reused for pq of any type, as long as it
is a pointer to struct.

>> +    /* Bubble up the new one */
>> +    for (ix = queue->nr - 1; ix; ix = parent) {
>> +            parent = (ix - 1) / 2;
>> +            if (compare(queue->array[parent], queue->array[ix],
>> +                        queue->cb_data) < 0)
>> +                    break;
> In my implementation, I stopped on "compare() <= 0". It is late and my
> mind is fuzzy, but I recall that heaps are never stable with respect to
> insertion order, so I don't think it would matter.

It would matter in the sense that we cannot replace linked-list, if
the caller wants stability.  It is more like "we cannot do anything
about it" than "it would not matter".

We can make each queue element a pair of <pointer to payload,
insertion counter>, and tiebreak using the insertion order, if the
callers want the same stability as linked-list implementation, but
I tend to think it really matters.

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to
More majordomo info at

Reply via email to