home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / sdktools / windiff / compitem.c < prev    next >
C/C++ Source or Header  |  1997-10-05  |  30KB  |  912 lines
  1.  
  2. /******************************************************************************\
  3. *       This is a part of the Microsoft Source Code Samples. 
  4. *       Copyright (C) 1993-1997 Microsoft Corporation.
  5. *       All rights reserved. 
  6. *       This source code is only intended as a supplement to 
  7. *       Microsoft Development Tools and/or WinHelp documentation.
  8. *       See these sources for detailed information regarding the 
  9. *       Microsoft samples programs.
  10. \******************************************************************************/
  11.  
  12. /****************************** Module Header *******************************
  13. * Module Name: COMPITEM.C
  14. *
  15. * Module which does the comparison between two files. 
  16. *
  17. * Functions:
  18. *
  19. * ci_copytext()
  20. * ci_makecomposite()
  21. * ci_compare()
  22. * ci_onesection()
  23. * compitem_new()
  24. * compitem_delete()
  25. * compitem_discardsections()
  26. * compitem_getcomposite()
  27. * compitem_getleftsections()
  28. * compitem_getrightsections()
  29. * compitem_getleftfile()
  30. * compitem_getrightfile()
  31. * compitem_getstate()
  32. * compitem_gettext_tag()
  33. * compitem_gettext_result()
  34. * compitem_getfilename()
  35. * compitem_frefilename()
  36. *
  37. * Comments:
  38. *
  39. * This module uses the structure compitem which is a data type that knows
  40. * about two files, and can compare them. The result of the comparison
  41. * is a list of sections for each file, and a composite list of sections
  42. * representing the comparison of the two files.
  43. *
  44. * A compitem has a state (one of the integer values defined in state.h)
  45. * representing the result of the comparison. It can also be
  46. * queried for the text result (text equivalent of the state) as well
  47. * as the tag - or title for this compitem (usually a text string containing
  48. * the name(s) of the files being compared).
  49. *
  50. * A compitem will supply a composite section list even if the files are
  51. * the same, or if there is only one file. The composite section list will
  52. * only be built (and the files read in) when the compitem_getcomposite()
  53. * call is made (and not at compitem_new time).
  54. * 
  55. *  
  56. ****************************************************************************/
  57.  
  58. #include <windows.h>
  59. #include <stdlib.h>
  60. #include <string.h>
  61.  
  62. #include "gutils.h"
  63. #include "state.h"
  64. #include "windiff.h"
  65. #include "wdiffrc.h"
  66. #include "list.h"
  67. #include "line.h"
  68. #include "scandir.h"
  69. #include "file.h"
  70. #include "section.h"
  71. #include "compitem.h"
  72.  
  73.  
  74. struct compitem {
  75.  
  76.         FILEDATA left;          /* handle for left-hand file */
  77.         FILEDATA right;         /* handle for right-hand file */
  78.  
  79.         LIST secs_composite;    /* list of sections (composite file)*/
  80.         LIST secs_left;         /* list of sections (left file) */
  81.         LIST secs_right;        /* list of sections (right file) */
  82.  
  83.         int state;              /* compitem state - result of compare */
  84.         BOOL bDiscard;          /* true if not alloc-ed on list */
  85.         LPSTR tag;              /* text for tag (title of compitem) */
  86.         LPSTR result;           /* text equivalent of state */
  87.  
  88. };
  89.  
  90.  
  91. LPSTR ci_copytext(LPSTR in);
  92. void ci_makecomposite(COMPITEM ci);
  93. void ci_compare(COMPITEM ci);
  94.  
  95.  
  96. /***************************************************************************
  97.  * Function: compitem_new
  98.  *
  99.  * Purpose:
  100.  *
  101.  * Returns a handle to a new compitem - given the filenames for the
  102.  * left and right files to be compared. Either left or right or neither
  103.  * (but not both) may be null. In this case we set the state accordingly.
  104.  *
  105.  * The parameters are handles to DIRITEM objects: these allow us to get the
  106.  * the name of the file relative to the compare roots (needed for the tag)
  107.  * and the absolute name of the file (needed for opening the file).
  108.  *
  109.  * Comments:
  110.  *
  111.  * If the list parameter is not null, the List_New* functions are used to
  112.  * allocate memory for the compitem. We remember this (in the bDiscard flag)
  113.  * so we do not delete the compitem if it was allocated on the list.
  114.  *
  115.  * If the list parameter is null, the memory
  116.  * for the compitem is allocated from the gmem_* heap initialised by the app.
  117.  *
  118.  ****************************************************************************/
  119. COMPITEM
  120. compitem_new(DIRITEM leftname, DIRITEM rightname, LIST list, BOOL fExact)
  121. {
  122.         COMPITEM ci;
  123.         LPSTR str1, str2;
  124.         char buf[2*MAX_PATH+20];
  125.  
  126.  
  127.         /*
  128.          * Allocate the memory for the compitem, either at the end of the
  129.          * list or in the gmem_* heap.
  130.          */
  131.         if (list == NULL) {
  132.                 /* no list passed */
  133.                 ci = (COMPITEM) gmem_get(hHeap, sizeof(struct compitem));
  134.                 memset(ci, 0, sizeof(struct compitem));
  135.                 ci->bDiscard = TRUE;
  136.         } else {
  137.                 /* add to end of list */
  138.                 ci = (COMPITEM) List_NewLast(list, sizeof(struct compitem));
  139.                 ci->bDiscard = FALSE;
  140.         }
  141.  
  142.         ci->secs_composite = NULL;
  143.         ci->secs_left = NULL;
  144.         ci->secs_right = NULL;
  145.  
  146.         /*
  147.          * Make a filedata for each of the files that are non-null.
  148.          * Filedata objects are responsible for reading the file and
  149.          * accessing the lines in it. Don't read in the files until we need to.
  150.          */
  151.         if (leftname != NULL) {
  152.                 ci->left = file_new(leftname, FALSE);
  153.                 if (ci->left == NULL) {
  154.                         return(NULL);
  155.                 }
  156.         } else {
  157.                 ci->left = NULL;
  158.         }
  159.         if ( rightname != NULL) {
  160.                 ci->right = file_new(rightname, FALSE);
  161.                 if (ci->right == NULL) {
  162.                         return(NULL);
  163.                 }
  164.         } else {
  165.                 ci->right = NULL;
  166.         }
  167.  
  168.  
  169.         /*
  170.          * See if we have one or two files, and set the state accordingly
  171.          */
  172.         if ( ! ci->left && !ci->right) {
  173.                 /* two NULL files - this is wrong */
  174.                 return(NULL);
  175.         }
  176.  
  177.  
  178.         /* Set the tag (title field) for this item. If the
  179.          * two files have names that match, we use just that name -
  180.          * otherwise we use both names separated by a colon 'left : right'.
  181.          *
  182.          * In both cases, use the names relative to compare root (the
  183.          * names will certainly be different if we compare the abs paths)
  184.          */
  185.         str1 = dir_getrelname(leftname);
  186.         str2 = dir_getrelname(rightname);
  187.  
  188.         /* If only one file - set name to that */
  189.         if (ci->left == NULL) {
  190.                 ci->tag = ci_copytext(str2);
  191.         } else if (ci->right == NULL) {
  192.                 ci->tag = ci_copytext(str1);
  193.         } else {
  194.                 if (lstrcmpi(str1, str2) == 0) {
  195.                         ci->tag = ci_copytext(str2);
  196.                 } else {
  197.                         wsprintf(buf, "%s : %s", str1, str2);
  198.                         ci->tag = ci_copytext(buf);
  199.                 }
  200.         }
  201.  
  202.         dir_freerelname(leftname, str1);
  203.         dir_freerelname(leftname, str2);
  204.  
  205.  
  206.         if (ci->left == NULL) {
  207.                 str1 = dir_getroot_item(rightname);
  208.                 wsprintf(buf, LoadRcString(IDS_ONLY_IN), str1);
  209.                 dir_freeroot_item(rightname, str1);
  210.  
  211.                 ci->result = ci_copytext(buf);
  212.                 ci->state = STATE_FILERIGHTONLY;
  213.         } else if (ci->right == NULL) {
  214.                 str1 = dir_getroot_item(leftname);
  215.                 wsprintf(buf, LoadRcString(IDS_ONLY_IN), str1);
  216.                 dir_freeroot_item(leftname, str1);
  217.  
  218.                 ci->result = ci_copytext(buf);
  219.                 ci->state = STATE_FILELEFTONLY;
  220.         } else {
  221.                 /* two files - are they the same ? compare
  222.                  * the file sizes
  223.                  */
  224.  
  225.  
  226.                 if (dir_getfilesize(leftname) != dir_getfilesize(rightname)) 
  227.                 {
  228.                     ci->state = STATE_DIFFER;
  229.                     ci->result = ci_copytext(LoadRcString(IDS_DIFFERENT_SIZES));
  230.                 } else if (!fExact){
  231.                     ci->result = ci_copytext(LoadRcString(IDS_SAME_SIZE));
  232.                     ci->state = STATE_SAME;
  233.                 } else {
  234.                     ci->result =  ci_copytext(LoadRcString(IDS_IDENTICAL));
  235.                     ci->state = STATE_SAME;
  236.                 }
  237.         }
  238.  
  239.  
  240. #if FALSE
  241.                 if (dir_getfilesize(leftname) == dir_getfilesize(rightname)) {
  242.                     if (  !fExact )
  243.                        {
  244.                         ci->result = ci_copytext("same size etc.");
  245.                         ci->state = STATE_SAME;
  246.                     } else {
  247.                         ci->result = ci_copytext("files differ");
  248.                         ci->state = STATE_DIFFER;
  249.                         ci->result = ci_copytext("files differ");
  250.                      }
  251.                 } else {
  252.                         ci->result = ci_copytext("files differ");
  253.                         ci->state = STATE_DIFFER;
  254.                 }
  255.         }
  256. #endif
  257.  
  258.         /*
  259.          * Building the section lists and composite lists can wait
  260.          * until needed.
  261.          */
  262.         return(ci);
  263. } /* compitem_new */
  264.  
  265. /***************************************************************************
  266.  * Function: compitem_delete
  267.  *
  268.  * Purpose:
  269.  *
  270.  * Deletes a compitem and free all associated data.
  271.  *
  272.  * Comments:
  273.  *
  274.  * If the ci->bDiscard flag is set, the compitem was alloc-ed on a list,
  275.  * and should not be discarded (the list itself will be deleted).
  276.  *
  277.  * The DIRDATA we were passed are not deleted. the filedata, lines
  278.  * and sections are.
  279.  ***************************************************************************/
  280. void
  281. compitem_delete(COMPITEM ci)
  282. {
  283.         if (ci == NULL) {
  284.                 return;
  285.         }
  286.  
  287.         compitem_discardsections(ci);
  288.  
  289.         /* Delete the two filedatas (and associated line lists) */
  290.         file_delete(ci->left);
  291.         file_delete(ci->right);
  292.  
  293.         /* text we allocated */
  294.         gmem_free(hHeap, ci->tag, lstrlen(ci->tag) + 1);
  295.         gmem_free(hHeap, ci->result, lstrlen(ci->result) + 1);
  296.  
  297.         /* Free the compitem struct itself if not alloced on a list */
  298.         if (ci->bDiscard) {
  299.                 gmem_free(hHeap, (LPSTR) ci, sizeof(struct compitem));
  300.         }
  301. }
  302.  
  303.  
  304. /*
  305. /***************************************************************************
  306.  * Function: compitem_discardsections
  307.  *
  308.  * Purpose:
  309.  *
  310.  * To discard sections - throw away cached information relating to the
  311.  * comparison (but not the files if they are read into memory). This
  312.  * is used to force a re-compare if changes in the comparison options
  313.  * are made
  314.  *
  315.  ***************************************************************************/
  316. void
  317. compitem_discardsections(COMPITEM ci)
  318. {
  319.         /* delete the lists of sections we built */
  320.         if (ci == NULL) {
  321.                 return;
  322.         }
  323.         if (ci->secs_composite) {
  324.                 section_deletelist(ci->secs_composite);
  325.                 ci->secs_composite = NULL;
  326.         }
  327.         if (ci->secs_left) {
  328.                 section_deletelist(ci->secs_left);
  329.                 ci->secs_left = NULL;
  330.         }
  331.         if (ci->secs_right) {
  332.                 section_deletelist(ci->secs_right);
  333.                 ci->secs_right = NULL;
  334.         }
  335.  
  336.         /* reset the line lists to throw away cached hash codes and links */
  337.         if (ci->left != NULL) {
  338.                 file_reset(ci->left);
  339.         }
  340.         if (ci->right != NULL) {
  341.                 file_reset(ci->right);
  342.         }
  343.  
  344. }
  345.  
  346. /***************************************************************************
  347.  * Function: compitem_getcomposite
  348.  *
  349.  * Purpose:
  350.  *
  351.  * To get the handle for the composite section list 
  352.  *
  353.  ***************************************************************************/
  354. LIST
  355. compitem_getcomposite(COMPITEM ci)
  356. {
  357.         if (ci == NULL) {
  358.                 return NULL;
  359.         }
  360.         /*
  361.          * do the comparison if we haven't already done it
  362.          */
  363.         if (ci->secs_composite == NULL) {
  364.                 ci_makecomposite(ci);
  365.         }
  366.  
  367.         return(ci->secs_composite);
  368. }
  369.  
  370. /***************************************************************************
  371.  * Function: compitem_getleftsections
  372.  *
  373.  * Purpose:
  374.  *
  375.  * To get the handle for the list of sections in the left file 
  376.  *
  377.  ***************************************************************************/
  378. LIST
  379. compitem_getleftsections(COMPITEM ci)
  380. {
  381.         if (ci == NULL) {
  382.                 return NULL;
  383.         }
  384.         /*
  385.          * do the comparison if we haven't already done it
  386.          */
  387.         if (ci->secs_composite == NULL) {
  388.                 ci_makecomposite(ci);
  389.         }
  390.  
  391.         return(ci->secs_left);
  392. }
  393.  
  394. /***************************************************************************
  395.  * Function: compitem_getrightsections
  396.  *
  397.  * Purpose:
  398.  *
  399.  * To get the handle for the list of sections in the right file 
  400.  *
  401.  ***************************************************************************/
  402. LIST
  403. compitem_getrightsections(COMPITEM ci)
  404. {
  405.         if (ci == NULL) {
  406.                 return NULL;
  407.         }
  408.         /*
  409.          * do the comparison if we haven't already done it
  410.          */
  411.         if (ci->secs_composite == NULL) {
  412.                 ci_makecomposite(ci);
  413.         }
  414.  
  415.         return(ci->secs_right);
  416. }
  417.  
  418. /***************************************************************************
  419.  * Function: compitem_getleftfile
  420.  *
  421.  * Purpose:
  422.  *
  423.  * To get the handle to the left file itself
  424.  *
  425.  ***************************************************************************/
  426. FILEDATA
  427. compitem_getleftfile(COMPITEM ci)
  428. {
  429.         if (ci == NULL) {
  430.                 return(NULL);
  431.         }
  432.         return(ci->left);
  433. }
  434.  
  435. /***************************************************************************
  436.  * Function: compitem_getrightfile
  437.  *
  438.  * Purpose:
  439.  *
  440.  * To get the handle to the right file itself 
  441.  *
  442.  ***************************************************************************/
  443. FILEDATA
  444. compitem_getrightfile(COMPITEM ci)
  445. {
  446.         if (ci == NULL) {
  447.                 return(NULL);
  448.         }
  449.         return(ci->right);
  450. }
  451.  
  452. /***************************************************************************
  453.  * Function: compitem_getstate
  454.  *
  455.  * Purpose:
  456.  *
  457.  * To get the state (compare result) of this compitem 
  458.  *
  459.  ***************************************************************************/
  460. int
  461. compitem_getstate(COMPITEM ci)
  462. {
  463.         if (ci == NULL) {
  464.                 return(0);
  465.         }
  466.         return(ci->state);
  467. }
  468.  
  469. /***************************************************************************
  470.  * Function: compitem_gettext_tag
  471.  *
  472.  * Purpose:
  473.  *
  474.  * To get the tag (text for the compitem title) 
  475.  *
  476.  ***************************************************************************/
  477. LPSTR
  478. compitem_gettext_tag(COMPITEM ci)
  479. {
  480.         if (ci == NULL) {
  481.                 return(NULL);
  482.         }
  483.         return(ci->tag);
  484. }
  485.  
  486. /***************************************************************************
  487.  * Function: compitem_gettext_result
  488.  *
  489.  * Purpose:
  490.  *
  491.  * To get the result text (text equiv of state) 
  492.  *
  493.  ***************************************************************************/
  494. LPSTR
  495. compitem_gettext_result(COMPITEM ci)
  496. {
  497.         if (ci == NULL) {
  498.                 return(NULL);
  499.         }
  500.         return(ci->result);
  501. }
  502.  
  503. /***************************************************************************
  504.  * Function: compitem_getfilename
  505.  *
  506.  * Purpose:
  507.  *
  508.  * To return the name of the file associated with this compitem. The option
  509.  * argument (one of CI_LEFT, CI_RIGHT, CI_COMP) indicates which file
  510.  * is required.
  511.  *
  512.  * Comments:
  513.  *
  514.  * CI_LEFT and CI_RIGHT just result in calls to dir_getopenname to get
  515.  * an open-able filename.
  516.  *
  517.  * For CI_COMP, we create a temporary file, write out all the text in the
  518.  * composite section list to this file, and then pass the name of the
  519.  * temporary file to the caller. This file will be deleted on
  520.  * the call to compitem_freefilename().
  521.  * 
  522.  ***************************************************************************/
  523. LPSTR
  524. compitem_getfilename(COMPITEM item, int option)
  525. {
  526.         LPSTR fname;
  527.         LINE line;
  528.         LPSTR tag, text;
  529.         SECTION sec;
  530.         OFSTRUCT os;
  531.         int fh;
  532.  
  533.         if (item == NULL) {
  534.                 return(NULL);
  535.         }
  536.  
  537.         switch(option) {
  538.         case CI_LEFT:
  539.                 if (item->left != NULL) {
  540.                         return(dir_getopenname(file_getdiritem(item->left)));
  541.                 } else {
  542.                         return(NULL);
  543.                 }
  544.  
  545.         case CI_RIGHT:
  546.                 if (item->right != NULL) {
  547.                         return(dir_getopenname(file_getdiritem(item->right)));
  548.                 } else {
  549.                         return(NULL);
  550.                 }
  551.  
  552.         case CI_COMP:
  553.  
  554.                 /* caller has asked for the filename of the composite file.
  555.                  * we need to create a temporary file and write the
  556.                  * lines in the composite section list out to it.
  557.                  */
  558.                 fname = gmem_get(hHeap, MAX_PATH);
  559.                 GetTempPath(MAX_PATH, fname);
  560.                 GetTempFileName(fname, "wdf", 0, fname);
  561.  
  562.                 fh = OpenFile(fname, &os, OF_READWRITE|OF_SHARE_DENY_NONE);
  563.                 if (fh < 0) {
  564.                         MessageBox(NULL, LoadRcString(IDS_CANT_OPEN_TMP_FILE), NULL, MB_OK | MB_ICONSTOP);
  565.                         return(NULL);
  566.                 }
  567.  
  568.                 /* make sure the composite list has been built */
  569.  
  570.                 if (item->secs_composite == NULL) {
  571.                         ci_makecomposite(item);
  572.                 }
  573.  
  574.                 /* write out every line in every section on the composite
  575.                  * list to the temp file.
  576.                  */
  577.                 List_TRAVERSE(item->secs_composite, sec) {
  578.  
  579.                         /* get the tag field based on the section state*/
  580.                         switch(section_getstate(sec)) {
  581.                         case STATE_SAME:
  582.                                 tag = "    ";
  583.                                 break;
  584.  
  585.                         case STATE_LEFTONLY:
  586.                                 tag = " <! ";
  587.                                 break;
  588.                         case STATE_RIGHTONLY:
  589.                                 tag = " !> ";
  590.                                 break;
  591.  
  592.                         case STATE_MOVEDLEFT:
  593.                                 tag = " <- ";
  594.                                 break;
  595.  
  596.                         case STATE_MOVEDRIGHT:
  597.                                 tag = " -> ";
  598.                                 break;
  599.                         }
  600.  
  601.                         /* write out each line in this section.
  602.                          * non-standard traverse of list as we only
  603.                          * want to go from section first to section last
  604.                          * inclusive.
  605.                          */
  606.                         for (line = section_getfirstline(sec);
  607.                              line != NULL;
  608.                              line = List_Next(line) ) {
  609.  
  610.                                 text = line_gettext(line);
  611.  
  612.                                 /* write out to file */
  613.                                 _lwrite(fh, tag, lstrlen(tag));
  614.                                 _lwrite(fh, text, lstrlen(text));
  615.  
  616.                                 if (line == section_getlastline(sec)) {
  617.                                         break;
  618.                                 }
  619.                         }
  620.                 }
  621.  
  622.                 /* now close the file and return its name */
  623.                 _lclose(fh);
  624.                 return(fname);
  625.  
  626.  
  627.         default:
  628.                 MessageBox(NULL, LoadRcString(IDS_BAD_ARGUMENT), NULL, MB_OK | MB_ICONSTOP);
  629.                 return(NULL);
  630.         }
  631. }
  632.  
  633. /***************************************************************************
  634.  * Function: compitem_freefilename
  635.  *
  636.  * Purpose:
  637.  *
  638.  * Free memory created by a call to compitem_getfilename. If a temporary
  639.  * file was created, this may cause it to be deleted. The option argument must
  640.  * be the same as passed to the original compitem_getfilename call.
  641.  *
  642.  * If we created a temporary file for CI_COMP, then delete it; otherwise,
  643.  * just pass the name to dir_freeopenname.
  644.  *
  645.  ***************************************************************************/
  646. void
  647. compitem_freefilename(COMPITEM item, int option, LPSTR filename)
  648. {
  649.         OFSTRUCT os;
  650.  
  651.  
  652.         if ((item == NULL) || (filename == NULL)) {
  653.                 return;
  654.         }
  655.  
  656.         switch(option) {
  657.  
  658.         case CI_LEFT:
  659.                 dir_freeopenname(file_getdiritem(item->left), filename);
  660.                 break;
  661.  
  662.         case CI_RIGHT:
  663.                 dir_freeopenname(file_getdiritem(item->right), filename);
  664.                 break;
  665.  
  666.         case CI_COMP:
  667.  
  668.                 /* this is a temporary file we created. Delete it. */
  669.                 OpenFile(filename, &os, OF_DELETE);
  670.  
  671.                 gmem_free(hHeap, filename, MAX_PATH);
  672.                 break;
  673.         }
  674. }
  675.  
  676.  
  677. /***************************************************************************
  678.  * Function: ci_copytext
  679.  *
  680.  * Purpose:
  681.  *
  682.  * To alloc a buffer large enough for the text string and copy the text into
  683.  * it and return a pointer to the string.
  684.  *
  685.  ***************************************************************************/
  686. LPSTR
  687. ci_copytext(LPSTR in)
  688. {
  689.         LPSTR out;
  690.  
  691.         if (in == NULL) {
  692.                 out = gmem_get(hHeap, 1);
  693.                 out[0] = '\0';
  694.         } else {
  695.                 out = gmem_get(hHeap, lstrlen(in) + 1);
  696.                 lstrcpy(out, in);
  697.         }
  698.         return(out);
  699. }
  700.  
  701. /***************************************************************************
  702.  * Function: ci_onesection
  703.  *
  704.  * Purpose:
  705.  *
  706.  * To make a list containing a single section from the whole list of lines 
  707.  *
  708.  ***************************************************************************/
  709. LIST
  710. ci_onesection(FILEDATA file)
  711. {
  712.         LIST lines;
  713.         LIST sections;
  714.         SECTION section;
  715.  
  716.         lines = file_getlinelist(file);
  717.  
  718.         /* create a null list */
  719.         sections = List_Create();
  720.  
  721.         /* tell the section to create itself on the end of this list. */
  722.         section = section_new(List_First(lines), List_Last(lines), sections);
  723.         section_setstate(section, STATE_SAME);
  724.  
  725.  
  726.         return(sections);
  727. }
  728.  
  729.  
  730.  
  731. /***************************************************************************
  732.  * Function: ci_makecomposite
  733.  *
  734.  * Purpose:
  735.  *
  736.  * Compare the two files and build the composite list. This function is
  737.  * called whenever we need one of the section lists and only does the 
  738.  * comparison if the composite list does not already exist.
  739.  *
  740.  ***************************************************************************/
  741. void
  742. ci_makecomposite(COMPITEM ci)
  743. {
  744.         if (ci->secs_composite != NULL) {
  745.                 return;
  746.         }
  747.  
  748.         /* if there is only one file, make a single item list
  749.          * of sections
  750.          */
  751.         if (ci->left == NULL) {
  752.                 ci->secs_left = NULL;
  753.                 ci->secs_right = ci_onesection(ci->right);
  754.  
  755.                 /* make a second list, not a pointer to the first
  756.                  * or we will get confused when deleting
  757.                  */
  758.                 ci->secs_composite = ci_onesection(ci->right);
  759.                 return;
  760.         } else if (ci->right == NULL) {
  761.                 ci->secs_right = NULL;
  762.                 ci->secs_left = ci_onesection(ci->left);
  763.  
  764.                 /* make a second list, not a pointer to the first
  765.                  * or we will get confused when deleting
  766.                  */
  767.                 ci->secs_composite = ci_onesection(ci->left);
  768.                 return;
  769.         }
  770.  
  771.         /* we have two files - we need to compare them fully */
  772.         ci_compare(ci);
  773. }
  774.  
  775. /***************************************************************************
  776.  * Function: ci_compare
  777.  *
  778.  * Purpose:
  779.  *
  780.  * Compare files and build a composite list.
  781.  *
  782.  * Comments:
  783.  *
  784.  * Comparison method:
  785.  *
  786.  *    0   Break each file into lines and hash each line.  Lines which 
  787.  *        don't match can be rapidly eliminated by comparing the hash code.
  788.  *
  789.  *        Store the hash codes in a binary search tree that
  790.  *        will give for each hash code the number of times that it
  791.  *        occurred in each file and one of the lines where it occurred
  792.  *        in each file.  The tree is used to rapidly find the partner
  793.  *        of a line which occurs exactly once in each file.
  794.  *
  795.  *    1   Make a section covering the whole file (for both)
  796.  *        and link unique lines between these sections (i.e. link lines
  797.  *        which occur exactly once in each file as they must match each other).
  798.  *        These are referred to as anchor points.
  799.  *
  800.  *    2   Build section lists for both files by traversing line lists and
  801.  *        making a section for each set of adjacent lines that are unmatched
  802.  *        and for each set of adjacent lines that match a set of adjacent
  803.  *        lines in the other file.  In making a section we start from a
  804.  *        known matching line and work both forwards and backwards through
  805.  *        the file including lines which match, whether they are unique or not.
  806.  *
  807.  *    3   Establish links between sections that match
  808.  *        and also between sections that don't match but do
  809.  *        correspond (by position in file between matching sections)
  810.  *
  811.  *    4   For each section pair that don't match but do correspond,
  812.  *        link up matching lines unique within that section.  (i.e. do
  813.  *        the whole algorithm again on just this section).
  814.  *
  815.  *    There may be some lines which occur many times over in each file.
  816.  *    As these occurrences are matched up, so the number left to match
  817.  *    reduces, and may reach one in each file.  At this point these two
  818.  *    can be matched.  Therefore we...
  819.  *
  820.  *    Repeat steps 0-4 until no more new links are added, but (especially
  821.  *    in step 0) we only bother with lines which have not yet been matched.
  822.  *    This means that a line which has only one unmatched instance in each
  823.  *    file gets a count of one and so is a new anchor point.
  824.  *
  825.  *    Finally build a composite list from the two lists of sections.
  826.  *
  827.  ***************************************************************************/
  828. void
  829. ci_compare(COMPITEM ci)
  830. {
  831.         LIST lines_left, lines_right;
  832.         SECTION whole_left, whole_right;
  833.         BOOL bChanges;
  834.  
  835.         /* get the list of lines for each file */
  836.         lines_left = file_getlinelist(ci->left);
  837.         lines_right = file_getlinelist(ci->right);
  838.  
  839.         if ((lines_left == NULL) || (lines_right == NULL)) {
  840.                 ci->secs_left = NULL;
  841.                 ci->secs_right = NULL;
  842.                 ci->secs_composite = NULL;
  843.                 return;
  844.         }
  845.  
  846.         do {
  847.  
  848.                 /* we have made no changes so far this time round the
  849.                  * loop
  850.                  */
  851.                 bChanges = FALSE;
  852.  
  853.                 /* make a section covering the whole file */
  854.                 whole_left = section_new(List_First(lines_left),
  855.                                          List_Last(lines_left), NULL);
  856.  
  857.                 whole_right = section_new(List_First(lines_right),
  858.                                          List_Last(lines_right), NULL);
  859.  
  860.                 /* link up matching unique lines between these sections */
  861.                 if (section_match(whole_left, whole_right)) {
  862.                         bChanges = TRUE;
  863.                 }
  864.  
  865.                 /* delete the two temp sections */
  866.                 section_delete(whole_left);
  867.                 section_delete(whole_right);
  868.  
  869.                 /* discard previous section lists if made */
  870.                 if (ci->secs_left) {
  871.                         section_deletelist(ci->secs_left);
  872.                         ci->secs_left = NULL;
  873.                 }
  874.                 if (ci->secs_right) {
  875.                         section_deletelist(ci->secs_right);
  876.                         ci->secs_right = NULL;
  877.                 }
  878.                 /* build new section lists for both files */
  879.                 ci->secs_left = section_makelist(lines_left, TRUE);
  880.                 ci->secs_right = section_makelist(lines_right, FALSE);
  881.  
  882.                 /* match up sections - make links and corresponds between
  883.                  * sections. Attempts to section_match corresponding
  884.                  * sections that are not matched. returns true if any
  885.                  * further links were made
  886.                  */
  887.                 if (section_matchlists(ci->secs_left, ci->secs_right)) {
  888.                         bChanges = TRUE;
  889.                 }
  890.  
  891.         /* repeat as long as we keep adding new links */
  892.  
  893.         } while (bChanges);
  894.  
  895.         /* all possible lines linked, and section lists made .
  896.          * combine the two section lists to get a view of the
  897.          * whole comparison - the composite section list. This also
  898.          * sets the state of each section in the composite list.
  899.          */
  900.         ci->secs_composite = section_makecomposite(ci->secs_left, ci->secs_right);
  901.  
  902. }
  903.  
  904.  
  905.  
  906.  
  907.  
  908.  
  909.  
  910.  
  911.  
  912.