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