diff options
Diffstat (limited to 'libpatch_rewrite_diff2.c')
| -rw-r--r-- | libpatch_rewrite_diff2.c | 195 |
1 files changed, 195 insertions, 0 deletions
diff --git a/libpatch_rewrite_diff2.c b/libpatch_rewrite_diff2.c new file mode 100644 index 0000000..5af72ba --- /dev/null +++ b/libpatch_rewrite_diff2.c @@ -0,0 +1,195 @@ +/* See LICENSE file for copyright and license details. */ +#include "common.h" + + +#define REPETITION_MAX ((1U << (sizeof(int) * CHAR_BIT - CHAR_BIT)) - 1U) + + +static int +allocate(struct libpatch_diff2 **diff, size_t *difflen, size_t *r, size_t *w, int change) +{ +#define GROWTH 32U + + void *new; + size_t size; + + if (*w == *r) { + if (GROWTH > SIZE_MAX / sizeof(**diff) - *difflen) { + errno = ENOMEM; + return -1; + } + size = (*difflen + GROWTH) * sizeof(**diff); + new = realloc(*diff, size); + if (!new) + return -1; + *diff = new; + memmove(&(*diff)[*r + GROWTH], &(*diff)[*r], *difflen - *r); + *difflen += GROWTH; + *r += GROWTH; + } + + (*diff)[*w].change = (unsigned char)change; + (*diff)[*w].repetition = 0; + *w += 1; + return 0; +} + + +static int +putchange(struct libpatch_diff2 **diff, size_t *difflen, size_t *r, size_t *w, int change, size_t count) +{ + if (!count) + return 0; + if (*w && (*diff)[*w - 1].change == change && (*diff)[*w - 1].repetition < REPETITION_MAX) + goto start; + do { + if (allocate(diff, difflen, r, w, change)) + return -1; + start: + if (count > (size_t)(REPETITION_MAX - (*diff)[*w - 1].repetition)) { + count -= (size_t)(REPETITION_MAX - (*diff)[*w - 1].repetition); + (*diff)[*w - 1].repetition = REPETITION_MAX; + } else { + (*diff)[*w - 1].repetition += count; + break; + } + } while (count); + return 0; +} + + +static int +put(struct libpatch_diff2 **diff, size_t *difflen, + const struct libpatch_diff2_spec *spec, size_t *r, size_t *w, + size_t common, size_t onlyfile1, size_t onlyfile2, size_t changed) +{ + int a, b; + size_t an, bn, i; + size_t context, a_context, z_context; + + if (common) { + if (spec->full_context) { + return putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, common); + } else if (*w > 0 && *r < *difflen) { + context = MAX(spec->context_after + spec->context_before, spec->context_between); + if (common <= context) + return putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, common); + common -= a_context = MIN(spec->context_after, common); + common -= z_context = MIN(spec->context_before, common); + return -(putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, a_context) || + putchange(diff, difflen, r, w, LIBPATCH_DIFF2_SKIP, common) || + putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, z_context)); + } else if (*w > 0) { + common -= context = MIN(spec->context_after, common); + return -(putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, context) || + putchange(diff, difflen, r, w, LIBPATCH_DIFF2_SKIP, common)); + } else if (*r < *difflen) { + common -= context = MIN(spec->context_before, common); + return -(putchange(diff, difflen, r, w, LIBPATCH_DIFF2_SKIP, common) || + putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, context)); + } else { + return putchange(diff, difflen, r, w, LIBPATCH_DIFF2_SKIP, common); + } + + } else { + if (!spec->keep_split_changes) { + changed += MIN(onlyfile1, onlyfile2); + onlyfile1 -= changed; + onlyfile2 -= changed; + } + + if (spec->single_file_change_order == LIBPATCH_DIFF2_FILE1_ONLY_FIRST) { + a = LIBPATCH_DIFF2_FILE1_ONLY; + an = onlyfile1; + b = LIBPATCH_DIFF2_FILE2_ONLY; + bn = onlyfile2; + } else { + a = LIBPATCH_DIFF2_FILE2_ONLY; + an = onlyfile2; + b = LIBPATCH_DIFF2_FILE1_ONLY; + bn = onlyfile1; + } + + if (spec->two_file_change_order == LIBPATCH_DIFF2_TWO_FILE_CHANGES_BEFORE_SINGLE_FILE) + if (putchange(diff, difflen, r, w, LIBPATCH_DIFF2_TWO_FILE_CHANGE, changed)) + return -1; + + if (putchange(diff, difflen, r, w, a, an)) + return -1; + + if (spec->two_file_change_order == LIBPATCH_DIFF2_NO_TWO_FILE_CHANGES) { + if (putchange(diff, difflen, r, w, a, changed)) + return -1; + if (putchange(diff, difflen, r, w, b, changed)) + return -1; + } else if (spec->two_file_change_order == LIBPATCH_DIFF2_NO_TWO_FILE_CHANGES_INTERLEAVE) { + for (i = 0; i < changed; i++) { + if (putchange(diff, difflen, r, w, a, 1)) + return -1; + if (putchange(diff, difflen, r, w, b, 1)) + return -1; + } + } + + if (spec->two_file_change_order == LIBPATCH_DIFF2_TWO_FILE_CHANGES_BETWEEN_SINGLE_FILE) + if (putchange(diff, difflen, r, w, LIBPATCH_DIFF2_TWO_FILE_CHANGE, changed)) + return -1; + + if (putchange(diff, difflen, r, w, b, bn)) + return -1; + + if (spec->two_file_change_order == LIBPATCH_DIFF2_TWO_FILE_CHANGES_AFTER_SINGLE_FILE) + if (putchange(diff, difflen, r, w, LIBPATCH_DIFF2_TWO_FILE_CHANGE, changed)) + return -1; + + return 0; + } +} + + +int +libpatch_rewrite_diff2(struct libpatch_diff2 **diff, size_t *difflen, + const struct libpatch_diff2_spec *spec) +{ + size_t r, w = 0; + size_t saved0 = 0, saved1 = 0, saved2 = 0, saved3 = 0; + + for (r = 0; r < *difflen; r++) { + if ((*diff)[r].change == LIBPATCH_DIFF2_SKIP || + (*diff)[r].change == LIBPATCH_DIFF2_CONTEXT) { + if (saved1 || saved2) { + if (put(diff, difflen, spec, &r, &w, saved0, saved1, saved2, saved3)) + return -1; + saved1 = 0; + saved2 = 0; + saved3 = 0; + } + saved0 += (size_t)(*diff)[r].repetition; + } else { + if (saved0) { + if (put(diff, difflen, spec, &r, &w, saved0, saved1, saved2, saved3)) + return -1; + saved0 = 0; + } + if (spec->keep_split_changes) { + if ((*diff)[r].change == LIBPATCH_DIFF2_FILE1_ONLY) + saved1 += (size_t)(*diff)[r].repetition; + else if ((*diff)[r].change == LIBPATCH_DIFF2_FILE2_ONLY) + saved2 += (size_t)(*diff)[r].repetition; + else + saved3 += (size_t)(*diff)[r].repetition; + } else { + if ((*diff)[r].change != LIBPATCH_DIFF2_FILE2_ONLY) + saved1 += (size_t)(*diff)[r].repetition; + if ((*diff)[r].change != LIBPATCH_DIFF2_FILE1_ONLY) + saved2 += (size_t)(*diff)[r].repetition; + } + } + } + + if (put(diff, difflen, spec, &r, &w, saved0, saved1, saved2, saved3)) + return -1; + + *difflen = w; + return 0; +} |