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.56 2007/10/13 18:47:25 Miroslav.Lichvar 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 NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH];
85 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH];
86 # define OLDNUM(n) oldnums[n]
87 # define OLDTEXT(n) oldtext[n]
88 # define NEWTEXT(m) newtext[m]
91 #else /* !HASHDEBUG */
93 # define OLDNUM(n) SP->_oldnum_list[n]
94 # define OLDTEXT(n) curscr->_line[n].text
95 # define NEWTEXT(m) newscr->_line[m].text
96 # define TEXTWIDTH (curscr->_maxx+1)
97 # define PENDING(n) (newscr->_line[n].firstchar != _NOCHANGE)
99 #endif /* !HASHDEBUG */
101 #define oldhash (SP->oldhash)
102 #define newhash (SP->newhash)
103 #define hashtab (SP->hashtab)
104 #define lines_alloc (SP->hashtab_len)
106 #if USE_WIDEC_SUPPORT
107 #define HASH_VAL(ch) (ch.chars[0])
109 #define HASH_VAL(ch) (ch)
112 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
114 static NCURSES_INLINE unsigned long
115 hash(NCURSES_CH_T * text)
119 unsigned long result = 0;
120 for (i = TEXTWIDTH; i > 0; i--) {
122 result += (result << 5) + HASH_VAL(ch);
127 /* approximate update cost */
129 update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to)
134 for (i = TEXTWIDTH; i > 0; i--, from++, to++)
135 if (!(CharEq(*from, *to)))
142 update_cost_from_blank(NCURSES_CH_T * to)
146 NCURSES_CH_T blank = blankchar;
148 if (back_color_erase)
149 SetPair(blank, GetPair(stdscr->_nc_bkgd));
151 for (i = TEXTWIDTH; i > 0; i--, to++)
152 if (!(CharEq(blank, *to)))
159 * Returns true when moving line 'from' to line 'to' seems to be cost
160 * effective. 'blank' indicates whether the line 'to' would become blank.
162 static NCURSES_INLINE bool
163 cost_effective(const int from, const int to, const bool blank)
170 new_from = OLDNUM(from);
171 if (new_from == _NEWINDEX)
175 * On the left side of >= is the cost before moving;
176 * on the right side -- cost after moving.
178 return (((blank ? update_cost_from_blank(NEWTEXT(to))
179 : update_cost(OLDTEXT(to), NEWTEXT(to)))
180 + update_cost(OLDTEXT(new_from), NEWTEXT(from)))
181 >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from))
182 : update_cost(OLDTEXT(new_from), NEWTEXT(from)))
183 + update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE;
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 && OLDNUM(i) == _NEWINDEX)
205 for (; i < screen_lines; i = next_hunk) {
207 shift = OLDNUM(i) - i;
209 /* get forward limit */
211 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
215 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
219 if (i >= screen_lines || OLDNUM(i) >= i)
220 forward_ref_limit = i;
222 forward_ref_limit = OLDNUM(i);
227 back_limit = back_ref_limit + (-shift);
228 while (i >= back_limit) {
229 if (newhash[i] == oldhash[i + shift]
230 || cost_effective(i + shift, i, shift < 0)) {
231 OLDNUM(i) = i + shift;
232 TR(TRACE_UPDATE | TRACE_MOVE,
233 ("connected new line %d to old line %d (backward continuation)",
236 TR(TRACE_UPDATE | TRACE_MOVE,
237 ("not connecting new line %d to old line %d (backward continuation)",
247 forward_limit = forward_ref_limit - shift;
248 while (i < forward_limit) {
249 if (newhash[i] == oldhash[i + shift]
250 || cost_effective(i + shift, i, shift > 0)) {
251 OLDNUM(i) = i + shift;
252 TR(TRACE_UPDATE | TRACE_MOVE,
253 ("connected new line %d to old line %d (forward continuation)",
256 TR(TRACE_UPDATE | TRACE_MOVE,
257 ("not connecting new line %d to old line %d (forward continuation)",
264 back_ref_limit = back_limit = i;
266 back_ref_limit += shift;
275 int start, shift, size;
277 if (screen_lines > lines_alloc) {
280 hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2);
283 FreeAndNull(oldhash);
288 lines_alloc = screen_lines;
291 if (oldhash && newhash) {
292 /* re-hash only changed lines */
293 for (i = 0; i < screen_lines; i++) {
295 newhash[i] = hash(NEWTEXT(i));
300 oldhash = typeCalloc(unsigned long, (unsigned) screen_lines);
302 newhash = typeCalloc(unsigned long, (unsigned) screen_lines);
303 if (!oldhash || !newhash)
304 return; /* malloc failure */
305 for (i = 0; i < screen_lines; i++) {
306 newhash[i] = hash(NEWTEXT(i));
307 oldhash[i] = hash(OLDTEXT(i));
312 for (i = 0; i < screen_lines; i++) {
313 if (newhash[i] != hash(NEWTEXT(i)))
314 fprintf(stderr, "error in newhash[%d]\n", i);
315 if (oldhash[i] != hash(OLDTEXT(i)))
316 fprintf(stderr, "error in oldhash[%d]\n", i);
321 * Set up and count line-hash values.
323 memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2);
324 for (i = 0; i < screen_lines; i++) {
325 unsigned long hashval = oldhash[i];
327 for (sp = hashtab; sp->hashval; sp++)
328 if (sp->hashval == hashval)
330 sp->hashval = hashval; /* in case this is a new entry */
334 for (i = 0; i < screen_lines; i++) {
335 unsigned long hashval = newhash[i];
337 for (sp = hashtab; sp->hashval; sp++)
338 if (sp->hashval == hashval)
340 sp->hashval = hashval; /* in case this is a new entry */
344 OLDNUM(i) = _NEWINDEX; /* initialize old indices array */
348 * Mark line pairs corresponding to unique hash pairs.
350 * We don't mark lines with offset 0, because it can make fail
351 * extending hunks by cost_effective. Otherwise, it does not
352 * have any side effects.
354 for (sp = hashtab; sp->hashval; sp++)
355 if (sp->oldcount == 1 && sp->newcount == 1
356 && sp->oldindex != sp->newindex) {
357 TR(TRACE_UPDATE | TRACE_MOVE,
358 ("new line %d is hash-identical to old line %d (unique)",
359 sp->newindex, sp->oldindex));
360 OLDNUM(sp->newindex) = sp->oldindex;
366 * Eliminate bad or impossible shifts -- this includes removing
367 * those hunks which could not grow because of conflicts, as well
368 * those which are to be moved too far, they are likely to destroy
371 for (i = 0; i < screen_lines;) {
372 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
374 if (i >= screen_lines)
377 shift = OLDNUM(i) - i;
379 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
383 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
385 OLDNUM(start) = _NEWINDEX;
391 /* After clearing invalid hunks, try grow the rest. */
396 _nc_make_oldhash(int i)
399 oldhash[i] = hash(OLDTEXT(i));
403 _nc_scroll_oldhash(int n, int top, int bot)
411 size = sizeof(*oldhash) * (bot - top + 1 - abs(n));
413 memmove(oldhash + top, oldhash + top + n, size);
414 for (i = bot; i > bot - n; i--)
415 oldhash[i] = hash(OLDTEXT(i));
417 memmove(oldhash + top - n, oldhash + top, size);
418 for (i = top; i < top - n; i++)
419 oldhash[i] = hash(OLDTEXT(i));
427 static const char *table[] =
429 "hashmap test-driver",
432 "l get initial line number vector",
433 "n use following letters as text of new lines",
434 "o use following letters as text of old lines",
435 "d dump state of test arrays",
436 "h apply hash mapper and see scroll optimization",
440 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
441 fprintf(stderr, "%s\n", table[n]);
445 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
447 char line[BUFSIZ], *st;
450 if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
452 (void) _nc_alloc_screen();
454 for (n = 0; n < screen_lines; n++) {
456 oldnums[n] = _NEWINDEX;
457 CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
460 if (isatty(fileno(stdin)))
464 _nc_tracing = TRACE_MOVE;
467 /* grab a test command */
468 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
472 case '#': /* comment */
473 (void) fputs(line, stderr);
476 case 'l': /* get initial line number vector */
477 for (n = 0; n < screen_lines; n++) {
479 oldnums[n] = _NEWINDEX;
482 st = strtok(line, " ");
484 oldnums[n++] = atoi(st);
486 ((st = strtok((char *) NULL, " ")) != 0);
489 case 'n': /* use following letters as text of new lines */
490 for (n = 0; n < screen_lines; n++)
491 CharOf(newtext[n][0]) = '.';
492 for (n = 0; n < screen_lines; n++)
493 if (line[n + 1] == '\n')
496 CharOf(newtext[n][0]) = line[n + 1];
499 case 'o': /* use following letters as text of old lines */
500 for (n = 0; n < screen_lines; n++)
501 CharOf(oldtext[n][0]) = '.';
502 for (n = 0; n < screen_lines; n++)
503 if (line[n + 1] == '\n')
506 CharOf(oldtext[n][0]) = line[n + 1];
509 case 'd': /* dump state of test arrays */
513 (void) fputs("Old lines: [", stdout);
514 for (n = 0; n < screen_lines; n++)
515 putchar(CharOf(oldtext[n][0]));
518 (void) fputs("New lines: [", stdout);
519 for (n = 0; n < screen_lines; n++)
520 putchar(CharOf(newtext[n][0]));
525 case 'h': /* apply hash mapper and see scroll optimization */
527 (void) fputs("Result:\n", stderr);
531 _nc_scroll_optimize();
532 (void) fputs("Done.\n", stderr);
541 _nc_free_and_exit(EXIT_SUCCESS);
547 #endif /* HASHDEBUG */
549 /* hashmap.c ends here */