section.c

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

|  lines, we skip over blank lines both forwards and backwards from an anchor.
|  When we are making real sections for display we only go forwards.
|  This results in a possible anomaly at the top of the whole file where
|  there could be some blanks which do not match and which can only possibly
|  be described as the start of a section.
|  For this reason, we label the sections with their state as early as possible
|  and go by that rather than by the presence or absence of link fields.
|  (It takes some scanning to find a link.  The first line in the section
|  could be a blank).
*/

/***************************************************************************
 * Function: FindEndOfUnmatched
 *
 * Purpose:
 *
 * Returns a LINE which is the last line in an unmatched section
 * containing (probably starting with) Line.
 * Note that it does not necessarily make progress.
 *
 * As noted above, even if blank lines are being ignored, we don't
 * mind tagging them onto the end of an already unmatching section.
 * This means we carry on until we find the first real link
 */
LINE FindEndOfUnmatched(LINE line)
{
        LINE next;

        for (; ; )
        {       next = List_Next(line);
                if (next==NULL) return line;
                if (line_getlink(next)!=NULL) return line;
                line = next;
        }
} /* FindEndOfUnmatched */


/***************************************************************************
 * Function: NextNonIgnorable
 *
 * Purpose:
 *
 * An ignorable line is a blank line with no link and ignore_blanks set
 *
 * Given that line is initially not NULL and not ignorable:
 * If line is the last line in the list then return NULL
 * Else If ignore_blanks is FALSE then return the next line after line
 * else return next line which has a link or which is non-blank.
 * If there is no such line then return the last line in the list.
 *
 * Note that this does always make progress (at the cost of
 * sometimes returning NULL).
 */
LINE NextNonIgnorable(LINE line)
{       LINE next;

        next = List_Next(line);
        if (next==NULL) return NULL;
        for (; ; ) {
                line = next;
                if (  line_getlink(line)!=NULL) return line;
                if (! ignore_blanks)            return line;
                if (! line_isblank(line))       return line;
                next = List_Next(line);
                if (next==NULL) return line;
        }
} /* NextNonIgnorable */


/***************************************************************************
 * Function: FindEndOfMatched
 *
 * Purpose:
 *
 * Given that line is either linked or an ignorable blank:
 * Return a LINE which is the last line in a matched section
 * containing (probably starting with) line.
 * This could mean returning the line we were given.
 *
 * If the lines linked to are not consecutive then the section ends.
 * If blanks are being ignored, then any blank line is deemed
 * to match (even if it doesn't match).  In this case we need the
 * links of the lines before and after the blanks to be consecutive
 * in order to carry on.  There could be blank lines on either or both
 * ends of the links.
 */
LINE FindEndOfMatched(LINE line)
{
        LINE next;              /* next non-ignored or linked line */
        LINE nextlink;          /* next in other file */

        /* The basic algorithm is to set up next and nextlink to point to
           candidate lines.  Examine them.  If they are good then step
           on to them, else return the line one before.
           There are confusion factors associated with the beginning and
           end of the file.
        */

        /* ASSERT( line is either an ignorable blank or else is linked) */

        /* As a section (at least at the start of the file) might start
           with an ignored non-linked blank line, first step over any such
        */
        if( line_getlink(line)==NULL && line_isblank(line) ) {
                next = NextNonIgnorable(line);

                /* There are unfortunately 6 cases to deal with
                   * marks where next will be. * against eof means next==NULL
                   blank(s) refer to ignorable unlinked blanks.
                          A         B        C        D        E        F
                   line-> xxxxx     xxxxx    xxxxx    xxxxx    xxxxx    xxxxx
                         *unlinked  blanks  *linked   blanks  *eof     *blanks
                                   *unlinked         *linked            eof

                   next could be:
                
                      null - case E => return line
                      unlinked ignorable blank - case F => return that blank line
                      unlinked other - cases A,B return prev(that unlinked line)
                      linked - cases C,D continue from that linked line
                */
                if (next==NULL) return line;
                if (line_getlink(next)==NULL) {
                        if (ignore_blanks && line_isblank(next)) {
                                return next;
                        }
                        return List_Prev(next);
                }

                line = next;
        }

        /* we have stepped over inital blanks and now do have a link */

        for ( ; ; ) {

                next = NextNonIgnorable(line);
                /* Same 6 cases - basically same again */
                if (next==NULL) return line;
                if (line_getlink(next)==NULL) {
                        if (ignore_blanks && line_isblank(next)) {
                                return next;
                        }
                        return List_Prev(next);
                }

                nextlink = NextNonIgnorable(line_getlink(line));

                /* WEAK LOOP INVARIANT
                   line is linked.
                   next is the next non-ignorable line in this list after line.
                   nextlink is the next non-ignorable line after link(line)
                                        in the other list (could be NULL etc).
                */
                if (line_getlink(next) != nextlink) return List_Prev(next);

                line = next;
        }
        return line;
} /* FindEndOfMatched */


/***************************************************************************
 * Function: section_makelist
 *
 * Purpose:
 *
 * Make a list of sections by traversing a list of lines. Consecutive
 * linked lines that are linked to consecutive lines are put in a single
 * section. Blocks of unlinked lines are placed in a section.
 * If ignore_blanks is set then we first try to link them as normal.
 * but if they won't link then we just skip over them and keep them
 * in the same section.
 *
 * Left must be set TRUE iff the list of lines is a left hand section.
 * Returns a handle to a list of sections
 */
