Re: [PATCH 4/3] sha1_name: use bsearch_pack() in unique_in_pack()
On 3/24/2018 12:41 PM, René Scharfe wrote: Replace the custom binary search in unique_in_pack() with a call to bsearch_pack(). This reduces code duplication and makes use of the fan-out table of packs. Signed-off-by: Rene Scharfe --- This is basically the same replacement as done by patch 3. Speed is less of a concern here -- at least I don't know a commonly used command that needs to resolve lots of short hashes. Thanks, René! Good teamwork on this patch series. Reviewed-by: Derrick Stolee
Re: [PATCH 4/3] sha1_name: use bsearch_pack() in unique_in_pack()
Am 25.03.2018 um 18:19 schrieb Junio C Hamano: > René Scharfe writes: > >> Replace the custom binary search in unique_in_pack() with a call to >> bsearch_pack(). This reduces code duplication and makes use of the >> fan-out table of packs. >> >> Signed-off-by: Rene Scharfe >> --- >> This is basically the same replacement as done by patch 3. Speed is >> less of a concern here -- at least I don't know a commonly used >> command that needs to resolve lots of short hashes. > > Looks correct. Did you find this by eyeballing, or do you have some > interesting tool you use? I was looking for SHA1 binary searches using something like this: git grep -e '/ 2' -e hashcmp -W --all-match René
Re: [PATCH 4/3] sha1_name: use bsearch_pack() in unique_in_pack()
René Scharfe writes:
> Replace the custom binary search in unique_in_pack() with a call to
> bsearch_pack(). This reduces code duplication and makes use of the
> fan-out table of packs.
>
> Signed-off-by: Rene Scharfe
> ---
> This is basically the same replacement as done by patch 3. Speed is
> less of a concern here -- at least I don't know a commonly used
> command that needs to resolve lots of short hashes.
Looks correct. Did you find this by eyeballing, or do you have some
interesting tool you use?
>
> sha1_name.c | 21 ++---
> 1 file changed, 2 insertions(+), 19 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index 24894b3dbe..0185c6081a 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -150,31 +150,14 @@ static int match_sha(unsigned len, const unsigned char
> *a, const unsigned char *
> static void unique_in_pack(struct packed_git *p,
> struct disambiguate_state *ds)
> {
> - uint32_t num, last, i, first = 0;
> + uint32_t num, i, first = 0;
> const struct object_id *current = NULL;
>
> if (open_pack_index(p) || !p->num_objects)
> return;
>
> num = p->num_objects;
> - last = num;
> - while (first < last) {
> - uint32_t mid = first + (last - first) / 2;
> - const unsigned char *current;
> - int cmp;
> -
> - current = nth_packed_object_sha1(p, mid);
> - cmp = hashcmp(ds->bin_pfx.hash, current);
> - if (!cmp) {
> - first = mid;
> - break;
> - }
> - if (cmp > 0) {
> - first = mid+1;
> - continue;
> - }
> - last = mid;
> - }
> + bsearch_pack(&ds->bin_pfx, p, &first);
>
> /*
>* At this point, "first" is the location of the lowest object
[PATCH 4/3] sha1_name: use bsearch_pack() in unique_in_pack()
Replace the custom binary search in unique_in_pack() with a call to
bsearch_pack(). This reduces code duplication and makes use of the
fan-out table of packs.
Signed-off-by: Rene Scharfe
---
This is basically the same replacement as done by patch 3. Speed is
less of a concern here -- at least I don't know a commonly used
command that needs to resolve lots of short hashes.
sha1_name.c | 21 ++---
1 file changed, 2 insertions(+), 19 deletions(-)
diff --git a/sha1_name.c b/sha1_name.c
index 24894b3dbe..0185c6081a 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -150,31 +150,14 @@ static int match_sha(unsigned len, const unsigned char
*a, const unsigned char *
static void unique_in_pack(struct packed_git *p,
struct disambiguate_state *ds)
{
- uint32_t num, last, i, first = 0;
+ uint32_t num, i, first = 0;
const struct object_id *current = NULL;
if (open_pack_index(p) || !p->num_objects)
return;
num = p->num_objects;
- last = num;
- while (first < last) {
- uint32_t mid = first + (last - first) / 2;
- const unsigned char *current;
- int cmp;
-
- current = nth_packed_object_sha1(p, mid);
- cmp = hashcmp(ds->bin_pfx.hash, current);
- if (!cmp) {
- first = mid;
- break;
- }
- if (cmp > 0) {
- first = mid+1;
- continue;
- }
- last = mid;
- }
+ bsearch_pack(&ds->bin_pfx, p, &first);
/*
* At this point, "first" is the location of the lowest object
--
2.16.3
