treebuilder: use a map instead of vector to store the entries

Finding a filename in a vector means we need to resort it every time we
want to read from it, which includes every time we want to write to it
as well, as we want to find duplicate keys.

A hash-map fits what we want to do much more accurately, as we do not
care about sorting, but just the particular filename.

We still keep removed entries around, as the interface let you assume
they were going to be around until the treebuilder is cleared or freed,
but in this case that involves an append to a vector in the filter case,
which can now fail.

The only time we care about sorting is when we write out the tree, so
let's make that the only time we do any sorting.

1 files changed, 74 insertions, 49 deletions

diff --git a/src/tree.c b/src/tree.c
index b64efe460..7d28c86ce 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);
 }