[PATCH 0/10] re-based and expanded tree-walker cleanup patches

[PATCH 0/10] re-based and expanded tree-walker cleanup patches

[Linus Torvalds]

Ok, this is largely the same series as the previous 1..4 patches, but 
rebased on top of the current master tree because the cache-tree patches 
added some tree_entry_list walkers (which accounts for one extra patch in 
the series, and some trivial merge fixups).

Two new patches then clean up fsck-objects, which really didn't want the 
old tree_entry_list at all (and had added some hacks to the list entry 
just because fsck actually needed to check the raw data).

Another two new patches convert the last remnant of tree_entry_list in 
revision.c and fetch.c respectively to the new world order.

And the final patch then moves the "tree_entry_list" crud into the only 
remaining user, namely builtin-read-tree.c. That file is pretty messy and 
hard to convert, and I don't want to touch it right now, so I left it with 
the nasty compatibility functions. But now that's at least well-contained.

I think the series is all good, and should replace the old one in "next" 
(and cook there for a while just to make sure it's ok).

		Linus

[PATCH 1/10] Make "struct tree" contain the pointer to the tree buffer

[Linus Torvalds]

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 <torvalds@osdl.org>
---
 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 716f792..6876f3d 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -39,7 +39,7 @@ static struct tree_entry_list df_conflic
 
 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_
 	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 5277d3c..72c1549 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -136,10 +136,11 @@ static struct object_list **process_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 1922b6d..5e65df4 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 4d46e0d..1a7823c 100644
--- a/object.c
+++ b/object.c
@@ -200,8 +200,11 @@ struct object *parse_object(const unsign
 			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 d599fb5..1e76d9c 100644
--- a/tree.c
+++ b/tree.c
@@ -3,6 +3,7 @@ #include "tree.h"
 #include "blob.h"
 #include "commit.h"
 #include "tag.h"
+#include "tree-walk.h"
 #include <stdlib.h>
 
 const char *tree_type = "tree";
@@ -145,46 +146,45 @@ struct tree *lookup_tree(const unsigned 
 
 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 330ab64..066ac5d 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;
 };
 
-- 
1.3.3.gcd01d

[PATCH 2/10] Make "tree_entry" have a SHA1 instead of a union of object pointers

[Linus Torvalds]

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 <torvalds@osdl.org>
---
 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 99ceea8..88bfec2 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,
 	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 6876f3d..5e513c8 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -161,9 +161,10 @@ #endif
 			}
 
 			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 @@ #endif
 
 			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 
 			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 72c1549..94f520b 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -133,9 +133,9 @@ static struct object_list **process_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 5e65df4..ed2eb27 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 b4327d9..f492a5d 100644
--- a/http-push.c
+++ b/http-push.c
@@ -1733,9 +1733,9 @@ static struct object_list **process_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 1a7823c..9adc874 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 42c077a..8d70a6f 100644
--- a/revision.c
+++ b/revision.c
@@ -68,9 +68,9 @@ void mark_tree_uninteresting(struct 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 1e76d9c..ba8742c 100644
--- a/tree.c
+++ b/tree.c
@@ -8,7 +8,7 @@ #include <stdlib.h>
 
 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 *tre
 				      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 *tre
 			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,
 
 		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,
 		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,
 		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 066ac5d..a27bae4 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,
-- 
1.3.3.gcd01d

[PATCH 3/10] Switch "read_tree_recursive()" over to tree-walk functionality

[Linus Torvalds]

Don't use the tree_entry list any more.

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---
 tree.c |   33 ++++++++++++++++++++-------------
 1 files changed, 20 insertions(+), 13 deletions(-)

diff --git a/tree.c b/tree.c
index ba8742c..8a7fdd4 100644
--- a/tree.c
+++ b/tree.c
@@ -78,19 +78,26 @@ int read_tree_recursive(struct tree *tre
 			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 *tre
 		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);
-- 
1.3.3.gcd01d

[PATCH 4/10] builtin-read-tree.c: avoid tree_entry_list in prime_cache_tree_rec()

[Linus Torvalds]

Use the raw tree walker instead.

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---
 builtin-read-tree.c |   20 +++++++++++++++-----
 1 files changed, 15 insertions(+), 5 deletions(-)

diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index 5e513c8..67492bf 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -9,6 +9,7 @@ #include "cache.h"
 
 #include "object.h"
 #include "tree.h"
+#include "tree-walk.h"
 #include "cache-tree.h"
 #include <sys/time.h>
 #include <signal.h>
@@ -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;
-- 
1.3.3.gcd01d

[PATCH 5/10] Remove "tree->entries" tree-entry list from tree parser

[Linus Torvalds]

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 <torvalds@osdl.org>
---
 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 48385d5..b8d0d88 100644
--- a/builtin-ls-tree.c
+++ b/builtin-ls-tree.c
@@ -53,7 +53,7 @@ static int show_recursive(const char *ba
 	}
 }
 
-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 67492bf..480e6ed 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -165,7 +165,7 @@ #endif
 				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 94f520b..6e2b898 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -113,7 +113,7 @@ static struct object_list **process_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
 	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 f7f8902..d9fe41f 100644
--- a/fetch.c
+++ b/fetch.c
@@ -41,16 +41,22 @@ static int process_tree(struct tree *tre
 	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 ed2eb27..42778e8 100644
--- a/fsck-objects.c
+++ b/fsck-objects.c
@@ -11,6 +11,7 @@ #include "pack.h"
 #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 f492a5d..72ad89c 100644
--- a/http-push.c
+++ b/http-push.c
@@ -1704,6 +1704,7 @@ static struct object_list **process_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
 					 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
 		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 8d70a6f..c51ea83 100644
--- a/revision.c
+++ b/revision.c
@@ -63,8 +63,7 @@ void mark_tree_uninteresting(struct 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 8a7fdd4..db6e59f 100644
--- a/tree.c
+++ b/tree.c
@@ -151,22 +151,65 @@ struct tree *lookup_tree(const unsigned 
 	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,
 		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 a27bae4..c7b5248 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);
-- 
1.3.3.gcd01d

[PATCH 6/10] fsck-objects: avoid unnecessary tree_entry_list usage

[Linus Torvalds]

Prime example of where the raw tree parser is easier for everybody.

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---
 fsck-objects.c |   55 +++++++++++++++++++++++++++++++++++--------------------
 1 files changed, 35 insertions(+), 20 deletions(-)

diff --git a/fsck-objects.c b/fsck-objects.c
index 42778e8..a9680dc 100644
--- a/fsck-objects.c
+++ b/fsck-objects.c
@@ -9,6 +9,7 @@ #include "tag.h"
 #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_en
 	 * 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_en
 		 * 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,15 +160,30 @@ 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.. 
 		 */
@@ -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;
 
-- 
1.3.3.gcd01d

Re: [PATCH 6/10] fsck-objects: avoid unnecessary tree_entry_list usage

[Linus Torvalds]

On Mon, 29 May 2006, Linus Torvalds wrote:
> -		has_zero_pad |= entry->zeropad;
> +		has_zero_pad |= *(char *)desc.buf = '0';

Aieee.

I fixed that once in my tree already, and then broke it again when 
re-doing the series with cherry-picking but didn't notice, because the 
tests don't pick up the totally bogus warnings that it causes.

That "= '0'" should obviously be "== '0'"

		Linus

[PATCH 7/10] Remove unused "zeropad" entry from tree_list_entry

[Linus Torvalds]

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 <torvalds@osdl.org>
---
 tree.c |    3 +--
 tree.h |    1 -
 2 files changed, 1 insertions(+), 3 deletions(-)

diff --git a/tree.c b/tree.c
index db6e59f..47318ef 100644
--- a/tree.c
+++ b/tree.c
@@ -217,6 +217,7 @@ struct tree_entry_list *create_tree_entr
 		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_entr
 		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 c7b5248..6a87546 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;
-- 
1.3.3.gcd01d

[PATCH 8/10] Convert "mark_tree_uninteresting()" to raw tree walker

[Linus Torvalds]

Not very many users to go..

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---
 revision.c |   31 ++++++++++++++++++++++---------
 1 files changed, 22 insertions(+), 9 deletions(-)

diff --git a/revision.c b/revision.c
index c51ea83..8e93e40 100644
--- a/revision.c
+++ b/revision.c
@@ -53,8 +53,8 @@ static void mark_blob_uninteresting(stru
 
 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
 		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)
-- 
1.3.3.gcd01d

[PATCH 9/10] Convert fetch.c: process_tree() to raw tree walker

[Linus Torvalds]

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 <torvalds@osdl.org>
---
 fetch.c |   24 +++++++++++++++---------
 1 files changed, 15 insertions(+), 9 deletions(-)

diff --git a/fetch.c b/fetch.c
index d9fe41f..976a5a4 100644
--- a/fetch.c
+++ b/fetch.c
@@ -3,6 +3,7 @@ #include "fetch.h"
 #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;
 }
 
-- 
1.3.3.gcd01d

[PATCH 10/10] Remove last vestiges of generic tree_entry_list

[Linus Torvalds]

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 <torvalds@osdl.org>
---
 builtin-read-tree.c |   43 +++++++++++++++++++++++++++++++++++++++++++
 tree.c              |   42 ------------------------------------------
 tree.h              |   13 -------------
 3 files changed, 43 insertions(+), 55 deletions(-)

diff --git a/builtin-read-tree.c b/builtin-read-tree.c
index 480e6ed..b413e91 100644
--- a/builtin-read-tree.c
+++ b/builtin-read-tree.c
@@ -33,6 +33,16 @@ static struct object_list *trees = NULL;
 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 = {
 	.name = NULL,
 	.next = &df_conflict_list
@@ -40,6 +50,39 @@ static struct tree_entry_list df_conflic
 
 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 47318ef..fb18724 100644
--- a/tree.c
+++ b/tree.c
@@ -201,48 +201,6 @@ int parse_tree_buffer(struct tree *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;
-
-	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 6a87546..dd25c53 100644
--- a/tree.h
+++ b/tree.h
@@ -5,25 +5,12 @@ #include "object.h"
 
 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);
-- 
1.3.3.gcd01d

Re: [PATCH 0/10] re-based and expanded tree-walker cleanup patches

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> Ok, this is largely the same series as the previous 1..4 patches, but 
> rebased on top of the current master tree because the cache-tree patches 
> added some tree_entry_list walkers (which accounts for one extra patch in 
> the series, and some trivial merge fixups).
>
> Two new patches then clean up fsck-objects, which really didn't want the 
> old tree_entry_list at all (and had added some hacks to the list entry 
> just because fsck actually needed to check the raw data).
>
> Another two new patches convert the last remnant of tree_entry_list in 
> revision.c and fetch.c respectively to the new world order.
>
> And the final patch then moves the "tree_entry_list" crud into the only 
> remaining user, namely builtin-read-tree.c. That file is pretty messy and 
> hard to convert, and I don't want to touch it right now, so I left it with 
> the nasty compatibility functions. But now that's at least well-contained.
>
> I think the series is all good, and should replace the old one in "next" 
> (and cook there for a while just to make sure it's ok).

Sorry for having you have done this -- last night I've merged
the series without rebasing and have the result in "next".  I'll
compare to see if you have spotted my mismerges there tonight.

This reminds me of one issue.

        From: Junio C Hamano <junkio@cox.net>
        Subject: Necessity of "evil" merge and topic branches
        Cc: git@vger.kernel.org
        Date: Wed, 17 May 2006 23:25:55 -0700
        Message-ID: <7vy7wz6e8c.fsf@assigned-by-dhcp.cox.net>

I have such an evil-merge branch merged in "next" to deal with
necessarily adjustments; it is 0a2586c, which is the tip of its
own branch.  I was hoping this way I can merge it in to "master"
when I want to pull your yesterday's series.

Re: [PATCH 0/10] re-based and expanded tree-walker cleanup patches

[Linus Torvalds]

On Mon, 29 May 2006, Junio C Hamano wrote:
> 
> Sorry for having you have done this -- last night I've merged
> the series without rebasing and have the result in "next".  I'll
> compare to see if you have spotted my mismerges there tonight.

It was interesting. I cleaned up the series and switched the order of some 
commits in my tree by doing first a "git rebase" and then cherry-picking 
them into another branch, and using "git commit --amend" to fix up some of 
the things I had missed.

Pretty powerful, although at one point I was wondering about having a "git 
rebase" that could switch commits around or drop unwanted ones (ie let the 
user edit the cherry-picking list before the actual rebase).

Re: [PATCH 0/10] re-based and expanded tree-walker cleanup patches

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> On Mon, 29 May 2006, Junio C Hamano wrote:
>> 
>> Sorry for having you have done this -- last night I've merged
>> the series without rebasing and have the result in "next".  I'll
>> compare to see if you have spotted my mismerges there tonight.
>
> It was interesting. I cleaned up the series and switched the order of some 
> commits in my tree by doing first a "git rebase" and then cherry-picking 
> them into another branch, and using "git commit --amend" to fix up some of 
> the things I had missed.

I just did this (readers on the list needs to disect "next" if
they are interested to reproduce this, since I do not publish
individual topic heads, but each of the merge commits on "next"
tells which topics are merged, so that should be trivial):

	$ git checkout -b lt/tree-2 master
        $ apply your 10-patch series
	$ git show-branch lt/tree lt/tree-2 jc/lt-tree-n-cache-tree next

Your yesterday's series is on lt/tree, and jc/lt-tree-n-cache-tree
is my "evil merge" branch to adjust it to the cache-tree that I had
in "next".  It's tip has cache-tree and lt/tree merged, so
it should match the early parts of today's 10-patch series.  I
used show-branch to find that lt/tree-2~5 is the one to match
yesterday's series:

	$ git diff --name-only lt/tree~4..lt/tree |
	  xargs git diff lt/tree-2~5 jc/lt-tree-n-cache-tree --

This shows only cosmetic differences, which is good.

> Pretty powerful, although at one point I was wondering about having a "git 
> rebase" that could switch commits around or drop unwanted ones (ie let the 
> user edit the cherry-picking list before the actual rebase).

I think true power users would just do the last two lines of
git-rebase.sh by hand in two steps.  By stashing away the
format-patch output, and using git-am interactively, you can
easily drop unwanted ones, and then re-run git-am on the same
format-patch output to apply the ones you dropped on the first
run practically amounts to reordering the patches ;-).

Re: [PATCH 0/10] re-based and expanded tree-walker cleanup patches

[Linus Torvalds]

On Mon, 29 May 2006, Junio C Hamano wrote:
>
> > Pretty powerful, although at one point I was wondering about having a "git 
> > rebase" that could switch commits around or drop unwanted ones (ie let the 
> > user edit the cherry-picking list before the actual rebase).
> 
> I think true power users would just do the last two lines of
> git-rebase.sh by hand in two steps.  By stashing away the
> format-patch output, and using git-am interactively, you can
> easily drop unwanted ones, and then re-run git-am on the same
> format-patch output to apply the ones you dropped on the first
> run practically amounts to reordering the patches ;-).

