public
Last active

[gsoc-diff] try_lcs: skip chains

  • Download Gist
gistfile1.diff
Diff
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
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)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.