Improved gitattributes macro implementation

This updates to implementation of gitattribute macros to be much more
similar to core git (albeit not 100%) and to handle expansion of
macros within macros, etc.  It also cleans up the refcounting usage
with macros to be much cleaner.

Also, this adds a new vector function `git_vector_insert_sorted()`
which allows you to maintain a sorted list as you go.  In order to
write that function, this changes the function `git__bsearch()` to
take a somewhat different set of parameters, although the core
functionality is still the same.

1 files changed, 23 insertions, 15 deletions

diff --git a/src/util.c b/src/util.c
index b3af7ffd8..1ca9d850c 100644
--- a/src/util.c
+++ b/src/util.c
@@ -348,22 +348,30 @@ uint32_t git__hash(const void *key, int len, uint32_t seed)
  * Copyright (c) 1990 Regents of the University of California.
  * All rights reserved.
  */
-void **git__bsearch(const void *key, void **base, size_t nmemb, int (*compar)(const void *, const void *))
+int git__bsearch(
+	void **array,
+	size_t array_len,
+	const void *key,
+	int (*compare)(const void *, const void *),
+	size_t *position)
 {
-		int lim, cmp;
-		void **p;
-
-		for (lim = nmemb; lim != 0; lim >>= 1) {
-				p = base + (lim >> 1);
-				cmp = (*compar)(key, *p);
-				if (cmp > 0) { /* key > p: move right */
-						base = p + 1;
-						lim--;
-				} else if (cmp == 0) {
-						return (void **)p;
-				} /* else move left */
-		}
-		return NULL;
+	int lim, cmp;
+	void **part, **base = array;
+
+	for (lim = array_len; lim != 0; lim >>= 1) {
+		part = base + (lim >> 1);
+		cmp = (*compare)(key, *part);
+		if (cmp == 0) {
+			*position = (part - array);
+			return GIT_SUCCESS;
+		} else if (cmp > 0) { /* key > p; take right partition */
+			base = part + 1;
+			lim--;
+		} /* else take left partition */
+	}
+
+	*position = (base - array);
+	return GIT_ENOTFOUND;
 }
 
 /**