home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume7 / cacm-diff < prev    next >
Encoding:
Text File  |  1989-07-02  |  30.4 KB  |  766 lines
  1. Newsgroups: comp.sources.misc
  2. From: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc)
  3. Subject: v07i056: July CACM Diff program
  4. Reply-To: Donald.Lindsay@MATHOM.GANDALF.CS.CMU.EDU
  5.  
  6. Posting-number: Volume 7, Issue 56
  7. Submitted-by: Donald.Lindsay@MATHOM.GANDALF.CS.CMU.EDU
  8. Archive-name: cacm-diff
  9.  
  10. # Delete all above this line, put the rest in a file, and do
  11. #    sh <filename>
  12. # This creates file diff.c, the file difference program described
  13. # in the July CACM ( Literate Programming column, July 1989).
  14. # (The tabs have been turned to blanks: "unexpand" can reverse this.)
  15. #
  16. echo extracting diff.c
  17. cat > diff.c <<\EOF
  18. /***************************************************************************
  19. *
  20. * diff         Text file difference utility.
  21. * ----         Copyright 1987, 1989 by Donald C. Lindsay,
  22. *              School of Computer Science,  Carnegie Mellon University.
  23. *              Copyright 1982 by Symbionics.
  24. *              Use without fee is permitted when not for direct commercial
  25. *              advantage, and when credit to the source is given. Other uses
  26. *              require specific permission.
  27. *
  28. * USEAGE:      diff oldfile newfile
  29. *
  30. * This program assumes that "oldfile" and "newfile" are text files.
  31. * The program writes to stdout a description of the changes which would
  32. * transform "oldfile" into "newfile".
  33. *
  34. * The printout is in the form of commands, each followed by a block of
  35. * text. The text is delimited by the commands, which are:
  36. *
  37. *    DELETE AT n
  38. *         ..deleted lines
  39. *
  40. *    INSERT BEFORE n
  41. *         ..inserted lines
  42. *
  43. *    n MOVED TO BEFORE n
  44. *         ..moved lines
  45. *
  46. *    n CHANGED FROM
  47. *         ..old lines
  48. *    CHANGED TO
  49. *         ..newer lines
  50. *
  51. * The line numbers all refer to the lines of the oldfile, as they are
  52. *    numbered before any commands are applied.
  53. * The text lines are printed as-is, without indentation or prefixing. The
  54. *    commands are printed in upper case, with a prefix of ">>>>", so that
  55. *    they will stand out. Other schemes may be preferred.
  56. * Input lines which are longer than MAXLINELEN characters will be chopped 
  57. *    into multiple lines.
  58. * Files which contain more than MAXLINECOUNT lines cannot be processed.
  59. * The algorithm is taken from Communications of the ACM, Apr78 (21, 4, 264-),
  60. *    "A Technique for Isolating Differences Between Files."
  61. *    Ignoring I/O, and ignoring the symbol table, it should take O(N) time.
  62. *    This implementation takes fixed space, plus O(U) space for the symbol
  63. *    table (where U is the number of unique lines). Methods exist to change
  64. *    the fixed space to O(N) space.
  65. * Note that this is not the only interesting file-difference algorithm. In
  66. *    general, different algorithms draw different conclusions about the
  67. *    changes that have been made to the oldfile. This algorithm is sometimes
  68. *    "more right", particularly since it does not consider a block move to be 
  69. *    an insertion and a (separate) deletion. However, on some files it will be
  70. *    "less right". This is a consequence of the fact that files may contain
  71. *    many identical lines (particularly if they are program source). Each
  72. *    algorithm resolves the ambiguity in its own way, and the resolution
  73. *    is never guaranteed to be "right". However, it is often excellent.
  74. * This program is intended to be pedagogic.  Specifically, this program was
  75. *    the basis of the Literate Programming column which appeared in the
  76. *    Communications of the ACM (CACM), in the June 1989 issue (32, 6,
  77. *    740-755).
  78. * By "pedagogic", I do not mean that the program is gracefully worded, or
  79. *    that it showcases language features or its algorithm. I also do not mean
  80. *    that it is highly accessible to beginners, or that it is intended to be
  81. *    read in full, or in a particular order. Rather, this program is an
  82. *    example of one professional's style of keeping things organized and
  83. *    maintainable.
  84. * This program is a de-engineered version of a program which uses less
  85. *    memory and less time.  The article points out that the "symbol" arrays
  86. *    can be implemented as arrays of pointers to arrays, with dynamic
  87. *    allocation of the subarrays.  (Macros are very useful for hiding the
  88. *    two-level accesses.) This allows an extremely large value for
  89. *    MAXLINECOUNT, without dedicating fixed arrays. (The "other" and
  90. *    "blocklen" arrays can be allocated after the input phase, when the exact
  91. *    sizes are known.) The only slow piece of code is the "strcmp" in the tree
  92. *    descent: it can be speeded up by keeping a hash in the tree node, and
  93. *    only using "strcmp" when two hashes happen to be equal.
  94. * This program has been coded with 5-column tab settings.
  95. *
  96. * Change Log
  97. * ----------
  98. * 10jun89 D.C.Lindsay, CMU: posted version created.
  99. *         Copyright notice changed to ACM style, and Dept. is now School.
  100. *         ACM article referenced in docn.
  101. * 26sep87 D.C.Lindsay, CMU: publication version created.
  102. *         Condensed all 1982/83 change log entries.
  103. *         Removed all command line options, and supporting code. This 
  104. *         simplified the input code (no case reduction etc). It also
  105. *         simplified the symbol table, which was capable of remembering
  106. *         offsets into files (instead of strings), and trusting (!) hash
  107. *         values to be unique.
  108. *         Removed dynamic allocation of arrays: now fixed static arrays.
  109. *         Removed speed optimizations in symtab package.
  110. *         Removed string compression/decompression code.
  111. *         Recoded to Unix standards from old Lattice/MSDOS standards.
  112. *         (This affected only the #include's and the IO.)
  113. *         Some renaming of variables, and rewording of comments.
  114. * 1982/83 D.C.Lindsay, Symbionics: created.
  115. *
  116. */
  117.  
  118. #define MAXLINECOUNT 20000         /* arbitrary */
  119. #define MAXLINELEN  255            /* arbitrary */
  120.  
  121. #include <stdio.h>
  122. /************************************************/
  123. #define UNREAL (MAXLINECOUNT+2)  /* block len > any possible real block len */
  124.  
  125. /************************************************/
  126.  
  127. struct info{                         /* This is the info kept per-file.     */
  128.      FILE *file;                     /* File handle that is open for read.  */
  129.      int maxline;                    /* After input done, # lines in file.  */
  130.      char *symbol[ MAXLINECOUNT+2 ]; /* The symtab handle of each line.     */
  131.      int other   [ MAXLINECOUNT+2 ]; /* Map of line# to line# in other file */
  132.                                      /* ( -1 means don't-know ).            */
  133. } oldinfo, newinfo;
  134.  
  135. int blocklen[ MAXLINECOUNT+2 ];
  136. /* The above is the info about found blocks. It will be set to 0, except
  137. *  at the line#s where blocks start in the old file. At these places it
  138. *  will be set to the # of lines in the block. During the printout phase,
  139. *  this value will be reset to -1 if the block is printed as a MOVE block.
  140. *  (This is because the printout phase will encounter the block twice, but
  141. *  must only print it once. )
  142. *  The array declarations are to MAXLINECOUNT+2 so that we can have two
  143. *  extra lines (pseudolines) at line# 0 and line# MAXLINECOUNT+1 (or less).
  144. */
  145.  
  146.                /* function predeclarations */
  147.                /* (These could be eliminated by a reordering) */
  148. FILE *openfile();
  149. void inputscan();
  150. void storeline();
  151. void transform();
  152. void scanunique();
  153. void scanafter();
  154. void scanbefore();
  155. void scanblocks();
  156. void printout();
  157. void newconsume();
  158. void oldconsume();
  159. void showdelete();
  160. void showinsert();
  161. void showchange();
  162. void skipold();
  163. void showsame();
  164. void showmove();
  165. void initsymtab();
  166. char *addsymbol();
  167. int symbolisunique();
  168. int lineofsymbol();
  169. void showsymbol();
  170. /***************************************************************************
  171. *
  172. * main         Entry point.
  173. * ----
  174. *
  175. * NOTE: no routines return error codes. Instead, any routine may complain
  176. *       to stderr and then exit with error to the system. This property 
  177. *       is not mentioned in the various routine headers.
  178. *
  179. ***************************************************************************/
  180. main( argcount, argstrings )
  181. int argcount;
  182. char *argstrings[];
  183. {
  184.      if( argcount != 3 ) {
  185.           fprintf( stderr, "TRY: diff oldfile newfile\n\007" );  /* (bel) */
  186.           exit(1);
  187.      }
  188.      printf( ">>>> Difference of file \"%s\" and file \"%s\".\n\n",
  189.           argstrings[1], argstrings[2] );
  190.      initsymtab();
  191.      oldinfo.file = openfile( argstrings[1] );
  192.      newinfo.file = openfile( argstrings[2] );
  193.      /* note, we don't process until we know both files really do exist. */
  194.      inputscan( &oldinfo );
  195.      inputscan( &newinfo );
  196.      transform();
  197.      printout();
  198.      exit(0);       /* OK */
  199. }
  200. /***************************************************************************
  201. *
  202. * openfile     Opens the filename for reading.
  203. * --------     Returns the file handle.
  204. *
  205. ***************************************************************************/
  206. FILE *openfile( filename )
  207. char *filename;
  208. {
  209.      FILE *file = fopen( filename, "r" );
  210.      if( file == NULL ) {
  211.           fprintf( stderr, "CAN'T OPEN FILE %s\n\007", filename );  /* (bel) */
  212.           exit(1);
  213.      }
  214.      return file;
  215. }
  216. /***************************************************************************
  217. *
  218. * inputscan    Reads the file specified by pinfo->file.
  219. * ---------    Places the lines of that file in the symbol table.
  220. *              Sets pinfo->maxline to the number of lines found.
  221. *              Expects initsymtab has been called.
  222. *
  223. ****************************************************************************/
  224. void inputscan( pinfo )
  225. struct info *pinfo;
  226. {
  227.      char ch, linebuffer[ MAXLINELEN+1 ];    /* accumulate lines to here */
  228.      int linelen = 0;                        /* # of chars in linebuffer */
  229.  
  230.      pinfo-> maxline = 0;
  231.      for(;;) {
  232.           ch = getc( pinfo-> file );
  233.           if( ch == EOF ) break;
  234.           if( ch == '\n' ){                                 /* end of line */
  235.                storeline( linebuffer, linelen, pinfo );
  236.                linelen = 0;
  237.           }else if( linelen >= MAXLINELEN ) {               /* overflow */
  238.                storeline( linebuffer, linelen, pinfo );
  239.                linelen = 1;
  240.                linebuffer[ 0 ] = ch;                   /* start next line */
  241.           }else linebuffer[ linelen++ ] = ch;
  242.      }
  243.      if( linelen != 0 ) storeline( linebuffer, linelen, pinfo );  /* runt */
  244. }
  245. /**************************************************************************
  246. *
  247. * storeline    Places line into symbol table.
  248. * ---------    Expects pinfo-> maxline initted: increments.
  249. *              Places symbol table handle in pinfo->symbol.
  250. *              Expects pinfo is either &oldinfo or &newinfo.
  251. *              Expects linebuffer contains linelen nonnull chars.
  252. *              Expects linebuffer has room to write a trailing nul into.
  253. *              Expects initsymtab has been called.
  254. *
  255. ***************************************************************************/
  256. void storeline( linebuffer, linelen, pinfo )
  257. char linebuffer[];
  258. int linelen;
  259. struct info *pinfo;
  260. {
  261.      int linenum = ++( pinfo-> maxline );    /* note, no line zero */
  262.      if( linenum > MAXLINECOUNT ) {
  263.           fprintf( stderr, "MAXLINECOUNT exceeded, must stop.\n\007" );
  264.           exit(1);
  265.      }
  266.      linebuffer[ linelen ] = '\0';           /* nul terminate */
  267.      pinfo-> symbol[ linenum ] =
  268.           addsymbol( linebuffer, linelen, pinfo == &oldinfo, linenum );
  269. }
  270. /***************************************************************************
  271. *
  272. * transform    Expects both files in symtab.
  273. * ---------    Expects valid "maxline" and "symbol" in oldinfo and newinfo.
  274. *              Analyzes the file differences and leaves its findings in
  275. *              the global arrays oldinfo.other, newinfo.other, and blocklen.
  276. *
  277. ***************************************************************************/
  278. void transform()
  279. {                                  
  280.      int oldline, newline;
  281.      int oldmax = oldinfo.maxline + 2;  /* Count pseudolines at  */
  282.      int newmax = newinfo.maxline + 2;  /* ..front and rear of file */
  283.  
  284.      for(oldline=0; oldline < oldmax; oldline++ ) oldinfo.other[oldline]= -1;
  285.      for(newline=0; newline < newmax; newline++ ) newinfo.other[newline]= -1;
  286.  
  287.      scanunique();  /* scan for lines used once in both files */
  288.      scanafter();   /* scan past sure-matches for non-unique blocks */
  289.      scanbefore();  /* scan backwards from sure-matches */
  290.      scanblocks();  /* find the fronts and lengths of blocks */
  291. }
  292. /***************************************************************************
  293. *
  294. * scanunique   Expects both files in symtab, and oldinfo and newinfo valid.
  295. * ----------   Scans for lines which are used exactly once in each file.
  296. *              The appropriate "other" array entries are set to the line# in
  297. *              the other file.
  298. *              Claims pseudo-lines at 0 and XXXinfo.maxline+1 are unique.
  299. *
  300. ***************************************************************************/
  301. void scanunique()
  302. {
  303.      int oldline, newline;
  304.      char *psymbol;
  305.  
  306.      for( newline = 1; newline <= newinfo.maxline; newline++ ) {
  307.           psymbol = newinfo.symbol[ newline ];
  308.           if( symbolisunique( psymbol )) {        /* 1 use in each file */
  309.                oldline = lineofsymbol( psymbol );
  310.                newinfo.other[ newline ] = oldline;     /* record a 1-1 map */
  311.                oldinfo.other[ oldline ] = newline;
  312.           }
  313.      }
  314.      newinfo.other[ 0 ] = 0;
  315.      oldinfo.other[ 0 ] = 0;
  316.      newinfo.other[ newinfo.maxline + 1 ] = oldinfo.maxline + 1;
  317.      oldinfo.other[ oldinfo.maxline + 1 ] = newinfo.maxline + 1;
  318. }
  319. /***************************************************************************
  320. *
  321. * scanafter    Expects both files in symtab, and oldinfo and newinfo valid.
  322. * ---------    Expects the "other" arrays contain positive #s to indicate
  323. *              lines that are unique in both files.
  324. *              For each such pair of places, scans past in each file.
  325. *              Contiguous groups of lines that match non-uniquely are
  326. *              taken to be good-enough matches, and so marked in "other".
  327. *              Assumes each other[0] is 0.
  328. *
  329. ***************************************************************************/
  330. void scanafter()
  331. {
  332.      int oldline, newline;
  333.  
  334.      for( newline = 0; newline <= newinfo.maxline; newline++ ) {
  335.           oldline = newinfo.other[ newline ];
  336.           if( oldline >= 0 ) {          /* is unique in old & new */
  337.                for(;;) {                /* scan after there in both files */
  338.                     if( ++oldline > oldinfo.maxline   ) break; 
  339.                     if( oldinfo.other[ oldline ] >= 0 ) break;
  340.                     if( ++newline > newinfo.maxline   ) break; 
  341.                     if( newinfo.other[ newline ] >= 0 ) break;
  342.  
  343.                     /* oldline & newline exist, and aren't already matched */
  344.  
  345.                     if( newinfo.symbol[ newline ] !=
  346.                         oldinfo.symbol[ oldline ] ) break;  /* not same */
  347.  
  348.                     newinfo.other[ newline ] = oldline;   /* record a match */
  349.                     oldinfo.other[ oldline ] = newline;
  350.                }
  351.           }
  352.      }
  353. }
  354. /***************************************************************************
  355. *
  356. * scanbefore   As scanafter, except scans towards file fronts.
  357. * ----------   Assumes the off-end lines have been marked as a match.
  358. *
  359. ***************************************************************************/
  360. void scanbefore()
  361. {
  362.      int oldline, newline;
  363.  
  364.      for( newline = newinfo.maxline + 1; newline > 0; newline-- ) {
  365.           oldline = newinfo.other[ newline ];
  366.           if( oldline >= 0 ) {               /* unique in each */
  367.                for(;;) {
  368.                     if( --oldline <= 0                ) break;
  369.                     if( oldinfo.other[ oldline ] >= 0 ) break;
  370.                     if( --newline <= 0                ) break;
  371.                     if( newinfo.other[ newline ] >= 0 ) break;
  372.      
  373.                     /* oldline and newline exist, and aren't marked yet */
  374.  
  375.                     if( newinfo.symbol[ newline ] !=
  376.                         oldinfo.symbol[ oldline ] ) break;  /* not same */
  377.  
  378.                     newinfo.other[ newline ] = oldline;   /* record a match */
  379.                     oldinfo.other[ oldline ] = newline;
  380.                }
  381.           }
  382.      }
  383. }
  384. /***************************************************************************
  385. *
  386. * scanblocks   Expects oldinfo valid.
  387. * ----------   Finds the beginnings and lengths of blocks of matches.
  388. *              Sets the blocklen array (see definition).
  389. *
  390. ***************************************************************************/
  391. void scanblocks()
  392. {
  393.      int oldline, newline;
  394.      int oldfront = 0;      /* line# of front of a block in old file, or 0  */
  395.      int newlast = -1;      /* newline's value during the previous iteration*/
  396.  
  397.      for( oldline = 1; oldline <= oldinfo.maxline; oldline++ )
  398.                blocklen[ oldline ] = 0;
  399.      blocklen[ oldinfo.maxline + 1 ] = UNREAL;    /* starts  a mythical blk */
  400.  
  401.      for( oldline = 1; oldline <= oldinfo.maxline; oldline++ ) {
  402.           newline = oldinfo.other[ oldline ];
  403.           if( newline < 0 ) oldfront = 0;         /* no match: not in block */
  404.           else{                                   /* match. */
  405.                if( oldfront == 0 )         oldfront = oldline;
  406.                if( newline != (newlast+1)) oldfront = oldline;
  407.                ++blocklen[ oldfront ];            
  408.           }
  409.           newlast = newline;
  410.      }
  411. }
  412. /***************************************************************************
  413. *
  414. * printout     Expects all data structures have been filled out.
  415. * --------     Prints summary to stdout.
  416. *
  417. ***************************************************************************/
  418.           /* The following are global to printout's subsidiary routines */
  419.  
  420. enum{ idle, delete, insert, movenew, moveold, same, change } printstatus;
  421. enum{ false, true } anyprinted;
  422. int printoldline, printnewline;         /* line numbers in old & new file */
  423.  
  424. void printout()
  425. {
  426.      printstatus = idle;
  427.      anyprinted = false;
  428.      for( printoldline = printnewline = 1; ; ) {
  429.           if( printoldline > oldinfo.maxline ) { newconsume(); break;}
  430.           if( printnewline > newinfo.maxline ) { oldconsume(); break;}
  431.           if(      newinfo.other[ printnewline ] < 0 ) {
  432.                if( oldinfo.other[ printoldline ] < 0 )           showchange();
  433.                else                                              showinsert();
  434.           }
  435.           else if( oldinfo.other[ printoldline ] < 0 )           showdelete();
  436.           else if( blocklen[ printoldline ] < 0 )                  skipold();
  437.           else if( oldinfo.other[ printoldline ] == printnewline ) showsame();
  438.           else                                                     showmove();
  439.      }
  440.      if( anyprinted == true ) printf( ">>>> End of differences.\n"  );
  441.      else                     printf( ">>>> Files are identical.\n" );
  442. }
  443. /***************************************************************************
  444. *
  445. * newconsume        Part of printout. Have run out of old file. 
  446. * ----------        Print the rest of the new file, as inserts and/or moves.
  447. *
  448. ***************************************************************************/
  449. void newconsume()
  450. {
  451.      for(;;) {
  452.           if( printnewline > newinfo.maxline ) break;        /* end of file */
  453.           if( newinfo.other[ printnewline ] < 0 ) showinsert();
  454.           else                                    showmove();
  455.      }
  456. }
  457. /***************************************************************************
  458. *
  459. * oldconsume        Part of printout. Have run out of new file.
  460. * ----------        Process the rest of the old file, printing any
  461. *                   parts which were deletes or moves.
  462. *
  463. ***************************************************************************/
  464. void oldconsume()
  465. {
  466.      for(;;) {
  467.           if( printoldline > oldinfo.maxline ) break;       /* end of file */
  468.           printnewline = oldinfo.other[ printoldline ];
  469.           if( printnewline < 0 ) showdelete();
  470.           else if( blocklen[ printoldline ] < 0 ) skipold();
  471.           else showmove();
  472.      }
  473. }
  474. /***************************************************************************
  475. *
  476. * showdelete        Part of printout.
  477. * ----------        Expects printoldline is at a deletion.
  478. *
  479. ***************************************************************************/
  480. void showdelete()
  481. {
  482.      if( printstatus != delete ) printf( ">>>> DELETE AT %d\n", printoldline);
  483.      printstatus = delete;
  484.      showsymbol( oldinfo.symbol[ printoldline ]);
  485.      anyprinted = true;
  486.      printoldline++;
  487. }
  488. /***************************************************************************
  489. *
  490. * showinsert        Part of printout.
  491. * ----------        Expects printnewline is at an insertion.
  492. *
  493. ***************************************************************************/
  494. void showinsert()
  495. {
  496.      if( printstatus == change ) printf( ">>>>     CHANGED TO\n" );
  497.      else if( printstatus != insert ) 
  498.           printf( ">>>> INSERT BEFORE %d\n", printoldline );
  499.      printstatus = insert;
  500.      showsymbol( newinfo.symbol[ printnewline ]);
  501.      anyprinted = true;
  502.      printnewline++;
  503. }
  504. /***************************************************************************
  505. *
  506. * showchange        Part of printout.
  507. * ----------        Expects printnewline is an insertion.
  508. *                   Expects printoldline is a deletion.
  509. *
  510. ***************************************************************************/
  511. void showchange()
  512. {
  513.      if( printstatus != change ) 
  514.           printf( ">>>> %d CHANGED FROM\n", printoldline );
  515.      printstatus = change;
  516.      showsymbol( oldinfo.symbol[ printoldline ]);
  517.      anyprinted = true;
  518.      printoldline++;
  519. }
  520. /***************************************************************************
  521. *
  522. * skipold           Part of printout.
  523. * -------           Expects printoldline at start of an old block that has 
  524. *                   already been announced as a move.
  525. *                   Skips over the old block.
  526. *
  527. ***************************************************************************/
  528. void skipold()
  529. {
  530.      printstatus = idle;
  531.      for(;;) {
  532.           if( ++printoldline > oldinfo.maxline ) break;     /* end of file  */
  533.           if( oldinfo.other[ printoldline ] < 0 ) break;    /* end of block */
  534.           if( blocklen[ printoldline ]) break;          /* start of another */
  535.      }
  536. }
  537. /***************************************************************************
  538. *
  539. * skipnew           Part of printout.
  540. * -------           Expects printnewline is at start of a new block that has
  541. *                   already been announced as a move.
  542. *                   Skips over the new block.
  543. *
  544. ***************************************************************************/
  545. void skipnew()
  546. {
  547.      int oldline;
  548.      printstatus = idle;
  549.      for(;;) {
  550.           if( ++printnewline > newinfo.maxline ) break;    /* end of file  */
  551.           oldline = newinfo.other[ printnewline ];
  552.           if( oldline < 0 ) break;                         /* end of block */
  553.           if( blocklen[ oldline ]) break;              /* start of another */
  554.  
  555.      }
  556. }
  557. /***************************************************************************
  558. *
  559. * showsame          Part of printout.
  560. * --------          Expects printnewline and printoldline at start of
  561. *                   two blocks that aren't to be displayed.
  562. *
  563. ***************************************************************************/
  564. void showsame()
  565. {
  566.      int count;
  567.      printstatus = idle;
  568.      if( newinfo.other[ printnewline ] != printoldline ) {
  569.           fprintf( stderr, "BUG IN LINE REFERENCING\n\007" );     /* (bel) */
  570.           exit(1);
  571.      }
  572.      count = blocklen[ printoldline ];
  573.      printoldline += count;
  574.      printnewline += count;
  575. }
  576. /***************************************************************************
  577. *
  578. * showmove          Part of printout.
  579. * --------          Expects printoldline, printnewline at start of
  580. *                   two different blocks ( a move was done).
  581. *
  582. ***************************************************************************/
  583. void showmove()
  584. {
  585.      int oldblock = blocklen[ printoldline ];
  586.      int newother = newinfo.other[ printnewline ];
  587.      int newblock = blocklen[ newother ];
  588.  
  589.      if( newblock < 0 ) skipnew();           /* already printed */
  590.      else if( oldblock >= newblock ) {       /* assume new's blk moved */
  591.           blocklen[ newother ] = -1;         /* stamp block as "printed" */
  592.           printf( ">>>> %d MOVED TO BEFORE %d\n", newother, printoldline );
  593.           for( ; newblock > 0; newblock--, printnewline++ )
  594.                showsymbol( newinfo.symbol[ printnewline ]);
  595.           anyprinted = true;
  596.           printstatus = idle;
  597.  
  598.      }else                         /* assume old's block moved */
  599.           skipold();               /* target line# not known, display later */
  600.  
  601. }
  602. /***************************************************************************
  603. *
  604. * The symbol table routines follow. They are a "package" and all
  605. * understand the symbol table format, which is a binary tree.
  606. * The "entry points" are: initsymtab, addsymbol, symbolisunique,
  607. * lineofsymbol, and showsymbol.
  608. *
  609. ***************************************************************************/
  610.  
  611. enum linestates{ freshnode, oldonce, newonce, bothonce, other };
  612.  
  613. struct node{                       /* the tree is made up of these nodes */
  614.      struct node *pleft, *pright;
  615.      int linenum;
  616.      enum linestates linestate;
  617.      /* The text of the line is stored after this, as a varying-length
  618.      *  nul-terminated string.
  619.      */
  620. };
  621. struct node *panchor;    /* symtab is a tree hung from this */
  622.  
  623. /* The following macro computes the address of the string part of a node. */
  624. #define PTEXT( PNODE )   (sizeof( struct node) + (char *)PNODE)
  625. /***************************************************************************
  626. *
  627. * initsymtab        Must be called, once, before any calls to addsymbol.
  628. * ----------
  629. *
  630. ***************************************************************************/
  631. void initsymtab()
  632. {
  633.      panchor = NULL;
  634. }
  635. /***************************************************************************
  636. *
  637. * newnode        Allocates a new symbol table node and fills in its fields.
  638. * -------        Expects pline -> a nul-terminated string of linelen 
  639. *                non-nul characters. Copies this string into the new node.
  640. *                Sets linestate = freshnode. Does not set linenum.
  641. *                Returns a pointer to the new node.
  642. *
  643. ***************************************************************************/
  644. struct node *newnode( pline, linelen )
  645. char *pline;
  646. int linelen;
  647. {
  648.      struct node *new = 
  649.           (struct node *) malloc( 1 + linelen + sizeof( struct node ));
  650.      if( new == NULL ) { 
  651.           fprintf( stderr, "Out of memory, sorry.\n\007");       /* (bel) */
  652.           exit(1);
  653.      }
  654.      new-> pleft = new-> pright = NULL;
  655.      new-> linestate = freshnode;
  656.      /* linenum field is not always valid */     
  657.      strcpy( PTEXT( new ), pline );
  658.      return new;
  659. }
  660. /***************************************************************************
  661. *
  662. * matchsymbol       Searches tree for a match to the line.
  663. * ----------        Expects pline-> a nul-terminated string of linelen
  664. *                   non-null chars.
  665. *                   Returns a ptr to a matching node.
  666. *                   If node's linestate == freshnode, then created the node.
  667. *
  668. ***************************************************************************/
  669. struct node *matchsymbol( pline, linelen )
  670. char *pline;
  671. int linelen;
  672. {
  673.      int comparison;
  674.      struct node *pnode = panchor;
  675.      if( panchor == NULL ) return panchor = newnode( pline, linelen );
  676.      for(;;) {
  677.           comparison = strcmp( PTEXT(pnode), pline );
  678.           if( comparison == 0 ) return pnode;          /* found */
  679.  
  680.           if( comparison < 0 ) {
  681.                if( pnode-> pleft == NULL ) {
  682.                     pnode->pleft = newnode( pline, linelen );
  683.                     return pnode-> pleft;
  684.                }
  685.                pnode = pnode-> pleft;
  686.           }
  687.           if( comparison > 0 ) {
  688.                if( pnode-> pright == NULL ) {
  689.                     pnode->pright = newnode( pline, linelen );
  690.                     return pnode-> pright;
  691.                }
  692.                pnode = pnode-> pright;
  693.           }
  694.      }
  695.      /* NOTE: There are return stmts, so control does not get here. */
  696. }
  697. /***************************************************************************
  698. *
  699. * addsymbol    Expects pline-> a string with linelen non-nul chars.
  700. * ---------    Saves that line into the symbol table.
  701. *              Returns a handle to the symtab entry for that unique line.
  702. *              If inoldfile nonzero, then linenum is remembered.
  703. *              Expects initsymbtab has been called, once.
  704. *
  705. ****************************************************************************/
  706. char *addsymbol( pline, linelen, inoldfile, linenum )
  707. char *pline;
  708. int linelen, inoldfile, linenum;
  709. {
  710.      struct node *pnode;
  711.      pnode = matchsymbol( pline, linelen );  /* find the node in the tree */
  712.      if( pnode-> linestate == freshnode ) {
  713.           pnode-> linestate = inoldfile ? oldonce : newonce;
  714.      }else{
  715.           if(( pnode-> linestate == oldonce && !inoldfile ) ||
  716.              ( pnode-> linestate == newonce &&  inoldfile )) 
  717.                pnode-> linestate = bothonce;
  718.           else pnode-> linestate = other;
  719.      }
  720.      if( inoldfile ) pnode-> linenum = linenum;
  721.      return (char *)pnode;
  722. }
  723. /***************************************************************************
  724. *
  725. * symbolisunique    Arg is a ptr previously returned by addsymbol.
  726. * --------------    Returns true if the line was added to the
  727. *                   symbol table exactly once with inoldfile true,
  728. *                   and exactly once with inoldfile false.
  729. *
  730. ***************************************************************************/
  731. int symbolisunique( psymbol )
  732. struct node *psymbol;
  733. {
  734.      return (psymbol-> linestate == bothonce );
  735. }
  736. /***************************************************************************
  737. *
  738. * lineofsymbol      Arg is a ptr previously returned by addsymbol.
  739. * ------------      Returns the line number stored with the line.
  740. *
  741. ***************************************************************************/
  742. int lineofsymbol( psymbol )
  743. struct node *psymbol;
  744. {
  745.      return psymbol-> linenum;
  746. }
  747. /***************************************************************************
  748. *
  749. * showsymbol        Arg is a ptr previously returned by addsymbol.
  750. * ----------        Prints the line to stdout.
  751. *
  752. ***************************************************************************/
  753. void showsymbol( psymbol )
  754. struct node *psymbol;
  755. {
  756.      printf( "%s\n", PTEXT( psymbol ) );
  757. }
  758. /***************************************************************************/
  759. EOF
  760. if test `wc -c < diff.c` -ne 30350
  761. then    echo 'diff.c is the wrong size'
  762. fi
  763. echo Unpacking done.
  764. exit
  765.  
  766.