section.c

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

                        }
                } else {
                        /* there must be at most one section in each
                         * file, and they are unmatched. make these correspond.
                         */
                        sec2 = List_First(secsright);
                }


                /* make the correspondence links
                 */
                if ((sec1 != NULL) && (sec2 != NULL)) {
                        sec1->correspond = sec2;
                        sec2->correspond = sec1;
                }

                /* attempt to link up lines */
                if (section_match(sec1, sec2)) {
                        bLinked = TRUE;
                }
        }

        return(bLinked);
} /* section_matchlists */

/***************************************************************************
 * Function: section_takesection
 *
 * Purpose:
 *
 * Add a section to the composite list. Called from make_composites
 * to copy a section, add it to the composite list and set the state,
 * leftbase and rightbase.   Note that the state could be STATE_SAME
 * with a NULL section on the left.  May NOT call with STATE_SAME and
 * a NULL right section!
 *
 */
void
section_takesection(LIST compo, SECTION left, SECTION right, int state)
{
        SECTION newsec;
        SECTION sec;

        /* select which section is being output, and change the state
         * to indicate it has been output
         */
        switch(state) {
        case STATE_SAME:
                /* both the same. we mark both as output, and
                 * take the right one.  It is possible that the
                 * left one could be NULL (an ignorable blank section)
                 */
                if (left!=NULL) left->state = STATE_MARKED;
                right->state = STATE_MARKED;
                sec = right;
                break;

        case STATE_LEFTONLY:
        case STATE_MOVEDLEFT:
                sec = left;
                left->state = STATE_MARKED;
                break;

        case STATE_RIGHTONLY:
        case STATE_MOVEDRIGHT:
                sec = right;
                right->state = STATE_MARKED;
                break;
        }


        /* create a new section on the list */
        newsec = section_new(sec->first, sec->last, compo);

        newsec->state = state;


        if (left != NULL) {
                newsec->leftbase = line_getlinenr(left->first);
        } else {
                newsec->leftbase = 0;
        }

        if (right != NULL) {
                newsec->rightbase = line_getlinenr(right->first);
        } else {
                newsec->rightbase = 0;
        }

} /* section_takesection */

/***************************************************************************
 * Function: section_makecomposite
 *
 * Purpose:
 *
 * Make a composite list of sections by traversing a list of sections.
 *
 * Return a handle to a list of sections.
 *
 * During this, set state, leftbase and rightbase for sections.
 *
 * Comments:
 *
 * This function creates a list that corresponds to the 'best' view
 * of the differences between the two lists. We place sections from the
 * two lists into one composite list. Sections that match each other are only
 * inserted once (from the right list). Sections that match, but in different
 * positions in the two lists are inserted twice, once in each position, with
 * status to indicate this. Unmatched sections are inserted in the correct
 * position.
 *
 * - Take sections from the left list until the section is linked to one not
 *   already taken.
 * - Then take sections from right until we find a section linked to one not
 *   already taken.
 * - If the two sections waiting are linked to each other, take them both
 *   (once- we take the right one and advance past both).
 *
 * - Now we have to decide which to take in place and which to declare
 *   'moved'. Consider the case where the only change is that the first line
 *   has been moved to the end. We should take the first line (as a move),
 *   then the bulk of the file (SAME) then the last line (as a move). Hence,
 *   in difficult cases, we take the smaller section first, to ensure that
 *   the larger section is taken as SAME.
 *
 *   To indicate which section has been output, we set the state field
 *   to STATE_MARKED once we have taken it.   States in left and right
 *   lists are of no further interest once we have built the composite.
 *
 *   Up to this point we have worked off the STATE of a section.  By now
 *   all the section links are in place, so we can use them too.
 */
LIST
section_makecomposite(LIST secsleft, LIST secsright)
{
        SECTION left, right;
        LIST compo;

        /* make an empty list for the composite */
        compo = List_Create();

        left = List_First(secsleft);
        right = List_First(secsright);

        while ( (left != NULL) || (right != NULL)) {

                if (left == NULL) {
                        /* no more in left list - take right section */
                        /* is it moved or just unmatched ? */
                        if (right->link == NULL) {
                                section_takesection(compo, NULL, right, STATE_RIGHTONLY);
                                right = List_Next(right);
                        } else {
                                section_takesection(compo, right->link, right, STATE_MOVEDRIGHT);
                                right = List_Next(right);
                        }
                } else if (right == NULL) {
                        /* right list empty - must be left next */

                        /* is it moved or just unmatched ? */
                        if (left->link == NULL) {
                                section_takesection(compo, left, NULL, STATE_LEFTONLY);
                                left = List_Next(left);
                        } else {
                                section_takesection(compo, left, left->link, STATE_MOVEDLEFT);
                                left = List_Next(left);
                        }

                } else if (left->state == STATE_LEFTONLY) {
                        /* unlinked section on left */
                        section_takesection(compo, left, NULL, STATE_LEFTONLY);
                        left = List_Next(left);

                } else if (left->link==NULL) {
                        /* This is an ignorable blank section on the left.
                         * We ignore it. (We will take any such from the right)
                         */
                        left = List_Next(left);

                } else if (left->link->state==STATE_MARKED) {
                        /* left is linked to section that is already taken*/
                        section_takesection(compo, left, left->link, STATE_MOVEDLEFT);
                        left = List_Next(left);

                } else  if (right->link == NULL) {
                        /* take unlinked section on right
                         * Either unmatched or ignorable blanks
                         */
                        section_takesection(compo, NULL, right, right->state);
                        right = List_Next(right);
                
                } else if (right->link->state==STATE_MARKED) {
                        /* right is linked to section that's already taken */
                        section_takesection(compo, right->link, right, STATE_MOVEDRIGHT);
                        right = List_Next(right);
                
                } else if (left->link == right) {
                        /* sections match */
                        section_takesection(compo, left, right, STATE_SAME);
                        right = List_Next(right);
                        left = List_Next(left);
                } else {
                        /* both sections linked to forward sections
                         * decide first based on size of sections
                         * - smallest first as a move so that largest
                         * is an unchanged.
                         */
                        if (section_getlinecount(right) > section_getlinecount(left)) {
                                section_takesection(compo, left, left->link, STATE_MOVEDLEFT);
                                left = List_Next(left);
                        } else {
                                section_takesection(compo, right->link, right, STATE_MOVEDRIGHT);
                                right = List_Next(right);
                        }
                }
        }

        return(compo);
} /* section_makecomposite */

