Skip to content

@rctay /gist:1066773
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
[gsoc-diff] try_lcs: skip chains
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.