1 /****************************************************************************
2 * Copyright (c) 1998-2006,2007 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>
71 #include <term.h> /* for back_color_erase */
73 MODULE_ID("$Id: hashmap.c,v 1.51 2007/04/28 20:14:15 tom Exp $")
77 # define _tracef printf
79 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
81 # define screen_lines MAXLINES
83 int oldnums[MAXLINES], reallines[MAXLINES];
84 static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH];
85 # define OLDNUM(n) oldnums[n]
86 # define OLDTEXT(n) oldtext[n]
87 # define NEWTEXT(m) newtext[m]
90 extern NCURSES_EXPORT_VAR(unsigned) _nc_tracing;
92 #else /* !HASHDEBUG */
94 # define OLDNUM(n) SP->_oldnum_list[n]
95 # define OLDTEXT(n) curscr->_line[n].text
96 # define NEWTEXT(m) newscr->_line[m].text
97 # define TEXTWIDTH (curscr->_maxx+1)
98 # define PENDING(n) (newscr->_line[n].firstchar != _NOCHANGE)
100 #endif /* !HASHDEBUG */
102 #define oldhash (SP->oldhash)
103 #define newhash (SP->newhash)
104 #define hashtab (SP->hashtab)
105 #define lines_alloc (SP->hashtab_len)
107 #if USE_WIDEC_SUPPORT
108 #define HASH_VAL(ch) (ch.chars[0])
110 #define HASH_VAL(ch) (ch)
113 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
115 static NCURSES_INLINE unsigned long
116 hash(NCURSES_CH_T * text)
120 unsigned long result = 0;
121 for (i = TEXTWIDTH; i > 0; i--) {
123 result += (result << 5) + HASH_VAL(ch);
128 /* approximate update cost */
130 update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to)
135 for (i = TEXTWIDTH; i > 0; i--)
136 if (!(CharEq(*from++, *to++)))
143 update_cost_from_blank(NCURSES_CH_T * to)
147 NCURSES_CH_T blank = blankchar;
149 if (back_color_erase)
150 SetPair(blank, GetPair(stdscr->_nc_bkgd));
152 for (i = TEXTWIDTH; i > 0; i--)
153 if (!(CharEq(blank, *to++)))
160 * Returns true when moving line 'from' to line 'to' seems to be cost
161 * effective. 'blank' indicates whether the line 'to' would become blank.
163 static NCURSES_INLINE bool
164 cost_effective(const int from, const int to, const bool blank)
171 new_from = OLDNUM(from);
172 if (new_from == _NEWINDEX)
176 * On the left side of >= is the cost before moving;
177 * on the right side -- cost after moving.
179 return (((blank ? update_cost_from_blank(NEWTEXT(to))
180 : update_cost(OLDTEXT(to), NEWTEXT(to)))
181 + update_cost(OLDTEXT(new_from), NEWTEXT(from)))
182 >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from))
183 : update_cost(OLDTEXT(new_from), NEWTEXT(from)))
184 + update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE;
190 int start, end, shift;
191 int back_limit, forward_limit; /* limits for cells to fill */
192 int back_ref_limit, forward_ref_limit; /* limits for refrences */
197 * This is tricky part. We have unique pairs to use as anchors.
198 * Use these to deduce the presence of spans of identical lines.
204 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
206 for (; i < screen_lines; i = next_hunk) {
208 shift = OLDNUM(i) - i;
210 /* get forward limit */
212 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
216 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
220 if (i >= screen_lines || OLDNUM(i) >= i)
221 forward_ref_limit = i;
223 forward_ref_limit = OLDNUM(i);
228 back_limit = back_ref_limit + (-shift);
229 while (i >= back_limit) {
230 if (newhash[i] == oldhash[i + shift]
231 || cost_effective(i + shift, i, shift < 0)) {
232 OLDNUM(i) = i + shift;
233 TR(TRACE_UPDATE | TRACE_MOVE,
234 ("connected new line %d to old line %d (backward continuation)",
237 TR(TRACE_UPDATE | TRACE_MOVE,
238 ("not connecting new line %d to old line %d (backward continuation)",
248 forward_limit = forward_ref_limit - shift;
249 while (i < forward_limit) {
250 if (newhash[i] == oldhash[i + shift]
251 || cost_effective(i + shift, i, shift > 0)) {
252 OLDNUM(i) = i + shift;
253 TR(TRACE_UPDATE | TRACE_MOVE,
254 ("connected new line %d to old line %d (forward continuation)",
257 TR(TRACE_UPDATE | TRACE_MOVE,
258 ("not connecting new line %d to old line %d (forward continuation)",
265 back_ref_limit = back_limit = i;
267 back_ref_limit += shift;
276 int start, shift, size;
278 if (screen_lines > lines_alloc) {
281 hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2);
284 FreeAndNull(oldhash);
289 lines_alloc = screen_lines;
292 if (oldhash && newhash) {
293 /* re-hash only changed lines */
294 for (i = 0; i < screen_lines; i++) {
296 newhash[i] = hash(NEWTEXT(i));
301 oldhash = typeCalloc(unsigned long, (unsigned) screen_lines);
303 newhash = typeCalloc(unsigned long, (unsigned) screen_lines);
304 if (!oldhash || !newhash)
305 return; /* malloc failure */
306 for (i = 0; i < screen_lines; i++) {
307 newhash[i] = hash(NEWTEXT(i));
308 oldhash[i] = hash(OLDTEXT(i));
313 for (i = 0; i < screen_lines; i++) {
314 if (newhash[i] != hash(NEWTEXT(i)))
315 fprintf(stderr, "error in newhash[%d]\n", i);
316 if (oldhash[i] != hash(OLDTEXT(i)))
317 fprintf(stderr, "error in oldhash[%d]\n", i);
322 * Set up and count line-hash values.
324 memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2);
325 for (i = 0; i < screen_lines; i++) {
326 unsigned long hashval = oldhash[i];
328 for (sp = hashtab; sp->hashval; sp++)
329 if (sp->hashval == hashval)
331 sp->hashval = hashval; /* in case this is a new entry */
335 for (i = 0; i < screen_lines; i++) {
336 unsigned long hashval = newhash[i];
338 for (sp = hashtab; sp->hashval; sp++)
339 if (sp->hashval == hashval)
341 sp->hashval = hashval; /* in case this is a new entry */
345 OLDNUM(i) = _NEWINDEX; /* initialize old indices array */
349 * Mark line pairs corresponding to unique hash pairs.
351 * We don't mark lines with offset 0, because it can make fail
352 * extending hunks by cost_effective. Otherwise, it does not
353 * have any side effects.
355 for (sp = hashtab; sp->hashval; sp++)
356 if (sp->oldcount == 1 && sp->newcount == 1
357 && sp->oldindex != sp->newindex) {
358 TR(TRACE_UPDATE | TRACE_MOVE,
359 ("new line %d is hash-identical to old line %d (unique)",
360 sp->newindex, sp->oldindex));
361 OLDNUM(sp->newindex) = sp->oldindex;
367 * Eliminate bad or impossible shifts -- this includes removing
368 * those hunks which could not grow because of conflicts, as well
369 * those which are to be moved too far, they are likely to destroy
372 for (i = 0; i < screen_lines;) {
373 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
375 if (i >= screen_lines)
378 shift = OLDNUM(i) - i;
380 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
384 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
386 OLDNUM(start) = _NEWINDEX;
392 /* After clearing invalid hunks, try grow the rest. */
397 _nc_make_oldhash(int i)
400 oldhash[i] = hash(OLDTEXT(i));
404 _nc_scroll_oldhash(int n, int top, int bot)
412 size = sizeof(*oldhash) * (bot - top + 1 - abs(n));
414 memmove(oldhash + top, oldhash + top + n, size);
415 for (i = bot; i > bot - n; i--)
416 oldhash[i] = hash(OLDTEXT(i));
418 memmove(oldhash + top - n, oldhash + top, size);
419 for (i = top; i < top - n; i++)
420 oldhash[i] = hash(OLDTEXT(i));
428 static const char *table[] =
430 "hashmap test-driver",
433 "l get initial line number vector",
434 "n use following letters as text of new lines",
435 "o use following letters as text of old lines",
436 "d dump state of test arrays",
437 "h apply hash mapper and see scroll optimization",
441 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
442 fprintf(stderr, "%s\n", table[n]);
446 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
448 char line[BUFSIZ], *st;
451 SP = typeCalloc(SCREEN, 1);
452 for (n = 0; n < screen_lines; n++) {
454 oldnums[n] = _NEWINDEX;
455 oldtext[n][0] = newtext[n][0] = '.';
458 if (isatty(fileno(stdin)))
462 _nc_tracing = TRACE_MOVE;
465 /* grab a test command */
466 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
470 case '#': /* comment */
471 (void) fputs(line, stderr);
474 case 'l': /* get initial line number vector */
475 for (n = 0; n < screen_lines; n++) {
477 oldnums[n] = _NEWINDEX;
480 st = strtok(line, " ");
482 oldnums[n++] = atoi(st);
484 ((st = strtok((char *) NULL, " ")) != 0);
487 case 'n': /* use following letters as text of new lines */
488 for (n = 0; n < screen_lines; n++)
490 for (n = 0; n < screen_lines; n++)
491 if (line[n + 1] == '\n')
494 newtext[n][0] = line[n + 1];
497 case 'o': /* use following letters as text of old lines */
498 for (n = 0; n < screen_lines; n++)
500 for (n = 0; n < screen_lines; n++)
501 if (line[n + 1] == '\n')
504 oldtext[n][0] = line[n + 1];
507 case 'd': /* dump state of test arrays */
511 (void) fputs("Old lines: [", stdout);
512 for (n = 0; n < screen_lines; n++)
513 putchar(oldtext[n][0]);
516 (void) fputs("New lines: [", stdout);
517 for (n = 0; n < screen_lines; n++)
518 putchar(newtext[n][0]);
523 case 'h': /* apply hash mapper and see scroll optimization */
525 (void) fputs("Result:\n", stderr);
529 _nc_scroll_optimize();
530 (void) fputs("Done.\n", stderr);
540 #endif /* HASHDEBUG */
542 /* hashmap.c ends here */