{"thread":{"id":"4323","subject":"[PATCH 0/4] Start migrating away from the \"struct tree_entry\" list","startedAt":"2006-05-28T22:03:49Z","lastAt":"2006-05-28T22:13:53Z","messageCount":5,"participants":["Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"20842","messageId":"Pine.LNX.4.64.0605281453460.5623@g5.osdl.org","threadId":"4323","inReplyTo":null,"subject":"[PATCH 0/4] Start migrating away from the \"struct tree_entry\" list","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-28T22:03:49Z","receivedAt":"2006-05-28T22:03:49Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThe old \"tree.h\" parsing logic (before I did the \"tree-walk\" tree buffer \nparser) would generate a list of \"struct tree_entry\" objects, which was \nbasically a simpler-to-walk version of the raw tree buffer.\n\nNow, the problem with that simpler-to-walk version is that it's a lot less \nefficient than just walking the raw tree buffer in-place, and a lot of the \ncore git tree walkers already use the much more efficient in-place \ntree-walker interfaces. Which means that we have _two_ independent ways of \nwalking the tree. Very annoying.\n\nThis series of four patches (on top of my trivial memory leak fix for git \nrev-list) gets rid of the tree-entry list from tree parsing, and converts \nmost users over to use the tree-walker, and has a small compatibility \nhelper function to keep some users that are hard to convert using what is \nnow obviously just a temporary list.\n\nApart from being one more step in the direction of cleaning up tree \nwalking, it also makes things more efficient, by not needlessly creating \nthat silly list that most users don't actually want. I used the same test \nvector as I did for the git rev-list leaker: doing a\n\n\tgit-rev-list --all --objects\n\non the historical kernel archive (that one has 566k objects and is more \nthan twice the size of the current kernel git tree). The series brings \nthat down from\n\n\t74.67user 0.45system 1:15.43elapsed\n\nto\n\n\t62.50user 0.41system 1:02.93elapsed\n\nfor me.\n\nNOTE! I think the git-rev-list leak fix can go into the main tree \nimmediately, but this series should probably be kept in \"next\" for a \nwhile, just to verify that it all is good..\n\n\t\tLinus\n"},{"id":"20844","messageId":"Pine.LNX.4.64.0605281504400.5623@g5.osdl.org","threadId":"4323","inReplyTo":"Pine.LNX.4.64.0605281453460.5623@g5.osdl.org","subject":"[PATCH 1/4] Add raw tree buffer info to \"struct tree\"","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-28T22:07:07Z","receivedAt":"2006-05-28T22:07:07Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis allows us to avoid allocating information for names etc, because\nwe can just use the information from the tree buffer directly.\n\nWe still keep the old \"tree_entry_list\" in struct tree as well, so old \nusers aren't affected, apart from the fact that the allocations are \ndifferent (if you free a tree entry, you should no longer free the name \nallocation for it, since it's allocated as part of \"tree->buffer\")\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex ec40d01..740a8c7 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -38,7 +38,7 @@ static struct tree_entry_list df_conflic\n \n typedef int (*merge_fn_t)(struct cache_entry **src);\n \n-static int entcmp(char *name1, int dir1, char *name2, int dir2)\n+static int entcmp(const char *name1, int dir1, const char *name2, int dir2)\n {\n \tint len1 = strlen(name1);\n \tint len2 = strlen(name2);\n@@ -66,7 +66,7 @@ static int unpack_trees_rec(struct tree_\n \tint src_size = len + 1;\n \tdo {\n \t\tint i;\n-\t\tchar *first;\n+\t\tconst char *first;\n \t\tint firstdir = 0;\n \t\tint pathlen;\n \t\tunsigned ce_size;\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 5277d3c..72c1549 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -136,10 +136,11 @@ static struct object_list **process_tree\n \t\t\tp = process_tree(entry->item.tree, p, &me, entry->name);\n \t\telse\n \t\t\tp = process_blob(entry->item.blob, p, &me, entry->name);\n-\t\tfree(entry->name);\n \t\tfree(entry);\n \t\tentry = next;\n \t}\n+\tfree(tree->buffer);\n+\ttree->buffer = NULL;\n \treturn p;\n }\n \ndiff --git a/fsck-objects.c b/fsck-objects.c\nindex 59b2590..a0290b0 100644\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -197,17 +197,16 @@ static int fsck_tree(struct tree *item)\n \t\t\tdefault:\n \t\t\t\tbreak;\n \t\t\t}\n-\t\t\tfree(last->name);\n \t\t\tfree(last);\n \t\t}\n \n \t\tlast = entry;\n \t}\n-\tif (last) {\n-\t\tfree(last->name);\n+\tif (last)\n \t\tfree(last);\n-\t}\n \titem->entries = NULL;\n+\tfree(item->buffer);\n+\titem->buffer = NULL;\n \n \tretval = 0;\n \tif (has_full_path) {\ndiff --git a/object.c b/object.c\nindex 4d46e0d..1a7823c 100644\n--- a/object.c\n+++ b/object.c\n@@ -200,8 +200,11 @@ struct object *parse_object(const unsign\n \t\t\tobj = &blob->object;\n \t\t} else if (!strcmp(type, tree_type)) {\n \t\t\tstruct tree *tree = lookup_tree(sha1);\n-\t\t\tparse_tree_buffer(tree, buffer, size);\n \t\t\tobj = &tree->object;\n+\t\t\tif (!tree->object.parsed) {\n+\t\t\t\tparse_tree_buffer(tree, buffer, size);\n+\t\t\t\tbuffer = NULL;\n+\t\t\t}\n \t\t} else if (!strcmp(type, commit_type)) {\n \t\t\tstruct commit *commit = lookup_commit(sha1);\n \t\t\tparse_commit_buffer(commit, buffer, size);\ndiff --git a/tree.c b/tree.c\nindex d599fb5..1e76d9c 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -3,6 +3,7 @@ #include \"tree.h\"\n #include \"blob.h\"\n #include \"commit.h\"\n #include \"tag.h\"\n+#include \"tree-walk.h\"\n #include <stdlib.h>\n \n const char *tree_type = \"tree\";\n@@ -145,46 +146,45 @@ struct tree *lookup_tree(const unsigned \n \n int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size)\n {\n-\tvoid *bufptr = buffer;\n+\tstruct tree_desc desc;\n \tstruct tree_entry_list **list_p;\n \tint n_refs = 0;\n \n \tif (item->object.parsed)\n \t\treturn 0;\n \titem->object.parsed = 1;\n+\titem->buffer = buffer;\n+\titem->size = size;\n+\n+\tdesc.buf = buffer;\n+\tdesc.size = size;\n+\n \tlist_p = &item->entries;\n-\twhile (size) {\n-\t\tstruct object *obj;\n+\twhile (desc.size) {\n+\t\tunsigned mode;\n+\t\tconst char *path;\n+\t\tconst unsigned char *sha1;\n \t\tstruct tree_entry_list *entry;\n-\t\tint len = 1+strlen(bufptr);\n-\t\tunsigned char *file_sha1 = bufptr + len;\n-\t\tchar *path = strchr(bufptr, ' ');\n-\t\tunsigned int mode;\n-\t\tif (size < len + 20 || !path || \n-\t\t    sscanf(bufptr, \"%o\", &mode) != 1)\n-\t\t\treturn -1;\n+\n+\t\tsha1 = tree_entry_extract(&desc, &path, &mode);\n \n \t\tentry = xmalloc(sizeof(struct tree_entry_list));\n-\t\tentry->name = strdup(path + 1);\n+\t\tentry->name = path;\n+\t\tentry->mode = mode;\n \t\tentry->directory = S_ISDIR(mode) != 0;\n \t\tentry->executable = (mode & S_IXUSR) != 0;\n \t\tentry->symlink = S_ISLNK(mode) != 0;\n-\t\tentry->zeropad = *(char *)bufptr == '0';\n-\t\tentry->mode = mode;\n+\t\tentry->zeropad = *(const char *)(desc.buf) == '0';\n \t\tentry->next = NULL;\n \n-\t\tbufptr += len + 20;\n-\t\tsize -= len + 20;\n+\t\tupdate_tree_entry(&desc);\n \n \t\tif (entry->directory) {\n-\t\t\tentry->item.tree = lookup_tree(file_sha1);\n-\t\t\tobj = &entry->item.tree->object;\n+\t\t\tentry->item.tree = lookup_tree(sha1);\n \t\t} else {\n-\t\t\tentry->item.blob = lookup_blob(file_sha1);\n-\t\t\tobj = &entry->item.blob->object;\n+\t\t\tentry->item.blob = lookup_blob(sha1);\n \t\t}\n-\t\tif (obj)\n-\t\t\tn_refs++;\n+\t\tn_refs++;\n \t\t*list_p = entry;\n \t\tlist_p = &entry->next;\n \t}\n@@ -206,7 +206,6 @@ int parse_tree(struct tree *item)\n \t char type[20];\n \t void *buffer;\n \t unsigned long size;\n-\t int ret;\n \n \tif (item->object.parsed)\n \t\treturn 0;\n@@ -219,9 +218,7 @@ int parse_tree(struct tree *item)\n \t\treturn error(\"Object %s not a tree\",\n \t\t\t     sha1_to_hex(item->object.sha1));\n \t}\n-\tret = parse_tree_buffer(item, buffer, size);\n-\tfree(buffer);\n-\treturn ret;\n+\treturn parse_tree_buffer(item, buffer, size);\n }\n \n struct tree *parse_tree_indirect(const unsigned char *sha1)\ndiff --git a/tree.h b/tree.h\nindex 330ab64..066ac5d 100644\n--- a/tree.h\n+++ b/tree.h\n@@ -12,7 +12,7 @@ struct tree_entry_list {\n \tunsigned symlink : 1;\n \tunsigned zeropad : 1;\n \tunsigned int mode;\n-\tchar *name;\n+\tconst char *name;\n \tunion {\n \t\tstruct object *any;\n \t\tstruct tree *tree;\n@@ -22,6 +22,8 @@ struct tree_entry_list {\n \n struct tree {\n \tstruct object object;\n+\tvoid *buffer;\n+\tunsigned long size;\n \tstruct tree_entry_list *entries;\n };\n \n"},{"id":"20845","messageId":"Pine.LNX.4.64.0605281507110.5623@g5.osdl.org","threadId":"4323","inReplyTo":"Pine.LNX.4.64.0605281453460.5623@g5.osdl.org","subject":"[PATCH 2/4] Make \"tree_entry\" have a SHA1 instead of a union of object pointers","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-28T22:10:04Z","receivedAt":"2006-05-28T22:10:04Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis is preparatory work for further cleanups, where we try to make\ntree_entry look more like the more efficient tree-walk descriptor.\n\nInstead of having a union of pointers to blob/tree/objects, this just \nmakes \"struct tree_entry\" have the raw SHA1, and makes all the users use \nthat instead (often that implies adding a \"lookup_tree(..)\" on the sha1, \nbut sometimes the user just wanted the SHA1 in the first place, and it \njust avoids an unnecessary indirection).\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n\n---\n blame.c             |    4 ++--\n builtin-read-tree.c |    7 ++++---\n builtin-rev-list.c  |    4 ++--\n fsck-objects.c      |    1 +\n http-push.c         |    4 ++--\n object.c            |    2 +-\n revision.c          |    4 ++--\n tree.c              |   25 ++++++++++++++-----------\n tree.h              |    8 ++------\n 9 files changed, 30 insertions(+), 29 deletions(-)\n\ndiff --git a/blame.c b/blame.c\nindex 99ceea8..88bfec2 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -149,7 +149,7 @@ static void free_patch(struct patch *p)\n \tfree(p);\n }\n \n-static int get_blob_sha1_internal(unsigned char *sha1, const char *base,\n+static int get_blob_sha1_internal(const unsigned char *sha1, const char *base,\n \t\t\t\t  int baselen, const char *pathname,\n \t\t\t\t  unsigned mode, int stage);\n \n@@ -178,7 +178,7 @@ static int get_blob_sha1(struct tree *t,\n \treturn 0;\n }\n \n-static int get_blob_sha1_internal(unsigned char *sha1, const char *base,\n+static int get_blob_sha1_internal(const unsigned char *sha1, const char *base,\n \t\t\t\t  int baselen, const char *pathname,\n \t\t\t\t  unsigned mode, int stage)\n {\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex 740a8c7..f0b8dad 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -160,9 +160,10 @@ #endif\n \t\t\t}\n \n \t\t\tif (posns[i]->directory) {\n+\t\t\t\tstruct tree *tree = lookup_tree(posns[i]->sha1);\n \t\t\t\tany_dirs = 1;\n-\t\t\t\tparse_tree(posns[i]->item.tree);\n-\t\t\t\tsubposns[i] = posns[i]->item.tree->entries;\n+\t\t\t\tparse_tree(tree);\n+\t\t\t\tsubposns[i] = tree->entries;\n \t\t\t\tposns[i] = posns[i]->next;\n \t\t\t\tsrc[i + merge] = &df_conflict_entry;\n \t\t\t\tcontinue;\n@@ -186,7 +187,7 @@ #endif\n \n \t\t\tany_files = 1;\n \n-\t\t\tmemcpy(ce->sha1, posns[i]->item.any->sha1, 20);\n+\t\t\tmemcpy(ce->sha1, posns[i]->sha1, 20);\n \t\t\tsrc[i + merge] = ce;\n \t\t\tsubposns[i] = &df_conflict_list;\n \t\t\tposns[i] = posns[i]->next;\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 72c1549..94f520b 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -133,9 +133,9 @@ static struct object_list **process_tree\n \twhile (entry) {\n \t\tstruct tree_entry_list *next = entry->next;\n \t\tif (entry->directory)\n-\t\t\tp = process_tree(entry->item.tree, p, &me, entry->name);\n+\t\t\tp = process_tree(lookup_tree(entry->sha1), p, &me, entry->name);\n \t\telse\n-\t\t\tp = process_blob(entry->item.blob, p, &me, entry->name);\n+\t\t\tp = process_blob(lookup_blob(entry->sha1), p, &me, entry->name);\n \t\tfree(entry);\n \t\tentry = next;\n \t}\ndiff --git a/fsck-objects.c b/fsck-objects.c\nindex a0290b0..44b6465 100644\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -441,6 +441,7 @@ int main(int argc, char **argv)\n {\n \tint i, heads;\n \n+\ttrack_object_refs = 1;\n \tsetup_git_directory();\n \n \tfor (i = 1; i < argc; i++) {\ndiff --git a/http-push.c b/http-push.c\nindex b4327d9..f492a5d 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1733,9 +1733,9 @@ static struct object_list **process_tree\n \twhile (entry) {\n \t\tstruct tree_entry_list *next = entry->next;\n \t\tif (entry->directory)\n-\t\t\tp = process_tree(entry->item.tree, p, &me, entry->name);\n+\t\t\tp = process_tree(lookup_tree(entry->sha1), p, &me, entry->name);\n \t\telse\n-\t\t\tp = process_blob(entry->item.blob, p, &me, entry->name);\n+\t\t\tp = process_blob(lookup_blob(entry->sha1), p, &me, entry->name);\n \t\tfree(entry);\n \t\tentry = next;\n \t}\ndiff --git a/object.c b/object.c\nindex 1a7823c..9adc874 100644\n--- a/object.c\n+++ b/object.c\n@@ -9,7 +9,7 @@ struct object **objs;\n static int nr_objs;\n int obj_allocs;\n \n-int track_object_refs = 1;\n+int track_object_refs = 0;\n \n static int hashtable_index(const unsigned char *sha1)\n {\ndiff --git a/revision.c b/revision.c\nindex 2294b16..35f8e3b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -68,9 +68,9 @@ void mark_tree_uninteresting(struct tree\n \twhile (entry) {\n \t\tstruct tree_entry_list *next = entry->next;\n \t\tif (entry->directory)\n-\t\t\tmark_tree_uninteresting(entry->item.tree);\n+\t\t\tmark_tree_uninteresting(lookup_tree(entry->sha1));\n \t\telse\n-\t\t\tmark_blob_uninteresting(entry->item.blob);\n+\t\t\tmark_blob_uninteresting(lookup_blob(entry->sha1));\n \t\tfree(entry);\n \t\tentry = next;\n \t}\ndiff --git a/tree.c b/tree.c\nindex 1e76d9c..ba8742c 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -8,7 +8,7 @@ #include <stdlib.h>\n \n const char *tree_type = \"tree\";\n \n-static int read_one_entry(unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage)\n+static int read_one_entry(const unsigned char *sha1, const char *base, int baselen, const char *pathname, unsigned mode, int stage)\n {\n \tint len;\n \tunsigned int size;\n@@ -89,7 +89,7 @@ int read_tree_recursive(struct tree *tre\n \t\t\t\t      current->mode, match))\n \t\t\tcontinue;\n \n-\t\tswitch (fn(current->item.any->sha1, base, baselen,\n+\t\tswitch (fn(current->sha1, base, baselen,\n \t\t\t   current->name, current->mode, stage)) {\n \t\tcase 0:\n \t\t\tcontinue;\n@@ -107,7 +107,7 @@ int read_tree_recursive(struct tree *tre\n \t\t\tmemcpy(newbase, base, baselen);\n \t\t\tmemcpy(newbase + baselen, current->name, pathlen);\n \t\t\tnewbase[baselen + pathlen] = '/';\n-\t\t\tretval = read_tree_recursive(current->item.tree,\n+\t\t\tretval = read_tree_recursive(lookup_tree(current->sha1),\n \t\t\t\t\t\t     newbase,\n \t\t\t\t\t\t     baselen + pathlen + 1,\n \t\t\t\t\t\t     stage, match, fn);\n@@ -170,6 +170,7 @@ int parse_tree_buffer(struct tree *item,\n \n \t\tentry = xmalloc(sizeof(struct tree_entry_list));\n \t\tentry->name = path;\n+\t\tentry->sha1 = sha1;\n \t\tentry->mode = mode;\n \t\tentry->directory = S_ISDIR(mode) != 0;\n \t\tentry->executable = (mode & S_IXUSR) != 0;\n@@ -178,12 +179,6 @@ int parse_tree_buffer(struct tree *item,\n \t\tentry->next = NULL;\n \n \t\tupdate_tree_entry(&desc);\n-\n-\t\tif (entry->directory) {\n-\t\t\tentry->item.tree = lookup_tree(sha1);\n-\t\t} else {\n-\t\t\tentry->item.blob = lookup_blob(sha1);\n-\t\t}\n \t\tn_refs++;\n \t\t*list_p = entry;\n \t\tlist_p = &entry->next;\n@@ -193,8 +188,16 @@ int parse_tree_buffer(struct tree *item,\n \t\tstruct tree_entry_list *entry;\n \t\tunsigned i = 0;\n \t\tstruct object_refs *refs = alloc_object_refs(n_refs);\n-\t\tfor (entry = item->entries; entry; entry = entry->next)\n-\t\t\trefs->ref[i++] = entry->item.any;\n+\t\tfor (entry = item->entries; entry; entry = entry->next) {\n+\t\t\tstruct object *obj;\n+\n+\t\t\tif (entry->directory)\n+\t\t\t\tobj = &lookup_tree(entry->sha1)->object;\n+\t\t\telse\n+\t\t\t\tobj = &lookup_blob(entry->sha1)->object;\n+\t\t\trefs->ref[i++] = obj;\n+\t\t}\n+\t\t\t\t\n \t\tset_object_refs(&item->object, refs);\n \t}\n \ndiff --git a/tree.h b/tree.h\nindex 066ac5d..a27bae4 100644\n--- a/tree.h\n+++ b/tree.h\n@@ -13,11 +13,7 @@ struct tree_entry_list {\n \tunsigned zeropad : 1;\n \tunsigned int mode;\n \tconst char *name;\n-\tunion {\n-\t\tstruct object *any;\n-\t\tstruct tree *tree;\n-\t\tstruct blob *blob;\n-\t} item;\n+\tconst unsigned char *sha1;\n };\n \n struct tree {\n@@ -37,7 +33,7 @@ int parse_tree(struct tree *tree);\n struct tree *parse_tree_indirect(const unsigned char *sha1);\n \n #define READ_TREE_RECURSIVE 1\n-typedef int (*read_tree_fn_t)(unsigned char *, const char *, int, const char *, unsigned int, int);\n+typedef int (*read_tree_fn_t)(const unsigned char *, const char *, int, const char *, unsigned int, int);\n \n extern int read_tree_recursive(struct tree *tree,\n \t\t\t       const char *base, int baselen,\n"},{"id":"20846","messageId":"Pine.LNX.4.64.0605281510080.5623@g5.osdl.org","threadId":"4323","inReplyTo":"Pine.LNX.4.64.0605281453460.5623@g5.osdl.org","subject":"[PATCH 3/4] Switch \"read_tree_recursive()\" over to tree-walk functionality","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-28T22:11:28Z","receivedAt":"2006-05-28T22:11:28Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nDon't use the tree_entry list, it really had no major reason not to just\nwalk the raw tree instead.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n tree.c |   33 ++++++++++++++++++++-------------\n 1 files changed, 20 insertions(+), 13 deletions(-)\n\ndiff --git a/tree.c b/tree.c\nindex ba8742c..8a7fdd4 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -78,19 +78,26 @@ int read_tree_recursive(struct tree *tre\n \t\t\tint stage, const char **match,\n \t\t\tread_tree_fn_t fn)\n {\n-\tstruct tree_entry_list *list;\n+\tstruct tree_desc desc;\n+\n \tif (parse_tree(tree))\n \t\treturn -1;\n-\tlist = tree->entries;\n-\twhile (list) {\n-\t\tstruct tree_entry_list *current = list;\n-\t\tlist = list->next;\n-\t\tif (!match_tree_entry(base, baselen, current->name,\n-\t\t\t\t      current->mode, match))\n+\n+\tdesc.buf = tree->buffer;\n+\tdesc.size = tree->size;\n+\n+\twhile (desc.size) {\n+\t\tunsigned mode;\n+\t\tconst char *name;\n+\t\tconst unsigned char *sha1;\n+\n+\t\tsha1 = tree_entry_extract(&desc, &name, &mode);\n+\t\tupdate_tree_entry(&desc);\n+\n+\t\tif (!match_tree_entry(base, baselen, name, mode, match))\n \t\t\tcontinue;\n \n-\t\tswitch (fn(current->sha1, base, baselen,\n-\t\t\t   current->name, current->mode, stage)) {\n+\t\tswitch (fn(sha1, base, baselen, name, mode, stage)) {\n \t\tcase 0:\n \t\t\tcontinue;\n \t\tcase READ_TREE_RECURSIVE:\n@@ -98,16 +105,16 @@ int read_tree_recursive(struct tree *tre\n \t\tdefault:\n \t\t\treturn -1;\n \t\t}\n-\t\tif (current->directory) {\n+\t\tif (S_ISDIR(mode)) {\n \t\t\tint retval;\n-\t\t\tint pathlen = strlen(current->name);\n+\t\t\tint pathlen = strlen(name);\n \t\t\tchar *newbase;\n \n \t\t\tnewbase = xmalloc(baselen + 1 + pathlen);\n \t\t\tmemcpy(newbase, base, baselen);\n-\t\t\tmemcpy(newbase + baselen, current->name, pathlen);\n+\t\t\tmemcpy(newbase + baselen, name, pathlen);\n \t\t\tnewbase[baselen + pathlen] = '/';\n-\t\t\tretval = read_tree_recursive(lookup_tree(current->sha1),\n+\t\t\tretval = read_tree_recursive(lookup_tree(sha1),\n \t\t\t\t\t\t     newbase,\n \t\t\t\t\t\t     baselen + pathlen + 1,\n \t\t\t\t\t\t     stage, match, fn);\n"},{"id":"20847","messageId":"Pine.LNX.4.64.0605281511350.5623@g5.osdl.org","threadId":"4323","inReplyTo":"Pine.LNX.4.64.0605281453460.5623@g5.osdl.org","subject":"[PATCH 4/4] Remove \"tree->entries\" tree-entry list from tree parser","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-05-28T22:13:53Z","receivedAt":"2006-05-28T22:13:53Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis finally removes the tree-entry list from \"struct tree\", since most of \nthe users can just use the tree-walk infrastructure to walk the raw tree \nbuffers instead of the tree-entry list.\n\nThe tree-entry list is inefficient, and generates tons of small \nallocations for no good reason. The tree-walk infrastructure is generally \nno harder to use than following a linked list, and allows us to do most \ntree parsing in-place.\n\nSome programs still use the old tree-entry lists, and are a bit painful to \nconvert without major surgery. For them we have a helper function that \ncreates a temporary tree-entry list on demand. We can convert those too \neventually, but with this they no longer affect any users who don't need \nthe explicit lists.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n builtin-ls-tree.c   |    2 +\n builtin-read-tree.c |    4 +--\n builtin-rev-list.c  |   26 ++++++++++------\n fetch.c             |   16 +++++++---\n fsck-objects.c      |    7 +++-\n http-push.c         |   30 +++++++++++++------\n revision.c          |    3 +-\n tree.c              |   81 ++++++++++++++++++++++++++++++++++++---------------\n tree.h              |    4 ++-\n 9 files changed, 116 insertions(+), 57 deletions(-)\n\ndiff --git a/builtin-ls-tree.c b/builtin-ls-tree.c\nindex 48385d5..b8d0d88 100644\n--- a/builtin-ls-tree.c\n+++ b/builtin-ls-tree.c\n@@ -53,7 +53,7 @@ static int show_recursive(const char *ba\n \t}\n }\n \n-static int show_tree(unsigned char *sha1, const char *base, int baselen,\n+static int show_tree(const unsigned char *sha1, const char *base, int baselen,\n \t\t     const char *pathname, unsigned mode, int stage)\n {\n \tint retval = 0;\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex f0b8dad..da0731c 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -163,7 +163,7 @@ #endif\n \t\t\t\tstruct tree *tree = lookup_tree(posns[i]->sha1);\n \t\t\t\tany_dirs = 1;\n \t\t\t\tparse_tree(tree);\n-\t\t\t\tsubposns[i] = tree->entries;\n+\t\t\t\tsubposns[i] = create_tree_entry_list(tree);\n \t\t\t\tposns[i] = posns[i]->next;\n \t\t\t\tsrc[i + merge] = &df_conflict_entry;\n \t\t\t\tcontinue;\n@@ -368,7 +368,7 @@ static int unpack_trees(merge_fn_t fn)\n \tif (len) {\n \t\tposns = xmalloc(len * sizeof(struct tree_entry_list *));\n \t\tfor (i = 0; i < len; i++) {\n-\t\t\tposns[i] = ((struct tree *) posn->item)->entries;\n+\t\t\tposns[i] = create_tree_entry_list((struct tree *) posn->item);\n \t\t\tposn = posn->next;\n \t\t}\n \t\tif (unpack_trees_rec(posns, len, \"\", fn, &indpos))\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 94f520b..6e2b898 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -113,7 +113,7 @@ static struct object_list **process_tree\n \t\t\t\t\t const char *name)\n {\n \tstruct object *obj = &tree->object;\n-\tstruct tree_entry_list *entry;\n+\tstruct tree_desc desc;\n \tstruct name_path me;\n \n \tif (!revs.tree_objects)\n@@ -128,16 +128,22 @@ static struct object_list **process_tree\n \tme.up = path;\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n-\tentry = tree->entries;\n-\ttree->entries = NULL;\n-\twhile (entry) {\n-\t\tstruct tree_entry_list *next = entry->next;\n-\t\tif (entry->directory)\n-\t\t\tp = process_tree(lookup_tree(entry->sha1), p, &me, entry->name);\n+\n+\tdesc.buf = tree->buffer;\n+\tdesc.size = tree->size;\n+\n+\twhile (desc.size) {\n+\t\tunsigned mode;\n+\t\tconst char *name;\n+\t\tconst unsigned char *sha1;\n+\n+\t\tsha1 = tree_entry_extract(&desc, &name, &mode);\n+\t\tupdate_tree_entry(&desc);\n+\n+\t\tif (S_ISDIR(mode))\n+\t\t\tp = process_tree(lookup_tree(sha1), p, &me, name);\n \t\telse\n-\t\t\tp = process_blob(lookup_blob(entry->sha1), p, &me, entry->name);\n-\t\tfree(entry);\n-\t\tentry = next;\n+\t\t\tp = process_blob(lookup_blob(sha1), p, &me, name);\n \t}\n \tfree(tree->buffer);\n \ttree->buffer = NULL;\ndiff --git a/fetch.c b/fetch.c\nindex f7f8902..d9fe41f 100644\n--- a/fetch.c\n+++ b/fetch.c\n@@ -41,16 +41,22 @@ static int process_tree(struct tree *tre\n \tif (parse_tree(tree))\n \t\treturn -1;\n \n-\tentry = tree->entries;\n-\ttree->entries = NULL;\n+\tentry = create_tree_entry_list(tree);\n \twhile (entry) {\n \t\tstruct tree_entry_list *next = entry->next;\n-\t\tif (process(entry->item.any))\n-\t\t\treturn -1;\n-\t\tfree(entry->name);\n+\n+\t\tif (entry->directory) {\n+\t\t\tstruct tree *tree = lookup_tree(entry->sha1);\n+\t\t\tprocess_tree(tree);\n+\t\t} else {\n+\t\t\tstruct blob *blob = lookup_blob(entry->sha1);\n+\t\t\tprocess(&blob->object);\n+\t\t}\n \t\tfree(entry);\n \t\tentry = next;\n \t}\n+\tfree(tree->buffer);\n+\ttree->buffer = NULL;\n \treturn 0;\n }\n \ndiff --git a/fsck-objects.c b/fsck-objects.c\nindex 44b6465..ec99a7a 100644\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -10,6 +10,7 @@ #include \"refs.h\"\n #include \"pack.h\"\n \n #define REACHABLE 0x0001\n+#define SEEN      0x0002\n \n static int show_root = 0;\n static int show_tags = 0;\n@@ -160,7 +161,7 @@ static int fsck_tree(struct tree *item)\n \tstruct tree_entry_list *entry, *last;\n \n \tlast = NULL;\n-\tfor (entry = item->entries; entry; entry = entry->next) {\n+\tfor (entry = create_tree_entry_list(item); entry; entry = entry->next) {\n \t\tif (strchr(entry->name, '/'))\n \t\t\thas_full_path = 1;\n \t\thas_zero_pad |= entry->zeropad;\n@@ -204,7 +205,6 @@ static int fsck_tree(struct tree *item)\n \t}\n \tif (last)\n \t\tfree(last);\n-\titem->entries = NULL;\n \tfree(item->buffer);\n \titem->buffer = NULL;\n \n@@ -276,6 +276,9 @@ static int fsck_sha1(unsigned char *sha1\n \tstruct object *obj = parse_object(sha1);\n \tif (!obj)\n \t\treturn error(\"%s: object not found\", sha1_to_hex(sha1));\n+\tif (obj->flags & SEEN)\n+\t\treturn 0;\n+\tobj->flags |= SEEN;\n \tif (obj->type == blob_type)\n \t\treturn 0;\n \tif (obj->type == tree_type)\ndiff --git a/http-push.c b/http-push.c\nindex f492a5d..72ad89c 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1704,6 +1704,7 @@ static struct object_list **process_blob\n \t\treturn p;\n \n \tobj->flags |= SEEN;\n+\tname = strdup(name);\n \treturn add_object(obj, p, path, name);\n }\n \n@@ -1713,7 +1714,7 @@ static struct object_list **process_tree\n \t\t\t\t\t const char *name)\n {\n \tstruct object *obj = &tree->object;\n-\tstruct tree_entry_list *entry;\n+\tstruct tree_desc desc;\n \tstruct name_path me;\n \n \tobj->flags |= LOCAL;\n@@ -1724,21 +1725,30 @@ static struct object_list **process_tree\n \t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n \n \tobj->flags |= SEEN;\n+\tname = strdup(name);\n \tp = add_object(obj, p, NULL, name);\n \tme.up = path;\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n-\tentry = tree->entries;\n-\ttree->entries = NULL;\n-\twhile (entry) {\n-\t\tstruct tree_entry_list *next = entry->next;\n-\t\tif (entry->directory)\n-\t\t\tp = process_tree(lookup_tree(entry->sha1), p, &me, entry->name);\n+\n+\tdesc.buf = tree->buffer;\n+\tdesc.size = tree->size;\n+\n+\twhile (desc.size) {\n+\t\tunsigned mode;\n+\t\tconst char *name;\n+\t\tconst unsigned char *sha1;\n+\n+\t\tsha1 = tree_entry_extract(&desc, &name, &mode);\n+\t\tupdate_tree_entry(&desc);\n+\n+\t\tif (S_ISDIR(mode))\n+\t\t\tp = process_tree(lookup_tree(sha1), p, &me, name);\n \t\telse\n-\t\t\tp = process_blob(lookup_blob(entry->sha1), p, &me, entry->name);\n-\t\tfree(entry);\n-\t\tentry = next;\n+\t\t\tp = process_blob(lookup_blob(sha1), p, &me, name);\n \t}\n+\tfree(tree->buffer);\n+\ttree->buffer = NULL;\n \treturn p;\n }\n \ndiff --git a/revision.c b/revision.c\nindex 35f8e3b..c366178 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -63,8 +63,7 @@ void mark_tree_uninteresting(struct tree\n \t\treturn;\n \tif (parse_tree(tree) < 0)\n \t\tdie(\"bad tree %s\", sha1_to_hex(obj->sha1));\n-\tentry = tree->entries;\n-\ttree->entries = NULL;\n+\tentry = create_tree_entry_list(tree);\n \twhile (entry) {\n \t\tstruct tree_entry_list *next = entry->next;\n \t\tif (entry->directory)\ndiff --git a/tree.c b/tree.c\nindex 8a7fdd4..db6e59f 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -151,22 +151,65 @@ struct tree *lookup_tree(const unsigned \n \treturn (struct tree *) obj;\n }\n \n-int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size)\n+static int track_tree_refs(struct tree *item)\n {\n+\tint n_refs = 0, i;\n+\tstruct object_refs *refs;\n \tstruct tree_desc desc;\n-\tstruct tree_entry_list **list_p;\n-\tint n_refs = 0;\n \n+\t/* Count how many entries there are.. */\n+\tdesc.buf = item->buffer;\n+\tdesc.size = item->size;\n+\twhile (desc.size) {\n+\t\tn_refs++;\n+\t\tupdate_tree_entry(&desc);\n+\t}\n+\n+\t/* Allocate object refs and walk it again.. */\n+\ti = 0;\n+\trefs = alloc_object_refs(n_refs);\n+\tdesc.buf = item->buffer;\n+\tdesc.size = item->size;\n+\twhile (desc.size) {\n+\t\tunsigned mode;\n+\t\tconst char *name;\n+\t\tconst unsigned char *sha1;\n+\t\tstruct object *obj;\n+\n+\t\tsha1 = tree_entry_extract(&desc, &name, &mode);\n+\t\tupdate_tree_entry(&desc);\n+\t\tif (S_ISDIR(mode))\n+\t\t\tobj = &lookup_tree(sha1)->object;\n+\t\telse\n+\t\t\tobj = &lookup_blob(sha1)->object;\n+\t\trefs->ref[i++] = obj;\n+\t}\n+\tset_object_refs(&item->object, refs);\n+\treturn 0;\n+}\n+\n+int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size)\n+{\n \tif (item->object.parsed)\n \t\treturn 0;\n \titem->object.parsed = 1;\n \titem->buffer = buffer;\n \titem->size = size;\n \n-\tdesc.buf = buffer;\n-\tdesc.size = size;\n+\tif (track_object_refs)\n+\t\ttrack_tree_refs(item);\n+\treturn 0;\n+}\n+\n+struct tree_entry_list *create_tree_entry_list(struct tree *tree)\n+{\n+\tstruct tree_desc desc;\n+\tstruct tree_entry_list *ret = NULL;\n+\tstruct tree_entry_list **list_p = &ret;\n+\n+\tdesc.buf = tree->buffer;\n+\tdesc.size = tree->size;\n \n-\tlist_p = &item->entries;\n \twhile (desc.size) {\n \t\tunsigned mode;\n \t\tconst char *path;\n@@ -186,29 +229,19 @@ int parse_tree_buffer(struct tree *item,\n \t\tentry->next = NULL;\n \n \t\tupdate_tree_entry(&desc);\n-\t\tn_refs++;\n \t\t*list_p = entry;\n \t\tlist_p = &entry->next;\n \t}\n+\treturn ret;\n+}\n \n-\tif (track_object_refs) {\n-\t\tstruct tree_entry_list *entry;\n-\t\tunsigned i = 0;\n-\t\tstruct object_refs *refs = alloc_object_refs(n_refs);\n-\t\tfor (entry = item->entries; entry; entry = entry->next) {\n-\t\t\tstruct object *obj;\n-\n-\t\t\tif (entry->directory)\n-\t\t\t\tobj = &lookup_tree(entry->sha1)->object;\n-\t\t\telse\n-\t\t\t\tobj = &lookup_blob(entry->sha1)->object;\n-\t\t\trefs->ref[i++] = obj;\n-\t\t}\n-\t\t\t\t\n-\t\tset_object_refs(&item->object, refs);\n+void free_tree_entry_list(struct tree_entry_list *list)\n+{\n+\twhile (list) {\n+\t\tstruct tree_entry_list *next = list->next;\n+\t\tfree(list);\n+\t\tlist = next;\n \t}\n-\n-\treturn 0;\n }\n \n int parse_tree(struct tree *item)\ndiff --git a/tree.h b/tree.h\nindex a27bae4..c7b5248 100644\n--- a/tree.h\n+++ b/tree.h\n@@ -20,9 +20,11 @@ struct tree {\n \tstruct object object;\n \tvoid *buffer;\n \tunsigned long size;\n-\tstruct tree_entry_list *entries;\n };\n \n+struct tree_entry_list *create_tree_entry_list(struct tree *);\n+void free_tree_entry_list(struct tree_entry_list *);\n+\n struct tree *lookup_tree(const unsigned char *sha1);\n \n int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size);\n"}]}