From 2d9c58c69d1bab601e67b036d0546e85abcee7eb Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:18:33 -0700 Subject: [PATCH] Remove "tree->entries" tree-entry list from tree parser Instead, just use the tree buffer directly, and use the tree-walk infrastructure to walk the buffers instead of the tree-entry list. The tree-entry list is inefficient, and generates tons of small allocations for no good reason. The tree-walk infrastructure is generally no harder to use than following a linked list, and allows us to do most tree parsing in-place. Some programs still use the old tree-entry lists, and are a bit painful to convert without major surgery. For them we have a helper function that creates a temporary tree-entry list on demand. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- builtin-ls-tree.c | 2 +- builtin-read-tree.c | 4 +-- builtin-rev-list.c | 26 +++++++++------ fetch.c | 16 ++++++--- fsck-objects.c | 7 ++-- http-push.c | 30 +++++++++++------ revision.c | 3 +- tree.c | 81 +++++++++++++++++++++++++++++++-------------- tree.h | 4 ++- 9 files changed, 116 insertions(+), 57 deletions(-) diff --git a/builtin-ls-tree.c b/builtin-ls-tree.c index 48385d59f..b8d0d88ba 100644 --- a/builtin-ls-tree.c +++ b/builtin-ls-tree.c @@ -53,7 +53,7 @@ static int show_recursive(const char *base, int baselen, const char *pathname) } } -static int show_tree(unsigned char *sha1, const char *base, int baselen, +static int show_tree(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage) { int retval = 0; diff --git a/builtin-read-tree.c b/builtin-read-tree.c index 67492bfb4..480e6ed37 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -165,7 +165,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len, struct tree *tree = lookup_tree(posns[i]->sha1); any_dirs = 1; parse_tree(tree); - subposns[i] = tree->entries; + subposns[i] = create_tree_entry_list(tree); posns[i] = posns[i]->next; src[i + merge] = &df_conflict_entry; continue; @@ -370,7 +370,7 @@ static int unpack_trees(merge_fn_t fn) if (len) { posns = xmalloc(len * sizeof(struct tree_entry_list *)); for (i = 0; i < len; i++) { - posns[i] = ((struct tree *) posn->item)->entries; + posns[i] = create_tree_entry_list((struct tree *) posn->item); posn = posn->next; } if (unpack_trees_rec(posns, len, "", fn, &indpos)) diff --git a/builtin-rev-list.c b/builtin-rev-list.c index 94f520b90..6e2b898cc 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -113,7 +113,7 @@ static struct object_list **process_tree(struct tree *tree, const char *name) { struct object *obj = &tree->object; - struct tree_entry_list *entry; + struct tree_desc desc; struct name_path me; if (!revs.tree_objects) @@ -128,16 +128,22 @@ static struct object_list **process_tree(struct tree *tree, me.up = path; me.elem = name; me.elem_len = strlen(name); - entry = tree->entries; - tree->entries = NULL; - while (entry) { - struct tree_entry_list *next = entry->next; - if (entry->directory) - p = process_tree(lookup_tree(entry->sha1), p, &me, entry->name); + + desc.buf = tree->buffer; + desc.size = tree->size; + + while (desc.size) { + unsigned mode; + const char *name; + const unsigned char *sha1; + + sha1 = tree_entry_extract(&desc, &name, &mode); + update_tree_entry(&desc); + + if (S_ISDIR(mode)) + p = process_tree(lookup_tree(sha1), p, &me, name); else - p = process_blob(lookup_blob(entry->sha1), p, &me, entry->name); - free(entry); - entry = next; + p = process_blob(lookup_blob(sha1), p, &me, name); } free(tree->buffer); tree->buffer = NULL; diff --git a/fetch.c b/fetch.c index f7f890258..d9fe41f34 100644 --- a/fetch.c +++ b/fetch.c @@ -41,16 +41,22 @@ static int process_tree(struct tree *tree) if (parse_tree(tree)) return -1; - entry = tree->entries; - tree->entries = NULL; + entry = create_tree_entry_list(tree); while (entry) { struct tree_entry_list *next = entry->next; - if (process(entry->item.any)) - return -1; - free(entry->name); + + if (entry->directory) { + struct tree *tree = lookup_tree(entry->sha1); + process_tree(tree); + } else { + struct blob *blob = lookup_blob(entry->sha1); + process(&blob->object); + } free(entry); entry = next; } + free(tree->buffer); + tree->buffer = NULL; return 0; } diff --git a/fsck-objects.c b/fsck-objects.c index ed2eb278e..42778e87d 100644 --- a/fsck-objects.c +++ b/fsck-objects.c @@ -11,6 +11,7 @@ #include "cache-tree.h" #define REACHABLE 0x0001 +#define SEEN 0x0002 static int show_root = 0; static int show_tags = 0; @@ -161,7 +162,7 @@ static int fsck_tree(struct tree *item) struct tree_entry_list *entry, *last; last = NULL; - for (entry = item->entries; entry; entry = entry->next) { + for (entry = create_tree_entry_list(item); entry; entry = entry->next) { if (strchr(entry->name, '/')) has_full_path = 1; has_zero_pad |= entry->zeropad; @@ -205,7 +206,6 @@ static int fsck_tree(struct tree *item) } if (last) free(last); - item->entries = NULL; free(item->buffer); item->buffer = NULL; @@ -277,6 +277,9 @@ static int fsck_sha1(unsigned char *sha1) struct object *obj = parse_object(sha1); if (!obj) return error("%s: object not found", sha1_to_hex(sha1)); + if (obj->flags & SEEN) + return 0; + obj->flags |= SEEN; if (obj->type == blob_type) return 0; if (obj->type == tree_type) diff --git a/http-push.c b/http-push.c index f492a5d36..72ad89ce1 100644 --- a/http-push.c +++ b/http-push.c @@ -1704,6 +1704,7 @@ static struct object_list **process_blob(struct blob *blob, return p; obj->flags |= SEEN; + name = strdup(name); return add_object(obj, p, path, name); } @@ -1713,7 +1714,7 @@ static struct object_list **process_tree(struct tree *tree, const char *name) { struct object *obj = &tree->object; - struct tree_entry_list *entry; + struct tree_desc desc; struct name_path me; obj->flags |= LOCAL; @@ -1724,21 +1725,30 @@ static struct object_list **process_tree(struct tree *tree, die("bad tree object %s", sha1_to_hex(obj->sha1)); obj->flags |= SEEN; + name = strdup(name); p = add_object(obj, p, NULL, name); me.up = path; me.elem = name; me.elem_len = strlen(name); - entry = tree->entries; - tree->entries = NULL; - while (entry) { - struct tree_entry_list *next = entry->next; - if (entry->directory) - p = process_tree(lookup_tree(entry->sha1), p, &me, entry->name); + + desc.buf = tree->buffer; + desc.size = tree->size; + + while (desc.size) { + unsigned mode; + const char *name; + const unsigned char *sha1; + + sha1 = tree_entry_extract(&desc, &name, &mode); + update_tree_entry(&desc); + + if (S_ISDIR(mode)) + p = process_tree(lookup_tree(sha1), p, &me, name); else - p = process_blob(lookup_blob(entry->sha1), p, &me, entry->name); - free(entry); - entry = next; + p = process_blob(lookup_blob(sha1), p, &me, name); } + free(tree->buffer); + tree->buffer = NULL; return p; } diff --git a/revision.c b/revision.c index 8d70a6f77..c51ea833f 100644 --- a/revision.c +++ b/revision.c @@ -63,8 +63,7 @@ void mark_tree_uninteresting(struct tree *tree) return; if (parse_tree(tree) < 0) die("bad tree %s", sha1_to_hex(obj->sha1)); - entry = tree->entries; - tree->entries = NULL; + entry = create_tree_entry_list(tree); while (entry) { struct tree_entry_list *next = entry->next; if (entry->directory) diff --git a/tree.c b/tree.c index 88f8fd589..db6e59f20 100644 --- a/tree.c +++ b/tree.c @@ -151,22 +151,65 @@ struct tree *lookup_tree(const unsigned char *sha1) return (struct tree *) obj; } -int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) +static int track_tree_refs(struct tree *item) { + int n_refs = 0, i; + struct object_refs *refs; struct tree_desc desc; - struct tree_entry_list **list_p; - int n_refs = 0; + /* Count how many entries there are.. */ + desc.buf = item->buffer; + desc.size = item->size; + while (desc.size) { + n_refs++; + update_tree_entry(&desc); + } + + /* Allocate object refs and walk it again.. */ + i = 0; + refs = alloc_object_refs(n_refs); + desc.buf = item->buffer; + desc.size = item->size; + while (desc.size) { + unsigned mode; + const char *name; + const unsigned char *sha1; + struct object *obj; + + sha1 = tree_entry_extract(&desc, &name, &mode); + update_tree_entry(&desc); + if (S_ISDIR(mode)) + obj = &lookup_tree(sha1)->object; + else + obj = &lookup_blob(sha1)->object; + refs->ref[i++] = obj; + } + set_object_refs(&item->object, refs); + return 0; +} + +int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) +{ if (item->object.parsed) return 0; item->object.parsed = 1; item->buffer = buffer; item->size = size; - desc.buf = buffer; - desc.size = size; + if (track_object_refs) + track_tree_refs(item); + return 0; +} + +struct tree_entry_list *create_tree_entry_list(struct tree *tree) +{ + struct tree_desc desc; + struct tree_entry_list *ret = NULL; + struct tree_entry_list **list_p = &ret; + + desc.buf = tree->buffer; + desc.size = tree->size; - list_p = &item->entries; while (desc.size) { unsigned mode; const char *path; @@ -186,29 +229,19 @@ int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) entry->next = NULL; update_tree_entry(&desc); - n_refs++; *list_p = entry; list_p = &entry->next; } + return ret; +} - if (track_object_refs) { - struct tree_entry_list *entry; - unsigned i = 0; - struct object_refs *refs = alloc_object_refs(n_refs); - for (entry = item->entries; entry; entry = entry->next) { - struct object *obj; - - if (entry->directory) - obj = &lookup_tree(entry->sha1)->object; - else - obj = &lookup_blob(entry->sha1)->object; - refs->ref[i++] = obj; - } - - set_object_refs(&item->object, refs); +void free_tree_entry_list(struct tree_entry_list *list) +{ + while (list) { + struct tree_entry_list *next = list->next; + free(list); + list = next; } - - return 0; } int parse_tree(struct tree *item) diff --git a/tree.h b/tree.h index a27bae41b..c7b524861 100644 --- a/tree.h +++ b/tree.h @@ -20,9 +20,11 @@ struct tree { struct object object; void *buffer; unsigned long size; - struct tree_entry_list *entries; }; +struct tree_entry_list *create_tree_entry_list(struct tree *); +void free_tree_entry_list(struct tree_entry_list *); + struct tree *lookup_tree(const unsigned char *sha1); int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size); -- 2.26.2