summaryrefslogtreecommitdiff
path: root/builtin/fetch-pack.c
diff options
context:
space:
mode:
authorJeff King <peff@peff.net>2012-05-21 22:17:20 (GMT)
committerJunio C Hamano <gitster@pobox.com>2012-05-22 20:31:03 (GMT)
commit7db8d5370f070ab983e1bc3569380b8aca899c6d (patch)
tree0d26e016fc63b21d22de4100a93d5f59b5230f6a /builtin/fetch-pack.c
parent443596850f464c768624e6b6477acadc2aa35e8f (diff)
downloadgit-7db8d5370f070ab983e1bc3569380b8aca899c6d.zip
git-7db8d5370f070ab983e1bc3569380b8aca899c6d.tar.gz
git-7db8d5370f070ab983e1bc3569380b8aca899c6d.tar.bz2
fetch-pack: avoid quadratic behavior in remove_duplicates
We remove duplicate entries from the list of refs we are fed in fetch-pack. The original algorithm is quadratic over the number of refs, but since the list is now guaranteed to be sorted, we can do it in linear time. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'builtin/fetch-pack.c')
-rw-r--r--builtin/fetch-pack.c21
1 files changed, 6 insertions, 15 deletions
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index d9e0ee5..e101842 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -834,21 +834,12 @@ static int remove_duplicates(int nr_heads, char **heads)
{
int src, dst;
- for (src = dst = 0; src < nr_heads; src++) {
- /* If heads[src] is different from any of
- * heads[0..dst], push it in.
- */
- int i;
- for (i = 0; i < dst; i++) {
- if (!strcmp(heads[i], heads[src]))
- break;
- }
- if (i < dst)
- continue;
- if (src != dst)
- heads[dst] = heads[src];
- dst++;
- }
+ if (!nr_heads)
+ return 0;
+
+ for (src = dst = 1; src < nr_heads; src++)
+ if (strcmp(heads[src], heads[dst-1]))
+ heads[dst++] = heads[src];
return dst;
}