commit 727b847b7a003fb900f714a515563b73438576cf from: Martin Pieuchot date: Fri Mar 20 19:19:34 2020 UTC Abstract atoms.len commit - 2f5ea1f2666b6fd29c2d1d96f9c4078dba7c1002 commit + 727b847b7a003fb900f714a515563b73438576cf blob - 54bfbd32659848193843158b18d13f6d04d16db9 blob + c13b953f2a07e3aad86e65bfeef0505ccd339ab8 --- debug.h +++ debug.h @@ -77,7 +77,7 @@ dump_atoms(const struct diff_data *d, struct diff_atom static inline void dump(struct diff_data *dd) { - dump_atoms(dd, dd->atoms.head, dd->atoms.len); + dump_atoms(dd, DD_ATOM_FIRST(dd), DD_ATOM_NB(dd)); } static inline void @@ -86,18 +86,18 @@ dump_myers_graph(const struct diff_data *l, const stru int x, y; print(" "); - for (x = 0; x <= l->atoms.len; x++) + for (x = 0; x <= DD_ATOM_NB(l); x++) print("%2d", x); print("\n"); - for (y = 0; y <= r->atoms.len; y++) { + for (y = 0; y <= DD_ATOM_NB(r); y++) { print("%2d ", y); - for (x = 0; x <= l->atoms.len; x++) { + for (x = 0; x <= DD_ATOM_NB(l); x++) { /* print d advancements from kd, if any. */ int d = -1; if (kd) { - int max = l->atoms.len + r->atoms.len; + int max = DD_ATOM_NB(l) + DD_ATOM_NB(r); size_t kd_len = max + 1 + max; int *kd_pos = kd; int di; @@ -120,15 +120,15 @@ dump_myers_graph(const struct diff_data *l, const stru print("%d", d); else print("o"); - if (x < l->atoms.len && d < 10) + if (x < DD_ATOM_NB(l) && d < 10) print("-"); } print("\n"); - if (y == r->atoms.len) + if (y == DD_ATOM_NB(r)) break; print(" "); - for (x = 0; x < l->atoms.len; x++) { + for (x = 0; x < DD_ATOM_NB(l); x++) { if (diff_atom_same(DD_ATOM_AT(l, x), DD_ATOM_AT(r, y))) print("|\\"); else @@ -142,7 +142,7 @@ static inline void debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r, int *kd) { - if (l->atoms.len > 99 || r->atoms.len > 99) + if (DD_ATOM_NB(l) > 99 || DD_ATOM_NB(r) > 99) return; dump_myers_graph(l, r, kd); } blob - c14efef129560f59679e467d0887f73cde78850d blob + 1a556f7d0464e0bb4e03a1fa3ce0b45209e09ae9 --- diff_main.c +++ diff_main.c @@ -118,8 +118,8 @@ diff_algo_none(const struct diff_algo_config *algo_con debug_dump_myers_graph(&state->left, &state->right, NULL); /* Add a chunk of equal lines, if any */ - while (equal_atoms < state->left.atoms.len && - equal_atoms < state->right.atoms.len && + while (equal_atoms < DD_ATOM_NB(&state->left) && + equal_atoms < DD_ATOM_NB(&state->right) && diff_atom_same(DD_ATOM_AT(&state->left, equal_atoms), DD_ATOM_AT(&state->right, equal_atoms))) equal_atoms++; @@ -132,20 +132,20 @@ diff_algo_none(const struct diff_algo_config *algo_con } /* Add a "minus" chunk with all lines from the left. */ - if (equal_atoms < state->left.atoms.len) { + if (equal_atoms < DD_ATOM_NB(&state->left)) { if (!diff_state_add_chunk(state, true, DD_ATOM_AT(&state->left, equal_atoms), - state->left.atoms.len - equal_atoms, + DD_ATOM_NB(&state->left) - equal_atoms, NULL, 0)) return DIFF_RC_ENOMEM; } /* Add a "plus" chunk with all lines from the right. */ - if (equal_atoms < state->right.atoms.len) { + if (equal_atoms < DD_ATOM_NB(&state->right)) { if (!diff_state_add_chunk(state, true, NULL, 0, DD_ATOM_AT(&state->right, equal_atoms), - state->right.atoms.len - equal_atoms)) + DD_ATOM_NB(&state->right) - equal_atoms)) return DIFF_RC_ENOMEM; } return DIFF_RC_OK; @@ -258,9 +258,9 @@ diff_main(const struct diff_config *config, .recursion_depth_left = config->max_recursion_depth ? : 1024, }; diff_data_init_subsection(&state.left, &result->left, - result->left.atoms.head, result->left.atoms.len); + DD_ATOM_FIRST(&result->left), DD_ATOM_NB(&result->left)); diff_data_init_subsection(&state.right, &result->right, - result->right.atoms.head, result->right.atoms.len); + DD_ATOM_FIRST(&result->right), DD_ATOM_NB(&result->right)); result->rc = diff_run_algo(config->algo, &state); blob - 4ed4751e18170b7687cd69954a5816da10a6743d blob + 292966ca8047daf16d8a927e173d0281df2ea867 --- diff_main.h +++ diff_main.h @@ -134,9 +134,19 @@ void diff_data_free(struct diff_data *diff_data); (_atom)++) /* - * Get Atom from `_dd' at given `_index'. + * Number of atoms in a given `_dd' */ +#define DD_ATOM_NB(_dd) ((_dd)->atoms.len) + +/* + * Atom from `_dd' at given `_index'. + */ #define DD_ATOM_AT(_dd, _index) (&(_dd)->atoms.head[(_index)]) + +/* + * First Atom from `_dd' + */ +#define DD_ATOM_FIRST(_dd) DD_ATOM_AT(_dd, 0) /* * Atom index within `_dd'. @@ -145,7 +155,7 @@ void diff_data_free(struct diff_data *diff_data); * (starting with 0). */ #define DD_ATOM_INDEX(_dd, _atom) \ - ((_atom) != NULL ? (_atom) - ((_dd)->atoms.head) : (_dd)->atoms.len) + ((_atom) != NULL ? (_atom) - DD_ATOM_FIRST(_dd) : DD_ATOM_NB(_dd)) /* * Atom index in the entire file. @@ -162,9 +172,9 @@ void diff_data_free(struct diff_data *diff_data); */ #define DD_ATOM_FOREACH(_atom, _dd, _index) \ for ((_atom) = DD_ATOM_AT(_dd, _index); \ - (_atom) && \ - ((_atom) >= (_dd)->atoms.head) && \ - ((_atom) - (_dd)->atoms.head < (_dd)->atoms.len); \ + (_atom) != NULL && \ + ((_atom) >= DD_ATOM_FIRST(_dd)) && \ + (DD_ATOM_INDEX(_dd, _atom) < DD_ATOM_NB(_dd)); \ (_atom)++) /* blob - 12558d34034a00395ecdcfed676f506cb93e5046 blob + 5f17805145c8c9c1632284d791685c83b1f01d68 --- diff_myers.c +++ diff_myers.c @@ -221,7 +221,7 @@ static void diff_divide_myers_forward(struct diff_data *left, struct diff_data *right, int *kd_forward, int *kd_backward, int d, struct diff_box *meeting_snake) { - int delta = (int)right->atoms.len - (int)left->atoms.len; + int delta = (int)DD_ATOM_NB(right) - (int)DD_ATOM_NB(left); int prev_x; int prev_y; int k; @@ -231,17 +231,17 @@ diff_divide_myers_forward(struct diff_data *left, stru debug_dump_myers_graph(left, right, NULL); for (k = d; k >= -d; k -= 2) { - if (k < -(int)right->atoms.len || k > (int)left->atoms.len) { + if (k < -(int)DD_ATOM_NB(right) || k > (int)DD_ATOM_NB(left)) { /* * This diagonal is completely outside of the Myers * graph, don't calculate it. */ - if (k < -(int)right->atoms.len) - debug(" %d k < -(int)right->atoms.len %d\n", k, - -(int)right->atoms.len); + if (k < -(int)DD_ATOM_NB(right)) + debug(" %d k < -(int)DD_ATOM_NB(right) %d\n", k, + -(int)DD_ATOM_NB(right)); else - debug(" %d k > left->atoms.len %d\n", k, - left->atoms.len); + debug(" %d k > DD_ATOM_NB(left) %d\n", k, + DD_ATOM_NB(left)); if (k < 0) { /* * We are traversing negatively, and already @@ -289,7 +289,7 @@ diff_divide_myers_forward(struct diff_data *left, stru * k + 1 if k - 1 is outside the graph. */ else if (k > -d && (k == d || - (k - 1 >= -(int)right->atoms.len && + (k - 1 >= -(int)DD_ATOM_NB(right) && kd_forward[k - 1] >= kd_forward[k + 1]))) { /* * Advance from k - 1. @@ -316,8 +316,8 @@ diff_divide_myers_forward(struct diff_data *left, stru } /* Slide down any snake that we might find here. */ - while (x < left->atoms.len && - xk_to_y(x, k) < right->atoms.len && + while (x < DD_ATOM_NB(left) && + xk_to_y(x, k) < DD_ATOM_NB(right) && diff_atom_same(DD_ATOM_AT(left, x), DD_ATOM_AT(right, xk_to_y(x, k)))) x++; @@ -330,13 +330,13 @@ diff_divide_myers_forward(struct diff_data *left, stru kd_forward[fi], kd_forward[fi] - fi); #if 0 if (kd_forward[fi] >= 0 && - kd_forward[fi] < left->atoms.len) + kd_forward[fi] < DD_ATOM_NB(left)) debug_dump_atom(left, right, DD_ATOM_AT(left, kd_forward[fi])); else debug("\n"); if (kd_forward[fi]-fi >= 0 && - kd_forward[fi]-fi < right->atoms.len) + kd_forward[fi]-fi < DD_ATOM_NB(right)) debug_dump_atom(right, left, DD_ATOM_AT(right, kd_forward[fi) - fi]); @@ -346,8 +346,8 @@ diff_divide_myers_forward(struct diff_data *left, stru } } - if (x < 0 || x > left->atoms.len || - xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len) + if (x < 0 || x > DD_ATOM_NB(left) || + xk_to_y(x, k) < 0 || xk_to_y(x, k) > DD_ATOM_NB(right)) continue; /* @@ -506,7 +506,7 @@ static void diff_divide_myers_backward(struct diff_data *left, struct diff_data *right, int *kd_forward, int *kd_backward, int d, struct diff_box *meeting_snake) { - int delta = (int)right->atoms.len - (int)left->atoms.len; + int delta = (int)DD_ATOM_NB(right) - (int)DD_ATOM_NB(left); int prev_x; int prev_y; int c; @@ -516,17 +516,17 @@ diff_divide_myers_backward(struct diff_data *left, str debug_dump_myers_graph(left, right, NULL); for (c = d; c >= -d; c -= 2) { - if (c < -(int)left->atoms.len || c > (int)right->atoms.len) { + if (c < -(int)DD_ATOM_NB(left) || c > (int)DD_ATOM_NB(right)) { /* * This diagonal is completely outside of the Myers * graph, don't calculate it. */ - if (c < -(int)left->atoms.len) - debug(" %d c < -(int)left->atoms.len %d\n", c, - -(int)left->atoms.len); + if (c < -(int)DD_ATOM_NB(left)) + debug(" %d c < -(int)DD_ATOM_NB(left) %d\n", c, + -(int)DD_ATOM_NB(left)); else - debug(" %d c > right->atoms.len %d\n", c, - right->atoms.len); + debug(" %d c > DD_ATOM_NB(right) %d\n", c, + DD_ATOM_NB(right)); if (c < 0) { /* * We are traversing negatively, and already @@ -546,7 +546,7 @@ diff_divide_myers_backward(struct diff_data *left, str * yet, get the initial x from the bottom right of the * Myers graph. */ - x = left->atoms.len; + x = DD_ATOM_NB(left); } /* * Favoring "-" lines first means favoring moving rightwards @@ -575,7 +575,7 @@ diff_divide_myers_backward(struct diff_data *left, str * c + 1 if c - 1 is outside the graph. */ else if (c > -d && (c == d || - (c - 1 >= -(int)right->atoms.len && + (c - 1 >= -(int)DD_ATOM_NB(right) && kd_backward[c - 1] <= kd_backward[c + 1]))) { /* * A top one. @@ -627,13 +627,13 @@ diff_divide_myers_backward(struct diff_data *left, str kd_backward[fi] - fi + delta); #if 0 if (kd_backward[fi] >= 0 && - kd_backward[fi] < left->atoms.len) + kd_backward[fi] < DD_ATOM_NB(left)) debug_dump_atom(left, right, DD_ATOM_AT(left, kd_backward[fi])); else debug("\n"); if (kd_backward[fi]-fi+delta >= 0 && - kd_backward[fi]-fi+delta < right->atoms.len) + kd_backward[fi]-fi+delta < DD_ATOM_NB(right)) debug_dump_atom(right, left, DD_ATOM_AT(right, kd_backward[fi]-fi+delta)); else @@ -642,8 +642,8 @@ diff_divide_myers_backward(struct diff_data *left, str } } - if (x < 0 || x > left->atoms.len || xc_to_y(x, c, delta) < 0 || - xc_to_y(x, c, delta) > right->atoms.len) + if (x < 0 || x > DD_ATOM_NB(left) || xc_to_y(x, c, delta) < 0 || + xc_to_y(x, c, delta) > DD_ATOM_NB(right)) continue; /* @@ -758,7 +758,7 @@ diff_algo_myers_divide(const struct diff_algo_config * * Allocate two columns of a Myers graph, one for the forward and * one for the backward traversal. */ - max = left->atoms.len + right->atoms.len; + max = DD_ATOM_NB(left) + DD_ATOM_NB(right); kd_len = max + 1; kd_buf_size = kd_len << 1; kd_buf = reallocarray(NULL, kd_buf_size, sizeof(int)); @@ -801,9 +801,9 @@ diff_algo_myers_divide(const struct diff_algo_config * goto return_rc; } else { debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n", - mid_snake.left_start, mid_snake.left_end, left->atoms.len, + mid_snake.left_start, mid_snake.left_end, DD_ATOM_NB(left), mid_snake.right_start, mid_snake.right_end, - right->atoms.len); + DD_ATOM_NB(right)); /* Section before the mid-snake. */ debug("Section before the mid-snake\n"); @@ -859,13 +859,13 @@ diff_algo_myers_divide(const struct diff_algo_config * debug("Section after the mid-snake\n"); debug(" left_end %u right_end %u\n", mid_snake.left_end, mid_snake.right_end); - debug(" left_count %u right_count %u\n", left->atoms.len, - right->atoms.len); + debug(" left_count %u right_count %u\n", DD_ATOM_NB(left), + DD_ATOM_NB(right)); left_atom = DD_ATOM_AT(left, mid_snake.left_end); - left_section_len = left->atoms.len - mid_snake.left_end; + left_section_len = DD_ATOM_NB(left) - mid_snake.left_end; right_atom = DD_ATOM_AT(right, mid_snake.right_end); - right_section_len = right->atoms.len - mid_snake.right_end; + right_section_len = DD_ATOM_NB(right) - mid_snake.right_end; if (left_section_len && right_section_len) { /* @@ -943,7 +943,7 @@ diff_algo_myers(const struct diff_algo_config *algo_co * Allocate two columns of a Myers graph, one for the forward and * one for the backward traversal. */ - max = left->atoms.len + right->atoms.len; + max = DD_ATOM_NB(left) + DD_ATOM_NB(right); kd_len = max + 1 + max; kd_buf_size = kd_len * kd_len; debug("state size: %zu\n", kd_buf_size); @@ -976,18 +976,18 @@ diff_algo_myers(const struct diff_algo_config *algo_co debug("-- %s d=%d\n", __func__, d); for (k = d; k >= -d; k -= 2) { - if (k < -(int)right->atoms.len || - k > (int)left->atoms.len) { + if (k < -(int)DD_ATOM_NB(right) || + k > (int)DD_ATOM_NB(left)) { /* * This diagonal is completely outside of the * Myers graph, don't calculate it. */ - if (k < -(int)right->atoms.len) - debug(" %d k < -(int)right->atoms.len" - " %d\n", k, -(int)right->atoms.len); + if (k < -(int)DD_ATOM_NB(right)) + debug(" %d k < -(int)DD_ATOM_NB(right)" + " %d\n", k, -(int)DD_ATOM_NB(right)); else - debug(" %d k > left->atoms.len %d\n", - k, left->atoms.len); + debug(" %d k > DD_ATOM_NB(left) %d\n", + k, DD_ATOM_NB(left)); if (k < 0) { /* * We are traversing negatively, and @@ -1041,7 +1041,7 @@ diff_algo_myers(const struct diff_algo_config *algo_co * the graph. */ if (k > -d && (k == d || - (k - 1 >= -(int)right->atoms.len && + (k - 1 >= -(int)DD_ATOM_NB(right) && kd_prev_column[k - 1] >= kd_prev_column[k + 1]))) { /* * Advance from k - 1. @@ -1068,8 +1068,8 @@ diff_algo_myers(const struct diff_algo_config *algo_co } /* Slide down any snake that we might find here. */ - while (x < left->atoms.len && - xk_to_y(x, k) < right->atoms.len && + while (x < DD_ATOM_NB(left) && + xk_to_y(x, k) < DD_ATOM_NB(right) && diff_atom_same(DD_ATOM_AT(left, x), DD_ATOM_AT(right, xk_to_y(x, k)))) x++; @@ -1082,13 +1082,13 @@ diff_algo_myers(const struct diff_algo_config *algo_co kd_column[fi], kd_column[fi] - fi); #if 0 if (kd_column[fi] >= 0 && - kd_column[fi] < left->atoms.len) + kd_column[fi] < DD_ATOM_NB(left)) debug_dump_atom(left, right, DD_ATOM_AT(left, kd_column[fi])); else debug("\n"); if (kd_column[fi]-fi >= 0 && - kd_column[fi]-fi < right->atoms.len) + kd_column[fi]-fi < DD_ATOM_NB(right)) debug_dump_atom(right, left, DD_ATOM_AT(right, kd_column[fi]-fi)); else @@ -1097,8 +1097,8 @@ diff_algo_myers(const struct diff_algo_config *algo_co } } - if (x == left->atoms.len && - xk_to_y(x, k) == right->atoms.len) { + if (x == DD_ATOM_NB(left) && + xk_to_y(x, k) == DD_ATOM_NB(right)) { /* Found a path */ backtrack_d = d; backtrack_k = k; blob - ad1277540a1e9a2d0a96ca0573c21ca19a01481d blob + 2c70b87049628a7751c32a0e70784ec2be23cd56 --- diff_patience.c +++ diff_patience.c @@ -149,7 +149,7 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat debug("trivially combine identical lines around unique_in_both lines\n"); - for (l_idx = 0; l_idx < left->atoms.len; l_idx = next_l_idx) { + for (l_idx = 0; l_idx < DD_ATOM_NB(left); l_idx = next_l_idx) { struct diff_atom *l = DD_ATOM_AT(left, l_idx); next_l_idx = l_idx + 1; @@ -180,8 +180,8 @@ diff_atoms_swallow_identical_neighbors(struct diff_dat /* Swallow downwards */ for (identical_l.end = l_idx + 1, identical_r.end = r_idx + 1; - (identical_l.end < left->atoms.len && - identical_r.end < right->atoms.len && + (identical_l.end < DD_ATOM_NB(left) && + identical_r.end < DD_ATOM_NB(right) && diff_atom_same(DD_ATOM_AT(left, identical_l.end), DD_ATOM_AT(right, identical_r.end))); identical_l.end++, identical_r.end++, next_l_idx++) { @@ -426,8 +426,8 @@ diff_algo_patience(const struct diff_algo_config *algo } else { atom = NULL; atom_r = NULL; - left_idx = left->atoms.len; - right_idx = right->atoms.len; + left_idx = DD_ATOM_NB(left); + right_idx = DD_ATOM_NB(right); } /*