ncurses 4.2
[ncurses.git] / ncurses / 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
67 *****************************************************************************/
68
69 #include <curses.priv.h>
70
71 MODULE_ID("$Id: hashmap.c,v 1.24 1998/02/11 12:13:55 tom Exp $")
72
73 #ifdef HASHDEBUG
74 #define TEXTWIDTH       1
75 int oldnums[MAXLINES], reallines[MAXLINES];
76 static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH];
77 #define OLDNUM(n)       oldnums[n]
78 #define REAL(m)         reallines[m]
79 #define OLDTEXT(n)      oldtext[n]
80 #define NEWTEXT(m)      newtext[m]
81 #undef T
82 #define T(x)            (void) printf x ; (void) putchar('\n');
83 #else
84 #include <curses.h>
85 #define OLDNUM(n)       newscr->_line[n].oldindex
86 #define REAL(m)         curscr->_line[m].oldindex
87 #define OLDTEXT(n)      curscr->_line[n].text
88 #define NEWTEXT(m)      newscr->_line[m].text
89 #define TEXTWIDTH       (curscr->_maxx+1)
90 #ifndef _NEWINDEX
91 #define _NEWINDEX       -1
92 #endif /* _NEWINDEX */
93 #endif /* HASHDEBUG */
94
95 static inline unsigned long hash(chtype *text)
96 {
97     int i;
98     chtype ch;
99     unsigned long result = 0;
100     for (i = TEXTWIDTH; i>0; i--)
101     {
102         ch = *text++;
103         result += (result<<5) + ch + (ch>>16);
104     }
105     return result;
106 }
107
108 /* approximate update cost */
109 static int update_cost(chtype *from,chtype *to)
110 {
111     int cost=0;
112     int i;
113
114     for (i=TEXTWIDTH; i>0; i--)
115         if (*from++ != *to++)
116             cost++;
117
118     return cost;
119 }
120 static int update_cost_from_blank(chtype *to)
121 {
122     int cost=0;
123     int i;
124
125     /* FIXME: ClrBlank should be used */
126     for (i=TEXTWIDTH; i>0; i--)
127         if (BLANK != *to++)
128             cost++;
129
130     return cost;
131 }
132
133 /*
134  * Returns true when moving line 'from' to line 'to' seems to be cost
135  * effective. 'blank' indicates whether the line 'to' would become blank.
136  */
137 static inline bool cost_effective(const int from, const int to, const bool blank)
138 {
139     int new_from;
140
141     if (from == to)
142         return FALSE;
143
144     new_from = OLDNUM(from);
145     if (new_from == _NEWINDEX)
146         new_from = from;
147
148     /* 
149      * On the left side of >= is the cost before moving;
150      * on the right side -- cost after moving.
151      */
152     return (((blank ? update_cost_from_blank(NEWTEXT(to))
153                     : update_cost(OLDTEXT(to),NEWTEXT(to)))
154              + update_cost(OLDTEXT(new_from),NEWTEXT(from)))
155          >= ((new_from==from ? update_cost_from_blank(NEWTEXT(from))
156                              : update_cost(OLDTEXT(new_from),NEWTEXT(from)))
157              + update_cost(OLDTEXT(from),NEWTEXT(to)))) ? TRUE : FALSE;
158 }
159
160
161 typedef struct
162 {
163     unsigned long       hashval;
164     int         oldcount, newcount;
165     int         oldindex, newindex;
166 }
167     sym;
168
169 static sym *hashtab=0;
170 static int lines_alloc=0; 
171 static long *oldhash=0;
172 static long *newhash=0;
173
174 static void grow_hunks(void)
175 {
176     int start, end, shift;
177     int back_limit, forward_limit;          /* limits for cells to fill */
178     int back_ref_limit, forward_ref_limit;  /* limits for refrences */
179     int i;
180     int next_hunk;
181
182     /*
183      * This is tricky part.  We have unique pairs to use as anchors.
184      * Use these to deduce the presence of spans of identical lines.
185      */
186     back_limit = 0;
187     back_ref_limit = 0;
188
189     i = 0;
190     while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
191         i++;
192     for ( ; i < screen_lines; i=next_hunk)
193     {
194         start = i;
195         shift = OLDNUM(i) - i;
196         
197         /* get forward limit */
198         i = start+1;
199         while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift)
200             i++;
201         end = i;
202         while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
203             i++;
204         next_hunk = i;
205         forward_limit = i;
206         if (i >= screen_lines || OLDNUM(i) >= i)
207             forward_ref_limit = i;
208         else
209             forward_ref_limit = OLDNUM(i);
210
211         i = start-1;
212         /* grow back */
213         if (shift < 0)
214             back_limit = back_ref_limit + (-shift);
215         while (i >= back_limit)
216         {
217             if(newhash[i] == oldhash[i+shift]
218             || cost_effective(i+shift, i, shift<0))
219             {
220                 OLDNUM(i) = i+shift;
221                 TR(TRACE_UPDATE | TRACE_MOVE,
222                    ("connected new line %d to old line %d (backward continuation)",
223                     i, i+shift));
224             }
225             else
226             {
227                 TR(TRACE_UPDATE | TRACE_MOVE,
228                    ("not connecting new line %d to old line %d (backward continuation)",
229                     i, i+shift));
230                 break;
231             }
232             i--;
233         }
234         
235         i = end;
236         /* grow forward */
237         if (shift > 0)
238             forward_limit = forward_ref_limit - shift;
239         while (i < forward_limit)
240         {
241             if(newhash[i] == oldhash[i+shift]
242             || cost_effective(i+shift, i, shift>0))
243             {
244                 OLDNUM(i) = i+shift;
245                 TR(TRACE_UPDATE | TRACE_MOVE,
246                    ("connected new line %d to old line %d (forward continuation)",
247                     i, i+shift));
248             }
249             else
250             {
251                 TR(TRACE_UPDATE | TRACE_MOVE,
252                    ("not connecting new line %d to old line %d (forward continuation)",
253                     i, i+shift));
254                 break;
255             }
256             i++;
257         }
258         
259         back_ref_limit = back_limit = i;
260         if (shift > 0)
261             back_ref_limit += shift;
262     }
263 }
264
265 void _nc_hash_map(void)
266 {
267     sym *sp;
268     register int i;
269     int start, shift, size;
270
271
272     if (screen_lines > lines_alloc)
273     {
274         if (hashtab)
275             free (hashtab);
276         hashtab = malloc (sizeof(*hashtab)*(screen_lines+1)*2);
277         if (!hashtab)
278         {
279             if (oldhash)
280                 FreeAndNull(oldhash);
281             lines_alloc = 0;
282             return;
283         }
284   
285         if (oldhash)
286             free (oldhash);
287         oldhash = malloc (sizeof(*oldhash)*screen_lines*2);
288         if (!oldhash)
289         {
290             if (hashtab)
291                 FreeAndNull(hashtab);
292             lines_alloc = 0;
293             return;
294         }
295         
296         lines_alloc = screen_lines;
297     }
298     newhash = oldhash + screen_lines;   /* two arrays in the same memory block */
299
300     /*
301      * Set up and count line-hash values.
302      */
303     memset(hashtab, '\0', sizeof(*hashtab)*(screen_lines+1)*2);
304     for (i = 0; i < screen_lines; i++)
305     {
306         unsigned long hashval = hash(OLDTEXT(i));
307
308         for (sp = hashtab; sp->hashval; sp++)
309             if (sp->hashval == hashval)
310                 break;
311         sp->hashval = hashval;  /* in case this is a new entry */
312         oldhash[i] = hashval;
313         sp->oldcount++;
314         sp->oldindex = i;
315     }
316     for (i = 0; i < screen_lines; i++)
317     {
318         unsigned long hashval = hash(NEWTEXT(i));
319
320         for (sp = hashtab; sp->hashval; sp++)
321             if (sp->hashval == hashval)
322                 break;
323         sp->hashval = hashval;  /* in case this is a new entry */
324         newhash[i] = hashval;
325         sp->newcount++;
326         sp->newindex = i;
327     
328         OLDNUM(i) = _NEWINDEX;
329     }
330
331     /*
332      * Mark line pairs corresponding to unique hash pairs.
333      * 
334      * We don't mark lines with offset 0, because it can make fail
335      * extending hunks by cost_effective. Otherwise, it does not
336      * have any side effects.
337      */
338     for (sp = hashtab; sp->hashval; sp++)
339         if (sp->oldcount == 1 && sp->newcount == 1
340             && sp->oldindex != sp->newindex)
341         {
342             TR(TRACE_UPDATE | TRACE_MOVE,
343                ("new line %d is hash-identical to old line %d (unique)",
344                    sp->newindex, sp->oldindex));
345             OLDNUM(sp->newindex) = sp->oldindex;
346         }
347
348     grow_hunks();
349
350     /*
351      * Eliminate bad or impossible shifts -- this includes removing
352      * those hunks which could not grow because of conflicts, as well
353      * those which are to be moved too far, they are likely to destroy
354      * more than carry.
355      */
356     for (i = 0; i < screen_lines; )
357     {
358         while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
359             i++;
360         if (i >= screen_lines)
361             break;
362         start = i;
363         shift = OLDNUM(i) - i;
364         i++;
365         while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift)
366             i++;
367         size = i - start;
368         if (size <= abs(shift))
369         {
370             while (start < i)
371             {
372                 OLDNUM(start) = _NEWINDEX;
373                 start++;
374             }
375         }
376     }
377     
378     /* After clearing invalid hunks, try grow the rest. */
379     grow_hunks();
380
381 #if NO_LEAKS
382     FreeAndNull(hashtab);
383     FreeAndNull(oldhash);
384     lines_alloc = 0;
385 #endif
386 }
387
388 #ifdef HASHDEBUG
389
390 int
391 main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED)
392 {
393     char        line[BUFSIZ], *st;
394     int         n;
395
396     for (n = 0; n < screen_lines; n++)
397     {
398         reallines[n] = n;
399         oldnums[n] = _NEWINDEX;
400         oldtext[n][0] = newtext[n][0] = '.';
401     }
402
403 #ifdef TRACE
404     _nc_tracing = TRACE_MOVE;
405 #endif
406     for (;;)
407     {
408         /* grab a test command */
409         if (fgets(line, sizeof(line), stdin) == (char *)NULL)
410             exit(EXIT_SUCCESS);
411
412         switch(line[0])
413         {
414         case '#':       /* comment */
415             (void) fputs(line, stderr);
416             break;
417
418         case 'l':       /* get initial line number vector */
419             for (n = 0; n < screen_lines; n++)
420             {
421                 reallines[n] = n;
422                 oldnums[n] = _NEWINDEX;
423             }
424             n = 0;
425             st = strtok(line, " ");
426             do {
427                 oldnums[n++] = atoi(st);
428             } while
429                 ((st = strtok((char *)NULL, " ")) != 0);
430             break;
431
432         case 'n':       /* use following letters as text of new lines */
433             for (n = 0; n < screen_lines; n++)
434                 newtext[n][0] = '.';
435             for (n = 0; n < screen_lines; n++)
436                 if (line[n+1] == '\n')
437                     break;
438                 else
439                     newtext[n][0] = line[n+1];
440             break;
441
442         case 'o':       /* use following letters as text of old lines */
443             for (n = 0; n < screen_lines; n++)
444                 oldtext[n][0] = '.';
445             for (n = 0; n < screen_lines; n++)
446                 if (line[n+1] == '\n')
447                     break;
448                 else
449                     oldtext[n][0] = line[n+1];
450             break;
451
452         case 'd':       /* dump state of test arrays */
453 #ifdef TRACE
454             _nc_linedump();
455 #endif
456             (void) fputs("Old lines: [", stdout);
457             for (n = 0; n < screen_lines; n++)
458                 putchar(oldtext[n][0]);
459             putchar(']');
460             putchar('\n');
461             (void) fputs("New lines: [", stdout);
462             for (n = 0; n < screen_lines; n++)
463                 putchar(newtext[n][0]);
464             putchar(']');
465             putchar('\n');
466             break;
467
468         case 'h':       /* apply hash mapper and see scroll optimization */
469             _nc_hash_map();
470             (void) fputs("Result:\n", stderr);
471 #ifdef TRACE
472             _nc_linedump();
473 #endif
474             _nc_scroll_optimize();
475             (void) fputs("Done.\n", stderr);
476             break;
477         }
478     }
479     return EXIT_SUCCESS;
480 }
481
482 #endif /* HASHDEBUG */
483
484 /* hashmap.c ends here */