5 files changed, 106 insertions, 58 deletions

diff --git a/src/attr_file.c b/src/attr_file.c
index a1379054b..fe8844e2d 100644
--- a/src/attr_file.c
+++ b/src/attr_file.c
@@ -12,17 +12,9 @@ static void git_attr_rule__clear(git_attr_rule *rule);
 
 int git_attr_cache__insert_macro(git_repository *repo, git_attr_rule *macro)
 {
-	unsigned int i;
-	git_attr_assignment *assign;
-
 	if (macro->assigns.length == 0)
 		return git__throw(GIT_EMISSINGOBJDATA, "git attribute macro with no values");
 
-	git_vector_foreach(&macro->assigns, i, assign) {
-		GIT_REFCOUNT_OWN(assign, macro);
-		GIT_REFCOUNT_INC(assign);
-	}
-
 	return git_hashtable_insert(
 		repo->attrcache.macros, macro->match.pattern, macro);
 }
@@ -358,7 +350,7 @@ static int sort_by_hash_and_name(const void *a_raw, const void *b_raw)
 		return strcmp(b->name, a->name);
 }
 
-static void free_assign(git_attr_assignment *assign)
+static void git_attr_assignment__free(git_attr_assignment *assign)
 {
 	git__free(assign->name);
 	assign->name = NULL;
@@ -371,6 +363,16 @@ static void free_assign(git_attr_assignment *assign)
 	git__free(assign);
 }
 
