![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to idln.getst.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / ncurses / screen|
Return to idln.getst.c CVS log | Up to [Research Unix] / researchv10no / ncurses / screen |
1.1 ! root 1: /* @(#) idln.getst.c: 1.1 10/15/83 (1.19 2/9/83) */ ! 2: ! 3: #include "curses.ext" ! 4: int InputPending; ! 5: ! 6: struct st { /* symbol table */ ! 7: int hash; /* hashed value of line ("text") */ ! 8: char oc, nc; /* 0, 1, or many: # times this value occurs */ ! 9: short olno; /* line # of line in "old" array */ ! 10: }; ! 11: ! 12: /* ! 13: * Routines to deal with calculation of how to do ins/del line optimally. ! 14: * Update the Screen. Consider using insert and delete line. ! 15: * Using Heckel's algorithm from April 1978 CACM. ! 16: * ! 17: * This algorithm is based on two observations: ! 18: * (1) A line that occurs once and only once in each file must be ! 19: * the same line (unchanged but possibly moved). ! 20: * (2) If i each file immediately adjacent to a "found" line pair ! 21: * there are lines identical to each other, these lines must be ! 22: * the same line. Repeated application will "find" sequences ! 23: * of unchanged lines. ! 24: * ! 25: * We view the old and new screens' hashed values as the old and new "files". ! 26: * Since crossing match lines cannot be taken advantage of with real insert ! 27: * and delete line, we ignore those matches - this is the one real disadvantage ! 28: * of this algorithm. ! 29: * ! 30: * first and last are the integer line numbers (first line is 1) of the ! 31: * portion of the screen to consider. ! 32: */ ! 33: _id_line(first, last) ! 34: register int first, last; ! 35: { ! 36: register int i, j, k, n; ! 37: int base, ndel; ! 38: int idl_offset = 0; /* number of extra del lines done so far. */ ! 39: #ifdef NONSTANDARD ! 40: static ! 41: #endif NONSTANDARD ! 42: struct st symtab[256]; ! 43: /* ! 44: * oa and na represent the old and new files (SP->cur_body and ! 45: * SP->std_body, respectively.) If they are > 0 they are ! 46: * subscripts in each other (e.g. na[4] = 3 means that na[4] ! 47: * points to oa[3]). If they are <= 0 their negative is taken ! 48: * as a symbol table index into the symtab array. ! 49: */ ! 50: #ifdef NONSTANDARD ! 51: static ! 52: #endif NONSTANDARD ! 53: short oa[256], na[256]; ! 54: ! 55: for (i=0; i<256; i++) ! 56: symtab[i].hash = symtab[i].oc = symtab[i].nc = 0; ! 57: ! 58: #ifdef DEBUG ! 59: if(outf) fprintf(outf, "_id_line(%d, %d)\n", first, last); ! 60: #endif ! 61: /* Pass 1: enter old file into symtab */ ! 62: for (i=first; i<=last; i++) { ! 63: n = _getst(SP->std_body[i]->hash, symtab); ! 64: symtab[n].nc++; ! 65: na[i] = -n; ! 66: } ! 67: ! 68: #ifdef LONGDEBUG ! 69: if(outf) fprintf(outf, "Pass 2\n"); ! 70: if(outf) fprintf(outf, "na[12] = %d\n", na[12]); ! 71: #endif ! 72: /* Pass 2: enter new into symtab */ ! 73: for (i=first; i<=last; i++) { ! 74: n = _getst(SP->cur_body[i]->hash, symtab); ! 75: symtab[n].oc++; ! 76: symtab[n].olno = i; ! 77: oa[i] = -n; ! 78: } ! 79: ! 80: #ifdef LONGDEBUG ! 81: if(outf) fprintf(outf, "Pass 3\n"); ! 82: if(outf) fprintf(outf, "\nsymtab oc nc olno hash\n"); ! 83: for (i=0; i<256; i++) ! 84: if (symtab[i].hash) ! 85: if(outf) fprintf(outf, "%d %d %d %d %d\n", ! 86: i, symtab[i].oc, symtab[i].nc, ! 87: symtab[i].olno, symtab[i].hash); ! 88: #endif ! 89: /* ! 90: * Pass 3: Match all lines with exactly one match. ! 91: * Matching lines in oa and na point at each other. ! 92: */ ! 93: for (i=first; i<=last; i++) { ! 94: n = -na[i]; ! 95: if (symtab[n].oc == 1 && symtab[n].nc == 1) { ! 96: na[i] = symtab[n].olno; ! 97: oa[na[i]] = i; ! 98: } ! 99: } ! 100: oa[first-1] = na[first-1] = first-1; ! 101: oa[last+1] = na[last+1] = last+1; ! 102: ! 103: /* Pass 4: Find following implied matches based on sequence */ ! 104: #ifdef DEBUG ! 105: if(outf) fprintf(outf, "Pass 4\n"); ! 106: #endif ! 107: for (i=first; i<=last; i++) { ! 108: if (na[i] > 0 && na[i+1] <= 0) { ! 109: j = na[i]; ! 110: if (na[i+1] == oa[j+1]) { ! 111: oa[j+1] = i+1; ! 112: na[i+1] = j+1; ! 113: } ! 114: } ! 115: } ! 116: ! 117: /* Pass 5: Find preceding implied matches based on sequence */ ! 118: #ifdef DEBUG ! 119: if(outf) fprintf(outf, "Pass 5\n"); ! 120: if(outf) fprintf(outf, "na[12] = %d\n", na[12]); ! 121: #endif ! 122: for (i=last; i>=first; i--) { ! 123: if (na[i] > 0 && na[i-1] <= 0) { ! 124: j = na[i]; ! 125: if (na[i-1] == oa[j-1]) { ! 126: oa[j-1] = i-1; ! 127: na[i-1] = j-1; ! 128: } ! 129: } ! 130: } ! 131: ! 132: #ifdef DEBUG ! 133: if(outf) fprintf(outf, "\ni oa na After pass 5\n"); ! 134: for (i=first; i<=last; i++) ! 135: if(outf) fprintf(outf, "%d %d %d\n", i, oa[i], na[i]); ! 136: if(outf) fprintf(outf, "\n"); ! 137: #endif ! 138: /* Pass 6: Find matches from more than one line, in order. */ ! 139: for (i=first; i<=last; i++) { ! 140: if (na[i] < -1 && symtab[-na[i]].nc > 1) { ! 141: j = na[i]; ! 142: #ifdef DEBUG ! 143: if(outf) fprintf(outf, "i %d, na[i] %d\n", i, na[i]); ! 144: #endif ! 145: for (k=first; k<last; k++) { ! 146: if (j == oa[k]) { ! 147: #ifdef DEBUG ! 148: if(outf) fprintf(outf, "k %d, oa[i] %d, matching them up\n", k, oa[i]); ! 149: #endif ! 150: na[i] = k; ! 151: oa[k] = i; ! 152: break; ! 153: } ! 154: } ! 155: } ! 156: } ! 157: #ifdef DEBUG ! 158: if(outf) fprintf(outf, "\ni oa na After pass 6\n"); ! 159: for (i=first; i<=last; i++) ! 160: if(outf) fprintf(outf, "%d %d %d\n", i, oa[i], na[i]); ! 161: if(outf) fprintf(outf, "\n"); ! 162: #endif ! 163: ! 164: /* ! 165: * Passes 7abcd: Remove any match lines that cross backwards. ! 166: * (Draw lines connecting the matching lines on debug output ! 167: * to see what I mean about crossing lines.) ! 168: * The na's must be monotonically increasing except for those < 0 ! 169: * which say there is no match. k counts the number of matches ! 170: * we have to throw away. ! 171: */ ! 172: n = k = 0; /* k is the added cost to throw away nw-se matches */ ! 173: /* 7a: get nw-se cost in k */ ! 174: for (i=first; i<=last; i++) { ! 175: if (na[i] > 0 && na[i] < n) { ! 176: k += SP->std_body[i]->bodylen; ! 177: } ! 178: if (na[i] > n) ! 179: n = na[i]; ! 180: } ! 181: /* 7b: get sw-ne cost in j */ ! 182: /* Consider throwing away in the other direction. */ ! 183: if (k > 0) { ! 184: j = 0; /* j is the added cost to throw away sw-ne matches */ ! 185: n = last+1; ! 186: for (i=last; i>=first; i--) { ! 187: if (na[i] > 0 && na[i] > n) { ! 188: j += SP->std_body[i]->bodylen; ! 189: } ! 190: if (na[i] > 0 && na[i] < n) ! 191: n = na[i]; ! 192: } ! 193: } ! 194: else ! 195: j = 1; /* will be > 0 for sure */ ! 196: #ifdef DEBUG ! 197: if(outf) fprintf(outf, "forward, k is %d, backward, j is %d\n", k, j); ! 198: #endif ! 199: ! 200: /* Remove whichever is cheapest. */ ! 201: if (k < j) { ! 202: /* 7c: remove nw-se */ ! 203: n = 0; ! 204: for (i=first; i<=last; i++) { ! 205: if (na[i] > 0 && na[i] < n) { ! 206: oa[na[i]] = -1; ! 207: na[i] = -1; ! 208: } ! 209: if (na[i] > n) ! 210: n = na[i]; ! 211: } ! 212: } else { ! 213: /* 7d: remove sw-ne */ ! 214: n = last+1; ! 215: for (i=last; i>=first; i--) { ! 216: if (na[i] > 0 && na[i] > n) { ! 217: oa[na[i]] = -1; ! 218: na[i] = -1; ! 219: } ! 220: if (na[i] > 0 && na[i] < n) ! 221: n = na[i]; ! 222: } ! 223: } ! 224: #ifdef DEBUG ! 225: if(outf) fprintf(outf, "\ni oa na After pass 7\n"); ! 226: for (i=first; i<=last; i++) ! 227: if(outf) fprintf(outf, "%d %d %d\n", i, oa[i], na[i]); ! 228: if(outf) fprintf(outf, "\nPass 7\n"); ! 229: if(outf) fprintf(outf, "ILmf %d/32, ILov %d\n", ! 230: SP->term_costs.ilvar, SP->term_costs.ilfixed); ! 231: if(outf) fprintf(outf, "i base j k DC n\n"); ! 232: #endif ! 233: ! 234: /* ! 235: * Pass 8: we go through and remove all matches if the ! 236: * overall ins/del lines would be too expensive to capatilize on. ! 237: * j is cost with ins/del line, k is cost without it. base is the ! 238: * logical beginning of the oa array, as the array would be after ! 239: * inserts and deletes, ignoring anything before row i. This ! 240: * approximates things by not taking into account SP->curptr motion, ! 241: * funny insert line costs, or lines that are partially equal. ! 242: * This macro is the cost to insert or delete n lines at screen line i. ! 243: * It is approximated for speed and simplicity, but shouldn't be. ! 244: * The approximation assumes each line is deleted separately. ! 245: */ ! 246: ! 247: #define idlcost(n, i) n * \ ! 248: (((SP->term_costs.ilvar * (lines-i))>>5) + SP->term_costs.ilfixed) ! 249: ! 250: base = ndel = 0; ! 251: j = k = 0; ! 252: for (i=first; i<=last; i++) { ! 253: #ifdef DEBUG ! 254: n = 0; ! 255: #endif ! 256: if (oa[i] != na[i]) { ! 257: /* Cost to turn Phys[i] into Des[i] on same line */ ! 258: if (SP->cur_body[i] == 0 || SP->cur_body[i]->length == 0) { ! 259: k += SP->std_body[i]->bodylen; ! 260: } else if (SP->std_body[i] == 0 || ! 261: SP->std_body[i]->length == 0) { ! 262: k += 2; /* guess at cost of clr to eol */ ! 263: } else { ! 264: register chtype *p0, *p1, *p2; ! 265: n = SP->cur_body[i]->length - ! 266: SP->std_body[i]->length; ! 267: if (n > 0) { ! 268: k += n; ! 269: n = SP->std_body[i]->length; ! 270: } else { ! 271: k += -n; ! 272: n = SP->cur_body[i]->length; ! 273: } ! 274: p0 = &SP->std_body[i]->body[0]; ! 275: p1 = &SP->std_body[i]->body[n]; ! 276: p2 = &SP->cur_body[i]->body[n]; ! 277: while (--p1 >= p0) ! 278: if (*p1 != *--p2) ! 279: k++; ! 280: } ! 281: } ! 282: /* cost to do using ins/del line */ ! 283: if (na[i] <= 0) { ! 284: /* totally different - plan on redrawing whole thing ! 285: * (even though chances are good they are partly the ! 286: * same - _id_char will take care of this, if it ! 287: * happens to get the same line on the screen). ! 288: * Should probably figure out what will be there on ! 289: * the screen and do above k algorithm on it. ! 290: */ ! 291: j += SP->std_body[i]->bodylen; ! 292: } else if ((n = (na[i] - base) - i) > 0) { ! 293: /* delete line */ ! 294: j += idlcost(n, i); ! 295: ndel += n; ! 296: base += n; ! 297: } else if (n < 0) { ! 298: /* insert line */ ! 299: j += idlcost((-n), i); ! 300: ndel += n; ! 301: base += n; ! 302: } ! 303: /* else they are the same line: no cost */ ! 304: #ifdef DEBUG ! 305: if(outf) fprintf(outf, "%d %d %d %d %d", i, base, j, k, SP->std_body[i]->bodylen); ! 306: if (n < 0) ! 307: if(outf) fprintf(outf, " %d lines inserted", -n); ! 308: else if (n > 0) ! 309: if(outf) fprintf(outf, " %d lines deleted", n); ! 310: if(outf) fprintf(outf, "\n"); ! 311: #endif ! 312: } ! 313: if (j >= k) { ! 314: /* It's as cheap to just redraw, so do it. */ ! 315: for (i=first; i<=last; i++) ! 316: na[i] = oa[i] = -1; ! 317: } else if (ndel < 0) { ! 318: ndel = -ndel; ! 319: #ifdef DEBUG ! 320: if(outf) fprintf(outf, "will do %d extra inserts, so del now.\n", ndel); ! 321: #endif ! 322: if (SP->des_bot_mgn - last >= 0) { ! 323: _pos(last-ndel, 0); ! 324: idl_offset += ndel; ! 325: _dellines(ndel); ! 326: } ! 327: } ! 328: ! 329: #ifdef DEBUG ! 330: if(outf) fprintf(outf, "\ni oa na After pass 8\n"); ! 331: for (i=first; i<=last; i++) ! 332: if(outf) fprintf(outf, "%d %d %d\n", i, oa[i], na[i]); ! 333: if(outf) fprintf(outf, "\n"); ! 334: #endif ! 335: /* Pass 9: Do any delete lines that are needed */ ! 336: k = first-1; /* previous matching spot in oa */ ! 337: ndel = 0; ! 338: for (i=first; i<=last; i++) { ! 339: if (oa[i] > 0) { ! 340: n = (i-k) - (oa[i]-oa[k]); ! 341: #ifdef DEBUG ! 342: if(outf) fprintf(outf, ! 343: "del loop, i %d, k %d, oa[i] %d, oa[k] %d, n %d\n", ! 344: i, k, oa[i], oa[k], n); ! 345: #endif ! 346: if (n > 0) { ! 347: if (i-n == SP->des_top_mgn+1) { ! 348: _scrollf(n); ! 349: } else { ! 350: _pos(i-n-1, 0); ! 351: _dellines(n); ! 352: } ! 353: idl_offset += n; ! 354: ndel += n; ! 355: for (j=i-n; j<=last-n; j++) { ! 356: if (oa[j] > 0 && na[oa[j]] > 0) ! 357: na[oa[j]] -= n; ! 358: _line_free(SP->cur_body[j]); ! 359: SP->cur_body[j] = SP->cur_body[j+n]; ! 360: oa[j] = oa[j+n]; ! 361: } ! 362: for ( ; j<=last; j++) { ! 363: if (oa[j] > 0 && na[oa[j]] > 0) ! 364: na[oa[j]] -= n; ! 365: _line_free(SP->cur_body[j]); ! 366: SP->cur_body[j] = NULL; ! 367: oa[j] = -1; ! 368: } ! 369: i -= n; ! 370: } ! 371: k = i; ! 372: } ! 373: } ! 374: #ifdef DEBUG ! 375: if(outf) fprintf(outf, "\ni oa na After pass 9\n"); ! 376: for (i=first; i<=last; i++) ! 377: if(outf) fprintf(outf, "%d %d %d\n", i, oa[i], na[i]); ! 378: if(outf) fprintf(outf, "\n"); ! 379: #endif ! 380: ! 381: /* Half way through - check for typeahead */ ! 382: _chk_typeahead(); ! 383: if (idl_offset == 0 && InputPending) { ! 384: #ifdef DEBUG ! 385: if (outf) fprintf(outf, "InputPending %d, aborted after dellines\n", InputPending); ! 386: #endif ! 387: return; ! 388: } ! 389: ! 390: /* for pass 10, j is the next line above i that will be used */ ! 391: for (j=first; na[j] <= 0; j++) ! 392: ; ! 393: ! 394: /* Pass 10: insert and fix remaining lines */ ! 395: for (i=first; i<=last; i++) { ! 396: if (j <= i) ! 397: for (j++; na[j] <= 0; j++) ! 398: ; ! 399: #ifdef DEBUG ! 400: if(outf) fprintf(outf, "i %d, j %d, na[i] %d, na[j] %d\n", ! 401: i, j, na[i], na[j]); ! 402: if (na[i] > 0 && na[i] != i) ! 403: if(outf) fprintf(outf, "OOPS: na[%d] is %d\n", i, na[i]); ! 404: #endif ! 405: /* There are two cases: na[i] < 0 or na[i] == i */ ! 406: if (na[i] < 0) { ! 407: /* ! 408: * This line must be fixed from scratch. First ! 409: * check to see if the line physically there is ! 410: * going to be used later, if so, move it down. ! 411: */ ! 412: if (na[j]==i || ndel+i>last && last<SP->des_bot_mgn+1) { ! 413: _pos(i-1, 0); ! 414: n = j - i; ! 415: idl_offset -= n; ! 416: ndel -= n; ! 417: _inslines(n); ! 418: _chk_typeahead(); ! 419: if (idl_offset == 0 && InputPending) { ! 420: #ifdef DEBUG ! 421: if (outf) fprintf(outf, "InputPending %d, aborted after dellines\n", InputPending); ! 422: #endif ! 423: return; ! 424: } ! 425: for (k=last; k>=j; k--) { ! 426: if (na[k] > 0) ! 427: na[k] += n; ! 428: _line_free(SP->cur_body[k]); ! 429: SP->cur_body[k] = SP->cur_body[k-n]; ! 430: oa[k] = oa[k-n]; ! 431: } ! 432: for ( ; k>=i; k--) { ! 433: if (na[k] > 0) ! 434: na[k] += n; ! 435: _line_free(SP->cur_body[k]); ! 436: SP->cur_body[k] = NULL; ! 437: oa[k] = 0; ! 438: } ! 439: } ! 440: } ! 441: /* Now transform line i to new line j */ ! 442: if (!InputPending) { ! 443: _id_char (SP->cur_body[i], SP->std_body[i], i-1); ! 444: if (SP->cur_body[i] != SP->std_body[i]) ! 445: _line_free (SP->cur_body[i]); ! 446: SP->cur_body[i] = SP->std_body[i]; ! 447: } ! 448: } ! 449: #ifdef DEBUG ! 450: if(outf) fprintf(outf, "\ni oa na After pass 10: _id_line completed\n"); ! 451: for (i=first; i<=last; i++) ! 452: if(outf) fprintf(outf, "%d %d %d\n", i, oa[i], na[i]); ! 453: if(outf) fprintf(outf, "\n"); ! 454: #endif ! 455: } ! 456: ! 457: int ! 458: _getst(val, symtab) ! 459: register struct st *symtab; ! 460: { ! 461: register int i; ! 462: register int h; ! 463: register int hopcount = 256; ! 464: ! 465: i = val & 0377; ! 466: while ((h=symtab[i].hash) && h != val) { ! 467: if (++i >= 256) ! 468: i = 0; ! 469: if (--hopcount <= 0) { ! 470: _ec_quit("Hash table full in dispcalc", ""); ! 471: } ! 472: } ! 473: symtab[i].hash = val; ! 474: #ifdef LONGDEBUG ! 475: if(outf) fprintf(outf, "_getst, val %d, init slot %d, return %d\n", ! 476: val, val & 0377, i); ! 477: #endif ! 478: return i; ! 479: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.