diff options
| author | René Scharfe <rene.scharfe@lsrfire.ath.cx> | 2010-09-26 18:26:56 +0200 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2010-09-30 11:43:07 -0700 |
| commit | c099789bb01b810e40f9cfaa5c842ed568110fc8 (patch) | |
| tree | 1a4b9a59bd1363fc47636b1b6a49a838f9377bad /xdiff | |
| parent | ad14b450c0c70bfcf90de0aa19ffa5e44e402b69 (diff) | |
| download | git-c099789bb01b810e40f9cfaa5c842ed568110fc8.tar.gz | |
diff: avoid repeated scanning while looking for funcname
For each hunk, xdl_find_func searches the preimage for a function name
until the beginning of the file. If the file does not contain any
function names, this search has complexity O(n^2) in the number of
hunks n.
Instead, inline xdl_find_func() and keep track of up to which line we
have scanned already and the contents of the last funcname line that
we have found.
Noticed and a different approach proposed by Clemens Buchacher.
This alternative solution was done by René Scharfe.
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'xdiff')
| -rw-r--r-- | xdiff/xemit.c | 38 |
1 files changed, 14 insertions, 24 deletions
diff --git a/xdiff/xemit.c b/xdiff/xemit.c index c4bedf0d1c..277e2eec5b 100644 --- a/xdiff/xemit.c +++ b/xdiff/xemit.c @@ -85,27 +85,6 @@ static long def_ff(const char *rec, long len, char *buf, long sz, void *priv) return -1; } -static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll, - find_func_t ff, void *ff_priv) { - - /* - * Be quite stupid about this for now. Find a line in the old file - * before the start of the hunk (and context) which starts with a - * plausible character. - */ - - const char *rec; - long len; - - while (i-- > 0) { - len = xdl_get_rec(xf, i, &rec); - if ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0) - return; - } - *ll = 0; -} - - static int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, xdemitconf_t const *xecfg) { xdfile_t *xdf = &xe->xdf1; @@ -127,6 +106,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, xdchange_t *xch, *xche; char funcbuf[80]; long funclen = 0; + long funclineprev = -1; find_func_t ff = xecfg->find_func ? xecfg->find_func : def_ff; if (xecfg->flags & XDL_EMIT_COMMON) @@ -150,9 +130,19 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, */ if (xecfg->flags & XDL_EMIT_FUNCNAMES) { - xdl_find_func(&xe->xdf1, s1, funcbuf, - sizeof(funcbuf), &funclen, - ff, xecfg->find_func_priv); + long l; + for (l = s1 - 1; l >= 0 && l > funclineprev; l--) { + const char *rec; + long reclen = xdl_get_rec(&xe->xdf1, l, &rec); + long newfunclen = ff(rec, reclen, funcbuf, + sizeof(funcbuf), + xecfg->find_func_priv); + if (newfunclen >= 0) { + funclen = newfunclen; + break; + } + } + funclineprev = s1 - 1; } if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2, funcbuf, funclen, ecb) < 0) |