Gotweb

Commit Diff

Commit:: 727b847b7a003fb900f714a515563b73438576cf
From:: Martin Pieuchot <mpi@openbsd.org>
Date:: Fri Mar 20 19:19:34 2020 UTC
Message:: Abstract atoms.len
Actions:: Patch | Tree
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);
 		}
 
 		/*