This source file includes following definitions.
- insert_record
- fill_hashmap
- binary_search
- find_longest_common_sequence
- match
- walk_common_sequence
- fall_back_to_classic_diff
- patience_diff
- xdl_do_patience_diff
#include "xinclude.h"
#include "xtypes.h"
#include "xdiff.h"
#define NON_UNIQUE ULONG_MAX
struct hashmap {
int nr, alloc;
struct entry {
unsigned long hash;
unsigned long line1, line2;
struct entry *next, *previous;
} *entries, *first, *last;
unsigned long has_matches;
mmfile_t *file1, *file2;
xdfenv_t *env;
xpparam_t const *xpp;
};
static void insert_record(int line, struct hashmap *map, int pass)
{
xrecord_t **records = pass == 1 ?
map->env->xdf1.recs : map->env->xdf2.recs;
xrecord_t *record = records[line - 1], *other;
int index = (int)((record->ha << 1) % map->alloc);
while (map->entries[index].line1) {
other = map->env->xdf1.recs[map->entries[index].line1 - 1];
if (map->entries[index].hash != record->ha ||
!xdl_recmatch(record->ptr, record->size,
other->ptr, other->size,
map->xpp->flags)) {
if (++index >= map->alloc)
index = 0;
continue;
}
if (pass == 2)
map->has_matches = 1;
if (pass == 1 || map->entries[index].line2)
map->entries[index].line2 = NON_UNIQUE;
else
map->entries[index].line2 = line;
return;
}
if (pass == 2)
return;
map->entries[index].line1 = line;
map->entries[index].hash = record->ha;
if (!map->first)
map->first = map->entries + index;
if (map->last) {
map->last->next = map->entries + index;
map->entries[index].previous = map->last;
}
map->last = map->entries + index;
map->nr++;
}
static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
struct hashmap *result,
int line1, int count1, int line2, int count2)
{
result->file1 = file1;
result->file2 = file2;
result->xpp = xpp;
result->env = env;
result->alloc = count1 * 2;
result->entries = (struct entry *)
xdl_malloc(result->alloc * sizeof(struct entry));
if (!result->entries)
return -1;
memset(result->entries, 0, result->alloc * sizeof(struct entry));
while (count1--)
insert_record(line1++, result, 1);
while (count2--)
insert_record(line2++, result, 2);
return 0;
}
static int binary_search(struct entry **sequence, int longest,
struct entry *entry)
{
int left = -1, right = longest;
while (left + 1 < right) {
int middle = (left + right) / 2;
if (sequence[middle]->line2 > entry->line2)
right = middle;
else
left = middle;
}
return left;
}
static struct entry *find_longest_common_sequence(struct hashmap *map)
{
struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));
int longest = 0, i;
struct entry *entry;
for (entry = map->first; entry; entry = entry->next) {
if (!entry->line2 || entry->line2 == NON_UNIQUE)
continue;
i = binary_search(sequence, longest, entry);
entry->previous = i < 0 ? NULL : sequence[i];
sequence[++i] = entry;
if (i == longest)
longest++;
}
if (!longest) {
xdl_free(sequence);
return NULL;
}
entry = sequence[longest - 1];
entry->next = NULL;
while (entry->previous) {
entry->previous->next = entry;
entry = entry->previous;
}
xdl_free(sequence);
return entry;
}
static int match(struct hashmap *map, int line1, int line2)
{
xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];
xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];
return xdl_recmatch(record1->ptr, record1->size,
record2->ptr, record2->size, map->xpp->flags);
}
static int patience_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2);
static int walk_common_sequence(struct hashmap *map, struct entry *first,
int line1, int count1, int line2, int count2)
{
int end1 = line1 + count1, end2 = line2 + count2;
int next1, next2;
for (;;) {
if (first) {
next1 = first->line1;
next2 = first->line2;
while (next1 > line1 && next2 > line2 &&
match(map, next1 - 1, next2 - 1)) {
next1--;
next2--;
}
} else {
next1 = end1;
next2 = end2;
}
while (line1 < next1 && line2 < next2 &&
match(map, line1, line2)) {
line1++;
line2++;
}
if (next1 > line1 || next2 > line2) {
struct hashmap submap;
memset(&submap, 0, sizeof(submap));
if (patience_diff(map->file1, map->file2,
map->xpp, map->env,
line1, next1 - line1,
line2, next2 - line2))
return -1;
}
if (!first)
return 0;
while (first->next &&
first->next->line1 == first->line1 + 1 &&
first->next->line2 == first->line2 + 1)
first = first->next;
line1 = first->line1 + 1;
line2 = first->line2 + 1;
first = first->next;
}
}
static int fall_back_to_classic_diff(struct hashmap *map,
int line1, int count1, int line2, int count2)
{
xpparam_t xpp;
xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
return xdl_fall_back_diff(map->env, &xpp,
line1, count1, line2, count2);
}
static int patience_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2)
{
struct hashmap map;
struct entry *first;
int result = 0;
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(&map, 0, sizeof(map));
if (fill_hashmap(file1, file2, xpp, env, &map,
line1, count1, line2, count2))
return -1;
if (!map.has_matches) {
while(count1--)
env->xdf1.rchg[line1++ - 1] = 1;
while(count2--)
env->xdf2.rchg[line2++ - 1] = 1;
xdl_free(map.entries);
return 0;
}
first = find_longest_common_sequence(&map);
if (first)
result = walk_common_sequence(&map, first,
line1, count1, line2, count2);
else
result = fall_back_to_classic_diff(&map,
line1, count1, line2, count2);
xdl_free(map.entries);
return result;
}
int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env)
{
if (xdl_prepare_env(file1, file2, xpp, env) < 0)
return -1;
return patience_diff(file1, file2, xpp, env,
1, env->xdf1.nrec, 1, env->xdf2.nrec);
}