Having to move around whole patches in the editor is not what you want to 
do. I was thinking more along the lines of

 (a) git-rev-list --pretty=oneline "$upstream"..ORIG_HEAD > rev-list

 (b) edit the rev-list, moving the single lines around, deleting them, etc

 (c) cat rev-list |
     git-format-patch -k --stdout --stdin --full_index |
     git-am

because the "--pretty=oneline" format is actually very nice as a way to 
re-order things and select single commits to be deleted or whatever..

		Linus

Re: [PATCH 0/10] re-based and expanded tree-walker cleanup patches

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> Having to move around whole patches in the editor is not what you want to 
> do.

I know.  What I meant was:

	$ format-patch >those-patches
        $ am -i those-patches
	.. say no to the first two and yes to the third one
        $ am -i those-patches ;# again!!
        .. say yes to the first two

> I was thinking more along the lines of
>
>  (a) git-rev-list --pretty=oneline "$upstream"..ORIG_HEAD > rev-list
>
>  (b) edit the rev-list, moving the single lines around, deleting them, etc
>
>  (c) cat rev-list |
>      git-format-patch -k --stdout --stdin --full_index |
>      git-am
>
> because the "--pretty=oneline" format is actually very nice as a way to 
> re-order things and select single commits to be deleted or whatever..

