1 /****************************************************************************
2 * Copyright (c) 1998-2015,2016 Free Software Foundation, Inc. *
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: *
12 * The above copyright notice and this permission notice shall be included *
13 * in all copies or substantial portions of the Software. *
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. *
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 *
27 ****************************************************************************/
29 /****************************************************************************
30 * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 *
31 * and: Eric S. Raymond <esr@snark.thyrsus.com> *
32 ****************************************************************************/
34 /******************************************************************************
37 hashmap.c -- fill in scramble vector based on text hashes
40 void _nc_hash_map(void)
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).
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.
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.
59 Use the following production:
62 $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
65 Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
66 Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997
68 *****************************************************************************/
70 #include <curses.priv.h>
73 #define CUR SP_TERMTYPE
76 MODULE_ID("$Id: hashmap.c,v 1.66 2016/05/28 23:32:40 tom Exp $")
80 # define _tracef printf
83 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
85 # define TR(n, a) { _tracef a ; putchar('\n'); }
88 # define screen_lines(sp) MAXLINES
89 # define TEXTWIDTH(sp) 1
90 int oldnums[MAXLINES], reallines[MAXLINES];
91 static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH(sp)];
92 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH(sp)];
93 # define OLDNUM(sp,n) oldnums[n]
94 # define OLDTEXT(sp,n) oldtext[n]
95 # define NEWTEXT(sp,m) newtext[m]
96 # define PENDING(sp,n) 1
98 #else /* !HASHDEBUG */
100 # define OLDNUM(sp,n) (sp)->_oldnum_list[n]
101 # define OLDTEXT(sp,n) CurScreen(sp)->_line[n].text
102 # define NEWTEXT(sp,m) NewScreen(sp)->_line[m].text
103 # define TEXTWIDTH(sp) (CurScreen(sp)->_maxx + 1)
104 # define PENDING(sp,n) (NewScreen(sp)->_line[n].firstchar != _NOCHANGE)
106 #endif /* !HASHDEBUG */
108 #define oldhash(sp) ((sp)->oldhash)
109 #define newhash(sp) ((sp)->newhash)
110 #define hashtab(sp) ((sp)->hashtab)
111 #define lines_alloc(sp) ((sp)->hashtab_len)
113 #if USE_WIDEC_SUPPORT
114 #define HASH_VAL(ch) (ch.chars[0])
116 #define HASH_VAL(ch) (ch)
119 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
121 static NCURSES_INLINE unsigned long
122 hash(SCREEN *sp, NCURSES_CH_T * text)
126 unsigned long result = 0;
129 for (i = TEXTWIDTH(sp); i > 0; i--) {
131 result += (result << 5) + (unsigned long) HASH_VAL(ch);
136 /* approximate update cost */
138 update_cost(SCREEN *sp, NCURSES_CH_T * from, NCURSES_CH_T * to)
144 for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
145 if (!(CharEq(*from, *to)))
152 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T * to)
156 NCURSES_CH_T blank = blankchar;
159 if (back_color_erase)
160 SetPair(blank, GetPair(stdscr->_nc_bkgd));
162 for (i = TEXTWIDTH(sp); i > 0; i--, to++)
163 if (!(CharEq(blank, *to)))
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.
173 static NCURSES_INLINE bool
174 cost_effective(SCREEN *sp, const int from, const int to, const int blank)
181 new_from = OLDNUM(sp, from);
182 if (new_from == _NEWINDEX)
186 * On the left side of >= is the cost before moving;
187 * on the right side -- cost after moving.
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))))
199 grow_hunks(SCREEN *sp)
201 int back_limit; /* limits for cells to fill */
202 int back_ref_limit; /* limit for references */
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.
214 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
216 for (; i < screen_lines(sp); i = next_hunk) {
218 int forward_ref_limit;
221 int shift = OLDNUM(sp, i) - i;
223 /* get forward limit */
225 while (i < screen_lines(sp)
226 && OLDNUM(sp, i) != _NEWINDEX
227 && OLDNUM(sp, i) - i == shift)
230 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
234 if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
235 forward_ref_limit = i;
237 forward_ref_limit = OLDNUM(sp, i);
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)",
251 TR(TRACE_UPDATE | TRACE_MOVE,
252 ("not connecting new line %d to old line %d (backward continuation)",
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)",
271 TR(TRACE_UPDATE | TRACE_MOVE,
272 ("not connecting new line %d to old line %d (forward continuation)",
279 back_ref_limit = back_limit = i;
281 back_ref_limit += shift;
286 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
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));
300 lines_alloc(SP_PARM) = 0;
303 lines_alloc(SP_PARM) = screen_lines(SP_PARM);
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));
314 if (oldhash(SP_PARM) == 0)
315 oldhash(SP_PARM) = typeCalloc(unsigned long,
316 (size_t) screen_lines(SP_PARM));
317 if (newhash(SP_PARM) == 0)
318 newhash(SP_PARM) = typeCalloc(unsigned long,
319 (size_t) screen_lines(SP_PARM));
320 if (!oldhash(SP_PARM) || !newhash(SP_PARM))
321 return; /* malloc failure */
322 for (i = 0; i < screen_lines(SP_PARM); i++) {
323 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
324 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
329 for (i = 0; i < screen_lines(SP_PARM); i++) {
330 if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
331 fprintf(stderr, "error in newhash[%d]\n", i);
332 if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
333 fprintf(stderr, "error in oldhash[%d]\n", i);
338 * Set up and count line-hash values.
340 memset(hashtab(SP_PARM), '\0',
341 sizeof(*(hashtab(SP_PARM)))
342 * ((size_t) screen_lines(SP_PARM) + 1) * 2);
343 for (i = 0; i < screen_lines(SP_PARM); i++) {
344 unsigned long hashval = oldhash(SP_PARM)[i];
346 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
347 if (hsp->hashval == hashval)
349 hsp->hashval = hashval; /* in case this is a new entry */
353 for (i = 0; i < screen_lines(SP_PARM); i++) {
354 unsigned long hashval = newhash(SP_PARM)[i];
356 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
357 if (hsp->hashval == hashval)
359 hsp->hashval = hashval; /* in case this is a new entry */
363 OLDNUM(SP_PARM, i) = _NEWINDEX; /* initialize old indices array */
367 * Mark line pairs corresponding to unique hash pairs.
369 * We don't mark lines with offset 0, because it can make fail
370 * extending hunks by cost_effective. Otherwise, it does not
371 * have any side effects.
373 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
374 if (hsp->oldcount == 1 && hsp->newcount == 1
375 && hsp->oldindex != hsp->newindex) {
376 TR(TRACE_UPDATE | TRACE_MOVE,
377 ("new line %d is hash-identical to old line %d (unique)",
378 hsp->newindex, hsp->oldindex));
379 OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
385 * Eliminate bad or impossible shifts -- this includes removing
386 * those hunks which could not grow because of conflicts, as well
387 * those which are to be moved too far, they are likely to destroy
390 for (i = 0; i < screen_lines(SP_PARM);) {
391 int start, shift, size;
393 while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
395 if (i >= screen_lines(SP_PARM))
398 shift = OLDNUM(SP_PARM, i) - i;
400 while (i < screen_lines(SP_PARM)
401 && OLDNUM(SP_PARM, i) != _NEWINDEX
402 && OLDNUM(SP_PARM, i) - i == shift)
405 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
407 OLDNUM(SP_PARM, start) = _NEWINDEX;
413 /* After clearing invalid hunks, try grow the rest. */
421 NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
426 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
428 if (oldhash(SP_PARM))
429 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
434 _nc_make_oldhash(int i)
436 NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
441 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
446 if (!oldhash(SP_PARM))
449 size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
451 memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
452 for (i = bot; i > bot - n; i--)
453 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
455 memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
456 for (i = top; i < top - n; i++)
457 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
463 _nc_scroll_oldhash(int n, int top, int bot)
465 NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
473 static const char *table[] =
475 "hashmap test-driver",
478 "l get initial line number vector",
479 "n use following letters as text of new lines",
480 "o use following letters as text of old lines",
481 "d dump state of test arrays",
482 "h apply hash mapper and see scroll optimization",
486 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
487 fprintf(stderr, "%s\n", table[n]);
491 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
493 char line[BUFSIZ], *st;
496 if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
498 (void) _nc_alloc_screen();
500 for (n = 0; n < screen_lines(sp); n++) {
502 oldnums[n] = _NEWINDEX;
503 CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
506 if (NC_ISATTY(fileno(stdin)))
510 _nc_tracing = TRACE_MOVE;
513 /* grab a test command */
514 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
518 case '#': /* comment */
519 (void) fputs(line, stderr);
522 case 'l': /* get initial line number vector */
523 for (n = 0; n < screen_lines(sp); n++) {
525 oldnums[n] = _NEWINDEX;
528 st = strtok(line, " ");
530 oldnums[n++] = atoi(st);
532 ((st = strtok((char *) NULL, " ")) != 0);
535 case 'n': /* use following letters as text of new lines */
536 for (n = 0; n < screen_lines(sp); n++)
537 CharOf(newtext[n][0]) = '.';
538 for (n = 0; n < screen_lines(sp); n++)
539 if (line[n + 1] == '\n')
542 CharOf(newtext[n][0]) = line[n + 1];
545 case 'o': /* use following letters as text of old lines */
546 for (n = 0; n < screen_lines(sp); n++)
547 CharOf(oldtext[n][0]) = '.';
548 for (n = 0; n < screen_lines(sp); n++)
549 if (line[n + 1] == '\n')
552 CharOf(oldtext[n][0]) = line[n + 1];
555 case 'd': /* dump state of test arrays */
559 (void) fputs("Old lines: [", stdout);
560 for (n = 0; n < screen_lines(sp); n++)
561 putchar(CharOf(oldtext[n][0]));
564 (void) fputs("New lines: [", stdout);
565 for (n = 0; n < screen_lines(sp); n++)
566 putchar(CharOf(newtext[n][0]));
571 case 'h': /* apply hash mapper and see scroll optimization */
573 (void) fputs("Result:\n", stderr);
577 _nc_scroll_optimize();
578 (void) fputs("Done.\n", stderr);
587 _nc_free_and_exit(EXIT_SUCCESS);
593 #endif /* HASHDEBUG */
595 /* hashmap.c ends here */