{"thread":{"id":"10240","subject":"[PATCH] clear_commit_marks(): avoid deep recursion","startedAt":"2007-10-10T22:14:35Z","lastAt":"2007-10-10T22:14:35Z","messageCount":1,"participants":["Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"55429","messageId":"Pine.LNX.4.64.0710102313530.4174@racer.site","threadId":"10240","inReplyTo":null,"subject":"[PATCH] clear_commit_marks(): avoid deep recursion","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-10-10T22:14:35Z","receivedAt":"2007-10-10T22:14:35Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nBefore this patch, clear_commit_marks() recursed for each parent.  This\ncould be potentially very expensive in terms of stack space.  Probably\nthe only reason that this did not lead to problems is the fact that we\ntypically call clear_commit_marks() after marking a relatively small set\nof commits.\n\nUse (sort of) a tail recursion instead: first recurse on the parents\nother than the first one, and then continue the loop with the first\nparent.\n\nNoticed by Shawn Pearce.\n\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n---\n commit.c |   23 ++++++++++++++---------\n 1 files changed, 14 insertions(+), 9 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex 20fb220..ac24266 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -441,17 +441,22 @@ struct commit *pop_most_recent_commit(struct commit_list **list,\n \n void clear_commit_marks(struct commit *commit, unsigned int mark)\n {\n-\tstruct commit_list *parents;\n+\twhile (commit) {\n+\t\tstruct commit_list *parents;\n \n-\tcommit->object.flags &= ~mark;\n-\tparents = commit->parents;\n-\twhile (parents) {\n-\t\tstruct commit *parent = parents->item;\n+\t\tif (!(mark & commit->object.flags))\n+\t\t\treturn;\n \n-\t\t/* Have we already cleared this? */\n-\t\tif (mark & parent->object.flags)\n-\t\t\tclear_commit_marks(parent, mark);\n-\t\tparents = parents->next;\n+\t\tcommit->object.flags &= ~mark;\n+\n+\t\tparents = commit->parents;\n+\t\tif (!parents)\n+\t\t\treturn;\n+\n+\t\twhile ((parents = parents->next))\n+\t\t\tclear_commit_marks(parents->item, mark);\n+\n+\t\tcommit = commit->parents->item;\n \t}\n }\n \n-- \n1.5.3.4.1169.g5fb8d\n"}]}