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