Merge pull request #3702 from libgit2/cmn/tree-reuse

Reuse a tree's buffer and allocate constant-sized entries in an array

8 files changed, 76 insertions, 83 deletions

diff --git a/src/index.c b/src/index.c
index 62aacf959..63e47965a 100644
--- a/src/index.c
+++ b/src/index.c
@@ -2836,7 +2836,7 @@ static int read_tree_cb(
 		return -1;
 
 	entry->mode = tentry->attr;
-	entry->id = tentry->oid;
+	git_oid_cpy(&entry->id, git_tree_entry_id(tentry));
 
 	/* look for corresponding old entry and copy data to new entry */
 	if (data->old_entries != NULL &&
diff --git a/src/iterator.c b/src/iterator.c
index 024a97573..cb1ea6a87 100644
--- a/src/iterator.c
+++ b/src/iterator.c
@@ -458,7 +458,7 @@ static int tree_iterator__set_next(tree_iterator *ti, tree_iterator_frame *tf)
 		/* try to load trees for items in [current,next) range */
 		if (!error && git_tree_entry__is_tree(te))
 			error = git_tree_lookup(
-				&tf->entries[tf->next]->tree, ti->base.repo, &te->oid);
+				&tf->entries[tf->next]->tree, ti->base.repo, te->oid);
 	}
 
 	if (tf->next > tf->current + 1)
@@ -603,7 +603,7 @@ static int tree_iterator__update_entry(tree_iterator *ti)
     te = tf->entries[tf->current]->te;
 
 	ti->entry.mode = te->attr;
-	git_oid_cpy(&ti->entry.id, &te->oid);
+	git_oid_cpy(&ti->entry.id, te->oid);
 
 	ti->entry.path = tree_iterator__current_filename(ti, te);
 	GITERR_CHECK_ALLOC(ti->entry.path);
diff --git a/src/push.c b/src/push.c
index 3c9fa2f1b..0747259c8 100644
--- a/src/push.c
+++ b/src/push.c
@@ -374,9 +374,9 @@ static int enqueue_object(
 		case GIT_OBJ_COMMIT:
 			return 0;
 		case GIT_OBJ_TREE:
-			return git_packbuilder_insert_tree(pb, &entry->oid);
+			return git_packbuilder_insert_tree(pb, entry->oid);
 		default:
-			return git_packbuilder_insert(pb, &entry->oid, entry->filename);
+			return git_packbuilder_insert(pb, entry->oid, entry->filename);
 	}
 }
 
@@ -396,7 +396,7 @@ static int queue_differences(
 		const git_tree_entry *d_entry = git_tree_entry_byindex(delta, j);
 		int cmp = 0;
 
-		if (!git_oid__cmp(&b_entry->oid, &d_entry->oid))
+		if (!git_oid__cmp(b_entry->oid, d_entry->oid))
 			goto loop;
 
 		cmp = strcmp(b_entry->filename, d_entry->filename);
@@ -407,15 +407,15 @@ static int queue_differences(
 			git_tree_entry__is_tree(b_entry) &&
 			git_tree_entry__is_tree(d_entry)) {
 			/* Add the right-hand entry */
-			if ((error = git_packbuilder_insert(pb, &d_entry->oid,
+			if ((error = git_packbuilder_insert(pb, d_entry->oid,
 				d_entry->filename)) < 0)
 				goto on_error;
 
 			/* Acquire the subtrees and recurse */
 			if ((error = git_tree_lookup(&b_child,
-					git_tree_owner(base), &b_entry->oid)) < 0 ||
+					git_tree_owner(base), b_entry->oid)) < 0 ||
 				(error = git_tree_lookup(&d_child,
-					git_tree_owner(delta), &d_entry->oid)) < 0 ||
+					git_tree_owner(delta), d_entry->oid)) < 0 ||
 				(error = queue_differences(b_child, d_child, pb)) < 0)
 				goto on_error;
 
diff --git a/src/submodule.c b/src/submodule.c
index 3f39b9ef0..c903cf939 100644
--- a/src/submodule.c
+++ b/src/submodule.c
@@ -1417,7 +1417,7 @@ static int submodule_update_head(git_submodule *submodule)
 		git_tree_entry_bypath(&te, head, submodule->path) < 0)
 		giterr_clear();
 	else
-		submodule_update_from_head_data(submodule, te->attr, &te->oid);
+		submodule_update_from_head_data(submodule, te->attr, git_tree_entry_id(te));
 
 	git_tree_entry_free(te);
 	git_tree_free(head);
