Re: [PATCH v2 2/4] commit-queue: LIFO or priority queue of commits

Jeff King [off-list ref] 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:

quoted

+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.

quoted

+	/* 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.