typedef LINE (APIENTRY * MOVEPROC)(LINE);

/***************************************************************************
 * Function: AbsorbAnyBlanks
 *
 * Purpose:
 *
 * Update PLINE by making it point to the first non-blank
 * at-or-after from but not after limit.
 * If they are all blank then make it point to limit
 * If from is non-blank then leave it alone.
 * Return TRUE iff PLINE was updated.
 * It is legit for limit to be NULL (meaning end of file).
 */
BOOL AbsorbAnyBlanks(LINE * from, LINE limit, MOVEPROC Move)
{       BOOL progress = FALSE;

        while ( (from!=NULL)
              && (line_isblank(*from))
              && (*from!=limit)
              ) {
                *from = Move(*from);
                progress = TRUE;
        }
        return progress;
} /* AbsorbAnyBlanks */


/***************************************************************************
 * Function: section_expandanchor
 *
 * Purpose:
 *
 * Given an anchor point (two lines that we think should match),
 * try to link them, and the lines above and below them for as long
 * as the lines can be linked (are the same, are unlinked).
 *
 * Return TRUE if we make any links.
 *
 */
BOOL
section_expandanchor(SECTION sec1, LINE line1, SECTION sec2, LINE line2)
{
        /* when a line is matched we set bChanges.  If we notice some
         * blank lines, but do NOT link any new non-blank lines, we
         * do NOT set bChanges.  (If we did it would cause a closed
         * loop as they would get noticed again next time.  line_link
         * only returns TRUE if it is a NEW link).
         * At this stage we are only interested in making links, not in
         * the size of the section that results (that fun comes later).
         * therefore trailing blanks at the end of a section are not
         * interesting and we don't look for them.
         */
        BOOL bChanges = FALSE;
        LINE left, right;

        /* We handle the section limits by using a sentinel which is one
         * past the end of the section.  (If the section ends at the end
         * of the list then the sentinel is NULL).
         */
        LINE leftend, rightend;
        leftend = List_Next(sec1->last);
        rightend = List_Next(sec2->last);

        /* null lines shall not match */
        if ((line1 == NULL) || (line2 == NULL)) {
                return(FALSE);
        }

        /* check all lines forward until fail to link (because null,
         * not matching, or already linked).
         * include the passed in anchor point since this has not
         * yet been linked.
         * If blanks are ignorable then skip over any number of whole
         * blank lines.
         */
        left = line1;
        right = line2;
        for (; ; ) {
                if (line_link(left, right) ) {

                        bChanges = TRUE;
                        left = List_Next(left);
                        right = List_Next(right);
                        if (left==leftend || right==rightend) break;
                }
                else if (ignore_blanks){
                        /* even though no match, maybe an ignorable blank? */

                        BOOL moved = FALSE;
                        moved |= AbsorbAnyBlanks(&left, leftend, (MOVEPROC)List_Next);
                        moved |= AbsorbAnyBlanks(&right, rightend, (MOVEPROC)List_Next);
                        if (!moved) break; /* it didn't match and we didn't move on */
                        if (left==leftend || right==rightend) break;
                }
                else break;
        }

        /* check all matches going backwards from anchor point
           but only if it was a real anchor  (could have been
           end-of-section/end-of-file and non-matching).
        */
        if (line_getlink(line1)==NULL) return bChanges;

        left = List_Prev(line1);
        right = List_Prev(line2);
        if (left==NULL || right==NULL) return bChanges;

        leftend = List_Prev(sec1->first);
        rightend = List_Prev(sec2->first);

        for (; ; ) {
                if (line_link(left, right)) {

                        bChanges = TRUE;
                        left = List_Prev(left);
                        right = List_Prev(right);
                        if (left == leftend || right == rightend) break;

                }
                else if (ignore_blanks){
                        /* even though no match, maybe an ignorable blank? */

                        BOOL moved = FALSE;
                        moved |= AbsorbAnyBlanks(&left, leftend, (MOVEPROC)List_Prev);
                        moved |= AbsorbAnyBlanks(&right, rightend, (MOVEPROC)List_Prev);
                        if (!moved) break; /* it didn't match and we didn't move on */
                        if (left==leftend || right==rightend) break;

                }
                else break;
        }

        return(bChanges);
}


/***************************************************************************
 * Function: section_makectree
 *
 * Purpose:
 *
 * Build a ctree from the lines in the section given
 *
 * Remember that we are only interested in the lines that are
 * not already linked.
 *
 * The value we store in the tree is the handle of the line. the key
 * is the line hash code
 */
TREE
section_makectree(SECTION sec)
{
        TREE tree;
        LINE line;

        /* make an empty tree */
        tree = ctree_create(hHeap);

        for (line = sec->first; line != NULL; line = List_Next(line)) {
                if (line_getlink(line) == NULL) {
                        ctree_update(tree, line_gethashcode(line),
                                        &line, sizeof(LINE));
                }
                if (line == sec->last) {
                        break;
                }
        }
        return(tree);
}