[PATCH 3/3] use cache for function names in hunk headers

[Clemens Buchacher <drizzd@aon.at>]

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 of searching the entire file for each hunk
individually, cache and reuse the search result
from previous hunks.

Diff performance for the 50000 line test in t3419
before and after this patch:

2.78user 0.01system 0:02.82elapsed 99%CPU
0.05user 0.01system 0:00.06elapsed 96%CPU

Signed-off-by: Clemens Buchacher <drizzd@aon.at>
---
 xdiff/xemit.c |   44 ++++++++++++++++++++++++++++++++------------
 1 files changed, 32 insertions(+), 12 deletions(-)

diff --git a/xdiff/xemit.c b/xdiff/xemit.c
index c4bedf0..349bd6b 100644
--- a/xdiff/xemit.c
+++ b/xdiff/xemit.c
@@ -85,8 +85,15 @@ 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) {
+struct xdl_find_func_cache {
+	char buf[80];
+	long len;
+	xdfile_t *xf;
+	int line;
+};
+
+static void xdl_find_func(xdfile_t *xf, long line, find_func_t ff,
+		          void *ff_priv, struct xdl_find_func_cache *cache) {
 
 	/*
 	 * Be quite stupid about this for now.  Find a line in the old file
@@ -96,13 +103,28 @@ static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll,
 
 	const char *rec;
 	long len;
+	int i, l;
 
-	while (i-- > 0) {
-		len = xdl_get_rec(xf, i, &rec);
-		if ((*ll = ff(rec, len, buf, sz, ff_priv)) >= 0)
+	if (line < cache->line)
+		cache->xf = 0;
+
+	i = line;
+	l = -1;
+	while (--i >= 0 && l < 0) {
+		if (xf == cache->xf && i < cache->line) {
+			cache->line = line;
 			return;
+		}
+
+		len = xdl_get_rec(xf, i, &rec);
+		l = ff(rec, len, cache->buf, sizeof(cache->buf), ff_priv);
 	}
-	*ll = 0;
+	if (l < 0)
+		l = 0;
+
+	cache->xf = xf;
+	cache->len = l;
+	cache->line = line;
 }
 
 
@@ -125,8 +147,7 @@ int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
 		  xdemitconf_t const *xecfg) {
 	long s1, s2, e1, e2, lctx;
 	xdchange_t *xch, *xche;
-	char funcbuf[80];
-	long funclen = 0;
+	struct xdl_find_func_cache func_cache = { "", 0, NULL, -1 };
 	find_func_t ff = xecfg->find_func ?  xecfg->find_func : def_ff;
 
 	if (xecfg->flags & XDL_EMIT_COMMON)
@@ -150,12 +171,11 @@ 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);
+			xdl_find_func(&xe->xdf1, s1, ff, xecfg->find_func_priv,
+					&func_cache);
 		}
 		if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,
-				      funcbuf, funclen, ecb) < 0)
+				      func_cache.buf, func_cache.len, ecb) < 0)
 			return -1;
 
 		/*
-- 
1.7.1.571.gba4d01