commit - c8846eb959c22c43dd5f8d9193b7e0c83c31b8af
commit + 6c8c5d3f0b6b2ba6c23acd67179fd37e8f2af66b
blob - 9dc641cf345f7bda61a2e56012332d68e357bddb
blob + f49a6893b6847f02d5127764222375f1184d051d
--- include/diff_main.h
+++ include/diff_main.h
ARRAYLIST(struct diff_atom) atoms;
struct diff_data *root;
+ struct diff_data *current;
+ void *algo_data;
int diff_flags;
blob - e9088e91a37fcda61b2cf9cd6487f3abe30adee4
blob + 5c8fd1fc7ae45e166e7af7a09a3e9b4cfa0f47b9
--- lib/diff_internal.h
+++ lib/diff_internal.h
* atoms. When hashes match, we still need to compare entire atoms to
* find out whether they are indeed identical or not. */
unsigned int hash;
-
- /* State for the Patience Diff algorithm */
- /* TODO: keep a separate array for the patience state */
- struct {
- bool unique_in_both;
- struct diff_atom *pos_in_other;
- struct diff_atom *prev_stack;
- struct diff_range identical_lines;
- } patience;
};
int
blob - e7f728f1729206b8262ad23227da9f0d7d0dff66
blob + 90e4bb8ef6330a66994c94fc1ecbd104f42a3846
--- lib/diff_patience.c
+++ lib/diff_patience.c
#include "diff_internal.h"
#include "diff_debug.h"
+/* Per-atom state for the Patience Diff algorithm */
+struct atom_patience {
+ bool unique_in_both;
+ struct diff_atom *pos_in_other;
+ struct diff_atom *prev_stack;
+ struct diff_range identical_lines;
+};
+
+/* A diff_atom has a backpointer to the root diff_data. That points to the
+ * current diff_data, a possibly smaller section of the root. That current
+ * diff_data->algo_data is a pointer to an array of struct atom_patience. The
+ * atom's index in current diff_data gives the index in the atom_patience array.
+ */
+#define PATIENCE(ATOM) \
+ (((struct atom_patience*)((ATOM)->root->current->algo_data))\
+ [diff_atom_idx((ATOM)->root->current, ATOM)])
+
int diff_atoms_qsort_compar(const void *_a, const void *_b)
{
const struct diff_atom *a = *(struct diff_atom**)_a;
unsigned int i;
unsigned int unique_in_both_count = 0;
int rc;
+ left->err = 0;
+ right->err = 0;
left->root->err = 0;
right->root->err = 0;
diff_data_foreach_atom(a, left) {
if ((count_first_side == 1)
&& (count_other_side == 1)) {
b = all_atoms[i+1];
- a->patience.unique_in_both = true;
- a->patience.pos_in_other = b;
- b->patience.unique_in_both = true;
- b->patience.pos_in_other = a;
+ PATIENCE(a).unique_in_both = true;
+ PATIENCE(a).pos_in_other = b;
+ PATIENCE(b).unique_in_both = true;
+ PATIENCE(b).pos_in_other = a;
unique_in_both_count++;
}
}
next_l_idx = l_idx + 1;
struct diff_atom *l = &left->atoms.head[l_idx];
- if (!l->patience.unique_in_both)
+ if (!PATIENCE(l).unique_in_both)
continue;
debug("check identical lines around ");
debug_dump_atom(left, right, l);
- unsigned int r_idx = diff_atom_idx(right,
- l->patience.pos_in_other);
+ unsigned int r_idx = diff_atom_idx(right, PATIENCE(l).pos_in_other);
struct diff_range identical_l;
struct diff_range identical_r;
break;
l_end = &left->atoms.head[identical_l.end];
r_end = &right->atoms.head[identical_r.end];
- if (!l_end->patience.unique_in_both)
+ if (!PATIENCE(l_end).unique_in_both)
continue;
/* Part of a chunk of identical lines, remove from
* listing of unique_in_both lines */
- l_end->patience.unique_in_both = false;
- r_end->patience.unique_in_both = false;
+ PATIENCE(l_end).unique_in_both = false;
+ PATIENCE(r_end).unique_in_both = false;
(*unique_in_both_count)--;
}
- l->patience.identical_lines = identical_l;
- l->patience.pos_in_other->patience.identical_lines =
+ PATIENCE(l).identical_lines = identical_l;
+ PATIENCE(PATIENCE(l).pos_in_other).identical_lines =
identical_r;
l_min = identical_l.end;
r_min = identical_r.end;
- if (!diff_range_empty(&l->patience.identical_lines)) {
+ if (!diff_range_empty(&PATIENCE(l).identical_lines)) {
debug("common-unique line at l=%u r=%u swallowed"
" identical lines l=%u-%u r=%u-%u\n",
l_idx, r_idx,
while (lo < hi) {
unsigned int mid = (lo + hi) >> 1;
- if (patience_stacks[mid]->patience.pos_in_other
- < atom->patience.pos_in_other)
+ if (PATIENCE(patience_stacks[mid]).pos_in_other
+ < PATIENCE(atom).pos_in_other)
lo = mid + 1;
else
hi = mid;
struct diff_state *state)
{
int rc;
-
struct diff_data *left = &state->left;
struct diff_data *right = &state->right;
-
+ struct atom_patience *atom_patience_left =
+ calloc(left->atoms.len, sizeof(struct atom_patience));
+ struct atom_patience *atom_patience_right =
+ calloc(right->atoms.len, sizeof(struct atom_patience));
unsigned int unique_in_both_count;
+ struct diff_atom **lcs = NULL;
debug("\n** %s\n", __func__);
+ left->root->current = left;
+ right->root->current = right;
+ left->algo_data = atom_patience_left;
+ right->algo_data = atom_patience_right;
+
/* Find those lines that appear exactly once in 'left' and exactly once
* in 'right'. */
rc = diff_atoms_mark_unique_in_both_by_qsort(left, right,
&unique_in_both_count);
if (rc)
- return rc;
+ goto free_and_exit;
debug("unique_in_both_count %u\n", unique_in_both_count);
debug("left:\n");
if (!unique_in_both_count) {
/* Cannot apply Patience, tell the caller to use fallback_algo
* instead. */
- return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
+ rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
+ goto free_and_exit;
}
rc = diff_atoms_swallow_identical_neighbors(left, right,
&unique_in_both_count);
if (rc)
- return rc;
+ goto free_and_exit;
debug("After swallowing identical neighbors: unique_in_both = %u\n",
unique_in_both_count);
/* An array of Longest Common Sequence is the result of the below
* subscope: */
unsigned int lcs_count = 0;
- struct diff_atom **lcs = NULL;
struct diff_atom *lcs_tail = NULL;
{
struct diff_atom *atom;
struct diff_atom **uniques_end = uniques;
diff_data_foreach_atom(atom, left) {
- if (!atom->patience.unique_in_both)
+ if (!PATIENCE(atom).unique_in_both)
continue;
*uniques_end = atom;
uniques_end++;
* line number is derived from the atom*, which are array items
* and hence reflect the relative position in the source file.
* So we got the common-uniques from 'left' and sort them
- * according to atom->patience.pos_in_other. */
+ * according to PATIENCE(atom).pos_in_other. */
unsigned int i;
for (i = 0; i < unique_in_both_count; i++) {
atom = uniques[i];
/* Record a back reference to the next stack on the
* left, which will form the final longest sequence
* later. */
- atom->patience.prev_stack = target_stack ?
+ PATIENCE(atom).prev_stack = target_stack ?
patience_stacks[target_stack - 1] : NULL;
}
lcs_count = patience_stacks_count;
/* uniques and patience_stacks are no longer needed.
- * Backpointers are in atom->patience.prev_stack */
+ * Backpointers are in PATIENCE(atom).prev_stack */
free(atom_pointers);
}
lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
struct diff_atom *atom;
- for (atom = lcs_tail; atom; atom = atom->patience.prev_stack, lcs_backtrace_pos--) {
+ for (atom = lcs_tail; atom; atom = PATIENCE(atom).prev_stack, lcs_backtrace_pos--) {
assert(lcs_backtrace_pos >= lcs);
*lcs_backtrace_pos = atom;
}
if (i < lcs_count) {
atom = lcs[i];
- atom_r = atom->patience.pos_in_other;
+ atom_r = PATIENCE(atom).pos_in_other;
debug("lcs[%u] = left[%u] = right[%u]\n", i,
diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
- left_idx = atom->patience.identical_lines.start;
- right_idx = atom_r->patience.identical_lines.start;
+ left_idx = PATIENCE(atom).identical_lines.start;
+ right_idx = PATIENCE(atom_r).identical_lines.start;
debug(" identical lines l %u-%u r %u-%u\n",
- atom->patience.identical_lines.start, atom->patience.identical_lines.end,
- atom_r->patience.identical_lines.start, atom_r->patience.identical_lines.end);
+ PATIENCE(atom).identical_lines.start, PATIENCE(atom).identical_lines.end,
+ PATIENCE(atom_r).identical_lines.start, PATIENCE(atom_r).identical_lines.end);
} else {
atom = NULL;
atom_r = NULL;
left_atom, left_section_len,
right_atom,
right_section_len))
- goto return_rc;
+ goto free_and_exit;
} else if (left_section_len && !right_section_len) {
/* Only left atoms and none on the right, they form a
* "minus" chunk, then. */
if (!diff_state_add_chunk(state, true,
left_atom, left_section_len,
right_atom, 0))
- goto return_rc;
+ goto free_and_exit;
} else if (!left_section_len && right_section_len) {
/* No left atoms, only atoms on the right, they form a
* "plus" chunk, then. */
if (!diff_state_add_chunk(state, true,
left_atom, 0,
right_atom, right_section_len))
- goto return_rc;
+ goto free_and_exit;
}
/* else: left_section_len == 0 and right_section_len == 0, i.e.
* nothing here. */
void *ok;
ok = diff_state_add_chunk(state, true,
left->atoms.head
- + atom->patience.identical_lines.start,
- diff_range_len(&atom->patience.identical_lines),
+ + PATIENCE(atom).identical_lines.start,
+ diff_range_len(&PATIENCE(atom).identical_lines),
right->atoms.head
- + atom_r->patience.identical_lines.start,
- diff_range_len(&atom_r->patience.identical_lines));
+ + PATIENCE(atom_r).identical_lines.start,
+ diff_range_len(&PATIENCE(atom_r).identical_lines));
if (!ok)
- goto return_rc;
- left_pos = atom->patience.identical_lines.end;
- right_pos = atom_r->patience.identical_lines.end;
+ goto free_and_exit;
+ left_pos = PATIENCE(atom).identical_lines.end;
+ right_pos = PATIENCE(atom_r).identical_lines.end;
} else {
left_pos = left_idx + 1;
right_pos = right_idx + 1;
rc = DIFF_RC_OK;
-return_rc:
- free(lcs);
+free_and_exit:
+ left->root->current = NULL;
+ right->root->current = NULL;
+ free(atom_patience_left);
+ free(atom_patience_right);
+ if (lcs)
+ free(lcs);
return rc;
}
