X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/291d809da56d391a5e1aac7588bc0b4f4cdff260..49e717ce62a05692fc037261e131f78ba52adff2:/src/xbt/xbt_str.c

diff --git a/src/xbt/xbt_str.c b/src/xbt/xbt_str.c
index b2593e5f1f..5815b8b1f1 100644
--- a/src/xbt/xbt_str.c
+++ b/src/xbt/xbt_str.c
@@ -573,82 +573,208 @@ long getline(char **buf, size_t * n, FILE * stream)
 
 /*
  * Diff related functions
+ *
+ * Implementation of the algorithm described in "An O(NP) Sequence
+ * Comparison Algorithm", by Sun Wu, Udi Manber, Gene Myers, and Webb
+ * Miller.
  */
-static XBT_INLINE int diff_get(xbt_matrix_t C, int i, int j)
+
+struct subsequence {
+    int x, y;                   /* starting coordinates */
+    int len;                    /* length */
+};
+
+static XBT_INLINE
+void diff_snake(const char *vec_a[], int a0, int len_a,
+                const char *vec_b[], int b0, int len_b,
+                struct subsequence *seqs, int *fp, int k, int limit)
 {
-  return (i == -1 || j == -1) ? 0 : xbt_matrix_get_as(C, i, j, int);
+  int record_seq;
+  int x, y;
+  int fp_left = fp[k - 1] + 1;
+  int fp_right = fp[k + 1];
+  if (fp_left > fp_right) {
+    x = fp_left;
+    record_seq = k - 1;
+  } else {
+    x = fp_right;
+    record_seq = k + 1;
+  }
+  y = x - k;
+  if (x + y <= limit) {
+    seqs[k].x = x;
+    seqs[k].y = y;
+    record_seq = k;
+  } else {
+    seqs[k] = seqs[record_seq];
+  }
+  while (x < len_a && y < len_b && !strcmp(vec_a[a0 + x], vec_b[b0 + y]))
+    ++x, ++y;
+  fp[k] = x;
+  if (record_seq == k)
+    seqs[k].len = x - seqs[k].x;
+}
+
+/* Returns the length of a shortest edit script, and a common
+ * subsequence from the middle.
+ */
+static int diff_middle_subsequence(const char *vec_a[], int a0,  int len_a,
+                                   const char *vec_b[], int b0,  int len_b,
+                                   struct subsequence *subseq,
+                                   struct subsequence *seqs, int *fp)
+{
+  const int delta = len_a - len_b;
+  const int limit = (len_a + len_b) / 2;
+  int kmin;
+  int kmax;
+  int k;
+  int p = -1;
+
+  if (delta >= 0) {
+    kmin = 0;
+    kmax = delta;
+  } else {
+    kmin = delta;
+    kmax = 0;
+  }
+  for (k = kmin; k <= kmax; k++)
+    fp[k] = -1;
+  do {
+    p++;
+    fp[kmin - p - 1] = fp[kmax + p + 1] = -1;
+    for (k = kmax + p; k > delta; k--)
+      diff_snake(vec_a, a0, len_a, vec_b, b0, len_b, seqs, fp, k, limit);
+    for (k = kmin - p; k <= delta; k++)
+      diff_snake(vec_a, a0, len_a, vec_b, b0, len_b, seqs, fp, k, limit);
+  } while (fp[delta] != len_a);
+
+  subseq->x = a0 + seqs[delta].x;
+  subseq->y = b0 + seqs[delta].y;
+  subseq->len = seqs[delta].len;
+  return abs(delta) + 2 * p;;
 }
 
