[gsoc-diff] try_lcs: skip chains

gistfile1.diff

diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c
index e65bc29..fb7f17a 100644
--- a/xdiff/xhistogram.c
+++ b/xdiff/xhistogram.c
@@ -11,6 +11,7 @@
 struct histindex {
 	struct record {
 		unsigned int ptr, cnt;
+		unsigned long *ha;
 		struct record *next, *head;
 	} **records; /* an ocurrence */
 	unsigned int table_bits,
@@ -58,8 +59,11 @@ static int cmp_recs(xpparam_t const *xpp, xdfenv_t *env,
 #define cmp(i, s1, l1, s2, l2) \
 	(cmp_env(i->xpp, i->env, s1, l1, s2, l2))
 
+#define table_hash_rec(index, rec) \
+	XDL_HASHLONG((rec)->ha, index->table_bits)
+
 #define table_hash(index, side, line) \
-	XDL_HASHLONG((get_rec(index->env, side, line))->ha, index->table_bits)
+	table_hash_rec(index, get_rec(index->env, side, line))
 
 static int scanA(struct histindex *index, int line1, int count1)
 {
@@ -88,6 +92,7 @@ static int scanA(struct histindex *index, int line1, int count1)
 
 				new_rec->next = rec;
 				new_rec->head = rec->head;
+				new_rec->ha = rec->ha;
 				*rec_chain = new_rec;
 				INDEX_NEXT_PTR(index, ptr) = rec->ptr;
 				INDEX_CNT(index, ptr) = new_cnt;
@@ -109,6 +114,7 @@ static int scanA(struct histindex *index, int line1, int count1)
 		new_rec->cnt = 1;
 		new_rec->next = *rec_chain;
 		new_rec->head = new_rec;
+		new_rec->ha = &(get_rec(index->env, 1, ptr))->ha;
 		INDEX_NEXT_PTR(index, ptr) = 0;
 		INDEX_CNT(index, ptr) = 1;
 		*rec_chain = new_rec;
@@ -124,10 +130,19 @@ static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr,
 	int line1, int count1, int line2, int count2)
 {
 	unsigned int b_next = b_ptr + 1;
-	struct record *rec = index->records[table_hash(index, 2, b_ptr)];
+	xrecord_t *brec = get_rec(index->env, 2, b_ptr);
+	struct record *rec = index->records[table_hash_rec(index, brec)];
 	unsigned int as, ae, bs, be, np, rc;
 	int should_break;
 
+	while (rec
+		&& !cmp_recs(index->xpp, index->env, brec, get_rec(index->env, 1, rec->ptr))) {
+		rec = rec->head->next;
+	}
+
+	if (!rec)
+		return b_next;
+
 	for (; rec; rec = rec->next) {
 		if (rec->cnt > index->cnt) {
 			if (!index->has_common)