I like this approach as well.

Re: [PATCH 0/10] re-based and expanded tree-walker cleanup patches

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

>  (a) git-rev-list --pretty=oneline "$upstream"..ORIG_HEAD > rev-list
>
>  (b) edit the rev-list, moving the single lines around, deleting them, etc
>
>  (c) cat rev-list |
>      git-format-patch -k --stdout --stdin --full_index |
>      git-am
>
> because the "--pretty=oneline" format is actually very nice as a way to 
> re-order things and select single commits to be deleted or whatever..

I am thinking about doing "format-patch --stdin" while I am
futzing with it for other reasons, and one issue is where to
"tac" the revision list.

We could internally reverse topo-sort what we read from --stdin
inside format-patch, but that would defeat the reordering that
is done in the step (b) above, so that is not a useful thing to
do.

If we wanted to make rev-list piped straight to format-patch
equilvalent to giving the arguments you would have given rev-list
directly to format-patch, then format-patch should read --stdin
and reverse the list before emitting them out.

However, that would mean in the step (b) above the user needs to
be conscious that the list being edited is in the reverse order,
so if the list of commits needs to be reordered (and that is one
of the reasons the user is doing this step) what comes earlier
in the edited list will be output later in the result.

Tentatively my feeling is that we should make it known that the
list format-patch takes from --stdin is supposed to be _not_
reversed, and do nothing in format-patch.  In other words, the
list fed is a moral equivalent to quilt "series" file.

