From d2eafb76611670d7573f9409b0c727019fe50e18 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sun, 28 May 2006 15:07:07 -0700 Subject: Add raw tree buffer info to "struct tree" This allows us to avoid allocating information for names etc, because we can just use the information from the tree buffer directly. We still keep the old "tree_entry_list" in struct tree as well, so old users aren't affected, apart from the fact that the allocations are different (if you free a tree entry, you should no longer free the name allocation for it, since it's allocated as part of "tree->buffer") Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- builtin-read-tree.c | 4 ++-- builtin-rev-list.c | 3 ++- fsck-objects.c | 7 +++---- object.c | 5 ++++- tree.c | 47 ++++++++++++++++++++++------------------------- tree.h | 4 +++- 6 files changed, 36 insertions(+), 34 deletions(-) diff --git a/builtin-read-tree.c b/builtin-read-tree.c index ec40d013c..740a8c7e6 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -38,7 +38,7 @@ static struct tree_entry_list df_conflict_list = { typedef int (*merge_fn_t)(struct cache_entry **src); -static int entcmp(char *name1, int dir1, char *name2, int dir2) +static int entcmp(const char *name1, int dir1, const char *name2, int dir2) { int len1 = strlen(name1); int len2 = strlen(name2); @@ -66,7 +66,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len, int src_size = len + 1; do { int i; - char *first; + const char *first; int firstdir = 0; int pathlen; unsigned ce_size; diff --git a/builtin-rev-list.c b/builtin-rev-list.c index 5277d3cf1..72c1549c7 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -136,10 +136,11 @@ static struct object_list **process_tree(struct tree *tree, p = process_tree(entry->item.tree, p, &me, entry->name); else p = process_blob(entry->item.blob, p, &me, entry->name); - free(entry->name); free(entry); entry = next; } + free(tree->buffer); + tree->buffer = NULL; return p; } diff --git a/fsck-objects.c b/fsck-objects.c index 59b25904c..a0290b09c 100644 --- a/fsck-objects.c +++ b/fsck-objects.c @@ -197,17 +197,16 @@ static int fsck_tree(struct tree *item) default: break; } - free(last->name); free(last); } last = entry; } - if (last) { - free(last->name); + if (last) free(last); - } item->entries = NULL; + free(item->buffer); + item->buffer = NULL; retval = 0; if (has_full_path) { diff --git a/object.c b/object.c index 4d46e0d5e..1a7823c23 100644 --- a/object.c +++ b/object.c @@ -200,8 +200,11 @@ struct object *parse_object(const unsigned char *sha1) obj = &blob->object; } else if (!strcmp(type, tree_type)) { struct tree *tree = lookup_tree(sha1); - parse_tree_buffer(tree, buffer, size); obj = &tree->object; + if (!tree->object.parsed) { + parse_tree_buffer(tree, buffer, size); + buffer = NULL; + } } else if (!strcmp(type, commit_type)) { struct commit *commit = lookup_commit(sha1); parse_commit_buffer(commit, buffer, size); diff --git a/tree.c b/tree.c index d599fb5e1..1e76d9cc1 100644 --- a/tree.c +++ b/tree.c @@ -3,6 +3,7 @@ #include "blob.h" #include "commit.h" #include "tag.h" +#include "tree-walk.h" #include const char *tree_type = "tree"; @@ -145,46 +146,45 @@ struct tree *lookup_tree(const unsigned char *sha1) int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) { - void *bufptr = buffer; + struct tree_desc desc; struct tree_entry_list **list_p; int n_refs = 0; if (item->object.parsed) return 0; item->object.parsed = 1; + item->buffer = buffer; + item->size = size; + + desc.buf = buffer; + desc.size = size; + list_p = &item->entries; - while (size) { - struct object *obj; + while (desc.size) { + unsigned mode; + const char *path; + const unsigned char *sha1; struct tree_entry_list *entry; - int len = 1+strlen(bufptr); - unsigned char *file_sha1 = bufptr + len; - char *path = strchr(bufptr, ' '); - unsigned int mode; - if (size < len + 20 || !path || - sscanf(bufptr, "%o", &mode) != 1) - return -1; + + sha1 = tree_entry_extract(&desc, &path, &mode); entry = xmalloc(sizeof(struct tree_entry_list)); - entry->name = strdup(path + 1); + entry->name = path; + entry->mode = mode; entry->directory = S_ISDIR(mode) != 0; entry->executable = (mode & S_IXUSR) != 0; entry->symlink = S_ISLNK(mode) != 0; - entry->zeropad = *(char *)bufptr == '0'; - entry->mode = mode; + entry->zeropad = *(const char *)(desc.buf) == '0'; entry->next = NULL; - bufptr += len + 20; - size -= len + 20; + update_tree_entry(&desc); if (entry->directory) { - entry->item.tree = lookup_tree(file_sha1); - obj = &entry->item.tree->object; + entry->item.tree = lookup_tree(sha1); } else { - entry->item.blob = lookup_blob(file_sha1); - obj = &entry->item.blob->object; + entry->item.blob = lookup_blob(sha1); } - if (obj) - n_refs++; + n_refs++; *list_p = entry; list_p = &entry->next; } @@ -206,7 +206,6 @@ int parse_tree(struct tree *item) char type[20]; void *buffer; unsigned long size; - int ret; if (item->object.parsed) return 0; @@ -219,9 +218,7 @@ int parse_tree(struct tree *item) return error("Object %s not a tree", sha1_to_hex(item->object.sha1)); } - ret = parse_tree_buffer(item, buffer, size); - free(buffer); - return ret; + return parse_tree_buffer(item, buffer, size); } struct tree *parse_tree_indirect(const unsigned char *sha1) diff --git a/tree.h b/tree.h index 330ab64bb..066ac5d5b 100644 --- a/tree.h +++ b/tree.h @@ -12,7 +12,7 @@ struct tree_entry_list { unsigned symlink : 1; unsigned zeropad : 1; unsigned int mode; - char *name; + const char *name; union { struct object *any; struct tree *tree; @@ -22,6 +22,8 @@ struct tree_entry_list { struct tree { struct object object; + void *buffer; + unsigned long size; struct tree_entry_list *entries; }; -- cgit v1.2.1 From a755dfe45c10ccd9f180d3c267602ad18d127d6a Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sun, 28 May 2006 15:10:04 -0700 Subject: Make "tree_entry" have a SHA1 instead of a union of object pointers This is preparatory work for further cleanups, where we try to make tree_entry look more like the more efficient tree-walk descriptor. Instead of having a union of pointers to blob/tree/objects, this just makes "struct tree_entry" have the raw SHA1, and makes all the users use that instead (often that implies adding a "lookup_tree(..)" on the sha1, but sometimes the user just wanted the SHA1 in the first place, and it just avoids an unnecessary indirection). Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- blame.c | 4 ++-- builtin-read-tree.c | 7 ++++--- builtin-rev-list.c | 4 ++-- fsck-objects.c | 1 + http-push.c | 4 ++-- object.c | 2 +- revision.c | 4 ++-- tree.c | 25 ++++++++++++++----------- tree.h | 8 ++------ 9 files changed, 30 insertions(+), 29 deletions(-) diff --git a/blame.c b/blame.c index 99ceea81d..88bfec262 100644 --- a/blame.c +++ b/blame.c @@ -149,7 +149,7 @@ static void free_patch(struct patch *p) free(p); } -static int get_blob_sha1_internal(unsigned char *sha1, const char *base, +static int get_blob_sha1_internal(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage); @@ -178,7 +178,7 @@ static int get_blob_sha1(struct tree *t, const char *pathname, return 0; } -static int get_blob_sha1_internal(unsigned char *sha1, const char *base, +static int get_blob_sha1_internal(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage) { diff --git a/builtin-read-tree.c b/builtin-read-tree.c index 740a8c7e6..f0b8dad6e 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -160,9 +160,10 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len, } if (posns[i]->directory) { + struct tree *tree = lookup_tree(posns[i]->sha1); any_dirs = 1; - parse_tree(posns[i]->item.tree); - subposns[i] = posns[i]->item.tree->entries; + parse_tree(tree); + subposns[i] = tree->entries; posns[i] = posns[i]->next; src[i + merge] = &df_conflict_entry; continue; @@ -186,7 +187,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len, any_files = 1; - memcpy(ce->sha1, posns[i]->item.any->sha1, 20); + memcpy(ce->sha1, posns[i]->sha1, 20); src[i + merge] = ce; subposns[i] = &df_conflict_list; posns[i] = posns[i]->next; diff --git a/builtin-rev-list.c b/builtin-rev-list.c index 72c1549c7..94f520b90 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -133,9 +133,9 @@ static struct object_list **process_tree(struct tree *tree, while (entry) { struct tree_entry_list *next = entry->next; if (entry->directory) - p = process_tree(entry->item.tree, p, &me, entry->name); + p = process_tree(lookup_tree(entry->sha1), p, &me, entry->name); else - p = process_blob(entry->item.blob, p, &me, entry->name); + p = process_blob(lookup_blob(entry->sha1), p, &me, entry->name); free(entry); entry = next; } diff --git a/fsck-objects.c b/fsck-objects.c index a0290b09c..44b646540 100644 --- a/fsck-objects.c +++ b/fsck-objects.c @@ -441,6 +441,7 @@ int main(int argc, char **argv) { int i, heads; + track_object_refs = 1; setup_git_directory(); for (i = 1; i < argc; i++) { diff --git a/http-push.c b/http-push.c index b4327d924..f492a5d36 100644 --- a/http-push.c +++ b/http-push.c @@ -1733,9 +1733,9 @@ static struct object_list **process_tree(struct tree *tree, while (entry) { struct tree_entry_list *next = entry->next; if (entry->directory) - p = process_tree(entry->item.tree, p, &me, entry->name); + p = process_tree(lookup_tree(entry->sha1), p, &me, entry->name); else - p = process_blob(entry->item.blob, p, &me, entry->name); + p = process_blob(lookup_blob(entry->sha1), p, &me, entry->name); free(entry); entry = next; } diff --git a/object.c b/object.c index 1a7823c23..9adc87479 100644 --- a/object.c +++ b/object.c @@ -9,7 +9,7 @@ struct object **objs; static int nr_objs; int obj_allocs; -int track_object_refs = 1; +int track_object_refs = 0; static int hashtable_index(const unsigned char *sha1) { diff --git a/revision.c b/revision.c index 42c077a4c..8d70a6f77 100644 --- a/revision.c +++ b/revision.c @@ -68,9 +68,9 @@ void mark_tree_uninteresting(struct tree *tree) while (entry) { struct tree_entry_list *next = entry->next; if (entry->directory) - mark_tree_uninteresting(entry->item.tree); + mark_tree_uninteresting(lookup_tree(entry->sha1)); else - mark_blob_uninteresting(entry->item.blob); + mark_blob_uninteresting(lookup_blob(entry->sha1)); free(entry); entry = next; } diff --git a/tree.c b/tree.c index 1e76d9cc1..88c221903 100644 --- a/tree.c +++ b/tree.c @@ -8,7 +8,7 @@ const char *tree_type = "tree"; -static int read_one_entry(unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage) +static int read_one_entry(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage) { int len; unsigned int size; @@ -89,7 +89,7 @@ int read_tree_recursive(struct tree *tree, current->mode, match)) continue; - switch (fn(current->item.any->sha1, base, baselen, + switch (fn(current->sha1, base, baselen, current->name, current->mode, stage)) { case 0: continue; @@ -107,7 +107,7 @@ int read_tree_recursive(struct tree *tree, memcpy(newbase, base, baselen); memcpy(newbase + baselen, current->name, pathlen); newbase[baselen + pathlen] = '/'; - retval = read_tree_recursive(current->item.tree, + retval = read_tree_recursive(lookup_tree(current->sha1), newbase, baselen + pathlen + 1, stage, match, fn); @@ -170,6 +170,7 @@ int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) entry = xmalloc(sizeof(struct tree_entry_list)); entry->name = path; + entry->sha1 = sha1; entry->mode = mode; entry->directory = S_ISDIR(mode) != 0; entry->executable = (mode & S_IXUSR) != 0; @@ -178,12 +179,6 @@ int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) entry->next = NULL; update_tree_entry(&desc); - - if (entry->directory) { - entry->item.tree = lookup_tree(sha1); - } else { - entry->item.blob = lookup_blob(sha1); - } n_refs++; *list_p = entry; list_p = &entry->next; @@ -193,8 +188,16 @@ int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) 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) - refs->ref[i++] = entry->item.any; + 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); } diff --git a/tree.h b/tree.h index 066ac5d5b..a27bae41b 100644 --- a/tree.h +++ b/tree.h @@ -13,11 +13,7 @@ struct tree_entry_list { unsigned zeropad : 1; unsigned int mode; const char *name; - union { - struct object *any; - struct tree *tree; - struct blob *blob; - } item; + const unsigned char *sha1; }; struct tree { @@ -37,7 +33,7 @@ int parse_tree(struct tree *tree); struct tree *parse_tree_indirect(const unsigned char *sha1); #define READ_TREE_RECURSIVE 1 -typedef int (*read_tree_fn_t)(unsigned char *, const char *, int, const char *, unsigned int, int); +typedef int (*read_tree_fn_t)(const unsigned char *, const char *, int, const char *, unsigned int, int); extern int read_tree_recursive(struct tree *tree, const char *base, int baselen, -- cgit v1.2.1 From 2522c13244c13fe3a9f0769ea6294dce08e6596c Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sun, 28 May 2006 15:11:28 -0700 Subject: Switch "read_tree_recursive()" over to tree-walk functionality Don't use the tree_entry list, it really had no major reason not to just walk the raw tree instead. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- tree.c | 33 ++++++++++++++++++++------------- 1 file changed, 20 insertions(+), 13 deletions(-) diff --git a/tree.c b/tree.c index 88c221903..88f8fd589 100644 --- a/tree.c +++ b/tree.c @@ -78,19 +78,26 @@ int read_tree_recursive(struct tree *tree, int stage, const char **match, read_tree_fn_t fn) { - struct tree_entry_list *list; + struct tree_desc desc; + if (parse_tree(tree)) return -1; - list = tree->entries; - while (list) { - struct tree_entry_list *current = list; - list = list->next; - if (!match_tree_entry(base, baselen, current->name, - current->mode, match)) + + 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 (!match_tree_entry(base, baselen, name, mode, match)) continue; - switch (fn(current->sha1, base, baselen, - current->name, current->mode, stage)) { + switch (fn(sha1, base, baselen, name, mode, stage)) { case 0: continue; case READ_TREE_RECURSIVE: @@ -98,16 +105,16 @@ int read_tree_recursive(struct tree *tree, default: return -1; } - if (current->directory) { + if (S_ISDIR(mode)) { int retval; - int pathlen = strlen(current->name); + int pathlen = strlen(name); char *newbase; newbase = xmalloc(baselen + 1 + pathlen); memcpy(newbase, base, baselen); - memcpy(newbase + baselen, current->name, pathlen); + memcpy(newbase + baselen, name, pathlen); newbase[baselen + pathlen] = '/'; - retval = read_tree_recursive(lookup_tree(current->sha1), + retval = read_tree_recursive(lookup_tree(sha1), newbase, baselen + pathlen + 1, stage, match, fn); -- cgit v1.2.1 From 097dc3d8c32f4b85bf9701d5e1de98999ac25c1c Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Sun, 28 May 2006 15:13:53 -0700 Subject: Remove "tree->entries" tree-entry list from tree parser This finally removes the tree-entry list from "struct tree", since most of the users can just use the tree-walk infrastructure to walk the raw tree 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. We can convert those too eventually, but with this they no longer affect any users who don't need the explicit lists. 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 f0b8dad6e..da0731ca0 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -163,7 +163,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; @@ -368,7 +368,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 44b646540..ec99a7a6c 100644 --- a/fsck-objects.c +++ b/fsck-objects.c @@ -10,6 +10,7 @@ #include "pack.h" #define REACHABLE 0x0001 +#define SEEN 0x0002 static int show_root = 0; static int show_tags = 0; @@ -160,7 +161,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; @@ -204,7 +205,6 @@ static int fsck_tree(struct tree *item) } if (last) free(last); - item->entries = NULL; free(item->buffer); item->buffer = NULL; @@ -276,6 +276,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); -- cgit v1.2.1 From 136f2e548a34f1f504b0f062f87ddf33e8d6e83b Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:16:12 -0700 Subject: Make "struct tree" contain the pointer to the tree buffer This allows us to avoid allocating information for names etc, because we can just use the information from the tree buffer directly. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- builtin-read-tree.c | 4 ++-- builtin-rev-list.c | 3 ++- fsck-objects.c | 7 +++---- object.c | 5 ++++- tree.c | 47 ++++++++++++++++++++++------------------------- tree.h | 4 +++- 6 files changed, 36 insertions(+), 34 deletions(-) diff --git a/builtin-read-tree.c b/builtin-read-tree.c index 716f79251..6876f3d79 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -39,7 +39,7 @@ static struct tree_entry_list df_conflict_list = { typedef int (*merge_fn_t)(struct cache_entry **src); -static int entcmp(char *name1, int dir1, char *name2, int dir2) +static int entcmp(const char *name1, int dir1, const char *name2, int dir2) { int len1 = strlen(name1); int len2 = strlen(name2); @@ -67,7 +67,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len, int src_size = len + 1; do { int i; - char *first; + const char *first; int firstdir = 0; int pathlen; unsigned ce_size; diff --git a/builtin-rev-list.c b/builtin-rev-list.c index 5277d3cf1..72c1549c7 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -136,10 +136,11 @@ static struct object_list **process_tree(struct tree *tree, p = process_tree(entry->item.tree, p, &me, entry->name); else p = process_blob(entry->item.blob, p, &me, entry->name); - free(entry->name); free(entry); entry = next; } + free(tree->buffer); + tree->buffer = NULL; return p; } diff --git a/fsck-objects.c b/fsck-objects.c index 1922b6d84..5e65df436 100644 --- a/fsck-objects.c +++ b/fsck-objects.c @@ -198,17 +198,16 @@ static int fsck_tree(struct tree *item) default: break; } - free(last->name); free(last); } last = entry; } - if (last) { - free(last->name); + if (last) free(last); - } item->entries = NULL; + free(item->buffer); + item->buffer = NULL; retval = 0; if (has_full_path) { diff --git a/object.c b/object.c index 4d46e0d5e..1a7823c23 100644 --- a/object.c +++ b/object.c @@ -200,8 +200,11 @@ struct object *parse_object(const unsigned char *sha1) obj = &blob->object; } else if (!strcmp(type, tree_type)) { struct tree *tree = lookup_tree(sha1); - parse_tree_buffer(tree, buffer, size); obj = &tree->object; + if (!tree->object.parsed) { + parse_tree_buffer(tree, buffer, size); + buffer = NULL; + } } else if (!strcmp(type, commit_type)) { struct commit *commit = lookup_commit(sha1); parse_commit_buffer(commit, buffer, size); diff --git a/tree.c b/tree.c index d599fb5e1..1e76d9cc1 100644 --- a/tree.c +++ b/tree.c @@ -3,6 +3,7 @@ #include "blob.h" #include "commit.h" #include "tag.h" +#include "tree-walk.h" #include const char *tree_type = "tree"; @@ -145,46 +146,45 @@ struct tree *lookup_tree(const unsigned char *sha1) int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) { - void *bufptr = buffer; + struct tree_desc desc; struct tree_entry_list **list_p; int n_refs = 0; if (item->object.parsed) return 0; item->object.parsed = 1; + item->buffer = buffer; + item->size = size; + + desc.buf = buffer; + desc.size = size; + list_p = &item->entries; - while (size) { - struct object *obj; + while (desc.size) { + unsigned mode; + const char *path; + const unsigned char *sha1; struct tree_entry_list *entry; - int len = 1+strlen(bufptr); - unsigned char *file_sha1 = bufptr + len; - char *path = strchr(bufptr, ' '); - unsigned int mode; - if (size < len + 20 || !path || - sscanf(bufptr, "%o", &mode) != 1) - return -1; + + sha1 = tree_entry_extract(&desc, &path, &mode); entry = xmalloc(sizeof(struct tree_entry_list)); - entry->name = strdup(path + 1); + entry->name = path; + entry->mode = mode; entry->directory = S_ISDIR(mode) != 0; entry->executable = (mode & S_IXUSR) != 0; entry->symlink = S_ISLNK(mode) != 0; - entry->zeropad = *(char *)bufptr == '0'; - entry->mode = mode; + entry->zeropad = *(const char *)(desc.buf) == '0'; entry->next = NULL; - bufptr += len + 20; - size -= len + 20; + update_tree_entry(&desc); if (entry->directory) { - entry->item.tree = lookup_tree(file_sha1); - obj = &entry->item.tree->object; + entry->item.tree = lookup_tree(sha1); } else { - entry->item.blob = lookup_blob(file_sha1); - obj = &entry->item.blob->object; + entry->item.blob = lookup_blob(sha1); } - if (obj) - n_refs++; + n_refs++; *list_p = entry; list_p = &entry->next; } @@ -206,7 +206,6 @@ int parse_tree(struct tree *item) char type[20]; void *buffer; unsigned long size; - int ret; if (item->object.parsed) return 0; @@ -219,9 +218,7 @@ int parse_tree(struct tree *item) return error("Object %s not a tree", sha1_to_hex(item->object.sha1)); } - ret = parse_tree_buffer(item, buffer, size); - free(buffer); - return ret; + return parse_tree_buffer(item, buffer, size); } struct tree *parse_tree_indirect(const unsigned char *sha1) diff --git a/tree.h b/tree.h index 330ab64bb..066ac5d5b 100644 --- a/tree.h +++ b/tree.h @@ -12,7 +12,7 @@ struct tree_entry_list { unsigned symlink : 1; unsigned zeropad : 1; unsigned int mode; - char *name; + const char *name; union { struct object *any; struct tree *tree; @@ -22,6 +22,8 @@ struct tree_entry_list { struct tree { struct object object; + void *buffer; + unsigned long size; struct tree_entry_list *entries; }; -- cgit v1.2.1 From 3a7c352bd0ecac4b4c96c0995d61de9ef8d814f9 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:16:46 -0700 Subject: Make "tree_entry" have a SHA1 instead of a union of object pointers This is preparatory work for further cleanups, where we try to make tree_entry look more like the more efficient tree-walk descriptor. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- blame.c | 4 ++-- builtin-read-tree.c | 9 +++++---- builtin-rev-list.c | 4 ++-- fsck-objects.c | 1 + http-push.c | 4 ++-- object.c | 2 +- revision.c | 4 ++-- tree.c | 25 ++++++++++++++----------- tree.h | 8 ++------ 9 files changed, 31 insertions(+), 30 deletions(-) diff --git a/blame.c b/blame.c index 99ceea81d..88bfec262 100644 --- a/blame.c +++ b/blame.c @@ -149,7 +149,7 @@ static void free_patch(struct patch *p) free(p); } -static int get_blob_sha1_internal(unsigned char *sha1, const char *base, +static int get_blob_sha1_internal(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage); @@ -178,7 +178,7 @@ static int get_blob_sha1(struct tree *t, const char *pathname, return 0; } -static int get_blob_sha1_internal(unsigned char *sha1, const char *base, +static int get_blob_sha1_internal(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage) { diff --git a/builtin-read-tree.c b/builtin-read-tree.c index 6876f3d79..5e513c85c 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -161,9 +161,10 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len, } if (posns[i]->directory) { + struct tree *tree = lookup_tree(posns[i]->sha1); any_dirs = 1; - parse_tree(posns[i]->item.tree); - subposns[i] = posns[i]->item.tree->entries; + parse_tree(tree); + subposns[i] = tree->entries; posns[i] = posns[i]->next; src[i + merge] = &df_conflict_entry; continue; @@ -187,7 +188,7 @@ static int unpack_trees_rec(struct tree_entry_list **posns, int len, any_files = 1; - memcpy(ce->sha1, posns[i]->item.any->sha1, 20); + memcpy(ce->sha1, posns[i]->sha1, 20); src[i + merge] = ce; subposns[i] = &df_conflict_list; posns[i] = posns[i]->next; @@ -783,7 +784,7 @@ static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree) cnt++; else { struct cache_tree_sub *sub; - struct tree *subtree = (struct tree *)ent->item.tree; + struct tree *subtree = lookup_tree(ent->sha1); if (!subtree->object.parsed) parse_tree(subtree); sub = cache_tree_sub(it, ent->name); diff --git a/builtin-rev-list.c b/builtin-rev-list.c index 72c1549c7..94f520b90 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -133,9 +133,9 @@ static struct object_list **process_tree(struct tree *tree, while (entry) { struct tree_entry_list *next = entry->next; if (entry->directory) - p = process_tree(entry->item.tree, p, &me, entry->name); + p = process_tree(lookup_tree(entry->sha1), p, &me, entry->name); else - p = process_blob(entry->item.blob, p, &me, entry->name); + p = process_blob(lookup_blob(entry->sha1), p, &me, entry->name); free(entry); entry = next; } diff --git a/fsck-objects.c b/fsck-objects.c index 5e65df436..ed2eb278e 100644 --- a/fsck-objects.c +++ b/fsck-objects.c @@ -464,6 +464,7 @@ int main(int argc, char **argv) { int i, heads; + track_object_refs = 1; setup_git_directory(); for (i = 1; i < argc; i++) { diff --git a/http-push.c b/http-push.c index b4327d924..f492a5d36 100644 --- a/http-push.c +++ b/http-push.c @@ -1733,9 +1733,9 @@ static struct object_list **process_tree(struct tree *tree, while (entry) { struct tree_entry_list *next = entry->next; if (entry->directory) - p = process_tree(entry->item.tree, p, &me, entry->name); + p = process_tree(lookup_tree(entry->sha1), p, &me, entry->name); else - p = process_blob(entry->item.blob, p, &me, entry->name); + p = process_blob(lookup_blob(entry->sha1), p, &me, entry->name); free(entry); entry = next; } diff --git a/object.c b/object.c index 1a7823c23..9adc87479 100644 --- a/object.c +++ b/object.c @@ -9,7 +9,7 @@ struct object **objs; static int nr_objs; int obj_allocs; -int track_object_refs = 1; +int track_object_refs = 0; static int hashtable_index(const unsigned char *sha1) { diff --git a/revision.c b/revision.c index 42c077a4c..8d70a6f77 100644 --- a/revision.c +++ b/revision.c @@ -68,9 +68,9 @@ void mark_tree_uninteresting(struct tree *tree) while (entry) { struct tree_entry_list *next = entry->next; if (entry->directory) - mark_tree_uninteresting(entry->item.tree); + mark_tree_uninteresting(lookup_tree(entry->sha1)); else - mark_blob_uninteresting(entry->item.blob); + mark_blob_uninteresting(lookup_blob(entry->sha1)); free(entry); entry = next; } diff --git a/tree.c b/tree.c index 1e76d9cc1..88c221903 100644 --- a/tree.c +++ b/tree.c @@ -8,7 +8,7 @@ const char *tree_type = "tree"; -static int read_one_entry(unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage) +static int read_one_entry(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage) { int len; unsigned int size; @@ -89,7 +89,7 @@ int read_tree_recursive(struct tree *tree, current->mode, match)) continue; - switch (fn(current->item.any->sha1, base, baselen, + switch (fn(current->sha1, base, baselen, current->name, current->mode, stage)) { case 0: continue; @@ -107,7 +107,7 @@ int read_tree_recursive(struct tree *tree, memcpy(newbase, base, baselen); memcpy(newbase + baselen, current->name, pathlen); newbase[baselen + pathlen] = '/'; - retval = read_tree_recursive(current->item.tree, + retval = read_tree_recursive(lookup_tree(current->sha1), newbase, baselen + pathlen + 1, stage, match, fn); @@ -170,6 +170,7 @@ int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) entry = xmalloc(sizeof(struct tree_entry_list)); entry->name = path; + entry->sha1 = sha1; entry->mode = mode; entry->directory = S_ISDIR(mode) != 0; entry->executable = (mode & S_IXUSR) != 0; @@ -178,12 +179,6 @@ int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) entry->next = NULL; update_tree_entry(&desc); - - if (entry->directory) { - entry->item.tree = lookup_tree(sha1); - } else { - entry->item.blob = lookup_blob(sha1); - } n_refs++; *list_p = entry; list_p = &entry->next; @@ -193,8 +188,16 @@ int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) 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) - refs->ref[i++] = entry->item.any; + 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); } diff --git a/tree.h b/tree.h index 066ac5d5b..a27bae41b 100644 --- a/tree.h +++ b/tree.h @@ -13,11 +13,7 @@ struct tree_entry_list { unsigned zeropad : 1; unsigned int mode; const char *name; - union { - struct object *any; - struct tree *tree; - struct blob *blob; - } item; + const unsigned char *sha1; }; struct tree { @@ -37,7 +33,7 @@ int parse_tree(struct tree *tree); struct tree *parse_tree_indirect(const unsigned char *sha1); #define READ_TREE_RECURSIVE 1 -typedef int (*read_tree_fn_t)(unsigned char *, const char *, int, const char *, unsigned int, int); +typedef int (*read_tree_fn_t)(const unsigned char *, const char *, int, const char *, unsigned int, int); extern int read_tree_recursive(struct tree *tree, const char *base, int baselen, -- cgit v1.2.1 From 0790a42a502701c7b58e9ad4123e46bf46bbf319 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:17:28 -0700 Subject: Switch "read_tree_recursive()" over to tree-walk functionality Don't use the tree_entry list any more. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- tree.c | 33 ++++++++++++++++++++------------- 1 file changed, 20 insertions(+), 13 deletions(-) diff --git a/tree.c b/tree.c index 88c221903..88f8fd589 100644 --- a/tree.c +++ b/tree.c @@ -78,19 +78,26 @@ int read_tree_recursive(struct tree *tree, int stage, const char **match, read_tree_fn_t fn) { - struct tree_entry_list *list; + struct tree_desc desc; + if (parse_tree(tree)) return -1; - list = tree->entries; - while (list) { - struct tree_entry_list *current = list; - list = list->next; - if (!match_tree_entry(base, baselen, current->name, - current->mode, match)) + + 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 (!match_tree_entry(base, baselen, name, mode, match)) continue; - switch (fn(current->sha1, base, baselen, - current->name, current->mode, stage)) { + switch (fn(sha1, base, baselen, name, mode, stage)) { case 0: continue; case READ_TREE_RECURSIVE: @@ -98,16 +105,16 @@ int read_tree_recursive(struct tree *tree, default: return -1; } - if (current->directory) { + if (S_ISDIR(mode)) { int retval; - int pathlen = strlen(current->name); + int pathlen = strlen(name); char *newbase; newbase = xmalloc(baselen + 1 + pathlen); memcpy(newbase, base, baselen); - memcpy(newbase + baselen, current->name, pathlen); + memcpy(newbase + baselen, name, pathlen); newbase[baselen + pathlen] = '/'; - retval = read_tree_recursive(lookup_tree(current->sha1), + retval = read_tree_recursive(lookup_tree(sha1), newbase, baselen + pathlen + 1, stage, match, fn); -- cgit v1.2.1 From 1ccf5a345a6e7974ec0380eed735c2db97e50b4c Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:18:00 -0700 Subject: builtin-read-tree.c: avoid tree_entry_list in prime_cache_tree_rec() Use the raw tree walker instead. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- builtin-read-tree.c | 20 +++++++++++++++----- 1 file changed, 15 insertions(+), 5 deletions(-) diff --git a/builtin-read-tree.c b/builtin-read-tree.c index 5e513c85c..67492bfb4 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -9,6 +9,7 @@ #include "object.h" #include "tree.h" +#include "tree-walk.h" #include "cache-tree.h" #include #include @@ -775,19 +776,28 @@ static int read_cache_unmerged(void) static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree) { - struct tree_entry_list *ent; + struct tree_desc desc; int cnt; memcpy(it->sha1, tree->object.sha1, 20); - for (cnt = 0, ent = tree->entries; ent; ent = ent->next) { - if (!ent->directory) + desc.buf = tree->buffer; + desc.size = tree->size; + cnt = 0; + 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)) cnt++; else { struct cache_tree_sub *sub; - struct tree *subtree = lookup_tree(ent->sha1); + struct tree *subtree = lookup_tree(sha1); if (!subtree->object.parsed) parse_tree(subtree); - sub = cache_tree_sub(it, ent->name); + sub = cache_tree_sub(it, name); sub->cache_tree = cache_tree(); prime_cache_tree_rec(sub->cache_tree, subtree); cnt += sub->cache_tree->entry_count; -- cgit v1.2.1 From 2d9c58c69d1bab601e67b036d0546e85abcee7eb Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:18:33 -0700 Subject: 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); -- cgit v1.2.1 From e9a95bef7f9648b3827813906582bb8a6d922d21 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:19:02 -0700 Subject: fsck-objects: avoid unnecessary tree_entry_list usage Prime example of where the raw tree parser is easier for everybody. [jc: "Aieee" one-liner fix from the list applied. ] Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- fsck-objects.c | 57 ++++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 36 insertions(+), 21 deletions(-) diff --git a/fsck-objects.c b/fsck-objects.c index 42778e87d..33ce366e9 100644 --- a/fsck-objects.c +++ b/fsck-objects.c @@ -9,6 +9,7 @@ #include "refs.h" #include "pack.h" #include "cache-tree.h" +#include "tree-walk.h" #define REACHABLE 0x0001 #define SEEN 0x0002 @@ -116,15 +117,15 @@ static void check_connectivity(void) #define TREE_UNORDERED (-1) #define TREE_HAS_DUPS (-2) -static int verify_ordered(struct tree_entry_list *a, struct tree_entry_list *b) +static int verify_ordered(unsigned mode1, const char *name1, unsigned mode2, const char *name2) { - int len1 = strlen(a->name); - int len2 = strlen(b->name); + int len1 = strlen(name1); + int len2 = strlen(name2); int len = len1 < len2 ? len1 : len2; unsigned char c1, c2; int cmp; - cmp = memcmp(a->name, b->name, len); + cmp = memcmp(name1, name2, len); if (cmp < 0) return 0; if (cmp > 0) @@ -135,8 +136,8 @@ static int verify_ordered(struct tree_entry_list *a, struct tree_entry_list *b) * Now we need to order the next one, but turn * a '\0' into a '/' for a directory entry. */ - c1 = a->name[len]; - c2 = b->name[len]; + c1 = name1[len]; + c2 = name2[len]; if (!c1 && !c2) /* * git-write-tree used to write out a nonsense tree that has @@ -144,9 +145,9 @@ static int verify_ordered(struct tree_entry_list *a, struct tree_entry_list *b) * sure we do not have duplicate entries. */ return TREE_HAS_DUPS; - if (!c1 && a->directory) + if (!c1 && S_ISDIR(mode1)) c1 = '/'; - if (!c2 && b->directory) + if (!c2 && S_ISDIR(mode2)) c2 = '/'; return c1 < c2 ? 0 : TREE_UNORDERED; } @@ -159,17 +160,32 @@ static int fsck_tree(struct tree *item) int has_bad_modes = 0; int has_dup_entries = 0; int not_properly_sorted = 0; - struct tree_entry_list *entry, *last; + struct tree_desc desc; + unsigned o_mode; + const char *o_name; + const unsigned char *o_sha1; - last = NULL; - for (entry = create_tree_entry_list(item); entry; entry = entry->next) { - if (strchr(entry->name, '/')) + desc.buf = item->buffer; + desc.size = item->size; + + o_mode = 0; + o_name = NULL; + o_sha1 = NULL; + while (desc.size) { + unsigned mode; + const char *name; + const unsigned char *sha1; + + sha1 = tree_entry_extract(&desc, &name, &mode); + + if (strchr(name, '/')) has_full_path = 1; - has_zero_pad |= entry->zeropad; + has_zero_pad |= *(char *)desc.buf == '0'; + update_tree_entry(&desc); - switch (entry->mode) { + switch (mode) { /* - * Standard modes.. + * Standard modes.. */ case S_IFREG | 0755: case S_IFREG | 0644: @@ -188,8 +204,8 @@ static int fsck_tree(struct tree *item) has_bad_modes = 1; } - if (last) { - switch (verify_ordered(last, entry)) { + if (o_name) { + switch (verify_ordered(o_mode, o_name, mode, name)) { case TREE_UNORDERED: not_properly_sorted = 1; break; @@ -199,13 +215,12 @@ static int fsck_tree(struct tree *item) default: break; } - free(last); } - last = entry; + o_mode = mode; + o_name = name; + o_sha1 = sha1; } - if (last) - free(last); free(item->buffer); item->buffer = NULL; -- cgit v1.2.1 From 3bc1eca91e5230739cfb488e63fae35a166a07de Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:19:37 -0700 Subject: Remove unused "zeropad" entry from tree_list_entry That was a hack, only needed because 'git fsck-objects' didn't look at the raw tree format. Now that fsck traverses the tree itself, we can drop it. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- tree.c | 3 +-- tree.h | 1 - 2 files changed, 1 insertion(+), 3 deletions(-) diff --git a/tree.c b/tree.c index db6e59f20..47318ef89 100644 --- a/tree.c +++ b/tree.c @@ -217,6 +217,7 @@ struct tree_entry_list *create_tree_entry_list(struct tree *tree) struct tree_entry_list *entry; sha1 = tree_entry_extract(&desc, &path, &mode); + update_tree_entry(&desc); entry = xmalloc(sizeof(struct tree_entry_list)); entry->name = path; @@ -225,10 +226,8 @@ struct tree_entry_list *create_tree_entry_list(struct tree *tree) entry->directory = S_ISDIR(mode) != 0; entry->executable = (mode & S_IXUSR) != 0; entry->symlink = S_ISLNK(mode) != 0; - entry->zeropad = *(const char *)(desc.buf) == '0'; entry->next = NULL; - update_tree_entry(&desc); *list_p = entry; list_p = &entry->next; } diff --git a/tree.h b/tree.h index c7b524861..6a875464b 100644 --- a/tree.h +++ b/tree.h @@ -10,7 +10,6 @@ struct tree_entry_list { unsigned directory : 1; unsigned executable : 1; unsigned symlink : 1; - unsigned zeropad : 1; unsigned int mode; const char *name; const unsigned char *sha1; -- cgit v1.2.1 From f75e53edb38c97c8b21b69d4fc00d5419199ae4b Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:20:14 -0700 Subject: Convert "mark_tree_uninteresting()" to raw tree walker Not very many users to go.. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- revision.c | 31 ++++++++++++++++++++++--------- 1 file changed, 22 insertions(+), 9 deletions(-) diff --git a/revision.c b/revision.c index c51ea833f..8e93e40bb 100644 --- a/revision.c +++ b/revision.c @@ -53,8 +53,8 @@ static void mark_blob_uninteresting(struct blob *blob) void mark_tree_uninteresting(struct tree *tree) { + struct tree_desc desc; struct object *obj = &tree->object; - struct tree_entry_list *entry; if (obj->flags & UNINTERESTING) return; @@ -63,16 +63,29 @@ void mark_tree_uninteresting(struct tree *tree) return; if (parse_tree(tree) < 0) die("bad tree %s", sha1_to_hex(obj->sha1)); - entry = create_tree_entry_list(tree); - while (entry) { - struct tree_entry_list *next = entry->next; - if (entry->directory) - mark_tree_uninteresting(lookup_tree(entry->sha1)); + + 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)) + mark_tree_uninteresting(lookup_tree(sha1)); else - mark_blob_uninteresting(lookup_blob(entry->sha1)); - free(entry); - entry = next; + mark_blob_uninteresting(lookup_blob(sha1)); } + + /* + * We don't care about the tree any more + * after it has been marked uninteresting. + */ + free(tree->buffer); + tree->buffer = NULL; } void mark_parents_uninteresting(struct commit *commit) -- cgit v1.2.1 From 1bc995a3920da4e9143ccf9d34bdabf70ab8a211 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:20:48 -0700 Subject: Convert fetch.c: process_tree() to raw tree walker This leaves only the horrid code in builtin-read-tree.c using the old interface. Some day I will gather the strength to tackle that one too. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- fetch.c | 24 +++++++++++++++--------- 1 file changed, 15 insertions(+), 9 deletions(-) diff --git a/fetch.c b/fetch.c index d9fe41f34..976a5a459 100644 --- a/fetch.c +++ b/fetch.c @@ -3,6 +3,7 @@ #include "cache.h" #include "commit.h" #include "tree.h" +#include "tree-walk.h" #include "tag.h" #include "blob.h" #include "refs.h" @@ -36,27 +37,32 @@ static int process(struct object *obj); static int process_tree(struct tree *tree) { - struct tree_entry_list *entry; + struct tree_desc desc; if (parse_tree(tree)) return -1; - entry = create_tree_entry_list(tree); - while (entry) { - struct tree_entry_list *next = entry->next; + desc.buf = tree->buffer; + desc.size = tree->size; + while (desc.size) { + unsigned mode; + const char *name; + const unsigned char *sha1; - if (entry->directory) { - struct tree *tree = lookup_tree(entry->sha1); + sha1 = tree_entry_extract(&desc, &name, &mode); + update_tree_entry(&desc); + + if (S_ISDIR(mode)) { + struct tree *tree = lookup_tree(sha1); process_tree(tree); } else { - struct blob *blob = lookup_blob(entry->sha1); + struct blob *blob = lookup_blob(sha1); process(&blob->object); } - free(entry); - entry = next; } free(tree->buffer); tree->buffer = NULL; + tree->size = 0; return 0; } -- cgit v1.2.1 From 15b5536ee47c6684806edd7725adbbdede9fb95c Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Mon, 29 May 2006 12:21:28 -0700 Subject: Remove last vestiges of generic tree_entry_list The old tree_entry_list is dead, long live the unified single tree parser. Yes, we now still have a compatibility function to create a bogus tree_entry_list in builtin-read-tree.c, but that is now entirely local to that very messy piece of code. I'd love to clean read-tree.c up too, but I'm too scared right now, so the best I can do is to just contain the damage, and try to make sure that no new users of the tree_entry_list sprout up by not having it as an exported interface any more. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- builtin-read-tree.c | 45 ++++++++++++++++++++++++++++++++++++++++++++- tree.c | 42 ------------------------------------------ tree.h | 13 ------------- 3 files changed, 44 insertions(+), 56 deletions(-) diff --git a/builtin-read-tree.c b/builtin-read-tree.c index 480e6ed37..00cdb5a6d 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -30,7 +30,17 @@ static int merge_size = 0; static struct object_list *trees = NULL; -static struct cache_entry df_conflict_entry = { +static struct cache_entry df_conflict_entry = { +}; + +struct tree_entry_list { + struct tree_entry_list *next; + unsigned directory : 1; + unsigned executable : 1; + unsigned symlink : 1; + unsigned int mode; + const char *name; + const unsigned char *sha1; }; static struct tree_entry_list df_conflict_list = { @@ -40,6 +50,39 @@ static struct tree_entry_list df_conflict_list = { typedef int (*merge_fn_t)(struct cache_entry **src); +static 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; + + while (desc.size) { + unsigned mode; + const char *path; + const unsigned char *sha1; + struct tree_entry_list *entry; + + sha1 = tree_entry_extract(&desc, &path, &mode); + update_tree_entry(&desc); + + entry = xmalloc(sizeof(struct tree_entry_list)); + entry->name = path; + entry->sha1 = sha1; + entry->mode = mode; + entry->directory = S_ISDIR(mode) != 0; + entry->executable = (mode & S_IXUSR) != 0; + entry->symlink = S_ISLNK(mode) != 0; + entry->next = NULL; + + *list_p = entry; + list_p = &entry->next; + } + return ret; +} + static int entcmp(const char *name1, int dir1, const char *name2, int dir2) { int len1 = strlen(name1); diff --git a/tree.c b/tree.c index 47318ef89..fb1872425 100644 --- a/tree.c +++ b/tree.c @@ -201,48 +201,6 @@ int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size) 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; - - while (desc.size) { - unsigned mode; - const char *path; - const unsigned char *sha1; - struct tree_entry_list *entry; - - sha1 = tree_entry_extract(&desc, &path, &mode); - update_tree_entry(&desc); - - entry = xmalloc(sizeof(struct tree_entry_list)); - entry->name = path; - entry->sha1 = sha1; - entry->mode = mode; - entry->directory = S_ISDIR(mode) != 0; - entry->executable = (mode & S_IXUSR) != 0; - entry->symlink = S_ISLNK(mode) != 0; - entry->next = NULL; - - *list_p = entry; - list_p = &entry->next; - } - return ret; -} - -void free_tree_entry_list(struct tree_entry_list *list) -{ - while (list) { - struct tree_entry_list *next = list->next; - free(list); - list = next; - } -} - int parse_tree(struct tree *item) { char type[20]; diff --git a/tree.h b/tree.h index 6a875464b..dd25c539e 100644 --- a/tree.h +++ b/tree.h @@ -5,25 +5,12 @@ extern const char *tree_type; -struct tree_entry_list { - struct tree_entry_list *next; - unsigned directory : 1; - unsigned executable : 1; - unsigned symlink : 1; - unsigned int mode; - const char *name; - const unsigned char *sha1; -}; - struct tree { struct object object; void *buffer; unsigned long size; }; -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); -- cgit v1.2.1 From e76abd701419b50937708cfec2f772d33057505e Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 29 May 2006 22:00:21 -0700 Subject: adjust to the rebased series by Linus. Signed-off-by: Junio C Hamano --- builtin-read-tree.c | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) diff --git a/builtin-read-tree.c b/builtin-read-tree.c index b93178a4b..480e6ed37 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -9,8 +9,8 @@ #include "object.h" #include "tree.h" -#include "cache-tree.h" #include "tree-walk.h" +#include "cache-tree.h" #include #include #include "builtin.h" @@ -777,12 +777,12 @@ static int read_cache_unmerged(void) static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree) { struct tree_desc desc; - int cnt = 0; + int cnt; memcpy(it->sha1, tree->object.sha1, 20); desc.buf = tree->buffer; desc.size = tree->size; - + cnt = 0; while (desc.size) { unsigned mode; const char *name; @@ -790,14 +790,11 @@ static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree) sha1 = tree_entry_extract(&desc, &name, &mode); update_tree_entry(&desc); - if (!S_ISDIR(mode)) cnt++; else { struct cache_tree_sub *sub; - struct tree *subtree; - - subtree = lookup_tree(sha1); + struct tree *subtree = lookup_tree(sha1); if (!subtree->object.parsed) parse_tree(subtree); sub = cache_tree_sub(it, name); -- cgit v1.2.1 From 4c068a983150b740c3fcf6a33f342ac923abd3f4 Mon Sep 17 00:00:00 2001 From: Linus Torvalds Date: Tue, 30 May 2006 09:45:45 -0700 Subject: tree_entry(): new tree-walking helper function This adds a "tree_entry()" function that combines the common operation of doing a "tree_entry_extract()" + "update_tree_entry()". It also has a simplified calling convention, designed for simple loops that traverse over a whole tree: the arguments are pointers to the tree descriptor and a name_entry structure to fill in, and it returns a boolean "true" if there was an entry left to be gotten in the tree. This allows tree traversal with struct tree_desc desc; struct name_entry entry; desc.buf = tree->buffer; desc.size = tree->size; while (tree_entry(&desc, &entry) { ... use "entry.{path, sha1, mode, pathlen}" ... } which is not only shorter than writing it out in full, it's hopefully less error prone too. [ It's actually a tad faster too - we don't need to recalculate the entry pathlength in both extract and update, but need to do it only once. Also, some callers can avoid doing a "strlen()" on the result, since it's returned as part of the name_entry structure. However, by now we're talking just 1% speedup on "git-rev-list --objects --all", and we're definitely at the point where tree walking is no longer the issue any more. ] NOTE! Not everybody wants to use this new helper function, since some of the tree walkers very much on purpose do the descriptor update separately from the entry extraction. So the "extract + update" sequence still remains as the core sequence, this is just a simplified interface. We should probably add a silly two-line inline helper function for initializing the descriptor from the "struct tree" too, just to cut down on the noise from that common "desc" initializer. Signed-off-by: Linus Torvalds Signed-off-by: Junio C Hamano --- builtin-grep.c | 26 ++++++++++---------------- builtin-read-tree.c | 36 +++++++++++++----------------------- builtin-rev-list.c | 16 +++++----------- builtin-tar-tree.c | 21 ++++++++------------- fetch.c | 16 +++++----------- http-push.c | 16 +++++----------- pack-objects.c | 27 +++++++++++---------------- revision.c | 16 +++++----------- tree-walk.c | 33 +++++++++++++++++++++++++++++++-- tree-walk.h | 5 ++++- tree.c | 41 +++++++++++++++-------------------------- 11 files changed, 112 insertions(+), 141 deletions(-) diff --git a/builtin-grep.c b/builtin-grep.c index 53de8a883..acc4eea36 100644 --- a/builtin-grep.c +++ b/builtin-grep.c @@ -578,11 +578,9 @@ static int grep_tree(struct grep_opt *opt, const char **paths, struct tree_desc *tree, const char *tree_name, const char *base) { - unsigned mode; int len; int hit = 0; - const char *path; - const unsigned char *sha1; + struct name_entry entry; char *down; char *path_buf = xmalloc(PATH_MAX + strlen(tree_name) + 100); @@ -597,36 +595,32 @@ static int grep_tree(struct grep_opt *opt, const char **paths, } len = strlen(path_buf); - while (tree->size) { - int pathlen; - sha1 = tree_entry_extract(tree, &path, &mode); - pathlen = strlen(path); - strcpy(path_buf + len, path); + while (tree_entry(tree, &entry)) { + strcpy(path_buf + len, entry.path); - if (S_ISDIR(mode)) + if (S_ISDIR(entry.mode)) /* Match "abc/" against pathspec to * decide if we want to descend into "abc" * directory. */ - strcpy(path_buf + len + pathlen, "/"); + strcpy(path_buf + len + entry.pathlen, "/"); if (!pathspec_matches(paths, down)) ; - else if (S_ISREG(mode)) - hit |= grep_sha1(opt, sha1, path_buf); - else if (S_ISDIR(mode)) { + else if (S_ISREG(entry.mode)) + hit |= grep_sha1(opt, entry.sha1, path_buf); + else if (S_ISDIR(entry.mode)) { char type[20]; struct tree_desc sub; void *data; - data = read_sha1_file(sha1, type, &sub.size); + data = read_sha1_file(entry.sha1, type, &sub.size); if (!data) die("unable to read tree (%s)", - sha1_to_hex(sha1)); + sha1_to_hex(entry.sha1)); sub.buf = data; hit |= grep_tree(opt, paths, &sub, tree_name, down); free(data); } - update_tree_entry(tree); } return hit; } diff --git a/builtin-read-tree.c b/builtin-read-tree.c index 00cdb5a6d..10afd4696 100644 --- a/builtin-read-tree.c +++ b/builtin-read-tree.c @@ -53,28 +53,23 @@ typedef int (*merge_fn_t)(struct cache_entry **src); static struct tree_entry_list *create_tree_entry_list(struct tree *tree) { struct tree_desc desc; + struct name_entry one; struct tree_entry_list *ret = NULL; struct tree_entry_list **list_p = &ret; desc.buf = tree->buffer; desc.size = tree->size; - while (desc.size) { - unsigned mode; - const char *path; - const unsigned char *sha1; + while (tree_entry(&desc, &one)) { struct tree_entry_list *entry; - sha1 = tree_entry_extract(&desc, &path, &mode); - update_tree_entry(&desc); - entry = xmalloc(sizeof(struct tree_entry_list)); - entry->name = path; - entry->sha1 = sha1; - entry->mode = mode; - entry->directory = S_ISDIR(mode) != 0; - entry->executable = (mode & S_IXUSR) != 0; - entry->symlink = S_ISLNK(mode) != 0; + entry->name = one.path; + entry->sha1 = one.sha1; + entry->mode = one.mode; + entry->directory = S_ISDIR(one.mode) != 0; + entry->executable = (one.mode & S_IXUSR) != 0; + entry->symlink = S_ISLNK(one.mode) != 0; entry->next = NULL; *list_p = entry; @@ -820,27 +815,22 @@ static int read_cache_unmerged(void) static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree) { struct tree_desc desc; + struct name_entry entry; int cnt; memcpy(it->sha1, tree->object.sha1, 20); desc.buf = tree->buffer; desc.size = tree->size; cnt = 0; - 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)) + while (tree_entry(&desc, &entry)) { + if (!S_ISDIR(entry.mode)) cnt++; else { struct cache_tree_sub *sub; - struct tree *subtree = lookup_tree(sha1); + struct tree *subtree = lookup_tree(entry.sha1); if (!subtree->object.parsed) parse_tree(subtree); - sub = cache_tree_sub(it, name); + sub = cache_tree_sub(it, entry.path); sub->cache_tree = cache_tree(); prime_cache_tree_rec(sub->cache_tree, subtree); cnt += sub->cache_tree->entry_count; diff --git a/builtin-rev-list.c b/builtin-rev-list.c index 6e2b898cc..17c04b962 100644 --- a/builtin-rev-list.c +++ b/builtin-rev-list.c @@ -114,6 +114,7 @@ static struct object_list **process_tree(struct tree *tree, { struct object *obj = &tree->object; struct tree_desc desc; + struct name_entry entry; struct name_path me; if (!revs.tree_objects) @@ -132,18 +133,11 @@ static struct object_list **process_tree(struct tree *tree, 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); + while (tree_entry(&desc, &entry)) { + if (S_ISDIR(entry.mode)) + p = process_tree(lookup_tree(entry.sha1), p, &me, name); else - p = process_blob(lookup_blob(sha1), p, &me, name); + p = process_blob(lookup_blob(entry.sha1), p, &me, name); } free(tree->buffer); tree->buffer = NULL; diff --git a/builtin-tar-tree.c b/builtin-tar-tree.c index 2d5e06fb6..5f740cf70 100644 --- a/builtin-tar-tree.c +++ b/builtin-tar-tree.c @@ -271,30 +271,25 @@ static void write_global_extended_header(const unsigned char *sha1) static void traverse_tree(struct tree_desc *tree, struct strbuf *path) { int pathlen = path->len; + struct name_entry entry; - while (tree->size) { - const char *name; - const unsigned char *sha1; - unsigned mode; + while (tree_entry(tree, &entry)) { void *eltbuf; char elttype[20]; unsigned long eltsize; - sha1 = tree_entry_extract(tree, &name, &mode); - update_tree_entry(tree); - - eltbuf = read_sha1_file(sha1, elttype, &eltsize); + eltbuf = read_sha1_file(entry.sha1, elttype, &eltsize); if (!eltbuf) - die("cannot read %s", sha1_to_hex(sha1)); + die("cannot read %s", sha1_to_hex(entry.sha1)); path->len = pathlen; - strbuf_append_string(path, name); - if (S_ISDIR(mode)) + strbuf_append_string(path, entry.path); + if (S_ISDIR(entry.mode)) strbuf_append_string(path, "/"); - write_entry(sha1, path, mode, eltbuf, eltsize); + write_entry(entry.sha1, path, entry.mode, eltbuf, eltsize); - if (S_ISDIR(mode)) { + if (S_ISDIR(entry.mode)) { struct tree_desc subtree; subtree.buf = eltbuf; subtree.size = eltsize; diff --git a/fetch.c b/fetch.c index 976a5a459..ec2d8c3d9 100644 --- a/fetch.c +++ b/fetch.c @@ -38,25 +38,19 @@ static int process(struct object *obj); static int process_tree(struct tree *tree) { struct tree_desc desc; + struct name_entry entry; if (parse_tree(tree)) return -1; 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)) { - struct tree *tree = lookup_tree(sha1); + while (tree_entry(&desc, &entry)) { + if (S_ISDIR(entry.mode)) { + struct tree *tree = lookup_tree(entry.sha1); process_tree(tree); } else { - struct blob *blob = lookup_blob(sha1); + struct blob *blob = lookup_blob(entry.sha1); process(&blob->object); } } diff --git a/http-push.c b/http-push.c index 72ad89ce1..b1c018a08 100644 --- a/http-push.c +++ b/http-push.c @@ -1715,6 +1715,7 @@ static struct object_list **process_tree(struct tree *tree, { struct object *obj = &tree->object; struct tree_desc desc; + struct name_entry entry; struct name_path me; obj->flags |= LOCAL; @@ -1734,18 +1735,11 @@ static struct object_list **process_tree(struct tree *tree, 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); + while (tree_entry(&desc, &entry)) { + if (S_ISDIR(entry.mode)) + p = process_tree(lookup_tree(entry.sha1), p, &me, name); else - p = process_blob(lookup_blob(sha1), p, &me, name); + p = process_blob(lookup_blob(entry.sha1), p, &me, name); } free(tree->buffer); tree->buffer = NULL; diff --git a/pack-objects.c b/pack-objects.c index 77284cfdb..3590cd5e5 100644 --- a/pack-objects.c +++ b/pack-objects.c @@ -690,25 +690,20 @@ static void add_pbase_object(struct tree_desc *tree, const char *name, int cmplen) { - while (tree->size) { - const unsigned char *sha1; - const char *entry_name; - int entry_len; - unsigned mode; + struct name_entry entry; + + while (tree_entry(tree,&entry)) { unsigned long size; char type[20]; - sha1 = tree_entry_extract(tree, &entry_name, &mode); - update_tree_entry(tree); - entry_len = strlen(entry_name); - if (entry_len != cmplen || - memcmp(entry_name, name, cmplen) || - !has_sha1_file(sha1) || - sha1_object_info(sha1, type, &size)) + if (entry.pathlen != cmplen || + memcmp(entry.path, name, cmplen) || + !has_sha1_file(entry.sha1) || + sha1_object_info(entry.sha1, type, &size)) continue; if (name[cmplen] != '/') { unsigned hash = name_hash(up, name); - add_object_entry(sha1, hash, 1); + add_object_entry(entry.sha1, hash, 1); return; } if (!strcmp(type, tree_type)) { @@ -718,15 +713,15 @@ static void add_pbase_object(struct tree_desc *tree, const char *down = name+cmplen+1; int downlen = name_cmp_len(down); - tree = pbase_tree_get(sha1); + tree = pbase_tree_get(entry.sha1); if (!tree) return; sub.buf = tree->tree_data; sub.size = tree->tree_size; me.up = up; - me.elem = entry_name; - me.len = entry_len; + me.elem = entry.path; + me.len = entry.pathlen; add_pbase_object(&sub, &me, down, downlen); pbase_tree_put(tree); } diff --git a/revision.c b/revision.c index 8e93e40bb..6a6952cd5 100644 --- a/revision.c +++ b/revision.c @@ -54,6 +54,7 @@ static void mark_blob_uninteresting(struct blob *blob) void mark_tree_uninteresting(struct tree *tree) { struct tree_desc desc; + struct name_entry entry; struct object *obj = &tree->object; if (obj->flags & UNINTERESTING) @@ -66,18 +67,11 @@ void mark_tree_uninteresting(struct tree *tree) 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)) - mark_tree_uninteresting(lookup_tree(sha1)); + while (tree_entry(&desc, &entry)) { + if (S_ISDIR(entry.mode)) + mark_tree_uninteresting(lookup_tree(entry.sha1)); else - mark_blob_uninteresting(lookup_blob(sha1)); + mark_blob_uninteresting(lookup_blob(entry.sha1)); } /* diff --git a/tree-walk.c b/tree-walk.c index 392205827..297c6972b 100644 --- a/tree-walk.c +++ b/tree-walk.c @@ -37,7 +37,7 @@ static void entry_extract(struct tree_desc *t, struct name_entry *a) void update_tree_entry(struct tree_desc *desc) { - void *buf = desc->buf; + const void *buf = desc->buf; unsigned long size = desc->size; int len = strlen(buf) + 1 + 20; @@ -63,7 +63,7 @@ static const char *get_mode(const char *str, unsigned int *modep) const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep) { - void *tree = desc->buf; + const void *tree = desc->buf; unsigned long size = desc->size; int len = strlen(tree)+1; const unsigned char *sha1 = tree + len; @@ -78,6 +78,35 @@ const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pat return sha1; } +int tree_entry(struct tree_desc *desc, struct name_entry *entry) +{ + const void *tree = desc->buf, *path; + unsigned long len, size = desc->size; + + if (!size) + return 0; + + path = get_mode(tree, &entry->mode); + if (!path) + die("corrupt tree file"); + + entry->path = path; + len = strlen(path); + entry->pathlen = len; + + path += len + 1; + entry->sha1 = path; + + path += 20; + len = path - tree; + if (len > size) + die("corrupt tree file"); + + desc->buf = path; + desc->size = size - len; + return 1; +} + void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback) { struct name_entry *entry = xmalloc(n*sizeof(*entry)); diff --git a/tree-walk.h b/tree-walk.h index 47438fe1c..e57befa4d 100644 --- a/tree-walk.h +++ b/tree-walk.h @@ -2,7 +2,7 @@ #define TREE_WALK_H struct tree_desc { - void *buf; + const void *buf; unsigned long size; }; @@ -16,6 +16,9 @@ struct name_entry { void update_tree_entry(struct tree_desc *); const unsigned char *tree_entry_extract(struct tree_desc *, const char **, unsigned int *); +/* Helper function that does both of the above and returns true for success */ +int tree_entry(struct tree_desc *, struct name_entry *); + void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1); typedef void (*traverse_callback_t)(int n, unsigned long mask, struct name_entry *entry, const char *base); diff --git a/tree.c b/tree.c index fb1872425..9bbe2da37 100644 --- a/tree.c +++ b/tree.c @@ -79,6 +79,7 @@ int read_tree_recursive(struct tree *tree, read_tree_fn_t fn) { struct tree_desc desc; + struct name_entry entry; if (parse_tree(tree)) return -1; @@ -86,18 +87,11 @@ int read_tree_recursive(struct tree *tree, 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 (!match_tree_entry(base, baselen, name, mode, match)) + while (tree_entry(&desc, &entry)) { + if (!match_tree_entry(base, baselen, entry.path, entry.mode, match)) continue; - switch (fn(sha1, base, baselen, name, mode, stage)) { + switch (fn(entry.sha1, base, baselen, entry.path, entry.mode, stage)) { case 0: continue; case READ_TREE_RECURSIVE: @@ -105,18 +99,17 @@ int read_tree_recursive(struct tree *tree, default: return -1; } - if (S_ISDIR(mode)) { + if (S_ISDIR(entry.mode)) { int retval; - int pathlen = strlen(name); char *newbase; - newbase = xmalloc(baselen + 1 + pathlen); + newbase = xmalloc(baselen + 1 + entry.pathlen); memcpy(newbase, base, baselen); - memcpy(newbase + baselen, name, pathlen); - newbase[baselen + pathlen] = '/'; - retval = read_tree_recursive(lookup_tree(sha1), + memcpy(newbase + baselen, entry.path, entry.pathlen); + newbase[baselen + entry.pathlen] = '/'; + retval = read_tree_recursive(lookup_tree(entry.sha1), newbase, - baselen + pathlen + 1, + baselen + entry.pathlen + 1, stage, match, fn); free(newbase); if (retval) @@ -156,6 +149,7 @@ static int track_tree_refs(struct tree *item) int n_refs = 0, i; struct object_refs *refs; struct tree_desc desc; + struct name_entry entry; /* Count how many entries there are.. */ desc.buf = item->buffer; @@ -170,18 +164,13 @@ static int track_tree_refs(struct tree *item) 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; + while (tree_entry(&desc, &entry)) { struct object *obj; - sha1 = tree_entry_extract(&desc, &name, &mode); - update_tree_entry(&desc); - if (S_ISDIR(mode)) - obj = &lookup_tree(sha1)->object; + if (S_ISDIR(entry.mode)) + obj = &lookup_tree(entry.sha1)->object; else - obj = &lookup_blob(sha1)->object; + obj = &lookup_blob(entry.sha1)->object; refs->ref[i++] = obj; } set_object_refs(&item->object, refs); -- cgit v1.2.1 From 6f9012b62517ca490e4131f24e03ff842527f1b9 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 2 Jun 2006 15:23:47 -0700 Subject: fetch.c: do not call process_tree() from process_tree(). This function reads a freshly fetched tree object, and schedules the objects pointed by it for further fetching, so doing lookup_tree() and process_tree() recursively from there does not make much sense. We need to use process() on it to make sure we fetch it first, and leave the recursive processing to later stages. Signed-off-by: Junio C Hamano --- fetch.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/fetch.c b/fetch.c index ec2d8c3d9..107504b72 100644 --- a/fetch.c +++ b/fetch.c @@ -46,13 +46,20 @@ static int process_tree(struct tree *tree) desc.buf = tree->buffer; desc.size = tree->size; while (tree_entry(&desc, &entry)) { + struct object *obj = NULL; + if (S_ISDIR(entry.mode)) { struct tree *tree = lookup_tree(entry.sha1); - process_tree(tree); - } else { + if (tree) + obj = &tree->object; + } + else { struct blob *blob = lookup_blob(entry.sha1); - process(&blob->object); + if (blob) + obj = &blob->object; } + if (!obj || process(obj)) + return -1; } free(tree->buffer); tree->buffer = NULL; -- cgit v1.2.1