sha1-lookup: handle duplicates in sha1_pos()

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.  Simply remove the erroneous check.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
Acked-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/sha1-lookup.c b/sha1-lookup.c
index 2dd851598a9d1444fe479d149ee3c2cb93e8cba9..5f069214d9060da8ceb001e6c037607c1d0096bf 100644 (file)
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -84,8 +84,6 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
                                die("BUG: assertion failed in binary search");
                        }
                }
                                die("BUG: assertion failed in binary search");
                        }
                }

-               if (18 <= ofs)
-                       die("cannot happen -- lo and hi are identical");

        }
 
        do {
        }
 
        do {

diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
index 06549656c8d9ea3a35149ca42399bd6f83ec1d54..50b31ffe756658dfa8ce435381ad7f48fee91462 100755 (executable)
--- a/t/t0064-sha1-array.sh
+++ b/t/t0064-sha1-array.sh
@@ -71,4 +71,24 @@ test_expect_success 'lookup non-existing entry with duplicates' '
        test "$n" -lt 0
 '
 
        test "$n" -lt 0
 '
 

+test_expect_success 'lookup with almost duplicate values' '
+       {
+               echo "append 5555555555555555555555555555555555555555" &&
+               echo "append 555555555555555555555555555555555555555f" &&
+               echo20 lookup 55
+       } | test-sha1-array >actual &&
+       n=$(cat actual) &&
+       test "$n" -eq 0
+'
+
+test_expect_success 'lookup with single duplicate value' '
+       {
+               echo20 append 55 55 &&
+               echo20 lookup 55
+       } | test-sha1-array >actual &&
+       n=$(cat actual) &&
+       test "$n" -ge 0 &&
+       test "$n" -le 1
+'
+

 test_done
 test_done