From f3badaed5106a16499d0fae31a382f9047b272d7 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 11 Feb 2016 17:26:18 -0500
Subject: 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>
---
 list-objects.c | 22 +++++++++-------------
 1 file changed, 9 insertions(+), 13 deletions(-)

(limited to 'list-objects.c')

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) {
-- 
cgit 1.2.3-korg


From dc06dc880013d48f2b09c6b4295419382f3b8230 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 11 Feb 2016 17:26:44 -0500
Subject: list-objects: drop name_path entirely

In the previous commit, we left name_path as a thin wrapper
around a strbuf. This patch drops it entirely. As a result,
every show_object_fn callback needs to be adjusted. However,
none of their code needs to be changed at all, because the
only use was to pass it to path_name(), which now handles
the bare strbuf.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/pack-objects.c |  4 ++--
 builtin/rev-list.c     |  4 ++--
 list-objects.c         | 12 +++++-------
 list-objects.h         |  2 +-
 pack-bitmap-write.c    |  2 +-
 pack-bitmap.c          |  4 ++--
 reachable.c            |  2 +-
 revision.c             |  6 +++---
 revision.h             |  8 ++------
 9 files changed, 19 insertions(+), 25 deletions(-)

(limited to 'list-objects.c')

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index c067107a6a..c886258b75 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2285,7 +2285,7 @@ static void show_commit(struct commit *commit, void *data)
 }
 
 static void show_object(struct object *obj,
-			const struct name_path *path, const char *last,
+			struct strbuf *path, const char *last,
 			void *data)
 {
 	char *name = path_name(path, last);
@@ -2480,7 +2480,7 @@ static int get_object_list_from_bitmap(struct rev_info *revs)
 }
 
 static void record_recent_object(struct object *obj,
-				 const struct name_path *path,
+				 struct strbuf *path,
 				 const char *last,
 				 void *data)
 {
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index c0b4b53652..3d3a2665f1 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -178,7 +178,7 @@ static void finish_commit(struct commit *commit, void *data)
 }
 
 static void finish_object(struct object *obj,
-			  const struct name_path *path, const char *name,
+			  struct strbuf *path, const char *name,
 			  void *cb_data)
 {
 	struct rev_list_info *info = cb_data;
@@ -189,7 +189,7 @@ static void finish_object(struct object *obj,
 }
 
 static void show_object(struct object *obj,
-			const struct name_path *path, const char *component,
+			struct strbuf *path, const char *component,
 			void *cb_data)
 {
 	struct rev_list_info *info = cb_data;
diff --git a/list-objects.c b/list-objects.c
index dc46b9a2b3..0d56b50a15 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -11,7 +11,7 @@
 static void process_blob(struct rev_info *revs,
 			 struct blob *blob,
 			 show_object_fn show,
-			 struct name_path *path,
+			 struct strbuf *path,
 			 const char *name,
 			 void *cb_data)
 {
@@ -52,7 +52,7 @@ static void process_blob(struct rev_info *revs,
 static void process_gitlink(struct rev_info *revs,
 			    const unsigned char *sha1,
 			    show_object_fn show,
-			    struct name_path *path,
+			    struct strbuf *path,
 			    const char *name,
 			    void *cb_data)
 {
@@ -69,7 +69,6 @@ static void process_tree(struct rev_info *revs,
 	struct object *obj = &tree->object;
 	struct tree_desc desc;
 	struct name_entry entry;
-	struct name_path me;
 	enum interesting match = revs->diffopt.pathspec.nr == 0 ?
 		all_entries_interesting: entry_not_interesting;
 	int baselen = base->len;
@@ -87,8 +86,7 @@ static void process_tree(struct rev_info *revs,
 	}
 
 	obj->flags |= SEEN;
-	me.base = base;
-	show(obj, &me, name, cb_data);
+	show(obj, base, name, cb_data);
 
 	strbuf_addstr(base, name);
 	if (base->len)
@@ -113,12 +111,12 @@ static void process_tree(struct rev_info *revs,
 				     cb_data);
 		else if (S_ISGITLINK(entry.mode))
 			process_gitlink(revs, entry.sha1,
-					show, &me, entry.path,
+					show, base, entry.path,
 					cb_data);
 		else
 			process_blob(revs,
 				     lookup_blob(entry.sha1),
-				     show, &me, entry.path,
+				     show, base, entry.path,
 				     cb_data);
 	}
 	strbuf_setlen(base, baselen);
diff --git a/list-objects.h b/list-objects.h
index 136a1da5a6..69c4c7de6e 100644
--- a/list-objects.h
+++ b/list-objects.h
@@ -2,7 +2,7 @@
 #define LIST_OBJECTS_H
 
 typedef void (*show_commit_fn)(struct commit *, void *);
-typedef void (*show_object_fn)(struct object *, const struct name_path *, const char *, void *);
+typedef void (*show_object_fn)(struct object *, struct strbuf *, const char *, void *);
 void traverse_commit_list(struct rev_info *, show_commit_fn, show_object_fn, void *);
 
 typedef void (*show_edge_fn)(struct commit *);
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index c05d1386af..e49255df6c 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -148,7 +148,7 @@ static uint32_t find_object_pos(const unsigned char *sha1)
 	return entry->in_pack_pos;
 }
 
-static void show_object(struct object *object, const struct name_path *path,
+static void show_object(struct object *object, struct strbuf *path,
 			const char *last, void *data)
 {
 	struct bitmap *base = data;
diff --git a/pack-bitmap.c b/pack-bitmap.c
index 637770af81..d12e56511a 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -422,7 +422,7 @@ static int ext_index_add_object(struct object *object, const char *name)
 	return bitmap_pos + bitmap_git.pack->num_objects;
 }
 
-static void show_object(struct object *object, const struct name_path *path,
+static void show_object(struct object *object, struct strbuf *path,
 			const char *last, void *data)
 {
 	struct bitmap *base = data;
@@ -903,7 +903,7 @@ struct bitmap_test_data {
 };
 
 static void test_show_object(struct object *object,
-			     const struct name_path *path,
+			     struct strbuf *path,
 			     const char *last, void *data)
 {
 	struct bitmap_test_data *tdata = data;
diff --git a/reachable.c b/reachable.c
index 69fa6851da..4379d1ac79 100644
--- a/reachable.c
+++ b/reachable.c
@@ -36,7 +36,7 @@ static int add_one_ref(const char *path, const unsigned char *sha1, int flag, vo
  * The traversal will have already marked us as SEEN, so we
  * only need to handle any progress reporting here.
  */
-static void mark_object(struct object *obj, const struct name_path *path,
+static void mark_object(struct object *obj, struct strbuf *path,
 			const char *name, void *data)
 {
 	update_progress(data);
diff --git a/revision.c b/revision.c
index f8c30341ed..1ff6709d4b 100644
--- a/revision.c
+++ b/revision.c
@@ -21,17 +21,17 @@
 
 volatile show_early_output_fn_t show_early_output;
 
-char *path_name(const struct name_path *path, const char *name)
+char *path_name(struct strbuf *path, const char *name)
 {
 	struct strbuf ret = STRBUF_INIT;
 	if (path)
-		strbuf_addbuf(&ret, path->base);
+		strbuf_addbuf(&ret, path);
 	strbuf_addstr(&ret, name);
 	return strbuf_detach(&ret, NULL);
 }
 
 void show_object_with_name(FILE *out, struct object *obj,
-			   const struct name_path *path, const char *component)
+			   struct strbuf *path, const char *component)
 {
 	char *name = path_name(path, component);
 	char *p;
diff --git a/revision.h b/revision.h
index 5e3c47cb48..3a4cf9e61b 100644
--- a/revision.h
+++ b/revision.h
@@ -256,14 +256,10 @@ extern void put_revision_mark(const struct rev_info *revs,
 extern void mark_parents_uninteresting(struct commit *commit);
 extern void mark_tree_uninteresting(struct tree *tree);
 
-struct name_path {
-	struct strbuf *base;
-};
-
-char *path_name(const struct name_path *path, const char *name);
+char *path_name(struct strbuf *path, const char *name);
 
 extern void show_object_with_name(FILE *, struct object *,
-				  const struct name_path *, const char *);
+				  struct strbuf *, const char *);
 
 extern void add_pending_object(struct rev_info *revs,
 			       struct object *obj, const char *name);
-- 
cgit 1.2.3-korg


From 2824e1841b99393d2469c495253d547c643bd8f1 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 11 Feb 2016 17:28:36 -0500
Subject: list-objects: pass full pathname to callbacks

When we find a blob at "a/b/c", we currently pass this to
our show_object_fn callbacks as two components: "a/b/" and
"c". Callbacks which want the full value then call
path_name(), which concatenates the two. But this is an
inefficient interface; the path is a strbuf, and we could
simply append "c" to it temporarily, then roll back the
length, without creating a new copy.

So we could improve this by teaching the callsites of
path_name() this trick (and there are only 3). But we can
also notice that no callback actually cares about the
broken-down representation, and simply pass each callback
the full path "a/b/c" as a string. The callback code becomes
even simpler, then, as we do not have to worry about freeing
an allocated buffer, nor rolling back our modification to
the strbuf.

This is theoretically less efficient, as some callbacks
would not bother to format the final path component. But in
practice this is not measurable. Since we use the same
strbuf over and over, our work to grow it is amortized, and
we really only pay to memcpy a few bytes.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/pack-objects.c | 15 ++-------------
 builtin/rev-list.c     | 12 ++++--------
 list-objects.c         | 14 +++++++++-----
 list-objects.h         |  2 +-
 pack-bitmap-write.c    |  3 +--
 pack-bitmap.c          | 13 ++++---------
 reachable.c            |  5 ++---
 revision.c             | 17 ++---------------
 revision.h             |  3 +--
 9 files changed, 26 insertions(+), 58 deletions(-)

(limited to 'list-objects.c')

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index c886258b75..4af92f113c 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2284,21 +2284,11 @@ static void show_commit(struct commit *commit, void *data)
 		index_commit_for_bitmap(commit);
 }
 
-static void show_object(struct object *obj,
-			struct strbuf *path, const char *last,
-			void *data)
+static void show_object(struct object *obj, const char *name, void *data)
 {
-	char *name = path_name(path, last);
-
 	add_preferred_base_object(name);
 	add_object_entry(obj->sha1, obj->type, name, 0);
 	obj->flags |= OBJECT_ADDED;
-
-	/*
-	 * We will have generated the hash from the name,
-	 * but not saved a pointer to it - we can free it
-	 */
-	free((char *)name);
 }
 
 static void show_edge(struct commit *commit)
@@ -2480,8 +2470,7 @@ static int get_object_list_from_bitmap(struct rev_info *revs)
 }
 
 static void record_recent_object(struct object *obj,
-				 struct strbuf *path,
-				 const char *last,
+				 const char *name,
 				 void *data)
 {
 	sha1_array_append(&recent_objects, obj->sha1);
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index 3d3a2665f1..7ae255862a 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -177,9 +177,7 @@ static void finish_commit(struct commit *commit, void *data)
 	free_commit_buffer(commit);
 }
 
-static void finish_object(struct object *obj,
-			  struct strbuf *path, const char *name,
-			  void *cb_data)
+static void finish_object(struct object *obj, const char *name, void *cb_data)
 {
 	struct rev_list_info *info = cb_data;
 	if (obj->type == OBJ_BLOB && !has_sha1_file(obj->sha1))
@@ -188,15 +186,13 @@ static void finish_object(struct object *obj,
 		parse_object(obj->sha1);
 }
 
-static void show_object(struct object *obj,
-			struct strbuf *path, const char *component,
-			void *cb_data)
+static void show_object(struct object *obj, const char *name, void *cb_data)
 {
 	struct rev_list_info *info = cb_data;
-	finish_object(obj, path, component, cb_data);
+	finish_object(obj, name, cb_data);
 	if (info->flags & REV_LIST_QUIET)
 		return;
-	show_object_with_name(stdout, obj, path, component);
+	show_object_with_name(stdout, obj, name);
 }
 
 static void show_edge(struct commit *commit)
diff --git a/list-objects.c b/list-objects.c
index 0d56b50a15..37d0d10ab2 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -16,6 +16,7 @@ static void process_blob(struct rev_info *revs,
 			 void *cb_data)
 {
 	struct object *obj = &blob->object;
+	size_t pathlen;
 
 	if (!revs->blob_objects)
 		return;
@@ -24,7 +25,11 @@ static void process_blob(struct rev_info *revs,
 	if (obj->flags & (UNINTERESTING | SEEN))
 		return;
 	obj->flags |= SEEN;
-	show(obj, path, name, cb_data);
+
+	pathlen = path->len;
+	strbuf_addstr(path, name);
+	show(obj, path->buf, cb_data);
+	strbuf_setlen(path, pathlen);
 }
 
 /*
@@ -86,9 +91,8 @@ static void process_tree(struct rev_info *revs,
 	}
 
 	obj->flags |= SEEN;
-	show(obj, base, name, cb_data);
-
 	strbuf_addstr(base, name);
+	show(obj, base->buf, cb_data);
 	if (base->len)
 		strbuf_addch(base, '/');
 
@@ -207,7 +211,7 @@ void traverse_commit_list(struct rev_info *revs,
 			continue;
 		if (obj->type == OBJ_TAG) {
 			obj->flags |= SEEN;
-			show_object(obj, NULL, name, data);
+			show_object(obj, name, data);
 			continue;
 		}
 		if (!path)
@@ -219,7 +223,7 @@ void traverse_commit_list(struct rev_info *revs,
 		}
 		if (obj->type == OBJ_BLOB) {
 			process_blob(revs, (struct blob *)obj, show_object,
-				     NULL, path, data);
+				     &base, path, data);
 			continue;
 		}
 		die("unknown pending object %s (%s)",
diff --git a/list-objects.h b/list-objects.h
index 69c4c7de6e..0cebf8585c 100644
--- a/list-objects.h
+++ b/list-objects.h
@@ -2,7 +2,7 @@
 #define LIST_OBJECTS_H
 
 typedef void (*show_commit_fn)(struct commit *, void *);
-typedef void (*show_object_fn)(struct object *, struct strbuf *, const char *, void *);
+typedef void (*show_object_fn)(struct object *, const char *, void *);
 void traverse_commit_list(struct rev_info *, show_commit_fn, show_object_fn, void *);
 
 typedef void (*show_edge_fn)(struct commit *);
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index e49255df6c..b2f6cb537c 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -148,8 +148,7 @@ static uint32_t find_object_pos(const unsigned char *sha1)
 	return entry->in_pack_pos;
 }
 
-static void show_object(struct object *object, struct strbuf *path,
-			const char *last, void *data)
+static void show_object(struct object *object, const char *name, void *data)
 {
 	struct bitmap *base = data;
 	bitmap_set(base, find_object_pos(object->sha1));
diff --git a/pack-bitmap.c b/pack-bitmap.c
index d12e56511a..aee7acf392 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c
@@ -422,19 +422,15 @@ static int ext_index_add_object(struct object *object, const char *name)
 	return bitmap_pos + bitmap_git.pack->num_objects;
 }
 
-static void show_object(struct object *object, struct strbuf *path,
-			const char *last, void *data)
+static void show_object(struct object *object, const char *name, void *data)
 {
 	struct bitmap *base = data;
 	int bitmap_pos;
 
 	bitmap_pos = bitmap_position(object->sha1);
 
-	if (bitmap_pos < 0) {
-		char *name = path_name(path, last);
+	if (bitmap_pos < 0)
 		bitmap_pos = ext_index_add_object(object, name);
-		free(name);
-	}
 
 	bitmap_set(base, bitmap_pos);
 }
@@ -902,9 +898,8 @@ struct bitmap_test_data {
 	size_t seen;
 };
 
-static void test_show_object(struct object *object,
-			     struct strbuf *path,
-			     const char *last, void *data)
+static void test_show_object(struct object *object, const char *name,
+			     void *data)
 {
 	struct bitmap_test_data *tdata = data;
 	int bitmap_pos;
diff --git a/reachable.c b/reachable.c
index 4379d1ac79..9b0295469f 100644
--- a/reachable.c
+++ b/reachable.c
@@ -36,15 +36,14 @@ static int add_one_ref(const char *path, const unsigned char *sha1, int flag, vo
  * The traversal will have already marked us as SEEN, so we
  * only need to handle any progress reporting here.
  */
-static void mark_object(struct object *obj, struct strbuf *path,
-			const char *name, void *data)
+static void mark_object(struct object *obj, const char *name, void *data)
 {
 	update_progress(data);
 }
 
 static void mark_commit(struct commit *c, void *data)
 {
-	mark_object(&c->object, NULL, NULL, data);
+	mark_object(&c->object, NULL, data);
 }
 
 struct recent_data {
diff --git a/revision.c b/revision.c
index 1ff6709d4b..871812db2a 100644
--- a/revision.c
+++ b/revision.c
@@ -21,27 +21,14 @@
 
 volatile show_early_output_fn_t show_early_output;
 
-char *path_name(struct strbuf *path, const char *name)
+void show_object_with_name(FILE *out, struct object *obj, const char *name)
 {
-	struct strbuf ret = STRBUF_INIT;
-	if (path)
-		strbuf_addbuf(&ret, path);
-	strbuf_addstr(&ret, name);
-	return strbuf_detach(&ret, NULL);
-}
-
-void show_object_with_name(FILE *out, struct object *obj,
-			   struct strbuf *path, const char *component)
-{
-	char *name = path_name(path, component);
-	char *p;
+	const char *p;
 
 	fprintf(out, "%s ", sha1_to_hex(obj->sha1));
 	for (p = name; *p && *p != '\n'; p++)
 		fputc(*p, out);
 	fputc('\n', out);
-
-	free(name);
 }
 
 static void mark_blob_uninteresting(struct blob *blob)
diff --git a/revision.h b/revision.h
index 3a4cf9e61b..1b58aacc03 100644
--- a/revision.h
+++ b/revision.h
@@ -258,8 +258,7 @@ extern void mark_tree_uninteresting(struct tree *tree);
 
 char *path_name(struct strbuf *path, const char *name);
 
-extern void show_object_with_name(FILE *, struct object *,
-				  struct strbuf *, const char *);
+extern void show_object_with_name(FILE *, struct object *, const char *);
 
 extern void add_pending_object(struct rev_info *revs,
 			       struct object *obj, const char *name);
-- 
cgit 1.2.3-korg