-static xbt_matrix_t diff_build_LCS(xbt_dynar_t da, xbt_dynar_t db,
-                                   int len_a, int len_b)
+/* Finds a longest common subsequence.
+ */
+static void diff_compute_lcs(const char *vec_a[], int a0, int len_a,
+                             const char *vec_b[], int b0, int len_b,
+                             xbt_dynar_t common_sequence,
+                             struct subsequence *seqs, int *fp)
 {
-  xbt_matrix_t C = xbt_matrix_new(len_a, len_b, sizeof(int), NULL);
-  int i, j;
-
-  /* Compute the LCS */
-  /*
-     function LCSLength(X[1..m], Y[1..n])
-       C = array(0..m, 0..n)
-       for i := 0..m
-         C[i,0] = 0
-       for j := 1..n
-         C[0,j] = 0
-       for i := 1..m
-         for j := 1..n
-           if X[i] = Y[j]
-             C[i,j] := C[i-1,j-1] + 1
-           else:
-             C[i,j] := max(C[i,j-1], C[i-1,j])
-       return C[m,n]
-   */
-  for (i = 0; i < len_a; i++)
-    for (j = 0; j < len_b; j++) {
-
-      if (!strcmp(xbt_dynar_get_as(da, i, char *),
-                  xbt_dynar_get_as(db, j, char *)))
-        *((int *) xbt_matrix_get_ptr(C, i, j)) = diff_get(C, i - 1, j - 1) + 1;
-      else
-        *((int *) xbt_matrix_get_ptr(C, i, j)) = max(diff_get(C, i, j - 1),
-                                                     diff_get(C, i - 1, j));
+  if (len_a > 0 && len_b > 0) {
+    struct subsequence subseq;
+    int ses_len = diff_middle_subsequence(vec_a, a0, len_a, vec_b, b0, len_b,
+                                          &subseq, seqs, fp);
+    if (ses_len > 1) {
+      int u = subseq.x + subseq.len;
+      int v = subseq.y + subseq.len;
+      diff_compute_lcs(vec_a, a0, subseq.x - a0, vec_b, b0, subseq.y - b0,
+                       common_sequence, seqs, fp);
+      if (subseq.len > 0)
+        xbt_dynar_push(common_sequence, &subseq);
+      diff_compute_lcs(vec_a, u, a0 + len_a - u, vec_b, v, b0 + len_b - v,
+                       common_sequence, seqs, fp);
+    } else {
+      int len = MIN(len_a, len_b) - subseq.len;
+      if (subseq.x == a0 && subseq.y == b0) {
+        if (subseq.len > 0)
+          xbt_dynar_push(common_sequence, &subseq);
+        if (len > 0) {
+          struct subsequence subseq0 = {a0 + len_a - len,
+                                        b0 + len_b - len, len};
+          xbt_dynar_push(common_sequence, &subseq0);
+        }
+      } else {
+        if (len > 0) {
+          struct subsequence subseq0 = {a0, b0, len};
+          xbt_dynar_push(common_sequence, &subseq0);
+        }
+        if (subseq.len > 0)
+          xbt_dynar_push(common_sequence, &subseq);
+      }
     }
-  return C;
+  }
 }
 
-static void diff_build_diff(xbt_dynar_t res,
-                            xbt_matrix_t C,
-                            xbt_dynar_t da, xbt_dynar_t db, int i, int j)
+static int diff_member(const char *s, const char *vec[], int from, int to)
 {
-  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;
+    }
+  }
+
+  *a0_p = a0;
+  *b0_p = b0;
+  *len_a_p = len_a;
+  *len_b_p = len_b;
 }
 
 /** @brief Compute the unified diff of two strings */
