home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume3 / hdiff / hdiff.c next >
Encoding:
C/C++ Source or Header  |  1986-11-30  |  33.9 KB  |  1,429 lines
  1. /*
  2.  * f=hdiff.c  (In honor of Mr Heckel, the guy who thought up this
  3.  * algorithm).
  4.  *
  5.  * author - dennis bednar  8 22 84
  6.  * Source file comparison program similar to UNIX diff, except this
  7.  * version outputs moved blocks whereas UNIX diff reports it as
  8.  * delete/add blocks.
  9.  *
  10.  * Algorithm from "A Technique for Isolating Differences Between Files"
  11.  * CACM, April 1978, by Paul Heckel.
  12.  * Some ideas for pass 6 were borrowed from "What's The Diff? -- A File
  13.  * Comparator for CP/M", Dr. Dobb's Journal, August 1984, by D.E. Cortesi.
  14.  * The borrowed idea was that when you are at the beginning of two
  15.  * blocks of lines which link with lines in the other file, but don't
  16.  * match, then the smaller ascending block is the "moved block".
  17.  *
  18.  * The pass5a () is coded directly from his his pass5 Pascal procedure.
  19.  * It doesn't work if the old line being looked up in the symbol table
  20.  * isn't unique!!!  You would have to change the format of the linerec
  21.  * record to make it work.  That's why it's commented out.
  22.  *
  23.  * Output
  24.  
  25. DELETES
  26. -------
  27. old d new         // Single line delete - Old line number 'old' is
  28.             // deleted after new line numbered 'new'
  29. startold,endold d new    // Block line delete - Old block of lines 'startold'
  30.             // to 'endold' are deleted after new line number 'new'
  31.  
  32. INSERTS
  33. -------
  34. old a new        // After old line number 'old' is new line number 'new'
  35. old a startnew,endnew    // After old line number 'old', new lines numbered
  36.             // 'startnew' to 'endnew'
  37.  
  38. CHANGES
  39. -------
  40. old c new        // Change old line numbered 'old' to new line numbered
  41.             // 'new'
  42. old c startnew,endnew    // Change one line to a block of lines.  Old line
  43.             // numbered 'old' becomes the new set of lines.
  44. startold,endold c new    //  Change a block of old lines to one new line.
  45. startold,endold c startnew,endnew    // Change a block of lines to
  46.             // a different block of lines.
  47.  
  48. MOVES
  49. -----
  50. old m new        // Old line number 'old' is moved to new line
  51.             // number 'new'
  52. startold,endold m startnew,endnew  // The old block of lines have been moved
  53.             // and the old line numbers have changed.
  54.  
  55.  
  56. For DELETES, INSERTS, and CHANGES (but not MOVES) the old line and new lines
  57. are displayed as follows:
  58. < old line
  59. > new line
  60.  
  61.  */
  62.  
  63. #include <stdio.h>
  64. #include "stripnl.h"
  65.  
  66. /* choose SKIPCOUNT and BIGPRIME as follows:
  67.  * BIGPRIME > 2*MAXLINES in case both files have all unique lines
  68.  * such that SKIPCOUNT*tablesize probes will hit every slot in hash tbl
  69.  * (hint: use the hashtbl a.out to help you)
  70.  */
  71. #define MAXLINES 5000        /* max lines per file that can handle    */
  72. #define BIGPRIME 10001        /* ideally a prime number > 2*MAXLINES for hash into symtbl */
  73. #define _MAXLINE1 MAXLINES+2    /* two extra for first, last sentinel    */
  74. #define LINESIZE 1024        /* max chars per line            */
  75. #define _LINESIZE LINESIZE+2    /* two extra for '\n', '\0' fgets rtns    */
  76. #define SKIPCOUNT    4    /* reprobe into hash symbol table    */
  77. #define CHANGESEP    "---\n"    /* line separator for change block    */
  78. #define ZAPFLAG    1        /* 1 = yes, remove leading white space    */
  79.  
  80.  
  81.  
  82.  
  83. /* structure for old, new files.  One structure per line.
  84.  * An array oa for the old file, and an array na for the new file.
  85.  * If the line 'oldi' in the old file has NOT been matched to a line in
  86.  * the new file then oa[oldi].flag == L_SYMINDX.
  87.  * Similarly if the line 'newi' in the new file has NOT been matched to
  88.  * a line in the old file, then na[newi].flag == L_SYMINDX.
  89.  * When line 'oldi' in the old file has been matched to line 'newi'
  90.  * in the new file, then oa[oldi].flag == L_LINENUM,
  91.  * na[newi].flag == L_LINENUM, and each line points to the other, e.g.,
  92.  * oa[oldi].lineloc == newi, and na[newi].lineloc == oldi.
  93.  */
  94. struct linerec {
  95.     int lineloc;        /* line number in other file or symtbl index */
  96.     int flag;        /* tells which as defined below        */
  97.     };
  98. #define L_LINENUM 0
  99. #define L_SYMINDX 1
  100.  
  101.  
  102.  
  103. /* symbol table structure.  One per unique line in both files.        */
  104. /* the line is keyed into the array via a hash code            */
  105. struct symrec {
  106.     char    *stashline;    /* saved line in malloc'ed memory    */
  107.     int    ocount;        /* count of lines in old file, 0,1,many    */
  108.     int    ncount;        /* count of lines in new file, 0,1,many    */
  109.     int    olinenum;    /* line number in the old file        */
  110.     };
  111.  
  112.  
  113.  
  114.  
  115. /*globals */
  116. char    *cmd,            /* name of this command            */
  117.     errbuf [_LINESIZE],    /* build err msg for perror        */
  118.     linebuf [_LINESIZE],    /* read line from either file into here    */
  119.     runflag [26],        /* array of options flags set        */
  120.     *oldfile,        /* name of old file            */
  121.     *newfile;        /* name of new file            */
  122.  
  123. FILE    *oldfp,            /* stream for old file            */
  124.     *newfp;            /* stream for new file            */
  125.  
  126. struct linerec
  127.     oa [_MAXLINE1],        /* for old file                */
  128.     na [_MAXLINE1];        /* for new file                */
  129.  
  130. struct symrec
  131.     symtbl [BIGPRIME];    /* symbol table of all lines seen    */
  132.  
  133. int    lastnew,        /* total lines read from new file    */
  134.     lastold,        /* total lines in old file        */
  135.     numsymbols,        /* number of entries in symbol table    */
  136.     debug;            /* debug flag set by -d flag        */
  137.  
  138.  
  139.  
  140.  
  141. /* external non-integer functions */
  142. FILE    *fopen();        /* fopen (3)            */
  143. char    *malloc ();        /* malloc (3)            */
  144. char    *remwhite ();        /* remove white space from string */
  145.  
  146. /* internal non-integer functions */
  147. unsigned int hashline ();
  148.  
  149.  
  150. main (argc, argv)
  151.     int argc;
  152.     char **argv;
  153.  
  154. {
  155.     int    usage;        /* TRUE iff there is a usage error */
  156.  
  157.     /* name of command */
  158.     cmd = argv [0];
  159.  
  160.     /* check arguments and assign global file names */
  161.     usage = 0;        /* assume no usage error */
  162.     debug = 0;        /* assume no debugging wanted */
  163.     if (argc == 3)
  164.         {
  165.         oldfile = argv [1];
  166.         newfile = argv [2];
  167.         }
  168.     else if (argc == 4 && *argv[1] == '-')
  169.         {
  170.         register char *cp;
  171.         for (cp = argv[1]+1; *cp; ++cp)
  172.             if ('a' <= *cp && *cp <= 'z')
  173.                 switch (*cp) {
  174.                 case 'v':    /* verbose - debug */
  175.                 case 'd':    /* drop */
  176.                 case 'm':    /* monotonical by 1 */
  177.                 case 'c':    /* count */
  178.                 case 'w':    /* white space */
  179.                     if (*cp == 'v')
  180.                         debug = 1;
  181.                     runflag [*cp - 'a'] = 1;
  182.                     break;
  183.                 default:
  184.                     usage = 1;
  185.                     break;
  186.                 }
  187.             else
  188.                 usage = 1;
  189.         oldfile = argv[2];
  190.         newfile = argv[3];
  191.         }
  192.     else
  193.         usage = 1;
  194.  
  195.     if (usage)
  196.         {
  197.         fprintf (stderr, "usage: %s [-cdmvw] oldfile newfile\n", cmd);
  198.         exit (1);
  199.         }
  200.  
  201.  
  202.     /* open both files */
  203.     openfiles ();
  204.  
  205.     initvars ();
  206.  
  207.     src_compare ();
  208.  
  209.     /* close both files */
  210.     closefiles ();
  211.  
  212. }
  213.  
  214. initvars ()
  215. {
  216.     numsymbols = 0;
  217. }
  218.  
  219.  
  220.  
  221. /*
  222.  * compare the 2 files in 6 easy passes
  223.  */
  224.  
  225. src_compare ()
  226. {
  227.     pass1 ();    /* read, store new file                */
  228.     pass2 ();    /* read, store old file                */
  229.     pass3 ();    /* match up lines which occur only once        */
  230.     pass4 ();    /* apply rule 2 working toward end        */
  231.     pass5 ();    /* apply rule 2 working toward beginning    */
  232. /*    pass5a ();    /* convert block-moves to insert/deletes    */
  233. /*    dumparray ();    /* see if internal tables are built correctly    */
  234.     pass6 ();    /* print out differences            */
  235.     if (debug)
  236.         printf ("debug: symbol table: occupied = %d, total = %d\n",
  237.         numsymbols, BIGPRIME);
  238. }
  239.  
  240. /*
  241.  * pass 1
  242.  * read in new file.
  243.  */
  244.  
  245. pass1 ()
  246. {
  247.     int
  248.         linenum,    /* which line we are on            */
  249.         stat,        /* result from stripnl            */
  250.         sindex;        /* index into symbol table        */
  251.     char    *cp;        /* char pointer into line        */
  252.  
  253.  
  254.  
  255.     /* read each line of new file in a loop.        */
  256.     /* stop if eof or can't handle that many lines        */
  257.     for (linenum = 0;
  258.         fgets (linebuf, sizeof(linebuf), newfp) != (char *)NULL &&
  259.         ++linenum <= MAXLINES; )
  260.         {
  261.  
  262.         /* strip newline at end and make sure line wasn't too long */
  263.         stat = stripnl (linebuf, sizeof(linebuf) );
  264.  
  265.         if (stat == L_SUCCESS)
  266.             ;
  267.         else if (stat == L_BADFORM)
  268.             fprintf (stderr, "%s: Warning, line %d in file %s not terminated with newline\n",
  269.             cmd, linenum, newfile);
  270.         else
  271.             {
  272.             fprintf (stderr, "%s: line %d longer than %d chars in file %s\n",
  273.             cmd, linenum, LINESIZE, newfile);
  274.             exit (1);
  275.             }
  276.  
  277.         /* if compressing white space, then compress into line buf */
  278.         if (runflag ['w' - 'a'] )
  279.             {
  280.             char *cp;
  281.             cp = remwhite (linebuf, ZAPFLAG);
  282.             strcpy (linebuf, cp);
  283.             }
  284.  
  285.         sindex = addsymbol (linebuf);    /* put line into symbol tbl */
  286.         if (symtbl [sindex].ncount < 2)
  287.             ++symtbl [sindex].ncount;
  288.         na [linenum].lineloc = sindex;
  289.         na [linenum].flag = L_SYMINDX;
  290.         }
  291.  
  292.     /* see if new file was empty */
  293.     if (linenum == 0)
  294.         {
  295.         fprintf (stderr, "%s:  New file %s is empty.  Diff is delete entire old file.\n", newfile, cmd);
  296.         exit (1);
  297.         }
  298.  
  299.     if (linenum > MAXLINES)
  300.         {
  301.         fprintf (stderr, "%s:  New file %s is too big.  Last line read was %d.\n", cmd, newfile, MAXLINES);
  302.         exit (1);
  303.         }
  304.  
  305.     /* assign global number of new lines */
  306.     lastnew = linenum;
  307. }
  308.  
  309.  
  310. /*
  311.  * pass 2
  312.  * read in old file.
  313.  */
  314.  
  315. pass2 ()
  316. {
  317.     int
  318.         linenum,    /* which linenum we are on        */
  319.         stat,        /* result from stripnl            */
  320.         sindex;        /* index into symbol table        */
  321.     char    *cp;        /* char pointer into line        */
  322.  
  323.  
  324.  
  325.     /* read each line of old file in a loop.        */
  326.     /* stop if eof or can't handle that many lines        */
  327.     for (linenum = 0;
  328.         fgets (linebuf, sizeof(linebuf), oldfp) != (char *)NULL &&
  329.         ++linenum <= MAXLINES; )
  330.         {
  331.  
  332. #if 0        /* old way */
  333.         /* strip newline at end and make sure line wasn't too long */
  334.         cp = &linebuf[strlen(linebuf)-1];
  335.         if (*cp == '\n')
  336.             *cp = '\0';
  337.         else if (strlen(linebuf) < sizeof(linebuf)-1)
  338.             fprintf (stderr, "%s: Warning, line %d in file %s not terminated with newline\n", cmd, linenum, oldfile);
  339.         else
  340.             {
  341.             fprintf (stderr, "%s: line %d longer than %d chars in file %s\n",
  342.                 cmd, linenum, LINESIZE, oldfile);
  343.             exit (1);
  344.             }
  345. #endif
  346.  
  347.         /* strip newline at end and make sure line wasn't too long */
  348.         stat = stripnl (linebuf, sizeof(linebuf) );
  349.  
  350.         if (stat == L_SUCCESS)
  351.             ;
  352.         else if (stat == L_BADFORM)
  353.             fprintf (stderr, "%s: Warning, line %d in file %s not terminated with newline\n",
  354.             cmd, linenum, oldfile);
  355.         else
  356.             {
  357.             fprintf (stderr, "%s: line %d longer than %d chars in file %s\n",
  358.             cmd, linenum, LINESIZE, oldfile);
  359.             exit (1);
  360.             }
  361.  
  362.  
  363.         /* if compressing white space, then compress into line buf */
  364.         if (runflag ['w' - 'a'] )
  365.             {
  366.             char *cp;
  367.             cp = remwhite (linebuf, ZAPFLAG);
  368.             strcpy (linebuf, cp);
  369.             }
  370.  
  371.         sindex = addsymbol (linebuf);    /* put line into symbol tbl */
  372.         if (symtbl [sindex].ocount < 2)
  373.             ++symtbl [sindex].ocount;
  374.         symtbl[sindex].olinenum = linenum;
  375.         oa [linenum].lineloc = sindex;
  376.         oa [linenum].flag = L_SYMINDX;
  377.         }
  378.  
  379.     /* see if old file was empty */
  380.     if (linenum == 0)
  381.         {
  382.         fprintf (stderr, "%s:  Old file %s is empty.  Diff is add entire new file.\n", oldfile, cmd);
  383.         exit (1);
  384.         }
  385.  
  386.     if (linenum > MAXLINES)
  387.         {
  388.         fprintf (stderr, "%s:  Old file %s is too big.  Last line read was %d.\n", cmd, oldfile, MAXLINES);
  389.         exit (1);
  390.         }
  391.  
  392.     /* assign number of lines in old file */
  393.     lastold = linenum;
  394. }
  395.  
  396.  
  397. /*
  398.  * Add a line to the symbol table.
  399.  * The hash function determines the initial probe into the symbol table.
  400.  * If the line is new, then core is malloc'ed for storage, and
  401.  * the 'value' is the pointer to the line (empty slot can be found).
  402.  * If the line is old, the old index is returned.
  403.  *
  404.  * returns
  405.  *    index into symbol table
  406.  *    updated global 'numsymbols' for debugging.
  407.  *
  408.  */
  409. addsymbol (line)
  410.     char *line;
  411. {
  412.     int    sindex,        /* symbol table index            */
  413.         firstprobe;    /* index of first probe into symbol tbl    */
  414.     char    *cp;        /* malloc char pointer            */
  415.  
  416.     sindex = firstprobe = hashline (line, BIGPRIME);
  417.  
  418.     /* keep looping until empty slot found or table is full.    */
  419.     /* table cannot be full.                    */
  420.     while (1)
  421.         {
  422.         /* if find an empty slot, add the line there.        */
  423.         if (symtbl [sindex].stashline == (char *)NULL)
  424.             {
  425.             cp = malloc (strlen (linebuf) + 1);
  426.             if (cp == (char *)NULL)
  427.                 {
  428.                 fprintf (stderr, "%s: out of space in function addsymbol\n", cmd);
  429.                 exit (1);
  430.                 }
  431.  
  432.             /* copy the line to storage area        */
  433.             strcpy (cp, line);
  434.  
  435.             /* save the line in the symbol table entry    */
  436.             symtbl [sindex].stashline = cp;
  437.  
  438.             ++numsymbols;
  439.  
  440.             break;
  441.             }
  442.  
  443.         /* if the line is already in the table, then done */
  444.         else if (strcmp (symtbl [sindex].stashline, line) == 0)
  445.             break;
  446.  
  447.         /* else it's a collision with a different line, so
  448.          * let's do linear open addressing.  That is, reprobe
  449.          * SKIPCOUNT slots below, modulo the table size.
  450.          * SKIPCOUNT == 1 means primaray clustering.
  451.          * SKIPCOUNT > 1 means secondary clustering.
  452.          * Check for overflow.
  453.          */
  454.         else
  455.             {
  456.             sindex += SKIPCOUNT;
  457.             if (sindex >= BIGPRIME)
  458.                 sindex = 0;        /* wraparound */
  459.             if (sindex == firstprobe)
  460.                 {
  461.                 fprintf (stderr, "%s: symtbl overflow!\n", cmd);
  462.                 exit (1);
  463.                 }
  464.             }
  465.         }
  466.  
  467.  
  468.     return sindex;
  469. }
  470.  
  471.  
  472. /*
  473.  * pass 3.
  474.  * Process NA array and link lines up which appear only once
  475.  * in both files.
  476.  * Link virtual line pointer at front and end of both files.
  477.  */
  478.  
  479. pass3 ()
  480. {
  481.     int    newi,        /* loop counter thru na array        */
  482.         oldi,        /* index into oa array            */
  483.         symi;        /* index into symbol table array    */
  484.  
  485.     /* loop thru all new lines.  Those that occur once are linked to
  486.      * each other instead of to the symbol table as they used to be.
  487.      */
  488.     for (newi = 1; newi <= lastnew; ++newi)
  489.         {
  490.         symi = na[newi].lineloc;    /* get symbol tbl index    */
  491.         if ((symtbl[symi].ocount == 1) && (symtbl[symi].ncount == 1))
  492.             {
  493.             oldi = symtbl[symi].olinenum;
  494.             linkup (oldi, newi);
  495.             }
  496.         }
  497.  
  498.     /* link the virtual line 'begin' of each file to each other */
  499.     linkup (0, 0);
  500.  
  501.     /* line the virtual line 'end' of each file to each other */
  502.     linkup (lastold+1, lastnew+1);
  503. }
  504.  
  505.  
  506. /*
  507.  * pass 4
  508.  * loop ascending thru new lines in na array.
  509.  * If line newi in new file is linked to line oldi in old file,
  510.  * but the next lines of each contain the same symbol table
  511.  * pointer, then link na[newi+1] to oa[oldi+1].
  512.  */
  513. pass4 ()
  514. {
  515.     int    newi,
  516.         oldi;
  517.  
  518.     /* process 'begin', all lines in new file, but NOT virtual 'end' */
  519.     for (newi = 0; newi <= lastnew; ++newi)
  520.         {
  521.         if (na[newi].flag == L_LINENUM)
  522.             {
  523.             oldi = na[newi].lineloc;
  524.             if ((na[newi+1].flag == L_SYMINDX) &&
  525.                 (oa[oldi+1].flag == L_SYMINDX) &&
  526.                 (na[newi+1].lineloc == oa[oldi+1].lineloc))
  527.                 linkup (oldi+1, newi+1);
  528.             }
  529.         }
  530. }
  531.  
  532.  
  533. /*
  534.  * pass 5
  535.  * Process new file in descending order.
  536.  * Similar to pass 4, but in reverse order.
  537.  */
  538. pass5 ()
  539. {
  540.     int    newi,
  541.         oldi;
  542.  
  543.     /* process 'end', all lines in new file, but NOT virtual 'begin' */
  544.     for (newi = lastnew+1; newi > 0; --newi)
  545.         {
  546.         if (na[newi].flag == L_LINENUM)
  547.             {
  548.             oldi = na[newi].lineloc;
  549.             if ((na[newi-1].flag == L_SYMINDX) &&
  550.                 (oa[oldi-1].flag == L_SYMINDX) &&
  551.                 (na[newi-1].lineloc == oa[oldi-1].lineloc))
  552.                 linkup (oldi-1, newi-1);
  553.             }
  554.         }
  555.  
  556.  
  557. }
  558.  
  559.  
  560. /*
  561.  * pass 6
  562.  * output the differences.
  563.  */
  564. pass6 ()
  565. {
  566.     int    oldi,        /* current line number in old file    */
  567.         newi,        /* current line number in new file    */
  568.         oldmatch,    /* true iff old line matches SOME line in new file */
  569.         newmatch,    /* true iff new line matches SOME line in old file */
  570.         omatcount,    /* match count in old file        */
  571.         nmatcount,    /* match count in new file        */
  572.         odrop,        /* old file "relative drop" of new line */
  573.         ndrop,        /* new file "relative drop" of old line */
  574.         ocomp,        /* comparison result for old file    */
  575.         ncomp,        /* comparison result for new file    */
  576.         ospan,        /* size of old monotonical block    */
  577.         nspan;        /* size of new monotonical block    */
  578.  
  579.     for (oldi = 0, newi = 0; oldi <= lastold+1 && newi <= lastnew+1;)
  580.         {
  581.  
  582.         /* set flags to indicate if each line is linked
  583.          * to another line in the other file.
  584.          */
  585.  
  586.         /* is old line linked to another line in the new file? */
  587.         oldmatch = (oa[oldi].flag == L_LINENUM);
  588.  
  589.         /* is new line linked to another line in the old file? */
  590.         newmatch = (na[newi].flag == L_LINENUM);
  591.  
  592.  
  593.         /* if old line moved from old file up (toward begin) in
  594.          * new file, then we have already processed the block
  595.          * move in the new file.  Just skip the line in the old file.
  596.          */
  597.         if (oa[oldi].lineloc < newi && oldmatch)
  598.             {
  599.             ++oldi;
  600.             continue;
  601.             }
  602.  
  603.         /* if old line moved from old file down (toward end) in
  604.          * old file, then we we have already processed the block
  605.          * move in the old file.  Just skip the line in the new file.
  606.          */
  607.         else if (na[newi].lineloc < oldi && newmatch)
  608.             {
  609.             ++newi;
  610.             continue;
  611.             }
  612.  
  613.  
  614.         /* there are four combinations of booleans oldmatch and newmatch */
  615.  
  616.         /* if both lines are linked to SOME line in the other file */
  617.         if (oldmatch && newmatch)
  618.             {
  619.             /* if both lines match each other, then go
  620.              * to next line in both files
  621.              */
  622.             if (oa[oldi].lineloc == newi)
  623.                 {
  624.                 if (debug)
  625.                     printf ("debug: Same old line %d and new line %d\n", oldi, newi);
  626.                 ++oldi;
  627.                 ++newi;
  628.                 continue;
  629.                 }
  630.  
  631.             /* blocks not linked to each other.
  632.              * If there are more lines in oldfile that
  633.              * are monotonically increasing by one in
  634.              * the new file, then this is normal, and the
  635.              * new block is moved down in the old file.
  636.              * If there are more lines in newfile that
  637.              * are monotonically increasing by one in
  638.              * the old file, then this is normal, and
  639.              * the old block is moved down in the new file.
  640.              */
  641.  
  642.             /* get size of old block which is monitonically
  643.              * increasing by one in the new file.
  644.              */
  645.             ospan = oldmon (oldi);
  646.  
  647.             /* get size of new block which is monitonically
  648.              * increasing by one in the old file.
  649.              */
  650.             nspan = newmon (newi);
  651.  
  652.             /* count the number of lines in the old file between
  653.              * the current line and the line which corresponds
  654.              * to the first new moved line.
  655.              */
  656.             omatcount = gomatch (oldi, na[newi].lineloc);
  657.  
  658.             /* count the number of lines in the new file between
  659.              * the current line and the old moved line which
  660.              * match.
  661.              */
  662.             nmatcount = gnmatch (newi, oa[oldi].lineloc);
  663.  
  664.             /* get number of old lines the new block drops down
  665.              * into the old file.  If old drop is < new drop
  666.              * then the old block has moved down further into
  667.              * the new file than the new block has moved down
  668.              * into the old file.  The relative steepness of the
  669.              * slope of the line from oldi to its matched line
  670.              * is more than the steepnes of the other slope,
  671.              * and since line don't usually move far, assume
  672.              * that the new to old move is a match, and the
  673.              * old to new is an old block moved down.
  674.              */
  675.             odrop = na [newi].lineloc - oldi;
  676.  
  677.             /* same for new file */
  678.             ndrop = oa [oldi].lineloc - newi;
  679.  
  680.             /* if 'd' flag is set, use 'drop' for match */
  681.             if (runflag ['d' - 'a'])
  682.                 {
  683.                 ocomp = odrop;
  684.                 ncomp = ndrop;
  685.                 }
  686.             /* if 'm' flag set, use bigger monotonically increasing
  687.              * by 1 span
  688.              */
  689.             else if (runflag ['m' - 'a'])
  690.                 {
  691.                 ocomp = ospan;
  692.                 ncomp = nspan;
  693.                 }
  694.             /* if 'c' flag then use match count */
  695.             else if (runflag ['c' - 'a'])
  696.                 {
  697.                 ocomp = omatcount;
  698.                 ncomp = nmatcount;
  699.                 }
  700.             /* default - best one */
  701.             else
  702.                 {
  703.                 ocomp = omatcount;
  704.                 ncomp = nmatcount;
  705.                 }
  706.  
  707.  
  708.  
  709.             if (ocomp < ncomp)        /* old block moved down */
  710.                 eatold (&oldi, ospan);    /* eat old mv'ed blk */
  711.             else                /* new block moved down */
  712.                 eatnew (&newi, nspan);    /* eat new mv'ed blk */
  713.             }
  714.  
  715.         /* new lines added (inserted) into new file */
  716.         else if (oldmatch && !newmatch)
  717.             newinsert (oldi, &newi); /* skip new insert blk */
  718.  
  719.         /* old lines deleted from old file */
  720.         else if (!oldmatch && newmatch)
  721.             olddelete (&oldi, newi);    /* skip old delete block */
  722.  
  723.         /* old lines changed into new file */
  724.         else    /* !oldmatch && !newmatch */
  725.             oldchange (&oldi, &newi); /* skip old delete block and new insert block */
  726.         }
  727. }
  728.  
  729. /*
  730.  * block of old lines beginning at linenum 'oldi' are matched with
  731.  * a block of new lines.  Count the number of lines in the old block
  732.  * which are monotonically increasing by one in the new file.
  733.  * returns -
  734.  *    size of old block
  735.  */
  736. oldmon (oldi)
  737.     int    oldi;
  738. {
  739.     int    osize,        /* size of old block            */
  740.         expnew,        /* line number expected in new file    */
  741.         curoldnum;    /* current line number in old file    */
  742.  
  743.  
  744.     curoldnum = oldi;    /* save old line number so can tell
  745.                  * how big the old block is at the end
  746.                  */
  747.  
  748.     do
  749.         {
  750.         expnew = oa[curoldnum].lineloc + 1;
  751.         ++curoldnum;
  752.         }
  753.     while ((curoldnum <= lastold+1)            /* in bounds */
  754.         && (expnew == oa[curoldnum].lineloc)    /* monotonical by 1 */
  755.         && (oa[curoldnum].flag == L_LINENUM));    /* match */
  756.  
  757.     osize = curoldnum - oldi;
  758.  
  759.     if (debug)
  760.         printf ("debug: lines %d-%d of old file are monotonical\n", oldi, curoldnum-1);
  761.  
  762.     return osize;
  763. }
  764.  
  765.  
  766. newmon (newi)
  767.     int    newi;
  768. {
  769.     int    nsize,        /* size of new block            */
  770.         expold,        /* line number expected in old file    */
  771.         curnewnum;    /* current line number in new file    */
  772.  
  773.  
  774.     curnewnum = newi;    /* save new line number so can tell
  775.                  * how big the new block is at the end
  776.                  */
  777.  
  778.     do
  779.         {
  780.         expold = na[curnewnum].lineloc + 1;
  781.         ++curnewnum;
  782.         }
  783.     while ((curnewnum <= lastnew+1)            /* in bounds */
  784.         && (expold == na[curnewnum].lineloc)    /* monotonical by 1 */
  785.         && (na[curnewnum].flag == L_LINENUM));    /* match */
  786.  
  787.     nsize = curnewnum - newi;
  788.  
  789.     if (debug)
  790.         printf ("debug: lines %d-%d of new file are monotonical\n", newi, curnewnum-1);
  791.  
  792.     return nsize;
  793. }
  794.  
  795.  
  796. /*
  797.  * eat old block beginning with old line number *'oldi' and 'ospan' lines
  798.  * These old lines are moved down into the new file.
  799.  * The output format is
  800. 5,6m7,8        // old lines 5-6 are moved to new lines 7-8
  801. 5m7        // old line 5 is moved to new line 7
  802.  * returns
  803.  *    *oldi = updated old line number
  804.  */
  805. eatold (oldi, ospan)
  806.     int    *oldi,
  807.         ospan;
  808. {
  809.     int    newi;
  810.  
  811.     /* get starting line number of new block */
  812.     newi = oa[*oldi].lineloc;
  813.  
  814.     /* how many lines in the old block - one or more? */
  815.     if (ospan == 1)
  816.         printf ("%dm%d\n", *oldi, newi);
  817.     else if (ospan > 1)
  818.         printf ("%d,%dm%d,%d\n", *oldi, *oldi+ospan-1, newi, newi+ospan-1);
  819.     else
  820.         {
  821.         fprintf (stderr, "%s: unexpected negative ospan = %d in function eatold\n", ospan);
  822.         exit (1);
  823.         }
  824.  
  825.     /* return old line number after the old moved block */
  826.     *oldi += ospan;
  827.  
  828. }
  829.  
  830.  
  831. /*
  832.  * eat the new block
  833.  * Like eatold, but works on the new block.
  834.  */
  835.  
  836. eatnew (newi, nspan)
  837.     int    *newi,
  838.         nspan;
  839. {
  840.     int    oldi;
  841.  
  842.     /* get starting line number in the old file */
  843.     oldi = na[*newi].lineloc;
  844.  
  845.     if (nspan == 1)
  846.         printf ("%dm%d\n", oldi, *newi);
  847.     else if (nspan > 1)
  848.         printf ("%d,%dm%d,%d\n", oldi, oldi+nspan-1, *newi, *newi+nspan-1);
  849.     else
  850.         {
  851.         fprintf (stderr, "%s: unexpected negative nspan = %d in function eatnew\n", nspan);
  852.         exit (1);
  853.         }
  854.  
  855.     *newi += nspan;
  856. }
  857.  
  858. /*
  859.  * Print new lines inserted in old file to transform into new file
  860.  * input
  861.  *    oldi - one after the current old line number !!!!!!!
  862.  *    *newi - first line number in new file of inserted line.
  863.  * output
  864.  *    *newi - next line number in new file after inserted block.
  865.  *    printed lines of the form
  866.  *
  867.  
  868. 5a7        // after old line 5 add one newline as newline 7
  869. > new line 8
  870.  
  871.  * or
  872.  
  873. 5a7,8        // after old line 5 add two newlines as newline 7 and 8
  874. > new line 7
  875. > new line 8
  876.  
  877.  */
  878. newinsert (oldi, newi)
  879.     int    oldi,
  880.         *newi;
  881. {
  882.     int    nsize,        /* number of lines inserted in new file    */
  883.         csize,        /* current number of lines in a loop    */
  884.         curnewline;    /* current line number in new file    */
  885.  
  886.     if (debug)
  887.         printf ("debug: Found New Insert.  Old line %d.  New line %d.\n", oldi, *newi);
  888.  
  889.     /* first compute size so we know which format to use (single line
  890.      * insert or multiline insert)
  891.      * Get the number of lines in the insert block.
  892.      */
  893.     nsize = inssize (*newi);
  894.  
  895.     if (nsize == 1)
  896.         printf ("%da%d\n", oldi-1, *newi);
  897.     else if (nsize > 1)
  898.         printf ("%da%d,%d\n", oldi-1, *newi, *newi+nsize-1);
  899.     else
  900.         {
  901.         fprintf (stderr, "%s: unexpected new block size = %d in function newinsert\n", nsize);
  902.         exit (1);
  903.         }
  904.  
  905.     /* print the new inserted lines */
  906.     for (curnewline = *newi, csize = nsize; csize > 0; ++curnewline, --csize)
  907.         printf ("> %s\n", symtbl [ na[curnewline].lineloc ].stashline);
  908.  
  909.     /* return the new line */
  910.     *newi += nsize;
  911. }
  912.  
  913.  
  914.  
  915.  
  916. /*
  917.  * Print that a group of lines in the old file was deleted
  918.  * input -
  919.  *    *oldi - line number in old file where the group of lines begins
  920.  *    newi - line number + 1 in new file after which the delete occurs.
  921.  * output
  922.  *    *oldi - updated with the next old line after the delete block
  923. 5d7        // old line 5 deleted after new line 7
  924. < old line 5
  925. 5,6d7        // old lines 5 and 6 deleted after new line 7
  926. < old line 5
  927. < old line 6
  928.  *
  929.  */
  930.  
  931. olddelete (oldi, newi)
  932.     int    *oldi,
  933.         newi;
  934. {
  935.     int    osize,        /* number of lines deleted in old file    */
  936.         csize,        /* current size in in the loop        */
  937.         curoldline;    /* current line number in old file    */
  938.  
  939.     if (debug)
  940.         printf ("debug: Found Old Delete.  Old line %d.  New line %d.\n", *oldi, newi);
  941.  
  942.     /* first compute size so we know which format to use (single line
  943.      * insert or multiline delete)
  944.      * Get the number of lines in the old delete block.
  945.      */
  946.     osize = delsize (*oldi);
  947.  
  948.  
  949.     /* print the header for the line deletes */
  950.     if (osize == 1)
  951.         printf ("%dd%d\n", *oldi, newi-1);
  952.     else if (osize > 1)
  953.         printf ("%d,%dd%d\n", *oldi, *oldi+osize-1, newi-1);
  954.     else
  955.         {
  956.         fprintf (stderr, "%s: unexpected old block size = %d in function olddelete\n", osize);
  957.         exit (1);
  958.         }
  959.  
  960.     /* print the old deleted lines */
  961.     for (curoldline = *oldi, csize = osize; csize > 0; ++curoldline, --csize)
  962.         printf ("< %s\n", symtbl [ oa[curoldline].lineloc ].stashline);
  963.  
  964.     /* return the old line after the delete block */
  965.     *oldi += osize;
  966. }
  967.  
  968.  
  969.  
  970.  
  971. /*
  972.  * Print that a group of old lines has been updated to a group of new lines.
  973.  * input
  974.  *    *oldi = line number of start of old lines
  975.  *    *newi = line number of start of new lines
  976.  * output
  977.  *    *oldi = line number after block deleted in the old file
  978.  *    *newi = line number after block inserted in the new file
  979.  *    print statements according to one of 4 forms:
  980. startold c startnew
  981. startold c startnew,endnew
  982. startold,endold c startnew
  983. startold,endold c startnew,endnew
  984.  * Examples
  985. 5c7        // old line 5 has been replace by new line 7
  986. < old line 5
  987. ---
  988. > new line 7
  989.  
  990. 5,6c7,8        // old lines 5 and 6 have been replaced by new lines 7 and 8
  991. < old line 5
  992. < old line 6
  993. ---
  994. > new line 7
  995. > new line 8
  996.  */
  997.  
  998. oldchange (oldi, newi)
  999.     int    *oldi,
  1000.         *newi;
  1001. {
  1002.     int    curold,        /* current line number in old file    */
  1003.         curnew,        /* current line number in new file    */
  1004.         osize,        /* size of block changed in old file    */
  1005.         nsize,        /* size of block changed in new file    */
  1006.         csize,        /* current block size for the loop    */
  1007.         curoldline,    /* current line number in old file    */
  1008.         curnewline;    /* current line number in new file    */
  1009.  
  1010.     if (debug)
  1011.         printf ("debug: Found Changed Lines.  Old line %d.  New line %d\n", *oldi, *newi);
  1012.  
  1013.     /* get the size of the old deleted block and the new inserted block */
  1014.     osize = delsize (*oldi);
  1015.     nsize = inssize (*newi);
  1016.  
  1017.     /* print the header for the old deleted block */
  1018.     if (osize == 1)
  1019.         printf ("%dc", *oldi);
  1020.     else if (osize > 1)
  1021.         printf ("%d,%dc", *oldi, (*oldi)+osize-1);
  1022.     else
  1023.         {
  1024.         fprintf (stderr, "%s: unexpected old block size = %d in function oldchange\n", osize);
  1025.         exit (1);
  1026.         }
  1027.  
  1028.     /* print the header for the new inserted block */
  1029.     if (nsize == 1)
  1030.         printf ("%d\n", *newi);
  1031.     else if (nsize > 1)
  1032.         printf ("%d,%d\n", *newi, (*newi)+nsize-1);
  1033.     else
  1034.         {
  1035.         fprintf (stderr, "%s: unexpected new block size = %d in function oldchange\n", nsize);
  1036.         exit (1);
  1037.         }
  1038.  
  1039.     /* Now print the old changed (delete) lines */
  1040.     for (curoldline = *oldi, csize = osize; csize > 0; ++curoldline, --csize)
  1041.         printf ("< %s\n", symtbl [ oa[curoldline].lineloc ].stashline);
  1042.  
  1043.     /* print line change separator */
  1044.     printf (CHANGESEP);
  1045.  
  1046.     /* Now print the new changed (inserted) lines */
  1047.     for (curnewline = *newi, csize = nsize; csize > 0; ++curnewline, --csize)
  1048.         printf ("> %s\n", symtbl [ na[curnewline].lineloc ].stashline);
  1049.  
  1050.     /* return the new old and new lines */
  1051.     *oldi += osize;
  1052.     *newi += nsize;
  1053. }
  1054.  
  1055.  
  1056.  
  1057. /*
  1058.  * these next two routines are called upon by functions
  1059.  *    olddelete, newinsert, and oldchange
  1060.  */
  1061.  
  1062. /*
  1063.  * starting with line number 'newi' in the new file, count the number of
  1064.  * lines in the insert block.
  1065.  *
  1066.  * Loop thru the insert block.  The block is a series of new lines
  1067.  * that aren't linked to lines in the old file.  That is, each
  1068.  * inserted line points to a symbol table entry.
  1069.  */
  1070. inssize (newi)
  1071.     int    newi;
  1072. {
  1073.     register
  1074.     int    curnewline,        /* current line number in new file    */
  1075.         nsize;            /* number of new lines in insert block    */
  1076.  
  1077.  
  1078.     curnewline = newi;
  1079.     while (curnewline <= lastnew+1 && na[curnewline].flag == L_SYMINDX)
  1080.         ++curnewline;
  1081.  
  1082.     /* curnewline is now the new line number AFTER the insert block */
  1083.  
  1084.     /* compute the number of lines in the insert block */
  1085.     nsize = curnewline - newi;
  1086.  
  1087.     if (debug)
  1088.         printf ("debug: at new line %d, the insert block has %d lines\n", newi, nsize);
  1089.  
  1090.     return nsize;
  1091. }
  1092.  
  1093.  
  1094.  
  1095. /*
  1096.  * compute the number of lines in the old delete block beginning
  1097.  * with old line number 'oldi' and return it.
  1098.  *
  1099.  * Loop thru the delete block.  The block is a series of old lines
  1100.  * that aren't linked to lines in the new file.  That is, each
  1101.  * deleted line points to a symbol table entry.
  1102.  */
  1103.  
  1104. delsize (oldi)
  1105.     int oldi;
  1106. {
  1107.     register
  1108.     int    curoldline,    /* current line number in old file    */
  1109.         osize;        /* number of old lines in delete block    */
  1110.  
  1111.     curoldline = oldi;
  1112.     while (curoldline <= lastold+1 && oa[curoldline].flag == L_SYMINDX)
  1113.         ++curoldline;
  1114.  
  1115.     /* curoldline is now the old line number AFTER the delete block */
  1116.  
  1117.     /* compute the number of lines in the delete block */
  1118.     osize = curoldline - oldi;
  1119.  
  1120.     if (debug)
  1121.         printf ("debug: at old line %d, the delete block has %d lines\n", oldi, osize);
  1122.  
  1123.     /* return the delete block size */
  1124.     return osize;
  1125. }
  1126.  
  1127.  
  1128.  
  1129.  
  1130.  
  1131.  
  1132. /*
  1133.  * dump the oa and na internal arrays which is the crudest way
  1134.  * to print the file comparisons.
  1135.  * This routine may be called in lieu of pass 6 as a debugging tool.
  1136.  */
  1137. dumparray ()
  1138. {
  1139.     int    oldi,
  1140.         newi;
  1141.  
  1142.     for (oldi = 0; oldi <= lastold+1; ++oldi)
  1143.         if (oa[oldi].flag == L_LINENUM)
  1144.             printf ("oa[%d] = %d\n", oldi, oa[oldi].lineloc);
  1145.         else
  1146.             printf ("oa[%d] INSERTED.\n", oldi);
  1147.  
  1148.  
  1149.     for (newi = 0; newi <= lastnew+1; ++newi)
  1150.         if (na[newi].flag == L_LINENUM)
  1151.             printf ("na[%d] = %d\n", newi, na[newi].lineloc);
  1152.         else
  1153.             printf ("na[%d] DELETED.\n", newi);
  1154. }
  1155.  
  1156.  
  1157.  
  1158. /* borrowed from hashname.c
  1159.  * eventually will be removed.
  1160.  */
  1161.  
  1162. unsigned int hashline (name,modval)
  1163.  
  1164.     register char *name;
  1165.     register unsigned int modval;
  1166.  
  1167. {
  1168.     register unsigned int i;
  1169.  
  1170.     i=0;
  1171.     while (*name != '\0'){
  1172.         i=((i<<2)+(*name&~040))%modval;
  1173.  
  1174.         name++;
  1175.         }
  1176.  
  1177.     return(i);
  1178. }
  1179.  
  1180.  
  1181.  
  1182. /*
  1183.  * linkup line oldi in old file to line newi' in new file
  1184.  */
  1185. linkup (oldi, newi)
  1186.     int    oldi,
  1187.         newi;
  1188. {
  1189.     oa[oldi].lineloc = newi;
  1190.     oa[oldi].flag = L_LINENUM;
  1191.     na[newi].lineloc = oldi;
  1192.     na[newi].flag = L_LINENUM;
  1193. }
  1194.  
  1195.  
  1196. /*
  1197.  * pass 5a converts block moves to delete/insert pairs
  1198.  */
  1199. pass5a ()
  1200. {
  1201.     int    oldi,
  1202.         newi;
  1203.  
  1204.     for (oldi = 1, newi = 1; oldi <= lastold+1; )
  1205.         {
  1206.         while (oa[oldi].flag == L_SYMINDX && oldi <= lastold+1)
  1207.             ++oldi;        /* skip deletes in old file    */
  1208.         while (na[newi].flag == L_SYMINDX && newi <= lastnew+1)
  1209.             ++newi;        /* skip inserts in new file    */
  1210.         if (oldi > lastold+1)
  1211.             break;
  1212.         if (newi > lastnew+1)
  1213.             break;
  1214.  
  1215.         if (oa[oldi].lineloc == newi)    /* begin matching lines */
  1216.             {
  1217.             oldi++;
  1218.             newi++;
  1219.             }
  1220.         else                /* discontinuity ?*/
  1221.             {
  1222.             if (oa[oldi].lineloc != lastnew+1)
  1223.                 resolve (oldi, newi);    /* yes */
  1224.             else
  1225.                 ;            /* no, sentinel */
  1226.             }
  1227.         }
  1228. }
  1229.  
  1230.  
  1231. resolve (oldi, newi)
  1232.     int    oldi,
  1233.         newi;
  1234.  
  1235. {
  1236.     int    xo, xn;
  1237.     int    t, ospan, nspan;
  1238.     int    symi;
  1239.  
  1240.     /* measure block starting at oa[oldi] */
  1241.     xo = oldi;
  1242.     do
  1243.         {
  1244.         t = 1 + oa[xo].lineloc;
  1245.         xo++;
  1246.         }
  1247.     while (t != oa[xo].lineloc);
  1248.     ospan = xo - oldi;
  1249.  
  1250.     /* measure block starting at na[newi] */
  1251.     xn = newi;
  1252.     do
  1253.         {
  1254.         t = 1 + na[xn].lineloc;
  1255.         xn++;
  1256.         }
  1257.     while (t != na[xn].lineloc);
  1258.     nspan = xn - newi;
  1259.  
  1260.  
  1261.  
  1262.     if (ospan < nspan)
  1263.         {
  1264.         xo = oldi;
  1265.         xn = oa[oldi].lineloc;
  1266.         t = ospan;
  1267.         oldi = oldi + ospan;
  1268.         }
  1269.     else
  1270.         {
  1271.         xn = newi;
  1272.         xo = na[newi].lineloc;
  1273.         t = nspan;
  1274.         newi = newi + nspan;
  1275.         }
  1276.  
  1277.     while (t > 0)
  1278.         {
  1279.         symi = 0;
  1280.         while (symi < BIGPRIME && symtbl[symi].olinenum != xo)
  1281.             symi++;
  1282.  
  1283.         if (symi >= BIGPRIME)
  1284.             {
  1285.             fprintf (stderr, "%s: can't find old line %d in symtbl\n", cmd, xo);
  1286.             dumpsym ();
  1287.             exit (1);
  1288.             }
  1289.  
  1290.  
  1291.         /* link the lines to the same symbol tbl entry */
  1292.         oa[xo].flag = L_SYMINDX;
  1293.         oa[xo].lineloc = symi;
  1294.         na[xn].flag = L_SYMINDX;
  1295.         na[xn].lineloc = symi;
  1296.  
  1297.         ++xo;
  1298.         ++xn;
  1299.         --t;
  1300.         }
  1301. }
  1302.  
  1303. /*
  1304.  * open global files 'oldfile' and 'newfile'
  1305.  */
  1306. openfiles ()
  1307. {
  1308.     /* open old source file for reading */
  1309.     oldfp = fopen (oldfile, "r");
  1310.     if (oldfp == (FILE *)NULL)
  1311.         {
  1312.         sprintf (errbuf, "%s: can't oldfile open %s", cmd, oldfile);
  1313.         perror (errbuf);
  1314.         exit (1);
  1315.         }
  1316.  
  1317.  
  1318.  
  1319.  
  1320.     /* open new source file for reading */
  1321.     newfp = fopen (newfile, "r");
  1322.     if (newfp == (FILE *)NULL)
  1323.         {
  1324.         sprintf (errbuf, "%s: can't open newfile %s", cmd, newfile);
  1325.         perror (errbuf);
  1326.         exit (2);
  1327.         }
  1328. }
  1329.  
  1330.  
  1331. /*
  1332.  * close both files
  1333.  */
  1334. closefiles ()
  1335. {
  1336.     fclose (oldfp);
  1337.     fclose (newfp);
  1338. }
  1339.  
  1340.  
  1341. /*
  1342.  * dump contents of symbol table
  1343.  * For now, only the old line number and the line of text.
  1344.  */
  1345. dumpsym ()
  1346. {
  1347.     register int i;
  1348.  
  1349.     printf ("Symbol Table Contents:\n");
  1350.     printf ("------ ----- --------\n");
  1351.     printf ("old_line_num: <line of text>\n");
  1352.     for (i = 0; i < BIGPRIME; ++i)
  1353.         if (symtbl[i].olinenum != 0)
  1354.             printf ("%d: %s\n", symtbl[i].olinenum, symtbl[i].stashline);
  1355. }
  1356.  
  1357.  
  1358. /*
  1359.  * get number of old lines which match new lines.
  1360.  *
  1361.  * return the number of lines number n in the old file such that
  1362.  * startline <= n < endline which are linked to lines in the new
  1363.  * file, and are strictly monotonically increasing in the new file (doesn't
  1364.  * have to be monotonically increasing by one, but it can't be the same).
  1365.  * Once the monotonical increase stops, we stop counting.
  1366.  * 'startline' is definitely matched to some line in new file.
  1367.  */
  1368.  
  1369. gomatch (startline, endline)
  1370.     int    startline,
  1371.         endline;
  1372.  
  1373. {
  1374.     register int    count,    /* lines counted in old file        */
  1375.             newi,    /* current new line number last matched    */
  1376.             oldi;    /* current old line number        */
  1377.  
  1378.  
  1379.     /* stop counting lines if reach endline or find non-monitonical
  1380.      * increase in the new file.  newi set to zero is virtual line begin.
  1381.      */
  1382.     for (oldi = startline, count = 0, newi = 0;
  1383.         oldi < endline && oldi <= lastold+1; ++oldi)
  1384.         if (oa[oldi].flag != L_LINENUM)        /* old line doesn't match any new line */
  1385.             continue;            /* so skip old line */
  1386.         else if (oa[oldi].lineloc > newi)    /* monotonical? */
  1387.             {
  1388.             newi = oa[oldi].lineloc;    /* yes, save new line number */
  1389.             ++count;
  1390.             }
  1391.         else
  1392.             break;                /* no, stop counting */
  1393.  
  1394.     return count;
  1395. }
  1396.  
  1397.  
  1398. /*
  1399.  * same idea as gomatch, except count lines in new file which match lines in
  1400.  * old file and old file lines are strictly monotonically increasing
  1401.  */
  1402. gnmatch (startline, endline)
  1403.     int    startline,
  1404.         endline;
  1405.  
  1406. {
  1407.     register int    count,
  1408.             oldi,
  1409.             newi;
  1410.  
  1411.  
  1412.     /* stop counting lines if reach endline or find non-monitonical
  1413.      * increase in the old file.  oldi set to zero is virtual line begin.
  1414.      */
  1415.     for (newi = startline, count = 0, oldi = 0;
  1416.         newi < endline && newi <= lastnew+1; ++newi)
  1417.         if (na[newi].flag != L_LINENUM)        /* new line doesn't match any new line */
  1418.             continue;            /* so skip new line */
  1419.         else if (na[newi].lineloc > oldi)    /* monotonical? */
  1420.             {
  1421.             oldi = na[newi].lineloc;    /* yes, save old line number */
  1422.             ++count;            /* bump count */
  1423.             }
  1424.         else
  1425.             break;                /* no, stop counting */
  1426.  
  1427.     return count;
  1428. }
  1429.