1 /****************************************************************************
2 * Copyright (c) 1998-2007,2009 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.61 2009/11/07 16:07:55 tom Exp $")
80 # define _tracef printf
82 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
84 # define screen_lines MAXLINES
86 int oldnums[MAXLINES], reallines[MAXLINES];
87 static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH];
88 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH];
89 # define OLDNUM(sp,n) oldnums[n]
90 # define OLDTEXT(sp,n) oldtext[n]
91 # define NEWTEXT(sp,m) newtext[m]
92 # define PENDING(sp,n) 1
94 #else /* !HASHDEBUG */
96 # define OLDNUM(sp,n) (sp)->_oldnum_list[n]
97 # define OLDTEXT(sp,n) CurScreen(sp)->_line[n].text
98 # define NEWTEXT(sp,m) NewScreen(sp)->_line[m].text
99 # define TEXTWIDTH(sp) (CurScreen(sp)->_maxx + 1)
100 # define PENDING(sp,n) (NewScreen(sp)->_line[n].firstchar != _NOCHANGE)
102 #endif /* !HASHDEBUG */
104 #define oldhash(sp) ((sp)->oldhash)
105 #define newhash(sp) ((sp)->newhash)
106 #define hashtab(sp) ((sp)->hashtab)
107 #define lines_alloc(sp) ((sp)->hashtab_len)
109 #if USE_WIDEC_SUPPORT
110 #define HASH_VAL(ch) (ch.chars[0])
112 #define HASH_VAL(ch) (ch)
115 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
117 static NCURSES_INLINE unsigned long
118 hash(SCREEN *sp, NCURSES_CH_T * text)
122 unsigned long result = 0;
123 for (i = TEXTWIDTH(sp); i > 0; i--) {
125 result += (result << 5) + HASH_VAL(ch);
130 /* approximate update cost */
132 update_cost(SCREEN *sp, NCURSES_CH_T * from, NCURSES_CH_T * to)
137 for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
138 if (!(CharEq(*from, *to)))
145 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T * to)
149 NCURSES_CH_T blank = blankchar;
151 if (back_color_erase)
152 SetPair(blank, GetPair(stdscr->_nc_bkgd));
154 for (i = TEXTWIDTH(sp); i > 0; i--, to++)
155 if (!(CharEq(blank, *to)))
162 * Returns true when moving line 'from' to line 'to' seems to be cost
163 * effective. 'blank' indicates whether the line 'to' would become blank.
165 static NCURSES_INLINE bool
166 cost_effective(SCREEN *sp, const int from, const int to, const bool blank)
173 new_from = OLDNUM(sp, from);
174 if (new_from == _NEWINDEX)
178 * On the left side of >= is the cost before moving;
179 * on the right side -- cost after moving.
181 return (((blank ? update_cost_from_blank(sp, NEWTEXT(sp, to))
182 : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to)))
183 + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
184 >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from))
185 : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
186 + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to))))
191 grow_hunks(SCREEN *sp)
193 int start, end, shift;
194 int back_limit, forward_limit; /* limits for cells to fill */
195 int back_ref_limit, forward_ref_limit; /* limits for refrences */
200 * This is tricky part. We have unique pairs to use as anchors.
201 * Use these to deduce the presence of spans of identical lines.
207 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
209 for (; i < screen_lines(sp); i = next_hunk) {
211 shift = OLDNUM(sp, i) - i;
213 /* get forward limit */
215 while (i < screen_lines(sp)
216 && OLDNUM(sp, i) != _NEWINDEX
217 && OLDNUM(sp, i) - i == shift)
220 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
224 if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
225 forward_ref_limit = i;
227 forward_ref_limit = OLDNUM(sp, i);
232 back_limit = back_ref_limit + (-shift);
233 while (i >= back_limit) {
234 if (newhash(sp)[i] == oldhash(sp)[i + shift]
235 || cost_effective(sp, i + shift, i, shift < 0)) {
236 OLDNUM(sp, i) = i + shift;
237 TR(TRACE_UPDATE | TRACE_MOVE,
238 ("connected new line %d to old line %d (backward continuation)",
241 TR(TRACE_UPDATE | TRACE_MOVE,
242 ("not connecting new line %d to old line %d (backward continuation)",
252 forward_limit = forward_ref_limit - shift;
253 while (i < forward_limit) {
254 if (newhash(sp)[i] == oldhash(sp)[i + shift]
255 || cost_effective(sp, i + shift, i, shift > 0)) {
256 OLDNUM(sp, i) = i + shift;
257 TR(TRACE_UPDATE | TRACE_MOVE,
258 ("connected new line %d to old line %d (forward continuation)",
261 TR(TRACE_UPDATE | TRACE_MOVE,
262 ("not connecting new line %d to old line %d (forward continuation)",
269 back_ref_limit = back_limit = i;
271 back_ref_limit += shift;
276 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
280 int start, shift, size;
282 if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
283 if (hashtab(SP_PARM))
284 free(hashtab(SP_PARM));
285 hashtab(SP_PARM) = typeMalloc(HASHMAP, (screen_lines(SP_PARM) + 1) * 2);
286 if (!hashtab(SP_PARM)) {
287 if (oldhash(SP_PARM)) {
288 FreeAndNull(oldhash(SP_PARM));
290 lines_alloc(SP_PARM) = 0;
293 lines_alloc(SP_PARM) = screen_lines(SP_PARM);
296 if (oldhash(SP_PARM) && newhash(SP_PARM)) {
297 /* re-hash only changed lines */
298 for (i = 0; i < screen_lines(SP_PARM); i++) {
299 if (PENDING(SP_PARM, i))
300 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
304 if (oldhash(SP_PARM) == 0)
305 oldhash(SP_PARM) = typeCalloc(unsigned long,
306 (unsigned) screen_lines(SP_PARM));
307 if (newhash(SP_PARM) == 0)
308 newhash(SP_PARM) = typeCalloc(unsigned long,
309 (unsigned) screen_lines(SP_PARM));
310 if (!oldhash(SP_PARM) || !newhash(SP_PARM))
311 return; /* malloc failure */
312 for (i = 0; i < screen_lines(SP_PARM); i++) {
313 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
314 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
319 for (i = 0; i < screen_lines(SP_PARM); i++) {
320 if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
321 fprintf(stderr, "error in newhash[%d]\n", i);
322 if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
323 fprintf(stderr, "error in oldhash[%d]\n", i);
328 * Set up and count line-hash values.
330 memset(hashtab(SP_PARM), '\0',
331 sizeof(*(hashtab(SP_PARM))) * (screen_lines(SP_PARM) + 1) * 2);
332 for (i = 0; i < screen_lines(SP_PARM); i++) {
333 unsigned long hashval = oldhash(SP_PARM)[i];
335 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
336 if (hsp->hashval == hashval)
338 hsp->hashval = hashval; /* in case this is a new entry */
342 for (i = 0; i < screen_lines(SP_PARM); i++) {
343 unsigned long hashval = newhash(SP_PARM)[i];
345 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
346 if (hsp->hashval == hashval)
348 hsp->hashval = hashval; /* in case this is a new entry */
352 OLDNUM(SP_PARM, i) = _NEWINDEX; /* initialize old indices array */
356 * Mark line pairs corresponding to unique hash pairs.
358 * We don't mark lines with offset 0, because it can make fail
359 * extending hunks by cost_effective. Otherwise, it does not
360 * have any side effects.
362 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
363 if (hsp->oldcount == 1 && hsp->newcount == 1
364 && hsp->oldindex != hsp->newindex) {
365 TR(TRACE_UPDATE | TRACE_MOVE,
366 ("new line %d is hash-identical to old line %d (unique)",
367 hsp->newindex, hsp->oldindex));
368 OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
374 * Eliminate bad or impossible shifts -- this includes removing
375 * those hunks which could not grow because of conflicts, as well
376 * those which are to be moved too far, they are likely to destroy
379 for (i = 0; i < screen_lines(SP_PARM);) {
380 while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
382 if (i >= screen_lines(SP_PARM))
385 shift = OLDNUM(SP_PARM, i) - i;
387 while (i < screen_lines(SP_PARM)
388 && OLDNUM(SP_PARM, i) != _NEWINDEX
389 && OLDNUM(SP_PARM, i) - i == shift)
392 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
394 OLDNUM(SP_PARM, start) = _NEWINDEX;
400 /* After clearing invalid hunks, try grow the rest. */
408 NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
413 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
415 if (oldhash(SP_PARM))
416 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
421 _nc_make_oldhash(int i)
423 NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
428 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
433 if (!oldhash(SP_PARM))
436 size = sizeof(*(oldhash(SP_PARM))) * (bot - top + 1 - abs(n));
438 memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
439 for (i = bot; i > bot - n; i--)
440 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
442 memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
443 for (i = top; i < top - n; i++)
444 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
450 _nc_scroll_oldhash(int n, int top, int bot)
452 NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
460 static const char *table[] =
462 "hashmap test-driver",
465 "l get initial line number vector",
466 "n use following letters as text of new lines",
467 "o use following letters as text of old lines",
468 "d dump state of test arrays",
469 "h apply hash mapper and see scroll optimization",
473 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
474 fprintf(stderr, "%s\n", table[n]);
478 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
480 char line[BUFSIZ], *st;
483 if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
485 (void) _nc_alloc_screen();
487 for (n = 0; n < screen_lines; n++) {
489 oldnums[n] = _NEWINDEX;
490 CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
493 if (isatty(fileno(stdin)))
497 _nc_tracing = TRACE_MOVE;
500 /* grab a test command */
501 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
505 case '#': /* comment */
506 (void) fputs(line, stderr);
509 case 'l': /* get initial line number vector */
510 for (n = 0; n < screen_lines; n++) {
512 oldnums[n] = _NEWINDEX;
515 st = strtok(line, " ");
517 oldnums[n++] = atoi(st);
519 ((st = strtok((char *) NULL, " ")) != 0);
522 case 'n': /* use following letters as text of new lines */
523 for (n = 0; n < screen_lines; n++)
524 CharOf(newtext[n][0]) = '.';
525 for (n = 0; n < screen_lines; n++)
526 if (line[n + 1] == '\n')
529 CharOf(newtext[n][0]) = line[n + 1];
532 case 'o': /* use following letters as text of old lines */
533 for (n = 0; n < screen_lines; n++)
534 CharOf(oldtext[n][0]) = '.';
535 for (n = 0; n < screen_lines; n++)
536 if (line[n + 1] == '\n')
539 CharOf(oldtext[n][0]) = line[n + 1];
542 case 'd': /* dump state of test arrays */
546 (void) fputs("Old lines: [", stdout);
547 for (n = 0; n < screen_lines; n++)
548 putchar(CharOf(oldtext[n][0]));
551 (void) fputs("New lines: [", stdout);
552 for (n = 0; n < screen_lines; n++)
553 putchar(CharOf(newtext[n][0]));
558 case 'h': /* apply hash mapper and see scroll optimization */
560 (void) fputs("Result:\n", stderr);
564 _nc_scroll_optimize();
565 (void) fputs("Done.\n", stderr);
574 _nc_free_and_exit(EXIT_SUCCESS);
580 #endif /* HASHDEBUG */
582 /* hashmap.c ends here */