quark updated this revision to Diff 6456. quark edited the summary of this revision. quark retitled this revision from "xdiff: remove patience and histogram diffs" to "xdiff: remove patience and histogram diff algorithms".
REPOSITORY rHG Mercurial CHANGES SINCE LAST UPDATE https://phab.mercurial-scm.org/D2573?vs=6416&id=6456 REVISION DETAIL https://phab.mercurial-scm.org/D2573 AFFECTED FILES mercurial/third-party/xdiff/xdiff.h mercurial/third-party/xdiff/xdiffi.c mercurial/third-party/xdiff/xhistogram.c mercurial/third-party/xdiff/xpatience.c mercurial/third-party/xdiff/xprepare.c CHANGE DETAILS diff --git a/mercurial/third-party/xdiff/xprepare.c b/mercurial/third-party/xdiff/xprepare.c --- a/mercurial/third-party/xdiff/xprepare.c +++ b/mercurial/third-party/xdiff/xprepare.c @@ -27,7 +27,6 @@ #define XDL_MAX_EQLIMIT 1024 #define XDL_SIMSCAN_WINDOW 100 #define XDL_GUESS_NLINES1 256 -#define XDL_GUESS_NLINES2 20 typedef struct s_xdlclass { @@ -181,9 +180,7 @@ if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) goto abort; - if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) - hbits = hsize = 0; - else { + { hbits = xdl_hashbits((unsigned int) narec); hsize = 1 << hbits; if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) @@ -209,8 +206,7 @@ crec->ha = hav; recs[nrec++] = crec; - if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && - xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) + if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) goto abort; } } @@ -266,21 +262,12 @@ memset(&cf, 0, sizeof(cf)); - /* - * For histogram diff, we can afford a smaller sample size and - * thus a poorer estimate of the number of lines, as the hash - * table (rhash) won't be filled up/grown. The number of lines - * (nrecs) will be updated correctly anyway by - * xdl_prepare_ctx(). - */ - sample = (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF - ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1); + sample = XDL_GUESS_NLINES1; enl1 = xdl_guess_lines(mf1, sample) + 1; enl2 = xdl_guess_lines(mf2, sample) + 1; - if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF && - xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) + if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) return -1; if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) { @@ -295,18 +282,14 @@ return -1; } - if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && - (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && - xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { - + if (xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf1); xdl_free_classifier(&cf); return -1; } - if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) - xdl_free_classifier(&cf); + xdl_free_classifier(&cf); return 0; } diff --git a/mercurial/third-party/xdiff/xpatience.c b/mercurial/third-party/xdiff/xpatience.c deleted file mode 100644 --- a/mercurial/third-party/xdiff/xpatience.c +++ /dev/null @@ -1,390 +0,0 @@ -/* - * LibXDiff by Davide Libenzi ( File Differential Library ) - * Copyright (C) 2003-2016 Davide Libenzi, Johannes E. Schindelin - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, see - * <http://www.gnu.org/licenses/>. - * - * Davide Libenzi <davi...@xmailserver.org> - * - */ -#include "xinclude.h" -#include "xtypes.h" -#include "xdiff.h" - -/* - * The basic idea of patience diff is to find lines that are unique in - * both files. These are intuitively the ones that we want to see as - * common lines. - * - * The maximal ordered sequence of such line pairs (where ordered means - * that the order in the sequence agrees with the order of the lines in - * both files) naturally defines an initial set of common lines. - * - * Now, the algorithm tries to extend the set of common lines by growing - * the line ranges where the files have identical lines. - * - * Between those common lines, the patience diff algorithm is applied - * recursively, until no unique line pairs can be found; these line ranges - * are handled by the well-known Myers algorithm. - */ - -#define NON_UNIQUE ULONG_MAX - -/* - * This is a hash mapping from line hash to line numbers in the first and - * second file. - */ -struct hashmap { - int nr, alloc; - struct entry { - unsigned long hash; - /* - * 0 = unused entry, 1 = first line, 2 = second, etc. - * line2 is NON_UNIQUE if the line is not unique - * in either the first or the second file. - */ - unsigned long line1, line2; - /* - * "next" & "previous" are used for the longest common - * sequence; - * initially, "next" reflects only the order in file1. - */ - struct entry *next, *previous; - - /* - * If 1, this entry can serve as an anchor. See - * Documentation/diff-options.txt for more information. - */ - unsigned anchor : 1; - } *entries, *first, *last; - /* were common records found? */ - unsigned long has_matches; - mmfile_t *file1, *file2; - xdfenv_t *env; - xpparam_t const *xpp; -}; - -static int is_anchor(xpparam_t const *xpp, const char *line) -{ - int i; - for (i = 0; i < xpp->anchors_nr; i++) { - if (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i]))) - return 1; - } - return 0; -} - -/* The argument "pass" is 1 for the first file, 2 for the second. */ -static void insert_record(xpparam_t const *xpp, 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; - /* - * After xdl_prepare_env() (or more precisely, due to - * xdl_classify_record()), the "ha" member of the records (AKA lines) - * is _not_ the hash anymore, but a linearized version of it. In - * other words, the "ha" member is guaranteed to start with 0 and - * the second record's ha can only be 0 or 1, etc. - * - * So we multiply ha by 2 in the hope that the hashing was - * "unique enough". - */ - 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; - map->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr); - 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++; -} - -/* - * This function has to be called for each recursion into the inter-hunk - * parts, as previously non-unique lines can become unique when being - * restricted to a smaller part of the files. - * - * It is assumed that env has been prepared using xdl_prepare(). - */ -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; - - /* We know exactly how large we want the hash map */ - 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)); - - /* First, fill with entries from the first file */ - while (count1--) - insert_record(xpp, line1++, result, 1); - - /* Then search for matches in the second file */ - while (count2--) - insert_record(xpp, line2++, result, 2); - - return 0; -} - -/* - * Find the longest sequence with a smaller last element (meaning a smaller - * line2, as we construct the sequence with entries ordered by line1). - */ -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 - left) / 2; - /* by construction, no two entries can be equal */ - if (sequence[middle]->line2 > entry->line2) - right = middle; - else - left = middle; - } - /* return the index in "sequence", _not_ the sequence length */ - return left; -} - -/* - * The idea is to start with the list of common unique lines sorted by - * the order in file1. For each of these pairs, the longest (partial) - * sequence whose last element's line2 is smaller is determined. - * - * For efficiency, the sequences are kept in a list containing exactly one - * item per sequence length: the sequence with the smallest last - * element (in terms of line2). - */ -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; - - /* - * If not -1, this entry in sequence must never be overridden. - * Therefore, overriding entries before this has no effect, so - * do not do that either. - */ - int anchor_i = -1; - - 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]; - ++i; - if (i <= anchor_i) - continue; - sequence[i] = entry; - if (entry->anchor) { - anchor_i = i; - longest = anchor_i + 1; - } else if (i == longest) { - longest++; - } - } - - /* No common unique lines were found */ - if (!longest) { - xdl_free(sequence); - return NULL; - } - - /* Iterate starting at the last element, adjusting the "next" members */ - 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 (;;) { - /* Try to grow the line ranges of common lines */ - 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++; - } - - /* Recurse */ - 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); -} - -/* - * Recursively find the longest common sequence of unique lines, - * and if none was found, ask xdl_do_diff() to do the job. - * - * This function assumes that env was prepared with xdl_prepare_env(). - */ -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; - - /* trivial case: one side is empty */ - 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; - - /* are there any matching lines at all? */ - 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; - - /* environment is cleaned up in xdl_diff() */ - return patience_diff(file1, file2, xpp, env, - 1, env->xdf1.nrec, 1, env->xdf2.nrec); -} diff --git a/mercurial/third-party/xdiff/xhistogram.c b/mercurial/third-party/xdiff/xhistogram.c deleted file mode 100644 --- a/mercurial/third-party/xdiff/xhistogram.c +++ /dev/null @@ -1,363 +0,0 @@ -/* - * Copyright (C) 2010, Google Inc. - * and other copyright owners as documented in JGit's IP log. - * - * This program and the accompanying materials are made available - * under the terms of the Eclipse Distribution License v1.0 which - * accompanies this distribution, is reproduced below, and is - * available at http://www.eclipse.org/org/documents/edl-v10.php - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or - * without modification, are permitted provided that the following - * conditions are met: - * - * - Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * - Redistributions in binary form must reproduce the above - * copyright notice, this list of conditions and the following - * disclaimer in the documentation and/or other materials provided - * with the distribution. - * - * - Neither the name of the Eclipse Foundation, Inc. nor the - * names of its contributors may be used to endorse or promote - * products derived from this software without specific prior - * written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND - * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, - * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER - * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF - * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#include "xinclude.h" -#include "xtypes.h" -#include "xdiff.h" - -#define MAX_PTR UINT_MAX -#define MAX_CNT UINT_MAX - -#define LINE_END(n) (line##n + count##n - 1) -#define LINE_END_PTR(n) (*line##n + *count##n - 1) - -struct histindex { - struct record { - unsigned int ptr, cnt; - struct record *next; - } **records, /* an occurrence */ - **line_map; /* map of line to record chain */ - chastore_t rcha; - unsigned int *next_ptrs; - unsigned int table_bits, - records_size, - line_map_size; - - unsigned int max_chain_length, - key_shift, - ptr_shift; - - unsigned int cnt, - has_common; - - xdfenv_t *env; - xpparam_t const *xpp; -}; - -struct region { - unsigned int begin1, end1; - unsigned int begin2, end2; -}; - -#define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift]) - -#define NEXT_PTR(index, ptr) \ - (index->next_ptrs[(ptr) - index->ptr_shift]) - -#define CNT(index, ptr) \ - ((LINE_MAP(index, ptr))->cnt) - -#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) -{ - return r1->ha == r2->ha && - xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size, - xpp->flags); -} - -#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))) - -#define TABLE_HASH(index, side, line) \ - XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits) - -static int scanA(struct histindex *index, int line1, int count1) -{ - unsigned int ptr, tbl_idx; - unsigned int chain_len; - struct record **rec_chain, *rec; - - for (ptr = LINE_END(1); line1 <= ptr; ptr--) { - tbl_idx = TABLE_HASH(index, 1, ptr); - rec_chain = index->records + tbl_idx; - rec = *rec_chain; - - chain_len = 0; - while (rec) { - if (CMP(index, 1, rec->ptr, 1, ptr)) { - /* - * ptr is identical to another element. Insert - * it onto the front of the existing element - * chain. - */ - NEXT_PTR(index, ptr) = rec->ptr; - rec->ptr = ptr; - /* cap rec->cnt at MAX_CNT */ - rec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1); - LINE_MAP(index, ptr) = rec; - goto continue_scan; - } - - rec = rec->next; - chain_len++; - } - - if (chain_len == index->max_chain_length) - return -1; - - /* - * This is the first time we have ever seen this particular - * element in the sequence. Construct a new chain for it. - */ - if (!(rec = xdl_cha_alloc(&index->rcha))) - return -1; - rec->ptr = ptr; - rec->cnt = 1; - rec->next = *rec_chain; - *rec_chain = rec; - LINE_MAP(index, ptr) = rec; - -continue_scan: - ; /* no op */ - } - - return 0; -} - -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)]; - unsigned int as, ae, bs, be, np, rc; - int should_break; - - for (; rec; rec = rec->next) { - if (rec->cnt > index->cnt) { - if (!index->has_common) - index->has_common = CMP(index, 1, rec->ptr, 2, b_ptr); - continue; - } - - as = rec->ptr; - if (!CMP(index, 1, as, 2, b_ptr)) - continue; - - index->has_common = 1; - for (;;) { - should_break = 0; - np = NEXT_PTR(index, as); - bs = b_ptr; - ae = as; - be = bs; - rc = rec->cnt; - - while (line1 < as && line2 < bs - && CMP(index, 1, as - 1, 2, bs - 1)) { - as--; - bs--; - if (1 < rc) - rc = XDL_MIN(rc, CNT(index, as)); - } - while (ae < LINE_END(1) && be < LINE_END(2) - && CMP(index, 1, ae + 1, 2, be + 1)) { - ae++; - be++; - if (1 < rc) - rc = XDL_MIN(rc, CNT(index, ae)); - } - - if (b_next <= be) - b_next = be + 1; - if (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) { - lcs->begin1 = as; - lcs->begin2 = bs; - lcs->end1 = ae; - lcs->end2 = be; - index->cnt = rc; - } - - if (np == 0) - break; - - while (np <= ae) { - np = NEXT_PTR(index, np); - if (np == 0) { - should_break = 1; - break; - } - } - - if (should_break) - break; - - as = np; - } - } - return b_next; -} - -static int find_lcs(struct histindex *index, struct region *lcs, - int line1, int count1, int line2, int count2) { - int b_ptr; - - if (scanA(index, line1, count1)) - return -1; - - 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); - - return index->has_common && index->max_chain_length < index->cnt; -} - -static int fall_back_to_classic_diff(struct histindex *index, - int line1, int count1, int line2, int count2) -{ - xpparam_t xpp; - xpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; - - return xdl_fall_back_diff(index->env, &xpp, - line1, count1, line2, count2); -} - -static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env, - int line1, int count1, int line2, int count2) -{ - struct histindex index; - struct region lcs; - int 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.env = env; - index.xpp = xpp; - - index.records = NULL; - index.line_map = NULL; - /* in case of early xdl_cha_free() */ - index.rcha.head = NULL; - - index.table_bits = xdl_hashbits(count1); - sz = index.records_size = 1 << index.table_bits; - sz *= sizeof(struct record *); - if (!(index.records = (struct record **) xdl_malloc(sz))) - goto cleanup; - memset(index.records, 0, sz); - - sz = index.line_map_size = count1; - sz *= sizeof(struct record *); - if (!(index.line_map = (struct record **) xdl_malloc(sz))) - goto cleanup; - memset(index.line_map, 0, sz); - - sz = index.line_map_size; - sz *= sizeof(unsigned int); - if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz))) - goto cleanup; - memset(index.next_ptrs, 0, sz); - - /* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */ - if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0) - goto cleanup; - - index.ptr_shift = line1; - index.max_chain_length = 64; - - 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); - else { - if (lcs.begin1 == 0 && lcs.begin2 == 0) { - while (count1--) - env->xdf1.rchg[line1++ - 1] = 1; - while (count2--) - env->xdf2.rchg[line2++ - 1] = 1; - result = 0; - } else { - result = histogram_diff(xpp, env, - 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; - } - } - -cleanup: - xdl_free(index.records); - xdl_free(index.line_map); - xdl_free(index.next_ptrs); - xdl_cha_free(&index.rcha); - - return result; -} - -int xdl_do_histogram_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 histogram_diff(xpp, env, - env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1, - env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1); -} diff --git a/mercurial/third-party/xdiff/xdiffi.c b/mercurial/third-party/xdiff/xdiffi.c --- a/mercurial/third-party/xdiff/xdiffi.c +++ b/mercurial/third-party/xdiff/xdiffi.c @@ -328,12 +328,6 @@ xdalgoenv_t xenv; diffdata_t dd1, dd2; - if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) - return xdl_do_patience_diff(mf1, mf2, xpp, xe); - - if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) - return xdl_do_histogram_diff(mf1, mf2, xpp, xe); - if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) { return -1; diff --git a/mercurial/third-party/xdiff/xdiff.h b/mercurial/third-party/xdiff/xdiff.h --- a/mercurial/third-party/xdiff/xdiff.h +++ b/mercurial/third-party/xdiff/xdiff.h @@ -27,6 +27,8 @@ extern "C" { #endif /* #ifdef __cplusplus */ +#include <stddef.h> /* size_t */ + /* xpparm_t.flags */ #define XDF_NEED_MINIMAL (1 << 0) @@ -41,11 +43,6 @@ #define XDF_IGNORE_BLANK_LINES (1 << 7) -#define XDF_PATIENCE_DIFF (1 << 14) -#define XDF_HISTOGRAM_DIFF (1 << 15) -#define XDF_DIFF_ALGORITHM_MASK (XDF_PATIENCE_DIFF | XDF_HISTOGRAM_DIFF) -#define XDF_DIFF_ALG(x) ((x) & XDF_DIFF_ALGORITHM_MASK) - #define XDF_INDENT_HEURISTIC (1 << 23) /* xdemitconf_t.flags */ To: ryanmce, #hg-reviewers Cc: mercurial-devel _______________________________________________ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
