-#if defined(SIMGRID_NEED_GETLINE) || defined(DOXYGEN)
-/** @brief Get a single line from the stream (reimplementation of the GNU getline)
- *
- * This is a redefinition of the GNU getline function, used on platforms where it does not exists.
- *
- * getline() reads an entire line from stream, storing the address of the buffer
- * containing the text into *buf. The buffer is null-terminated and includes
- * the newline character, if one was found.
- *
- * If *buf is NULL, then getline() will allocate a buffer for storing the line,
- * which should be freed by the user program. Alternatively, before calling getline(),
- * *buf can contain a pointer to a malloc()-allocated buffer *n bytes in size. If the buffer
- * is not large enough to hold the line, getline() resizes it with realloc(), updating *buf and *n
- * as necessary. In either case, on a successful call, *buf and *n will be updated to
- * reflect the buffer address and allocated size respectively.
- */
-long getline(char **buf, size_t * n, FILE * stream)
-{
-
- size_t i;
- int ch;
-
- if (!*buf) {
- *buf = xbt_malloc(512);
- *n = 512;
- }
-
- if (feof(stream))
- return (ssize_t) - 1;
-
- for (i = 0; (ch = fgetc(stream)) != EOF; i++) {
-
- if (i >= (*n) + 1)
- *buf = xbt_realloc(*buf, *n += 512);
-
- (*buf)[i] = ch;
-
- if ((*buf)[i] == '\n') {
- i++;
- (*buf)[i] = '\0';
- break;
- }
- }
-
- if (i == *n)
- *buf = xbt_realloc(*buf, *n += 1);
-
- (*buf)[i] = '\0';
-
- return (ssize_t) i;
-}
-
-#endif /* HAVE_GETLINE */
-
-/*
- * 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 (Information
- * Processing Letters 35(6):317-323, 1990), with the linear-space
- * divide-and-conquer strategy described in "An O(ND) Difference Algorithm and
- * Its Variations", by Eugene W. Myers (Algorithmica 1:251-266, 1986).
- */
-
-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)
-{
- 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;;
-}
-
-/* Finds a longest common subsequence.
- * Returns its length.
- */
-static int 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)
-{
- 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);
- int lcs_len = (len_a + len_b - ses_len) / 2;
- if (lcs_len == 0) {
- return 0;
- } else if (ses_len > 1) {
- int lcs_len1 = subseq.len;
- if (lcs_len1 < lcs_len)
- lcs_len1 += 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);
- if (lcs_len1 < lcs_len) {
- int u = subseq.x + subseq.len;
- int v = subseq.y + subseq.len;
- 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 lcs_len;
- } else {
- return 0;
- }
-}
-
-static int diff_member(const char *s, const char *vec[], int from, int to)
-{
- 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 */
-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_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;
- int x, y;
- unsigned s;
-
- /* Clean empty lines at the end of da and db */
- len = strlen(a);
- if (len > 0 && a[len - 1] == '\n')
- xbt_dynar_pop(da, NULL);
- len = strlen(b);
- if (len > 0 && b[len - 1] == '\n')
- xbt_dynar_pop(db, NULL);
-
- /* 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);
- }
-
- /* 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");
-
- xbt_free(fp_base);
- xbt_free(seqs_base);
- xbt_dynar_free(&db);
- xbt_dynar_free(&da);
- xbt_dynar_free(&common_sequence);
- xbt_dynar_free(&common_suffix);
- xbt_dynar_free(&diff);
-
- return res;
-}
-
-
-/** @brief creates a new string containing what can be read on a fd
- *
- */