diff --git a/src/tree.c b/src/tree.c
index 48b9f121d..1ba484918 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -85,9 +85,10 @@ int git_tree_entry_icmp(const git_tree_entry *e1, const git_tree_entry *e2)
 }
 
 /**
- * Allocate either from the pool or from the system allocator
+ * Allocate a new self-contained entry, with enough space after it to
+ * store the filename and the id.
  */
-static git_tree_entry *alloc_entry_base(git_pool *pool, const char *filename, size_t filename_len)
+static git_tree_entry *alloc_entry(const char *filename, size_t filename_len, const git_oid *id)
 {
 	git_tree_entry *entry = NULL;
 	size_t tree_len;
@@ -95,44 +96,32 @@ static git_tree_entry *alloc_entry_base(git_pool *pool, const char *filename, si
 	TREE_ENTRY_CHECK_NAMELEN(filename_len);
 
 	if (GIT_ADD_SIZET_OVERFLOW(&tree_len, sizeof(git_tree_entry), filename_len) ||
-	    GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, 1))
+	    GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, 1) ||
+	    GIT_ADD_SIZET_OVERFLOW(&tree_len, tree_len, GIT_OID_RAWSZ))
 		return NULL;
 
-	entry = pool ? git_pool_malloc(pool, tree_len) :
-		       git__malloc(tree_len);
+	entry = git__calloc(1, tree_len);
 	if (!entry)
 		return NULL;
 
-	memset(entry, 0x0, sizeof(git_tree_entry));
-	memcpy(entry->filename, filename, filename_len);
-	entry->filename[filename_len] = 0;
-	entry->filename_len = (uint16_t)filename_len;
-
-	return entry;
-}
+	{
+		char *filename_ptr;
+		void *id_ptr;
 
-/**
- * Allocate a tree entry, using the poolin the tree which owns
- * it. This is useful when reading trees, so we don't allocate a ton
- * of small strings but can use the pool.
- */
-static git_tree_entry *alloc_entry_pooled(git_pool *pool, const char *filename, size_t filename_len)
-{
-	git_tree_entry *entry = NULL;
+		filename_ptr = ((char *) entry) + sizeof(git_tree_entry);
+		memcpy(filename_ptr, filename, filename_len);
+		entry->filename = filename_ptr;
 
-	if (!(entry = alloc_entry_base(pool, filename, filename_len)))
-		return NULL;
+		id_ptr = filename_ptr + filename_len + 1;
+		git_oid_cpy(id_ptr, id);
+		entry->oid = id_ptr;
+	}
 
-	entry->pooled = true;
+	entry->filename_len = (uint16_t)filename_len;
 
 	return entry;
 }
 
