![[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.