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