NAME

diff — generate arbitrary sequence diffs

LIBRARY

library “libdiff”

SYNOPSIS

#include <diff.h>

int
diff(struct diff *p, int (*cmp)(const void *, const void *), size_t size, const void *base1, size_t nmemb1, const void *base2, size_t nmemb2);

DESCRIPTION

The diff() function generates the shortest edit script, longest common subsequence, and edit distance going from an origin array of nmemb1 objects, the initial member of which is pointed to as base1; to the target array of nmemb2 objects with initial member base2. The size of each object is specified by size. Objects are compared by cmp, which requires two arguments pointing to the objects being compared. It returns zero if the objects are the same, non-zero otherwise.

On success, diff() sets the edit distance in p->editdist. It allocates the p->ses array of length p->sessz and fills it with the shortest common subsequence. It also allocates the p->lcs array of length p->lcssz and fills it with the longest common subsequence. Both arrays must be passed to free(3) by the caller.

RETURN VALUES

The diff() function returns <0 on memory allocation failure, 0 if the sequence is too complicated to generate, or >0 otherwise on success.

EXAMPLES

The following example takes two strings, "asdf" and "fdsa", and displays the edit script to go from the first to the second.

int cmp(const void *p1, const void *p2) {
    return *(const char *)p1 == *(const char *)p2;
}

void compute(void) {
    size_t i;
    int rc;
    struct diff p;

    rc = diff(&p, cmp, 1, "asdf", 4, "fdsa", 4);

    if (rc < 0)
        err(EXIT_FAILURE, NULL);
    if (0 == rc)
        errx(EXIT_FAILURE, "cannot compute distance");

    for (i = 0; i < p.sessz; i++)
        printf("%s%c\n",
            DIFF_ADD == p.ses[i].type ?  "+" :
            DIFF_DELETE == p.ses[i].type ?  "-" : " ",
            *(const char *)p.ses[i].e);
    free(p.ses);
    free(p.lcs);
}

The second example looks for difference in words.

int cmp(const void *p1, const void *p2) {
    return 0 == strcmp
        (*(const char **)p1, *(const char **)p2);
}

void compute(void) {
    size_t i;
    int rc;
    struct diff p;
    const char *origin[] = { "hello", "there" };
    const char *target[] = { "hello", "world" };

    rc = diff(&p, cmp, sizeof(char *), origin, 2, target, 2);

    if (rc < 0)
        err(EXIT_FAILURE, NULL);
    if (0 == rc)
        errx(EXIT_FAILURE, "cannot compute distance");

    for (i = 0; i < p.sessz; i++)
        printf("%s%s\n",
            DIFF_ADD == p.ses[i].type ?  "+" :
            DIFF_DELETE == p.ses[i].type ?  "-" : " ",
            *(const char **)p.ses[i].e);
    free(p.ses);
    free(p.lcs);
}

SEE ALSO

Wu Sun, Manber Udi, and Myers Gene, An O(NP) sequence comparison algorithm, Issue 6, Information Processing Letters, Volume 35, 1990.