diff options
| author | Stefan Beller <sbeller@google.com> | 2018-07-20 00:19:42 +0200 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2018-07-23 19:12:16 +0200 |
| commit | 79cb2ebb92c18af11edf5eea238425d86eef173d (patch) | |
| tree | 3e41f104e579b7940af35b79d70e17b2312ba8ce | |
| parent | xdiff/xhistogram: move index allocation into find_lcs (diff) | |
| download | git-79cb2ebb92c18af11edf5eea238425d86eef173d.tar.xz git-79cb2ebb92c18af11edf5eea238425d86eef173d.zip | |
xdiff/histogram: remove tail recursion
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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
| -rw-r--r-- | xdiff/xhistogram.c | 20 |
1 files changed, 14 insertions, 6 deletions
diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index fc2d3cd95d..ec85f5992b 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: |