1 /****************************************************************************
2 * Copyright (c) 1998-2002,2005 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.47 2005/01/29 21:27:58 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 #else /* !HASHDEBUG */
92 # define OLDNUM(n) _nc_oldnums[n]
93 # define OLDTEXT(n) curscr->_line[n].text
94 # define NEWTEXT(m) newscr->_line[m].text
95 # define TEXTWIDTH (curscr->_maxx+1)
96 # define PENDING(n) (newscr->_line[n].firstchar != _NOCHANGE)
98 #endif /* !HASHDEBUG */
100 #define oldhash (SP->oldhash)
101 #define newhash (SP->newhash)
102 #define hashtab (SP->hashtab)
103 #define lines_alloc (SP->hashtab_len)
105 #if USE_WIDEC_SUPPORT
106 #define HASH_VAL(ch) (ch.chars[0])
108 #define HASH_VAL(ch) (ch)
111 static inline unsigned long
112 hash(NCURSES_CH_T * text)
116 unsigned long result = 0;
117 for (i = TEXTWIDTH; i > 0; i--) {
119 result += (result << 5) + HASH_VAL(ch);
124 /* approximate update cost */
126 update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to)
131 for (i = TEXTWIDTH; i > 0; i--)
132 if (!(CharEq(*from++, *to++)))
139 update_cost_from_blank(NCURSES_CH_T * to)
143 NCURSES_CH_T blank = NewChar2(BLANK_TEXT, BLANK_ATTR);
145 if (back_color_erase)
146 SetPair(blank, GetPair(stdscr->_nc_bkgd));
148 for (i = TEXTWIDTH; i > 0; i--)
149 if (!(CharEq(blank, *to++)))
156 * Returns true when moving line 'from' to line 'to' seems to be cost
157 * effective. 'blank' indicates whether the line 'to' would become blank.
160 cost_effective(const int from, const int to, const bool blank)
167 new_from = OLDNUM(from);
168 if (new_from == _NEWINDEX)
172 * On the left side of >= is the cost before moving;
173 * on the right side -- cost after moving.
175 return (((blank ? update_cost_from_blank(NEWTEXT(to))
176 : update_cost(OLDTEXT(to), NEWTEXT(to)))
177 + update_cost(OLDTEXT(new_from), NEWTEXT(from)))
178 >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from))
179 : update_cost(OLDTEXT(new_from), NEWTEXT(from)))
180 + update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE;
186 int start, end, shift;
187 int back_limit, forward_limit; /* limits for cells to fill */
188 int back_ref_limit, forward_ref_limit; /* limits for refrences */
193 * This is tricky part. We have unique pairs to use as anchors.
194 * Use these to deduce the presence of spans of identical lines.
200 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
202 for (; i < screen_lines; i = next_hunk) {
204 shift = OLDNUM(i) - i;
206 /* get forward limit */
208 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
212 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
216 if (i >= screen_lines || OLDNUM(i) >= i)
217 forward_ref_limit = i;
219 forward_ref_limit = OLDNUM(i);
224 back_limit = back_ref_limit + (-shift);
225 while (i >= back_limit) {
226 if (newhash[i] == oldhash[i + shift]
227 || cost_effective(i + shift, i, shift < 0)) {
228 OLDNUM(i) = i + shift;
229 TR(TRACE_UPDATE | TRACE_MOVE,
230 ("connected new line %d to old line %d (backward continuation)",
233 TR(TRACE_UPDATE | TRACE_MOVE,
234 ("not connecting new line %d to old line %d (backward continuation)",
244 forward_limit = forward_ref_limit - shift;
245 while (i < forward_limit) {
246 if (newhash[i] == oldhash[i + shift]
247 || cost_effective(i + shift, i, shift > 0)) {
248 OLDNUM(i) = i + shift;
249 TR(TRACE_UPDATE | TRACE_MOVE,
250 ("connected new line %d to old line %d (forward continuation)",
253 TR(TRACE_UPDATE | TRACE_MOVE,
254 ("not connecting new line %d to old line %d (forward continuation)",
261 back_ref_limit = back_limit = i;
263 back_ref_limit += shift;
272 int start, shift, size;
274 if (screen_lines > lines_alloc) {
277 hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2);
280 FreeAndNull(oldhash);
285 lines_alloc = screen_lines;
288 if (oldhash && newhash) {
289 /* re-hash only changed lines */
290 for (i = 0; i < screen_lines; i++) {
292 newhash[i] = hash(NEWTEXT(i));
297 oldhash = typeCalloc(unsigned long, (unsigned) screen_lines);
299 newhash = typeCalloc(unsigned long, (unsigned) screen_lines);
300 if (!oldhash || !newhash)
301 return; /* malloc failure */
302 for (i = 0; i < screen_lines; i++) {
303 newhash[i] = hash(NEWTEXT(i));
304 oldhash[i] = hash(OLDTEXT(i));
309 for (i = 0; i < screen_lines; i++) {
310 if (newhash[i] != hash(NEWTEXT(i)))
311 fprintf(stderr, "error in newhash[%d]\n", i);
312 if (oldhash[i] != hash(OLDTEXT(i)))
313 fprintf(stderr, "error in oldhash[%d]\n", i);
318 * Set up and count line-hash values.
320 memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2);
321 for (i = 0; i < screen_lines; i++) {
322 unsigned long hashval = oldhash[i];
324 for (sp = hashtab; sp->hashval; sp++)
325 if (sp->hashval == hashval)
327 sp->hashval = hashval; /* in case this is a new entry */
331 for (i = 0; i < screen_lines; i++) {
332 unsigned long hashval = newhash[i];
334 for (sp = hashtab; sp->hashval; sp++)
335 if (sp->hashval == hashval)
337 sp->hashval = hashval; /* in case this is a new entry */
341 OLDNUM(i) = _NEWINDEX; /* initialize old indices array */
345 * Mark line pairs corresponding to unique hash pairs.
347 * We don't mark lines with offset 0, because it can make fail
348 * extending hunks by cost_effective. Otherwise, it does not
349 * have any side effects.
351 for (sp = hashtab; sp->hashval; sp++)
352 if (sp->oldcount == 1 && sp->newcount == 1
353 && sp->oldindex != sp->newindex) {
354 TR(TRACE_UPDATE | TRACE_MOVE,
355 ("new line %d is hash-identical to old line %d (unique)",
356 sp->newindex, sp->oldindex));
357 OLDNUM(sp->newindex) = sp->oldindex;
363 * Eliminate bad or impossible shifts -- this includes removing
364 * those hunks which could not grow because of conflicts, as well
365 * those which are to be moved too far, they are likely to destroy
368 for (i = 0; i < screen_lines;) {
369 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
371 if (i >= screen_lines)
374 shift = OLDNUM(i) - i;
376 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
380 if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
382 OLDNUM(start) = _NEWINDEX;
388 /* After clearing invalid hunks, try grow the rest. */
393 _nc_make_oldhash(int i)
396 oldhash[i] = hash(OLDTEXT(i));
400 _nc_scroll_oldhash(int n, int top, int bot)
408 size = sizeof(*oldhash) * (bot - top + 1 - abs(n));
410 memmove(oldhash + top, oldhash + top + n, size);
411 for (i = bot; i > bot - n; i--)
412 oldhash[i] = hash(OLDTEXT(i));
414 memmove(oldhash + top - n, oldhash + top, size);
415 for (i = top; i < top - n; i++)
416 oldhash[i] = hash(OLDTEXT(i));
424 static const char *table[] =
426 "hashmap test-driver",
429 "l get initial line number vector",
430 "n use following letters as text of new lines",
431 "o use following letters as text of old lines",
432 "d dump state of test arrays",
433 "h apply hash mapper and see scroll optimization",
437 for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
438 fprintf(stderr, "%s\n", table[n]);
442 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
444 char line[BUFSIZ], *st;
447 SP = typeCalloc(SCREEN, 1);
448 for (n = 0; n < screen_lines; n++) {
450 oldnums[n] = _NEWINDEX;
451 oldtext[n][0] = newtext[n][0] = '.';
454 if (isatty(fileno(stdin)))
458 _nc_tracing = TRACE_MOVE;
461 /* grab a test command */
462 if (fgets(line, sizeof(line), stdin) == (char *) NULL)
466 case '#': /* comment */
467 (void) fputs(line, stderr);
470 case 'l': /* get initial line number vector */
471 for (n = 0; n < screen_lines; n++) {
473 oldnums[n] = _NEWINDEX;
476 st = strtok(line, " ");
478 oldnums[n++] = atoi(st);
480 ((st = strtok((char *) NULL, " ")) != 0);
483 case 'n': /* use following letters as text of new lines */
484 for (n = 0; n < screen_lines; n++)
486 for (n = 0; n < screen_lines; n++)
487 if (line[n + 1] == '\n')
490 newtext[n][0] = line[n + 1];
493 case 'o': /* use following letters as text of old lines */
494 for (n = 0; n < screen_lines; n++)
496 for (n = 0; n < screen_lines; n++)
497 if (line[n + 1] == '\n')
500 oldtext[n][0] = line[n + 1];
503 case 'd': /* dump state of test arrays */
507 (void) fputs("Old lines: [", stdout);
508 for (n = 0; n < screen_lines; n++)
509 putchar(oldtext[n][0]);
512 (void) fputs("New lines: [", stdout);
513 for (n = 0; n < screen_lines; n++)
514 putchar(newtext[n][0]);
519 case 'h': /* apply hash mapper and see scroll optimization */
521 (void) fputs("Result:\n", stderr);
525 _nc_scroll_optimize();
526 (void) fputs("Done.\n", stderr);
536 #endif /* HASHDEBUG */
538 /* hashmap.c ends here */