*/
#include "xinclude.h"
-#include "xtypes.h"
-#include "xdiff.h"
#define MAX_PTR UINT_MAX
#define MAX_CNT UINT_MAX
#define REC(env, s, l) \
(env->xdf##s.recs[l - 1])
-static int cmp_recs(xpparam_t const *xpp,
- xrecord_t *r1, xrecord_t *r2)
+static int cmp_recs(xrecord_t *r1, xrecord_t *r2)
{
- return r1->ha == r2->ha &&
- xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
- xpp->flags);
-}
+ return r1->ha == r2->ha;
-#define CMP_ENV(xpp, env, s1, l1, s2, l2) \
- (cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))
+}
#define CMP(i, s1, l1, s2, l2) \
- (cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2)))
+ (cmp_recs(REC(i->env, s1, l1), REC(i->env, s2, l2)))
#define TABLE_HASH(index, side, line) \
XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
-static int scanA(struct histindex *index, unsigned int line1, unsigned int count1)
+static int scanA(struct histindex *index, int line1, int count1)
{
- unsigned int ptr;
- unsigned int tbl_idx;
+ unsigned int ptr, tbl_idx;
unsigned int chain_len;
struct record **rec_chain, *rec;
return 0;
}
-static int try_lcs(
- struct histindex *index, struct region *lcs, unsigned int b_ptr,
- unsigned int line1, unsigned int count1,
- unsigned int line2, unsigned int count2)
+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)];
return b_next;
}
-static int find_lcs(
- struct histindex *index, struct region *lcs,
- unsigned int line1, unsigned int count1,
- unsigned int line2, unsigned int count2)
+static int fall_back_to_classic_diff(xpparam_t const *xpp, xdfenv_t *env,
+ int line1, int count1, int line2, int count2)
{
- unsigned int b_ptr;
-
- if (scanA(index, line1, count1))
- return -1;
-
- index->cnt = index->max_chain_length + 1;
+ xpparam_t xpparam;
- for (b_ptr = line2; b_ptr <= LINE_END(2); )
- b_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2);
+ memset(&xpparam, 0, sizeof(xpparam));
+ xpparam.flags = xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
- return index->has_common && index->max_chain_length < index->cnt;
+ return xdl_fall_back_diff(env, &xpparam,
+ line1, count1, line2, count2);
}
-static int fall_back_to_classic_diff(struct histindex *index,
- int line1, int count1, int line2, int count2)
+static inline void free_index(struct histindex *index)
{
- xpparam_t xpp;
- xpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
-
- return xdl_fall_back_diff(index->env, &xpp,
- line1, count1, line2, count2);
+ xdl_free(index->records);
+ xdl_free(index->line_map);
+ xdl_free(index->next_ptrs);
+ xdl_cha_free(&index->rcha);
}
-static int histogram_diff(
- xpparam_t const *xpp, xdfenv_t *env,
- unsigned int line1, unsigned int count1,
- unsigned int line2, unsigned int count2)
+static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,
+ struct region *lcs,
+ int line1, int count1, int line2, int count2)
{
+ int b_ptr;
+ int sz, ret = -1;
struct histindex index;
- struct region lcs;
- size_t sz;
- int result = -1;
-
- if (count1 <= 0 && count2 <= 0)
- return 0;
-
- if (LINE_END(1) >= MAX_PTR)
- return -1;
-
- if (!count1) {
- while(count2--)
- env->xdf2.rchg[line2++ - 1] = 1;
- return 0;
- } else if (!count2) {
- while(count1--)
- env->xdf1.rchg[line1++ - 1] = 1;
- return 0;
- }
memset(&index, 0, sizeof(index));
index.table_bits = xdl_hashbits(count1);
sz = index.records_size = 1 << index.table_bits;
- GIT_ERROR_CHECK_ALLOC_MULTIPLY(&sz, sz, sizeof(struct record *));
-
+ sz *= sizeof(struct record *);
if (!(index.records = (struct record **) xdl_malloc(sz)))
goto cleanup;
memset(index.records, 0, sz);
index.ptr_shift = line1;
index.max_chain_length = 64;
+ if (scanA(&index, line1, count1))
+ goto cleanup;
+
+ index.cnt = index.max_chain_length + 1;
+
+ for (b_ptr = line2; b_ptr <= LINE_END(2); )
+ b_ptr = try_lcs(&index, lcs, b_ptr, line1, count1, line2, count2);
+
+ if (index.has_common && index.max_chain_length < index.cnt)
+ ret = 1;
+ else
+ ret = 0;
+
+cleanup:
+ free_index(&index);
+ return ret;
+}
+
+static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
+ int line1, int count1, int line2, int count2)
+{
+ struct region lcs;
+ int lcs_found;
+ int result;
+redo:
+ result = -1;
+
+ if (count1 <= 0 && count2 <= 0)
+ return 0;
+
+ if (LINE_END(1) >= MAX_PTR)
+ return -1;
+
+ if (!count1) {
+ while(count2--)
+ env->xdf2.rchg[line2++ - 1] = 1;
+ return 0;
+ } else if (!count2) {
+ while(count1--)
+ env->xdf1.rchg[line1++ - 1] = 1;
+ return 0;
+ }
+
memset(&lcs, 0, sizeof(lcs));
- if (find_lcs(&index, &lcs, line1, count1, line2, count2))
- result = fall_back_to_classic_diff(&index, line1, count1, line2, count2);
+ lcs_found = find_lcs(xpp, env, &lcs, line1, count1, line2, count2);
+ if (lcs_found < 0)
+ goto out;
+ else if (lcs_found)
+ result = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2);
else {
if (lcs.begin1 == 0 && lcs.begin2 == 0) {
while (count1--)
line1, lcs.begin1 - line1,
line2, lcs.begin2 - line2);
if (result)
- goto cleanup;
- result = histogram_diff(xpp, env,
- lcs.end1 + 1, LINE_END(1) - lcs.end1,
- lcs.end2 + 1, LINE_END(2) - lcs.end2);
- if (result)
- goto cleanup;
+ goto out;
+ /*
+ * result = histogram_diff(xpp, env,
+ * lcs.end1 + 1, LINE_END(1) - lcs.end1,
+ * lcs.end2 + 1, LINE_END(2) - lcs.end2);
+ * but let's optimize tail recursion ourself:
+ */
+ count1 = LINE_END(1) - lcs.end1;
+ line1 = lcs.end1 + 1;
+ count2 = LINE_END(2) - lcs.end2;
+ line2 = lcs.end2 + 1;
+ goto redo;
}
}
-
-cleanup:
- xdl_free(index.records);
- xdl_free(index.line_map);
- xdl_free(index.next_ptrs);
- xdl_cha_free(&index.rcha);
-
+out:
return result;
}
projects / libgit2.git / blobdiff