This is an archive of the discontinued Mercurial Phabricator instance.

Differential D2630

xdiff: move hashtable calculation to a separate function
AbandonedPublic

Authored by quark on Mar 3 2018, 9:51 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Summary

Before running the main diff algorithm, xdiff will "prepare" the contexts
for both files. That includes splitting, hashing all the lines, and building
hash tables for those lines. The hash table building process could be
expensive. Moving it out so it can be optimized separately.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Revision Contents
Changeset List

Diff 6529

mercurial/thirdparty/xdiff/xprepare.c

rhash[hi] = rec; rhash[hi] = rec;
return 0; return 0;
} }
static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp, static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp,
xdlclassifier_t *cf, xdfile_t *xdf) { xdlclassifier_t *cf, xdfile_t *xdf) {
unsigned int hbits; long nrec, bsize;
long nrec, hsize, bsize;
unsigned long hav; unsigned long hav;
char const *blk, *cur, *top, *prev; char const *blk, *cur, *top, *prev;
xrecord_t *crec; xrecord_t *crec;
xrecord_t **recs, **rrecs; xrecord_t **recs, **rrecs;
xrecord_t **rhash;
unsigned long *ha; unsigned long *ha;
char *rchg; char *rchg;
long *rindex; long *rindex;
ha = NULL; ha = NULL;
rindex = NULL; rindex = NULL;
rchg = NULL; rchg = NULL;
rhash = NULL;
recs = NULL; recs = NULL;
if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)
goto abort; goto abort;
if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))
goto abort; goto abort;
{
hbits = xdl_hashbits((unsigned int) narec);
hsize = 1 << hbits;
if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
goto abort;
memset(rhash, 0, hsize * sizeof(xrecord_t *));
}
nrec = 0; nrec = 0;
if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) { if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {
for (top = blk + bsize; cur < top; ) { for (top = blk + bsize; cur < top; ) {
prev = cur; prev = cur;
hav = xdl_hash_record(&cur, top, xpp->flags); hav = xdl_hash_record(&cur, top, xpp->flags);
if (nrec >= narec) { if (nrec >= narec) {
narec *= 2; narec *= 2;
if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *))))
goto abort; goto abort;
recs = rrecs; recs = rrecs;
} }
if (!(crec = xdl_cha_alloc(&xdf->rcha))) if (!(crec = xdl_cha_alloc(&xdf->rcha)))
goto abort; goto abort;
crec->ptr = prev; crec->ptr = prev;
crec->size = (long) (cur - prev); crec->size = (long) (cur - prev);
crec->ha = hav; crec->ha = hav;
recs[nrec++] = crec; recs[nrec++] = crec;
if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
goto abort;
} }
} }
if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char))))
goto abort; goto abort;
memset(rchg, 0, (nrec + 2) * sizeof(char)); memset(rchg, 0, (nrec + 2) * sizeof(char));
if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long)))) if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long))))
goto abort; goto abort;
if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long)))) if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long))))
goto abort; goto abort;
xdf->nrec = nrec; xdf->nrec = nrec;
xdf->recs = recs; xdf->recs = recs;
xdf->hbits = hbits;
xdf->rhash = rhash;
xdf->rchg = rchg + 1; xdf->rchg = rchg + 1;
xdf->rindex = rindex; xdf->rindex = rindex;
xdf->nreff = 0; xdf->nreff = 0;
xdf->ha = ha; xdf->ha = ha;
xdf->dstart = 0; xdf->dstart = 0;
xdf->dend = nrec - 1; xdf->dend = nrec - 1;
/* use xdl_prepare_hashtable to set them */
xdf->hbits = 0;
xdf->rhash = NULL;
return 0; return 0;
abort: abort:
xdl_free(ha); xdl_free(ha);
xdl_free(rindex); xdl_free(rindex);
xdl_free(rchg); xdl_free(rchg);
xdl_free(rhash);
xdl_free(recs); xdl_free(recs);
xdl_cha_free(&xdf->rcha); xdl_cha_free(&xdf->rcha);
return -1; return -1;
} }
/*
* Adjust hash values for records (lines) in a file so the hash values become
* unique. This makes future calculation faster - they can just compare "ha"
* instead of comparing line content.
*/
static int xdl_prepare_hashtable(unsigned int pass, mmfile_t *mf,
xpparam_t const *xpp, xdlclassifier_t *cf, xdfile_t *xdf) {
xrecord_t **rhash = NULL;
long nrec = xdf->nrec;
unsigned int hbits;
long hsize;
long i;
hbits = xdl_hashbits((unsigned int) nrec);
hsize = 1 << hbits;
if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
goto abort;
memset(rhash, 0, hsize * sizeof(xrecord_t *));
for (i = 0; i < nrec; ++i) {
if (xdl_classify_record(pass, cf, rhash, hbits, xdf->recs[i]) < 0)
goto abort;
}
xdf->hbits = hbits;
xdf->rhash = rhash;
return 0;
abort:
xdl_free(rhash);
return -1;
}
static void xdl_free_ctx(xdfile_t *xdf) { static void xdl_free_ctx(xdfile_t *xdf) {
xdl_free(xdf->rhash); xdl_free(xdf->rhash);
xdl_free(xdf->rindex); xdl_free(xdf->rindex);
xdl_free(xdf->rchg - 1); xdl_free(xdf->rchg - 1);
xdl_free(xdf->ha); xdl_free(xdf->ha);
xdl_free(xdf->recs); xdl_free(xdf->recs);
if (xdl_trim_ends(&xe->xdf1, &xe->xdf2) < 0) { if (xdl_trim_ends(&xe->xdf1, &xe->xdf2) < 0) {
xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf2);
xdl_free_ctx(&xe->xdf1); xdl_free_ctx(&xe->xdf1);
xdl_free_classifier(&cf); xdl_free_classifier(&cf);
return -1; return -1;
} }
if (xdl_prepare_hashtable(1, mf1, xpp, &cf, &xe->xdf1) < 0) {
xdl_free_ctx(&xe->xdf1);
xdl_free_ctx(&xe->xdf2);
xdl_free_classifier(&cf);
return -1;
}
if (xdl_prepare_hashtable(2, mf2, xpp, &cf, &xe->xdf2) < 0) {
xdl_free_ctx(&xe->xdf1);
xdl_free_ctx(&xe->xdf2);
xdl_free_classifier(&cf);
return -1;
}
if (xdl_cleanup_records(&cf, &xe->xdf1, &xe->xdf2) < 0) { if (xdl_cleanup_records(&cf, &xe->xdf1, &xe->xdf2) < 0) {
xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf2);
xdl_free_ctx(&xe->xdf1); xdl_free_ctx(&xe->xdf1);
xdl_free_classifier(&cf); xdl_free_classifier(&cf);
return -1; return -1;
} }
xdl_free_classifier(&cf); xdl_free_classifier(&cf);