- char *topush;
- /* Construct the diff
- function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
- if i > 0 and j > 0 and X[i] = Y[j]
- printDiff(C, X, Y, i-1, j-1)
- print " " + X[i]
- else
- if j > 0 and (i = 0 or C[i,j-1] >= C[i-1,j])
- printDiff(C, X, Y, i, j-1)
- print "+ " + Y[j]
- else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
- printDiff(C, X, Y, i-1, j)
- print "- " + X[i]
- */
-
- if (i >= 0 && j >= 0 && !strcmp(xbt_dynar_get_as(da, i, char *),
- xbt_dynar_get_as(db, j, char *))) {
- diff_build_diff(res, C, da, db, i - 1, j - 1);
- topush = bprintf(" %s", xbt_dynar_get_as(da, i, char *));
- xbt_dynar_push(res, &topush);
- } else if (j >= 0 &&
- (i == -1 || diff_get(C, i, j - 1) >= diff_get(C, i - 1, j))) {
- diff_build_diff(res, C, da, db, i, j - 1);
- topush = bprintf("+ %s", xbt_dynar_get_as(db, j, char *));
- xbt_dynar_push(res, &topush);
- } else if (i >= 0 &&
- (j == -1 || diff_get(C, i, j - 1) < diff_get(C, i - 1, j))) {
- diff_build_diff(res, C, da, db, i - 1, j);
- topush = bprintf("- %s", xbt_dynar_get_as(da, i, char *));
- xbt_dynar_push(res, &topush);
+ for ( ; from < to ; from++)
+ if (!strcmp(s, vec[from]))
+ return 1;
+ return 0;
+}
+
+/* Extract common prefix.
+ */
+static void diff_easy_prefix(const char *vec_a[], int *a0_p, int *len_a_p,
+ const char *vec_b[], int *b0_p, int *len_b_p,
+ xbt_dynar_t common_sequence)
+{
+ int a0 = *a0_p;
+ int b0 = *b0_p;
+ int len_a = *len_a_p;
+ int len_b = *len_b_p;
+
+ while (len_a > 0 && len_b > 0) {
+ struct subsequence subseq = {a0, b0, 0};
+ while (len_a > 0 && len_b > 0 && !strcmp(vec_a[a0], vec_b[b0])) {
+ a0++, len_a--;
+ b0++, len_b--;
+ subseq.len++;
+ }
+ if (subseq.len > 0)
+ xbt_dynar_push(common_sequence, &subseq);
+ if (len_a > 0 && len_b > 0 &&
+ !diff_member(vec_a[a0], vec_b, b0 + 1, b0 + len_b)) {
+ a0++, len_a--;
+ } else {
+ break;
+ }
+ }
+
+ *a0_p = a0;
+ *b0_p = b0;
+ *len_a_p = len_a;
+ *len_b_p = len_b;
+}
+
+/* Extract common suffix.
+ */
+static void diff_easy_suffix(const char *vec_a[], int *a0_p, int *len_a_p,
+ const char *vec_b[], int *b0_p, int *len_b_p,
+ xbt_dynar_t common_suffix)
+{
+ int a0 = *a0_p;
+ int b0 = *b0_p;
+ int len_a = *len_a_p;
+ int len_b = *len_b_p;
+
+ while (len_a > 0 && len_b > 0){
+ struct subsequence subseq;
+ subseq.len = 0;
+ while (len_a > 0 && len_b > 0 &&
+ !strcmp(vec_a[a0 + len_a - 1], vec_b[b0 + len_b - 1])) {
+ len_a--;
+ len_b--;
+ subseq.len++;
+ }
+ if (subseq.len > 0) {
+ subseq.x = a0 + len_a;
+ subseq.y = b0 + len_b;
+ xbt_dynar_push(common_suffix, &subseq);
+ }
+ if (len_a > 0 && len_b > 0 &&
+ !diff_member(vec_b[b0 + len_b - 1], vec_a, a0, a0 + len_a - 1)) {
+ len_b--;
+ } else {
+ break;
+ }