Jeff King <peff@xxxxxxxx> 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 majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html