1 /****************************************************************************
2 * Copyright (c) 1998 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.33 1999/03/18 02:09:45 Alexander.V.Lukyanov 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)
103 static inline unsigned long hash(chtype *text)
107 unsigned long result = 0;
108 for (i = TEXTWIDTH; i>0; i--)
111 result += (result<<5) + ch;
116 /* approximate update cost */
117 static int update_cost(chtype *from,chtype *to)
122 for (i=TEXTWIDTH; i>0; i--)
123 if (*from++ != *to++)
128 static int update_cost_from_blank(chtype *to)
132 chtype blank = BLANK;
134 if (back_color_erase)
135 blank |= (stdscr->_bkgd & A_COLOR);
137 for (i=TEXTWIDTH; i>0; i--)
145 * Returns true when moving line 'from' to line 'to' seems to be cost
146 * effective. 'blank' indicates whether the line 'to' would become blank.
148 static inline bool cost_effective(const int from, const int to, const bool blank)
155 new_from = OLDNUM(from);
156 if (new_from == _NEWINDEX)
160 * On the left side of >= is the cost before moving;
161 * on the right side -- cost after moving.
163 return (((blank ? update_cost_from_blank(NEWTEXT(to))
164 : update_cost(OLDTEXT(to),NEWTEXT(to)))
165 + update_cost(OLDTEXT(new_from),NEWTEXT(from)))
166 >= ((new_from==from ? update_cost_from_blank(NEWTEXT(from))
167 : update_cost(OLDTEXT(new_from),NEWTEXT(from)))
168 + update_cost(OLDTEXT(from),NEWTEXT(to)))) ? TRUE : FALSE;
174 unsigned long hashval;
175 int oldcount, newcount;
176 int oldindex, newindex;
180 static sym *hashtab=0;
181 static int lines_alloc=0;
183 static void grow_hunks(void)
185 int start, end, shift;
186 int back_limit, forward_limit; /* limits for cells to fill */
187 int back_ref_limit, forward_ref_limit; /* limits for refrences */
192 * This is tricky part. We have unique pairs to use as anchors.
193 * Use these to deduce the presence of spans of identical lines.
199 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
201 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 == shift)
211 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
215 if (i >= screen_lines || OLDNUM(i) >= i)
216 forward_ref_limit = i;
218 forward_ref_limit = OLDNUM(i);
223 back_limit = back_ref_limit + (-shift);
224 while (i >= back_limit)
226 if(newhash[i] == oldhash[i+shift]
227 || cost_effective(i+shift, i, shift<0))
230 TR(TRACE_UPDATE | TRACE_MOVE,
231 ("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)
250 if(newhash[i] == oldhash[i+shift]
251 || cost_effective(i+shift, i, shift>0))
254 TR(TRACE_UPDATE | TRACE_MOVE,
255 ("connected new line %d to old line %d (forward continuation)",
260 TR(TRACE_UPDATE | TRACE_MOVE,
261 ("not connecting new line %d to old line %d (forward continuation)",
268 back_ref_limit = back_limit = i;
270 back_ref_limit += shift;
274 void _nc_hash_map(void)
278 int start, shift, size;
281 if (screen_lines > lines_alloc)
285 hashtab = typeMalloc(sym, (screen_lines+1)*2);
289 FreeAndNull(oldhash);
293 lines_alloc = screen_lines;
296 if (oldhash && newhash)
298 /* re-hash only changed lines */
299 for (i = 0; i < screen_lines; i++)
302 newhash[i] = hash(NEWTEXT(i));
309 oldhash = typeCalloc (unsigned long, screen_lines);
311 newhash = typeCalloc (unsigned long, screen_lines);
312 if (!oldhash || !newhash)
313 return; /* malloc failure */
314 for (i = 0; i < screen_lines; i++)
316 newhash[i] = hash(NEWTEXT(i));
317 oldhash[i] = hash(OLDTEXT(i));
322 for (i = 0; i < screen_lines; i++)
324 if(newhash[i] != hash(NEWTEXT(i)))
325 fprintf(stderr,"error in newhash[%d]\n",i);
326 if(oldhash[i] != hash(OLDTEXT(i)))
327 fprintf(stderr,"error in oldhash[%d]\n",i);
332 * Set up and count line-hash values.
334 memset(hashtab, '\0', sizeof(*hashtab)*(screen_lines+1)*2);
335 for (i = 0; i < screen_lines; i++)
337 unsigned long hashval = oldhash[i];
339 for (sp = hashtab; sp->hashval; sp++)
340 if (sp->hashval == hashval)
342 sp->hashval = hashval; /* in case this is a new entry */
346 for (i = 0; i < screen_lines; i++)
348 unsigned long hashval = newhash[i];
350 for (sp = hashtab; sp->hashval; sp++)
351 if (sp->hashval == hashval)
353 sp->hashval = hashval; /* in case this is a new entry */
357 OLDNUM(i) = _NEWINDEX; /* initialize old indices array */
361 * Mark line pairs corresponding to unique hash pairs.
363 * We don't mark lines with offset 0, because it can make fail
364 * extending hunks by cost_effective. Otherwise, it does not
365 * have any side effects.
367 for (sp = hashtab; sp->hashval; sp++)
368 if (sp->oldcount == 1 && sp->newcount == 1
369 && sp->oldindex != sp->newindex)
371 TR(TRACE_UPDATE | TRACE_MOVE,
372 ("new line %d is hash-identical to old line %d (unique)",
373 sp->newindex, sp->oldindex));
374 OLDNUM(sp->newindex) = sp->oldindex;
380 * Eliminate bad or impossible shifts -- this includes removing
381 * those hunks which could not grow because of conflicts, as well
382 * those which are to be moved too far, they are likely to destroy
385 for (i = 0; i < screen_lines; )
387 while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
389 if (i >= screen_lines)
392 shift = OLDNUM(i) - i;
394 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift)
397 if (size < 3 || size+min(size/8,2) < abs(shift))
401 OLDNUM(start) = _NEWINDEX;
407 /* After clearing invalid hunks, try grow the rest. */
411 FreeAndNull(hashtab);
416 void _nc_make_oldhash(int i)
419 oldhash[i] = hash(OLDTEXT(i));
422 void _nc_scroll_oldhash(int n, int top, int bot)
430 size = sizeof(*oldhash) * (bot-top+1-abs(n));
433 memmove (oldhash+top, oldhash+top+n, size);
434 for (i = bot; i > bot-n; i--)
435 oldhash[i] = hash(OLDTEXT(i));
439 memmove (oldhash+top-n, oldhash+top, size);
440 for (i = top; i < top-n; i++)
441 oldhash[i] = hash(OLDTEXT(i));
450 static const char *table[] = {
451 "hashmap test-driver",
454 "l get initial line number vector",
455 "n use following letters as text of new lines",
456 "o use following letters as text of old lines",
457 "d dump state of test arrays",
458 "h apply hash mapper and see scroll optimization",
462 for (n = 0; n < sizeof(table)/sizeof(table[0]); n++)
463 fprintf(stderr, "%s\n", table[n]);
467 main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED)
469 char line[BUFSIZ], *st;
472 SP = typeCalloc(SCREEN,1);
473 for (n = 0; n < screen_lines; n++)
476 oldnums[n] = _NEWINDEX;
477 oldtext[n][0] = newtext[n][0] = '.';
480 if (isatty(fileno(stdin)))
484 _nc_tracing = TRACE_MOVE;
488 /* grab a test command */
489 if (fgets(line, sizeof(line), stdin) == (char *)NULL)
494 case '#': /* comment */
495 (void) fputs(line, stderr);
498 case 'l': /* get initial line number vector */
499 for (n = 0; n < screen_lines; n++)
502 oldnums[n] = _NEWINDEX;
505 st = strtok(line, " ");
507 oldnums[n++] = atoi(st);
509 ((st = strtok((char *)NULL, " ")) != 0);
512 case 'n': /* use following letters as text of new lines */
513 for (n = 0; n < screen_lines; n++)
515 for (n = 0; n < screen_lines; n++)
516 if (line[n+1] == '\n')
519 newtext[n][0] = line[n+1];
522 case 'o': /* use following letters as text of old lines */
523 for (n = 0; n < screen_lines; n++)
525 for (n = 0; n < screen_lines; n++)
526 if (line[n+1] == '\n')
529 oldtext[n][0] = line[n+1];
532 case 'd': /* dump state of test arrays */
536 (void) fputs("Old lines: [", stdout);
537 for (n = 0; n < screen_lines; n++)
538 putchar(oldtext[n][0]);
541 (void) fputs("New lines: [", stdout);
542 for (n = 0; n < screen_lines; n++)
543 putchar(newtext[n][0]);
548 case 'h': /* apply hash mapper and see scroll optimization */
550 (void) fputs("Result:\n", stderr);
554 _nc_scroll_optimize();
555 (void) fputs("Done.\n", stderr);
565 #endif /* HASHDEBUG */
567 /* hashmap.c ends here */