[PATCH 2/5] fetch-pack: avoid quadratic behavior in remove_duplicates
- From
Jeff King <peff@peff.net>
- Date
- May 21, 2012, 22:17 UTC
- Message-ID
- <20120521221720.GB22914@sigill.intra.peff.net>
- In-Reply-To
- <20120521221417.GA22664@sigill.intra.peff.net>
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> --- builtin/fetch-pack.c | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-)
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c index 380743e..3522d8e 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; }
-- 1.7.10.1.19.g711d603