From 902bb3645160cae72fe43b5f7f5289968ac01617 Mon Sep 17 00:00:00 2001 From: Jeff King Date: Thu, 19 May 2011 17:34:33 -0400 Subject: bisect: refactor sha1_array into a generic sha1 list This is a generally useful abstraction, so let's let others make use of it. The refactoring is more or less a straight copy; however, functions and struct members have had their names changed to match string_list, which is the most similar data structure. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- sha1-array.c | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100644 sha1-array.c (limited to 'sha1-array.c') diff --git a/sha1-array.c b/sha1-array.c new file mode 100644 index 0000000000..5b75a5a35d --- /dev/null +++ b/sha1-array.c @@ -0,0 +1,43 @@ +#include "cache.h" +#include "sha1-array.h" +#include "sha1-lookup.h" + +void sha1_array_append(struct sha1_array *array, const unsigned char *sha1) +{ + ALLOC_GROW(array->sha1, array->nr + 1, array->alloc); + hashcpy(array->sha1[array->nr++], sha1); + array->sorted = 0; +} + +static int void_hashcmp(const void *a, const void *b) +{ + return hashcmp(a, b); +} + +void sha1_array_sort(struct sha1_array *array) +{ + qsort(array->sha1, array->nr, sizeof(*array->sha1), void_hashcmp); + array->sorted = 1; +} + +static const unsigned char *sha1_access(size_t index, void *table) +{ + unsigned char (*array)[20] = table; + return array[index]; +} + +int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1) +{ + if (!array->sorted) + sha1_array_sort(array); + return sha1_pos(sha1, array->sha1, array->nr, sha1_access); +} + +void sha1_array_clear(struct sha1_array *array) +{ + free(array->sha1); + array->sha1 = NULL; + array->nr = 0; + array->alloc = 0; + array->sorted = 0; +} -- cgit v1.3 From cff38a5e11217dc997c1ffae8d0856023e05554a Mon Sep 17 00:00:00 2001 From: Jeff King Date: Thu, 19 May 2011 17:34:46 -0400 Subject: receive-pack: eliminate duplicate .have refs When receiving a push, we advertise ref tips from any alternate repositories, in case that helps the client send a smaller pack. Since these refs don't actually exist in the destination repository, we don't transmit the real ref names, but instead use the pseudo-ref ".have". If your alternate has a large number of duplicate refs (for example, because it is aggregating objects from many related repositories, some of which will have the same tags and branch tips), then we will send each ".have $sha1" line multiple times. This is a pointless waste of bandwidth, as we are simply repeating the same fact to the client over and over. This patch eliminates duplicate .have refs early on. It does so efficiently by sorting the complete list and skipping duplicates. This has the side effect of re-ordering the .have lines by ascending sha1; this isn't a problem, though, as the original order was meaningless. There is a similar .have system in fetch-pack, but it does not suffer from the same problem. For each alternate ref we consider in fetch-pack, we actually open the object and mark it with the SEEN flag, so duplicates are automatically culled. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- builtin/receive-pack.c | 16 +++++++++++++--- sha1-array.c | 16 ++++++++++++++++ sha1-array.h | 6 ++++++ 3 files changed, 35 insertions(+), 3 deletions(-) (limited to 'sha1-array.c') diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c index 6bb1281666..e1a687ad07 100644 --- a/builtin/receive-pack.c +++ b/builtin/receive-pack.c @@ -10,6 +10,7 @@ #include "remote.h" #include "transport.h" #include "string-list.h" +#include "sha1-array.h" static const char receive_pack_usage[] = "git receive-pack "; @@ -731,14 +732,23 @@ static int delete_only(struct command *commands) return 1; } -static void add_one_alternate_ref(const struct ref *ref, void *unused) +static void add_one_alternate_sha1(const unsigned char sha1[20], void *unused) { - add_extra_ref(".have", ref->old_sha1, 0); + add_extra_ref(".have", sha1, 0); +} + +static void collect_one_alternate_ref(const struct ref *ref, void *data) +{ + struct sha1_array *sa = data; + sha1_array_append(sa, ref->old_sha1); } static void add_alternate_refs(void) { - for_each_alternate_ref(add_one_alternate_ref, NULL); + struct sha1_array sa = SHA1_ARRAY_INIT; + for_each_alternate_ref(collect_one_alternate_ref, &sa); + sha1_array_for_each_unique(&sa, add_one_alternate_sha1, NULL); + sha1_array_clear(&sa); } int cmd_receive_pack(int argc, const char **argv, const char *prefix) diff --git a/sha1-array.c b/sha1-array.c index 5b75a5a35d..b2f47f98fb 100644 --- a/sha1-array.c +++ b/sha1-array.c @@ -41,3 +41,19 @@ void sha1_array_clear(struct sha1_array *array) array->alloc = 0; array->sorted = 0; } + +void sha1_array_for_each_unique(struct sha1_array *array, + for_each_sha1_fn fn, + void *data) +{ + int i; + + if (!array->sorted) + sha1_array_sort(array); + + for (i = 0; i < array->nr; i++) { + if (i > 0 && !hashcmp(array->sha1[i], array->sha1[i-1])) + continue; + fn(array->sha1[i], data); + } +} diff --git a/sha1-array.h b/sha1-array.h index 15d3b6b984..4499b5dad4 100644 --- a/sha1-array.h +++ b/sha1-array.h @@ -15,4 +15,10 @@ void sha1_array_sort(struct sha1_array *array); int sha1_array_lookup(struct sha1_array *array, const unsigned char *sha1); void sha1_array_clear(struct sha1_array *array); +typedef void (*for_each_sha1_fn)(const unsigned char sha1[20], + void *data); +void sha1_array_for_each_unique(struct sha1_array *array, + for_each_sha1_fn fn, + void *data); + #endif /* SHA1_ARRAY_H */ -- cgit v1.3