diff strange diagnostic

[Alain Ketterlin]

Hi all, and first: many thanks for your excellent work.

I just noticed a funny behavior of diff (diff - GNU diffutils version
2.7) on my fairly old RedHat Linux distro (Linux durian 2.2.14-5.0 #1
Tue Mar 7 21:07:39 EST 2000 i686 unknown).

Given two files which differ only in empty lines, diff finds
differences where there is none (even with -B). The two files are
attached below (two versions of a simple C program). Suppose they're
called creuse.c and creuse.c.orig, here is diff's output:


% diff -B creuse.c creuse.c.orig
5d4
< struct cellule {
6a6
> struct cellule {
% diff -B creuse.c.orig creuse.c     
223d221
<     int tours;
224a223
>     int tours;


(Actually, bot files compile fine and give the exact same executable
provided they're compiled under the same name. Removing -B only adds a
bunch of a/d of empty lines.)

OK, no big deal. Maybe this is expected, I didn't have time to read
all of diff's docs. If it's not expected, well, it's no real problem.
If it is expected but you have no real sample of this behavior, here
is one.

Anyway, thanks again for this most useful tool, and have fun with
these files.

-- Alain.

#include <stdio.h>
#include <stdlib.h>

struct cellule {


    int val;
    int l;
    int c;


    struct cellule * nl;
    struct cellule * pl;
    struct cellule * nc;
    struct cellule * pc;


    struct cellule * n;
    struct cellule * p;


};

struct matrice {

    int l;
    int c;
    struct cellule ** lignes;
    struct cellule ** colonnes;
    struct cellule * cellules;
    int def;

};

int ncellules = 0;

struct matrice * make(int l, int c, int d)
{
    struct matrice * mat = malloc(sizeof(struct matrice));
    mat->l = l;
    mat->lignes = calloc(l,sizeof(struct cellule *));
    mat->c = c;
    mat->colonnes = calloc(c,sizeof(struct cellule *));
    mat->cellules = NULL;
    mat->def = d;
    return mat;
}

void destroy(struct matrice * mat)
{
    struct cellule * cellule = mat->cellules;
    while ( cellule != NULL )
    {
        struct cellule * d = cellule;
        cellule = cellule->n;
        free(d);
        --ncellules;
    }
    free(mat->lignes);
    free(mat->colonnes);
    free(mat);
}

struct cellule * find(const struct matrice * mat, int l, int c)
{
    struct cellule * cellule = mat->lignes[l];
    while ( cellule != NULL && cellule->c < c )
        cellule = cellule->nl;
    if ( cellule != NULL && cellule->c == c)
        return cellule;
    else
        return NULL;
}

int get(const struct matrice * mat, int l, int c)
{
    struct cellule * cellule = find(mat,l,c);
    if ( cellule != NULL )
        return cellule->val;
    else
        return mat->def;
}

void set(struct matrice * mat, int l, int c, int v)
{
    struct cellule * precl = NULL;
    struct cellule * suivl = mat->lignes[l];
    struct cellule * precc = NULL;
    struct cellule * suivc = mat->colonnes[c];

    while ( suivl != NULL && suivl->c < c )
    {
        precl = suivl;
        suivl = suivl->nl;
    }
    while ( suivc != NULL && suivc->l < l )
    {
        precc = suivc;
        suivc = suivc->nc;
    }
    if ( suivl != NULL && suivl->c == c
         && suivc != NULL && suivc->l == l )
    {
        struct cellule * cellule = suivl;
        if ( v == mat->def )
        {
            if ( cellule->pl != NULL )
                cellule->pl->nl = cellule->nl;
            else
                mat->lignes[l] = cellule->nl;
            if ( cellule->nl != NULL )
                cellule->nl->pl = cellule->pl;

            if ( cellule->pc != NULL )
                cellule->pc->nc = cellule->nc;
            else
                mat->colonnes[c] = cellule->nc;
            if ( cellule->nc != NULL )
                cellule->nc->pc = cellule->pc;

            if ( cellule->p != NULL )
                cellule->p->n = cellule->n;
            else
                mat->cellules = cellule->n;
            if ( cellule->n != NULL )
                cellule->n->p = cellule->p;

            free(cellule);
            --ncellules;
        }
        else
        {
            cellule->val = v;
        }
    }
    else
    {
        struct cellule * cellule = malloc(sizeof(struct cellule));
        ++ncellules;
        cellule->val = v;
        cellule->l = l;
        cellule->c = c;

        cellule->nl = suivl;
        cellule->pl = precl;
        cellule->nc = suivc;
        cellule->pc = precc;

        if ( precl != NULL )
            precl->nl = cellule;
        else
            mat->lignes[l] = cellule;
        if ( suivl != NULL )
            suivl->pl = cellule;

        if ( precc != NULL )
            precc->nc = cellule;
        else
            mat->colonnes[c] = cellule;
        if ( suivc != NULL )
            suivc->pc = cellule;

        cellule->n = mat->cellules;
        if ( cellule->n != NULL )
            cellule->n->p = cellule;
        cellule->p = NULL;
        mat->cellules = cellule;
    }

}

void print(const struct matrice * mat)
{
    int i;
    int j;

    printf("%dx%d :\n",mat->l,mat->c);
    for ( i=0 ; i<mat->l; i++ )
    {
        for ( j=0 ; j<mat->c ; j++ )
            printf(" %5d",get(mat,i,j));
        printf("\n");
    }
}

void dump(struct matrice * mat)
{
    struct cellule * cellule;
    printf("%dx%d\n",mat->l,mat->c);
    for ( cellule = mat->cellules ;
          cellule != NULL ;
          cellule = cellule->n )
    {
        printf("-> (%d,%d)=%d",cellule->l,cellule->c,cellule->val);
        printf(" LINE:");
        if ( cellule->pl != NULL )
            printf("]%d,%d]",cellule->pl->l,cellule->pl->c);
        else
            printf("]]");
        printf("-");
        if ( cellule->nl != NULL )
            printf("[%d,%d[",cellule->nl->l,cellule->nl->c);
        else
            printf("[[");
        printf(" COL:");
        if ( cellule->pc != NULL )
            printf("]%d,%d]",cellule->pc->l,cellule->pc->c);
        else
            printf("]]");
        printf("-");
        if ( cellule->nc != NULL )
            printf("[%d,%d[",cellule->nc->l,cellule->nc->c);
        else
            printf("[[");
        printf("\n");
    }
}

int main()
{

    int tours;
    for ( tours=0 ; tours<1 ; tours++ )
    {

        int i;
        int j;

        struct matrice * mat = make(10,10,0);

        set(mat,4,4,1);
        set(mat,4,8,1);
        set(mat,8,4,1);
        set(mat,8,8,1);
        set(mat,2,4,1);
        set(mat,4,2,1);
        set(mat,4,4,2);
        print(mat);
        dump(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,i,j,100+i*10+j);
        print(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,i,j,0);
        print(mat);
        dump(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,9-i,9-j,100+i*10+j);
        print(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,9-i,9-j,0);
        print(mat);
        dump(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,i,j,100+i*10+j);
        print(mat);

        for ( i=0 ; i<5 ; i++ )
            for ( j=0 ; j<5 ; j++ )
                set(mat,4-i,4-j,0);
        for ( i=0 ; i<5 ; i++ )
            for ( j=0 ; j<5 ; j++ )
                set(mat,9-2*i,9-2*j,0);
        print(mat);

        destroy(mat);

    }

    printf("Cellules : %d\n",ncellules);
    return 0;

}

#include <stdio.h>
#include <stdlib.h>


struct cellule {

    int val;
    int l;
    int c;
    struct cellule * nl;
    struct cellule * pl;
    struct cellule * nc;
    struct cellule * pc;
    struct cellule * n;
    struct cellule * p;

};

struct matrice {

    int l;
    int c;
    struct cellule ** lignes;
    struct cellule ** colonnes;
    struct cellule * cellules;
    int def;

};


int ncellules = 0;


struct matrice * make(int l, int c, int d)
{
    struct matrice * mat = malloc(sizeof(struct matrice));
    mat->l = l;
    mat->lignes = calloc(l,sizeof(struct cellule *));
    mat->c = c;
    mat->colonnes = calloc(c,sizeof(struct cellule *));
    mat->cellules = NULL;
    mat->def = d;
    return mat;
}

void destroy(struct matrice * mat)
{
    struct cellule * cellule = mat->cellules;
    while ( cellule != NULL )
    {
        struct cellule * d = cellule;
        cellule = cellule->n;
        free(d);
        --ncellules;
    }
    free(mat->lignes);
    free(mat->colonnes);
    free(mat);
}

struct cellule * find(const struct matrice * mat, int l, int c)
{
    struct cellule * cellule = mat->lignes[l];
    while ( cellule != NULL && cellule->c < c )
        cellule = cellule->nl;
    if ( cellule != NULL && cellule->c == c)
        return cellule;
    else
        return NULL;
}

int get(const struct matrice * mat, int l, int c)
{
    struct cellule * cellule = find(mat,l,c);
    if ( cellule != NULL )
        return cellule->val;
    else
        return mat->def;
}



void set(struct matrice * mat, int l, int c, int v)
{
    struct cellule * precl = NULL;
    struct cellule * suivl = mat->lignes[l];
    struct cellule * precc = NULL;
    struct cellule * suivc = mat->colonnes[c];

    while ( suivl != NULL && suivl->c < c )
    {
        precl = suivl;
        suivl = suivl->nl;
    }
    while ( suivc != NULL && suivc->l < l )
    {
        precc = suivc;
        suivc = suivc->nc;
    }
    if ( suivl != NULL && suivl->c == c
         && suivc != NULL && suivc->l == l )
    {
        struct cellule * cellule = suivl;
        if ( v == mat->def )
        {
            if ( cellule->pl != NULL )
                cellule->pl->nl = cellule->nl;
            else
                mat->lignes[l] = cellule->nl;
            if ( cellule->nl != NULL )
                cellule->nl->pl = cellule->pl;

            if ( cellule->pc != NULL )
                cellule->pc->nc = cellule->nc;
            else
                mat->colonnes[c] = cellule->nc;
            if ( cellule->nc != NULL )
                cellule->nc->pc = cellule->pc;

            if ( cellule->p != NULL )
                cellule->p->n = cellule->n;
            else
                mat->cellules = cellule->n;
            if ( cellule->n != NULL )
                cellule->n->p = cellule->p;

            free(cellule);
            --ncellules;
        }
        else
        {
            cellule->val = v;
        }
    }
    else
    {
        struct cellule * cellule = malloc(sizeof(struct cellule));
        ++ncellules;
        cellule->val = v;
        cellule->l = l;
        cellule->c = c;

        cellule->nl = suivl;
        cellule->pl = precl;
        cellule->nc = suivc;
        cellule->pc = precc;

        if ( precl != NULL )
            precl->nl = cellule;
        else
            mat->lignes[l] = cellule;
        if ( suivl != NULL )
            suivl->pl = cellule;

        if ( precc != NULL )
            precc->nc = cellule;
        else
            mat->colonnes[c] = cellule;
        if ( suivc != NULL )
            suivc->pc = cellule;

        cellule->n = mat->cellules;
        if ( cellule->n != NULL )
            cellule->n->p = cellule;
        cellule->p = NULL;
        mat->cellules = cellule;
    }

}


void print(const struct matrice * mat)
{
    int i;
    int j;

    printf("%dx%d :\n",mat->l,mat->c);
    for ( i=0 ; i<mat->l; i++ )
    {
        for ( j=0 ; j<mat->c ; j++ )
            printf(" %5d",get(mat,i,j));
        printf("\n");
    }
}

void dump(struct matrice * mat)
{
    struct cellule * cellule;
    printf("%dx%d\n",mat->l,mat->c);
    for ( cellule = mat->cellules ;
          cellule != NULL ;
          cellule = cellule->n )
    {
        printf("-> (%d,%d)=%d",cellule->l,cellule->c,cellule->val);
        printf(" LINE:");
        if ( cellule->pl != NULL )
            printf("]%d,%d]",cellule->pl->l,cellule->pl->c);
        else
            printf("]]");
        printf("-");
        if ( cellule->nl != NULL )
            printf("[%d,%d[",cellule->nl->l,cellule->nl->c);
        else
            printf("[[");
        printf(" COL:");
        if ( cellule->pc != NULL )
            printf("]%d,%d]",cellule->pc->l,cellule->pc->c);
        else
            printf("]]");
        printf("-");
        if ( cellule->nc != NULL )
            printf("[%d,%d[",cellule->nc->l,cellule->nc->c);
        else
            printf("[[");
        printf("\n");
    }
}


int main()
{
    int tours;

    for ( tours=0 ; tours<1 ; tours++ )
    {
        int i;
        int j;
        struct matrice * mat = make(10,10,0);

        set(mat,4,4,1);
        set(mat,4,8,1);
        set(mat,8,4,1);
        set(mat,8,8,1);
        set(mat,2,4,1);
        set(mat,4,2,1);
        set(mat,4,4,2);
        print(mat);
        dump(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,i,j,100+i*10+j);
        print(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,i,j,0);
        print(mat);
        dump(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,9-i,9-j,100+i*10+j);
        print(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,9-i,9-j,0);
        print(mat);
        dump(mat);

        for ( i=0 ; i<10 ; i++ )
            for ( j=0 ; j<10 ; j++ )
                set(mat,i,j,100+i*10+j);
        print(mat);

        for ( i=0 ; i<5 ; i++ )
            for ( j=0 ; j<5 ; j++ )
                set(mat,4-i,4-j,0);
        for ( i=0 ; i<5 ; i++ )
            for ( j=0 ; j<5 ; j++ )
                set(mat,9-2*i,9-2*j,0);
        print(mat);

        destroy(mat);
    }
    printf("Cellules : %d\n",ncellules);
    return 0;
}