Commit 5302a88538c870028f2623b099c66c800f5cfe68
2014-03-12T11:21:55
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!!!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
diff --git a/src/pqueue.c b/src/pqueue.c
index 172cf43..54a60ca 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 d91dbb0..bcd4eea 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 9fe8a35..7e08c18 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);
+}