8c0fdfd83f5c21ccf6570aeb6af01060aead22e9
[ncurses.git] / ncurses / tty / hashmap.c
1 /****************************************************************************
2  * Copyright (c) 1998-2014,2015 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.65 2015/07/25 20:13:56 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 start, end, shift;
202     int back_limit, forward_limit;      /* limits for cells to fill */
203     int back_ref_limit, forward_ref_limit;      /* limits for refrences */
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         start = i;
219         shift = OLDNUM(sp, i) - i;
220
221         /* get forward limit */
222         i = start + 1;
223         while (i < screen_lines(sp)
224                && OLDNUM(sp, i) != _NEWINDEX
225                && OLDNUM(sp, i) - i == shift)
226             i++;
227         end = i;
228         while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
229             i++;
230         next_hunk = i;
231         forward_limit = i;
232         if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
233             forward_ref_limit = i;
234         else
235             forward_ref_limit = OLDNUM(sp, i);
236
237         i = start - 1;
238         /* grow back */
239         if (shift < 0)
240             back_limit = back_ref_limit + (-shift);
241         while (i >= back_limit) {
242             if (newhash(sp)[i] == oldhash(sp)[i + shift]
243                 || cost_effective(sp, i + shift, i, shift < 0)) {
244                 OLDNUM(sp, i) = i + shift;
245                 TR(TRACE_UPDATE | TRACE_MOVE,
246                    ("connected new line %d to old line %d (backward continuation)",
247                     i, i + shift));
248             } else {
249                 TR(TRACE_UPDATE | TRACE_MOVE,
250                    ("not connecting new line %d to old line %d (backward continuation)",
251                     i, i + shift));
252                 break;
253             }
254             i--;
255         }
256
257         i = end;
258         /* grow forward */
259         if (shift > 0)
260             forward_limit = forward_ref_limit - shift;
261         while (i < forward_limit) {
262             if (newhash(sp)[i] == oldhash(sp)[i + shift]
263                 || cost_effective(sp, i + shift, i, shift > 0)) {
264                 OLDNUM(sp, i) = i + shift;
265                 TR(TRACE_UPDATE | TRACE_MOVE,
266                    ("connected new line %d to old line %d (forward continuation)",
267                     i, i + shift));
268             } else {
269                 TR(TRACE_UPDATE | TRACE_MOVE,
270                    ("not connecting new line %d to old line %d (forward continuation)",
271                     i, i + shift));
272                 break;
273             }
274             i++;
275         }
276
277         back_ref_limit = back_limit = i;
278         if (shift > 0)
279             back_ref_limit += shift;
280     }
281 }
282
283 NCURSES_EXPORT(void)
284 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
285 {
286     HASHMAP *hsp;
287     register int i;
288     int start, shift, size;
289
290     if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
291         if (hashtab(SP_PARM))
292             free(hashtab(SP_PARM));
293         hashtab(SP_PARM) = typeMalloc(HASHMAP,
294                                       ((size_t) screen_lines(SP_PARM) + 1) * 2);
295         if (!hashtab(SP_PARM)) {
296             if (oldhash(SP_PARM)) {
297                 FreeAndNull(oldhash(SP_PARM));
298             }
299             lines_alloc(SP_PARM) = 0;
300             return;
301         }
302         lines_alloc(SP_PARM) = screen_lines(SP_PARM);
303     }
304
305     if (oldhash(SP_PARM) && newhash(SP_PARM)) {
306         /* re-hash only changed lines */
307         for (i = 0; i < screen_lines(SP_PARM); i++) {
308             if (PENDING(SP_PARM, i))
309                 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
310         }
311     } else {
312         /* re-hash all */
313         if (oldhash(SP_PARM) == 0)
314             oldhash(SP_PARM) = typeCalloc(unsigned long,
315                                             (size_t) screen_lines(SP_PARM));
316         if (newhash(SP_PARM) == 0)
317             newhash(SP_PARM) = typeCalloc(unsigned long,
318                                             (size_t) screen_lines(SP_PARM));
319         if (!oldhash(SP_PARM) || !newhash(SP_PARM))
320             return;             /* malloc failure */
321         for (i = 0; i < screen_lines(SP_PARM); i++) {
322             newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
323             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
324         }
325     }
326
327 #ifdef HASH_VERIFY
328     for (i = 0; i < screen_lines(SP_PARM); i++) {
329         if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
330             fprintf(stderr, "error in newhash[%d]\n", i);
331         if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
332             fprintf(stderr, "error in oldhash[%d]\n", i);
333     }
334 #endif
335
336     /*
337      * Set up and count line-hash values.
338      */
339     memset(hashtab(SP_PARM), '\0',
340            sizeof(*(hashtab(SP_PARM)))
341            * ((size_t) screen_lines(SP_PARM) + 1) * 2);
342     for (i = 0; i < screen_lines(SP_PARM); i++) {
343         unsigned long hashval = oldhash(SP_PARM)[i];
344
345         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
346             if (hsp->hashval == hashval)
347                 break;
348         hsp->hashval = hashval; /* in case this is a new entry */
349         hsp->oldcount++;
350         hsp->oldindex = i;
351     }
352     for (i = 0; i < screen_lines(SP_PARM); i++) {
353         unsigned long hashval = newhash(SP_PARM)[i];
354
355         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
356             if (hsp->hashval == hashval)
357                 break;
358         hsp->hashval = hashval; /* in case this is a new entry */
359         hsp->newcount++;
360         hsp->newindex = i;
361
362         OLDNUM(SP_PARM, i) = _NEWINDEX;         /* initialize old indices array */
363     }
364
365     /*
366      * Mark line pairs corresponding to unique hash pairs.
367      *
368      * We don't mark lines with offset 0, because it can make fail
369      * extending hunks by cost_effective. Otherwise, it does not
370      * have any side effects.
371      */
372     for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
373         if (hsp->oldcount == 1 && hsp->newcount == 1
374             && hsp->oldindex != hsp->newindex) {
375             TR(TRACE_UPDATE | TRACE_MOVE,
376                ("new line %d is hash-identical to old line %d (unique)",
377                 hsp->newindex, hsp->oldindex));
378             OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
379         }
380
381     grow_hunks(SP_PARM);
382
383     /*
384      * Eliminate bad or impossible shifts -- this includes removing
385      * those hunks which could not grow because of conflicts, as well
386      * those which are to be moved too far, they are likely to destroy
387      * more than carry.
388      */
389     for (i = 0; i < screen_lines(SP_PARM);) {
390         while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
391             i++;
392         if (i >= screen_lines(SP_PARM))
393             break;
394         start = i;
395         shift = OLDNUM(SP_PARM, i) - i;
396         i++;
397         while (i < screen_lines(SP_PARM)
398                && OLDNUM(SP_PARM, i) != _NEWINDEX
399                && OLDNUM(SP_PARM, i) - i == shift)
400             i++;
401         size = i - start;
402         if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
403             while (start < i) {
404                 OLDNUM(SP_PARM, start) = _NEWINDEX;
405                 start++;
406             }
407         }
408     }
409
410     /* After clearing invalid hunks, try grow the rest. */
411     grow_hunks(SP_PARM);
412 }
413
414 #if NCURSES_SP_FUNCS
415 NCURSES_EXPORT(void)
416 _nc_hash_map(void)
417 {
418     NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
419 }
420 #endif
421
422 NCURSES_EXPORT(void)
423 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
424 {
425     if (oldhash(SP_PARM))
426         oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
427 }
428
429 #if NCURSES_SP_FUNCS
430 NCURSES_EXPORT(void)
431 _nc_make_oldhash(int i)
432 {
433     NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
434 }
435 #endif
436
437 NCURSES_EXPORT(void)
438 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
439 {
440     size_t size;
441     int i;
442
443     if (!oldhash(SP_PARM))
444         return;
445
446     size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
447     if (n > 0) {
448         memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
449         for (i = bot; i > bot - n; i--)
450             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
451     } else {
452         memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
453         for (i = top; i < top - n; i++)
454             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
455     }
456 }
457
458 #if NCURSES_SP_FUNCS
459 NCURSES_EXPORT(void)
460 _nc_scroll_oldhash(int n, int top, int bot)
461 {
462     NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
463 }
464 #endif
465
466 #ifdef HASHDEBUG
467 static void
468 usage(void)
469 {
470     static const char *table[] =
471     {
472         "hashmap test-driver",
473         "",
474         "#  comment",
475         "l  get initial line number vector",
476         "n  use following letters as text of new lines",
477         "o  use following letters as text of old lines",
478         "d  dump state of test arrays",
479         "h  apply hash mapper and see scroll optimization",
480         "?  this message"
481     };
482     size_t n;
483     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
484         fprintf(stderr, "%s\n", table[n]);
485 }
486
487 int
488 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
489 {
490     char line[BUFSIZ], *st;
491     int n;
492
493     if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
494         return EXIT_FAILURE;
495     (void) _nc_alloc_screen();
496
497     for (n = 0; n < screen_lines(sp); n++) {
498         reallines[n] = n;
499         oldnums[n] = _NEWINDEX;
500         CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
501     }
502
503     if (NC_ISATTY(fileno(stdin)))
504         usage();
505
506 #ifdef TRACE
507     _nc_tracing = TRACE_MOVE;
508 #endif
509     for (;;) {
510         /* grab a test command */
511         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
512             break;
513
514         switch (line[0]) {
515         case '#':               /* comment */
516             (void) fputs(line, stderr);
517             break;
518
519         case 'l':               /* get initial line number vector */
520             for (n = 0; n < screen_lines(sp); n++) {
521                 reallines[n] = n;
522                 oldnums[n] = _NEWINDEX;
523             }
524             n = 0;
525             st = strtok(line, " ");
526             do {
527                 oldnums[n++] = atoi(st);
528             } while
529                 ((st = strtok((char *) NULL, " ")) != 0);
530             break;
531
532         case 'n':               /* use following letters as text of new lines */
533             for (n = 0; n < screen_lines(sp); n++)
534                 CharOf(newtext[n][0]) = '.';
535             for (n = 0; n < screen_lines(sp); n++)
536                 if (line[n + 1] == '\n')
537                     break;
538                 else
539                     CharOf(newtext[n][0]) = line[n + 1];
540             break;
541
542         case 'o':               /* use following letters as text of old lines */
543             for (n = 0; n < screen_lines(sp); n++)
544                 CharOf(oldtext[n][0]) = '.';
545             for (n = 0; n < screen_lines(sp); n++)
546                 if (line[n + 1] == '\n')
547                     break;
548                 else
549                     CharOf(oldtext[n][0]) = line[n + 1];
550             break;
551
552         case 'd':               /* dump state of test arrays */
553 #ifdef TRACE
554             _nc_linedump();
555 #endif
556             (void) fputs("Old lines: [", stdout);
557             for (n = 0; n < screen_lines(sp); n++)
558                 putchar(CharOf(oldtext[n][0]));
559             putchar(']');
560             putchar('\n');
561             (void) fputs("New lines: [", stdout);
562             for (n = 0; n < screen_lines(sp); n++)
563                 putchar(CharOf(newtext[n][0]));
564             putchar(']');
565             putchar('\n');
566             break;
567
568         case 'h':               /* apply hash mapper and see scroll optimization */
569             _nc_hash_map();
570             (void) fputs("Result:\n", stderr);
571 #ifdef TRACE
572             _nc_linedump();
573 #endif
574             _nc_scroll_optimize();
575             (void) fputs("Done.\n", stderr);
576             break;
577         default:
578         case '?':
579             usage();
580             break;
581         }
582     }
583 #if NO_LEAKS
584     _nc_free_and_exit(EXIT_SUCCESS);
585 #else
586     return EXIT_SUCCESS;
587 #endif
588 }
589
590 #endif /* HASHDEBUG */
591
592 /* hashmap.c ends here */