diff.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,393 行 · 第 1/3 页

}

/*
 * Sort hash entries
 */

void sort( vector, vecsize )
     LINE           *vector;     /* What to sort       */
     SLONG             vecsize;    /* How many to sort      */
{
    register SLONG      j;
    register LINE       *aim;
    register LINE       *ai;
    SLONG               mid;
    SLONG               k;
    LINE                work;

    for( j = 1; j <= vecsize; j *= 2 )
        ;
    mid = ( j - 1 );
    while( ( mid /= 2 ) != 0 ) {
        k = vecsize - mid;
        for( j = 1; j <= k; j++ ) {
            for( ai = &vector[j]; ai > vector; ai -= mid ) {
                aim = &ai[mid];
                if( aim < ai )
		    break;      /* ?? Why ??     */
                if( aim->hash > ai->hash ||
                    ( aim->hash == ai->hash &&
                     aim->serial > ai->serial ) ) break;
                work.hash = ai->hash;
                ai->hash = aim->hash;
                aim->hash = work.hash;
                work.serial = ai->serial;
                ai->serial = aim->serial;
                aim->serial = work.serial;
            }
        }
    }
}

/*
 * Build equivalence class vector
 */

void equiv()
{
    register LINE       *ap;
    union {
        LINE    *bp;
        short   *mp;
    }                   r;
    register SLONG      j;
    LINE                *atop;

#ifdef DEBUG
    printf( "equiv entry\n" );
    for( j = 1; j <= slenA; j++ ) {
        printf( "sfileA[%d] = %6d %06o\n",
                j, sfileA[j].serial, sfileA[j].hash );
    }
    for( j = 1; j <= slenB; j++ ) {
        printf( "sfileB[%d] = %6d %06o\n",
                j, sfileB[j].serial, sfileB[j].hash );
    }
#endif
    j = 1;
    ap = &sfileA[1];
    r.bp = &sfileB[1];
    atop = &sfileA[slenA];
    while( ap <= atop && j <= slenB ) {
        if( ap->hash < r.bp->hash ) {
            ap->hash = 0;
            ap++;
        } else if( ap->hash == r.bp->hash ) {
            ap->hash = j;
            ap++;
        } else {
            r.bp++;
            j++;
        }
    }
    while( ap <= atop ) {
        ap->hash = 0;
        ap++;
    }
    sfileB[slenB + 1].hash = 0;
#ifdef DEBUG
    printf( "equiv exit\n" );
    for( j = 1; j <= slenA; j++ ) {
        printf( "sfileA[%d] = %6d %06o\n",
                j, sfileA[j].serial, sfileA[j].hash );
    }
    for( j = 1; j <= slenB; j++ ) {
        printf( "sfileB[%d] = %6d %06o\n",
                j, sfileB[j].serial, sfileB[j].hash );
    }
#endif
    ap = &sfileB[0];
    atop = &sfileB[slenB];
    r.mp = &member[0];
    while( ++ap <= atop ) {
        r.mp++;
        *r.mp = -( ap->serial );
        while( ap[1].hash == ap->hash ) {
            ap++;
            r.mp++;
            *r.mp = ap->serial;
        }
    }
    r.mp[1] = -1;
#ifdef DEBUG
    for( j = 0; j <= slenB; j++ ) {
        printf( "member[%d] = %d\n", j, member[j] );
    }
#endif
}

/*
 * Build class vector
 */

void unsort()
{
    SLONG               *temp;
    register SLONG      *tp;
    union {
        LINE    *ap;
        short   *cp;
    }                   u;
    LINE                *evec;
    short               *eclass;
#ifdef DEBUG
    SLONG               i;
#endif

    temp = ( SLONG * ) myalloc( ( slenA + 1 ) * sizeof( SLONG ), "unsort scratch" );
    u.ap = &sfileA[1];
    evec = &sfileA[slenA];
    while( u.ap <= evec ) {
#ifdef DEBUG
        printf( "temp[%2d] := %06o\n", u.ap->serial, u.ap->hash );
#endif
        temp[u.ap->serial] = u.ap->hash;
        u.ap++;
    }

    /*
     * Copy into class vector and free work space
     */
    u.cp = &class[1];
    eclass = &class[slenA];
    tp = &temp[1];
    while( u.cp <= eclass ) {
        *u.cp++ = *tp++;
    }
    myfree( &temp );
#ifdef DEBUG
    printf( "unsort exit\n" );
    for( i = 1; i <= slenA; i++ ) {
        printf( "class[%d] = %d %06o\n", i, class[i], class[i] );
    }
#endif
}

