[PATCH/RFH 0/3] stable priority-queue

[Jeff King <peff@peff.net>]

As Junio and I discussed earlier in [1], this series makes the
prio_queue struct stable with respect to object insertion (which in turn
means we can use it to replace commit_list in more places).

I think everything here is correct, but the second commit fails the
final test in t5539. I think the test is just flaky (hence the RFH and
cc to Duy).

That test creates some unrelated commits in two separate repositories,
and then fetches from one to the other. Since the commit creation
happens in a subshell, the first commit in each ends up with the same
test_tick value. When fetch-pack looks at the two root commits
"unrelated1" and "new-too", the exact sequence of ACKs is different
depending on which one it pulls out of the queue first.

With the current code, it happens to be "unrelated1" (though this is not
at all guaranteed by the prio_queue data structure, it is deterministic
for this particular sequence of input). We see the ready-ACK, and the
test succeeds.

With the stable queue, we reliably get "new-too" out (since it is our
local tip, it is added to the queue before we even talk to the remote).
We never see a ready-ACK, and the test fails due to the grep on the
TRACE_PACKET output at the end (the fetch itself succeeds as expected).

I'm really not quite clear on what's supposed to be going on in the
test. I can make it pass with:

diff --git a/t/t5539-fetch-http-shallow.sh b/t/t5539-fetch-http-shallow.sh
index 94553e1..b461188 100755
--- a/t/t5539-fetch-http-shallow.sh
+++ b/t/t5539-fetch-http-shallow.sh
@@ -54,6 +54,7 @@ EOF
 test_expect_success 'no shallow lines after receiving ACK ready' '
 	(
 		cd shallow &&
+		test_tick &&
 		for i in $(test_seq 15)
 		do
 			git checkout --orphan unrelated$i &&

which just bumps the timestamp for the unrelated* commits (so that they
are always more recent than "new-too" and get picked first). I'm not
sure if that is too hacky, or if there's a more robust way to set up the
test.

Anyway, here are the patches.

  [1/3]: prio-queue: factor out compare and swap operations
  [2/3]: prio-queue: make output stable with respect to insertion
  [3/3]: paint_down_to_common: use prio_queue

-Peff

[1] http://thread.gmane.org/gmane.comp.version-control.git/252472/focus=252475