{"thread":{"id":"6305","subject":"[PATCH 4/6] in_merge_bases(): optimization","startedAt":"2007-01-09T10:41:28Z","lastAt":"2007-01-09T10:41:28Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"31231","messageId":"7virfgo52f.fsf@assigned-by-dhcp.cox.net","threadId":"6305","inReplyTo":null,"subject":"[PATCH 4/6] in_merge_bases(): optimization","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-09T10:41:28Z","receivedAt":"2007-01-09T10:41:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The callers of in_merge_bases() are interested in finding out if\nthe given commit is reachable from others, and we do not have to\ncompute the true merge base.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n commit.c |   48 ++++++++++++++++++++++++++++++++++--------------\n 1 files changed, 34 insertions(+), 14 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 53f43e3..72f6980 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -1034,7 +1034,7 @@ static struct commit *interesting(struct commit_list *list)\n \treturn NULL;\n }\n \n-static struct commit_list *base_traverse(struct commit_list *list)\n+static struct commit_list *base_traverse(struct commit_list *list, struct commit *stop)\n {\n \tstruct commit_list *result = NULL;\n \n@@ -1068,10 +1068,20 @@ static struct commit_list *base_traverse(struct commit_list *list)\n \t\t\tp->object.flags |= flags;\n \t\t\tinsert_by_date(p, &list);\n \t\t}\n+\t\tif (stop && (stop->object.flags & PARENT2)) {\n+\t\t\tfree_commit_list(list);\n+\t\t\tlist = NULL;\n+\t\t\tinsert_by_date(stop, &list);\n+\t\t\treturn list;\n+\t\t}\n \t}\n \n \t/* Clean up the result to remove stale ones */\n \tfree_commit_list(list);\n+\n+\tif (stop)\n+\t\treturn NULL;\n+\n \tlist = result; result = NULL;\n \twhile (list) {\n \t\tstruct commit_list *n = list->next;\n@@ -1101,7 +1111,7 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)\n \tinsert_by_date(one, &list);\n \tinsert_by_date(two, &list);\n \n-\treturn base_traverse(list);\n+\treturn base_traverse(list, NULL);\n }\n \n struct commit_list *get_merge_bases(struct commit *one,\n@@ -1166,20 +1176,30 @@ struct commit_list *get_merge_bases(struct commit *one,\n \n int in_merge_bases(struct commit *commit, struct commit **reference, int num)\n {\n-\tstruct commit_list *bases, *b;\n-\tint ret = 0;\n+\tstruct commit_list *result, *list;\n+\tint i;\n \n-\tif (num == 1)\n-\t\tbases = get_merge_bases(commit, *reference, 1);\n-\telse\n-\t\tdie(\"not yet\");\n-\tfor (b = bases; b; b = b->next) {\n-\t\tif (!hashcmp(commit->object.sha1, b->item->object.sha1)) {\n-\t\t\tret = 1;\n-\t\t\tbreak;\n+\tlist = NULL;\n+\tparse_commit(commit);\n+\tcommit->object.flags |= PARENT1;\n+\tinsert_by_date(commit, &list);\n+\n+\tfor (i = 0; i < num; i++) {\n+\t\tstruct commit *two = reference[i];\n+\t\tparse_commit(two);\n+\t\tif (!(two->object.flags & PARENT2)) {\n+\t\t\ttwo->object.flags |= PARENT2;\n+\t\t\tinsert_by_date(two, &list);\n \t\t}\n \t}\n+\tresult = base_traverse(list, commit);\n+\ti = !!result;\n+\tfree_commit_list(result);\n \n-\tfree_commit_list(bases);\n-\treturn ret;\n+\tclear_commit_marks(commit, all_flags);\n+\tfor (i = 0; i < num; i++) {\n+\t\tstruct commit *two = reference[i];\n+\t\tclear_commit_marks(two, all_flags);\n+\t}\n+\treturn i;\n }\n-- \n1.4.4.4.g564d\n"}]}