On Sun, Jun 09, 2013 at 04:24:35PM -0700, Junio C Hamano wrote:
> Traditionally we used a singly linked list of commits to hold a set
> of in-flight commits while traversing history. The most typical use
> of the list is to add commits that are newly discovered to it, keep
> the list sorted by commit timestamp, pick up the newest one from the
> list, and keep digging. The cost of keeping the singly linked list
> sorted is nontrivial, and this typical use pattern better matches a
> priority queue.
>
> Introduce a commit-queue structure, that can be used either as a
> LIFO stack, or a priority queue. This will be used in the next
> patch to hold in-flight commits during sort-in-topological-order.
Great. You may recall I had a similar patch or year or two back, in an
attempt to fix some of the O(n^2) places (e.g., in fetch-pack's
mark_complete). We ended up dropping it because duplicate removal kept
"n" small enough for common cases, and most of the commit_list users
depend on doing cheap splicing and other linked-list operations.
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.
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.
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.
> + /* 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.
-Peff
--
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