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>
72 MODULE_ID("$Id: hashmap.c,v 1.57 2009/04/18 19:03:50 tom Exp $")
76 # define _tracef printf
78 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
80 # define screen_lines MAXLINES
82 int oldnums[MAXLINES], reallines[MAXLINES];
83 static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH];
84 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH];
85 # define OLDNUM(sp,n) oldnums[n]
86 # define OLDTEXT(sp,n) oldtext[n]
87 # define NEWTEXT(sp,m) newtext[m]
88 # define PENDING(sp,n) 1
90 #else /* !HASHDEBUG */
92 # define OLDNUM(sp,n) (sp)->_oldnum_list[n]
93 # define OLDTEXT(sp,n) (sp)->_curscr->_line[n].text
94 # define NEWTEXT(sp,m) (sp)->_newscr->_line[m].text
95 # define TEXTWIDTH(sp) ((sp)->_curscr->_maxx+1)
96 # define PENDING(sp,n) ((sp)->_newscr->_line[n].firstchar != _NOCHANGE)
98 #endif /* !HASHDEBUG */
100 #define oldhash(sp) ((sp)->oldhash)
101 #define newhash(sp) ((sp)->newhash)
102 #define hashtab(sp) ((sp)->hashtab)
103 #define lines_alloc(sp) ((sp)->hashtab_len)
105 #if USE_WIDEC_SUPPORT
106 #define HASH_VAL(ch) (ch.chars[0])
108 #define HASH_VAL(ch) (ch)
111 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
113 static NCURSES_INLINE unsigned long
114 hash(SCREEN *sp, NCURSES_CH_T * text)
118 unsigned long result = 0;
119 for (i = TEXTWIDTH(sp); i > 0; i--) {
121 result += (result << 5) + HASH_VAL(ch);
126 /* approximate update cost */
128 update_cost(SCREEN *sp, NCURSES_CH_T * from, NCURSES_CH_T * to)
133 for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
134 if (!(CharEq(*from, *to)))
141 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T * to)
145 NCURSES_CH_T blank = blankchar;
147 if (back_color_erase)
148 SetPair(blank, GetPair(stdscr->_nc_bkgd));
150 for (i = TEXTWIDTH(sp); i > 0; i--, to++)
151 if (!(CharEq(blank, *to)))
158 * Returns true when moving line 'from' to line 'to' seems to be cost
159 * effective. 'blank' indicates whether the line 'to' would become blank.
161 static NCURSES_INLINE bool
162 cost_effective(SCREEN *sp, const int from, const int to, const bool blank)
169 new_from = OLDNUM(sp, from);
170 if (new_from == _NEWINDEX)
174 * On the left side of >= is the cost before moving;
175 * on the right side -- cost after moving.
177 return (((blank ? update_cost_from_blank(sp, NEWTEXT(sp, to))
178 : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to)))
179 + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
180 >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from))
181 : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
182 + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to))))
187 grow_hunks(SCREEN *sp)
189 int start, end, shift;
190 int back_limit, forward_limit; /* limits for cells to fill */
191 int back_ref_limit, forward_ref_limit; /* limits for refrences */
196 * This is tricky part. We have unique pairs to use as anchors.
197 * Use these to deduce the presence of spans of identical lines.
203 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
205 for (; i < screen_lines(sp); i = next_hunk) {
207 shift = OLDNUM(sp, i) - i;
209 /* get forward limit */
211 while (i < screen_lines(sp)
212 && OLDNUM(sp, i) != _NEWINDEX
213 && OLDNUM(sp, i) - i == shift)
216 while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
220 if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
221 forward_ref_limit = i;
223 forward_ref_limit = OLDNUM(sp, i);
228 back_limit = back_ref_limit + (-shift);
229 while (i >= back_limit) {
230 if (newhash(sp)[i] == oldhash(sp)[i + shift]
231 || cost_effective(sp, i + shift, i, shift < 0)) {
232 OLDNUM(sp, 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(sp)[i] == oldhash(sp)[i + shift]
251 || cost_effective(sp, i + shift, i, shift > 0)) {
252 OLDNUM(sp, 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;
272 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
276 int start, shift, size;
278 if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
279 if (hashtab(SP_PARM))
280 free(hashtab(SP_PARM));
281 hashtab(SP_PARM) = typeMalloc(HASHMAP, (screen_lines(SP_PARM) + 1) * 2);
282 if (!hashtab(SP_PARM)) {
283 if (oldhash(SP_PARM)) {
284 FreeAndNull(oldhash(SP_PARM));
286 lines_alloc(SP_PARM) = 0;
289 lines_alloc(SP_PARM) = screen_lines(SP_PARM);
292 if (oldhash(SP_PARM) && newhash(SP_PARM)) {
293 /* re-hash only changed lines */
294 for (i = 0; i < screen_lines(SP_PARM); i++) {
295 if (PENDING(SP_PARM, i))
296 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
300 if (oldhash(SP_PARM) == 0)
301 oldhash(SP_PARM) = typeCalloc(unsigned long,
302 (unsigned) screen_lines(SP_PARM));
303 if (newhash(SP_PARM) == 0)
304 newhash(SP_PARM) = typeCalloc(unsigned long,
305 (unsigned) screen_lines(SP_PARM));
306 if (!oldhash(SP_PARM) || !newhash(SP_PARM))
307 return; /* malloc failure */
308 for (i = 0; i < screen_lines(SP_PARM); i++) {
309 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
310 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
315 for (i = 0; i < screen_lines(SP_PARM); i++) {
316 if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
317 fprintf(stderr, "error in newhash[%d]\n", i);
318 if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
319 fprintf(stderr, "error in oldhash[%d]\n", i);
324 * Set up and count line-hash values.
326 memset(hashtab(SP_PARM), '\0',
327 sizeof(*(hashtab(SP_PARM))) * (screen_lines(SP_PARM) + 1) * 2);
328 for (i = 0; i < screen_lines(SP_PARM); i++) {
329 unsigned long hashval = oldhash(SP_PARM)[i];
331 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
332 if (hsp->hashval == hashval)
334 hsp->hashval = hashval; /* in case this is a new entry */
338 for (i = 0; i < screen_lines(SP_PARM); i++) {
339 unsigned long hashval = newhash(SP_PARM)[i];
341 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
342 if (hsp->hashval == hashval)
344 hsp->hashval = hashval; /* in case this is a new entry */
348 OLDNUM(SP_PARM, i) = _NEWINDEX; /* initialize old indices array */
352 * Mark line pairs corresponding to unique hash pairs.
354 * We don't mark lines with offset 0, because it can make fail
355 * extending hunks by cost_effective. Otherwise, it does not
356 * have any side effects.
358 for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
359 if (hsp->oldcount == 1 && hsp->newcount == 1
360 && hsp->oldindex != hsp->newindex) {
361 TR(TRACE_UPDATE | TRACE_MOVE,
362 ("new line %d is hash-identical to old line %d (unique)",
363 hsp->newindex, hsp->oldindex));
364 OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
370 * Eliminate bad or impossible shifts -- this includes removing
371 * those hunks which could not grow because of conflicts, as well
372 * those which are to be moved too far, they are likely to destroy
375 for (i = 0; i < screen_lines(SP_PARM);) {
376 while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
378 if (i >= screen_lines(SP_PARM))
381 shift = OLDNUM(SP_PARM, i) - i;
383 while (i < screen_lines(SP_PARM)
384 && OLDNUM(SP_PARM, i) != _NEWINDEX
385 && OLDNUM(SP_PARM, i) - i == shift)
388 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
390 OLDNUM(SP_PARM, start) = _NEWINDEX;
396 /* After clearing invalid hunks, try grow the rest. */
404 NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
409 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
411 if (oldhash(SP_PARM))
412 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
417 _nc_make_oldhash(int i)
419 NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
424 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
429 if (!oldhash(SP_PARM))
432 size = sizeof(*(oldhash(SP_PARM))) * (bot - top + 1 - abs(n));
434 memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
435 for (i = bot; i > bot - n; i--)
436 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
438 memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
439 for (i = top; i < top - n; i++)
440 oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
446 _nc_scroll_oldhash(int n, int top, int bot)
448 NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
456 static const char *table[] =
458 "hashmap test-driver",
461 "l get initial line number vector",
462 "n use following letters as text of new lines",
463 "o use following letters as text of old lines",
464 "d dump state of test arrays",
465 "h apply hash mapper and see scroll optimization",
469 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
470 fprintf(stderr, "%s\n", table[n]);
474 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
476 char line[BUFSIZ], *st;
479 if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
481 (void) _nc_alloc_screen();
483 for (n = 0; n < screen_lines; n++) {
485 oldnums[n] = _NEWINDEX;
486 CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
489 if (isatty(fileno(stdin)))
493 _nc_tracing = TRACE_MOVE;
496 /* grab a test command */
497 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
501 case '#': /* comment */
502 (void) fputs(line, stderr);
505 case 'l': /* get initial line number vector */
506 for (n = 0; n < screen_lines; n++) {
508 oldnums[n] = _NEWINDEX;
511 st = strtok(line, " ");
513 oldnums[n++] = atoi(st);
515 ((st = strtok((char *) NULL, " ")) != 0);
518 case 'n': /* use following letters as text of new lines */
519 for (n = 0; n < screen_lines; n++)
520 CharOf(newtext[n][0]) = '.';
521 for (n = 0; n < screen_lines; n++)
522 if (line[n + 1] == '\n')
525 CharOf(newtext[n][0]) = line[n + 1];
528 case 'o': /* use following letters as text of old lines */
529 for (n = 0; n < screen_lines; n++)
530 CharOf(oldtext[n][0]) = '.';
531 for (n = 0; n < screen_lines; n++)
532 if (line[n + 1] == '\n')
535 CharOf(oldtext[n][0]) = line[n + 1];
538 case 'd': /* dump state of test arrays */
542 (void) fputs("Old lines: [", stdout);
543 for (n = 0; n < screen_lines; n++)
544 putchar(CharOf(oldtext[n][0]));
547 (void) fputs("New lines: [", stdout);
548 for (n = 0; n < screen_lines; n++)
549 putchar(CharOf(newtext[n][0]));
554 case 'h': /* apply hash mapper and see scroll optimization */
556 (void) fputs("Result:\n", stderr);
560 _nc_scroll_optimize();
561 (void) fputs("Done.\n", stderr);
570 _nc_free_and_exit(EXIT_SUCCESS);
576 #endif /* HASHDEBUG */
578 /* hashmap.c ends here */