ba53786a53499af351fd72c28f5e69ef7dd49743
[ncurses.git] / ncurses / tty / hashmap.c
1 /****************************************************************************
2  * Copyright (c) 1998-2001,2002 Free Software Foundation, Inc.                   *
3  *                                                                          *
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:                 *
11  *                                                                          *
12  * The above copyright notice and this permission notice shall be included  *
13  * in all copies or substantial portions of the Software.                   *
14  *                                                                          *
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.                               *
22  *                                                                          *
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       *
26  * authorization.                                                           *
27  ****************************************************************************/
28
29 /****************************************************************************
30  *  Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995               *
31  *     and: Eric S. Raymond <esr@snark.thyrsus.com>                         *
32  ****************************************************************************/
33
34 /******************************************************************************
35
36 NAME
37    hashmap.c -- fill in scramble vector based on text hashes
38
39 SYNOPSIS
40    void _nc_hash_map(void)
41
42 DESCRIPTION:
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).
47
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.
52
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.
56
57 HOW TO TEST THIS:
58
59 Use the following production:
60
61 hashmap: hashmap.c
62         $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
63
64 AUTHOR
65     Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
66     Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997
67
68 *****************************************************************************/
69
70 #include <curses.priv.h>
71 #include <term.h>               /* for back_color_erase */
72
73 MODULE_ID("$Id: hashmap.c,v 1.46 2002/09/07 18:13:15 tom Exp $")
74
75 #ifdef HASHDEBUG
76
77 # define _tracef        printf
78 # undef TR
79 # define TR(n, a)       if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
80 # undef screen_lines
81 # define screen_lines MAXLINES
82 # define TEXTWIDTH      1
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]
88 # define PENDING(n)     1
89
90 #else /* !HASHDEBUG */
91
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)
97
98 #endif /* !HASHDEBUG */
99
100 #define oldhash         (SP->oldhash)
101 #define newhash         (SP->newhash)
102 #define hashtab         (SP->hashtab)
103 #define lines_alloc     (SP->hashtab_len)
104
105 #if USE_WIDEC_SUPPORT
106 #define HASH_VAL(ch) (ch.chars[0])
107 #else
108 #define HASH_VAL(ch) (ch)
109 #endif
110
111 static inline unsigned long
112 hash(NCURSES_CH_T * text)
113 {
114     int i;
115     NCURSES_CH_T ch;
116     unsigned long result = 0;
117     for (i = TEXTWIDTH; i > 0; i--) {
118         ch = *text++;
119         result += (result << 5) + HASH_VAL(ch);
120     }
121     return result;
122 }
123
124 /* approximate update cost */
125 static int
126 update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to)
127 {
128     int cost = 0;
129     int i;
130
131     for (i = TEXTWIDTH; i > 0; i--)
132         if (!(CharEq(*from++, *to++)))
133             cost++;
134
135     return cost;
136 }
137
138 static int
139 update_cost_from_blank(NCURSES_CH_T * to)
140 {
141     int cost = 0;
142     int i;
143     NCURSES_CH_T blank = NewChar2(BLANK_TEXT, BLANK_ATTR);
144
145     if (back_color_erase)
146         AddAttr(blank, (AttrOf(stdscr->_nc_bkgd) & A_COLOR));
147
148     for (i = TEXTWIDTH; i > 0; i--)
149         if (!(CharEq(blank, *to++)))
150             cost++;
151
152     return cost;
153 }
154
155 /*
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.
158  */
159 static inline bool
160 cost_effective(const int from, const int to, const bool blank)
161 {
162     int new_from;
163
164     if (from == to)
165         return FALSE;
166
167     new_from = OLDNUM(from);
168     if (new_from == _NEWINDEX)
169         new_from = from;
170
171     /*
172      * On the left side of >= is the cost before moving;
173      * on the right side -- cost after moving.
174      */
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;
181 }
182
183 static void
184 grow_hunks(void)
185 {
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 */
189     int i;
190     int next_hunk;
191
192     /*
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.
195      */
196     back_limit = 0;
197     back_ref_limit = 0;
198
199     i = 0;
200     while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
201         i++;
202     for (; i < screen_lines; i = next_hunk) {
203         start = i;
204         shift = OLDNUM(i) - i;
205
206         /* get forward limit */
207         i = start + 1;
208         while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
209                == shift)
210             i++;
211         end = i;
212         while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
213             i++;
214         next_hunk = i;
215         forward_limit = i;
216         if (i >= screen_lines || OLDNUM(i) >= i)
217             forward_ref_limit = i;
218         else
219             forward_ref_limit = OLDNUM(i);
220
221         i = start - 1;
222         /* grow back */
223         if (shift < 0)
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)",
231                     i, i + shift));
232             } else {
233                 TR(TRACE_UPDATE | TRACE_MOVE,
234                    ("not connecting new line %d to old line %d (backward continuation)",
235                     i, i + shift));
236                 break;
237             }
238             i--;
239         }
240
241         i = end;
242         /* grow forward */
243         if (shift > 0)
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)",
251                     i, i + shift));
252             } else {
253                 TR(TRACE_UPDATE | TRACE_MOVE,
254                    ("not connecting new line %d to old line %d (forward continuation)",
255                     i, i + shift));
256                 break;
257             }
258             i++;
259         }
260
261         back_ref_limit = back_limit = i;
262         if (shift > 0)
263             back_ref_limit += shift;
264     }
265 }
266
267 NCURSES_EXPORT(void)
268 _nc_hash_map(void)
269 {
270     HASHMAP *sp;
271     register int i;
272     int start, shift, size;
273
274     if (screen_lines > lines_alloc) {
275         if (hashtab)
276             free(hashtab);
277         hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2);
278         if (!hashtab) {
279             if (oldhash) {
280                 FreeAndNull(oldhash);
281             }
282             lines_alloc = 0;
283             return;
284         }
285         lines_alloc = screen_lines;
286     }
287
288     if (oldhash && newhash) {
289         /* re-hash only changed lines */
290         for (i = 0; i < screen_lines; i++) {
291             if (PENDING(i))
292                 newhash[i] = hash(NEWTEXT(i));
293         }
294     } else {
295         /* re-hash all */
296         if (oldhash == 0)
297             oldhash = typeCalloc(unsigned long, (unsigned) screen_lines);
298         if (newhash == 0)
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));
305         }
306     }
307
308 #ifdef HASH_VERIFY
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);
314     }
315 #endif
316
317     /*
318      * Set up and count line-hash values.
319      */
320     memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2);
321     for (i = 0; i < screen_lines; i++) {
322         unsigned long hashval = oldhash[i];
323
324         for (sp = hashtab; sp->hashval; sp++)
325             if (sp->hashval == hashval)
326                 break;
327         sp->hashval = hashval;  /* in case this is a new entry */
328         sp->oldcount++;
329         sp->oldindex = i;
330     }
331     for (i = 0; i < screen_lines; i++) {
332         unsigned long hashval = newhash[i];
333
334         for (sp = hashtab; sp->hashval; sp++)
335             if (sp->hashval == hashval)
336                 break;
337         sp->hashval = hashval;  /* in case this is a new entry */
338         sp->newcount++;
339         sp->newindex = i;
340
341         OLDNUM(i) = _NEWINDEX;  /* initialize old indices array */
342     }
343
344     /*
345      * Mark line pairs corresponding to unique hash pairs.
346      *
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.
350      */
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;
358         }
359
360     grow_hunks();
361
362     /*
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
366      * more than carry.
367      */
368     for (i = 0; i < screen_lines;) {
369         while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
370             i++;
371         if (i >= screen_lines)
372             break;
373         start = i;
374         shift = OLDNUM(i) - i;
375         i++;
376         while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
377                == shift)
378             i++;
379         size = i - start;
380         if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
381             while (start < i) {
382                 OLDNUM(start) = _NEWINDEX;
383                 start++;
384             }
385         }
386     }
387
388     /* After clearing invalid hunks, try grow the rest. */
389     grow_hunks();
390 }
391
392 NCURSES_EXPORT(void)
393 _nc_make_oldhash(int i)
394 {
395     if (oldhash)
396         oldhash[i] = hash(OLDTEXT(i));
397 }
398
399 NCURSES_EXPORT(void)
400 _nc_scroll_oldhash(int n, int top, int bot)
401 {
402     size_t size;
403     int i;
404
405     if (!oldhash)
406         return;
407
408     size = sizeof(*oldhash) * (bot - top + 1 - abs(n));
409     if (n > 0) {
410         memmove(oldhash + top, oldhash + top + n, size);
411         for (i = bot; i > bot - n; i--)
412             oldhash[i] = hash(OLDTEXT(i));
413     } else {
414         memmove(oldhash + top - n, oldhash + top, size);
415         for (i = top; i < top - n; i++)
416             oldhash[i] = hash(OLDTEXT(i));
417     }
418 }
419
420 #ifdef HASHDEBUG
421 static void
422 usage(void)
423 {
424     static const char *table[] =
425     {
426         "hashmap test-driver",
427         "",
428         "#  comment",
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",
434         "?  this message"
435     };
436     size_t n;
437     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
438         fprintf(stderr, "%s\n", table[n]);
439 }
440
441 int
442 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
443 {
444     char line[BUFSIZ], *st;
445     int n;
446
447     SP = typeCalloc(SCREEN, 1);
448     for (n = 0; n < screen_lines; n++) {
449         reallines[n] = n;
450         oldnums[n] = _NEWINDEX;
451         oldtext[n][0] = newtext[n][0] = '.';
452     }
453
454     if (isatty(fileno(stdin)))
455         usage();
456
457 #ifdef TRACE
458     _nc_tracing = TRACE_MOVE;
459 #endif
460     for (;;) {
461         /* grab a test command */
462         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
463             exit(EXIT_SUCCESS);
464
465         switch (line[0]) {
466         case '#':               /* comment */
467             (void) fputs(line, stderr);
468             break;
469
470         case 'l':               /* get initial line number vector */
471             for (n = 0; n < screen_lines; n++) {
472                 reallines[n] = n;
473                 oldnums[n] = _NEWINDEX;
474             }
475             n = 0;
476             st = strtok(line, " ");
477             do {
478                 oldnums[n++] = atoi(st);
479             } while
480                 ((st = strtok((char *) NULL, " ")) != 0);
481             break;
482
483         case 'n':               /* use following letters as text of new lines */
484             for (n = 0; n < screen_lines; n++)
485                 newtext[n][0] = '.';
486             for (n = 0; n < screen_lines; n++)
487                 if (line[n + 1] == '\n')
488                     break;
489                 else
490                     newtext[n][0] = line[n + 1];
491             break;
492
493         case 'o':               /* use following letters as text of old lines */
494             for (n = 0; n < screen_lines; n++)
495                 oldtext[n][0] = '.';
496             for (n = 0; n < screen_lines; n++)
497                 if (line[n + 1] == '\n')
498                     break;
499                 else
500                     oldtext[n][0] = line[n + 1];
501             break;
502
503         case 'd':               /* dump state of test arrays */
504 #ifdef TRACE
505             _nc_linedump();
506 #endif
507             (void) fputs("Old lines: [", stdout);
508             for (n = 0; n < screen_lines; n++)
509                 putchar(oldtext[n][0]);
510             putchar(']');
511             putchar('\n');
512             (void) fputs("New lines: [", stdout);
513             for (n = 0; n < screen_lines; n++)
514                 putchar(newtext[n][0]);
515             putchar(']');
516             putchar('\n');
517             break;
518
519         case 'h':               /* apply hash mapper and see scroll optimization */
520             _nc_hash_map();
521             (void) fputs("Result:\n", stderr);
522 #ifdef TRACE
523             _nc_linedump();
524 #endif
525             _nc_scroll_optimize();
526             (void) fputs("Done.\n", stderr);
527             break;
528         case '?':
529             usage();
530             break;
531         }
532     }
533     return EXIT_SUCCESS;
534 }
535
536 #endif /* HASHDEBUG */
537
538 /* hashmap.c ends here */