Return to diffh.c CVS log

Up to [MW Coherent from dump] / coherent / d / bin / diff

Annotation of coherent/d/bin/diff/diffh.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Half-hearted version of diff (doesn't
        !             3:  * use the complicated algorithm).
        !             4:  * This algorithm works on arbitrary files
        !             5:  * but is only intended where changes are
        !             6:  * minimal and well-spaced.  There is another
        !             7:  * algorithm which also takes space but is at
        !             8:  * least guaranteed to be linear in time and space (unlike
        !             9:  * Least Common Subsequence) and sometimes produces
        !            10:  * more realistic results (and sometimes it doesn't)
        !            11:  * Consult: "A Technique for Isolating Diffeences between
        !            12:  * Files", Paul Heckel, CACM, November 1978.
        !            13:  * This shares code with the normal
        !            14:  * diff though.
        !            15:  */
        !            16: 
        !            17: #include "diff.h"
        !            18: 
        !            19: #define        NPEND   200             /* Default # pending lines */
        !            20: #define        NMATCH  2               /* Minimum lines in a row to have a match */
        !            21: 
        !            22: /*
        !            23:  * Structure for each line 
        !            24:  * This is referenced by the
        !            25:  * structure for each file
        !            26:  * below.
        !            27:  */
        !            28: typedef        struct  LINE {
        !            29:        unsigned        l_num;          /* Line number */
        !            30:        struct LINE     *l_next;        /* Pointer for ungetting lines */
        !            31:        char    l_text[];               /* Data of line */
        !            32: }      LINE;
        !            33: 
        !            34: /*
        !            35:  * Structure of pending lines
        !            36:  * and ungot lines stored for
        !            37:  * each of the input files.
        !            38:  */
        !            39: typedef        struct  PENDING {
        !            40:        FILE    *p_fp;          /* I/O stream for input */
        !            41:        int     p_eof;          /* Reached EOF on this input */
        !            42:        char    *p_fn;          /* File name */
        !            43:        LINE    *p_master;      /* Master input buffer */
        !            44:        LINE    *p_work;        /* Current working line */
        !            45:        LINE    *p_ungot;       /* Ungot lines */
        !            46:        LINE    *p_lines[NPEND]; /* Pending lines */
        !            47: }      PENDING;
        !            48: 
        !            49: PENDING        p1, p2;
        !            50: 
        !            51: LINE   *lcopy();
        !            52: 
        !            53: /*
        !            54:  * A NOP routine so that diff()
        !            55:  * gets invoked.
        !            56:  */
        !            57: /* ARGSUSED */
        !            58: diffh(args)
        !            59: char **args;
        !            60: {
        !            61: }
        !            62: 
        !            63: /*
        !            64:  * The actual code to produce list
        !            65:  * of differences by a stupider
        !            66:  * (but cheaper) algorithm.
        !            67:  */
        !            68: diff(fp1, fp2)
        !            69: FILE *fp1;
        !            70: FILE *fp2;
        !            71: {
        !            72:        register int top, bot;
        !            73:        register int i;
        !            74: 
        !            75:        p1.p_master = p1.p_work = (LINE *)alloc(sizeof(LINE) + LSIZE);
        !            76:        p2.p_master = p2.p_work = (LINE *)alloc(sizeof(LINE) + LSIZE);
        !            77:        p1.p_fp = fp1;
        !            78:        p2.p_fp = fp2;
        !            79:        p1.p_fn = fn1;
        !            80:        p2.p_fn = fn2;
        !            81:        while (lget(&p1) | lget(&p2)) {
        !            82:                register char *s1, *s2;
        !            83: 
        !            84:                s1 = p1.p_work->l_text;
        !            85:                s2 = p2.p_work->l_text;
        !            86:                if (*s1=='\0' && *s2=='\0')
        !            87:                        continue;
        !            88:                if ((*equal)(s1, s2)) {
        !            89:                        text(s1);
        !            90:                        continue;
        !            91:                }
        !            92:                top = 0;
        !            93:                lpend(&p1, top);
        !            94:                lpend(&p2, top++);
        !            95:                do {
        !            96:                        if (top >= NPEND)
        !            97:                                cerr("Out of memory, lines %d and %d",
        !            98:                                    p1.p_lines[0]->l_num, p2.p_lines[0]->l_num);
        !            99:                        /*
        !           100:                         * Not checked, lget has
        !           101:                         * to stop going over EOF
        !           102:                         * by itself.
        !           103:                         */
        !           104:                        lget(&p1);
        !           105:                        lget(&p2);
        !           106:                        lpend(&p1, top);
        !           107:                        lpend(&p2, top++);
        !           108:                        bot = top-NMATCH;
        !           109:                        for (i=0; i<bot; i++) {
        !           110:                                if (lsearch(i, bot)) {
        !           111:                                        lunget(&p1, i+NMATCH, top);
        !           112:                                        break;
        !           113:                                }
        !           114:                                if (lsearch(bot, i)) {
        !           115:                                        lunget(&p2, i+NMATCH, top);
        !           116:                                        break;
        !           117:                                }
        !           118:                        }
        !           119:                } while (i>bot || i==bot && !lsearch(i, i));
        !           120:        }
        !           121: }
        !           122: 
        !           123: /*
        !           124:  * Get a line and put it into the current
        !           125:  * working position.
        !           126:  * Return 0 at EOF.
        !           127:  */
        !           128: lget(pp)
        !           129: register PENDING *pp;
        !           130: {
        !           131:        if (pp->p_master != pp->p_work)
        !           132:                free(pp->p_work);
        !           133:        if (pp->p_ungot != NULL) {
        !           134:                pp->p_work = pp->p_ungot;
        !           135:                pp->p_ungot = pp->p_ungot->l_next;
        !           136:                return (1);
        !           137:        }
        !           138:        pp->p_work = pp->p_master;
        !           139:        return (lgets(pp));
        !           140: }
        !           141: 
        !           142: /*
        !           143:  * Unget pending lines between
        !           144:  * `beg' and `end' that are
        !           145:  * not already dealt with.
        !           146:  */
        !           147: lunget(pp, beg, end)
        !           148: register PENDING *pp;
        !           149: register int beg, end;
        !           150: {
        !           151:        while (--end >= beg) {
        !           152:                pp->p_lines[end]->l_next = pp->p_ungot;
        !           153:                pp->p_ungot = pp->p_lines[end];
        !           154:                pp->p_lines[end] = NULL;
        !           155:        }
        !           156: }
        !           157: 
        !           158: /*
        !           159:  * Copy a line to a new (allocated)
        !           160:  * line space.
        !           161:  */
        !           162: LINE *
        !           163: lcopy(lp)
        !           164: register LINE *lp;
        !           165: {
        !           166:        register LINE *rlp;
        !           167:        register char *cp;
        !           168: 
        !           169:        for (cp = lp->l_text; *cp != '\0'; cp++)
        !           170:                ;
        !           171:        rlp = (LINE *)alloc(cp-lp->l_text+1 + sizeof(LINE));
        !           172:        rlp->l_num = lp->l_num;
        !           173:        rlp->l_next = NULL;
        !           174:        strcpy(rlp->l_text, lp->l_text);
        !           175:        return (rlp);
        !           176: }
        !           177: 
        !           178: /*
        !           179:  * Save line away in a pending line
        !           180:  * position, specified by `pos'.
        !           181:  */
        !           182: lpend(pp, pos)
        !           183: register PENDING *pp;
        !           184: register int pos;
        !           185: {
        !           186:        if (pp->p_lines[pos] != NULL)
        !           187:                free(pp->p_lines[pos]);
        !           188:        if (pp->p_master != pp->p_work) {
        !           189:                pp->p_lines[pos] = pp->p_work;
        !           190:                pp->p_work = pp->p_master;
        !           191:        } else
        !           192:                pp->p_lines[pos] = lcopy(pp->p_work);
        !           193: }
        !           194: 
        !           195: /*
        !           196:  * Read a string from input (specified
        !           197:  * by the PENDING pointer) and throw away
        !           198:  * partial lines.
        !           199:  */
        !           200: lgets(pp)
        !           201: register PENDING *pp;
        !           202: {
        !           203:        register int c;
        !           204:        register char *s;
        !           205:        register unsigned lim = LSIZE;
        !           206: 
        !           207:        s = pp->p_master->l_text;
        !           208:        if (pp->p_eof) {
        !           209:                *s = '\0';
        !           210:                return (0);
        !           211:        }
        !           212:        while (--lim > 0 && (c = getc(pp->p_fp)) != EOF)
        !           213:                if ((*s++ = c) == '\n')
        !           214:                        break;
        !           215:        *s = '\0';
        !           216:        if (c == EOF) {
        !           217:                if (s != pp->p_master->l_text)
        !           218:                        fprintf(stderr, "diff: partial line omitted from %s\n",
        !           219:                            pp->p_fn);
        !           220:                pp->p_eof++;
        !           221:                return (0);
        !           222:        }
        !           223:        pp->p_master->l_num++;
        !           224:        return (1);
        !           225: }
        !           226: 
        !           227: /*
        !           228:  * Search for a match in the pending lines.
        !           229:  * The two parameters are `pos1' and `pos2'
        !           230:  * for the position to start searching in
        !           231:  * file1 and file2, respectively.  The
        !           232:  * search looks for at least NMATCH lines.
        !           233:  */
        !           234: lsearch(pos1, pos2)
        !           235: int pos1;
        !           236: int pos2;
        !           237: {
        !           238:        register LINE **lpp1, **lpp2;
        !           239:        register int i;
        !           240:        register char *s1, *s2;
        !           241:        register int ln11, ln12, ln21, ln22;
        !           242: 
        !           243:        lpp1 = &p1.p_lines[pos1];
        !           244:        lpp2 = &p2.p_lines[pos2];
        !           245:        /*
        !           246:         * Empty strings are actually
        !           247:         * dummies for after EOF.
        !           248:         */
        !           249:        for (i=0; i<NMATCH; i++) {
        !           250:                s1 = lpp1[i]->l_text;
        !           251:                s2 = lpp2[i]->l_text;
        !           252:                if (*s1!='\0' || *s2!='\0')
        !           253:                        if (!(*equal)(s1, s2))
        !           254:                                break;
        !           255:        }
        !           256:        if (i < NMATCH)
        !           257:                return (0);
        !           258:        lpp1 = p1.p_lines;
        !           259:        lpp2 = p2.p_lines;
        !           260:        ln11 = lpp1[0]->l_num;
        !           261:        ln12 = lpp1[pos1-1]->l_num;
        !           262:        ln21 = lpp2[0]->l_num;
        !           263:        ln22 = lpp2[pos2-1]->l_num;
        !           264:        if (pos1 == 0)
        !           265:                append(ln11, ln21, ln22);
        !           266:        else if (pos2 == 0)
        !           267:                delete(ln11, ln12, ln21);
        !           268:        else
        !           269:                change(ln11, ln12, ln21, ln22);
        !           270:        for (i = 0; i < pos1; i++)
        !           271:                text1(lpp1[i]->l_text);
        !           272:        prsep();
        !           273:        for (i = 0; i < pos2; i++)
        !           274:                text2(lpp2[i]->l_text);
        !           275:        prend();
        !           276:        for (i=0; i<NMATCH; i++)
        !           277:                if (*(s1 = lpp1[i+pos1]->l_text) != '\0')
        !           278:                        text(s1);
        !           279:        return (1);
        !           280: }
        !           281: 
        !           282: /*
        !           283:  * Allocator that also checks for
        !           284:  * an prints a message if out of space.
        !           285:  */
        !           286: char *
        !           287: alloc(nb)
        !           288: unsigned nb;
        !           289: {
        !           290:        register char *rp;
        !           291: 
        !           292:        if ((rp = calloc(nb, 1)) == NULL)
        !           293:                cerr("out of memory");
        !           294:        return (rp);
        !           295: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.