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>

diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index d9e0ee51b01e7e0f8ec2fbdc02b91f5d314458b0..e101842627d47f6e368201cd1d01690be016342e 100644 (file)
--- 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;
 
 {
        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;
 }
 
        return dst;
 }