f6a58bc6e112390578e3ad12ef9287e4748baaa1
[ncurses.git] / ncurses / tty / hashmap.c
1 /****************************************************************************
2  * Copyright (c) 1998 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.33 1999/03/18 02:09:45 Alexander.V.Lukyanov 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
103 static inline unsigned long hash(chtype *text)
104 {
105     int i;
106     chtype ch;
107     unsigned long result = 0;
108     for (i = TEXTWIDTH; i>0; i--)
109     {
110         ch = *text++;
111         result += (result<<5) + ch;
112     }
113     return result;
114 }
115
116 /* approximate update cost */
117 static int update_cost(chtype *from,chtype *to)
118 {
119     int cost=0;
120     int i;
121
122     for (i=TEXTWIDTH; i>0; i--)
123         if (*from++ != *to++)
124             cost++;
125
126     return cost;
127 }
128 static int update_cost_from_blank(chtype *to)
129 {
130     int cost=0;
131     int i;
132     chtype blank = BLANK;
133
134     if (back_color_erase)
135         blank |= (stdscr->_bkgd & A_COLOR);
136
137     for (i=TEXTWIDTH; i>0; i--)
138         if (blank != *to++)
139             cost++;
140
141     return cost;
142 }
143
144 /*
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.
147  */
148 static inline bool cost_effective(const int from, const int to, const bool blank)
149 {
150     int new_from;
151
152     if (from == to)
153         return FALSE;
154
155     new_from = OLDNUM(from);
156     if (new_from == _NEWINDEX)
157         new_from = from;
158
159     /*
160      * On the left side of >= is the cost before moving;
161      * on the right side -- cost after moving.
162      */
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;
169 }
170
171
172 typedef struct
173 {
174     unsigned long       hashval;
175     int         oldcount, newcount;
176     int         oldindex, newindex;
177 }
178     sym;
179
180 static sym *hashtab=0;
181 static int lines_alloc=0;
182
183 static void grow_hunks(void)
184 {
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 */
188     int i;
189     int next_hunk;
190
191     /*
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.
194      */
195     back_limit = 0;
196     back_ref_limit = 0;
197
198     i = 0;
199     while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
200         i++;
201     for ( ; i < screen_lines; i=next_hunk)
202     {
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 == shift)
209             i++;
210         end = i;
211         while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
212             i++;
213         next_hunk = i;
214         forward_limit = i;
215         if (i >= screen_lines || OLDNUM(i) >= i)
216             forward_ref_limit = i;
217         else
218             forward_ref_limit = OLDNUM(i);
219
220         i = start-1;
221         /* grow back */
222         if (shift < 0)
223             back_limit = back_ref_limit + (-shift);
224         while (i >= back_limit)
225         {
226             if(newhash[i] == oldhash[i+shift]
227             || cost_effective(i+shift, i, shift<0))
228             {
229                 OLDNUM(i) = i+shift;
230                 TR(TRACE_UPDATE | TRACE_MOVE,
231                    ("connected new line %d to old line %d (backward continuation)",
232                     i, i+shift));
233             }
234             else
235             {
236                 TR(TRACE_UPDATE | TRACE_MOVE,
237                    ("not connecting new line %d to old line %d (backward continuation)",
238                     i, i+shift));
239                 break;
240             }
241             i--;
242         }
243
244         i = end;
245         /* grow forward */
246         if (shift > 0)
247             forward_limit = forward_ref_limit - shift;
248         while (i < forward_limit)
249         {
250             if(newhash[i] == oldhash[i+shift]
251             || cost_effective(i+shift, i, shift>0))
252             {
253                 OLDNUM(i) = i+shift;
254                 TR(TRACE_UPDATE | TRACE_MOVE,
255                    ("connected new line %d to old line %d (forward continuation)",
256                     i, i+shift));
257             }
258             else
259             {
260                 TR(TRACE_UPDATE | TRACE_MOVE,
261                    ("not connecting new line %d to old line %d (forward continuation)",
262                     i, i+shift));
263                 break;
264             }
265             i++;
266         }
267
268         back_ref_limit = back_limit = i;
269         if (shift > 0)
270             back_ref_limit += shift;
271     }
272 }
273
274 void _nc_hash_map(void)
275 {
276     sym *sp;
277     register int i;
278     int start, shift, size;
279
280
281     if (screen_lines > lines_alloc)
282     {
283         if (hashtab)
284             free (hashtab);
285         hashtab = typeMalloc(sym, (screen_lines+1)*2);
286         if (!hashtab)
287         {
288             if (oldhash)
289                 FreeAndNull(oldhash);
290             lines_alloc = 0;
291             return;
292         }
293         lines_alloc = screen_lines;
294     }
295
296     if (oldhash && newhash)
297     {
298         /* re-hash only changed lines */
299         for (i = 0; i < screen_lines; i++)
300         {
301             if (PENDING(i))
302                 newhash[i] = hash(NEWTEXT(i));
303         }
304     }
305     else
306     {
307         /* re-hash all */
308         if (oldhash == 0)
309             oldhash = typeCalloc (unsigned long, screen_lines);
310         if (newhash == 0)
311             newhash = typeCalloc (unsigned long, screen_lines);
312         if (!oldhash || !newhash)
313             return; /* malloc failure */
314         for (i = 0; i < screen_lines; i++)
315         {
316             newhash[i] = hash(NEWTEXT(i));
317             oldhash[i] = hash(OLDTEXT(i));
318         }
319     }
320
321 #ifdef HASH_VERIFY
322     for (i = 0; i < screen_lines; i++)
323     {
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);
328     }
329 #endif
330
331     /*
332      * Set up and count line-hash values.
333      */
334     memset(hashtab, '\0', sizeof(*hashtab)*(screen_lines+1)*2);
335     for (i = 0; i < screen_lines; i++)
336     {
337         unsigned long hashval = oldhash[i];
338
339         for (sp = hashtab; sp->hashval; sp++)
340             if (sp->hashval == hashval)
341                 break;
342         sp->hashval = hashval;  /* in case this is a new entry */
343         sp->oldcount++;
344         sp->oldindex = i;
345     }
346     for (i = 0; i < screen_lines; i++)
347     {
348         unsigned long hashval = newhash[i];
349
350         for (sp = hashtab; sp->hashval; sp++)
351             if (sp->hashval == hashval)
352                 break;
353         sp->hashval = hashval;  /* in case this is a new entry */
354         sp->newcount++;
355         sp->newindex = i;
356
357         OLDNUM(i) = _NEWINDEX;  /* initialize old indices array */
358     }
359
360     /*
361      * Mark line pairs corresponding to unique hash pairs.
362      *
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.
366      */
367     for (sp = hashtab; sp->hashval; sp++)
368         if (sp->oldcount == 1 && sp->newcount == 1
369             && sp->oldindex != sp->newindex)
370         {
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;
375         }
376
377     grow_hunks();
378
379     /*
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
383      * more than carry.
384      */
385     for (i = 0; i < screen_lines; )
386     {
387         while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
388             i++;
389         if (i >= screen_lines)
390             break;
391         start = i;
392         shift = OLDNUM(i) - i;
393         i++;
394         while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift)
395             i++;
396         size = i - start;
397         if (size < 3 || size+min(size/8,2) < abs(shift))
398         {
399             while (start < i)
400             {
401                 OLDNUM(start) = _NEWINDEX;
402                 start++;
403             }
404         }
405     }
406
407     /* After clearing invalid hunks, try grow the rest. */
408     grow_hunks();
409
410 #if NO_LEAKS
411     FreeAndNull(hashtab);
412     lines_alloc = 0;
413 #endif
414 }
415
416 void _nc_make_oldhash(int i)
417 {
418     if (oldhash)
419         oldhash[i] = hash(OLDTEXT(i));
420 }
421
422 void _nc_scroll_oldhash(int n, int top, int bot)
423 {
424     int size;
425     int i;
426
427     if (!oldhash)
428         return;
429
430     size = sizeof(*oldhash) * (bot-top+1-abs(n));
431     if (n > 0)
432     {
433         memmove (oldhash+top, oldhash+top+n, size);
434         for (i = bot; i > bot-n; i--)
435             oldhash[i] = hash(OLDTEXT(i));
436     }
437     else
438     {
439         memmove (oldhash+top-n, oldhash+top, size);
440         for (i = top; i < top-n; i++)
441             oldhash[i] = hash(OLDTEXT(i));
442     }
443 }
444
445
446 #ifdef HASHDEBUG
447 static void
448 usage(void)
449 {
450     static const char *table[] = {
451         "hashmap test-driver",
452         "",
453         "#  comment",
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",
459         "?  this message"
460     };
461     size_t n;
462     for (n = 0; n < sizeof(table)/sizeof(table[0]); n++)
463         fprintf(stderr, "%s\n", table[n]);
464 }
465
466 int
467 main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED)
468 {
469     char        line[BUFSIZ], *st;
470     int         n;
471
472     SP = typeCalloc(SCREEN,1);
473     for (n = 0; n < screen_lines; n++)
474     {
475         reallines[n] = n;
476         oldnums[n] = _NEWINDEX;
477         oldtext[n][0] = newtext[n][0] = '.';
478     }
479
480     if (isatty(fileno(stdin)))
481         usage();
482
483 #ifdef TRACE
484     _nc_tracing = TRACE_MOVE;
485 #endif
486     for (;;)
487     {
488         /* grab a test command */
489         if (fgets(line, sizeof(line), stdin) == (char *)NULL)
490             exit(EXIT_SUCCESS);
491
492         switch(line[0])
493         {
494         case '#':       /* comment */
495             (void) fputs(line, stderr);
496             break;
497
498         case 'l':       /* get initial line number vector */
499             for (n = 0; n < screen_lines; n++)
500             {
501                 reallines[n] = n;
502                 oldnums[n] = _NEWINDEX;
503             }
504             n = 0;
505             st = strtok(line, " ");
506             do {
507                 oldnums[n++] = atoi(st);
508             } while
509                 ((st = strtok((char *)NULL, " ")) != 0);
510             break;
511
512         case 'n':       /* use following letters as text of new lines */
513             for (n = 0; n < screen_lines; n++)
514                 newtext[n][0] = '.';
515             for (n = 0; n < screen_lines; n++)
516                 if (line[n+1] == '\n')
517                     break;
518                 else
519                     newtext[n][0] = line[n+1];
520             break;
521
522         case 'o':       /* use following letters as text of old lines */
523             for (n = 0; n < screen_lines; n++)
524                 oldtext[n][0] = '.';
525             for (n = 0; n < screen_lines; n++)
526                 if (line[n+1] == '\n')
527                     break;
528                 else
529                     oldtext[n][0] = line[n+1];
530             break;
531
532         case 'd':       /* dump state of test arrays */
533 #ifdef TRACE
534             _nc_linedump();
535 #endif
536             (void) fputs("Old lines: [", stdout);
537             for (n = 0; n < screen_lines; n++)
538                 putchar(oldtext[n][0]);
539             putchar(']');
540             putchar('\n');
541             (void) fputs("New lines: [", stdout);
542             for (n = 0; n < screen_lines; n++)
543                 putchar(newtext[n][0]);
544             putchar(']');
545             putchar('\n');
546             break;
547
548         case 'h':       /* apply hash mapper and see scroll optimization */
549             _nc_hash_map();
550             (void) fputs("Result:\n", stderr);
551 #ifdef TRACE
552             _nc_linedump();
553 #endif
554             _nc_scroll_optimize();
555             (void) fputs("Done.\n", stderr);
556             break;
557         case '?':
558             usage();
559             break;
560         }
561     }
562     return EXIT_SUCCESS;
563 }
564
565 #endif /* HASHDEBUG */
566
567 /* hashmap.c ends here */