| pulkit | |
| ryanmce |
| hg-reviewers |
| Automatic diff as part of commit; lint not applicable. |
| Automatic diff as part of commit; unit tests not applicable. |
| static inline int cmp(struct bdiff_line *a, struct bdiff_line *b) | static inline int cmp(struct bdiff_line *a, struct bdiff_line *b) | ||||
| { | { | ||||
| return a->hash != b->hash || a->len != b->len || | return a->hash != b->hash || a->len != b->len || | ||||
| memcmp(a->l, b->l, a->len); | memcmp(a->l, b->l, a->len); | ||||
| } | } | ||||
| static int equatelines(struct bdiff_line *a, int an, struct bdiff_line *b, | static int equatelines(struct bdiff_line *a, int an, struct bdiff_line *b, | ||||
| int bn) | int bn) | ||||
| { | { | ||||
| int i, j, buckets = 1, t, scale; | int i, j, buckets = 1, t, scale; | ||||
| struct pos *h = NULL; | struct pos *h = NULL; | ||||
| /* build a hash table of the next highest power of 2 */ | /* build a hash table of the next highest power of 2 */ | ||||
| while (buckets < bn + 1) | while (buckets < bn + 1) | ||||
| buckets *= 2; | buckets *= 2; | ||||
| } | } | ||||
| /* discard hash tables */ | /* discard hash tables */ | ||||
| free(h); | free(h); | ||||
| return 1; | return 1; | ||||
| } | } | ||||
| static int longest_match(struct bdiff_line *a, struct bdiff_line *b, | static int longest_match(struct bdiff_line *a, struct bdiff_line *b, | ||||
| struct pos *pos, | struct pos *pos, int a1, int a2, int b1, int b2, | ||||
| int a1, int a2, int b1, int b2, int *omi, int *omj) | int *omi, int *omj) | ||||
| { | { | ||||
| int mi = a1, mj = b1, mk = 0, i, j, k, half, bhalf; | int mi = a1, mj = b1, mk = 0, i, j, k, half, bhalf; | ||||
| /* window our search on large regions to better bound | /* window our search on large regions to better bound | ||||
| worst-case performance. by choosing a window at the end, we | worst-case performance. by choosing a window at the end, we | ||||
| reduce skipping overhead on the b chains. */ | reduce skipping overhead on the b chains. */ | ||||
| if (a2 - a1 > 30000) | if (a2 - a1 > 30000) | ||||
| a1 = a2 - 30000; | a1 = a2 - 30000; | ||||
| *omi = mi; | *omi = mi; | ||||
| *omj = mj; | *omj = mj; | ||||
| return mk; | return mk; | ||||
| } | } | ||||
| static struct bdiff_hunk *recurse(struct bdiff_line *a, struct bdiff_line *b, | static struct bdiff_hunk *recurse(struct bdiff_line *a, struct bdiff_line *b, | ||||
| struct pos *pos, | struct pos *pos, int a1, int a2, int b1, | ||||
| int a1, int a2, int b1, int b2, struct bdiff_hunk *l) | int b2, struct bdiff_hunk *l) | ||||
| { | { | ||||
| int i, j, k; | int i, j, k; | ||||
| while (1) { | while (1) { | ||||
| /* find the longest match in this chunk */ | /* find the longest match in this chunk */ | ||||
| k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j); | k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j); | ||||
| if (!k) | if (!k) | ||||
| return l; | return l; | ||||
| l->next = NULL; | l->next = NULL; | ||||
| /* tail-recursion didn't happen, so do equivalent iteration */ | /* tail-recursion didn't happen, so do equivalent iteration */ | ||||
| a1 = i + k; | a1 = i + k; | ||||
| b1 = j + k; | b1 = j + k; | ||||
| } | } | ||||
| } | } | ||||
| int bdiff_diff(struct bdiff_line *a, int an, struct bdiff_line *b, | int bdiff_diff(struct bdiff_line *a, int an, struct bdiff_line *b, int bn, | ||||
| int bn, struct bdiff_hunk *base) | struct bdiff_hunk *base) | ||||
| { | { | ||||
| struct bdiff_hunk *curr; | struct bdiff_hunk *curr; | ||||
| struct pos *pos; | struct pos *pos; | ||||
| int t, count = 0; | int t, count = 0; | ||||
| /* allocate and fill arrays */ | /* allocate and fill arrays */ | ||||
| t = equatelines(a, an, b, bn); | t = equatelines(a, an, b, bn); | ||||
| pos = (struct pos *)calloc(bn ? bn : 1, sizeof(struct pos)); | pos = (struct pos *)calloc(bn ? bn : 1, sizeof(struct pos)); | ||||