[PATCH] xdiff/histogram: remove tail recursion
- From
Stefan Beller <sbeller@google.com>
- Date
- Jul 19, 2018, 22:19 UTC
- Message-ID
- <20180719221942.179565-1-sbeller@google.com>
- In-Reply-To
- <20180719185620.124768-4-sbeller@google.com>
When running the same reproduction script as the previous patch, it turns out the stack is too small, which can be easily avoided.
Signed-off-by: Stefan Beller <sbeller@google.com> --- xdiff/xhistogram.c | 20 ++++++++++++++------ 1 file changed, 14 insertions(+), 6 deletions(-)
diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index fc2d3cd95d9..ec85f5992bd 100644 --- a/xdiff/xhistogram.c +++ b/xdiff/xhistogram.c @@ -318,7 +318,9 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env, { struct region lcs; int lcs_found; - int result = -1; + int result; +redo: + result = -1; if (count1 <= 0 && count2 <= 0) return 0; @@ -355,11 +357,17 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env, line2, lcs.begin2 - line2); if (result) goto out; - result = histogram_diff(xpp, env, - lcs.end1 + 1, LINE_END(1) - lcs.end1, - lcs.end2 + 1, LINE_END(2) - lcs.end2); - if (result) - goto out; + /* + * result = histogram_diff(xpp, env, + * lcs.end1 + 1, LINE_END(1) - lcs.end1, + * lcs.end2 + 1, LINE_END(2) - lcs.end2); + * but let's optimize tail recursion ourself: + */ + count1 = LINE_END(1) - lcs.end1; + line1 = lcs.end1 + 1; + count2 = LINE_END(2) - lcs.end2; + line2 = lcs.end2 + 1; + goto redo; } } out:
-- 2.18.0.233.g985f88cf7e-goog