list-objects: convert name_path to a strbuf

The "struct name_path" data is examined in only two places:
we generate it in process_tree(), and we convert it to a
single string in path_name(). Everyone else just passes it
through to those functions.

We can further note that process_tree() already keeps a
single strbuf with the leading tree path, for use with
tree_entry_interesting().

Instead of building a separate name_path linked list, let's
just use the one we already build in "base". This reduces
the amount of code (especially tricky code in path_name()
which did not check for integer overflows caused by deep
or large pathnames).

It is also more efficient in some instances.  Any time we
were using tree_entry_interesting, we were building up the
strbuf anyway, so this is an immediate and obvious win
there. In cases where we were not, we trade off storing
"pathname/" in a strbuf on the heap for each level of the
path, instead of two pointers and an int on the stack (with
one pointer into the tree object). On a 64-bit system, the
latter is 20 bytes; so if path components are less than that
on average, this has lower peak memory usage.  In practice
it probably doesn't matter either way; we are already
holding in memory all of the tree objects leading up to each
pathname, and for normal-depth pathnames, we are only
talking about hundreds of bytes.

This patch leaves "struct name_path" as a thin wrapper
around the strbuf, to avoid disrupting callbacks. We should
fix them, but leaving it out makes this diff easier to view.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

3 files changed, 15 insertions, 36 deletions

diff --git a/list-objects.c b/list-objects.c
index 41736d2372..dc46b9a2b3 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -62,7 +62,6 @@ static void process_gitlink(struct rev_info *revs,
 static void process_tree(struct rev_info *revs,
 			 struct tree *tree,
 			 show_object_fn show,
-			 struct name_path *path,
 			 struct strbuf *base,
 			 const char *name,
 			 void *cb_data)
@@ -86,17 +85,14 @@ static void process_tree(struct rev_info *revs,
 			return;
 		die("bad tree object %s", sha1_to_hex(obj->sha1));
 	}
+
 	obj->flags |= SEEN;
-	show(obj, path, name, cb_data);
-	me.up = path;
-	me.elem = name;
-	me.elem_len = strlen(name);
-
-	if (!match) {
-		strbuf_addstr(base, name);
-		if (base->len)
-			strbuf_addch(base, '/');
-	}
+	me.base = base;
+	show(obj, &me, name, cb_data);
+
+	strbuf_addstr(base, name);
+	if (base->len)
+		strbuf_addch(base, '/');
 
 	init_tree_desc(&desc, tree->buffer, tree->size);
 
@@ -113,7 +109,7 @@ static void process_tree(struct rev_info *revs,
 		if (S_ISDIR(entry.mode))
 			process_tree(revs,
 				     lookup_tree(entry.sha1),
-				     show, &me, base, entry.path,
+				     show, base, entry.path,
 				     cb_data);
 		else if (S_ISGITLINK(entry.mode))
 			process_gitlink(revs, entry.sha1,
@@ -220,7 +216,7 @@ void traverse_commit_list(struct rev_info *revs,
 			path = "";
 		if (obj->type == OBJ_TREE) {
 			process_tree(revs, (struct tree *)obj, show_object,
-				     NULL, &base, path, data);
+				     &base, path, data);
 			continue;
 		}
 		if (obj->type == OBJ_BLOB) {
diff --git a/revision.c b/revision.c
index cf544b6e96..f8c30341ed 100644
--- a/revision.c
+++ b/revision.c
@@ -23,26 +23,11 @@ volatile show_early_output_fn_t show_early_output;
 
 char *path_name(const struct name_path *path, const char *name)
 {
-	const struct name_path *p;
-	char *n, *m;
-	int nlen = strlen(name);
-	int len = nlen + 1;
-
-	for (p = path; p; p = p->up) {
-		if (p->elem_len)
-			len += p->elem_len + 1;
-	}
-	n = xmalloc(len);
-	m = n + len - (nlen + 1);
-	strcpy(m, name);
-	for (p = path; p; p = p->up) {
-		if (p->elem_len) {
-			m -= p->elem_len + 1;
-			memcpy(m, p->elem, p->elem_len);
-			m[p->elem_len] = '/';
-		}
-	}
-	return n;
+	struct strbuf ret = STRBUF_INIT;
+	if (path)
+		strbuf_addbuf(&ret, path->base);
+	strbuf_addstr(&ret, name);
+	return strbuf_detach(&ret, NULL);
 }
 
 void show_object_with_name(FILE *out, struct object *obj,
diff --git a/revision.h b/revision.h
index 0ea8b4e255..5e3c47cb48 100644
--- a/revision.h
+++ b/revision.h
@@ -257,9 +257,7 @@ extern void mark_parents_uninteresting(struct commit *commit);
 extern void mark_tree_uninteresting(struct tree *tree);
 
 struct name_path {
-	struct name_path *up;
-	int elem_len;
-	const char *elem;
+	struct strbuf *base;
 };
 
 char *path_name(const struct name_path *path, const char *name);