LIST
section_makelist(LIST linelist, BOOL left)
{
        LINE line1, line2;
        LIST sections;
        BOOL matched;
        SECTION sect;

        /* make an empty list of sections */
        sections = List_Create();

        /* for each line in the list */

        List_TRAVERSE(linelist, line1) {

                /* is it linked ? */

                if( line_getlink(line1) != NULL
                  || ( ignore_blanks && line_isblank(line1))
                  ) {
                        line2 = FindEndOfMatched(line1);
                        matched = TRUE;
                } else {
                        line2 = FindEndOfUnmatched(line1);
                        matched = FALSE;
                }

                /* create the section and add to list */
                sect = section_new(line1, line2, sections);
                sect->state = (matched ? STATE_SAME
                                       : left ? STATE_LEFTONLY
                                              : STATE_RIGHTONLY
                              );

                /* advance to end of section (no-op if 1 line section) */
                line1 = line2;
        }

        return(sections);
} /* section_makelist */



/***************************************************************************
 * Function: section_deletelist
 *
 * Purpose:
 *
 * Delete a list of sections
 *
 * Sections have no dangling pointers, so all we do is delete the list
 */
void    
section_deletelist(LIST sections)
{
        List_Destroy(&sections);
}

/***************************************************************************
 * Function: FindFirstWithLink
 *
 * Purpose:
 *
 * Return the first line in the range first..last
 * which has a link.  Return last if none of them have a link.
 * List_Next must lead from first to last eventually.
 * It is legit for last to be NULL.
 */
LINE FindFirstWithLink(LINE first, LINE last)
{       
        /* The strategy of including blanks on the ENDS of sections rather
           than the start of new sections will mean that this function
           usually strikes gold immediately.  A file with a leading
           blank section is its raison d'etre.
        */
        while (line_getlink(first)==NULL && first!=last)
                first = List_Next(first);

        if (line_getlink(first)==NULL) {
        }
        return first;
} /* FindFirstWithLink */


/***************************************************************************
 * Function: section_matchlists
 *
 * Purpose:
 *
 * Match up two lists of sections. Establish links between sections
 * that match, and establish 'correspondence' between sections that
 * are in the same place, but don't match.
 *
 * For each pair of corresponding sections, we also call section_match
 * to try and link up more lines.
 *
 * We return TRUE if we made any more links between lines, or false
 * otherwise.
 *
 */
BOOL
section_matchlists(LIST secsleft, LIST secsright)
{
        BOOL bLinked = FALSE;
        SECTION sec1, sec2;

        /* match up linked sections - We know whether a section is
           supposed to link from its state, but we don't know what section
           it links to.  Also we can have sections which are defined to
           be matching but actually contain nothing but ignorable
           blank lines
        */
        
        /*  for each linked section try to find the section  linked to it. */
        List_TRAVERSE(secsleft, sec1) {
                if (sec1->state==STATE_SAME) {
                        LINE FirstWithLink = FindFirstWithLink(sec1->first, sec1->last);
                        List_TRAVERSE(secsright, sec2) {
                                if ( sec2->state==STATE_SAME
                                   && line_getlink(FirstWithLink)
                                        == FindFirstWithLink(sec2->first, sec2->last)) {
                                            break;
                                }
                        }
                        /* sec2 could be NULL if sec1 is all allowable blanks */
                        if (sec2!=NULL) {
                                sec1->link = sec2;
                                sec2->link = sec1;
                        }
                }
        }

        /* go through all unmatched sections. Note that we need to complete
         * the link-up of matching sections before this, since we need
         * all the links in place for this to work.
         */

        List_TRAVERSE(secsleft, sec1) {
                SECTION secTemp;

                if (sec1->state == STATE_SAME) {
                        /* skip the linked sections */
                        continue;
                }

                /* check that the previous and next sections, if
                 * they exist, are linked. this should not fail since
                 * two consecutive unlinked sections should be made into
                 * one section
                 */
                secTemp = List_Prev(sec1);
                if (secTemp && secTemp->state!= STATE_SAME) {
                        continue;
                }
                secTemp = List_Next(sec1);
                if (secTemp && secTemp->state!= STATE_SAME) {
                        continue;
                }

                /* find the section that corresponds to this - that is, the
                 * section following the section linked to our previous section.
                 * we could be at beginning or end of list.
                 */
                if (List_Prev(sec1) != NULL) {
                        SECTION secOther;
                        secOther = section_getlink(List_Prev(sec1));
                        if (secOther==NULL)
                                continue;

                        sec2 = List_Next(secOther);

                        /* check this section is not linked */
                        if ((sec2 == NULL) || (section_getlink(sec2) != NULL)) {
                                continue;
                        }
                        
                        /* check that the section after these are linked
                         * to each other (or both are at end of list).
                         */
                        if (List_Next(sec1) != NULL) {

                                if (section_getlink(List_Next(sec1)) !=
                                    List_Next(sec2)) {
                                        continue;
                                }
                        } else {
                                if (List_Next(sec2) == NULL) {
                                        continue;
                                }
                        }

                } else if (List_Next(sec1) != NULL) {
                        SECTION secOther;
                        secOther = section_getlink(List_Next(sec1));
                        if (secOther==NULL)
                                continue;

                        sec2 = List_Prev(secOther);

                        /* check this section is not linked */
                        if ((sec2 == NULL) || (section_getlink(sec2) != NULL)) {
                                continue;
                        }
                        
                        /* check that the section before these are linked
                         * to each other (or both are at start of list).
                         */
                        if (List_Prev(sec1) != NULL) {

                                if (section_getlink(List_Prev(sec1)) !=
                                    List_Prev(sec2)) {
                                        continue;
                                }
                        } else {
                                if (List_Prev(sec2) == NULL) {
                                        continue;
                                }