section.c

<Win2k系统编程>源码.次数为国人自编,内容丰富,还是不错的.

/****************************** Module Header *******************************
* Module Name: SECTION.C
*
* Manages sections of lines, and lists of sections.
*
* Functions:
*
* section_new()
* section_delete()
* section_match()
* section_getfirstline()
* section_getlastline()
* section_getlink()
* section_getcorrespond()
* section_getstate()
* section_setstate()
* section_getlinecount()
* section_getleftbasenr()
* section_setleftbasenr()
* section_getrightbasenr()
* section_setrightbasenr()
* FindEndOfUnmatched()
* NextNonIngnorable()
* FinEndOfMatched()
* section_makelist()
* section_deletelist()
* FindFirstWithLink()
* section_matchlists()
* section_takesection()
* section_makecomposite()
* AbsorbAnyBlanks()
* section_makectree()
* section_expandanchor()
*
* Comments:
*
* A section is a data type that represents a contiguous block of lines
* of the same state (all unmatched, or all matched to a contiguous block of
* lines). A section can link up matching lines within the section.
*
* Section list functions can make and match lists of sections from lists of
* lines, and create a composite list by combining sections from two lists
* to create a list that 'best represents' the similarities and differences
* between the two lists of lines.
* 
* Assumptions: the lines passed in are on a list (can be traversed with
* List_Next() etc. Line numbering using the section_get*basenr()
* functions work only if lines are numbered sequentially in ascending order.
*
****************************************************************************/

#include <windows.h>
#include <stdlib.h>
#include <string.h>

#include "gutils.h"
#include "tree.h"
#include "state.h"
#include "windiff.h"
#include "wdiffrc.h"
#include "list.h"
#include "line.h"
#include "section.h"

/*
 * a section handle (SECTION) is a pointer to one of these structures
 */
struct section {
        LINE first;             /* first line in section */
        LINE last;              /* last line in section */

        BOOL bDiscard;          /* true if not alloc-ed on list */

        SECTION link;           /* we match this section */
        SECTION correspond;     /* we correspond to this section, but
                                 * don't match it
                                 */

        int state;              /* compare state for section */

        int leftbase;           /* nr in original left list of first line*/
        int rightbase;          /* nr in original right list of first line*/
};

/* --- function prototypes ------------------------------------------*/

TREE section_makectree(SECTION sec);
BOOL section_expandanchor(SECTION sec1, LINE line1, SECTION sec2, LINE line2);



/***************************************************************************
 * Function: section_new
 *
 * Purpose:
 *
 * Makes a new section, given handles to a first and last line.
 *
 * A section must be at least one line long. The lines passed in must be
 * on a list in order.
 *
 * If the list parameter is non-null, we will allocate the section struct
 * on the list. otherwise we will alloc it from gmem_get(hHeap). We remember
 * this in the bDiscard flag for section_delete, so that we only
 * hand back to gmem_free memory that we got.
 **************************************************************************/
SECTION
section_new(LINE first, LINE last, LIST list)
{
        SECTION sec;

        /* alloc the sec and remember where we alloc-ed it */
        if (list) {
                sec = (SECTION) List_NewLast(list, sizeof(struct section));
                sec->bDiscard = TRUE;
        } else {
                sec = (SECTION) gmem_get(hHeap, sizeof(struct section));
                sec->bDiscard = FALSE;
        }

        sec->first = first;
        sec->last = last;
        sec->link = NULL;
        sec->correspond = NULL;
        sec->state = 0;
        sec->leftbase = 1;
        sec->rightbase = 1;

        return(sec);
}

/***************************************************************************
 * Function: section_delete
 *
 * Purpose:
 *
 * Discard a section. Free all associated memory (not the line list).
 * Free up the section itself if it was not alloc-ed on a list.
 */
void
section_delete(SECTION section)
{
        if (section->bDiscard) {
                gmem_free(hHeap, (LPSTR) section, sizeof(struct section));
        }
}

/***************************************************************************
 * Function: section_match
 *
 * Purpose:
 *
 * Match up two sections: match all lines that
 * are unique and identical between the two sections.
 *
 * We use a tree of line handles, keyed by the line hash code. We use a
 * ctree, which keeps a count for multiple identical keys. This allows
 * us to rapidly find lines that are unique within this section.
 * We build two of these trees (one for each line list). For each line
 * that is unique in both trees, we attempt to link the lines.
 *
 * We also attempt to link the first and last line of the section.
 *
 * For each line we successfully link, we spread up and down from
 * this anchor point attempting to link lines.
 *
 * We return true if we linked any lines
 *
 * This routine may be called more than once on the same list of lines.
 * In matching lines we want to find unique, *unmatched* lines: so we only
 * insert lines into the ctree if they are currently unlinked.
 */
