Renà Scharfe <rene.scharfe@xxxxxxxxxxxxxx> writes:
> Am 23.09.2010 09:04, schrieb Clemens Buchacher:
>> 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(n2) in the
>> number of hunks n.
> ...
> How about something like this? It also removes an outdated comment. The
> inlining part should probably split out in its own patch..
>
> xdiff/xemit.c | 38 ++++++++++++++------------------------
> 1 files changed, 14 insertions(+), 24 deletions(-)
I had to wonder if this optimization closes a door for us to extend the
function header patterns to allow inspecting multiple lines.
Suppose that a rule says that a header line is a first non-blank line that
follows two or more blank lines. E.g.
... the end of a paragraph that is not followed by two blank lines.
(blank line)
This is not a header, but is part of the previous paragraph group.
... body of the paragraph here ...
and this is the tail of the paragraph group.
(blank line)
(blank line)
This begins a new paragraph group.
And this is the second line of it.
Under such a rule, "This begins a new paragraph group." is a header line.
If the first hunk begins at the second blank line before that header, we
will scan down to the beginning of the file and will find a header that
comes before that header line, and remember it in funclen/funcbuf[]. The
next scan will stop after looking at one blank line before "This begins a
new paragraph group.", instead of going down to the beginning, and would
not to have a chance to notice that "This begins a new paragraph group."
indeed has two blank lines before it. It would instead keep returning the
header we found before this header.
I do not think this is such a big issue, though. In order to allow such a
multi-line matching, the loop in xdl_find_func(), now inlined, needs to be
restructured anyway, and whoever is doing such an enhancement hopefully
will notice that s/he needs to look behind beyond (s1-1) at that point.
So an Ack from me.
Thanks.
> diff --git a/xdiff/xemit.c b/xdiff/xemit.c
> index c4bedf0..a663f21 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)
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html