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