BOOL
section_match(SECTION sec1, SECTION sec2)
{
        TREE ctleft, ctright;
        LINE line, line2;
        BOOL bLinked = FALSE;


        if ((sec1 == NULL) || (sec2 == NULL)) {
                return(FALSE);
        }

        if ((sec1->first == NULL) || (sec2->first == NULL)) {
                return(FALSE);
        }
        /* ASSERT if first is non-null, so is last */

        /* attempt to link the first line of each file, and
         * if matched, expand as long as we keep matching
         */
        bLinked |= section_expandanchor(sec1, sec1->first, sec2, sec2->first);

        /* attempt to link the last lines of each file and
         * expand upwards
         */
        bLinked |= section_expandanchor(sec1, sec1->last, sec2, sec2->last);


        /* build a tree of lines, indexed by the line hashcode.
         * a ctree will hold only the first value of any given key, but
         * it will keep track of the number of items inserted on this key.
         * thus we can keep count of the number of times this line
         * (or at least this hashcode) appears.
         */
        ctleft = section_makectree(sec1);
        ctright = section_makectree(sec2);

        /* for each unlinked line in one list (doesnt matter which), find if
         * appears once only in each list. if so, link, and expand
         * the link to link lines before and after the matching line
         * as long as they continue to match.
         */
        for (line = sec1->first; line != NULL; line = List_Next(line)) {

                if ((line_getlink(line) == NULL) &&
                   (ctree_getcount(ctleft, line_gethashcode(line)) == 1) &&
                   (ctree_getcount(ctright, line_gethashcode(line)) == 1)) {

                        /* line appears exactly once in each list */
                        line2 = * ((LINE FAR *)ctree_find(ctright,
                                        line_gethashcode(line)));
                        bLinked |= section_expandanchor(sec1, line, sec2, line2);
                }               

                if (line == sec1->last) {
                        break;
                }
        }

        /* delete the ctrees */
        ctree_delete(ctleft);
        ctree_delete(ctright);

        return(bLinked);
} /* section_match */

/***************************************************************************
 * Function: section_getfirstline
 *
 * Purpose:
 *
 * Gets a handle to the first line in this section
 */
LINE
section_getfirstline(SECTION section)
{
        if (section == NULL) {
                return(NULL);
        }
        return(section->first);
}

/***************************************************************************
 * Function: section_getlastline
 *
 * Purpose:
 *
 * Returns a handle to the last line in a section
 */
LINE
section_getlastline(SECTION section)
{
        if (section == NULL) {
                return(NULL);
        }
        return(section->last);
}

/***************************************************************************
 * Function: section_getlink
 *
 * Purpose:
 *
 * Returns a handle to the linked section, if any. A linked section
 * is a section whose lines all match the lines in this section
 */
SECTION
section_getlink(SECTION section)
{
        if (section == NULL) {
                return NULL;
        }
        return(section->link);
}

/***************************************************************************
 * Function: section_getcorrespond
 *
 * Purpose:
 *
 * Returns a handle to the corresponding section (a section which
 * corresponds in position to this one, but whose lines do not match).
 */
SECTION
section_getcorrespond(SECTION section)
{
        if (section == NULL) {
                return(NULL);
        }
        return(section->correspond);    
}
/***************************************************************************
 * Function: section_getstate
 *
 * Purpose:
 *
 * Gets the state for this section */
int
section_getstate(SECTION section)
{
        if (section == NULL) 
                return(0);
        return(section->state);
}

/***************************************************************************
 * Function: section_setstate
 *
 * Purpose:
 *
 * Sets the state for this section */
void
section_setstate(SECTION section, int state)
{
        section->state = state;
}

/***************************************************************************
 * Function: section_getlinecount
 *
 * Purpose:
 *
 * Returns the number of lines in the section. Here we assume that
 * lines in the section are number sequentially in ascending order, and we
 * simply look at the first and last line numbers.
 */
int
section_getlinecount(SECTION section)
{
        return(line_getlinenr(section->last) -
                        line_getlinenr(section->first)) + 1;
}

/*
 * -- base line numbers --
 *
 * These functions only apply to sections in the composite list. When creating
 * a composite section, we record the line number of the first line in each
 * of the two sections we built it from. Thus we can calculate the
 * line number of any line in the section in either file it appeared in,
 * by adding the index of the line within the section to the base line
 * number.
 */
int
section_getleftbasenr(SECTION section)
{
        return(section->leftbase);
}

void
section_setleftbasenr(SECTION section, int base)
{
        section->leftbase = base;
}

int
section_getrightbasenr(SECTION section)
{
        return(section->rightbase);
}

void
section_setrightbasenr(SECTION section, int base)
{
        section->rightbase = base;
}


/* --- section list functions -------------------------------------*/

/* Theory of handling blank lines:
|   
|  If ignore_blanks is FALSE then a blank is just another character.
|  If it is TRUE then we will normally include unmatched blanks in whatever
|  section is surrounding them.  It would be nice if we could arrange to
|  never have a section that is only unmatched blanks, but (at least at
|  the start of the file) it can happen.
|
|  Note that there are two DIFFERENT blank handling techniques:
|  In the first phase of the comparison when we are just trying to match up