1 /****************************************************************************
2 * Copyright (c) 1998-2002,2005 Free Software Foundation, Inc. *
3 * *
4 * Permission is hereby granted, free of charge, to any person obtaining a *
5 * copy of this software and associated documentation files (the *
6 * "Software"), to deal in the Software without restriction, including *
7 * without limitation the rights to use, copy, modify, merge, publish, *
8 * distribute, distribute with modifications, sublicense, and/or sell *
9 * copies of the Software, and to permit persons to whom the Software is *
10 * furnished to do so, subject to the following conditions: *
11 * *
12 * The above copyright notice and this permission notice shall be included *
13 * in all copies or substantial portions of the Software. *
14 * *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS *
16 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF *
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. *
18 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, *
19 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR *
20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR *
21 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. *
22 * *
23 * Except as contained in this notice, the name(s) of the above copyright *
24 * holders shall not be used in advertising or otherwise to promote the *
25 * sale, use or other dealings in this Software without prior written *
26 * authorization. *
27 ****************************************************************************/
28
29 /****************************************************************************
30 * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 *
31 * and: Eric S. Raymond <esr@snark.thyrsus.com> *
32 ****************************************************************************/
33
34 /******************************************************************************
35
36 NAME
37 hashmap.c -- fill in scramble vector based on text hashes
38
39 SYNOPSIS
40 void _nc_hash_map(void)
41
42 DESCRIPTION:
43 This code attempts to recognize pairs of old and new lines in the physical
44 and virtual screens. When a line pair is recognized, the old line index is
45 placed in the oldindex member of the virtual screen line, to be used by the
46 vertical-motion optimizer portion of the update logic (see hardscroll.c).
47
48 Line pairs are recognized by applying a modified Heckel's algorithm,
49 sped up by hashing. If a line hash is unique in both screens, those
50 lines must be a pair. Then if the lines just before or after the pair
51 are the same or similar, they are a pair too.
52
53 We don't worry about false pairs produced by hash collisions, on the
54 assumption that such cases are rare and will only make the latter stages
55 of update less efficient, not introduce errors.
56
57 HOW TO TEST THIS:
58
59 Use the following production:
60
61 hashmap: hashmap.c
62 $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
63
64 AUTHOR
65 Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
66 Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997
67
68 *****************************************************************************/
69
70 #include <curses.priv.h>
71 #include <term.h> /* for back_color_erase */
72
73 MODULE_ID("$Id: hashmap.c,v 1.47 2005/01/29 21:27:58 tom Exp $")
74
75 #ifdef HASHDEBUG
76
77 # define _tracef printf
78 # undef TR
79 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
80 # undef screen_lines
81 # define screen_lines MAXLINES
82 # define TEXTWIDTH 1
83 int oldnums[MAXLINES], reallines[MAXLINES];
84 static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH];
85 # define OLDNUM(n) oldnums[n]
86 # define OLDTEXT(n) oldtext[n]
87 # define NEWTEXT(m) newtext[m]
88 # define PENDING(n) 1
89
90 #else /* !HASHDEBUG */
91
92 # define OLDNUM(n) _nc_oldnums[n]
93 # define OLDTEXT(n) curscr->_line[n].text
94 # define NEWTEXT(m) newscr->_line[m].text
95 # define TEXTWIDTH (curscr->_maxx+1)
96 # define PENDING(n) (newscr->_line[n].firstchar != _NOCHANGE)
97
98 #endif /* !HASHDEBUG */
99
100 #define oldhash (SP->oldhash)
101 #define newhash (SP->newhash)
102 #define hashtab (SP->hashtab)
103 #define lines_alloc (SP->hashtab_len)
104
105 #if USE_WIDEC_SUPPORT
106 #define HASH_VAL(ch) (ch.chars[0])
107 #else
108 #define HASH_VAL(ch) (ch)
109 #endif
110
111 static inline unsigned long
hash(NCURSES_CH_T * text)112 hash(NCURSES_CH_T * text)
113 {
114 int i;
115 NCURSES_CH_T ch;
116 unsigned long result = 0;
117 for (i = TEXTWIDTH; i > 0; i--) {
118 ch = *text++;
119 result += (result << 5) + HASH_VAL(ch);
120 }
121 return result;
122 }
123
124 /* approximate update cost */
125 static int
update_cost(NCURSES_CH_T * from,NCURSES_CH_T * to)126 update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to)
127 {
128 int cost = 0;
129 int i;
130
131 for (i = TEXTWIDTH; i > 0; i--)
132 if (!(CharEq(*from++, *to++)))
133 cost++;
134
135 return cost;
136 }
137
138 static int
update_cost_from_blank(NCURSES_CH_T * to)139 update_cost_from_blank(NCURSES_CH_T * to)
140 {
141 int cost = 0;
142 int i;
143 NCURSES_CH_T blank = NewChar2(BLANK_TEXT, BLANK_ATTR);
144
145 if (back_color_erase)
146 SetPair(blank, GetPair(stdscr->_nc_bkgd));
147
148 for (i = TEXTWIDTH; i > 0; i--)
149 if (!(CharEq(blank, *to++)))
150 cost++;
151
152 return cost;
153 }
154
155 /*
156 * Returns true when moving line 'from' to line 'to' seems to be cost
157 * effective. 'blank' indicates whether the line 'to' would become blank.
158 */
159 static inline bool
cost_effective(const int from,const int to,const bool blank)160 cost_effective(const int from, const int to, const bool blank)
161 {
162 int new_from;
163
164 if (from == to)
165 return FALSE;
166
167 new_from = OLDNUM(from);
168 if (new_from == _NEWINDEX)
169 new_from = from;
170
171 /*
172 * On the left side of >= is the cost before moving;
173 * on the right side -- cost after moving.
174 */
175 return (((blank ? update_cost_from_blank(NEWTEXT(to))
176 : update_cost(OLDTEXT(to), NEWTEXT(to)))
177 + update_cost(OLDTEXT(new_from), NEWTEXT(from)))
178 >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from))
179 : update_cost(OLDTEXT(new_from), NEWTEXT(from)))
180 + update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE;
181 }
182
183 static void
grow_hunks(void)184 grow_hunks(void)
185 {
186 int start, end, shift;
187 int back_limit, forward_limit; /* limits for cells to fill */
188 int back_ref_limit, forward_ref_limit; /* limits for refrences */
189 int i;
190 int next_hunk;
191
192 /*
193 * This is tricky part. We have unique pairs to use as anchors.
194 * Use these to deduce the presence of spans of identical lines.
195 */
196 back_limit = 0;
197 back_ref_limit = 0;
198
199 i = 0;
200 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
201 i++;
202 for (; i < screen_lines; i = next_hunk) {
203 start = i;
204 shift = OLDNUM(i) - i;
205
206 /* get forward limit */
207 i = start + 1;
208 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
209 == shift)
210 i++;
211 end = i;
212 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
213 i++;
214 next_hunk = i;
215 forward_limit = i;
216 if (i >= screen_lines || OLDNUM(i) >= i)
217 forward_ref_limit = i;
218 else
219 forward_ref_limit = OLDNUM(i);
220
221 i = start - 1;
222 /* grow back */
223 if (shift < 0)
224 back_limit = back_ref_limit + (-shift);
225 while (i >= back_limit) {
226 if (newhash[i] == oldhash[i + shift]
227 || cost_effective(i + shift, i, shift < 0)) {
228 OLDNUM(i) = i + shift;
229 TR(TRACE_UPDATE | TRACE_MOVE,
230 ("connected new line %d to old line %d (backward continuation)",
231 i, i + shift));
232 } else {
233 TR(TRACE_UPDATE | TRACE_MOVE,
234 ("not connecting new line %d to old line %d (backward continuation)",
235 i, i + shift));
236 break;
237 }
238 i--;
239 }
240
241 i = end;
242 /* grow forward */
243 if (shift > 0)
244 forward_limit = forward_ref_limit - shift;
245 while (i < forward_limit) {
246 if (newhash[i] == oldhash[i + shift]
247 || cost_effective(i + shift, i, shift > 0)) {
248 OLDNUM(i) = i + shift;
249 TR(TRACE_UPDATE | TRACE_MOVE,
250 ("connected new line %d to old line %d (forward continuation)",
251 i, i + shift));
252 } else {
253 TR(TRACE_UPDATE | TRACE_MOVE,
254 ("not connecting new line %d to old line %d (forward continuation)",
255 i, i + shift));
256 break;
257 }
258 i++;
259 }
260
261 back_ref_limit = back_limit = i;
262 if (shift > 0)
263 back_ref_limit += shift;
264 }
265 }
266
267 NCURSES_EXPORT(void)
_nc_hash_map(void)268 _nc_hash_map(void)
269 {
270 HASHMAP *sp;
271 register int i;
272 int start, shift, size;
273
274 if (screen_lines > lines_alloc) {
275 if (hashtab)
276 free(hashtab);
277 hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2);
278 if (!hashtab) {
279 if (oldhash) {
280 FreeAndNull(oldhash);
281 }
282 lines_alloc = 0;
283 return;
284 }
285 lines_alloc = screen_lines;
286 }
287
288 if (oldhash && newhash) {
289 /* re-hash only changed lines */
290 for (i = 0; i < screen_lines; i++) {
291 if (PENDING(i))
292 newhash[i] = hash(NEWTEXT(i));
293 }
294 } else {
295 /* re-hash all */
296 if (oldhash == 0)
297 oldhash = typeCalloc(unsigned long, (unsigned) screen_lines);
298 if (newhash == 0)
299 newhash = typeCalloc(unsigned long, (unsigned) screen_lines);
300 if (!oldhash || !newhash)
301 return; /* malloc failure */
302 for (i = 0; i < screen_lines; i++) {
303 newhash[i] = hash(NEWTEXT(i));
304 oldhash[i] = hash(OLDTEXT(i));
305 }
306 }
307
308 #ifdef HASH_VERIFY
309 for (i = 0; i < screen_lines; i++) {
310 if (newhash[i] != hash(NEWTEXT(i)))
311 fprintf(stderr, "error in newhash[%d]\n", i);
312 if (oldhash[i] != hash(OLDTEXT(i)))
313 fprintf(stderr, "error in oldhash[%d]\n", i);
314 }
315 #endif
316
317 /*
318 * Set up and count line-hash values.
319 */
320 memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2);
321 for (i = 0; i < screen_lines; i++) {
322 unsigned long hashval = oldhash[i];
323
324 for (sp = hashtab; sp->hashval; sp++)
325 if (sp->hashval == hashval)
326 break;
327 sp->hashval = hashval; /* in case this is a new entry */
328 sp->oldcount++;
329 sp->oldindex = i;
330 }
331 for (i = 0; i < screen_lines; i++) {
332 unsigned long hashval = newhash[i];
333
334 for (sp = hashtab; sp->hashval; sp++)
335 if (sp->hashval == hashval)
336 break;
337 sp->hashval = hashval; /* in case this is a new entry */
338 sp->newcount++;
339 sp->newindex = i;
340
341 OLDNUM(i) = _NEWINDEX; /* initialize old indices array */
342 }
343
344 /*
345 * Mark line pairs corresponding to unique hash pairs.
346 *
347 * We don't mark lines with offset 0, because it can make fail
348 * extending hunks by cost_effective. Otherwise, it does not
349 * have any side effects.
350 */
351 for (sp = hashtab; sp->hashval; sp++)
352 if (sp->oldcount == 1 && sp->newcount == 1
353 && sp->oldindex != sp->newindex) {
354 TR(TRACE_UPDATE | TRACE_MOVE,
355 ("new line %d is hash-identical to old line %d (unique)",
356 sp->newindex, sp->oldindex));
357 OLDNUM(sp->newindex) = sp->oldindex;
358 }
359
360 grow_hunks();
361
362 /*
363 * Eliminate bad or impossible shifts -- this includes removing
364 * those hunks which could not grow because of conflicts, as well
365 * those which are to be moved too far, they are likely to destroy
366 * more than carry.
367 */
368 for (i = 0; i < screen_lines;) {
369 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
370 i++;
371 if (i >= screen_lines)
372 break;
373 start = i;
374 shift = OLDNUM(i) - i;
375 i++;
376 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
377 == shift)
378 i++;
379 size = i - start;
380 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
381 while (start < i) {
382 OLDNUM(start) = _NEWINDEX;
383 start++;
384 }
385 }
386 }
387
388 /* After clearing invalid hunks, try grow the rest. */
389 grow_hunks();
390 }
391
392 NCURSES_EXPORT(void)
_nc_make_oldhash(int i)393 _nc_make_oldhash(int i)
394 {
395 if (oldhash)
396 oldhash[i] = hash(OLDTEXT(i));
397 }
398
399 NCURSES_EXPORT(void)
_nc_scroll_oldhash(int n,int top,int bot)400 _nc_scroll_oldhash(int n, int top, int bot)
401 {
402 size_t size;
403 int i;
404
405 if (!oldhash)
406 return;
407
408 size = sizeof(*oldhash) * (bot - top + 1 - abs(n));
409 if (n > 0) {
410 memmove(oldhash + top, oldhash + top + n, size);
411 for (i = bot; i > bot - n; i--)
412 oldhash[i] = hash(OLDTEXT(i));
413 } else {
414 memmove(oldhash + top - n, oldhash + top, size);
415 for (i = top; i < top - n; i++)
416 oldhash[i] = hash(OLDTEXT(i));
417 }
418 }
419
420 #ifdef HASHDEBUG
421 static void
usage(void)422 usage(void)
423 {
424 static const char *table[] =
425 {
426 "hashmap test-driver",
427 "",
428 "# comment",
429 "l get initial line number vector",
430 "n use following letters as text of new lines",
431 "o use following letters as text of old lines",
432 "d dump state of test arrays",
433 "h apply hash mapper and see scroll optimization",
434 "? this message"
435 };
436 size_t n;
437 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
438 fprintf(stderr, "%s\n", table[n]);
439 }
440
441 int
main(int argc GCC_UNUSED,char * argv[]GCC_UNUSED)442 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
443 {
444 char line[BUFSIZ], *st;
445 int n;
446
447 SP = typeCalloc(SCREEN, 1);
448 for (n = 0; n < screen_lines; n++) {
449 reallines[n] = n;
450 oldnums[n] = _NEWINDEX;
451 oldtext[n][0] = newtext[n][0] = '.';
452 }
453
454 if (isatty(fileno(stdin)))
455 usage();
456
457 #ifdef TRACE
458 _nc_tracing = TRACE_MOVE;
459 #endif
460 for (;;) {
461 /* grab a test command */
462 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
463 exit(EXIT_SUCCESS);
464
465 switch (line[0]) {
466 case '#': /* comment */
467 (void) fputs(line, stderr);
468 break;
469
470 case 'l': /* get initial line number vector */
471 for (n = 0; n < screen_lines; n++) {
472 reallines[n] = n;
473 oldnums[n] = _NEWINDEX;
474 }
475 n = 0;
476 st = strtok(line, " ");
477 do {
478 oldnums[n++] = atoi(st);
479 } while
480 ((st = strtok((char *) NULL, " ")) != 0);
481 break;
482
483 case 'n': /* use following letters as text of new lines */
484 for (n = 0; n < screen_lines; n++)
485 newtext[n][0] = '.';
486 for (n = 0; n < screen_lines; n++)
487 if (line[n + 1] == '\n')
488 break;
489 else
490 newtext[n][0] = line[n + 1];
491 break;
492
493 case 'o': /* use following letters as text of old lines */
494 for (n = 0; n < screen_lines; n++)
495 oldtext[n][0] = '.';
496 for (n = 0; n < screen_lines; n++)
497 if (line[n + 1] == '\n')
498 break;
499 else
500 oldtext[n][0] = line[n + 1];
501 break;
502
503 case 'd': /* dump state of test arrays */
504 #ifdef TRACE
505 _nc_linedump();
506 #endif
507 (void) fputs("Old lines: [", stdout);
508 for (n = 0; n < screen_lines; n++)
509 putchar(oldtext[n][0]);
510 putchar(']');
511 putchar('\n');
512 (void) fputs("New lines: [", stdout);
513 for (n = 0; n < screen_lines; n++)
514 putchar(newtext[n][0]);
515 putchar(']');
516 putchar('\n');
517 break;
518
519 case 'h': /* apply hash mapper and see scroll optimization */
520 _nc_hash_map();
521 (void) fputs("Result:\n", stderr);
522 #ifdef TRACE
523 _nc_linedump();
524 #endif
525 _nc_scroll_optimize();
526 (void) fputs("Done.\n", stderr);
527 break;
528 case '?':
529 usage();
530 break;
531 }
532 }
533 return EXIT_SUCCESS;
534 }
535
536 #endif /* HASHDEBUG */
537
538 /* hashmap.c ends here */
539