[PATCH] fast-import: use binary search in tree_content_remove

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Signed-off-by: Jeff King <peff@xxxxxxxx>
---
> I should note that this patch doesn't handle removing entries from
> tree_content structs; I will work up a patch for that momentarily.

And here it is. However, I should note that this patch is _not_
necessary. I had originally thought that removal might destroy the
sorting that I added in the last patch, but it looks like the entry
isn't actually removed. Shawn, can you sanity check this?

This patch still has value, though, because it improves performance when
deleting entries from a large tree (I just didn't do that in my test
case, so it wasn't a problem before).

 fast-import.c |   33 +++++++++++++++++----------------
 1 files changed, 17 insertions(+), 16 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 4cd01ee..4322216 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1295,6 +1295,7 @@ static int tree_content_remove(struct tree_entry *root, const char *p)
 	const char *slash1;
 	unsigned int i, n;
 	struct tree_entry *e;
+	struct atom_str *name;
 
 	slash1 = strchr(p, '/');
 	if (slash1)
@@ -1302,24 +1303,24 @@ static int tree_content_remove(struct tree_entry *root, const char *p)
 	else
 		n = strlen(p);
 
-	for (i = 0; i < t->entry_count; i++) {
-		e = t->entries[i];
-		if (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {
-			if (!slash1 || !S_ISDIR(e->versions[1].mode))
-				goto del_entry;
-			if (!e->tree)
-				load_tree(e);
-			if (tree_content_remove(e, slash1 + 1)) {
-				for (n = 0; n < e->tree->entry_count; n++) {
-					if (e->tree->entries[n]->versions[1].mode) {
-						hashclr(root->versions[1].sha1);
-						return 1;
-					}
-				}
-				goto del_entry;
+	name = to_atom(p, n);
+	i = find_tree_entry(t, name);
+	if(i == -1)
+		return 0;
+	e = t->entries[i];
+
+	if (!slash1 || !S_ISDIR(e->versions[1].mode))
+		goto del_entry;
+	if (!e->tree)
+		load_tree(e);
+	if (tree_content_remove(e, slash1 + 1)) {
+		for (n = 0; n < e->tree->entry_count; n++) {
+			if (e->tree->entries[n]->versions[1].mode) {
+				hashclr(root->versions[1].sha1);
+				return 1;
 			}
-			return 0;
 		}
+		goto del_entry;
 	}
 	return 0;
 
-- 
1.5.0.3.931.g55c05
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]