[PATCH] fast-import: use binary search in tree_content_remove
- From
Jeff King <peff@peff.net>
- Date
- Mar 10, 2007, 19:40 UTC
- Message-ID
- <20070310194012.GA5126@coredump.intra.peff.net>
- In-Reply-To
- <20070310192304.GB3416@coredump.intra.peff.net>
Signed-off-by: Jeff King <peff@peff.net> ---
> 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