add sorting infrastructure for list refs

Since we store lists of refs as linked lists, we can use
llist_mergesort to efficiently sort them.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

2 files changed, 24 insertions, 0 deletions

diff --git a/remote.c b/remote.c
index b296d17404..6833538829 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)
diff --git a/remote.h b/remote.h
index 9ad8eb6cc6..251d8fd965 100644
--- a/remote.h
+++ b/remote.h
@@ -72,6 +72,8 @@ extern const struct refspec *tag_refspec;
 struct ref *alloc_ref(const char *name);
 struct ref *copy_ref(const struct ref *ref);
 struct ref *copy_ref_list(const struct ref *ref);
+void sort_ref_list(struct ref **, int (*cmp)(const void *, const void *));
+int ref_compare_name(const void *, const void *);
 
 int check_ref_type(const struct ref *ref, int flags);