[PATCH 2/5] fetch-pack: avoid quadratic behavior in remove_duplicates
flat view
STALE3767d
From: Jeff King <hidden>
Date: 2016-06-15 22:53:52
Subsystem:
the rest · Maintainer:
Linus Torvalds
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 <redacted> --- 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