thodg/libgit2

diff --git a/include/git2/tree.h b/include/git2/tree.h
index 56922d4..8f1d8a0 100644
--- a/include/git2/tree.h
+++ b/include/git2/tree.h
@@ -354,7 +354,7 @@ typedef int (*git_treebuilder_filter_cb)(
  * @param filter Callback to filter entries
  * @param payload Extra data to pass to filter callback
  */
-GIT_EXTERN(void) git_treebuilder_filter(
+GIT_EXTERN(int) git_treebuilder_filter(
 	git_treebuilder *bld,
 	git_treebuilder_filter_cb filter,
 	void *payload);
diff --git a/src/tree.c b/src/tree.c
index b64efe4..7d28c86 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -17,6 +17,8 @@
 #define DEFAULT_TREE_SIZE 16
 #define MAX_FILEMODE_BYTES 6
 
+GIT__USE_STRMAP;
+
 static bool valid_filemode(const int filemode)
 {
 	return (filemode == GIT_FILEMODE_TREE
@@ -450,6 +452,7 @@ static int append_entry(
 	git_filemode_t filemode)
 {
 	git_tree_entry *entry;
+	int error = 0;
 
 	if (!valid_entry_name(filename))
 		return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
@@ -460,8 +463,9 @@ static int append_entry(
 	git_oid_cpy(&entry->oid, id);
 	entry->attr = (uint16_t)filemode;
 
-	if (git_vector_insert_sorted(&bld->entries, entry, NULL) < 0) {
-		git__free(entry);
+	git_strmap_insert(bld->map, entry->filename, entry, error);
+	if (error < 0) {
+		giterr_set(GITERR_TREE, "failed to append entry %s to the tree builder", filename);
 		return -1;
 	}
 
@@ -610,17 +614,18 @@ int git_tree__write_index(
 int git_treebuilder_create(git_treebuilder **builder_p, const git_tree *source)
 {
 	git_treebuilder *bld;
-	size_t i, source_entries = DEFAULT_TREE_SIZE;
+	size_t i;
 
 	assert(builder_p);
 
 	bld = git__calloc(1, sizeof(git_treebuilder));
 	GITERR_CHECK_ALLOC(bld);
 
-	if (source != NULL)
-		source_entries = source->entries.length;
+	if (git_strmap_alloc(&bld->map) < 0) {
+		return -1;
+	}
 
-	if (git_vector_init(&bld->entries, source_entries, entry_sort_cmp) < 0)
+	if (git_vector_init(&bld->removed, 0, NULL) < 0)
 		goto on_error;
 
 	if (source != NULL) {
@@ -651,7 +656,8 @@ int git_treebuilder_insert(
 	git_filemode_t filemode)
 {
 	git_tree_entry *entry;
-	size_t pos;
+	int error;
+	git_strmap_iter iter;
 
 	assert(bld && id && filename);
 
@@ -661,24 +667,25 @@ int git_treebuilder_insert(
 	if (!valid_entry_name(filename))
 		return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
 
-	if (!tree_key_search(&pos, &bld->entries, filename, strlen(filename))) {
-		entry = git_vector_get(&bld->entries, pos);
-		if (entry->removed) {
-			entry->removed = 0;
-			bld->entrycount++;
-		}
-	} else {
-		entry = alloc_entry(filename);
-		GITERR_CHECK_ALLOC(entry);
+	entry = alloc_entry(filename);
+	GITERR_CHECK_ALLOC(entry);
 
-		if (git_vector_insert_sorted(&bld->entries, entry, NULL) < 0) {
-			git__free(entry);
+	iter = git_strmap_lookup_index(bld->map, entry->filename);
+	if (git_strmap_valid_index(bld->map, iter)) {
+		git_tree_entry *old_val = git_strmap_value_at(bld->map, iter);
+		if (git_vector_insert(&bld->removed, old_val) < 0)
 			return -1;
-		}
 
-		bld->entrycount++;
+		git_strmap_delete_at(bld->map, iter);
 	}
 
+	git_strmap_insert(bld->map, entry->filename, entry, error);
+	if (error < 0) {
+		giterr_set(GITERR_TREE, "failed to insert %s", filename);
+		return -1;
+	}
+
+	bld->entrycount++;
 	git_oid_cpy(&entry->oid, id);
 	entry->attr = filemode;
 
@@ -690,17 +697,14 @@ int git_treebuilder_insert(
 
 static git_tree_entry *treebuilder_get(git_treebuilder *bld, const char *filename)
 {
-	size_t idx;
-	git_tree_entry *entry;
+	git_tree_entry *entry = NULL;
+	git_strmap_iter pos;
 
 	assert(bld && filename);
 
-	if (tree_key_search(&idx, &bld->entries, filename, strlen(filename)) < 0)
-		return NULL;
-
-	entry = git_vector_get(&bld->entries, idx);
-	if (entry->removed)
-		return NULL;
+	pos = git_strmap_lookup_index(bld->map, filename);
+	if (git_strmap_valid_index(bld->map, pos))
+		entry = git_strmap_value_at(bld->map, pos);
 
 	return entry;
 }
@@ -712,12 +716,16 @@ const git_tree_entry *git_treebuilder_get(git_treebuilder *bld, const char *file
 
 int git_treebuilder_remove(git_treebuilder *bld, const char *filename)
 {
-	git_tree_entry *remove_ptr = treebuilder_get(bld, filename);
+	git_tree_entry *entry = treebuilder_get(bld, filename);
 
-	if (remove_ptr == NULL || remove_ptr->removed)
+	if (entry == NULL)
 		return tree_error("Failed to remove entry. File isn't in the tree", filename);
 
-	remove_ptr->removed = 1;
+	if (git_vector_insert(&bld->removed, entry) < 0)
+		return -1;
+
+	git_strmap_delete(bld->map, filename);
+
 	bld->entrycount--;
 	return 0;
 }
@@ -728,19 +736,26 @@ int git_treebuilder_write(git_oid *oid, git_repository *repo, git_treebuilder *b
 	size_t i;
 	git_buf tree = GIT_BUF_INIT;
 	git_odb *odb;
+	git_tree_entry *entry;
+	git_vector entries;
 
 	assert(bld);
 
-	git_vector_sort(&bld->entries);
+	if (git_vector_init(&entries, bld->entrycount, entry_sort_cmp) < 0)
+		return -1;
 
-	/* Grow the buffer beforehand to an estimated size */
-	error = git_buf_grow(&tree, bld->entries.length * 72);
+	git_strmap_foreach_value(bld->map, entry, {
+		if (git_vector_insert(&entries, entry) < 0)
+			return -1;
+	});
 
-	for (i = 0; i < bld->entries.length && !error; ++i) {
-		git_tree_entry *entry = git_vector_get(&bld->entries, i);
+	git_vector_sort(&entries);
+
+	/* Grow the buffer beforehand to an estimated size */
+	error = git_buf_grow(&tree, bld->entrycount * 72);
 
-		if (entry->removed)
-			continue;
+	for (i = 0; i < entries.length && !error; ++i) {
+		git_tree_entry *entry = git_vector_get(&entries, i);
 
 		git_buf_printf(&tree, "%o ", entry->attr);
 		git_buf_put(&tree, entry->filename, entry->filename_len + 1);
@@ -750,6 +765,8 @@ int git_treebuilder_write(git_oid *oid, git_repository *repo, git_treebuilder *b
 			error = -1;
 	}
 
+	git_vector_free(&entries);
+
 	if (!error &&
 		!(error = git_repository_odb__weakptr(&odb, repo)))
 		error = git_odb_write(oid, odb, tree.ptr, tree.size, GIT_OBJ_TREE);
@@ -758,22 +775,27 @@ int git_treebuilder_write(git_oid *oid, git_repository *repo, git_treebuilder *b
 	return error;
 }
 
-void git_treebuilder_filter(
+int git_treebuilder_filter(
 	git_treebuilder *bld,
 	git_treebuilder_filter_cb filter,
 	void *payload)
 {
-	size_t i;
+	const char *filename;
 	git_tree_entry *entry;
 
 	assert(bld && filter);
 
-	git_vector_foreach(&bld->entries, i, entry) {
-		if (!entry->removed && filter(entry, payload)) {
-			entry->removed = 1;
-			bld->entrycount--;
-		}
-	}
+	git_strmap_foreach(bld->map, filename, entry, {
+			if (filter(entry, payload)) {
+				if (git_vector_insert(&bld->removed, entry) < 0)
+					return -1;
+
+				git_strmap_delete(bld->map, filename);
+				bld->entrycount--;
+			}
+	});
+
+	return 0;
 }
 
 void git_treebuilder_clear(git_treebuilder *bld)
@@ -783,10 +805,12 @@ void git_treebuilder_clear(git_treebuilder *bld)
 
 	assert(bld);
 
-	git_vector_foreach(&bld->entries, i, e)
+	git_vector_foreach(&bld->removed, i, e)
 		git_tree_entry_free(e);
 
-	git_vector_clear(&bld->entries);
+	git_strmap_foreach_value(bld->map, e, git_tree_entry_free(e));
+
+	git_vector_clear(&bld->removed);
 	bld->entrycount = 0;
 }
 
@@ -796,7 +820,8 @@ void git_treebuilder_free(git_treebuilder *bld)
 		return;
 
 	git_treebuilder_clear(bld);
-	git_vector_free(&bld->entries);
+	git_vector_free(&bld->removed);
+	git_strmap_free(bld->map);
 	git__free(bld);
 }
 
diff --git a/src/tree.h b/src/tree.h
index f07039a..38daf21 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -11,9 +11,9 @@
 #include "repository.h"
 #include "odb.h"
 #include "vector.h"
+#include "strmap.h"
 
 struct git_tree_entry {
-	uint16_t removed;
 	uint16_t attr;
 	git_oid oid;
 	size_t filename_len;
@@ -26,8 +26,9 @@ struct git_tree {
 };
 
 struct git_treebuilder {
-	git_vector entries;
+	git_vector removed;
 	size_t entrycount; /* vector may contain "removed" entries */
+	git_strmap *map;
 };
 
 GIT_INLINE(bool) git_tree_entry__is_tree(const struct git_tree_entry *e)
diff --git a/tests/object/tree/write.c b/tests/object/tree/write.c
index 45356e8..ddb62e2 100644
--- a/tests/object/tree/write.c
+++ b/tests/object/tree/write.c
@@ -104,6 +104,7 @@ void test_object_tree_write__subtree(void)
 void test_object_tree_write__sorted_subtrees(void)
 {
 	git_treebuilder *builder;
+	git_tree *tree;
 	unsigned int i;
 	int position_c = -1, position_cake = -1, position_config = -1;
 
@@ -143,8 +144,9 @@ void test_object_tree_write__sorted_subtrees(void)
 
 	cl_git_pass(git_treebuilder_write(&tree_oid, g_repo, builder));
 
-	for (i = 0; i < builder->entries.length; ++i) {
-		git_tree_entry *entry = git_vector_get(&builder->entries, i);
+	cl_git_pass(git_tree_lookup(&tree, g_repo, &tree_oid));
+	for (i = 0; i < git_tree_entrycount(tree); i++) {
+		const git_tree_entry *entry = git_tree_entry_byindex(tree, i);
 
 		if (strcmp(entry->filename, "c") == 0)
 			position_c = i;
@@ -156,6 +158,8 @@ void test_object_tree_write__sorted_subtrees(void)
 			position_config = i;
 	}
 
+	git_tree_free(tree);
+
 	cl_assert(position_c != -1);
 	cl_assert(position_cake != -1);
 	cl_assert(position_config != -1);