Jeff King <peff@xxxxxxxx> writes:
> Anyway, since this isn't yielding any performance benefit, I'm not going
> to go down that route. But stability of the queue is something that we
> need to consider if we ever do replace commit_list with a different data
> structure.
>
> Here's the patch to make the existing priority queue stable (by wasting
> space) in case we ever want to use it.
Thanks for being thorough and showing a good analysis.
If we want stability, the space to hold insertion counter is not
"wasted", by the way.
I actually think the generic "queue" implementation may want to
handle elements that are not just single pointers. Just like
qsort() is not about sorting an array of pointers but it is about
sorting an array of elements of caller specified size, perhaps
"queue" can hold elements of size the caller specified (set in stone
when the queue is initialized).
Then, a caller that wants a stable priority queue of commits can
tell the queue to manage "struct { struct commit *c; int gen; }",
use the "gen" field for stability in its comparison callback, etc.,
while a caller that does not need stability can tell the queue to
manage "struct commit *". That way, the generic queue layer does
not have to worry about wasting the insertion counter space, no?
--
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