What this means is:

	git-format-patch $revargs

is not equivalent to

	git-rev-list $revargs | git-format-patch --stdin

but is equivalent to

	git-rev-list $revargs | tac | git-format-patch --stdin


Thoughts from the list?

Re: [PATCH 0/10] re-based and expanded tree-walker cleanup patches

[Shawn Pearce]

Junio C Hamano <junkio@cox.net> wrote:
> Linus Torvalds <torvalds@osdl.org> writes:
> 
> >  (a) git-rev-list --pretty=oneline "$upstream"..ORIG_HEAD > rev-list
> >
> >  (b) edit the rev-list, moving the single lines around, deleting them, etc
> >
> >  (c) cat rev-list |
> >      git-format-patch -k --stdout --stdin --full_index |
> >      git-am
> >
[snip]
> What this means is:
> 
> 	git-format-patch $revargs
> 
> is not equivalent to
> 
> 	git-rev-list $revargs | git-format-patch --stdin
> 
> but is equivalent to
> 
> 	git-rev-list $revargs | tac | git-format-patch --stdin
> 
> 
> Thoughts from the list?

Aside from not knowing what tac is I agree with the latter.
It is what the user would expect to happen.  Except maybe add a
--ancestors-first option to git-rev-list to do what tac does before
outputting the revisions?

	git-rev-list --ancestors-first $revargs | git-format-patch --stdin

