05c379199c217f4aa513b1f8d4f1aef5ccc7ff95
[ncurses.git] / ncurses / tty / hashmap.c
1 /****************************************************************************
2  * Copyright (c) 1998-2007,2009 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
72 MODULE_ID("$Id: hashmap.c,v 1.57 2009/04/18 19:03:50 tom Exp $")
73
74 #ifdef HASHDEBUG
75
76 # define _tracef        printf
77 # undef TR
78 # define TR(n, a)       if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
79 # undef screen_lines
80 # define screen_lines MAXLINES
81 # define TEXTWIDTH      1
82 int oldnums[MAXLINES], reallines[MAXLINES];
83 static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH];
84 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH];
85 # define OLDNUM(sp,n)   oldnums[n]
86 # define OLDTEXT(sp,n)  oldtext[n]
87 # define NEWTEXT(sp,m)  newtext[m]
88 # define PENDING(sp,n)  1
89
90 #else /* !HASHDEBUG */
91
92 # define OLDNUM(sp,n)   (sp)->_oldnum_list[n]
93 # define OLDTEXT(sp,n)  (sp)->_curscr->_line[n].text
94 # define NEWTEXT(sp,m)  (sp)->_newscr->_line[m].text
95 # define TEXTWIDTH(sp)  ((sp)->_curscr->_maxx+1)
96 # define PENDING(sp,n)  ((sp)->_newscr->_line[n].firstchar != _NOCHANGE)
97
98 #endif /* !HASHDEBUG */
99
100 #define oldhash(sp)     ((sp)->oldhash)
101 #define newhash(sp)     ((sp)->newhash)
102 #define hashtab(sp)     ((sp)->hashtab)
103 #define lines_alloc(sp) ((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 const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
112
113 static NCURSES_INLINE unsigned long
114 hash(SCREEN *sp, NCURSES_CH_T * text)
115 {
116     int i;
117     NCURSES_CH_T ch;
118     unsigned long result = 0;
119     for (i = TEXTWIDTH(sp); i > 0; i--) {
120         ch = *text++;
121         result += (result << 5) + HASH_VAL(ch);
122     }
123     return result;
124 }
125
126 /* approximate update cost */
127 static int
128 update_cost(SCREEN *sp, NCURSES_CH_T * from, NCURSES_CH_T * to)
129 {
130     int cost = 0;
131     int i;
132
133     for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
134         if (!(CharEq(*from, *to)))
135             cost++;
136
137     return cost;
138 }
139
140 static int
141 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T * to)
142 {
143     int cost = 0;
144     int i;
145     NCURSES_CH_T blank = blankchar;
146
147     if (back_color_erase)
148         SetPair(blank, GetPair(stdscr->_nc_bkgd));
149
150     for (i = TEXTWIDTH(sp); i > 0; i--, to++)
151         if (!(CharEq(blank, *to)))
152             cost++;
153
154     return cost;
155 }
156
157 /*
158  * Returns true when moving line 'from' to line 'to' seems to be cost
159  * effective. 'blank' indicates whether the line 'to' would become blank.
160  */
161 static NCURSES_INLINE bool
162 cost_effective(SCREEN *sp, const int from, const int to, const bool blank)
163 {
164     int new_from;
165
166     if (from == to)
167         return FALSE;
168
169     new_from = OLDNUM(sp, from);
170     if (new_from == _NEWINDEX)
171         new_from = from;
172
173     /*
174      * On the left side of >= is the cost before moving;
175      * on the right side -- cost after moving.
176      */
177     return (((blank ? update_cost_from_blank(sp, NEWTEXT(sp, to))
178               : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to)))
179              + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
180             >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from))
181                  : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
182                 + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to))))
183         ? TRUE : FALSE;
184 }
185
186 static void
187 grow_hunks(SCREEN *sp)
188 {
189     int start, end, shift;
190     int back_limit, forward_limit;      /* limits for cells to fill */
191     int back_ref_limit, forward_ref_limit;      /* limits for refrences */
192     int i;
193     int next_hunk;
194
195     /*
196      * This is tricky part.  We have unique pairs to use as anchors.
197      * Use these to deduce the presence of spans of identical lines.
198      */
199     back_limit = 0;
200     back_ref_limit = 0;
201
202     i = 0;
203     while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
204         i++;
205     for (; i < screen_lines(sp); i = next_hunk) {
206         start = i;
207         shift = OLDNUM(sp, i) - i;
208
209         /* get forward limit */
210         i = start + 1;
211         while (i < screen_lines(sp)
212                && OLDNUM(sp, i) != _NEWINDEX
213                && OLDNUM(sp, i) - i == shift)
214             i++;
215         end = i;
216         while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
217             i++;
218         next_hunk = i;
219         forward_limit = i;
220         if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
221             forward_ref_limit = i;
222         else
223             forward_ref_limit = OLDNUM(sp, i);
224
225         i = start - 1;
226         /* grow back */
227         if (shift < 0)
228             back_limit = back_ref_limit + (-shift);
229         while (i >= back_limit) {
230             if (newhash(sp)[i] == oldhash(sp)[i + shift]
231                 || cost_effective(sp, i + shift, i, shift < 0)) {
232                 OLDNUM(sp, i) = i + shift;
233                 TR(TRACE_UPDATE | TRACE_MOVE,
234                    ("connected new line %d to old line %d (backward continuation)",
235                     i, i + shift));
236             } else {
237                 TR(TRACE_UPDATE | TRACE_MOVE,
238                    ("not connecting new line %d to old line %d (backward continuation)",
239                     i, i + shift));
240                 break;
241             }
242             i--;
243         }
244
245         i = end;
246         /* grow forward */
247         if (shift > 0)
248             forward_limit = forward_ref_limit - shift;
249         while (i < forward_limit) {
250             if (newhash(sp)[i] == oldhash(sp)[i + shift]
251                 || cost_effective(sp, i + shift, i, shift > 0)) {
252                 OLDNUM(sp, i) = i + shift;
253                 TR(TRACE_UPDATE | TRACE_MOVE,
254                    ("connected new line %d to old line %d (forward continuation)",
255                     i, i + shift));
256             } else {
257                 TR(TRACE_UPDATE | TRACE_MOVE,
258                    ("not connecting new line %d to old line %d (forward continuation)",
259                     i, i + shift));
260                 break;
261             }
262             i++;
263         }
264
265         back_ref_limit = back_limit = i;
266         if (shift > 0)
267             back_ref_limit += shift;
268     }
269 }
270
271 NCURSES_EXPORT(void)
272 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
273 {
274     HASHMAP *hsp;
275     register int i;
276     int start, shift, size;
277
278     if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
279         if (hashtab(SP_PARM))
280             free(hashtab(SP_PARM));
281         hashtab(SP_PARM) = typeMalloc(HASHMAP, (screen_lines(SP_PARM) + 1) * 2);
282         if (!hashtab(SP_PARM)) {
283             if (oldhash(SP_PARM)) {
284                 FreeAndNull(oldhash(SP_PARM));
285             }
286             lines_alloc(SP_PARM) = 0;
287             return;
288         }
289         lines_alloc(SP_PARM) = screen_lines(SP_PARM);
290     }
291
292     if (oldhash(SP_PARM) && newhash(SP_PARM)) {
293         /* re-hash only changed lines */
294         for (i = 0; i < screen_lines(SP_PARM); i++) {
295             if (PENDING(SP_PARM, i))
296                 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
297         }
298     } else {
299         /* re-hash all */
300         if (oldhash(SP_PARM) == 0)
301             oldhash(SP_PARM) = typeCalloc(unsigned long,
302                                             (unsigned) screen_lines(SP_PARM));
303         if (newhash(SP_PARM) == 0)
304             newhash(SP_PARM) = typeCalloc(unsigned long,
305                                             (unsigned) screen_lines(SP_PARM));
306         if (!oldhash(SP_PARM) || !newhash(SP_PARM))
307             return;             /* malloc failure */
308         for (i = 0; i < screen_lines(SP_PARM); i++) {
309             newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
310             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
311         }
312     }
313
314 #ifdef HASH_VERIFY
315     for (i = 0; i < screen_lines(SP_PARM); i++) {
316         if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
317             fprintf(stderr, "error in newhash[%d]\n", i);
318         if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
319             fprintf(stderr, "error in oldhash[%d]\n", i);
320     }
321 #endif
322
323     /*
324      * Set up and count line-hash values.
325      */
326     memset(hashtab(SP_PARM), '\0',
327            sizeof(*(hashtab(SP_PARM))) * (screen_lines(SP_PARM) + 1) * 2);
328     for (i = 0; i < screen_lines(SP_PARM); i++) {
329         unsigned long hashval = oldhash(SP_PARM)[i];
330
331         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
332             if (hsp->hashval == hashval)
333                 break;
334         hsp->hashval = hashval; /* in case this is a new entry */
335         hsp->oldcount++;
336         hsp->oldindex = i;
337     }
338     for (i = 0; i < screen_lines(SP_PARM); i++) {
339         unsigned long hashval = newhash(SP_PARM)[i];
340
341         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
342             if (hsp->hashval == hashval)
343                 break;
344         hsp->hashval = hashval; /* in case this is a new entry */
345         hsp->newcount++;
346         hsp->newindex = i;
347
348         OLDNUM(SP_PARM, i) = _NEWINDEX;         /* initialize old indices array */
349     }
350
351     /*
352      * Mark line pairs corresponding to unique hash pairs.
353      *
354      * We don't mark lines with offset 0, because it can make fail
355      * extending hunks by cost_effective. Otherwise, it does not
356      * have any side effects.
357      */
358     for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
359         if (hsp->oldcount == 1 && hsp->newcount == 1
360             && hsp->oldindex != hsp->newindex) {
361             TR(TRACE_UPDATE | TRACE_MOVE,
362                ("new line %d is hash-identical to old line %d (unique)",
363                 hsp->newindex, hsp->oldindex));
364             OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
365         }
366
367     grow_hunks(SP_PARM);
368
369     /*
370      * Eliminate bad or impossible shifts -- this includes removing
371      * those hunks which could not grow because of conflicts, as well
372      * those which are to be moved too far, they are likely to destroy
373      * more than carry.
374      */
375     for (i = 0; i < screen_lines(SP_PARM);) {
376         while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
377             i++;
378         if (i >= screen_lines(SP_PARM))
379             break;
380         start = i;
381         shift = OLDNUM(SP_PARM, i) - i;
382         i++;
383         while (i < screen_lines(SP_PARM)
384                && OLDNUM(SP_PARM, i) != _NEWINDEX
385                && OLDNUM(SP_PARM, i) - i == shift)
386             i++;
387         size = i - start;
388         if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
389             while (start < i) {
390                 OLDNUM(SP_PARM, start) = _NEWINDEX;
391                 start++;
392             }
393         }
394     }
395
396     /* After clearing invalid hunks, try grow the rest. */
397     grow_hunks(SP_PARM);
398 }
399
400 #if NCURSES_SP_FUNCS
401 NCURSES_EXPORT(void)
402 _nc_hash_map(void)
403 {
404     NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
405 }
406 #endif
407
408 NCURSES_EXPORT(void)
409 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
410 {
411     if (oldhash(SP_PARM))
412         oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
413 }
414
415 #if NCURSES_SP_FUNCS
416 NCURSES_EXPORT(void)
417 _nc_make_oldhash(int i)
418 {
419     NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
420 }
421 #endif
422
423 NCURSES_EXPORT(void)
424 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
425 {
426     size_t size;
427     int i;
428
429     if (!oldhash(SP_PARM))
430         return;
431
432     size = sizeof(*(oldhash(SP_PARM))) * (bot - top + 1 - abs(n));
433     if (n > 0) {
434         memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
435         for (i = bot; i > bot - n; i--)
436             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
437     } else {
438         memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
439         for (i = top; i < top - n; i++)
440             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
441     }
442 }
443
444 #if NCURSES_SP_FUNCS
445 NCURSES_EXPORT(void)
446 _nc_scroll_oldhash(int n, int top, int bot)
447 {
448     NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
449 }
450 #endif
451
452 #ifdef HASHDEBUG
453 static void
454 usage(void)
455 {
456     static const char *table[] =
457     {
458         "hashmap test-driver",
459         "",
460         "#  comment",
461         "l  get initial line number vector",
462         "n  use following letters as text of new lines",
463         "o  use following letters as text of old lines",
464         "d  dump state of test arrays",
465         "h  apply hash mapper and see scroll optimization",
466         "?  this message"
467     };
468     size_t n;
469     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
470         fprintf(stderr, "%s\n", table[n]);
471 }
472
473 int
474 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
475 {
476     char line[BUFSIZ], *st;
477     int n;
478
479     if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
480         return EXIT_FAILURE;
481     (void) _nc_alloc_screen();
482
483     for (n = 0; n < screen_lines; n++) {
484         reallines[n] = n;
485         oldnums[n] = _NEWINDEX;
486         CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
487     }
488
489     if (isatty(fileno(stdin)))
490         usage();
491
492 #ifdef TRACE
493     _nc_tracing = TRACE_MOVE;
494 #endif
495     for (;;) {
496         /* grab a test command */
497         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
498             break;
499
500         switch (line[0]) {
501         case '#':               /* comment */
502             (void) fputs(line, stderr);
503             break;
504
505         case 'l':               /* get initial line number vector */
506             for (n = 0; n < screen_lines; n++) {
507                 reallines[n] = n;
508                 oldnums[n] = _NEWINDEX;
509             }
510             n = 0;
511             st = strtok(line, " ");
512             do {
513                 oldnums[n++] = atoi(st);
514             } while
515                 ((st = strtok((char *) NULL, " ")) != 0);
516             break;
517
518         case 'n':               /* use following letters as text of new lines */
519             for (n = 0; n < screen_lines; n++)
520                 CharOf(newtext[n][0]) = '.';
521             for (n = 0; n < screen_lines; n++)
522                 if (line[n + 1] == '\n')
523                     break;
524                 else
525                     CharOf(newtext[n][0]) = line[n + 1];
526             break;
527
528         case 'o':               /* use following letters as text of old lines */
529             for (n = 0; n < screen_lines; n++)
530                 CharOf(oldtext[n][0]) = '.';
531             for (n = 0; n < screen_lines; n++)
532                 if (line[n + 1] == '\n')
533                     break;
534                 else
535                     CharOf(oldtext[n][0]) = line[n + 1];
536             break;
537
538         case 'd':               /* dump state of test arrays */
539 #ifdef TRACE
540             _nc_linedump();
541 #endif
542             (void) fputs("Old lines: [", stdout);
543             for (n = 0; n < screen_lines; n++)
544                 putchar(CharOf(oldtext[n][0]));
545             putchar(']');
546             putchar('\n');
547             (void) fputs("New lines: [", stdout);
548             for (n = 0; n < screen_lines; n++)
549                 putchar(CharOf(newtext[n][0]));
550             putchar(']');
551             putchar('\n');
552             break;
553
554         case 'h':               /* apply hash mapper and see scroll optimization */
555             _nc_hash_map();
556             (void) fputs("Result:\n", stderr);
557 #ifdef TRACE
558             _nc_linedump();
559 #endif
560             _nc_scroll_optimize();
561             (void) fputs("Done.\n", stderr);
562             break;
563         default:
564         case '?':
565             usage();
566             break;
567         }
568     }
569 #if NO_LEAKS
570     _nc_free_and_exit(EXIT_SUCCESS);
571 #else
572     return EXIT_SUCCESS;
573 #endif
574 }
575
576 #endif /* HASHDEBUG */
577
578 /* hashmap.c ends here */