Re: [PATCH] refs: Use binary search to lookup refs faster

Currently we linearly search through lists of refs when we need to
find a specific ref.  This can be very slow if we need to lookup a
large number of refs.  By changing to a binary search we can make this
faster.

In order to be able to use a binary search we need to change from
using linked lists to arrays, which we can manage using ALLOC_GROW.

We can now also use the standard library qsort function to sort the
refs arrays.

Signed-off-by: Julian Phillips <redacted>
---

Something like this?

 refs.c |  328 ++++++++++++++++++++++++++--------------------------------------
 1 files changed, 131 insertions(+), 197 deletions(-)

diff --git a/refs.c b/refs.c
index a49ff74..e411bea 100644
--- a/refs.c
+++ b/refs.c

@@ -8,14 +8,18 @@
 #define REF_KNOWS_PEELED 04
 #define REF_BROKEN 010
 
-struct ref_list {
-	struct ref_list *next;
+struct ref_entry {
 	unsigned char flag; /* ISSYMREF? ISPACKED? */
 	unsigned char sha1[20];
 	unsigned char peeled[20];
 	char name[FLEX_ARRAY];
 };
 
+struct ref_array {
+	int nr, alloc;
+	struct ref_entry **refs;
+};
+