[PATCH 1/3] use struct sha1_array in diff_tree_combined()

[PATCH 1/3] use struct sha1_array in diff_tree_combined()

[René Scharfe]

Maintaining an array of hashes is easier using sha1_array than
open-coding it.  This patch also fixes a leak of the SHA1 array
in  diff_tree_combined_merge().

---
 builtin/diff.c |   12 ++++++------
 combine-diff.c |   34 +++++++++++++---------------------
 diff.h         |    3 ++-
 submodule.c    |   14 +++++---------
 4 files changed, 26 insertions(+), 37 deletions(-)

diff --git a/builtin/diff.c b/builtin/diff.c
index 0fe638f..387afa7 100644
--- a/builtin/diff.c
+++ b/builtin/diff.c
@@ -14,6 +14,7 @@
 #include "log-tree.h"
 #include "builtin.h"
 #include "submodule.h"
+#include "sha1-array.h"
 
 struct blobinfo {
 	unsigned char sha1[20];
@@ -169,7 +170,7 @@ static int builtin_diff_combined(struct rev_info *revs,
 				 struct object_array_entry *ent,
 				 int ents)
 {
-	const unsigned char (*parent)[20];
+	struct sha1_array parents = SHA1_ARRAY_INIT;
 	int i;
 
 	if (argc > 1)
@@ -177,12 +178,11 @@ static int builtin_diff_combined(struct rev_info *revs,
 
 	if (!revs->dense_combined_merges && !revs->combine_merges)
 		revs->dense_combined_merges = revs->combine_merges = 1;
-	parent = xmalloc(ents * sizeof(*parent));
-	for (i = 0; i < ents; i++)
-		hashcpy((unsigned char *)(parent + i), ent[i].item->sha1);
-	diff_tree_combined(parent[0], parent + 1, ents - 1,
+	for (i = 1; i < ents; i++)
+		sha1_array_append(&parents, ent[i].item->sha1);
+	diff_tree_combined(ent[0].item->sha1, &parents,
 			   revs->dense_combined_merges, revs);
-	free((void *)parent);
+	sha1_array_clear(&parents);
 	return 0;
 }
 
diff --git a/combine-diff.c b/combine-diff.c
index 214014d..cfe6230 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -8,6 +8,7 @@
 #include "log-tree.h"
 #include "refs.h"
 #include "userdiff.h"
+#include "sha1-array.h"
 
 static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)
 {
@@ -1116,15 +1117,14 @@ static void handle_combined_callback(struct diff_options *opt,
 }
 
 void diff_tree_combined(const unsigned char *sha1,
-			const unsigned char parent[][20],
-			int num_parent,
+			const struct sha1_array *parents,
 			int dense,
 			struct rev_info *rev)
 {
 	struct diff_options *opt = &rev->diffopt;
 	struct diff_options diffopts;
 	struct combine_diff_path *p, *paths = NULL;
-	int i, num_paths, needsep, show_log_first;
+	int i, num_paths, needsep, show_log_first, num_parent = parents->nr;
 
 	diffopts = *opt;
 	diffopts.output_format = DIFF_FORMAT_NO_OUTPUT;
@@ -1144,7 +1144,7 @@ void diff_tree_combined(const unsigned char *sha1,
 			diffopts.output_format = stat_opt;
 		else
 			diffopts.output_format = DIFF_FORMAT_NO_OUTPUT;
-		diff_tree_sha1(parent[i], sha1, "", &diffopts);
+		diff_tree_sha1(parents->sha1[i], sha1, "", &diffopts);
 		diffcore_std(&diffopts);
 		paths = intersect_paths(paths, i, num_parent);
 
@@ -1199,22 +1199,14 @@ void diff_tree_combined(const unsigned char *sha1,
 void diff_tree_combined_merge(const unsigned char *sha1,
 			     int dense, struct rev_info *rev)
 {
-	int num_parent;
-	const unsigned char (*parent)[20];
 	struct commit *commit = lookup_commit(sha1);
-	struct commit_list *parents;
-
-	/* count parents */
-	for (parents = commit->parents, num_parent = 0;
-	     parents;
-	     parents = parents->next, num_parent++)
-		; /* nothing */
-
-	parent = xmalloc(num_parent * sizeof(*parent));
-	for (parents = commit->parents, num_parent = 0;
-	     parents;
-	     parents = parents->next, num_parent++)
-		hashcpy((unsigned char *)(parent + num_parent),
-			parents->item->object.sha1);
-	diff_tree_combined(sha1, parent, num_parent, dense, rev);
+	struct commit_list *parent = commit->parents;
+	struct sha1_array parents = SHA1_ARRAY_INIT;
+
+	while (parent) {
+		sha1_array_append(&parents, parent->item->object.sha1);
+		parent = parent->next;
+	}
+	diff_tree_combined(sha1, &parents, dense, rev);
+	sha1_array_clear(&parents);
 }
diff --git a/diff.h b/diff.h
index 0c51724..96085cb 100644
--- a/diff.h
+++ b/diff.h
@@ -12,6 +12,7 @@ struct diff_queue_struct;
 struct strbuf;
 struct diff_filespec;
 struct userdiff_driver;
+struct sha1_array;
 
 typedef void (*change_fn_t)(struct diff_options *options,
 		 unsigned old_mode, unsigned new_mode,
@@ -195,7 +196,7 @@ struct combine_diff_path {
 extern void show_combined_diff(struct combine_diff_path *elem, int num_parent,
 			      int dense, struct rev_info *);
 
-extern void diff_tree_combined(const unsigned char *sha1, const unsigned char parent[][20], int num_parent, int dense, struct rev_info *rev);
+extern void diff_tree_combined(const unsigned char *sha1, const struct sha1_array *parents, int dense, struct rev_info *rev);
 
 extern void diff_tree_combined_merge(const unsigned char *sha1, int, struct rev_info *);
 
diff --git a/submodule.c b/submodule.c
index 68c1ba9..788d532 100644
--- a/submodule.c
+++ b/submodule.c
@@ -373,15 +373,11 @@ static void collect_submodules_from_diff(struct diff_queue_struct *q,
 
 static void commit_need_pushing(struct commit *commit, struct commit_list *parent, int *needs_pushing)
 {
-	const unsigned char (*parents)[20];
-	unsigned int i, n;
+	struct sha1_array parents = SHA1_ARRAY_INIT;
 	struct rev_info rev;
 
-	n = commit_list_count(parent);
-	parents = xmalloc(n * sizeof(*parents));
-
-	for (i = 0; i < n; i++) {
-		hashcpy((unsigned char *)(parents + i), parent->item->object.sha1);
+	while (parent) {
+		sha1_array_append(&parents, parent->item->object.sha1);
 		parent = parent->next;
 	}
 
@@ -389,9 +385,9 @@ static void commit_need_pushing(struct commit *commit, struct commit_list *paren
 	rev.diffopt.output_format |= DIFF_FORMAT_CALLBACK;
 	rev.diffopt.format_callback = collect_submodules_from_diff;
 	rev.diffopt.format_callback_data = needs_pushing;
-	diff_tree_combined(commit->object.sha1, parents, n, 1, &rev);
+	diff_tree_combined(commit->object.sha1, &parents, 1, &rev);
 
-	free((void *)parents);
+	sha1_array_clear(&parents);
 }
 
 int check_submodule_needs_pushing(unsigned char new_sha1[20], const char *remotes_name)
-- 
1.7.8

[PATCH 2/3] pass struct commit to diff_tree_combined_merge()

[René Scharfe]

Instead of passing the hash of a commit and then searching that
same commit in the single caller, simply pass the commit directly.

---
 combine-diff.c |    7 +++----
 diff.h         |    3 ++-
 log-tree.c     |    4 +---
 3 files changed, 6 insertions(+), 8 deletions(-)

diff --git a/combine-diff.c b/combine-diff.c
index cfe6230..a2e8dcf 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -1196,10 +1196,9 @@ void diff_tree_combined(const unsigned char *sha1,
 	}
 }
 
-void diff_tree_combined_merge(const unsigned char *sha1,
-			     int dense, struct rev_info *rev)
+void diff_tree_combined_merge(const struct commit *commit, int dense,
+			      struct rev_info *rev)
 {
-	struct commit *commit = lookup_commit(sha1);
 	struct commit_list *parent = commit->parents;
 	struct sha1_array parents = SHA1_ARRAY_INIT;
 
@@ -1207,6 +1206,6 @@ void diff_tree_combined_merge(const unsigned char *sha1,
 		sha1_array_append(&parents, parent->item->object.sha1);
 		parent = parent->next;
 	}
-	diff_tree_combined(sha1, &parents, dense, rev);
+	diff_tree_combined(commit->object.sha1, &parents, dense, rev);
 	sha1_array_clear(&parents);
 }
diff --git a/diff.h b/diff.h
index 96085cb..ae71f4c 100644
--- a/diff.h
+++ b/diff.h
@@ -13,6 +13,7 @@ struct strbuf;
 struct diff_filespec;
 struct userdiff_driver;
 struct sha1_array;
+struct commit;
 
 typedef void (*change_fn_t)(struct diff_options *options,
 		 unsigned old_mode, unsigned new_mode,
@@ -198,7 +199,7 @@ extern void show_combined_diff(struct combine_diff_path *elem, int num_parent,
 
 extern void diff_tree_combined(const unsigned char *sha1, const struct sha1_array *parents, int dense, struct rev_info *rev);
 
-extern void diff_tree_combined_merge(const unsigned char *sha1, int, struct rev_info *);
+extern void diff_tree_combined_merge(const struct commit *commit, int dense, struct rev_info *rev);
 
 void diff_set_mnemonic_prefix(struct diff_options *options, const char *a, const char *b);
 
diff --git a/log-tree.c b/log-tree.c
index e7694a3..319bd31 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -599,9 +599,7 @@ int log_tree_diff_flush(struct rev_info *opt)
 
 static int do_diff_combined(struct rev_info *opt, struct commit *commit)
 {
-	unsigned const char *sha1 = commit->object.sha1;
-
-	diff_tree_combined_merge(sha1, opt->dense_combined_merges, opt);
+	diff_tree_combined_merge(commit, opt->dense_combined_merges, opt);
 	return !opt->loginfo;
 }
 
-- 
1.7.8

[PATCH 3/3] submodule: use diff_tree_combined_merge() instead of diff_tree_combined()

[René Scharfe]

Use diff_tree_combined_merge() instead of open-coding it.

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
---
 submodule.c |   14 +++-----------
 1 files changed, 3 insertions(+), 11 deletions(-)

diff --git a/submodule.c b/submodule.c
index 788d532..9a28060 100644
--- a/submodule.c
+++ b/submodule.c
@@ -371,23 +371,15 @@ static void collect_submodules_from_diff(struct diff_queue_struct *q,
 }
 
 
-static void commit_need_pushing(struct commit *commit, struct commit_list *parent, int *needs_pushing)
+static void commit_need_pushing(struct commit *commit, int *needs_pushing)
 {
-	struct sha1_array parents = SHA1_ARRAY_INIT;
 	struct rev_info rev;
 
-	while (parent) {
-		sha1_array_append(&parents, parent->item->object.sha1);
-		parent = parent->next;
-	}
-
 	init_revisions(&rev, NULL);
 	rev.diffopt.output_format |= DIFF_FORMAT_CALLBACK;
 	rev.diffopt.format_callback = collect_submodules_from_diff;
 	rev.diffopt.format_callback_data = needs_pushing;
-	diff_tree_combined(commit->object.sha1, &parents, 1, &rev);
-
-	sha1_array_clear(&parents);
+	diff_tree_combined_merge(commit, 1, &rev);
 }
 
 int check_submodule_needs_pushing(unsigned char new_sha1[20], const char *remotes_name)
@@ -410,7 +402,7 @@ int check_submodule_needs_pushing(unsigned char new_sha1[20], const char *remote
 		die("revision walk setup failed");
 
 	while ((commit = get_revision(&rev)) && !needs_pushing)
-		commit_need_pushing(commit, commit->parents, &needs_pushing);
+		commit_need_pushing(commit, &needs_pushing);
 
 	free(sha1_copy);
 	strbuf_release(&remotes_arg);
-- 
1.7.8

Re: [PATCH 1/3] use struct sha1_array in diff_tree_combined()

[René Scharfe]

Am 17.12.2011 11:15, schrieb René Scharfe:
> Maintaining an array of hashes is easier using sha1_array than
> open-coding it.  This patch also fixes a leak of the SHA1 array
> in  diff_tree_combined_merge().
>
> ---

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>

Re: [PATCH 2/3] pass struct commit to diff_tree_combined_merge()

[René Scharfe]

Am 17.12.2011 11:20, schrieb René Scharfe:
> Instead of passing the hash of a commit and then searching that
> same commit in the single caller, simply pass the commit directly.
>
> ---

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>

Ugh.  Forgetting it twice is stupid..

Re: [PATCH 1/3] use struct sha1_array in diff_tree_combined()

[Jeff King]

On Sat, Dec 17, 2011 at 11:15:48AM +0100, René Scharfe wrote:

> Maintaining an array of hashes is easier using sha1_array than
> open-coding it.  This patch also fixes a leak of the SHA1 array
> in  diff_tree_combined_merge().
> 
> ---
>  builtin/diff.c |   12 ++++++------
>  combine-diff.c |   34 +++++++++++++---------------------
>  diff.h         |    3 ++-
>  submodule.c    |   14 +++++---------
>  4 files changed, 26 insertions(+), 37 deletions(-)

Yay. When I refactored sha1_array, I hoped there would be other users,
but I hadn't actually converted any yet. Good to know it is paying off.

> -	parent = xmalloc(ents * sizeof(*parent));
> -	for (i = 0; i < ents; i++)
> -		hashcpy((unsigned char *)(parent + i), ent[i].item->sha1);
> -	diff_tree_combined(parent[0], parent + 1, ents - 1,
> +	for (i = 1; i < ents; i++)
> +		sha1_array_append(&parents, ent[i].item->sha1);
> +	diff_tree_combined(ent[0].item->sha1, &parents,
>  			   revs->dense_combined_merges, revs);
> -	free((void *)parent);
> +	sha1_array_clear(&parents);

The original code is slightly more efficient, as it is able to use a
single malloc (because it knows the number of entries ahead of time).
It probably doesn't make a difference, but we could also add a
sha1_array_grow() for this case.

I think it could be used in all three spots you converted in this patch.

-Peff

Re: [PATCH 1/3] use struct sha1_array in diff_tree_combined()

[René Scharfe]

Am 17.12.2011 11:53, schrieb Jeff King:
>> -	parent = xmalloc(ents * sizeof(*parent));
>> -	for (i = 0; i<  ents; i++)
>> -		hashcpy((unsigned char *)(parent + i), ent[i].item->sha1);
>> -	diff_tree_combined(parent[0], parent + 1, ents - 1,
>> +	for (i = 1; i<  ents; i++)
>> +		sha1_array_append(&parents, ent[i].item->sha1);
>> +	diff_tree_combined(ent[0].item->sha1,&parents,
>>   			   revs->dense_combined_merges, revs);
>> -	free((void *)parent);
>> +	sha1_array_clear(&parents);
>
> The original code is slightly more efficient, as it is able to use a
> single malloc (because it knows the number of entries ahead of time).
> It probably doesn't make a difference, but we could also add a
> sha1_array_grow() for this case.
>
> I think it could be used in all three spots you converted in this patch.

We coulddo that, yes.  In the case above we have the number already, in 
the other cases we'd have to count.

But I don't think it's worth it here.  ALLOC_GROW gives us 24 entries 
initially, which should be enough in most cases -- I'm not sure I want 
to see combined diff of that many tree.  And 24 times 20 bytes is small 
enough to not cause any memory allocation issues.

Taking out the counting and not having to worry about the number of 
items is a feature in my book.  Simple timings before and after the 
patch didn't show any significant difference.

René

Re: [PATCH 1/3] use struct sha1_array in diff_tree_combined()

[Jeff King]

On Sat, Dec 17, 2011 at 12:16:32PM +0100, René Scharfe wrote:

> >The original code is slightly more efficient, as it is able to use a
> >single malloc (because it knows the number of entries ahead of time).
> >It probably doesn't make a difference, but we could also add a
> >sha1_array_grow() for this case.
> [...]
> We coulddo that, yes.  In the case above we have the number already,
> in the other cases we'd have to count.
> 
> But I don't think it's worth it here.  ALLOC_GROW gives us 24 entries
> initially, which should be enough in most cases -- I'm not sure I
> want to see combined diff of that many tree.  And 24 times 20 bytes
> is small enough to not cause any memory allocation issues.

You're right.

I was blindly looking at the conversion without thinking about the
context. Of course if you have just a few items, it's going to be
irrelevant (my initial refactoring of sha1_array was to help speed up a
hundreds-of-thousands of sha1s case, so I think that put me in the
mindset of a large list).

Sorry for the noise.

-Peff