{"thread":{"id":"29194","subject":"[PATCH 1/3] use struct sha1_array in diff_tree_combined()","startedAt":"2011-12-17T10:15:48Z","lastAt":"2011-12-17T11:19:20Z","messageCount":8,"participants":["René Scharfe","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"181384","messageId":"4EEC6BD4.4040302@lsrfire.ath.cx","threadId":"29194","inReplyTo":null,"subject":"[PATCH 1/3] use struct sha1_array in diff_tree_combined()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-17T10:15:48Z","receivedAt":"2011-12-17T10:15:48Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Maintaining an array of hashes is easier using sha1_array than\nopen-coding it.  This patch also fixes a leak of the SHA1 array\nin  diff_tree_combined_merge().\n\n---\n builtin/diff.c |   12 ++++++------\n combine-diff.c |   34 +++++++++++++---------------------\n diff.h         |    3 ++-\n submodule.c    |   14 +++++---------\n 4 files changed, 26 insertions(+), 37 deletions(-)\n\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex 0fe638f..387afa7 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -14,6 +14,7 @@\n #include \"log-tree.h\"\n #include \"builtin.h\"\n #include \"submodule.h\"\n+#include \"sha1-array.h\"\n \n struct blobinfo {\n \tunsigned char sha1[20];\n@@ -169,7 +170,7 @@ static int builtin_diff_combined(struct rev_info *revs,\n \t\t\t\t struct object_array_entry *ent,\n \t\t\t\t int ents)\n {\n-\tconst unsigned char (*parent)[20];\n+\tstruct sha1_array parents = SHA1_ARRAY_INIT;\n \tint i;\n \n \tif (argc > 1)\n@@ -177,12 +178,11 @@ static int builtin_diff_combined(struct rev_info *revs,\n \n \tif (!revs->dense_combined_merges && !revs->combine_merges)\n \t\trevs->dense_combined_merges = revs->combine_merges = 1;\n-\tparent = xmalloc(ents * sizeof(*parent));\n-\tfor (i = 0; i < ents; i++)\n-\t\thashcpy((unsigned char *)(parent + i), ent[i].item->sha1);\n-\tdiff_tree_combined(parent[0], parent + 1, ents - 1,\n+\tfor (i = 1; i < ents; i++)\n+\t\tsha1_array_append(&parents, ent[i].item->sha1);\n+\tdiff_tree_combined(ent[0].item->sha1, &parents,\n \t\t\t   revs->dense_combined_merges, revs);\n-\tfree((void *)parent);\n+\tsha1_array_clear(&parents);\n \treturn 0;\n }\n \ndiff --git a/combine-diff.c b/combine-diff.c\nindex 214014d..cfe6230 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -8,6 +8,7 @@\n #include \"log-tree.h\"\n #include \"refs.h\"\n #include \"userdiff.h\"\n+#include \"sha1-array.h\"\n \n static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr, int n, int num_parent)\n {\n@@ -1116,15 +1117,14 @@ static void handle_combined_callback(struct diff_options *opt,\n }\n \n void diff_tree_combined(const unsigned char *sha1,\n-\t\t\tconst unsigned char parent[][20],\n-\t\t\tint num_parent,\n+\t\t\tconst struct sha1_array *parents,\n \t\t\tint dense,\n \t\t\tstruct rev_info *rev)\n {\n \tstruct diff_options *opt = &rev->diffopt;\n \tstruct diff_options diffopts;\n \tstruct combine_diff_path *p, *paths = NULL;\n-\tint i, num_paths, needsep, show_log_first;\n+\tint i, num_paths, needsep, show_log_first, num_parent = parents->nr;\n \n \tdiffopts = *opt;\n \tdiffopts.output_format = DIFF_FORMAT_NO_OUTPUT;\n@@ -1144,7 +1144,7 @@ void diff_tree_combined(const unsigned char *sha1,\n \t\t\tdiffopts.output_format = stat_opt;\n \t\telse\n \t\t\tdiffopts.output_format = DIFF_FORMAT_NO_OUTPUT;\n-\t\tdiff_tree_sha1(parent[i], sha1, \"\", &diffopts);\n+\t\tdiff_tree_sha1(parents->sha1[i], sha1, \"\", &diffopts);\n \t\tdiffcore_std(&diffopts);\n \t\tpaths = intersect_paths(paths, i, num_parent);\n \n@@ -1199,22 +1199,14 @@ void diff_tree_combined(const unsigned char *sha1,\n void diff_tree_combined_merge(const unsigned char *sha1,\n \t\t\t     int dense, struct rev_info *rev)\n {\n-\tint num_parent;\n-\tconst unsigned char (*parent)[20];\n \tstruct commit *commit = lookup_commit(sha1);\n-\tstruct commit_list *parents;\n-\n-\t/* count parents */\n-\tfor (parents = commit->parents, num_parent = 0;\n-\t     parents;\n-\t     parents = parents->next, num_parent++)\n-\t\t; /* nothing */\n-\n-\tparent = xmalloc(num_parent * sizeof(*parent));\n-\tfor (parents = commit->parents, num_parent = 0;\n-\t     parents;\n-\t     parents = parents->next, num_parent++)\n-\t\thashcpy((unsigned char *)(parent + num_parent),\n-\t\t\tparents->item->object.sha1);\n-\tdiff_tree_combined(sha1, parent, num_parent, dense, rev);\n+\tstruct commit_list *parent = commit->parents;\n+\tstruct sha1_array parents = SHA1_ARRAY_INIT;\n+\n+\twhile (parent) {\n+\t\tsha1_array_append(&parents, parent->item->object.sha1);\n+\t\tparent = parent->next;\n+\t}\n+\tdiff_tree_combined(sha1, &parents, dense, rev);\n+\tsha1_array_clear(&parents);\n }\ndiff --git a/diff.h b/diff.h\nindex 0c51724..96085cb 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -12,6 +12,7 @@ struct diff_queue_struct;\n struct strbuf;\n struct diff_filespec;\n struct userdiff_driver;\n+struct sha1_array;\n \n typedef void (*change_fn_t)(struct diff_options *options,\n \t\t unsigned old_mode, unsigned new_mode,\n@@ -195,7 +196,7 @@ struct combine_diff_path {\n extern void show_combined_diff(struct combine_diff_path *elem, int num_parent,\n \t\t\t      int dense, struct rev_info *);\n \n-extern void diff_tree_combined(const unsigned char *sha1, const unsigned char parent[][20], int num_parent, int dense, struct rev_info *rev);\n+extern void diff_tree_combined(const unsigned char *sha1, const struct sha1_array *parents, int dense, struct rev_info *rev);\n \n extern void diff_tree_combined_merge(const unsigned char *sha1, int, struct rev_info *);\n \ndiff --git a/submodule.c b/submodule.c\nindex 68c1ba9..788d532 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -373,15 +373,11 @@ static void collect_submodules_from_diff(struct diff_queue_struct *q,\n \n static void commit_need_pushing(struct commit *commit, struct commit_list *parent, int *needs_pushing)\n {\n-\tconst unsigned char (*parents)[20];\n-\tunsigned int i, n;\n+\tstruct sha1_array parents = SHA1_ARRAY_INIT;\n \tstruct rev_info rev;\n \n-\tn = commit_list_count(parent);\n-\tparents = xmalloc(n * sizeof(*parents));\n-\n-\tfor (i = 0; i < n; i++) {\n-\t\thashcpy((unsigned char *)(parents + i), parent->item->object.sha1);\n+\twhile (parent) {\n+\t\tsha1_array_append(&parents, parent->item->object.sha1);\n \t\tparent = parent->next;\n \t}\n \n@@ -389,9 +385,9 @@ static void commit_need_pushing(struct commit *commit, struct commit_list *paren\n \trev.diffopt.output_format |= DIFF_FORMAT_CALLBACK;\n \trev.diffopt.format_callback = collect_submodules_from_diff;\n \trev.diffopt.format_callback_data = needs_pushing;\n-\tdiff_tree_combined(commit->object.sha1, parents, n, 1, &rev);\n+\tdiff_tree_combined(commit->object.sha1, &parents, 1, &rev);\n \n-\tfree((void *)parents);\n+\tsha1_array_clear(&parents);\n }\n \n int check_submodule_needs_pushing(unsigned char new_sha1[20], const char *remotes_name)\n-- \n1.7.8\n"},{"id":"181385","messageId":"4EEC6CD7.2030408@lsrfire.ath.cx","threadId":"29194","inReplyTo":"4EEC6BD4.4040302@lsrfire.ath.cx","subject":"[PATCH 2/3] pass struct commit to diff_tree_combined_merge()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-17T10:20:07Z","receivedAt":"2011-12-17T10:20:07Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Instead of passing the hash of a commit and then searching that\nsame commit in the single caller, simply pass the commit directly.\n\n---\n combine-diff.c |    7 +++----\n diff.h         |    3 ++-\n log-tree.c     |    4 +---\n 3 files changed, 6 insertions(+), 8 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex cfe6230..a2e8dcf 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -1196,10 +1196,9 @@ void diff_tree_combined(const unsigned char *sha1,\n \t}\n }\n \n-void diff_tree_combined_merge(const unsigned char *sha1,\n-\t\t\t     int dense, struct rev_info *rev)\n+void diff_tree_combined_merge(const struct commit *commit, int dense,\n+\t\t\t      struct rev_info *rev)\n {\n-\tstruct commit *commit = lookup_commit(sha1);\n \tstruct commit_list *parent = commit->parents;\n \tstruct sha1_array parents = SHA1_ARRAY_INIT;\n \n@@ -1207,6 +1206,6 @@ void diff_tree_combined_merge(const unsigned char *sha1,\n \t\tsha1_array_append(&parents, parent->item->object.sha1);\n \t\tparent = parent->next;\n \t}\n-\tdiff_tree_combined(sha1, &parents, dense, rev);\n+\tdiff_tree_combined(commit->object.sha1, &parents, dense, rev);\n \tsha1_array_clear(&parents);\n }\ndiff --git a/diff.h b/diff.h\nindex 96085cb..ae71f4c 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -13,6 +13,7 @@ struct strbuf;\n struct diff_filespec;\n struct userdiff_driver;\n struct sha1_array;\n+struct commit;\n \n typedef void (*change_fn_t)(struct diff_options *options,\n \t\t unsigned old_mode, unsigned new_mode,\n@@ -198,7 +199,7 @@ extern void show_combined_diff(struct combine_diff_path *elem, int num_parent,\n \n extern void diff_tree_combined(const unsigned char *sha1, const struct sha1_array *parents, int dense, struct rev_info *rev);\n \n-extern void diff_tree_combined_merge(const unsigned char *sha1, int, struct rev_info *);\n+extern void diff_tree_combined_merge(const struct commit *commit, int dense, struct rev_info *rev);\n \n void diff_set_mnemonic_prefix(struct diff_options *options, const char *a, const char *b);\n \ndiff --git a/log-tree.c b/log-tree.c\nindex e7694a3..319bd31 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -599,9 +599,7 @@ int log_tree_diff_flush(struct rev_info *opt)\n \n static int do_diff_combined(struct rev_info *opt, struct commit *commit)\n {\n-\tunsigned const char *sha1 = commit->object.sha1;\n-\n-\tdiff_tree_combined_merge(sha1, opt->dense_combined_merges, opt);\n+\tdiff_tree_combined_merge(commit, opt->dense_combined_merges, opt);\n \treturn !opt->loginfo;\n }\n \n-- \n1.7.8\n"},{"id":"181387","messageId":"4EEC6E87.3060204@lsrfire.ath.cx","threadId":"29194","inReplyTo":"4EEC6CD7.2030408@lsrfire.ath.cx","subject":"[PATCH 3/3] submodule: use diff_tree_combined_merge() instead of diff_tree_combined()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-17T10:27:19Z","receivedAt":"2011-12-17T10:27:19Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use diff_tree_combined_merge() instead of open-coding it.\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n---\n submodule.c |   14 +++-----------\n 1 files changed, 3 insertions(+), 11 deletions(-)\n\ndiff --git a/submodule.c b/submodule.c\nindex 788d532..9a28060 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -371,23 +371,15 @@ static void collect_submodules_from_diff(struct diff_queue_struct *q,\n }\n \n \n-static void commit_need_pushing(struct commit *commit, struct commit_list *parent, int *needs_pushing)\n+static void commit_need_pushing(struct commit *commit, int *needs_pushing)\n {\n-\tstruct sha1_array parents = SHA1_ARRAY_INIT;\n \tstruct rev_info rev;\n \n-\twhile (parent) {\n-\t\tsha1_array_append(&parents, parent->item->object.sha1);\n-\t\tparent = parent->next;\n-\t}\n-\n \tinit_revisions(&rev, NULL);\n \trev.diffopt.output_format |= DIFF_FORMAT_CALLBACK;\n \trev.diffopt.format_callback = collect_submodules_from_diff;\n \trev.diffopt.format_callback_data = needs_pushing;\n-\tdiff_tree_combined(commit->object.sha1, &parents, 1, &rev);\n-\n-\tsha1_array_clear(&parents);\n+\tdiff_tree_combined_merge(commit, 1, &rev);\n }\n \n int check_submodule_needs_pushing(unsigned char new_sha1[20], const char *remotes_name)\n@@ -410,7 +402,7 @@ int check_submodule_needs_pushing(unsigned char new_sha1[20], const char *remote\n \t\tdie(\"revision walk setup failed\");\n \n \twhile ((commit = get_revision(&rev)) && !needs_pushing)\n-\t\tcommit_need_pushing(commit, commit->parents, &needs_pushing);\n+\t\tcommit_need_pushing(commit, &needs_pushing);\n \n \tfree(sha1_copy);\n \tstrbuf_release(&remotes_arg);\n-- \n1.7.8\n"},{"id":"181388","messageId":"4EEC6E8B.8080804@lsrfire.ath.cx","threadId":"29194","inReplyTo":"4EEC6BD4.4040302@lsrfire.ath.cx","subject":"Re: [PATCH 1/3] use struct sha1_array in diff_tree_combined()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-17T10:27:23Z","receivedAt":"2011-12-17T10:27:23Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 17.12.2011 11:15, schrieb René Scharfe:\n> Maintaining an array of hashes is easier using sha1_array than\n> open-coding it.  This patch also fixes a leak of the SHA1 array\n> in  diff_tree_combined_merge().\n>\n> ---\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n"},{"id":"181389","messageId":"4EEC6E8E.6090703@lsrfire.ath.cx","threadId":"29194","inReplyTo":"4EEC6CD7.2030408@lsrfire.ath.cx","subject":"Re: [PATCH 2/3] pass struct commit to diff_tree_combined_merge()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-17T10:27:26Z","receivedAt":"2011-12-17T10:27:26Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 17.12.2011 11:20, schrieb René Scharfe:\n> Instead of passing the hash of a commit and then searching that\n> same commit in the single caller, simply pass the commit directly.\n>\n> ---\n\nSigned-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>\n\nUgh.  Forgetting it twice is stupid..\n"},{"id":"181392","messageId":"20111217105315.GA23935@sigill.intra.peff.net","threadId":"29194","inReplyTo":"4EEC6BD4.4040302@lsrfire.ath.cx","subject":"Re: [PATCH 1/3] use struct sha1_array in diff_tree_combined()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-17T10:53:15Z","receivedAt":"2011-12-17T10:53:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 17, 2011 at 11:15:48AM +0100, René Scharfe wrote:\n\n> Maintaining an array of hashes is easier using sha1_array than\n> open-coding it.  This patch also fixes a leak of the SHA1 array\n> in  diff_tree_combined_merge().\n> \n> ---\n>  builtin/diff.c |   12 ++++++------\n>  combine-diff.c |   34 +++++++++++++---------------------\n>  diff.h         |    3 ++-\n>  submodule.c    |   14 +++++---------\n>  4 files changed, 26 insertions(+), 37 deletions(-)\n\nYay. When I refactored sha1_array, I hoped there would be other users,\nbut I hadn't actually converted any yet. Good to know it is paying off.\n\n> -\tparent = xmalloc(ents * sizeof(*parent));\n> -\tfor (i = 0; i < ents; i++)\n> -\t\thashcpy((unsigned char *)(parent + i), ent[i].item->sha1);\n> -\tdiff_tree_combined(parent[0], parent + 1, ents - 1,\n> +\tfor (i = 1; i < ents; i++)\n> +\t\tsha1_array_append(&parents, ent[i].item->sha1);\n> +\tdiff_tree_combined(ent[0].item->sha1, &parents,\n>  \t\t\t   revs->dense_combined_merges, revs);\n> -\tfree((void *)parent);\n> +\tsha1_array_clear(&parents);\n\nThe original code is slightly more efficient, as it is able to use a\nsingle malloc (because it knows the number of entries ahead of time).\nIt probably doesn't make a difference, but we could also add a\nsha1_array_grow() for this case.\n\nI think it could be used in all three spots you converted in this patch.\n\n-Peff\n"},{"id":"181395","messageId":"4EEC7A10.3080705@lsrfire.ath.cx","threadId":"29194","inReplyTo":"20111217105315.GA23935@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] use struct sha1_array in diff_tree_combined()","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2011-12-17T11:16:32Z","receivedAt":"2011-12-17T11:16:32Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 17.12.2011 11:53, schrieb Jeff King:\n>> -\tparent = xmalloc(ents * sizeof(*parent));\n>> -\tfor (i = 0; i<  ents; i++)\n>> -\t\thashcpy((unsigned char *)(parent + i), ent[i].item->sha1);\n>> -\tdiff_tree_combined(parent[0], parent + 1, ents - 1,\n>> +\tfor (i = 1; i<  ents; i++)\n>> +\t\tsha1_array_append(&parents, ent[i].item->sha1);\n>> +\tdiff_tree_combined(ent[0].item->sha1,&parents,\n>>   \t\t\t   revs->dense_combined_merges, revs);\n>> -\tfree((void *)parent);\n>> +\tsha1_array_clear(&parents);\n>\n> The original code is slightly more efficient, as it is able to use a\n> single malloc (because it knows the number of entries ahead of time).\n> It probably doesn't make a difference, but we could also add a\n> sha1_array_grow() for this case.\n>\n> I think it could be used in all three spots you converted in this patch.\n\nWe coulddo that, yes.  In the case above we have the number already, in \nthe other cases we'd have to count.\n\nBut I don't think it's worth it here.  ALLOC_GROW gives us 24 entries \ninitially, which should be enough in most cases -- I'm not sure I want \nto see combined diff of that many tree.  And 24 times 20 bytes is small \nenough to not cause any memory allocation issues.\n\nTaking out the counting and not having to worry about the number of \nitems is a feature in my book.  Simple timings before and after the \npatch didn't show any significant difference.\n\nRené\n"},{"id":"181396","messageId":"20111217111920.GA24917@sigill.intra.peff.net","threadId":"29194","inReplyTo":"4EEC7A10.3080705@lsrfire.ath.cx","subject":"Re: [PATCH 1/3] use struct sha1_array in diff_tree_combined()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-12-17T11:19:20Z","receivedAt":"2011-12-17T11:19:20Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Dec 17, 2011 at 12:16:32PM +0100, René Scharfe wrote:\n\n> >The original code is slightly more efficient, as it is able to use a\n> >single malloc (because it knows the number of entries ahead of time).\n> >It probably doesn't make a difference, but we could also add a\n> >sha1_array_grow() for this case.\n> [...]\n> We coulddo that, yes.  In the case above we have the number already,\n> in the other cases we'd have to count.\n> \n> But I don't think it's worth it here.  ALLOC_GROW gives us 24 entries\n> initially, which should be enough in most cases -- I'm not sure I\n> want to see combined diff of that many tree.  And 24 times 20 bytes\n> is small enough to not cause any memory allocation issues.\n\nYou're right.\n\nI was blindly looking at the conversion without thinking about the\ncontext. Of course if you have just a few items, it's going to be\nirrelevant (my initial refactoring of sha1_array was to help speed up a\nhundreds-of-thousands of sha1s case, so I think that put me in the\nmindset of a large list).\n\nSorry for the noise.\n\n-Peff\n"}]}