+static int merge_assignments(void **old_raw, void *new_raw)
+{
+	git_attr_assignment **old = (git_attr_assignment **)old_raw;
+	git_attr_assignment *new = (git_attr_assignment *)new_raw;
+
+	GIT_REFCOUNT_DEC(*old, git_attr_assignment__free);
+	*old = new;
+	return GIT_EEXISTS;
+}
+
 int git_attr_assignment__parse(
 	git_repository *repo,
 	git_vector *assigns,
@@ -382,6 +384,8 @@ int git_attr_assignment__parse(
 
 	assert(assigns && !assigns->length);
 
+	assigns->_cmp = sort_by_hash_and_name;
+
 	while (*scan && *scan != '\n' && error == GIT_SUCCESS) {
 		const char *name_start, *value_start;
 
@@ -395,6 +399,7 @@ int git_attr_assignment__parse(
 				error = GIT_ENOMEM;
 				break;
 			}
+			GIT_REFCOUNT_INC(assign);
 		}
 
 		assign->name_hash = 5381;
@@ -449,8 +454,8 @@ int git_attr_assignment__parse(
 			}
 		}
 
-		/* expand macros (if given a repo) */
-		if (repo != NULL) {
+		/* expand macros (if given a repo with a macro cache) */
+		if (repo != NULL && assign->value == GIT_ATTR_TRUE) {
 			git_attr_rule *macro =
 				git_hashtable_lookup(repo->attrcache.macros, assign->name);
 
@@ -458,30 +463,25 @@ int git_attr_assignment__parse(
 				unsigned int i;
 				git_attr_assignment *massign;
 
-				/* issue warning: if assign->value != GIT_ATTR_TRUE */
+				git_vector_foreach(&macro->assigns, i, massign) {
+					GIT_REFCOUNT_INC(massign);
 
-				git__free(assign->name);
-				assign->name = NULL;
-				if (assign->is_allocated) {
-					git__free((void *)assign->value);
-					assign->value = NULL;
-				}
+					error = git_vector_insert_sorted(
+						assigns, massign, &merge_assignments);
 
-				git_vector_foreach(&macro->assigns, i, massign) {
-					error = git_vector_insert(assigns, massign);
-					if (error != GIT_SUCCESS)
+					if (error == GIT_EEXISTS)
+						error = GIT_SUCCESS;
+					else if (error != GIT_SUCCESS)
 						break;
-					GIT_REFCOUNT_INC(&massign->rc);
 				}
-
-				/* continue to next assignment */
-				continue;
 			}
 		}
 
 		/* insert allocated assign into vector */
-		error = git_vector_insert(assigns, assign);
-		if (error < GIT_SUCCESS)
+		error = git_vector_insert_sorted(assigns, assign, &merge_assignments);
+		if (error == GIT_EEXISTS)
+			error = GIT_SUCCESS;
+		else if (error < GIT_SUCCESS)
 			break;
 
 		/* clear assign since it is now "owned" by the vector */
@@ -490,13 +490,9 @@ int git_attr_assignment__parse(
 
 	if (!assigns->length)
 		error = git__throw(GIT_ENOTFOUND, "No attribute assignments found for rule");
-	else {
-		assigns->_cmp = sort_by_hash_and_name;
-		git_vector_sort(assigns);
-	}
 
 	if (assign != NULL)
-		free_assign(assign);
+		git_attr_assignment__free(assign);
 
 	while (*scan && *scan != '\n') scan++;
 	if (*scan == '\n') scan++;
@@ -518,11 +514,8 @@ static void git_attr_rule__clear(git_attr_rule *rule)
 	rule->match.pattern = NULL;
 	rule->match.length = 0;
 
-	git_vector_foreach(&rule->assigns, i, assign) {
-		if (GIT_REFCOUNT_OWNER(assign) == rule)
-			GIT_REFCOUNT_OWN(assign, NULL);
-		GIT_REFCOUNT_DEC(assign, free_assign);
-	}
+	git_vector_foreach(&rule->assigns, i, assign)
+		GIT_REFCOUNT_DEC(assign, git_attr_assignment__free);
 
 	git_vector_free(&rule->assigns);
 }
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;
 }
 
 /**
diff --git a/src/util.h b/src/util.h
index 4b1104b7b..2367bb5f3 100644
--- a/src/util.h
+++ b/src/util.h
@@ -105,8 +105,13 @@ extern void git__strtolower(char *str);
 extern int git__fnmatch(const char *pattern, const char *name, int flags);
 
 extern void git__tsort(void **dst, size_t size, int (*cmp)(const void *, const void *));
-extern void **git__bsearch(const void *key, void **base, size_t nmemb,
-	int (*compar)(const void *, const void *));
+
+extern int git__bsearch(
+	void **array,
+	size_t array_len,
+	const void *key,
+	int (*compare)(const void *, const void *),
+	size_t *position);
 
 extern int git__strcmp_cb(const void *a, const void *b);
 
diff --git a/src/vector.c b/src/vector.c
index e745d77dd..593d037d4 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -74,6 +74,45 @@ int git_vector_insert(git_vector *v, void *element)
 	return GIT_SUCCESS;
 }
 
+int git_vector_insert_sorted(git_vector *v, void *element, int (*on_dup)(void **old, void *new))
+{
+	int error = GIT_SUCCESS;
+	size_t pos;
+
+	assert(v && v->_cmp);
+
+	if (!v->sorted)
+		git_vector_sort(v);
+
+	if (v->length >= v->_alloc_size) {
+		if (resize_vector(v) < 0)
+			return GIT_ENOMEM;
+	}
+
+	error = git__bsearch(v->contents, v->length, element, v->_cmp, &pos);
+
+	/* If we found the element and have a duplicate handler callback,
+	 * invoke it.  If it returns an error, then cancel insert, otherwise
+	 * proceed with normal insert.
+	 */
+	if (error == GIT_SUCCESS && on_dup != NULL) {
+		error = on_dup(&v->contents[pos], element);
+		if (error != GIT_SUCCESS)
+			return error;
+	}
+
+	/* shift elements to the right */
+	if (pos < v->length) {
+		memmove(v->contents + pos + 1, v->contents + pos,
+		        (v->length - pos) * sizeof(void *));
+	}
+
+	v->contents[pos] = element;
+	v->length++;
+
+	return GIT_SUCCESS;
+}
+
 void git_vector_sort(git_vector *v)
 {
 	assert(v);
@@ -87,7 +126,7 @@ void git_vector_sort(git_vector *v)
 
 int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *key)
 {
-	void **find;
+	size_t pos;
 
 	assert(v && key && key_lookup);
 
@@ -97,9 +136,9 @@ int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *ke
 
 	git_vector_sort(v);
 
-	find = git__bsearch(key, v->contents, v->length, key_lookup);
-	if (find != NULL)
-		return (int)(find - v->contents);
+	if (git__bsearch(v->contents, v->length, key, key_lookup,
+			&pos) == GIT_SUCCESS)
+		return (int)pos;
 
 	return git__throw(GIT_ENOTFOUND, "Can't find element");
 }
diff --git a/src/vector.h b/src/vector.h
index 4c053e6ae..9ee3c9ed5 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -45,6 +45,9 @@ GIT_INLINE(void *) git_vector_get(git_vector *v, unsigned int position)
 	for ((iter) = (v)->length; (iter) > 0 && ((elem) = (v)->contents[(iter)-1], 1); (iter)-- )
 
 int git_vector_insert(git_vector *v, void *element);
+int git_vector_insert_sorted(git_vector *v, void *element,
+	int (*on_dup)(void **old, void *new));
 int git_vector_remove(git_vector *v, unsigned int idx);
 void git_vector_uniq(git_vector *v);
+
 #endif