/*
 * Generate maximum common subsequence chain in clist[]
 */

SLONG newcand();
SLONG subseq()
{
    SLONG               a;
    register ULONG      ktop;
    register SLONG      b;
    register SLONG      s;
    ULONG               r;
    SLONG               i;
    SLONG               cand;

    klist[0] = newcand( 0, 0, -1 );
    klist[1] = newcand( slenA + 1, slenB + 1, -1 );
    ktop = 1;                   /* -> guard entry  */
    for( a = 1; a <= slenA; a++ ) {

        /*
         * For each non-zero element in fileA ...
         */
        if( ( i = class[a] ) == 0 )
	    continue;
        cand = klist[0];        /* No candidate now  */
        r = 0;                  /* Current r-candidate  */
        do {
#ifdef DEBUG
            printf( "a = %d, i = %d, b = %d\n", a, i, member[i] );
#endif

            /*
             * Perform the merge algorithm
             */
            if( ( b = member[i] ) < 0 ) {
                b = -b;
            }
#ifdef DEBUG
            printf( "search(%d, %d, %d) -> %d\n",
                    r, ktop, b, search( r, ktop, b ) );
#endif
            if( ( s = search( r, ktop, b ) ) != 0 ) {
                if( clist[klist[s]].b > b ) {
                    klist[r] = cand;
                    r = s;
                    cand = newcand( a, b, klist[s - 1] );
#ifdef DEBUG
                    dumpklist( ktop, "klist[s-1]->b > b" );
#endif
                }
                if( s >= ktop ) {
                    klist[ktop + 1] = klist[ktop];
                    ktop++;
#ifdef DEBUG
                    klist[r] = cand;
                    dumpklist( ktop, "extend" );
#endif
                    break;
                }
            }
        } while( member[++i] > 0 );
        klist[r] = cand;
    }
#ifdef DEBUG
    printf( "last entry = %d\n", ktop - 1 );
#endif
    return( ktop - 1 );          /* Last entry found  */
}

SLONG
newcand( a, b, pred )
    SLONG             a;          /* Line in fileA      */
    SLONG             b;          /* Line in fileB      */
    SLONG             pred;       /* Link to predecessor, index in cand[]  */
{
    register CANDIDATE  *new;

    clength++;
    if( ++clength >= csize ) {
        csize += CSIZE_INC;
        clist = ( CANDIDATE * ) compact( ( char *) clist,
                                         csize * sizeof( CANDIDATE ),
                                         "extending clist" );
    }
    new = &clist[clength - 1];
    new->a = a;
    new->b = b;
    new->link = pred;
    return( clength - 1 );
}

/*
 * Search klist[low..top] (inclusive) for b.  If klist[low]->b >= b,
 * return zero.  Else return s such that klist[s-1]->b < b and
 * klist[s]->b >= b.  Note that the algorithm presupposes the two
 * preset "fence" elements, (0, 0) and (slenA, slenB).
 */

SLONG search( low, high, b )
     register ULONG    low;
     register ULONG    high;
     register SLONG    b;
{
    register SLONG      temp;
    register ULONG      mid;

    if( clist[klist[low]].b >= b )
        return( 0 );
    while( ( mid = ( low + high ) / 2 ) > low ) {
        if( ( temp = clist[klist[mid]].b ) > b )
            high = mid;
        else if( temp < b )
            low = mid;
        else {
            return( mid );
        }
    }
    return( mid + 1 );
}

void unravel( k )
     register SLONG    k;
{
    register SLONG      i;
    register CANDIDATE  *cp;
    SLONG               first_trailer;
    SLONG               difference;

    first_trailer = lenA - suffix;
    difference = lenB - lenA;
#ifdef DEBUG
    printf( "first trailer = %d, difference = %d\n",
            first_trailer, difference );
#endif
    for( i = 0; i <= lenA; i++ ) {
        match[i] = ( i <= prefix ) ? i
            : ( i > first_trailer ) ? i + difference
            : 0;
    }
#ifdef DEBUG
    printf( "unravel\n" );
#endif
    while( k != -1 ) {
        cp = &clist[k];
#ifdef DEBUG
        if( k < 0 || k >= clength )
            error( "Illegal link -> %d", k );
        printf( "match[%d] := %d\n", cp->a + prefix, cp->b + prefix );
#endif
        match[cp->a + prefix] = cp->b + prefix;
        k = cp->link;
    }
}

