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