@@ -656,13 +782,19 @@ char *xbt_str_diff(const char *a, const char *b)
 {
   xbt_dynar_t da = xbt_str_split(a, "\n");
   xbt_dynar_t db = xbt_str_split(b, "\n");
-  xbt_matrix_t C;
+  xbt_dynar_t common_sequence, common_suffix;
+  size_t len;
+  const char **vec_a, **vec_b;
+  int a0, b0;
+  int len_a, len_b;
+  int max;
+  int *fp_base, *fp;
+  struct subsequence *seqs_base, *seqs;
+  struct subsequence subseq;
   xbt_dynar_t diff;
   char *res;
-  size_t len;
-  unsigned length_da;
-
-  diff = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
+  int x, y;
+  unsigned s;
 
   /* Clean empty lines at the end of da and db */
   len = strlen(a);
@@ -672,42 +804,64 @@ char *xbt_str_diff(const char *a, const char *b)
   if (len > 0 && b[len - 1] == '\n')
     xbt_dynar_pop(db, NULL);
 
-  /* Find the common suffix, do it before extracting the prefix,
-   * as xbt_dynar_pop costs less than xbt_dynar_shift */
-  length_da = xbt_dynar_length(da);
-  while (length_da > 0 && xbt_dynar_length(db) > 0 &&
-         !strcmp(xbt_dynar_get_as(da, length_da - 1, char *),
-                 xbt_dynar_getlast_as(db, char *))) {
-    xbt_dynar_pop(db, NULL);
-    length_da--;
+  /* Various initializations */
+  /* Assume that dynar's content is contiguous */
+  a0 = 0;
+  len_a = xbt_dynar_length(da);
+  vec_a = len_a ? xbt_dynar_get_ptr(da, 0) : NULL;
+  b0 = 0;
+  len_b = xbt_dynar_length(db);
+  vec_b = len_b ? xbt_dynar_get_ptr(db, 0) : NULL;
+  max = MAX(len_a, len_b) + 1;
+  fp_base = xbt_new(int, 2 * max + 1);
+  fp = fp_base + max;           /* indexes in [-max..max] */
+  seqs_base = xbt_new(struct subsequence, 2 * max + 1);
+  seqs = seqs_base + max;       /* indexes in [-max..max] */
+  common_sequence = xbt_dynar_new(sizeof(struct subsequence), NULL);
+  common_suffix = xbt_dynar_new(sizeof(struct subsequence), NULL);
+
+  /* Add a sentinel a the end of the sequence */
+  subseq.x = len_a;
+  subseq.y = len_b;
+  subseq.len = 0;
+  xbt_dynar_push(common_suffix, &subseq);
+
+  /* Compute the Longest Common Subsequence */
+  diff_easy_prefix(vec_a, &a0, &len_a, vec_b, &b0, &len_b, common_sequence);
+  diff_easy_suffix(vec_a, &a0, &len_a, vec_b, &b0, &len_b, common_suffix);
+  diff_compute_lcs(vec_a, a0, len_a, vec_b, b0, len_b, common_sequence, seqs, fp);
+  while (!xbt_dynar_is_empty(common_suffix)) {
+    xbt_dynar_pop(common_suffix, &subseq);
+    xbt_dynar_push(common_sequence, &subseq);
   }
 
-  /* Extract the common prefix */
-  while (length_da > 0 && xbt_dynar_length(db) > 0 &&
-         !strcmp(xbt_dynar_getfirst_as(da, char *),
-                 xbt_dynar_getfirst_as(db, char *))) {
-    char *topush = bprintf("  %s", xbt_dynar_getfirst_as(da, char *));
-    xbt_dynar_push(diff, &topush);
-    xbt_dynar_shift(da, NULL);
-    xbt_dynar_shift(db, NULL);
-    length_da--;
+  /* Build a Shortest Edit Script, and the final result */
+  diff = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
+  x = 0;
+  y = 0;
+  xbt_dynar_foreach(common_sequence, s, subseq) {
+    while (x < subseq.x) {
+      char *topush = bprintf("- %s", vec_a[x++]);
+      xbt_dynar_push_as(diff, char*, topush);
+    }
+    while (y < subseq.y) {
+      char *topush = bprintf("+ %s", vec_b[y++]);
+      xbt_dynar_push_as(diff, char*, topush);
+    }
+    while (x < subseq.x + subseq.len) {
+      char *topush = bprintf("  %s", vec_a[x++]);
+      xbt_dynar_push_as(diff, char*, topush);
+      y++;
+    }
   }
+  res = xbt_str_join(diff, "\n");
 
-  /* Compute the diff for the remaining */
-  C = diff_build_LCS(da, db, length_da, xbt_dynar_length(db));
-  diff_build_diff(diff, C, da, db, length_da - 1, xbt_dynar_length(db) - 1);
-  xbt_matrix_free(C);
+  xbt_free(fp_base);
+  xbt_free(seqs_base);
   xbt_dynar_free(&db);
-
-  /* Add the common suffix */
-  for (; length_da < xbt_dynar_length(da); length_da++) {
-    char *topush = bprintf("  %s", xbt_dynar_get_as(da, length_da, char *));
-    xbt_dynar_push(diff, &topush);
-  }
   xbt_dynar_free(&da);
-
-  /* Build the final result */
-  res = xbt_str_join(diff, "\n");
+  xbt_dynar_free(&common_sequence);
+  xbt_dynar_free(&common_suffix);
   xbt_dynar_free(&diff);
 
   return res;