[PATCH 1/5] fetch-pack: sort incoming heads

From: Jeff King <peff@peff.net>
Date: May 21, 2012, 22:17 UTC
Message-ID: <20120521221702.GA22914@sigill.intra.peff.net>
In-Reply-To: <20120521221417.GA22664@sigill.intra.peff.net>

There's no reason to preserve the incoming order of the heads we're requested to fetch. By having them sorted, we can replace some of the quadratic algorithms with linear ones.

Signed-off-by: Jeff King <peff@peff.net>
---
I actually wouldn't be surprised if these were typically sorted already,
as they frequently come from the ref-mapping functions, which in turn
process the lists we get from the remote. But we also might get random
junk on the command-line of fetch-pack, so we need to be careful.

 builtin/fetch-pack.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index 10db15b..380743e 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -1057,6 +1057,11 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
 	return ret;
 }
 
+static int compare_heads(const void *a, const void *b)
+{
+	return strcmp(*(const char **)a, *(const char **)b);
+}
+
 struct ref *fetch_pack(struct fetch_pack_args *my_args,
 		       int fd[], struct child_process *conn,
 		       const struct ref *ref,
@@ -1076,6 +1081,8 @@ struct ref *fetch_pack(struct fetch_pack_args *my_args,
 			st.st_mtime = 0;
 	}
 
+	qsort(heads, nr_heads, sizeof(*heads), compare_heads);
+
 	if (heads && nr_heads)
 		nr_heads = remove_duplicates(nr_heads, heads);
 	if (!ref) {

-- 
1.7.10.1.19.g711d603