-- 
Shawn.

A series file for git?

[Eric W. Biederman]

Junio C Hamano <junkio@cox.net> writes:

> Linus Torvalds <torvalds@osdl.org> writes:
>
>>  (a) git-rev-list --pretty=oneline "$upstream"..ORIG_HEAD > rev-list
>>
>>  (b) edit the rev-list, moving the single lines around, deleting them, etc
>>
>>  (c) cat rev-list |
>>      git-format-patch -k --stdout --stdin --full_index |
>>      git-am
>>

> Tentatively my feeling is that we should make it known that the
> list format-patch takes from --stdin is supposed to be _not_
> reversed, and do nothing in format-patch.  In other words, the
> list fed is a moral equivalent to quilt "series" file.

Agreed that seem to make a lot of sense.

> What this means is:
>
> 	git-format-patch $revargs
>
> is not equivalent to
>
> 	git-rev-list $revargs | git-format-patch --stdin
>
> but is equivalent to
>
> 	git-rev-list $revargs | tac | git-format-patch --stdin

At least for now the using tac is fine.  Longer term I think
having some reverse arguments to rev-list or even better
git-log so we can review patches in order instead backwards
would be very interesting.

> Thoughts from the list?

So I have played with this some and a bit of feedback.

I was using:
	git-rev-list $revargs | tac > list

	for sha1 in $(cat list); do git-cherry-pick -r $sha1 ; done