-static git_tree_entry *alloc_entry(const char *filename)
-{
-	return alloc_entry_base(NULL, filename, strlen(filename));
-}
-
 struct tree_key_search {
 	const char *filename;
 	uint16_t filename_len;
@@ -234,7 +223,7 @@ static int tree_key_search(
 
 void git_tree_entry_free(git_tree_entry *entry)
 {
-	if (entry == NULL || entry->pooled)
+	if (entry == NULL)
 		return;
 
 	git__free(entry);
@@ -242,36 +231,27 @@ void git_tree_entry_free(git_tree_entry *entry)
 
 int git_tree_entry_dup(git_tree_entry **dest, const git_tree_entry *source)
 {
-	size_t total_size;
-	git_tree_entry *copy;
+	git_tree_entry *cpy;
 
 	assert(source);
 
-	GITERR_CHECK_ALLOC_ADD(&total_size, sizeof(git_tree_entry), source->filename_len);
-	GITERR_CHECK_ALLOC_ADD(&total_size, total_size, 1);
-
-	copy = git__malloc(total_size);
-	GITERR_CHECK_ALLOC(copy);
-
-	memcpy(copy, source, total_size);
+	cpy = alloc_entry(source->filename, source->filename_len, source->oid);
+	if (cpy == NULL)
+		return -1;
 
-	copy->pooled = 0;
+	cpy->attr = source->attr;
 
-	*dest = copy;
+	*dest = cpy;
 	return 0;
 }
 
 void git_tree__free(void *_tree)
 {
 	git_tree *tree = _tree;
-	size_t i;
-	git_tree_entry *e;
-
-	git_vector_foreach(&tree->entries, i, e)
-		git_tree_entry_free(e);
 
+	git_odb_object_free(tree->odb_obj);
 	git_vector_free(&tree->entries);
-	git_pool_clear(&tree->pool);
+	git_array_clear(tree->entries_arr);
 	git__free(tree);
 }
 
@@ -294,7 +274,7 @@ const char *git_tree_entry_name(const git_tree_entry *entry)
 const git_oid *git_tree_entry_id(const git_tree_entry *entry)
 {
 	assert(entry);
-	return &entry->oid;
+	return entry->oid;
 }
 
 git_otype git_tree_entry_type(const git_tree_entry *entry)
@@ -315,7 +295,7 @@ int git_tree_entry_to_object(
 	const git_tree_entry *entry)
 {
 	assert(entry && object_out);
-	return git_object_lookup(object_out, repo, &entry->oid, GIT_OBJ_ANY);
+	return git_object_lookup(object_out, repo, entry->oid, GIT_OBJ_ANY);
 }
 
 static const git_tree_entry *entry_fromname(
@@ -356,7 +336,7 @@ const git_tree_entry *git_tree_entry_byid(
 	assert(tree);
 
 	git_vector_foreach(&tree->entries, i, e) {
-		if (memcmp(&e->oid.id, &id->id, sizeof(id->id)) == 0)
+		if (memcmp(&e->oid->id, &id->id, sizeof(id->id)) == 0)
 			return e;
 	}
 
@@ -443,14 +423,20 @@ static int parse_mode(unsigned int *modep, const char *buffer, const char **buff
 
 int git_tree__parse(void *_tree, git_odb_object *odb_obj)
 {
+	size_t i;
 	git_tree *tree = _tree;
-	const char *buffer = git_odb_object_data(odb_obj);
-	const char *buffer_end = buffer + git_odb_object_size(odb_obj);
+	const char *buffer;
+	const char *buffer_end;
 
-	git_pool_init(&tree->pool, 1);
-	if (git_vector_init(&tree->entries, DEFAULT_TREE_SIZE, entry_sort_cmp) < 0)
+	if (git_odb_object_dup(&tree->odb_obj, odb_obj) < 0)
 		return -1;
 
+	buffer = git_odb_object_data(tree->odb_obj);
+	buffer_end = buffer + git_odb_object_size(tree->odb_obj);
+
+	git_array_init_to_size(tree->entries_arr, DEFAULT_TREE_SIZE);
+	GITERR_CHECK_ARRAY(tree->entries_arr);
+
 	while (buffer < buffer_end) {
 		git_tree_entry *entry;
 		size_t filename_len;
@@ -466,22 +452,28 @@ int git_tree__parse(void *_tree, git_odb_object *odb_obj)
 		filename_len = nul - buffer;
 		/** Allocate the entry and store it in the entries vector */
 		{
-			entry = alloc_entry_pooled(&tree->pool, buffer, filename_len);
+			entry = git_array_alloc(tree->entries_arr);
 			GITERR_CHECK_ALLOC(entry);
 
-			if (git_vector_insert(&tree->entries, entry) < 0)
-				return -1;
-
 			entry->attr = attr;
+			entry->filename_len = filename_len;
+			entry->filename = buffer;
+			entry->oid = (git_oid *) ((char *) buffer + filename_len + 1);
 		}
 
-		/* Advance to the ID just after the path */
 		buffer += filename_len + 1;
-
-		git_oid_fromraw(&entry->oid, (const unsigned char *)buffer);
 		buffer += GIT_OID_RAWSZ;
 	}
 
+	/* Add the entries to the vector here, as we may reallocate during the loop */
+	if (git_vector_init(&tree->entries, tree->entries_arr.size, entry_sort_cmp) < 0)
+		return -1;
+
+	for (i = 0; i < tree->entries_arr.size; i++) {
+		if (git_vector_insert(&tree->entries, git_array_get(tree->entries_arr, i)) < 0)
+			return -1;
+	}
+
 	/* The tree is sorted by definition. Bad inputs give bad outputs */
 	tree->entries.flags |= GIT_VECTOR_SORTED;
 
@@ -517,10 +509,9 @@ static int append_entry(
 	if (!valid_entry_name(bld->repo, filename))
 		return tree_error("Failed to insert entry. Invalid name for a tree entry", filename);
 
-	entry = alloc_entry(filename);
+	entry = alloc_entry(filename, strlen(filename), id);
 	GITERR_CHECK_ALLOC(entry);
 
-	git_oid_cpy(&entry->oid, id);
 	entry->attr = (uint16_t)filemode;
 
 	git_strmap_insert(bld->map, entry->filename, entry, error);
@@ -712,7 +703,7 @@ int git_treebuilder_new(
 		git_vector_foreach(&source->entries, i, entry_src) {
 			if (append_entry(
 				bld, entry_src->filename,
-				&entry_src->oid,
+				entry_src->oid,
 				entry_src->attr) < 0)
 				goto on_error;
 		}
@@ -764,8 +755,9 @@ int git_treebuilder_insert(
 	pos = git_strmap_lookup_index(bld->map, filename);
 	if (git_strmap_valid_index(bld->map, pos)) {
 		entry = git_strmap_value_at(bld->map, pos);
+		git_oid_cpy((git_oid *) entry->oid, id);
 	} else {
-		entry = alloc_entry(filename);
+		entry = alloc_entry(filename, strlen(filename), id);
 		GITERR_CHECK_ALLOC(entry);
 
 		git_strmap_insert(bld->map, entry->filename, entry, error);
@@ -777,7 +769,6 @@ int git_treebuilder_insert(
 		}
 	}
 
-	git_oid_cpy(&entry->oid, id);
 	entry->attr = filemode;
 
 	if (entry_out)
@@ -848,7 +839,7 @@ int git_treebuilder_write(git_oid *oid, git_treebuilder *bld)
 
 		git_buf_printf(&tree, "%o ", entry->attr);
 		git_buf_put(&tree, entry->filename, entry->filename_len + 1);
-		git_buf_put(&tree, (char *)entry->oid.id, GIT_OID_RAWSZ);
+		git_buf_put(&tree, (char *)entry->oid->id, GIT_OID_RAWSZ);
 
 		if (git_buf_oom(&tree))
 			error = -1;
@@ -960,7 +951,7 @@ int git_tree_entry_bypath(
 		return git_tree_entry_dup(entry_out, entry);
 	}
 
-	if (git_tree_lookup(&subtree, root->object.repo, &entry->oid) < 0)
+	if (git_tree_lookup(&subtree, root->object.repo, entry->oid) < 0)
 		return -1;
 
 	error = git_tree_entry_bypath(
@@ -1001,7 +992,7 @@ static int tree_walk(
 			git_tree *subtree;
 			size_t path_len = git_buf_len(path);
 
-			error = git_tree_lookup(&subtree, tree->object.repo, &entry->oid);
+			error = git_tree_lookup(&subtree, tree->object.repo, entry->oid);
 			if (error < 0)
 				break;
 
diff --git a/src/tree.h b/src/tree.h
index 914d788c8..a108d964c 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -17,15 +17,15 @@
 struct git_tree_entry {
 	uint16_t attr;
 	uint16_t filename_len;
-	git_oid oid;
-	bool pooled;
-	char filename[GIT_FLEX_ARRAY];
+	const git_oid *oid;
+	const char *filename;
 };
 
 struct git_tree {
 	git_object object;
+	git_odb_object *odb_obj;
+	git_array_t(git_tree_entry) entries_arr;
 	git_vector entries;
-	git_pool pool;
 };
 
 struct git_treebuilder {
diff --git a/tests/diff/iterator.c b/tests/diff/iterator.c
index 8417e8ed4..25a23eda7 100644
--- a/tests/diff/iterator.c
+++ b/tests/diff/iterator.c
@@ -268,7 +268,7 @@ static void check_tree_entry(
 
 	cl_git_pass(git_iterator_current_tree_entry(&te, i));
 	cl_assert(te);
-	cl_assert(git_oid_streq(&te->oid, oid) == 0);
+	cl_assert(git_oid_streq(te->oid, oid) == 0);
 
 	cl_git_pass(git_iterator_current(&ie, i));
 	cl_git_pass(git_buf_sets(&path, ie->path));
diff --git a/tests/object/tree/attributes.c b/tests/object/tree/attributes.c
index 413514c48..8654dfa31 100644
--- a/tests/object/tree/attributes.c
+++ b/tests/object/tree/attributes.c
@@ -82,6 +82,7 @@ void test_object_tree_attributes__normalize_attributes_when_creating_a_tree_from
 	cl_git_pass(git_treebuilder_new(&builder, repo, tree));
 	
 	entry = git_treebuilder_get(builder, "old_mode.txt");
+	cl_assert(entry != NULL);
 	cl_assert_equal_i(
 		GIT_FILEMODE_BLOB,
 		git_tree_entry_filemode(entry));
@@ -92,6 +93,7 @@ void test_object_tree_attributes__normalize_attributes_when_creating_a_tree_from
 
 	cl_git_pass(git_tree_lookup(&tree, repo, &tid2));
 	entry = git_tree_entry_byname(tree, "old_mode.txt");
+	cl_assert(entry != NULL);
 	cl_assert_equal_i(
 		GIT_FILEMODE_BLOB,
 		git_tree_entry_filemode(entry));