Am 01.10.2014 um 12:50 schrieb Jeff King:
On Wed, Oct 01, 2014 at 11:43:21AM +0200, René Scharfe wrote:
If the first 18 bytes of the SHA1's of all entries are the same then
sha1_pos() dies and reports that the lower and upper limits of the
binary search were the same that this wasn't supposed to happen. This
is wrong because the remaining two bytes could still differ.
Furthermore: It wouldn't be a problem if they actually were the same,
i.e. if all entries have the same SHA1. The code already handles
duplicates just fine otherwise. Simply remove the erroneous check.
Yeah, I agree that assertion is just wrong.
Regarding duplicates: in sha1_entry_pos, we had to handle the "not
found" case specially, because we may have found the left-hand or
right-hand side of a run of duplicates, and we want to return the
correct slot where the new item would go (see the comment added by
171bdac). I think we don't have to deal with that here, because we are
just dealing with the initial "mi" selection. The actual binary search
is plain-vanilla, which handles that case just fine.
I wonder if it is worth adding a test (you test only that "not found"
produces a negative index, but not which index). Like:
api-sha1-array.txt says about sha1_array_lookup: "If not found, returns
a negative integer", and that's what the test checks.
I actually like that the value is not specified for that case because no
existing caller actually uses it and it leaves room to implement the
function e.g. using bsearch(3).
I agree that adding a "lookup non-existing entry with duplicates" test
would make t0064 more complete, though.
diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
index 3fcb8d8..7781129 100755
--- a/t/t0064-sha1-array.sh
+++ b/t/t0064-sha1-array.sh
@@ -42,12 +42,12 @@ test_expect_success 'lookup' '
'
test_expect_success 'lookup non-existing entry' '
+ echo -1 >expect &&
{
echo20 "append " 88 44 aa 55 &&
echo20 "lookup " 33
} | test-sha1-array >actual &&
- n=$(cat actual) &&
- test "$n" -lt 0
+ test_cmp expect actual
'
test_expect_success 'lookup with duplicates' '
@@ -61,6 +61,17 @@ test_expect_success 'lookup with duplicates' '
test "$n" -le 3
'
+test_expect_success 'lookup non-existing entry with duplicates' '
+ echo -5 >expect &&
+ {
+ echo20 "append " 88 44 aa 55 &&
+ echo20 "append " 88 44 aa 55 &&
+ echo20 "lookup " 66
+ } | test-sha1-array >actual &&
+ test_cmp expect actual
+'
+
+
test_expect_success 'lookup with almost duplicate values' '
{
echo "append 5555555555555555555555555555555555555555" &&
--
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