/*
 * Check for hash matches (jackpots) and collect random access indices to
 * the two files.
 *
 * It should be possible to avoid doing most of the ftell's by noticing
 * that we are not doing a context diff and noticing that if a line
 * compares equal to the other file, we will not ever need to know its
 * file position.  FIXME.
 */

INT check( char *fileAname, char *fileBname )
{
    SLONG       a;          /* Current line in file A  */
    SLONG       b;          /* Current line in file B  */
    SLONG       jackpot;

    fileAname= fileAname;
    fileBname= fileBname;
    /*
     * The VAX C ftell() returns the address of the CURRENT record, not the
     * next one (as in DECUS C or, effectively, other C's).  Hence, the values
     * are "off by one" in the array.  OFFSET compensates for this.
     */

#define OFFSET 0

    b = 1;
    rewind( infd[0] );
    rewind( infd[1] );
    /*
     * See above; these would be over-written on VMS anyway.
     */

    oldseek[0] = ftell( infd[0] );
    newseek[0] = ftell( infd[1] );

    jackpot = 0;
#ifdef DEBUG
    printf( "match vector\n" );
    for( a = 0; a <= lenA; a++ )
        printf( "match[%d] = %d\n", a, match[a] );
#endif
    for( a = 1; a <= lenA; a++ ) {
        if( match[a] == 0 ) {
            /* Unique line in A */
            oldseek[a + OFFSET] = ftell( infd[0] );
            getline( infd[0], text );
            continue;
        }
        while( b < match[a] ) {
            /* Skip over unique lines in B */
            newseek[b + OFFSET] = ftell( infd[1] );
            getline( infd[1], textb );
            b++;
        }

        /*
         * Compare the two, supposedly matching, lines. Unless we are going
         * to print these lines, don't bother to remember where they are.  We
         * only print matching lines if a context diff is happening, or if a
         * jackpot occurs.
         */
        //      if (cflag) {
        oldseek[a + OFFSET] = ftell( infd[0] );
        newseek[b + OFFSET] = ftell( infd[1] );
        //      }
        getline( infd[0], text );
        getline( infd[1], textb );
        if( !streq( text, textb ) ) {
#ifdef DEBUG
            fprintf( stderr, "Spurious match:\n" );
            fprintf( stderr, "line %d in %s, \"%s\"\n",
                     a, fileAname, text );
            fprintf( stderr, "line %d in %s, \"%s\"\n",
                     b, fileBname, textb );
#endif
            match[a] = 0;
            jackpot++;
        }
        b++;
    }
    for( ; b <= lenB; b++ ) {
        newseek[b + OFFSET] = ftell( infd[1] );
        getline( infd[1], textb );
    }
    /*
     * The logical converse to the code up above, for NON-VMS systems, to
     * store away an fseek() pointer at the beginning of the file.  For VMS,
     * we need one at EOF...
     */

    return( jackpot );
}

void output( char *fileAname, char *fileBname )
{
    SLONG       astart;
    SLONG       aend = 0;
    SLONG       bstart;
    SLONG       bend;

    rewind( infd[0] );
    rewind( infd[1] );
    match[0] = 0;
    match[lenA + 1] = lenB + 1;
    if( !eflag ) {
        if( cflag ) {

            /*
             * Should include ctime style dates after the file names, but
             * this would be non-trivial on OSK.  Perhaps there should be a
             * special case for stdin.
             */
            printf( "*** %s\n--- %s\n", fileAname, fileBname );
        }

        /*
         * Normal printout
         */
        for( astart = 1; astart <= lenA; astart = aend + 1 ) {

            /*
             * New subsequence, skip over matching stuff
             */
            while( astart <= lenA && match[astart] == ( match[astart - 1] + 1 ) ) {
                astart++;
            }

            /*
             * Found a difference, setup range and print it
             */
            bstart = match[astart - 1] + 1;
            aend = astart - 1;
            while( aend < lenA && match[aend + 1] == 0 ) {
                aend++;
            }
            bend = match[aend + 1] - 1;
            match[aend] = bend;
            change( astart, aend, bstart, bend );
        }
    } else {

        /*
         * Edit script output -- differences are output "backwards" for the
         * benefit of a line-oriented editor.