1 /****************************************************************************
2 * Copyright (c) 1998-2010,2011 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 <[email protected]> 1992,1995 *
31 * and: Eric S. Raymond <[email protected]> *
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 <[email protected]>, May 1996
66 Bug fixes and improvements by Alexander V. Lukyanov <[email protected]>, 1997
67
68 *****************************************************************************/
69
70 #include <curses.priv.h>
71
72 #ifndef CUR
73 #define CUR SP_TERMTYPE
74 #endif
75
76 MODULE_ID("$Id: hashmap.c,v 1.63 2011/10/22 16:34:50 tom Exp $")
77
78 #ifdef HASHDEBUG
79
80 # define _tracef printf
81 # undef TR
82 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
83 # undef screen_lines
84 # define screen_lines MAXLINES
85 # define TEXTWIDTH 1
86 int oldnums[MAXLINES], reallines[MAXLINES];
87 static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH];
88 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH];
89 # define OLDNUM(sp,n) oldnums[n]
90 # define OLDTEXT(sp,n) oldtext[n]
91 # define NEWTEXT(sp,m) newtext[m]
92 # define PENDING(sp,n) 1
93
94 #else /* !HASHDEBUG */
95
96 # define OLDNUM(sp,n) (sp)->_oldnum_list[n]
97 # define OLDTEXT(sp,n) CurScreen(sp)->_line[n].text
98 # define NEWTEXT(sp,m) NewScreen(sp)->_line[m].text
99 # define TEXTWIDTH(sp) (CurScreen(sp)->_maxx + 1)
100 # define PENDING(sp,n) (NewScreen(sp)->_line[n].firstchar != _NOCHANGE)
101
102 #endif /* !HASHDEBUG */
103
104 #define oldhash(sp) ((sp)->oldhash)
105 #define newhash(sp) ((sp)->newhash)
106 #define hashtab(sp) ((sp)->hashtab)
107 #define lines_alloc(sp) ((sp)->hashtab_len)
108
109 #if USE_WIDEC_SUPPORT
110 #define HASH_VAL(ch) (ch.chars[0])
111 #else
112 #define HASH_VAL(ch) (ch)
113 #endif
114
115 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
116
117 static NCURSES_INLINE unsigned long
hash(SCREEN * sp,NCURSES_CH_T * text)118 hash(SCREEN *sp, NCURSES_CH_T * text)
119 {
120 int i;
121 NCURSES_CH_T ch;
122 unsigned long result = 0;
123 for (i = TEXTWIDTH(sp); i > 0; i--) {
124 ch = *text++;
125 result += (result << 5) + (unsigned long) HASH_VAL(ch);
126 }
127 return result;
128 }
129
130 /* approximate update cost */
131 static int
update_cost(SCREEN * sp,NCURSES_CH_T * from,NCURSES_CH_T * to)132 update_cost(SCREEN *sp, NCURSES_CH_T * from, NCURSES_CH_T * to)
133 {
134 int cost = 0;
135 int i;
136
137 for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
138 if (!(CharEq(*from, *to)))
139 cost++;
140
141 return cost;
142 }
143
144 static int
update_cost_from_blank(SCREEN * sp,NCURSES_CH_T * to)145 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T * to)
146 {
147 int cost = 0;
148 int i;
149 NCURSES_CH_T blank = blankchar;
150
151 if (back_color_erase)
152 SetPair(blank, GetPair(stdscr->_nc_bkgd));
153
154 for (i = TEXTWIDTH(sp); i > 0; i--, to++)
155 if (!(CharEq(blank, *to)))
156 cost++;
157
158 return cost;
159 }
160
161 /*
162 * Returns true when moving line 'from' to line 'to' seems to be cost
163 * effective. 'blank' indicates whether the line 'to' would become blank.
164 */
165 static NCURSES_INLINE bool
cost_effective(SCREEN * sp,const int from,const int to,const int blank)166 cost_effective(SCREEN *sp, const int from, const int to, const int blank)
167 {
168 int new_from;
169
170 if (from == to)
171 return FALSE;
172
173 new_from = OLDNUM(sp, from);
174 if (new_from == _NEWINDEX)
175 new_from = from;
176
177 /*
178 * On the left side of >= is the cost before moving;
179 * on the right side -- cost after moving.
180 */
181 return (((blank ? update_cost_from_blank(sp, NEWTEXT(sp, to))
182 : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to)))
183 + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
184 >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from))
185 : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
186 + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to))))
187 ? TRUE : FALSE;
188 }
189
190 static void
grow_hunks(SCREEN * sp)191 grow_hunks(SCREEN *sp)
192 {
193 int start, end, shift;
194 int back_limit, forward_limit; /* limits for cells to fill */
195 int back_ref_limit, forward_ref_limit; /* limits for refrences */
196 int i;
197 int next_hunk;
198
199 /*
200 * This is tricky part. We have unique pairs to use as anchors.
201 * Use these to deduce the presence of spans of identical lines.
202 */
203 back_limit = 0;
204 back_ref_limit = 0;
205
206 i = 0;
207 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
208 i++;
209 for (; i < screen_lines(sp); i = next_hunk) {
210 start = i;
211 shift = OLDNUM(sp, i) - i;
212
213 /* get forward limit */
214 i = start + 1;
215 while (i < screen_lines(sp)
216 && OLDNUM(sp, i) != _NEWINDEX
217 && OLDNUM(sp, i) - i == shift)
218 i++;
219 end = i;
220 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
221 i++;
222 next_hunk = i;
223 forward_limit = i;
224 if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
225 forward_ref_limit = i;
226 else
227 forward_ref_limit = OLDNUM(sp, i);
228
229 i = start - 1;
230 /* grow back */
231 if (shift < 0)
232 back_limit = back_ref_limit + (-shift);
233 while (i >= back_limit) {
234 if (newhash(sp)[i] == oldhash(sp)[i + shift]
235 || cost_effective(sp, i + shift, i, shift < 0)) {
236 OLDNUM(sp, i) = i + shift;
237 TR(TRACE_UPDATE | TRACE_MOVE,
238 ("connected new line %d to old line %d (backward continuation)",
239 i, i + shift));
240 } else {
241 TR(TRACE_UPDATE | TRACE_MOVE,
242 ("not connecting new line %d to old line %d (backward continuation)",
243 i, i + shift));
244 break;
245 }
246 i--;
247 }
248
249 i = end;
250 /* grow forward */
251 if (shift > 0)
252 forward_limit = forward_ref_limit - shift;
253 while (i < forward_limit) {
254 if (newhash(sp)[i] == oldhash(sp)[i + shift]
255 || cost_effective(sp, i + shift, i, shift > 0)) {
256 OLDNUM(sp, i) = i + shift;
257 TR(TRACE_UPDATE | TRACE_MOVE,
258 ("connected new line %d to old line %d (forward continuation)",
259 i, i + shift));
260 } else {
261 TR(TRACE_UPDATE | TRACE_MOVE,
262 ("not connecting new line %d to old line %d (forward continuation)",
263 i, i + shift));
264 break;
265 }
266 i++;
267 }
268
269 back_ref_limit = back_limit = i;
270 if (shift > 0)
271 back_ref_limit += shift;
272 }
273 }
274
275 NCURSES_EXPORT(void)
NCURSES_SP_NAME(_nc_hash_map)276 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
277 {
278 HASHMAP *hsp;
279 register int i;
280 int start, shift, size;
281
282 if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
283 if (hashtab(SP_PARM))
284 free(hashtab(SP_PARM));
285 hashtab(SP_PARM) = typeMalloc(HASHMAP,
286 ((size_t) screen_lines(SP_PARM) + 1) * 2);
287 if (!hashtab(SP_PARM)) {
288 if (oldhash(SP_PARM)) {
289 FreeAndNull(oldhash(SP_PARM));
290 }
291 lines_alloc(SP_PARM) = 0;
292 return;
293 }
294 lines_alloc(SP_PARM) = screen_lines(SP_PARM);
295 }
296
297 if (oldhash(SP_PARM) && newhash(SP_PARM)) {
298 /* re-hash only changed lines */
299 for (i = 0; i < screen_lines(SP_PARM); i++) {
300 if (PENDING(SP_PARM, i))
301 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
302 }
303 } else {
304 /* re-hash all */
305 if (oldhash(SP_PARM) == 0)
306 oldhash(SP_PARM) = typeCalloc(unsigned long,
307 (size_t) screen_lines(SP_PARM));
308 if (newhash(SP_PARM) == 0)
309 newhash(SP_PARM) = typeCalloc(unsigned long,
310 (size_t) screen_lines(SP_PARM));
311 if (!oldhash(SP_PARM) || !newhash(SP_PARM))
312 return; /* malloc failure */
313 for (i = 0; i < screen_lines(SP_PARM); i++) {
314 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
315 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
316 }
317 }
318
319 #ifdef HASH_VERIFY
320 for (i = 0; i < screen_lines(SP_PARM); i++) {
321 if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
322 fprintf(stderr, "error in newhash[%d]\n", i);
323 if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
324 fprintf(stderr, "error in oldhash[%d]\n", i);
325 }
326 #endif
327
328 /*
329 * Set up and count line-hash values.
330 */
331 memset(hashtab(SP_PARM), '\0',
332 sizeof(*(hashtab(SP_PARM)))
333 * ((size_t) screen_lines(SP_PARM) + 1) * 2);
334 for (i = 0; i < screen_lines(SP_PARM); i++) {
335 unsigned long hashval = oldhash(SP_PARM)[i];
336
337 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
338 if (hsp->hashval == hashval)
339 break;
340 hsp->hashval = hashval; /* in case this is a new entry */
341 hsp->oldcount++;
342 hsp->oldindex = i;
343 }
344 for (i = 0; i < screen_lines(SP_PARM); i++) {
345 unsigned long hashval = newhash(SP_PARM)[i];
346
347 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
348 if (hsp->hashval == hashval)
349 break;
350 hsp->hashval = hashval; /* in case this is a new entry */
351 hsp->newcount++;
352 hsp->newindex = i;
353
354 OLDNUM(SP_PARM, i) = _NEWINDEX; /* initialize old indices array */
355 }
356
357 /*
358 * Mark line pairs corresponding to unique hash pairs.
359 *
360 * We don't mark lines with offset 0, because it can make fail
361 * extending hunks by cost_effective. Otherwise, it does not
362 * have any side effects.
363 */
364 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
365 if (hsp->oldcount == 1 && hsp->newcount == 1
366 && hsp->oldindex != hsp->newindex) {
367 TR(TRACE_UPDATE | TRACE_MOVE,
368 ("new line %d is hash-identical to old line %d (unique)",
369 hsp->newindex, hsp->oldindex));
370 OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
371 }
372
373 grow_hunks(SP_PARM);
374
375 /*
376 * Eliminate bad or impossible shifts -- this includes removing
377 * those hunks which could not grow because of conflicts, as well
378 * those which are to be moved too far, they are likely to destroy
379 * more than carry.
380 */
381 for (i = 0; i < screen_lines(SP_PARM);) {
382 while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
383 i++;
384 if (i >= screen_lines(SP_PARM))
385 break;
386 start = i;
387 shift = OLDNUM(SP_PARM, i) - i;
388 i++;
389 while (i < screen_lines(SP_PARM)
390 && OLDNUM(SP_PARM, i) != _NEWINDEX
391 && OLDNUM(SP_PARM, i) - i == shift)
392 i++;
393 size = i - start;
394 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
395 while (start < i) {
396 OLDNUM(SP_PARM, start) = _NEWINDEX;
397 start++;
398 }
399 }
400 }
401
402 /* After clearing invalid hunks, try grow the rest. */
403 grow_hunks(SP_PARM);
404 }
405
406 #if NCURSES_SP_FUNCS
407 NCURSES_EXPORT(void)
_nc_hash_map(void)408 _nc_hash_map(void)
409 {
410 NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
411 }
412 #endif
413
414 NCURSES_EXPORT(void)
NCURSES_SP_NAME(_nc_make_oldhash)415 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
416 {
417 if (oldhash(SP_PARM))
418 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
419 }
420
421 #if NCURSES_SP_FUNCS
422 NCURSES_EXPORT(void)
_nc_make_oldhash(int i)423 _nc_make_oldhash(int i)
424 {
425 NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
426 }
427 #endif
428
429 NCURSES_EXPORT(void)
NCURSES_SP_NAME(_nc_scroll_oldhash)430 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
431 {
432 size_t size;
433 int i;
434
435 if (!oldhash(SP_PARM))
436 return;
437
438 size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
439 if (n > 0) {
440 memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
441 for (i = bot; i > bot - n; i--)
442 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
443 } else {
444 memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
445 for (i = top; i < top - n; i++)
446 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
447 }
448 }
449
450 #if NCURSES_SP_FUNCS
451 NCURSES_EXPORT(void)
_nc_scroll_oldhash(int n,int top,int bot)452 _nc_scroll_oldhash(int n, int top, int bot)
453 {
454 NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
455 }
456 #endif
457
458 #ifdef HASHDEBUG
459 static void
usage(void)460 usage(void)
461 {
462 static const char *table[] =
463 {
464 "hashmap test-driver",
465 "",
466 "# comment",
467 "l get initial line number vector",
468 "n use following letters as text of new lines",
469 "o use following letters as text of old lines",
470 "d dump state of test arrays",
471 "h apply hash mapper and see scroll optimization",
472 "? this message"
473 };
474 size_t n;
475 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
476 fprintf(stderr, "%s\n", table[n]);
477 }
478
479 int
main(int argc GCC_UNUSED,char * argv[]GCC_UNUSED)480 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
481 {
482 char line[BUFSIZ], *st;
483 int n;
484
485 if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
486 return EXIT_FAILURE;
487 (void) _nc_alloc_screen();
488
489 for (n = 0; n < screen_lines; n++) {
490 reallines[n] = n;
491 oldnums[n] = _NEWINDEX;
492 CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
493 }
494
495 if (isatty(fileno(stdin)))
496 usage();
497
498 #ifdef TRACE
499 _nc_tracing = TRACE_MOVE;
500 #endif
501 for (;;) {
502 /* grab a test command */
503 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
504 break;
505
506 switch (line[0]) {
507 case '#': /* comment */
508 (void) fputs(line, stderr);
509 break;
510
511 case 'l': /* get initial line number vector */
512 for (n = 0; n < screen_lines; n++) {
513 reallines[n] = n;
514 oldnums[n] = _NEWINDEX;
515 }
516 n = 0;
517 st = strtok(line, " ");
518 do {
519 oldnums[n++] = atoi(st);
520 } while
521 ((st = strtok((char *) NULL, " ")) != 0);
522 break;
523
524 case 'n': /* use following letters as text of new lines */
525 for (n = 0; n < screen_lines; n++)
526 CharOf(newtext[n][0]) = '.';
527 for (n = 0; n < screen_lines; n++)
528 if (line[n + 1] == '\n')
529 break;
530 else
531 CharOf(newtext[n][0]) = line[n + 1];
532 break;
533
534 case 'o': /* use following letters as text of old lines */
535 for (n = 0; n < screen_lines; n++)
536 CharOf(oldtext[n][0]) = '.';
537 for (n = 0; n < screen_lines; n++)
538 if (line[n + 1] == '\n')
539 break;
540 else
541 CharOf(oldtext[n][0]) = line[n + 1];
542 break;
543
544 case 'd': /* dump state of test arrays */
545 #ifdef TRACE
546 _nc_linedump();
547 #endif
548 (void) fputs("Old lines: [", stdout);
549 for (n = 0; n < screen_lines; n++)
550 putchar(CharOf(oldtext[n][0]));
551 putchar(']');
552 putchar('\n');
553 (void) fputs("New lines: [", stdout);
554 for (n = 0; n < screen_lines; n++)
555 putchar(CharOf(newtext[n][0]));
556 putchar(']');
557 putchar('\n');
558 break;
559
560 case 'h': /* apply hash mapper and see scroll optimization */
561 _nc_hash_map();
562 (void) fputs("Result:\n", stderr);
563 #ifdef TRACE
564 _nc_linedump();
565 #endif
566 _nc_scroll_optimize();
567 (void) fputs("Done.\n", stderr);
568 break;
569 default:
570 case '?':
571 usage();
572 break;
573 }
574 }
575 #if NO_LEAKS
576 _nc_free_and_exit(EXIT_SUCCESS);
577 #else
578 return EXIT_SUCCESS;
579 #endif
580 }
581
582 #endif /* HASHDEBUG */
583
584 /* hashmap.c ends here */
585