1 /****************************************************************************
2 * Copyright 2019-2024,2025 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.75 2025/07/26 19:48:34 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,const NCURSES_CH_T * text)123 hash(SCREEN *sp, const NCURSES_CH_T *text)
124 {
125 int i;
126 unsigned long result = 0;
127 (void) sp;
128
129 for (i = TEXTWIDTH(sp); i > 0; i--) {
130 NCURSES_CH_T ch = *text++;
131 result += (result << 5) + (unsigned long) HASH_VAL(ch);
132 }
133 return result;
134 }
135
136 /* approximate update cost */
137 static int
update_cost(SCREEN * sp,NCURSES_CH_T * from,NCURSES_CH_T * to)138 update_cost(SCREEN *sp, NCURSES_CH_T *from, NCURSES_CH_T *to)
139 {
140 int cost = 0;
141 int i;
142 (void) sp;
143
144 for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
145 if (!(CharEq(*from, *to)))
146 cost++;
147
148 return cost;
149 }
150
151 static int
update_cost_from_blank(SCREEN * sp,NCURSES_CH_T * to)152 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T *to)
153 {
154 int cost = 0;
155 int i;
156 NCURSES_CH_T blank = blankchar;
157 (void) sp;
158
159 if (back_color_erase)
160 SetPair(blank, GetPair(stdscr->_nc_bkgd));
161
162 for (i = TEXTWIDTH(sp); i > 0; i--, to++)
163 if (!(CharEq(blank, *to)))
164 cost++;
165
166 return cost;
167 }
168
169 /*
170 * Returns true when moving line 'from' to line 'to' seems to be cost
171 * effective. 'blank' indicates whether the line 'to' would become blank.
172 */
173 static NCURSES_INLINE bool
cost_effective(SCREEN * sp,const int from,const int to,const int blank)174 cost_effective(SCREEN *sp, const int from, const int to, const int blank)
175 {
176 int new_from;
177
178 if (from == to)
179 return FALSE;
180
181 new_from = OLDNUM(sp, from);
182 if (new_from == _NEWINDEX)
183 new_from = from;
184
185 /*
186 * On the left side of >= is the cost before moving;
187 * on the right side -- cost after moving.
188 */
189 return (((blank ? update_cost_from_blank(sp, NEWTEXT(sp, to))
190 : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to)))
191 + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
192 >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from))
193 : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
194 + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to))))
195 ? TRUE : FALSE;
196 }
197
198 static void
grow_hunks(SCREEN * sp)199 grow_hunks(SCREEN *sp)
200 {
201 int back_limit; /* limits for cells to fill */
202 int back_ref_limit; /* limit for references */
203 int i;
204 int next_hunk;
205
206 /*
207 * This is tricky part. We have unique pairs to use as anchors.
208 * Use these to deduce the presence of spans of identical lines.
209 */
210 back_limit = 0;
211 back_ref_limit = 0;
212
213 i = 0;
214 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
215 i++;
216 for (; i < screen_lines(sp); i = next_hunk) {
217 int forward_limit;
218 int forward_ref_limit;
219 int end;
220 int start = i;
221 int shift = OLDNUM(sp, i) - i;
222
223 /* get forward limit */
224 i = start + 1;
225 while (i < screen_lines(sp)
226 && OLDNUM(sp, i) != _NEWINDEX
227 && OLDNUM(sp, i) - i == shift)
228 i++;
229 end = i;
230 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
231 i++;
232 next_hunk = i;
233 forward_limit = i;
234 if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
235 forward_ref_limit = i;
236 else
237 forward_ref_limit = OLDNUM(sp, i);
238
239 i = start - 1;
240 /* grow back */
241 if (shift < 0)
242 back_limit = back_ref_limit + (-shift);
243 while (i >= back_limit) {
244 if (newhash(sp)[i] == oldhash(sp)[i + shift]
245 || cost_effective(sp, i + shift, i, shift < 0)) {
246 OLDNUM(sp, i) = i + shift;
247 TR(TRACE_UPDATE | TRACE_MOVE,
248 ("connected new line %d to old line %d (backward continuation)",
249 i, i + shift));
250 } else {
251 TR(TRACE_UPDATE | TRACE_MOVE,
252 ("not connecting new line %d to old line %d (backward continuation)",
253 i, i + shift));
254 break;
255 }
256 i--;
257 }
258
259 i = end;
260 /* grow forward */
261 if (shift > 0)
262 forward_limit = forward_ref_limit - shift;
263 while (i < forward_limit) {
264 if (newhash(sp)[i] == oldhash(sp)[i + shift]
265 || cost_effective(sp, i + shift, i, shift > 0)) {
266 OLDNUM(sp, i) = i + shift;
267 TR(TRACE_UPDATE | TRACE_MOVE,
268 ("connected new line %d to old line %d (forward continuation)",
269 i, i + shift));
270 } else {
271 TR(TRACE_UPDATE | TRACE_MOVE,
272 ("not connecting new line %d to old line %d (forward continuation)",
273 i, i + shift));
274 break;
275 }
276 i++;
277 }
278
279 back_ref_limit = back_limit = i;
280 if (shift > 0)
281 back_ref_limit += shift;
282 }
283 }
284
285 NCURSES_EXPORT(void)
NCURSES_SP_NAME(_nc_hash_map)286 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
287 {
288 HASHMAP *hsp;
289 register int i;
290
291 if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
292 if (hashtab(SP_PARM))
293 free(hashtab(SP_PARM));
294 hashtab(SP_PARM) = typeMalloc(HASHMAP,
295 ((size_t) screen_lines(SP_PARM) + 1) * 2);
296 if (!hashtab(SP_PARM)) {
297 if (oldhash(SP_PARM)) {
298 FreeAndNull(oldhash(SP_PARM));
299 }
300 lines_alloc(SP_PARM) = 0;
301 return;
302 }
303 lines_alloc(SP_PARM) = screen_lines(SP_PARM);
304 }
305
306 if (oldhash(SP_PARM) && newhash(SP_PARM)) {
307 /* re-hash only changed lines */
308 for (i = 0; i < screen_lines(SP_PARM); i++) {
309 if (PENDING(SP_PARM, i))
310 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
311 }
312 } else {
313 /* re-hash all */
314 if (oldhash(SP_PARM) == NULL)
315 oldhash(SP_PARM) = typeCalloc(unsigned long,
316 (size_t) screen_lines(SP_PARM));
317 if (newhash(SP_PARM) == NULL)
318 newhash(SP_PARM) = typeCalloc(unsigned long,
319 (size_t) screen_lines(SP_PARM));
320 if (!oldhash(SP_PARM) || !newhash(SP_PARM)) {
321 FreeAndNull(oldhash(SP_PARM));
322 FreeAndNull(newhash(SP_PARM));
323 return; /* malloc failure */
324 }
325 for (i = 0; i < screen_lines(SP_PARM); i++) {
326 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
327 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
328 }
329 }
330
331 #ifdef HASH_VERIFY
332 for (i = 0; i < screen_lines(SP_PARM); i++) {
333 if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
334 fprintf(stderr, "error in newhash[%d]\n", i);
335 if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
336 fprintf(stderr, "error in oldhash[%d]\n", i);
337 }
338 #endif
339
340 /*
341 * Set up and count line-hash values.
342 */
343 memset(hashtab(SP_PARM), '\0',
344 sizeof(*(hashtab(SP_PARM)))
345 * ((size_t) screen_lines(SP_PARM) + 1) * 2);
346 for (i = 0; i < screen_lines(SP_PARM); i++) {
347 unsigned long hashval = oldhash(SP_PARM)[i];
348
349 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
350 if (hsp->hashval == hashval)
351 break;
352 hsp->hashval = hashval; /* in case this is a new entry */
353 hsp->oldcount++;
354 hsp->oldindex = i;
355 }
356 for (i = 0; i < screen_lines(SP_PARM); i++) {
357 unsigned long hashval = newhash(SP_PARM)[i];
358
359 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
360 if (hsp->hashval == hashval)
361 break;
362 hsp->hashval = hashval; /* in case this is a new entry */
363 hsp->newcount++;
364 hsp->newindex = i;
365
366 OLDNUM(SP_PARM, i) = _NEWINDEX; /* initialize old indices array */
367 }
368
369 /*
370 * Mark line pairs corresponding to unique hash pairs.
371 *
372 * We don't mark lines with offset 0, because it can make fail
373 * extending hunks by cost_effective. Otherwise, it does not
374 * have any side effects.
375 */
376 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
377 if (hsp->oldcount == 1 && hsp->newcount == 1
378 && hsp->oldindex != hsp->newindex) {
379 TR(TRACE_UPDATE | TRACE_MOVE,
380 ("new line %d is hash-identical to old line %d (unique)",
381 hsp->newindex, hsp->oldindex));
382 OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
383 }
384
385 grow_hunks(SP_PARM);
386
387 /*
388 * Eliminate bad or impossible shifts -- this includes removing
389 * those hunks which could not grow because of conflicts, as well
390 * those which are to be moved too far, they are likely to destroy
391 * more than carry.
392 */
393 for (i = 0; i < screen_lines(SP_PARM);) {
394 int start, shift, size;
395
396 while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
397 i++;
398 if (i >= screen_lines(SP_PARM))
399 break;
400 start = i;
401 shift = OLDNUM(SP_PARM, i) - i;
402 i++;
403 while (i < screen_lines(SP_PARM)
404 && OLDNUM(SP_PARM, i) != _NEWINDEX
405 && OLDNUM(SP_PARM, i) - i == shift)
406 i++;
407 size = i - start;
408 if (size < 3 || size + Min(size / 8, 2) < abs(shift)) {
409 while (start < i) {
410 OLDNUM(SP_PARM, start) = _NEWINDEX;
411 start++;
412 }
413 }
414 }
415
416 /* After clearing invalid hunks, try grow the rest. */
417 grow_hunks(SP_PARM);
418 }
419
420 #if NCURSES_SP_FUNCS
421 NCURSES_EXPORT(void)
_nc_hash_map(void)422 _nc_hash_map(void)
423 {
424 NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
425 }
426 #endif
427
428 NCURSES_EXPORT(void)
NCURSES_SP_NAME(_nc_make_oldhash)429 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
430 {
431 if (oldhash(SP_PARM))
432 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
433 }
434
435 #if NCURSES_SP_FUNCS
436 NCURSES_EXPORT(void)
_nc_make_oldhash(int i)437 _nc_make_oldhash(int i)
438 {
439 NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
440 }
441 #endif
442
443 NCURSES_EXPORT(void)
NCURSES_SP_NAME(_nc_scroll_oldhash)444 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
445 {
446 size_t size;
447 int i;
448
449 if (!oldhash(SP_PARM))
450 return;
451
452 size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
453 if (n > 0) {
454 memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
455 for (i = bot; i > bot - n; i--)
456 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
457 } else {
458 memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
459 for (i = top; i < top - n; i++)
460 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
461 }
462 }
463
464 #if NCURSES_SP_FUNCS
465 NCURSES_EXPORT(void)
_nc_scroll_oldhash(int n,int top,int bot)466 _nc_scroll_oldhash(int n, int top, int bot)
467 {
468 NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
469 }
470 #endif
471
472 #ifdef HASHDEBUG
473 static void
usage(void)474 usage(void)
475 {
476 static const char *table[] =
477 {
478 "hashmap test-driver",
479 "",
480 "# comment",
481 "l get initial line number vector",
482 "n use following letters as text of new lines",
483 "o use following letters as text of old lines",
484 "d dump state of test arrays",
485 "h apply hash mapper and see scroll optimization",
486 "? this message"
487 };
488 size_t n;
489 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
490 fprintf(stderr, "%s\n", table[n]);
491 }
492
493 int
main(int argc GCC_UNUSED,char * argv[]GCC_UNUSED)494 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
495 {
496 char line[BUFSIZ], *st;
497 int n;
498
499 if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
500 return EXIT_FAILURE;
501 (void) _nc_alloc_screen();
502
503 for (n = 0; n < screen_lines(sp); n++) {
504 reallines[n] = n;
505 oldnums[n] = _NEWINDEX;
506 SetChar(oldtext[n][0], '.', A_NORMAL);
507 SetChar(newtext[n][0], '.', A_NORMAL);
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, " ")) != NULL);
537 break;
538
539 case 'n': /* use following letters as text of new lines */
540 for (n = 0; n < screen_lines(sp); n++)
541 SetChar(newtext[n][0], '.', A_NORMAL);
542 for (n = 0; n < screen_lines(sp); n++)
543 if (line[n + 1] == '\n')
544 break;
545 else
546 SetChar(newtext[n][0], line[n + 1], A_NORMAL);
547 break;
548
549 case 'o': /* use following letters as text of old lines */
550 for (n = 0; n < screen_lines(sp); n++)
551 SetChar(oldtext[n][0], '.', A_NORMAL);
552 for (n = 0; n < screen_lines(sp); n++)
553 if (line[n + 1] == '\n')
554 break;
555 else
556 SetChar(oldtext[n][0], line[n + 1], A_NORMAL);
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