Merge remote-tracking branch 'upstream/cmn/treebuilder-perf'

4 files changed, 72 insertions, 62 deletions

diff --git a/include/git2/tree.h b/include/git2/tree.h
index 56922d40b..42b68193e 100644
--- a/include/git2/tree.h
+++ b/include/git2/tree.h
@@ -301,8 +301,10 @@ GIT_EXTERN(const git_tree_entry *) git_treebuilder_get(
  * If an entry named `filename` already exists, its attributes
  * will be updated with the given ones.
  *
- * The optional pointer `out` can be used to retrieve a pointer to
- * the newly created/updated entry.  Pass NULL if you do not need it.
+ * The optional pointer `out` can be used to retrieve a pointer to the
+ * newly created/updated entry.  Pass NULL if you do not need it. The
+ * pointer may not be valid past the next operation in this
+ * builder. Duplicate the entry if you want to keep it.
  *
  * No attempt is being made to ensure that the provided oid points
  * to an existing git object in the object database, nor that the
diff --git a/src/tree.c b/src/tree.c
index b64efe460..e0e2dbebf 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
@@ -365,7 +367,8 @@ size_t git_tree_entrycount(const git_tree *tree)
 unsigned int git_treebuilder_entrycount(git_treebuilder *bld)
 {
 	assert(bld);
-	return (unsigned int)bld->entrycount;
+
+	return git_strmap_num_entries(bld->map);
 }
 
 static int tree_error(const char *str, const char *path)
@@ -450,6 +453,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,12 +464,12 @@ 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;
 	}
 
-	bld->entrycount++;
 	return 0;
 }
 
@@ -610,18 +614,16 @@ 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_vector_init(&bld->entries, source_entries, entry_sort_cmp) < 0)
-		goto on_error;
+	if (git_strmap_alloc(&bld->map) < 0) {
+		return -1;
+	}
 
 	if (source != NULL) {
 		git_tree_entry *entry_src;
@@ -651,7 +653,8 @@ int git_treebuilder_insert(
 	git_filemode_t filemode)
 {
 	git_tree_entry *entry;
-	size_t pos;
+	int error;
+	git_strmap_iter pos;
 
 	assert(bld && id && filename);
 
@@ -661,22 +664,20 @@ 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++;
-		}
+	pos = git_strmap_lookup_index(bld->map, filename);
+	if (git_strmap_valid_index(bld->map, pos)) {
+		entry = git_strmap_value_at(bld->map, pos);
 	} else {
 		entry = alloc_entry(filename);
 		GITERR_CHECK_ALLOC(entry);
 
-		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) {
+			git_tree_entry_free(entry);
+			giterr_set(GITERR_TREE, "failed to insert %s", filename);
 			return -1;
 		}
-
-		bld->entrycount++;
 	}
 
 	git_oid_cpy(&entry->oid, id);
@@ -690,17 +691,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,35 +710,44 @@ 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;
-	bld->entrycount--;
+	git_strmap_delete(bld->map, filename);
+	git_tree_entry_free(entry);
+
 	return 0;
 }
 
 int git_treebuilder_write(git_oid *oid, git_repository *repo, git_treebuilder *bld)
 {
 	int error = 0;
-	size_t i;
+	size_t i, entrycount;
 	git_buf tree = GIT_BUF_INIT;
 	git_odb *odb;
+	git_tree_entry *entry;
+	git_vector entries;
 
 	assert(bld);
 
-	git_vector_sort(&bld->entries);
+	entrycount = git_strmap_num_entries(bld->map);
+	if (git_vector_init(&entries, 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, 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 +757,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);
@@ -763,31 +772,27 @@ void git_treebuilder_filter(
 	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)) {
+				git_strmap_delete(bld->map, filename);
+				git_tree_entry_free(entry);
+			}
+	});
 }
 
 void git_treebuilder_clear(git_treebuilder *bld)
 {
-	size_t i;
 	git_tree_entry *e;
 
 	assert(bld);
 
-	git_vector_foreach(&bld->entries, i, e)
-		git_tree_entry_free(e);
-
-	git_vector_clear(&bld->entries);
-	bld->entrycount = 0;
+	git_strmap_foreach_value(bld->map, e, git_tree_entry_free(e));
+	git_strmap_clear(bld->map);
 }
 
 void git_treebuilder_free(git_treebuilder *bld)
@@ -796,7 +801,7 @@ void git_treebuilder_free(git_treebuilder *bld)
 		return;
 
 	git_treebuilder_clear(bld);
-	git_vector_free(&bld->entries);
+	git_strmap_free(bld->map);
 	git__free(bld);
 }
 
diff --git a/src/tree.h b/src/tree.h
index f07039a07..5d27eb7c9 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,7 @@ struct git_tree {
 };
 
 struct git_treebuilder {
-	git_vector entries;
-	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 45356e807..ddb62e278 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);