ncurses 6.2 - patch 20200531
[ncurses.git] / ncurses / tty / hashmap.c
1 /****************************************************************************
2  * Copyright 2019,2020 Thomas E. Dickey                                     *
3  * Copyright 1998-2015,2016 Free Software Foundation, Inc.                  *
4  *                                                                          *
5  * Permission is hereby granted, free of charge, to any person obtaining a  *
6  * copy of this software and associated documentation files (the            *
7  * "Software"), to deal in the Software without restriction, including      *
8  * without limitation the rights to use, copy, modify, merge, publish,      *
9  * distribute, distribute with modifications, sublicense, and/or sell       *
10  * copies of the Software, and to permit persons to whom the Software is    *
11  * furnished to do so, subject to the following conditions:                 *
12  *                                                                          *
13  * The above copyright notice and this permission notice shall be included  *
14  * in all copies or substantial portions of the Software.                   *
15  *                                                                          *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
17  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
19  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
20  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
21  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
22  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
23  *                                                                          *
24  * Except as contained in this notice, the name(s) of the above copyright   *
25  * holders shall not be used in advertising or otherwise to promote the     *
26  * sale, use or other dealings in this Software without prior written       *
27  * authorization.                                                           *
28  ****************************************************************************/
29
30 /****************************************************************************
31  *  Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995               *
32  *     and: Eric S. Raymond <esr@snark.thyrsus.com>                         *
33  ****************************************************************************/
34
35 /******************************************************************************
36
37 NAME
38    hashmap.c -- fill in scramble vector based on text hashes
39
40 SYNOPSIS
41    void _nc_hash_map(void)
42
43 DESCRIPTION:
44    This code attempts to recognize pairs of old and new lines in the physical
45 and virtual screens.  When a line pair is recognized, the old line index is
46 placed in the oldindex member of the virtual screen line, to be used by the
47 vertical-motion optimizer portion of the update logic (see hardscroll.c).
48
49    Line pairs are recognized by applying a modified Heckel's algorithm,
50 sped up by hashing.  If a line hash is unique in both screens, those
51 lines must be a pair. Then if the lines just before or after the pair
52 are the same or similar, they are a pair too.
53
54    We don't worry about false pairs produced by hash collisions, on the
55 assumption that such cases are rare and will only make the latter stages
56 of update less efficient, not introduce errors.
57
58 HOW TO TEST THIS:
59
60 Use the following production:
61
62 hashmap: hashmap.c
63         $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
64
65 AUTHOR
66     Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
67     Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997
68
69 *****************************************************************************/
70
71 #include <curses.priv.h>
72
73 #ifndef CUR
74 #define CUR SP_TERMTYPE
75 #endif
76
77 MODULE_ID("$Id: hashmap.c,v 1.69 2020/05/31 17:50:48 tom Exp $")
78
79 #ifdef HASHDEBUG
80
81 # define _tracef        printf
82 # undef TR
83 # ifdef TRACE
84 # define TR(n, a)       if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
85 # else
86 # define TR(n, a)       { _tracef a ; putchar('\n'); }
87 # endif
88 # undef screen_lines
89 # define screen_lines(sp) MAXLINES
90 # define TEXTWIDTH(sp)  1
91 static int oldnums[MAXLINES], reallines[MAXLINES];
92 static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH(sp)];
93 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH(sp)];
94 # define OLDNUM(sp,n)   oldnums[n]
95 # define OLDTEXT(sp,n)  oldtext[n]
96 # define NEWTEXT(sp,m)  newtext[m]
97 # define PENDING(sp,n)  1
98
99 #else /* !HASHDEBUG */
100
101 # define OLDNUM(sp,n)   (sp)->_oldnum_list[n]
102 # define OLDTEXT(sp,n)  CurScreen(sp)->_line[n].text
103 # define NEWTEXT(sp,m)  NewScreen(sp)->_line[m].text
104 # define TEXTWIDTH(sp)  (CurScreen(sp)->_maxx + 1)
105 # define PENDING(sp,n)  (NewScreen(sp)->_line[n].firstchar != _NOCHANGE)
106
107 #endif /* !HASHDEBUG */
108
109 #define oldhash(sp)     ((sp)->oldhash)
110 #define newhash(sp)     ((sp)->newhash)
111 #define hashtab(sp)     ((sp)->hashtab)
112 #define lines_alloc(sp) ((sp)->hashtab_len)
113
114 #if USE_WIDEC_SUPPORT
115 #define HASH_VAL(ch) (ch.chars[0])
116 #else
117 #define HASH_VAL(ch) (ch)
118 #endif
119
120 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
121
122 static NCURSES_INLINE unsigned long
123 hash(SCREEN *sp, NCURSES_CH_T *text)
124 {
125     int i;
126     NCURSES_CH_T ch;
127     unsigned long result = 0;
128     (void) sp;
129
130     for (i = TEXTWIDTH(sp); i > 0; i--) {
131         ch = *text++;
132         result += (result << 5) + (unsigned long) HASH_VAL(ch);
133     }
134     return result;
135 }
136
137 /* approximate update cost */
138 static int
139 update_cost(SCREEN *sp, NCURSES_CH_T *from, NCURSES_CH_T *to)
140 {
141     int cost = 0;
142     int i;
143     (void) sp;
144
145     for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
146         if (!(CharEq(*from, *to)))
147             cost++;
148
149     return cost;
150 }
151
152 static int
153 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T *to)
154 {
155     int cost = 0;
156     int i;
157     NCURSES_CH_T blank = blankchar;
158     (void) sp;
159
160     if (back_color_erase)
161         SetPair(blank, GetPair(stdscr->_nc_bkgd));
162
163     for (i = TEXTWIDTH(sp); i > 0; i--, to++)
164         if (!(CharEq(blank, *to)))
165             cost++;
166
167     return cost;
168 }
169
170 /*
171  * Returns true when moving line 'from' to line 'to' seems to be cost
172  * effective. 'blank' indicates whether the line 'to' would become blank.
173  */
174 static NCURSES_INLINE bool
175 cost_effective(SCREEN *sp, const int from, const int to, const int blank)
176 {
177     int new_from;
178
179     if (from == to)
180         return FALSE;
181
182     new_from = OLDNUM(sp, from);
183     if (new_from == _NEWINDEX)
184         new_from = from;
185
186     /*
187      * On the left side of >= is the cost before moving;
188      * on the right side -- cost after moving.
189      */
190     return (((blank ? update_cost_from_blank(sp, NEWTEXT(sp, to))
191               : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to)))
192              + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
193             >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from))
194                  : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
195                 + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to))))
196         ? TRUE : FALSE;
197 }
198
199 static void
200 grow_hunks(SCREEN *sp)
201 {
202     int back_limit;             /* limits for cells to fill */
203     int back_ref_limit;         /* limit for references */
204     int i;
205     int next_hunk;
206
207     /*
208      * This is tricky part.  We have unique pairs to use as anchors.
209      * Use these to deduce the presence of spans of identical lines.
210      */
211     back_limit = 0;
212     back_ref_limit = 0;
213
214     i = 0;
215     while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
216         i++;
217     for (; i < screen_lines(sp); i = next_hunk) {
218         int forward_limit;
219         int forward_ref_limit;
220         int end;
221         int start = i;
222         int shift = OLDNUM(sp, i) - i;
223
224         /* get forward limit */
225         i = start + 1;
226         while (i < screen_lines(sp)
227                && OLDNUM(sp, i) != _NEWINDEX
228                && OLDNUM(sp, i) - i == shift)
229             i++;
230         end = i;
231         while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
232             i++;
233         next_hunk = i;
234         forward_limit = i;
235         if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
236             forward_ref_limit = i;
237         else
238             forward_ref_limit = OLDNUM(sp, i);
239
240         i = start - 1;
241         /* grow back */
242         if (shift < 0)
243             back_limit = back_ref_limit + (-shift);
244         while (i >= back_limit) {
245             if (newhash(sp)[i] == oldhash(sp)[i + shift]
246                 || cost_effective(sp, i + shift, i, shift < 0)) {
247                 OLDNUM(sp, i) = i + shift;
248                 TR(TRACE_UPDATE | TRACE_MOVE,
249                    ("connected new line %d to old line %d (backward continuation)",
250                     i, i + shift));
251             } else {
252                 TR(TRACE_UPDATE | TRACE_MOVE,
253                    ("not connecting new line %d to old line %d (backward continuation)",
254                     i, i + shift));
255                 break;
256             }
257             i--;
258         }
259
260         i = end;
261         /* grow forward */
262         if (shift > 0)
263             forward_limit = forward_ref_limit - shift;
264         while (i < forward_limit) {
265             if (newhash(sp)[i] == oldhash(sp)[i + shift]
266                 || cost_effective(sp, i + shift, i, shift > 0)) {
267                 OLDNUM(sp, i) = i + shift;
268                 TR(TRACE_UPDATE | TRACE_MOVE,
269                    ("connected new line %d to old line %d (forward continuation)",
270                     i, i + shift));
271             } else {
272                 TR(TRACE_UPDATE | TRACE_MOVE,
273                    ("not connecting new line %d to old line %d (forward continuation)",
274                     i, i + shift));
275                 break;
276             }
277             i++;
278         }
279
280         back_ref_limit = back_limit = i;
281         if (shift > 0)
282             back_ref_limit += shift;
283     }
284 }
285
286 NCURSES_EXPORT(void)
287 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
288 {
289     HASHMAP *hsp;
290     register int i;
291
292     if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
293         if (hashtab(SP_PARM))
294             free(hashtab(SP_PARM));
295         hashtab(SP_PARM) = typeMalloc(HASHMAP,
296                                       ((size_t) screen_lines(SP_PARM) + 1) * 2);
297         if (!hashtab(SP_PARM)) {
298             if (oldhash(SP_PARM)) {
299                 FreeAndNull(oldhash(SP_PARM));
300             }
301             lines_alloc(SP_PARM) = 0;
302             return;
303         }
304         lines_alloc(SP_PARM) = screen_lines(SP_PARM);
305     }
306
307     if (oldhash(SP_PARM) && newhash(SP_PARM)) {
308         /* re-hash only changed lines */
309         for (i = 0; i < screen_lines(SP_PARM); i++) {
310             if (PENDING(SP_PARM, i))
311                 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
312         }
313     } else {
314         /* re-hash all */
315         if (oldhash(SP_PARM) == 0)
316             oldhash(SP_PARM) = typeCalloc(unsigned long,
317                                             (size_t) screen_lines(SP_PARM));
318         if (newhash(SP_PARM) == 0)
319             newhash(SP_PARM) = typeCalloc(unsigned long,
320                                             (size_t) screen_lines(SP_PARM));
321         if (!oldhash(SP_PARM) || !newhash(SP_PARM))
322             return;             /* malloc failure */
323         for (i = 0; i < screen_lines(SP_PARM); i++) {
324             newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
325             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
326         }
327     }
328
329 #ifdef HASH_VERIFY
330     for (i = 0; i < screen_lines(SP_PARM); i++) {
331         if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
332             fprintf(stderr, "error in newhash[%d]\n", i);
333         if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
334             fprintf(stderr, "error in oldhash[%d]\n", i);
335     }
336 #endif
337
338     /*
339      * Set up and count line-hash values.
340      */
341     memset(hashtab(SP_PARM), '\0',
342            sizeof(*(hashtab(SP_PARM)))
343            * ((size_t) screen_lines(SP_PARM) + 1) * 2);
344     for (i = 0; i < screen_lines(SP_PARM); i++) {
345         unsigned long hashval = oldhash(SP_PARM)[i];
346
347         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
348             if (hsp->hashval == hashval)
349                 break;
350         hsp->hashval = hashval; /* in case this is a new entry */
351         hsp->oldcount++;
352         hsp->oldindex = i;
353     }
354     for (i = 0; i < screen_lines(SP_PARM); i++) {
355         unsigned long hashval = newhash(SP_PARM)[i];
356
357         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
358             if (hsp->hashval == hashval)
359                 break;
360         hsp->hashval = hashval; /* in case this is a new entry */
361         hsp->newcount++;
362         hsp->newindex = i;
363
364         OLDNUM(SP_PARM, i) = _NEWINDEX;         /* initialize old indices array */
365     }
366
367     /*
368      * Mark line pairs corresponding to unique hash pairs.
369      *
370      * We don't mark lines with offset 0, because it can make fail
371      * extending hunks by cost_effective. Otherwise, it does not
372      * have any side effects.
373      */
374     for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
375         if (hsp->oldcount == 1 && hsp->newcount == 1
376             && hsp->oldindex != hsp->newindex) {
377             TR(TRACE_UPDATE | TRACE_MOVE,
378                ("new line %d is hash-identical to old line %d (unique)",
379                 hsp->newindex, hsp->oldindex));
380             OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
381         }
382
383     grow_hunks(SP_PARM);
384
385     /*
386      * Eliminate bad or impossible shifts -- this includes removing
387      * those hunks which could not grow because of conflicts, as well
388      * those which are to be moved too far, they are likely to destroy
389      * more than carry.
390      */
391     for (i = 0; i < screen_lines(SP_PARM);) {
392         int start, shift, size;
393
394         while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
395             i++;
396         if (i >= screen_lines(SP_PARM))
397             break;
398         start = i;
399         shift = OLDNUM(SP_PARM, i) - i;
400         i++;
401         while (i < screen_lines(SP_PARM)
402                && OLDNUM(SP_PARM, i) != _NEWINDEX
403                && OLDNUM(SP_PARM, i) - i == shift)
404             i++;
405         size = i - start;
406         if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
407             while (start < i) {
408                 OLDNUM(SP_PARM, start) = _NEWINDEX;
409                 start++;
410             }
411         }
412     }
413
414     /* After clearing invalid hunks, try grow the rest. */
415     grow_hunks(SP_PARM);
416 }
417
418 #if NCURSES_SP_FUNCS
419 NCURSES_EXPORT(void)
420 _nc_hash_map(void)
421 {
422     NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
423 }
424 #endif
425
426 NCURSES_EXPORT(void)
427 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
428 {
429     if (oldhash(SP_PARM))
430         oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
431 }
432
433 #if NCURSES_SP_FUNCS
434 NCURSES_EXPORT(void)
435 _nc_make_oldhash(int i)
436 {
437     NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
438 }
439 #endif
440
441 NCURSES_EXPORT(void)
442 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
443 {
444     size_t size;
445     int i;
446
447     if (!oldhash(SP_PARM))
448         return;
449
450     size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
451     if (n > 0) {
452         memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
453         for (i = bot; i > bot - n; i--)
454             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
455     } else {
456         memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
457         for (i = top; i < top - n; i++)
458             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
459     }
460 }
461
462 #if NCURSES_SP_FUNCS
463 NCURSES_EXPORT(void)
464 _nc_scroll_oldhash(int n, int top, int bot)
465 {
466     NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
467 }
468 #endif
469
470 #ifdef HASHDEBUG
471 static void
472 usage(void)
473 {
474     static const char *table[] =
475     {
476         "hashmap test-driver",
477         "",
478         "#  comment",
479         "l  get initial line number vector",
480         "n  use following letters as text of new lines",
481         "o  use following letters as text of old lines",
482         "d  dump state of test arrays",
483         "h  apply hash mapper and see scroll optimization",
484         "?  this message"
485     };
486     size_t n;
487     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
488         fprintf(stderr, "%s\n", table[n]);
489 }
490
491 int
492 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
493 {
494     char line[BUFSIZ], *st;
495     int n;
496
497     if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
498         return EXIT_FAILURE;
499     (void) _nc_alloc_screen();
500
501     for (n = 0; n < screen_lines(sp); n++) {
502         reallines[n] = n;
503         oldnums[n] = _NEWINDEX;
504         CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
505     }
506
507     if (NC_ISATTY(fileno(stdin)))
508         usage();
509
510 #ifdef TRACE
511     _nc_tracing = TRACE_MOVE;
512 #endif
513     for (;;) {
514         /* grab a test command */
515         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
516             break;
517
518         switch (line[0]) {
519         case '#':               /* comment */
520             (void) fputs(line, stderr);
521             break;
522
523         case 'l':               /* get initial line number vector */
524             for (n = 0; n < screen_lines(sp); n++) {
525                 reallines[n] = n;
526                 oldnums[n] = _NEWINDEX;
527             }
528             n = 0;
529             st = strtok(line, " ");
530             do {
531                 oldnums[n++] = atoi(st);
532             } while
533                 ((st = strtok((char *) NULL, " ")) != 0);
534             break;
535
536         case 'n':               /* use following letters as text of new lines */
537             for (n = 0; n < screen_lines(sp); n++)
538                 CharOf(newtext[n][0]) = '.';
539             for (n = 0; n < screen_lines(sp); n++)
540                 if (line[n + 1] == '\n')
541                     break;
542                 else
543                     CharOf(newtext[n][0]) = line[n + 1];
544             break;
545
546         case 'o':               /* use following letters as text of old lines */
547             for (n = 0; n < screen_lines(sp); n++)
548                 CharOf(oldtext[n][0]) = '.';
549             for (n = 0; n < screen_lines(sp); n++)
550                 if (line[n + 1] == '\n')
551                     break;
552                 else
553                     CharOf(oldtext[n][0]) = line[n + 1];
554             break;
555
556         case 'd':               /* dump state of test arrays */
557 #ifdef TRACE
558             _nc_linedump();
559 #endif
560             (void) fputs("Old lines: [", stdout);
561             for (n = 0; n < screen_lines(sp); n++)
562                 putchar(CharOf(oldtext[n][0]));
563             putchar(']');
564             putchar('\n');
565             (void) fputs("New lines: [", stdout);
566             for (n = 0; n < screen_lines(sp); n++)
567                 putchar(CharOf(newtext[n][0]));
568             putchar(']');
569             putchar('\n');
570             break;
571
572         case 'h':               /* apply hash mapper and see scroll optimization */
573             _nc_hash_map();
574             (void) fputs("Result:\n", stderr);
575 #ifdef TRACE
576             _nc_linedump();
577 #endif
578             _nc_scroll_optimize();
579             (void) fputs("Done.\n", stderr);
580             break;
581         default:
582         case '?':
583             usage();
584             break;
585         }
586     }
587     exit_curses(EXIT_SUCCESS);
588 }
589
590 #endif /* HASHDEBUG */
591
592 /* hashmap.c ends here */