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:
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