diff options
| author | Jeff King <peff@peff.net> | 2012-05-21 18:17:20 -0400 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2012-05-22 13:31:03 -0700 |
| commit | 7db8d5370f070ab983e1bc3569380b8aca899c6d (patch) | |
| tree | 0d26e016fc63b21d22de4100a93d5f59b5230f6a /builtin/fetch-pack.c | |
| parent | 443596850f464c768624e6b6477acadc2aa35e8f (diff) | |
| download | git-7db8d5370f070ab983e1bc3569380b8aca899c6d.tar.gz git-7db8d5370f070ab983e1bc3569380b8aca899c6d.tar.xz | |
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.c | 21 |
1 files changed, 6 insertions, 15 deletions
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c index d9e0ee51b..e10184262 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; } |