Is there any real difference between using git-format-patch | git-am
and using git-am to apply patches.  I was using git-cherry-pick simply
because it was easier to sha1 too.

- When you reorder patches minor merge conflicts are common
  so a big pipe won't work very often in practice.  So you
  need a way to handle failures in the middle.

- Keeping patches in git and just remembering their sha1 is nice
  but it has the downside that it can be really easy to loose
  the sha1, and thus the patch.  So some sort of history mechanism
  so you can get back to where you were would be nice.

- This is a similar technique to topic branches.  However in some
  of the more interesting cases a topic branch can't be used because
  you have a whole series of little changes, that allow depend on
  each other.  So topic branches need not apply.

- One of the places where we currently uses series files
  (patch-scripts && quilt), and heavy cherry picking is for patch
  aging.  That is letting patches sit in a testing branch for 
  a while so people have a chance to test and look at them.

  The important pieces there are the ability to reorder the changes
  to put the patches with the highest confidence first.

  The ability to comment on the patches so that it is possible
  to record groups of patches and information about their relative
  stability.  As once a patch series gets large without at least
  a few comments it is too much for a person to remember what
  is happening with each patch without a few clues.

- The other place where we use series files is in pure development
  where we are breaking up or otherwise creating the needed changes
  in a set of simple obviously correct changes.

....

So I think it could be very interesting to have a series file
as something the base git porcelain helps to deal with.

If we create a meta data branch with just the series file
we can remove the risk of loosing things, as we always
have a path back to the old history if we want it.

We can keep track of the series file with a SERIES_HEAD
similar to FETCH_HEAD.  This fairly easily allows editing
in different places in the patch stack that normally happens
with  quilt or patch-scripts.

We can put comments in a series file to keep track of probationary
patches.

The two tricky pieces I see with this idea are:
- teaching git-fsck-objects that we have a sha1 in a blob objects.

- Where to put the active checkout series file when we are working,
  so we don't stumble on it.

...

I'm trying to sort out a sane work flow for developing with a large
number of highly related patches on the development side.  I care
because the way I think I usually fix the root cause of problems.

It took me nearly 25 patches to decouple the brain damage the msi
code imposed on x86 irq handling.   In the development of that
I had to reorder and edit things extensively as I broke the
work up, and created a sane patch flow.

The trick with rev-list | tac to create a series file for reordering
changes was very useful but it wasn't enough to say it solve the
problem.  

One trivial issue was that git-cherry-pick -r always does the full
git-commit so it is much more I/O bound than necessary, because
git-commit does git-status.  Which is just silly if you are applying
a bunch of changes that apply without errors.

Eric

Re: A series file for git?

[Junio C Hamano]

ebiederm@xmission.com (Eric W. Biederman) writes:

> Is there any real difference between using git-format-patch | git-am
> and using git-am to apply patches.  I was using git-cherry-pick simply
> because it was easier to sha1 too.
>
> - When you reorder patches minor merge conflicts are common
>   so a big pipe won't work very often in practice.  So you
>   need a way to handle failures in the middle.

True.  The big pipe's answer to that question is that git-am
stashes what is fed to it just like when it is applying multiple
patches in .dotest/ and lets you continue from where a breakage
happened.  Also the way rebase (without the new --merge flag)
worked was to produce format-patch with full blob SHA1's on the
index lines and run git-am with --3way, so it can fall back on
three-way merge when the patch does not apply.  This often
resulted in "git-am --3way" detecting a patch that does not
apply, falling back to do a three way to notice that the patch
has already been applied.

I have to think about the rest of your message on "series" file.

Re: A series file for git?

[Junio C Hamano]

ebiederm@xmission.com (Eric W. Biederman) writes:

> I was using:
> 	git-rev-list $revargs | tac > list
> 	for sha1 in $(cat list); do git-cherry-pick -r $sha1 ; done
>...
> - Keeping patches in git and just remembering their sha1 is nice
>   but it has the downside that it can be really easy to loose
>   the sha1, and thus the patch.  So some sort of history mechanism
>   so you can get back to where you were would be nice.

Actually, the $revargs above is composed of your branch names
(e.g. "^master this-topic that-topic"), so as long as you do not
lose these branches they are protected.
>
> - This is a similar technique to topic branches.  However in some
>   of the more interesting cases a topic branch can't be used because
>   you have a whole series of little changes, that allow depend on
>   each other.  So topic branches need not apply.

Sorry I fail to see why.  A series of little changes that depend
on each other would be a string of pearls on a topic branch in
the simplest case, or a handful of topic branches that
occasionally merge with each other if you want to get fancier.
Cherry-picking from a DAG of the latter kind with your rev-list
piped to tac is no different than cherry-picking from a simple
straight line of the former kind, isn't it?

> - One of the places where we currently uses series files
>   (patch-scripts && quilt), and heavy cherry picking is for patch
>   aging.  That is letting patches sit in a testing branch for 
>   a while so people have a chance to test and look at them.

I agree that patch aging and updating does not mesh well with
how git inherently works, as git regards commits immutable
objects.  Even then, I use my "pu" branch (and topics that
hasn't merged to "next" but in "pu") pretty much as patch aging
area and I regularly do "git commit --amend" to update them.
This however is cumbersome with core git tools alone, and I
suspect is better done with StGIT.

> If we create a meta data branch with just the series file
> we can remove the risk of loosing things, as we always
> have a path back to the old history if we want it.

I am not sure about that.  What does the series file contain,
and what other things the meta data branch contain?  If you are
listing commit SHA1 in the series file, you _do_ have the risk
of losing things -- git-fsck-objects needs to look at such blob
object and consider that as the root of reachability chain; to
me that seems too specialized hack.

I have a feeling that I really should study how well StGIT does
things before talking about this further.  It may suit your
needs perfectly.  What do you feel is lacking in StGIT that you
need?

Re: A series file for git?

[Eric W. Biederman]

Junio C Hamano <junkio@cox.net> writes:

> ebiederm@xmission.com (Eric W. Biederman) writes:
>
>> I was using:
>> 	git-rev-list $revargs | tac > list
>> 	for sha1 in $(cat list); do git-cherry-pick -r $sha1 ; done
>>...
>> - Keeping patches in git and just remembering their sha1 is nice
>>   but it has the downside that it can be really easy to loose
>>   the sha1, and thus the patch.  So some sort of history mechanism
>>   so you can get back to where you were would be nice.
>
> Actually, the $revargs above is composed of your branch names
> (e.g. "^master this-topic that-topic"), so as long as you do not
> lose these branches they are protected.

Right but typically I have something that looks like.
"git-rev-list --pretty=oneline 2.6.17-rc6-mm2..HEAD | tac > list"
and HEAD changes.

I could be careful and before I do each operation save a branch
name.

>> - This is a similar technique to topic branches.  However in some
>>   of the more interesting cases a topic branch can't be used because
>>   you have a whole series of little changes, that allow depend on
>>   each other.  So topic branches need not apply.
>
> Sorry I fail to see why.  A series of little changes that depend
> on each other would be a string of pearls on a topic branch in
> the simplest case, or a handful of topic branches that
> occasionally merge with each other if you want to get fancier.
> Cherry-picking from a DAG of the latter kind with your rev-list
> piped to tac is no different than cherry-picking from a simple
> straight line of the former kind, isn't it?

It is exactly a string of perls on a topic branch.  My point
is that when things are sufficiently interrelated that you
can't use more than one topic branch. 

With topic branches when you find a small fix to an existing
perl you just commit it to that branch, and it works
because each branch really is composed of a single pearl.
(At least that is my intuition).  

When you have multiple highly interrelated pearls and you
are testing you can easily put the fix for a pearl at
the end of the branch.  But before you push your changes
upstream that fix needs to be merged with the original
pearl that it fixes.  Which is fundamentally a history
editing kind of action.

>> - One of the places where we currently uses series files
>>   (patch-scripts && quilt), and heavy cherry picking is for patch
>>   aging.  That is letting patches sit in a testing branch for 
>>   a while so people have a chance to test and look at them.
>
> I agree that patch aging and updating does not mesh well with
> how git inherently works, as git regards commits immutable
> objects.  Even then, I use my "pu" branch (and topics that
> hasn't merged to "next" but in "pu") pretty much as patch aging
> area and I regularly do "git commit --amend" to update them.
> This however is cumbersome with core git tools alone, and I
> suspect is better done with StGIT.

I have a similar suspicion.  I am glad we pretty much see
the same problem.

>> If we create a meta data branch with just the series file
>> we can remove the risk of loosing things, as we always
>> have a path back to the old history if we want it.
>
> I am not sure about that.  What does the series file contain,
> and what other things the meta data branch contain?  If you are
> listing commit SHA1 in the series file, you _do_ have the risk
> of losing things -- git-fsck-objects needs to look at such blob
> object and consider that as the root of reachability chain; to
> me that seems too specialized hack.

When described that way I agree.   The best I can imagine
is to list those commits as ancestors of the current commit.
Hmm.  Or possibly I could collect up tag objects and work
with them.  In any case representing this in a non-hackish
way is my goal.

> I have a feeling that I really should study how well StGIT does
> things before talking about this further.  It may suit your
> needs perfectly.  What do you feel is lacking in StGIT that you
> need?

What I want and what I see lacking in the git and StGit is
the ability to record the history of editing the history
of a branch. 

A mundane example.  It would be nice if I rebased a branch if
I could record in some fashion what that branch was before
I rebased it.

So I am trying to figure out how to construct a meta branch
that records that kind of information about a branch.

Intuitively this feels like the history of a series file
to me.  Did I add commits?  Did I remove commits?  Did
I reorder commits?  Did I merge commits?

Andrew in his patch-scripts documentation recommends using
CVS to record this information (The documentation predates
git).  I think this is something that got lost with quilt when Andrews
patch-scripts were cleaned up and made more general.

I need to look some more but I don't think recording the history
of editing a branch is problem that has been solved in any of
the git flavors.

I will certainly look at StGit more and at the core git data
structures some more and see if I can come up with a creative
way of representing the history of branch edit operations
that will not break existing tools.

Eric

Re: A series file for git?

[Shawn Pearce]

"Eric W. Biederman" <ebiederm@xmission.com> wrote:
> Junio C Hamano <junkio@cox.net> writes:
[snip]
> > I am not sure about that.  What does the series file contain,
> > and what other things the meta data branch contain?  If you are
> > listing commit SHA1 in the series file, you _do_ have the risk
> > of losing things -- git-fsck-objects needs to look at such blob
> > object and consider that as the root of reachability chain; to
> > me that seems too specialized hack.
> 
> When described that way I agree.   The best I can imagine
> is to list those commits as ancestors of the current commit.
> Hmm.  Or possibly I could collect up tag objects and work
> with them.  In any case representing this in a non-hackish
> way is my goal.

I did this in pg.  It didn't work out very well as the GIT diff
tools (e.g. the diff in gitk) show the diff in a very odd way.
It did not work out as well as I had hoped.

> > I have a feeling that I really should study how well StGIT does
> > things before talking about this further.  It may suit your
> > needs perfectly.  What do you feel is lacking in StGIT that you
> > need?
> 
> What I want and what I see lacking in the git and StGit is
> the ability to record the history of editing the history
> of a branch. 
> 
> A mundane example.  It would be nice if I rebased a branch if
> I could record in some fashion what that branch was before
> I rebased it.

Use the new reflog code.  Its in 1.4.  Check the documentation for
git-update-ref for some details.  git-commit, git-rebase and git-am
should track history on a ref in the reflog.  However a reflog
won't anchor a commit into your repository and thus a prune may
remove it if no other commit/ref/tag mentions it.

-- 
Shawn.