Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

2013-08-23 Thread Junio C Hamano
Jeff King p...@peff.net writes: Furthermore, we know that one of our endpoints must be the edge of the run of duplicates. For example, given this sequence: idx 0 1 2 3 4 5 key A C C C C D If we are searching for B, we might hit the duplicate run at lo=1, hi=3 (e.g., by first mi=3, then

Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

2013-08-23 Thread Jeff King
On Fri, Aug 23, 2013 at 09:41:57AM -0700, Junio C Hamano wrote: Jeff King p...@peff.net writes: Furthermore, we know that one of our endpoints must be the edge of the run of duplicates. For example, given this sequence: idx 0 1 2 3 4 5 key A C C C C D If we are searching for

Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

2013-08-23 Thread Nicolas Pitre
On Fri, 23 Aug 2013, Jeff King wrote: Making the deltas was considerably less elegant, since we cannot provoke pack-objects to pick arbitrary deltas (and it will not even try to delta tiny objects, anyway, which would bloat our samples). I ended up with the horrible patch below. We _could_

Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

2013-08-23 Thread Jeff King
On Fri, Aug 23, 2013 at 02:54:19PM -0400, Nicolas Pitre wrote: On Fri, 23 Aug 2013, Jeff King wrote: Making the deltas was considerably less elegant, since we cannot provoke pack-objects to pick arbitrary deltas (and it will not even try to delta tiny objects, anyway, which would bloat

Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

2013-08-23 Thread Johannes Sixt
Am 23.08.2013 01:14, schrieb Jeff King: +++ b/t/t5308-pack-detect-duplicates.sh @@ -0,0 +1,73 @@ +#!/bin/sh + +test_description='handling of duplicate objects in incoming packfiles' +. ./test-lib.sh +. ../lib-pack.sh This should be . $TEST_DIRECTORY/lib-pack.sh to support running tests with

Re: [PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

2013-08-23 Thread Jeff King
On Fri, Aug 23, 2013 at 09:41:39PM +0200, Johannes Sixt wrote: Am 23.08.2013 01:14, schrieb Jeff King: +++ b/t/t5308-pack-detect-duplicates.sh @@ -0,0 +1,73 @@ +#!/bin/sh + +test_description='handling of duplicate objects in incoming packfiles' +. ./test-lib.sh +. ../lib-pack.sh This

[PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

2013-08-23 Thread Jeff King
The sha1_entry_pos function tries to be smart about selecting the middle of a range for its binary search by looking at the value differences between the lo and hi constraints. However, it is unable to cope with entries with duplicate keys in the sorted list. We may hit a point in the search

[PATCH 2/6] sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP

2013-08-22 Thread Jeff King
The sha1_entry_pos function tries to be smart about selecting the middle of a range for its binary search by looking at the value differences between the lo and hi constraints. However, it is unable to cope with entries with duplicate keys in the sorted list. We may hit a point in the search