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