Merge branch 'jk/fetch-pack-remove-dups-optim'

The way "fetch-pack" that is given multiple references to fetch tried to
remove duplicates was very inefficient.

By Jeff King
* jk/fetch-pack-remove-dups-optim:
  fetch-pack: sort incoming heads list earlier
  fetch-pack: avoid quadratic loop in filter_refs
  fetch-pack: sort the list of incoming refs
  add sorting infrastructure for list refs
  fetch-pack: avoid quadratic behavior in remove_duplicates
  fetch-pack: sort incoming heads

1 files changed, 22 insertions, 0 deletions

diff --git a/remote.c b/remote.c
index b296d1740..683353882 100644
--- a/remote.c
+++ b/remote.c
@@ -7,6 +7,7 @@
 #include "dir.h"
 #include "tag.h"
 #include "string-list.h"
+#include "mergesort.h"
 
 enum map_direction { FROM_SRC, FROM_DST };
 
@@ -918,6 +919,27 @@ void free_refs(struct ref *ref)
 	}
 }
 
+int ref_compare_name(const void *va, const void *vb)
+{
+	const struct ref *a = va, *b = vb;
+	return strcmp(a->name, b->name);
+}
+
+static void *ref_list_get_next(const void *a)
+{
+	return ((const struct ref *)a)->next;
+}
+
+static void ref_list_set_next(void *a, void *next)
+{
+	((struct ref *)a)->next = next;
+}
+
+void sort_ref_list(struct ref **l, int (*cmp)(const void *, const void *))
+{
+	*l = llist_mergesort(*l, ref_list_get_next, ref_list_set_next, cmp);
+}
+
 static int count_refspec_match(const char *pattern,
 			       struct ref *refs,
 			       struct ref **matched_ref)