![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to section.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff|
Return to section.c CVS log | Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff |
1.1 root 1:
2: /******************************************************************************\
3: * This is a part of the Microsoft Source Code Samples.
4: * Copyright (C) 1993 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: SECTION.C
14: *
15: * Manages sections of lines, and lists of sections.
16: *
17: * Functions:
18: *
19: * section_new()
20: * section_delete()
21: * section_match()
22: * section_getfirstline()
23: * section_getlastline()
24: * section_getlink()
25: * section_getcorrespond()
26: * section_getstate()
27: * section_setstate()
28: * section_getlinecount()
29: * section_getleftbasenr()
30: * section_setleftbasenr()
31: * section_getrightbasenr()
32: * section_setrightbasenr()
33: * FindEndOfUnmatched()
34: * NextNonIngnorable()
35: * FinEndOfMatched()
36: * section_makelist()
37: * section_deletelist()
38: * FindFirstWithLink()
39: * section_matchlists()
40: * section_takesection()
41: * section_makecomposite()
42: * AbsorbAnyBlanks()
43: * section_makectree()
44: * section_expandanchor()
45: *
46: * Comments:
47: *
48: * A section is a data type that represents a contiguous block of lines
49: * of the same state (all unmatched, or all matched to a contiguous block of
50: * lines). A section can link up matching lines within the section.
51: *
52: * Section list functions can make and match lists of sections from lists of
53: * lines, and create a composite list by combining sections from two lists
54: * to create a list that 'best represents' the similarities and differences
55: * between the two lists of lines.
56: *
57: * Assumptions: the lines passed in are on a list (can be traversed with
58: * List_Next() etc. Line numbering using the section_get*basenr()
59: * functions work only if lines are numbered sequentially in ascending order.
60: *
61: ****************************************************************************/
62:
63: #include <windows.h>
64: #include <stdlib.h>
65: #include <string.h>
66:
67: #include "gutils.h"
68: #include "tree.h"
69: #include "state.h"
70: #include "windiff.h"
71: #include "wdiffrc.h"
72: #include "list.h"
73: #include "line.h"
74: #include "section.h"
75:
76: /*
77: * a section handle (SECTION) is a pointer to one of these structures
78: */
79: struct section {
80: LINE first; /* first line in section */
81: LINE last; /* last line in section */
82:
83: BOOL bDiscard; /* true if not alloc-ed on list */
84:
85: SECTION link; /* we match this section */
86: SECTION correspond; /* we correspond to this section, but
87: * don't match it
88: */
89:
90: int state; /* compare state for section */
91:
92: int leftbase; /* nr in original left list of first line*/
93: int rightbase; /* nr in original right list of first line*/
94: };
95:
96: /* --- function prototypes ------------------------------------------*/
97:
98: TREE section_makectree(SECTION sec);
99: BOOL section_expandanchor(SECTION sec1, LINE line1, SECTION sec2, LINE line2);
100:
101:
102:
103: /***************************************************************************
104: * Function: section_new
105: *
106: * Purpose:
107: *
108: * Makes a new section, given handles to a first and last line.
109: *
110: * A section must be at least one line long. The lines passed in must be
111: * on a list in order.
112: *
113: * If the list parameter is non-null, we will allocate the section struct
114: * on the list. otherwise we will alloc it from gmem_get(hHeap). We remember
115: * this in the bDiscard flag for section_delete, so that we only
116: * hand back to gmem_free memory that we got.
117: **************************************************************************/
118: SECTION
119: section_new(LINE first, LINE last, LIST list)
120: {
121: SECTION sec;
122:
123: /* alloc the sec and remember where we alloc-ed it */
124: if (list) {
125: sec = (SECTION) List_NewLast(list, sizeof(struct section));
126: sec->bDiscard = TRUE;
127: } else {
128: sec = (SECTION) gmem_get(hHeap, sizeof(struct section));
129: sec->bDiscard = FALSE;
130: }
131:
132: sec->first = first;
133: sec->last = last;
134: sec->link = NULL;
135: sec->correspond = NULL;
136: sec->state = 0;
137: sec->leftbase = 1;
138: sec->rightbase = 1;
139:
140: return(sec);
141: }
142:
143: /***************************************************************************
144: * Function: section_delete
145: *
146: * Purpose:
147: *
148: * Discard a section. Free all associated memory (not the line list).
149: * Free up the section itself if it was not alloc-ed on a list.
150: */
151: void
152: section_delete(SECTION section)
153: {
154: if (section->bDiscard) {
155: gmem_free(hHeap, (LPSTR) section, sizeof(struct section));
156: }
157: }
158:
159: /***************************************************************************
160: * Function: section_match
161: *
162: * Purpose:
163: *
164: * Match up two sections: match all lines that
165: * are unique and identical between the two sections.
166: *
167: * We use a tree of line handles, keyed by the line hash code. We use a
168: * ctree, which keeps a count for multiple identical keys. This allows
169: * us to rapidly find lines that are unique within this section.
170: * We build two of these trees (one for each line list). For each line
171: * that is unique in both trees, we attempt to link the lines.
172: *
173: * We also attempt to link the first and last line of the section.
174: *
175: * For each line we successfully link, we spread up and down from
176: * this anchor point attempting to link lines.
177: *
178: * We return true if we linked any lines
179: *
180: * This routine may be called more than once on the same list of lines.
181: * In matching lines we want to find unique, *unmatched* lines: so we only
182: * insert lines into the ctree if they are currently unlinked.
183: */
184: BOOL
185: section_match(SECTION sec1, SECTION sec2)
186: {
187: TREE ctleft, ctright;
188: LINE line, line2;
189: BOOL bLinked = FALSE;
190:
191:
192: if ((sec1 == NULL) || (sec2 == NULL)) {
193: return(FALSE);
194: }
195:
196: if ((sec1->first == NULL) || (sec2->first == NULL)) {
197: return(FALSE);
198: }
199: /* ASSERT if first is non-null, so is last */
200:
201: /* attempt to link the first line of each file, and
202: * if matched, expand as long as we keep matching
203: */
204: bLinked |= section_expandanchor(sec1, sec1->first, sec2, sec2->first);
205:
206: /* attempt to link the last lines of each file and
207: * expand upwards
208: */
209: bLinked |= section_expandanchor(sec1, sec1->last, sec2, sec2->last);
210:
211:
212: /* build a tree of lines, indexed by the line hashcode.
213: * a ctree will hold only the first value of any given key, but
214: * it will keep track of the number of items inserted on this key.
215: * thus we can keep count of the number of times this line
216: * (or at least this hashcode) appears.
217: */
218: ctleft = section_makectree(sec1);
219: ctright = section_makectree(sec2);
220:
221: /* for each unlinked line in one list (doesnt matter which), find if
222: * appears once only in each list. if so, link, and expand
223: * the link to link lines before and after the matching line
224: * as long as they continue to match.
225: */
226: for (line = sec1->first; line != NULL; line = List_Next(line)) {
227:
228: if ((line_getlink(line) == NULL) &&
229: (ctree_getcount(ctleft, line_gethashcode(line)) == 1) &&
230: (ctree_getcount(ctright, line_gethashcode(line)) == 1)) {
231:
232: /* line appears exactly once in each list */
233: line2 = * ((LINE FAR *)ctree_find(ctright,
234: line_gethashcode(line)));
235: bLinked |= section_expandanchor(sec1, line, sec2, line2);
236: }
237:
238: if (line == sec1->last) {
239: break;
240: }
241: }
242:
243: /* delete the ctrees */
244: ctree_delete(ctleft);
245: ctree_delete(ctright);
246:
247: return(bLinked);
248: } /* section_match */
249:
250: /***************************************************************************
251: * Function: section_getfirstline
252: *
253: * Purpose:
254: *
255: * Gets a handle to the first line in this section
256: */
257: LINE
258: section_getfirstline(SECTION section)
259: {
260: if (section == NULL) {
261: return(NULL);
262: }
263: return(section->first);
264: }
265:
266: /***************************************************************************
267: * Function: section_getlastline
268: *
269: * Purpose:
270: *
271: * Returns a handle to the last line in a section
272: */
273: LINE
274: section_getlastline(SECTION section)
275: {
276: if (section == NULL) {
277: return(NULL);
278: }
279: return(section->last);
280: }
281:
282: /***************************************************************************
283: * Function: section_getlink
284: *
285: * Purpose:
286: *
287: * Returns a handle to the linked section, if any. A linked section
288: * is a section whose lines all match the lines in this section
289: */
290: SECTION
291: section_getlink(SECTION section)
292: {
293: if (section == NULL) {
294: return NULL;
295: }
296: return(section->link);
297: }
298:
299: /***************************************************************************
300: * Function: section_getcorrespond
301: *
302: * Purpose:
303: *
304: * Returns a handle to the corresponding section (a section which
305: * corresponds in position to this one, but whose lines do not match).
306: */
307: SECTION
308: section_getcorrespond(SECTION section)
309: {
310: if (section == NULL) {
311: return(NULL);
312: }
313: return(section->correspond);
314: }
315: /***************************************************************************
316: * Function: section_getstate
317: *
318: * Purpose:
319: *
320: * Gets the state for this section */
321: int
322: section_getstate(SECTION section)
323: {
324: if (section == NULL)
325: return(0);
326: return(section->state);
327: }
328:
329: /***************************************************************************
330: * Function: section_setstate
331: *
332: * Purpose:
333: *
334: * Sets the state for this section */
335: void
336: section_setstate(SECTION section, int state)
337: {
338: section->state = state;
339: }
340:
341: /***************************************************************************
342: * Function: section_getlinecount
343: *
344: * Purpose:
345: *
346: * Returns the number of lines in the section. Here we assume that
347: * lines in the section are number sequentially in ascending order, and we
348: * simply look at the first and last line numbers.
349: */
350: int
351: section_getlinecount(SECTION section)
352: {
353: return(line_getlinenr(section->last) -
354: line_getlinenr(section->first)) + 1;
355: }
356:
357: /*
358: * -- base line numbers --
359: *
360: * These functions only apply to sections in the composite list. When creating
361: * a composite section, we record the line number of the first line in each
362: * of the two sections we built it from. Thus we can calculate the
363: * line number of any line in the section in either file it appeared in,
364: * by adding the index of the line within the section to the base line
365: * number.
366: */
367: int
368: section_getleftbasenr(SECTION section)
369: {
370: return(section->leftbase);
371: }
372:
373: void
374: section_setleftbasenr(SECTION section, int base)
375: {
376: section->leftbase = base;
377: }
378:
379: int
380: section_getrightbasenr(SECTION section)
381: {
382: return(section->rightbase);
383: }
384:
385: void
386: section_setrightbasenr(SECTION section, int base)
387: {
388: section->rightbase = base;
389: }
390:
391:
392: /* --- section list functions -------------------------------------*/
393:
394: /* Theory of handling blank lines:
395: |
396: | If ignore_blanks is FALSE then a blank is just another character.
397: | If it is TRUE then we will normally include unmatched blanks in whatever
398: | section is surrounding them. It would be nice if we could arrange to
399: | never have a section that is only unmatched blanks, but (at least at
400: | the start of the file) it can happen.
401: |
402: | Note that there are two DIFFERENT blank handling techniques:
403: | In the first phase of the comparison when we are just trying to match up
404: | lines, we skip over blank lines both forwards and backwards from an anchor.
405: | When we are making real sections for display we only go forwards.
406: | This results in a possible anomaly at the top of the whole file where
407: | there could be some blanks which do not match and which can only possibly
408: | be described as the start of a section.
409: | For this reason, we label the sections with their state as early as possible
410: | and go by that rather than by the presence or absence of link fields.
411: | (It takes some scanning to find a link. The first line in the section
412: | could be a blank).
413: */
414:
415: /***************************************************************************
416: * Function: FindEndOfUnmatched
417: *
418: * Purpose:
419: *
420: * Returns a LINE which is the last line in an unmatched section
421: * containing (probably starting with) Line.
422: * Note that it does not necessarily make progress.
423: *
424: * As noted above, even if blank lines are being ignored, we don't
425: * mind tagging them onto the end of an already unmatching section.
426: * This means we carry on until we find the first real link
427: */
428: LINE FindEndOfUnmatched(LINE line)
429: {
430: LINE next;
431:
432: for (; ; )
433: { next = List_Next(line);
434: if (next==NULL) return line;
435: if (line_getlink(next)!=NULL) return line;
436: line = next;
437: }
438: } /* FindEndOfUnmatched */
439:
440:
441: /***************************************************************************
442: * Function: NextNonIgnorable
443: *
444: * Purpose:
445: *
446: * An ignorable line is a blank line with no link and ignore_blanks set
447: *
448: * Given that line is initially not NULL and not ignorable:
449: * If line is the last line in the list then return NULL
450: * Else If ignore_blanks is FALSE then return the next line after line
451: * else return next line which has a link or which is non-blank.
452: * If there is no such line then return the last line in the list.
453: *
454: * Note that this does always make progress (at the cost of
455: * sometimes returning NULL).
456: */
457: LINE NextNonIgnorable(LINE line)
458: { LINE next;
459:
460: next = List_Next(line);
461: if (next==NULL) return NULL;
462: for (; ; ) {
463: line = next;
464: if ( line_getlink(line)!=NULL) return line;
465: if (! ignore_blanks) return line;
466: if (! line_isblank(line)) return line;
467: next = List_Next(line);
468: if (next==NULL) return line;
469: }
470: } /* NextNonIgnorable */
471:
472:
473: /***************************************************************************
474: * Function: FindEndOfMatched
475: *
476: * Purpose:
477: *
478: * Given that line is either linked or an ignorable blank:
479: * Return a LINE which is the last line in a matched section
480: * containing (probably starting with) line.
481: * This could mean returning the line we were given.
482: *
483: * If the lines linked to are not consecutive then the section ends.
484: * If blanks are being ignored, then any blank line is deemed
485: * to match (even if it doesn't match). In this case we need the
486: * links of the lines before and after the blanks to be consecutive
487: * in order to carry on. There could be blank lines on either or both
488: * ends of the links.
489: */
490: LINE FindEndOfMatched(LINE line)
491: {
492: LINE next; /* next non-ignored or linked line */
493: LINE nextlink; /* next in other file */
494:
495: /* The basic algorithm is to set up next and nextlink to point to
496: candidate lines. Examine them. If they are good then step
497: on to them, else return the line one before.
498: There are confusion factors associated with the beginning and
499: end of the file.
500: */
501:
502: /* ASSERT( line is either an ignorable blank or else is linked) */
503:
504: /* As a section (at least at the start of the file) might start
505: with an ignored non-linked blank line, first step over any such
506: */
507: if( line_getlink(line)==NULL && line_isblank(line) ) {
508: next = NextNonIgnorable(line);
509:
510: /* There are unfortunately 6 cases to deal with
511: * marks where next will be. * against eof means next==NULL
512: blank(s) refer to ignorable unlinked blanks.
513: A B C D E F
514: line-> xxxxx xxxxx xxxxx xxxxx xxxxx xxxxx
515: *unlinked blanks *linked blanks *eof *blanks
516: *unlinked *linked eof
517:
518: next could be:
519:
520: null - case E => return line
521: unlinked ignorable blank - case F => return that blank line
522: unlinked other - cases A,B return prev(that unlinked line)
523: linked - cases C,D continue from that linked line
524: */
525: if (next==NULL) return line;
526: if (line_getlink(next)==NULL) {
527: if (ignore_blanks && line_isblank(next)) {
528: return next;
529: }
530: return List_Prev(next);
531: }
532:
533: line = next;
534: }
535:
536: /* we have stepped over inital blanks and now do have a link */
537:
538: for ( ; ; ) {
539:
540: next = NextNonIgnorable(line);
541: /* Same 6 cases - basically same again */
542: if (next==NULL) return line;
543: if (line_getlink(next)==NULL) {
544: if (ignore_blanks && line_isblank(next)) {
545: return next;
546: }
547: return List_Prev(next);
548: }
549:
550: nextlink = NextNonIgnorable(line_getlink(line));
551:
552: /* WEAK LOOP INVARIANT
553: line is linked.
554: next is the next non-ignorable line in this list after line.
555: nextlink is the next non-ignorable line after link(line)
556: in the other list (could be NULL etc).
557: */
558: if (line_getlink(next) != nextlink) return List_Prev(next);
559:
560: line = next;
561: }
562: return line;
563: } /* FindEndOfMatched */
564:
565:
566: /***************************************************************************
567: * Function: section_makelist
568: *
569: * Purpose:
570: *
571: * Make a list of sections by traversing a list of lines. Consecutive
572: * linked lines that are linked to consecutive lines are put in a single
573: * section. Blocks of unlinked lines are placed in a section.
574: * If ignore_blanks is set then we first try to link them as normal.
575: * but if they won't link then we just skip over them and keep them
576: * in the same section.
577: *
578: * Left must be set TRUE iff the list of lines is a left hand section.
579: * Returns a handle to a list of sections
580: */
581: LIST
582: section_makelist(LIST linelist, BOOL left)
583: {
584: LINE line1, line2;
585: LIST sections;
586: BOOL matched;
587: SECTION sect;
588:
589: /* make an empty list of sections */
590: sections = List_Create();
591:
592: /* for each line in the list */
593:
594: List_TRAVERSE(linelist, line1) {
595:
596: /* is it linked ? */
597:
598: if( line_getlink(line1) != NULL
599: || ( ignore_blanks && line_isblank(line1))
600: ) {
601: line2 = FindEndOfMatched(line1);
602: matched = TRUE;
603: } else {
604: line2 = FindEndOfUnmatched(line1);
605: matched = FALSE;
606: }
607:
608: /* create the section and add to list */
609: sect = section_new(line1, line2, sections);
610: sect->state = (matched ? STATE_SAME
611: : left ? STATE_LEFTONLY
612: : STATE_RIGHTONLY
613: );
614:
615: /* advance to end of section (no-op if 1 line section) */
616: line1 = line2;
617: }
618:
619: return(sections);
620: } /* section_makelist */
621:
622:
623:
624: /***************************************************************************
625: * Function: section_deletelist
626: *
627: * Purpose:
628: *
629: * Delete a list of sections
630: *
631: * Sections have no dangling pointers, so all we do is delete the list
632: */
633: void
634: section_deletelist(LIST sections)
635: {
636: List_Destroy(§ions);
637: }
638:
639: /***************************************************************************
640: * Function: FindFirstWithLink
641: *
642: * Purpose:
643: *
644: * Return the first line in the range first..last
645: * which has a link. Return last if none of them have a link.
646: * List_Next must lead from first to last eventually.
647: * It is legit for last to be NULL.
648: */
649: LINE FindFirstWithLink(LINE first, LINE last)
650: {
651: /* The strategy of including blanks on the ENDS of sections rather
652: than the start of new sections will mean that this function
653: usually strikes gold immediately. A file with a leading
654: blank section is its raison d'etre.
655: */
656: while (line_getlink(first)==NULL && first!=last)
657: first = List_Next(first);
658:
659: if (line_getlink(first)==NULL) {
660: }
661: return first;
662: } /* FindFirstWithLink */
663:
664:
665: /***************************************************************************
666: * Function: section_matchlists
667: *
668: * Purpose:
669: *
670: * Match up two lists of sections. Establish links between sections
671: * that match, and establish 'correspondence' between sections that
672: * are in the same place, but don't match.
673: *
674: * For each pair of corresponding sections, we also call section_match
675: * to try and link up more lines.
676: *
677: * We return TRUE if we made any more links between lines, or false
678: * otherwise.
679: *
680: */
681: BOOL
682: section_matchlists(LIST secsleft, LIST secsright)
683: {
684: BOOL bLinked = FALSE;
685: SECTION sec1, sec2;
686:
687: /* match up linked sections - We know whether a section is
688: supposed to link from its state, but we don't know what section
689: it links to. Also we can have sections which are defined to
690: be matching but actually contain nothing but ignorable
691: blank lines
692: */
693:
694: /* for each linked section try to find the section linked to it. */
695: List_TRAVERSE(secsleft, sec1) {
696: if (sec1->state==STATE_SAME) {
697: LINE FirstWithLink = FindFirstWithLink(sec1->first, sec1->last);
698: List_TRAVERSE(secsright, sec2) {
699: if ( sec2->state==STATE_SAME
700: && line_getlink(FirstWithLink)
701: == FindFirstWithLink(sec2->first, sec2->last)) {
702: break;
703: }
704: }
705: /* sec2 could be NULL if sec1 is all allowable blanks */
706: if (sec2!=NULL) {
707: sec1->link = sec2;
708: sec2->link = sec1;
709: }
710: }
711: }
712:
713: /* go through all unmatched sections. Note that we need to complete
714: * the link-up of matching sections before this, since we need
715: * all the links in place for this to work.
716: */
717:
718: List_TRAVERSE(secsleft, sec1) {
719: SECTION secTemp;
720:
721: if (sec1->state == STATE_SAME) {
722: /* skip the linked sections */
723: continue;
724: }
725:
726: /* check that the previous and next sections, if
727: * they exist, are linked. this should not fail since
728: * two consecutive unlinked sections should be made into
729: * one section
730: */
731: secTemp = List_Prev(sec1);
732: if (secTemp && secTemp->state!= STATE_SAME) {
733: continue;
734: }
735: secTemp = List_Next(sec1);
736: if (secTemp && secTemp->state!= STATE_SAME) {
737: continue;
738: }
739:
740: /* find the section that corresponds to this - that is, the
741: * section following the section linked to our previous section.
742: * we could be at beginning or end of list.
743: */
744: if (List_Prev(sec1) != NULL) {
745: SECTION secOther;
746: secOther = section_getlink(List_Prev(sec1));
747: if (secOther==NULL)
748: continue;
749:
750: sec2 = List_Next(secOther);
751:
752: /* check this section is not linked */
753: if ((sec2 == NULL) || (section_getlink(sec2) != NULL)) {
754: continue;
755: }
756:
757: /* check that the section after these are linked
758: * to each other (or both are at end of list).
759: */
760: if (List_Next(sec1) != NULL) {
761:
762: if (section_getlink(List_Next(sec1)) !=
763: List_Next(sec2)) {
764: continue;
765: }
766: } else {
767: if (List_Next(sec2) == NULL) {
768: continue;
769: }
770: }
771:
772: } else if (List_Next(sec1) != NULL) {
773: SECTION secOther;
774: secOther = section_getlink(List_Next(sec1));
775: if (secOther==NULL)
776: continue;
777:
778: sec2 = List_Prev(secOther);
779:
780: /* check this section is not linked */
781: if ((sec2 == NULL) || (section_getlink(sec2) != NULL)) {
782: continue;
783: }
784:
785: /* check that the section before these are linked
786: * to each other (or both are at start of list).
787: */
788: if (List_Prev(sec1) != NULL) {
789:
790: if (section_getlink(List_Prev(sec1)) !=
791: List_Prev(sec2)) {
792: continue;
793: }
794: } else {
795: if (List_Prev(sec2) == NULL) {
796: continue;
797: }
798: }
799: } else {
800: /* there must be at most one section in each
801: * file, and they are unmatched. make these correspond.
802: */
803: sec2 = List_First(secsright);
804: }
805:
806:
807: /* make the correspondence links
808: */
809: if ((sec1 != NULL) && (sec2 != NULL)) {
810: sec1->correspond = sec2;
811: sec2->correspond = sec1;
812: }
813:
814: /* attempt to link up lines */
815: if (section_match(sec1, sec2)) {
816: bLinked = TRUE;
817: }
818: }
819:
820: return(bLinked);
821: } /* section_matchlists */
822:
823: /***************************************************************************
824: * Function: section_takesection
825: *
826: * Purpose:
827: *
828: * Add a section to the composite list. Called from make_composites
829: * to copy a section, add it to the composite list and set the state,
830: * leftbase and rightbase. Note that the state could be STATE_SAME
831: * with a NULL section on the left. May NOT call with STATE_SAME and
832: * a NULL right section!
833: *
834: */
835: void
836: section_takesection(LIST compo, SECTION left, SECTION right, int state)
837: {
838: SECTION newsec;
839: SECTION sec;
840:
841: /* select which section is being output, and change the state
842: * to indicate it has been output
843: */
844: switch(state) {
845: case STATE_SAME:
846: /* both the same. we mark both as output, and
847: * take the right one. It is possible that the
848: * left one could be NULL (an ignorable blank section)
849: */
850: if (left!=NULL) left->state = STATE_MARKED;
851: right->state = STATE_MARKED;
852: sec = right;
853: break;
854:
855: case STATE_LEFTONLY:
856: case STATE_MOVEDLEFT:
857: sec = left;
858: left->state = STATE_MARKED;
859: break;
860:
861: case STATE_RIGHTONLY:
862: case STATE_MOVEDRIGHT:
863: sec = right;
864: right->state = STATE_MARKED;
865: break;
866: }
867:
868:
869: /* create a new section on the list */
870: newsec = section_new(sec->first, sec->last, compo);
871:
872: newsec->state = state;
873:
874:
875: if (left != NULL) {
876: newsec->leftbase = line_getlinenr(left->first);
877: } else {
878: newsec->leftbase = 0;
879: }
880:
881: if (right != NULL) {
882: newsec->rightbase = line_getlinenr(right->first);
883: } else {
884: newsec->rightbase = 0;
885: }
886:
887: } /* section_takesection */
888:
889: /***************************************************************************
890: * Function: section_makecomposite
891: *
892: * Purpose:
893: *
894: * Make a composite list of sections by traversing a list of sections.
895: *
896: * Return a handle to a list of sections.
897: *
898: * During this, set state, leftbase and rightbase for sections.
899: *
900: * Comments:
901: *
902: * This function creates a list that corresponds to the 'best' view
903: * of the differences between the two lists. We place sections from the
904: * two lists into one composite list. Sections that match each other are only
905: * inserted once (from the right list). Sections that match, but in different
906: * positions in the two lists are inserted twice, once in each position, with
907: * status to indicate this. Unmatched sections are inserted in the correct
908: * position.
909: *
910: * - Take sections from the left list until the section is linked to one not
911: * already taken.
912: * - Then take sections from right until we find a section linked to one not
913: * already taken.
914: * - If the two sections waiting are linked to each other, take them both
915: * (once- we take the right one and advance past both).
916: *
917: * - Now we have to decide which to take in place and which to declare
918: * 'moved'. Consider the case where the only change is that the first line
919: * has been moved to the end. We should take the first line (as a move),
920: * then the bulk of the file (SAME) then the last line (as a move). Hence,
921: * in difficult cases, we take the smaller section first, to ensure that
922: * the larger section is taken as SAME.
923: *
924: * To indicate which section has been output, we set the state field
925: * to STATE_MARKED once we have taken it. States in left and right
926: * lists are of no further interest once we have built the composite.
927: *
928: * Up to this point we have worked off the STATE of a section. By now
929: * all the section links are in place, so we can use them too.
930: */
931: LIST
932: section_makecomposite(LIST secsleft, LIST secsright)
933: {
934: SECTION left, right;
935: LIST compo;
936:
937: /* make an empty list for the composite */
938: compo = List_Create();
939:
940: left = List_First(secsleft);
941: right = List_First(secsright);
942:
943: while ( (left != NULL) || (right != NULL)) {
944:
945: if (left == NULL) {
946: /* no more in left list - take right section */
947: /* is it moved or just unmatched ? */
948: if (right->link == NULL) {
949: section_takesection(compo, NULL, right, STATE_RIGHTONLY);
950: right = List_Next(right);
951: } else {
952: section_takesection(compo, right->link, right, STATE_MOVEDRIGHT);
953: right = List_Next(right);
954: }
955: } else if (right == NULL) {
956: /* right list empty - must be left next */
957:
958: /* is it moved or just unmatched ? */
959: if (left->link == NULL) {
960: section_takesection(compo, left, NULL, STATE_LEFTONLY);
961: left = List_Next(left);
962: } else {
963: section_takesection(compo, left, left->link, STATE_MOVEDLEFT);
964: left = List_Next(left);
965: }
966:
967: } else if (left->state == STATE_LEFTONLY) {
968: /* unlinked section on left */
969: section_takesection(compo, left, NULL, STATE_LEFTONLY);
970: left = List_Next(left);
971:
972: } else if (left->link==NULL) {
973: /* This is an ignorable blank section on the left.
974: * We ignore it. (We will take any such from the right)
975: */
976: left = List_Next(left);
977:
978: } else if (left->link->state==STATE_MARKED) {
979: /* left is linked to section that is already taken*/
980: section_takesection(compo, left, left->link, STATE_MOVEDLEFT);
981: left = List_Next(left);
982:
983: } else if (right->link == NULL) {
984: /* take unlinked section on right
985: * Either unmatched or ignorable blanks
986: */
987: section_takesection(compo, NULL, right, right->state);
988: right = List_Next(right);
989:
990: } else if (right->link->state==STATE_MARKED) {
991: /* right is linked to section that's already taken */
992: section_takesection(compo, right->link, right, STATE_MOVEDRIGHT);
993: right = List_Next(right);
994:
995: } else if (left->link == right) {
996: /* sections match */
997: section_takesection(compo, left, right, STATE_SAME);
998: right = List_Next(right);
999: left = List_Next(left);
1000: } else {
1001: /* both sections linked to forward sections
1002: * decide first based on size of sections
1003: * - smallest first as a move so that largest
1004: * is an unchanged.
1005: */
1006: if (section_getlinecount(right) > section_getlinecount(left)) {
1007: section_takesection(compo, left, left->link, STATE_MOVEDLEFT);
1008: left = List_Next(left);
1009: } else {
1010: section_takesection(compo, right->link, right, STATE_MOVEDRIGHT);
1011: right = List_Next(right);
1012: }
1013: }
1014: }
1015:
1016: return(compo);
1017: } /* section_makecomposite */
1018:
1019: typedef LINE (APIENTRY * MOVEPROC)(LINE);
1020:
1021: /***************************************************************************
1022: * Function: AbsorbAnyBlanks
1023: *
1024: * Purpose:
1025: *
1026: * Update PLINE by making it point to the first non-blank
1027: * at-or-after from but not after limit.
1028: * If they are all blank then make it point to limit
1029: * If from is non-blank then leave it alone.
1030: * Return TRUE iff PLINE was updated.
1031: * It is legit for limit to be NULL (meaning end of file).
1032: */
1033: BOOL AbsorbAnyBlanks(LINE * from, LINE limit, MOVEPROC Move)
1034: { BOOL progress = FALSE;
1035:
1036: while ( (from!=NULL)
1037: && (line_isblank(*from))
1038: && (*from!=limit)
1039: ) {
1040: *from = Move(*from);
1041: progress = TRUE;
1042: }
1043: return progress;
1044: } /* AbsorbAnyBlanks */
1045:
1046:
1047: /***************************************************************************
1048: * Function: section_expandanchor
1049: *
1050: * Purpose:
1051: *
1052: * Given an anchor point (two lines that we think should match),
1053: * try to link them, and the lines above and below them for as long
1054: * as the lines can be linked (are the same, are unlinked).
1055: *
1056: * Return TRUE if we make any links.
1057: *
1058: */
1059: BOOL
1060: section_expandanchor(SECTION sec1, LINE line1, SECTION sec2, LINE line2)
1061: {
1062: /* when a line is matched we set bChanges. If we notice some
1063: * blank lines, but do NOT link any new non-blank lines, we
1064: * do NOT set bChanges. (If we did it would cause a closed
1065: * loop as they would get noticed again next time. line_link
1066: * only returns TRUE if it is a NEW link).
1067: * At this stage we are only interested in making links, not in
1068: * the size of the section that results (that fun comes later).
1069: * therefore trailing blanks at the end of a section are not
1070: * interesting and we don't look for them.
1071: */
1072: BOOL bChanges = FALSE;
1073: LINE left, right;
1074:
1075: /* We handle the section limits by using a sentinel which is one
1076: * past the end of the section. (If the section ends at the end
1077: * of the list then the sentinel is NULL).
1078: */
1079: LINE leftend, rightend;
1080: leftend = List_Next(sec1->last);
1081: rightend = List_Next(sec2->last);
1082:
1083: /* null lines shall not match */
1084: if ((line1 == NULL) || (line2 == NULL)) {
1085: return(FALSE);
1086: }
1087:
1088: /* check all lines forward until fail to link (because null,
1089: * not matching, or already linked).
1090: * include the passed in anchor point since this has not
1091: * yet been linked.
1092: * If blanks are ignorable then skip over any number of whole
1093: * blank lines.
1094: */
1095: left = line1;
1096: right = line2;
1097: for (; ; ) {
1098: if (line_link(left, right) ) {
1099:
1100: bChanges = TRUE;
1101: left = List_Next(left);
1102: right = List_Next(right);
1103: if (left==leftend || right==rightend) break;
1104: }
1105: else if (ignore_blanks){
1106: /* even though no match, maybe an ignorable blank? */
1107:
1108: BOOL moved = FALSE;
1109: moved |= AbsorbAnyBlanks(&left, leftend, (MOVEPROC)List_Next);
1110: moved |= AbsorbAnyBlanks(&right, rightend, (MOVEPROC)List_Next);
1111: if (!moved) break; /* it didn't match and we didn't move on */
1112: if (left==leftend || right==rightend) break;
1113: }
1114: else break;
1115: }
1116:
1117: /* check all matches going backwards from anchor point
1118: but only if it was a real anchor (could have been
1119: end-of-section/end-of-file and non-matching).
1120: */
1121: if (line_getlink(line1)==NULL) return bChanges;
1122:
1123: left = List_Prev(line1);
1124: right = List_Prev(line2);
1125: if (left==NULL || right==NULL) return bChanges;
1126:
1127: leftend = List_Prev(sec1->first);
1128: rightend = List_Prev(sec2->first);
1129:
1130: for (; ; ) {
1131: if (line_link(left, right)) {
1132:
1133: bChanges = TRUE;
1134: left = List_Prev(left);
1135: right = List_Prev(right);
1136: if (left == leftend || right == rightend) break;
1137:
1138: }
1139: else if (ignore_blanks){
1140: /* even though no match, maybe an ignorable blank? */
1141:
1142: BOOL moved = FALSE;
1143: moved |= AbsorbAnyBlanks(&left, leftend, (MOVEPROC)List_Prev);
1144: moved |= AbsorbAnyBlanks(&right, rightend, (MOVEPROC)List_Prev);
1145: if (!moved) break; /* it didn't match and we didn't move on */
1146: if (left==leftend || right==rightend) break;
1147:
1148: }
1149: else break;
1150: }
1151:
1152: return(bChanges);
1153: }
1154:
1155:
1156: /***************************************************************************
1157: * Function: section_makectree
1158: *
1159: * Purpose:
1160: *
1161: * Build a ctree from the lines in the section given
1162: *
1163: * Remember that we are only interested in the lines that are
1164: * not already linked.
1165: *
1166: * The value we store in the tree is the handle of the line. the key
1167: * is the line hash code
1168: */
1169: TREE
1170: section_makectree(SECTION sec)
1171: {
1172: TREE tree;
1173: LINE line;
1174:
1175: /* make an empty tree */
1176: tree = ctree_create(hHeap);
1177:
1178: for (line = sec->first; line != NULL; line = List_Next(line)) {
1179: if (line_getlink(line) == NULL) {
1180: ctree_update(tree, line_gethashcode(line),
1181: &line, sizeof(LINE));
1182: }
1183: if (line == sec->last) {
1184: break;
1185: }
1186: }
1187: return(tree);
1188: }
1189:
1190:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.