Fix pqueue sort boundary condition bug

If the pqueue comparison fn returned just 0 or 1 (think "a<b")
then the sort order of returned items could be wrong because there
was a "< 0" that really needed to be "<= 0".  Yikes!!!

3 files changed, 91 insertions, 1 deletions

diff --git a/src/pqueue.c b/src/pqueue.c
index 172cf43d5..54a60ca04 100644
--- a/src/pqueue.c
+++ b/src/pqueue.c
@@ -68,7 +68,7 @@ static void pqueue_down(git_pqueue *pq, size_t el)
 			kid_el += 1;
 		}
 
-		if (pq->_cmp(parent, kid) < 0)
+		if (pq->_cmp(parent, kid) <= 0)
 			break;
 
 		pq->contents[el] = kid;
diff --git a/tests/core/pqueue.c b/tests/core/pqueue.c
index d91dbb0cd..bcd4eea9f 100644
--- a/tests/core/pqueue.c
+++ b/tests/core/pqueue.c
@@ -95,3 +95,34 @@ void test_core_pqueue__max_heap_size(void)
 	git_pqueue_free(&pq);
 
 }
+
+static int cmp_ints_like_commit_time(const void *a, const void *b)
+{
+	return *((const int *)a) < *((const int *)b);
+}
+
+void test_core_pqueue__interleaved_pushes_and_pops(void)
+{
+	git_pqueue pq;
+	int i, j, *val;
+	static int commands[] =
+		{ 6, 9, 8, 0, 5, 0, 7, 0, 4, 3, 0, 0, 0, 4, 0, 2, 0, 1, 0, 0, -1 };
+	static int expected[] =
+		{ 9, 8, 7, 6, 5, 4, 4, 3, 2, 1, -1 };
+
+	cl_git_pass(git_pqueue_init(&pq, 0, 10, cmp_ints_like_commit_time));
+
+	for (i = 0, j = 0; commands[i] >= 0; ++i) {
+		if (!commands[i]) {
+			cl_assert((val = git_pqueue_pop(&pq)) != NULL);
+			cl_assert_equal_i(expected[j], *val);
+			++j;
+		} else {
+			cl_git_pass(git_pqueue_insert(&pq, &commands[i]));
+		}
+	}
+
+	cl_assert_equal_i(0, git_pqueue_size(&pq));
+	git_pqueue_free(&pq);
+}
+
diff --git a/tests/revwalk/basic.c b/tests/revwalk/basic.c
index 9fe8a350b..7e08c1840 100644
--- a/tests/revwalk/basic.c
+++ b/tests/revwalk/basic.c
@@ -290,3 +290,62 @@ void test_revwalk_basic__push_all(void)
 	/* git rev-list --count --all #=> 15 */
 	cl_assert_equal_i(15, i);
 }
+
+/*
+* $ git rev-list br2 master e908
+* a65fedf39aefe402d3bb6e24df4d4f5fe4547750
+* e90810b8df3e80c413d903f631643c716887138d
+* 6dcf9bf7541ee10456529833502442f385010c3d
+* a4a7dce85cf63874e984719f4fdd239f5145052f
+* be3563ae3f795b2b4353bcce3a527ad0a4f7f644
+* c47800c7266a2be04c571c04d5a6614691ea99bd
+* 9fd738e8f7967c078dceed8190330fc8648ee56a
+* 4a202b346bb0fb0db7eff3cffeb3c70babbd2045
+* 5b5b025afb0b4c913b4c338a42934a3863bf3644
+* 8496071c1b46c854b31185ea97743be6a8774479
+*/
+
+void test_revwalk_basic__mimic_git_rev_list(void)
+{
+   git_oid oid;
+
+   revwalk_basic_setup_walk(NULL);
+   git_revwalk_sorting(_walk, GIT_SORT_TIME);
+
+   cl_git_pass(git_revwalk_push_ref(_walk, "refs/heads/br2"));
+   cl_git_pass(git_revwalk_push_ref(_walk, "refs/heads/master"));
+   cl_git_pass(git_oid_fromstr(&oid, "e90810b8df3e80c413d903f631643c716887138d"));
+   cl_git_pass(git_revwalk_push(_walk, &oid));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "a65fedf39aefe402d3bb6e24df4d4f5fe4547750"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "e90810b8df3e80c413d903f631643c716887138d"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "6dcf9bf7541ee10456529833502442f385010c3d"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "a4a7dce85cf63874e984719f4fdd239f5145052f"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "be3563ae3f795b2b4353bcce3a527ad0a4f7f644"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "c47800c7266a2be04c571c04d5a6614691ea99bd"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "9fd738e8f7967c078dceed8190330fc8648ee56a"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "4a202b346bb0fb0db7eff3cffeb3c70babbd2045"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "5b5b025afb0b4c913b4c338a42934a3863bf3644"));
+
+   cl_git_pass(git_revwalk_next(&oid, _walk));
+   cl_assert(!git_oid_streq(&oid, "8496071c1b46c854b31185ea97743be6a8774479"));
+
+   cl_git_fail_with(git_revwalk_next(&oid, _walk), GIT_ITEROVER);
+}