1 /****************************************************************************
2 * Copyright 2019,2020 Thomas E. Dickey *
3 * Copyright 1998-2015,2016 Free Software Foundation, Inc. *
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: *
13 * The above copyright notice and this permission notice shall be included *
14 * in all copies or substantial portions of the Software. *
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. *
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 *
28 ****************************************************************************/
30 /****************************************************************************
31 * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 *
32 * and: Eric S. Raymond <esr@snark.thyrsus.com> *
33 ****************************************************************************/
35 /******************************************************************************
38 hashmap.c -- fill in scramble vector based on text hashes
41 void _nc_hash_map(void)
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).
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.
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.
60 Use the following production:
63 $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
66 Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
67 Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997
69 *****************************************************************************/
71 #include <curses.priv.h>
74 #define CUR SP_TERMTYPE
77 MODULE_ID("$Id: hashmap.c,v 1.69 2020/05/31 17:50:48 tom Exp $")
81 # define _tracef printf
84 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
86 # define TR(n, a) { _tracef a ; putchar('\n'); }
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
99 #else /* !HASHDEBUG */
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)
107 #endif /* !HASHDEBUG */
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)
114 #if USE_WIDEC_SUPPORT
115 #define HASH_VAL(ch) (ch.chars[0])
117 #define HASH_VAL(ch) (ch)
120 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
122 static NCURSES_INLINE unsigned long
123 hash(SCREEN *sp, NCURSES_CH_T *text)
127 unsigned long result = 0;
130 for (i = TEXTWIDTH(sp); i > 0; i--) {
132 result += (result << 5) + (unsigned long) HASH_VAL(ch);
137 /* approximate update cost */
139 update_cost(SCREEN *sp, NCURSES_CH_T *from, NCURSES_CH_T *to)
145 for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
146 if (!(CharEq(*from, *to)))
153 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T *to)
157 NCURSES_CH_T blank = blankchar;
160 if (back_color_erase)
161 SetPair(blank, GetPair(stdscr->_nc_bkgd));
163 for (i = TEXTWIDTH(sp); i > 0; i--, to++)
164 if (!(CharEq(blank, *to)))
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.
174 static NCURSES_INLINE bool
175 cost_effective(SCREEN *sp, const int from, const int to, const int blank)
182 new_from = OLDNUM(sp, from);
183 if (new_from == _NEWINDEX)
187 * On the left side of >= is the cost before moving;
188 * on the right side -- cost after moving.
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))))
200 grow_hunks(SCREEN *sp)
202 int back_limit; /* limits for cells to fill */
203 int back_ref_limit; /* limit for references */
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.
215 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
217 for (; i < screen_lines(sp); i = next_hunk) {
219 int forward_ref_limit;
222 int shift = OLDNUM(sp, i) - i;
224 /* get forward limit */
226 while (i < screen_lines(sp)
227 && OLDNUM(sp, i) != _NEWINDEX
228 && OLDNUM(sp, i) - i == shift)
231 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
235 if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
236 forward_ref_limit = i;
238 forward_ref_limit = OLDNUM(sp, i);
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)",
252 TR(TRACE_UPDATE | TRACE_MOVE,
253 ("not connecting new line %d to old line %d (backward continuation)",
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)",
272 TR(TRACE_UPDATE | TRACE_MOVE,
273 ("not connecting new line %d to old line %d (forward continuation)",
280 back_ref_limit = back_limit = i;
282 back_ref_limit += shift;
287 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
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));
301 lines_alloc(SP_PARM) = 0;
304 lines_alloc(SP_PARM) = screen_lines(SP_PARM);
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));
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 return; /* malloc failure */
323 for (i = 0; i < screen_lines(SP_PARM); i++) {
324 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
325 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
330 for (i = 0; i < screen_lines(SP_PARM); i++) {
331 if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
332 fprintf(stderr, "error in newhash[%d]\n", i);
333 if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
334 fprintf(stderr, "error in oldhash[%d]\n", i);
339 * Set up and count line-hash values.
341 memset(hashtab(SP_PARM), '\0',
342 sizeof(*(hashtab(SP_PARM)))
343 * ((size_t) screen_lines(SP_PARM) + 1) * 2);
344 for (i = 0; i < screen_lines(SP_PARM); i++) {
345 unsigned long hashval = oldhash(SP_PARM)[i];
347 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
348 if (hsp->hashval == hashval)
350 hsp->hashval = hashval; /* in case this is a new entry */
354 for (i = 0; i < screen_lines(SP_PARM); i++) {
355 unsigned long hashval = newhash(SP_PARM)[i];
357 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
358 if (hsp->hashval == hashval)
360 hsp->hashval = hashval; /* in case this is a new entry */
364 OLDNUM(SP_PARM, i) = _NEWINDEX; /* initialize old indices array */
368 * Mark line pairs corresponding to unique hash pairs.
370 * We don't mark lines with offset 0, because it can make fail
371 * extending hunks by cost_effective. Otherwise, it does not
372 * have any side effects.
374 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
375 if (hsp->oldcount == 1 && hsp->newcount == 1
376 && hsp->oldindex != hsp->newindex) {
377 TR(TRACE_UPDATE | TRACE_MOVE,
378 ("new line %d is hash-identical to old line %d (unique)",
379 hsp->newindex, hsp->oldindex));
380 OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
386 * Eliminate bad or impossible shifts -- this includes removing
387 * those hunks which could not grow because of conflicts, as well
388 * those which are to be moved too far, they are likely to destroy
391 for (i = 0; i < screen_lines(SP_PARM);) {
392 int start, shift, size;
394 while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
396 if (i >= screen_lines(SP_PARM))
399 shift = OLDNUM(SP_PARM, i) - i;
401 while (i < screen_lines(SP_PARM)
402 && OLDNUM(SP_PARM, i) != _NEWINDEX
403 && OLDNUM(SP_PARM, i) - i == shift)
406 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
408 OLDNUM(SP_PARM, start) = _NEWINDEX;
414 /* After clearing invalid hunks, try grow the rest. */
422 NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
427 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
429 if (oldhash(SP_PARM))
430 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
435 _nc_make_oldhash(int i)
437 NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
442 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
447 if (!oldhash(SP_PARM))
450 size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
452 memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
453 for (i = bot; i > bot - n; i--)
454 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
456 memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
457 for (i = top; i < top - n; i++)
458 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
464 _nc_scroll_oldhash(int n, int top, int bot)
466 NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
474 static const char *table[] =
476 "hashmap test-driver",
479 "l get initial line number vector",
480 "n use following letters as text of new lines",
481 "o use following letters as text of old lines",
482 "d dump state of test arrays",
483 "h apply hash mapper and see scroll optimization",
487 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
488 fprintf(stderr, "%s\n", table[n]);
492 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
494 char line[BUFSIZ], *st;
497 if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
499 (void) _nc_alloc_screen();
501 for (n = 0; n < screen_lines(sp); n++) {
503 oldnums[n] = _NEWINDEX;
504 CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
507 if (NC_ISATTY(fileno(stdin)))
511 _nc_tracing = TRACE_MOVE;
514 /* grab a test command */
515 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
519 case '#': /* comment */
520 (void) fputs(line, stderr);
523 case 'l': /* get initial line number vector */
524 for (n = 0; n < screen_lines(sp); n++) {
526 oldnums[n] = _NEWINDEX;
529 st = strtok(line, " ");
531 oldnums[n++] = atoi(st);
533 ((st = strtok((char *) NULL, " ")) != 0);
536 case 'n': /* use following letters as text of new lines */
537 for (n = 0; n < screen_lines(sp); n++)
538 CharOf(newtext[n][0]) = '.';
539 for (n = 0; n < screen_lines(sp); n++)
540 if (line[n + 1] == '\n')
543 CharOf(newtext[n][0]) = line[n + 1];
546 case 'o': /* use following letters as text of old lines */
547 for (n = 0; n < screen_lines(sp); n++)
548 CharOf(oldtext[n][0]) = '.';
549 for (n = 0; n < screen_lines(sp); n++)
550 if (line[n + 1] == '\n')
553 CharOf(oldtext[n][0]) = line[n + 1];
556 case 'd': /* dump state of test arrays */
560 (void) fputs("Old lines: [", stdout);
561 for (n = 0; n < screen_lines(sp); n++)
562 putchar(CharOf(oldtext[n][0]));
565 (void) fputs("New lines: [", stdout);
566 for (n = 0; n < screen_lines(sp); n++)
567 putchar(CharOf(newtext[n][0]));
572 case 'h': /* apply hash mapper and see scroll optimization */
574 (void) fputs("Result:\n", stderr);
578 _nc_scroll_optimize();
579 (void) fputs("Done.\n", stderr);
587 exit_curses(EXIT_SUCCESS);
590 #endif /* HASHDEBUG */
592 /* hashmap.c ends here */