ncurses 5.7 - patch 20090704
[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 #ifndef CUR
73 #define CUR SP_TERMTYPE
74 #endif
75
76 MODULE_ID("$Id: hashmap.c,v 1.59 2009/05/10 00:51:57 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)  (sp)->_curscr->_line[n].text
98 # define NEWTEXT(sp,m)  (sp)->_newscr->_line[m].text
99 # define TEXTWIDTH(sp)  ((sp)->_curscr->_maxx+1)
100 # define PENDING(sp,n)  ((sp)->_newscr->_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) + 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, (screen_lines(SP_PARM) + 1) * 2);
286         if (!hashtab(SP_PARM)) {
287             if (oldhash(SP_PARM)) {
288                 FreeAndNull(oldhash(SP_PARM));
289             }
290             lines_alloc(SP_PARM) = 0;
291             return;
292         }
293         lines_alloc(SP_PARM) = screen_lines(SP_PARM);
294     }
295
296     if (oldhash(SP_PARM) && newhash(SP_PARM)) {
297         /* re-hash only changed lines */
298         for (i = 0; i < screen_lines(SP_PARM); i++) {
299             if (PENDING(SP_PARM, i))
300                 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
301         }
302     } else {
303         /* re-hash all */
304         if (oldhash(SP_PARM) == 0)
305             oldhash(SP_PARM) = typeCalloc(unsigned long,
306                                             (unsigned) screen_lines(SP_PARM));
307         if (newhash(SP_PARM) == 0)
308             newhash(SP_PARM) = typeCalloc(unsigned long,
309                                             (unsigned) screen_lines(SP_PARM));
310         if (!oldhash(SP_PARM) || !newhash(SP_PARM))
311             return;             /* malloc failure */
312         for (i = 0; i < screen_lines(SP_PARM); i++) {
313             newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
314             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
315         }
316     }
317
318 #ifdef HASH_VERIFY
319     for (i = 0; i < screen_lines(SP_PARM); i++) {
320         if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
321             fprintf(stderr, "error in newhash[%d]\n", i);
322         if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
323             fprintf(stderr, "error in oldhash[%d]\n", i);
324     }
325 #endif
326
327     /*
328      * Set up and count line-hash values.
329      */
330     memset(hashtab(SP_PARM), '\0',
331            sizeof(*(hashtab(SP_PARM))) * (screen_lines(SP_PARM) + 1) * 2);
332     for (i = 0; i < screen_lines(SP_PARM); i++) {
333         unsigned long hashval = oldhash(SP_PARM)[i];
334
335         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
336             if (hsp->hashval == hashval)
337                 break;
338         hsp->hashval = hashval; /* in case this is a new entry */
339         hsp->oldcount++;
340         hsp->oldindex = i;
341     }
342     for (i = 0; i < screen_lines(SP_PARM); i++) {
343         unsigned long hashval = newhash(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->newcount++;
350         hsp->newindex = i;
351
352         OLDNUM(SP_PARM, i) = _NEWINDEX;         /* initialize old indices array */
353     }
354
355     /*
356      * Mark line pairs corresponding to unique hash pairs.
357      *
358      * We don't mark lines with offset 0, because it can make fail
359      * extending hunks by cost_effective. Otherwise, it does not
360      * have any side effects.
361      */
362     for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
363         if (hsp->oldcount == 1 && hsp->newcount == 1
364             && hsp->oldindex != hsp->newindex) {
365             TR(TRACE_UPDATE | TRACE_MOVE,
366                ("new line %d is hash-identical to old line %d (unique)",
367                 hsp->newindex, hsp->oldindex));
368             OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
369         }
370
371     grow_hunks(SP_PARM);
372
373     /*
374      * Eliminate bad or impossible shifts -- this includes removing
375      * those hunks which could not grow because of conflicts, as well
376      * those which are to be moved too far, they are likely to destroy
377      * more than carry.
378      */
379     for (i = 0; i < screen_lines(SP_PARM);) {
380         while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
381             i++;
382         if (i >= screen_lines(SP_PARM))
383             break;
384         start = i;
385         shift = OLDNUM(SP_PARM, i) - i;
386         i++;
387         while (i < screen_lines(SP_PARM)
388                && OLDNUM(SP_PARM, i) != _NEWINDEX
389                && OLDNUM(SP_PARM, i) - i == shift)
390             i++;
391         size = i - start;
392         if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
393             while (start < i) {
394                 OLDNUM(SP_PARM, start) = _NEWINDEX;
395                 start++;
396             }
397         }
398     }
399
400     /* After clearing invalid hunks, try grow the rest. */
401     grow_hunks(SP_PARM);
402 }
403
404 #if NCURSES_SP_FUNCS
405 NCURSES_EXPORT(void)
406 _nc_hash_map(void)
407 {
408     NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
409 }
410 #endif
411
412 NCURSES_EXPORT(void)
413 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
414 {
415     if (oldhash(SP_PARM))
416         oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
417 }
418
419 #if NCURSES_SP_FUNCS
420 NCURSES_EXPORT(void)
421 _nc_make_oldhash(int i)
422 {
423     NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
424 }
425 #endif
426
427 NCURSES_EXPORT(void)
428 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
429 {
430     size_t size;
431     int i;
432
433     if (!oldhash(SP_PARM))
434         return;
435
436     size = sizeof(*(oldhash(SP_PARM))) * (bot - top + 1 - abs(n));
437     if (n > 0) {
438         memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
439         for (i = bot; i > bot - n; i--)
440             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
441     } else {
442         memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
443         for (i = top; i < top - n; i++)
444             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
445     }
446 }
447
448 #if NCURSES_SP_FUNCS
449 NCURSES_EXPORT(void)
450 _nc_scroll_oldhash(int n, int top, int bot)
451 {
452     NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
453 }
454 #endif
455
456 #ifdef HASHDEBUG
457 static void
458 usage(void)
459 {
460     static const char *table[] =
461     {
462         "hashmap test-driver",
463         "",
464         "#  comment",
465         "l  get initial line number vector",
466         "n  use following letters as text of new lines",
467         "o  use following letters as text of old lines",
468         "d  dump state of test arrays",
469         "h  apply hash mapper and see scroll optimization",
470         "?  this message"
471     };
472     size_t n;
473     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
474         fprintf(stderr, "%s\n", table[n]);
475 }
476
477 int
478 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
479 {
480     char line[BUFSIZ], *st;
481     int n;
482
483     if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
484         return EXIT_FAILURE;
485     (void) _nc_alloc_screen();
486
487     for (n = 0; n < screen_lines; n++) {
488         reallines[n] = n;
489         oldnums[n] = _NEWINDEX;
490         CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
491     }
492
493     if (isatty(fileno(stdin)))
494         usage();
495
496 #ifdef TRACE
497     _nc_tracing = TRACE_MOVE;
498 #endif
499     for (;;) {
500         /* grab a test command */
501         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
502             break;
503
504         switch (line[0]) {
505         case '#':               /* comment */
506             (void) fputs(line, stderr);
507             break;
508
509         case 'l':               /* get initial line number vector */
510             for (n = 0; n < screen_lines; n++) {
511                 reallines[n] = n;
512                 oldnums[n] = _NEWINDEX;
513             }
514             n = 0;
515             st = strtok(line, " ");
516             do {
517                 oldnums[n++] = atoi(st);
518             } while
519                 ((st = strtok((char *) NULL, " ")) != 0);
520             break;
521
522         case 'n':               /* use following letters as text of new lines */
523             for (n = 0; n < screen_lines; n++)
524                 CharOf(newtext[n][0]) = '.';
525             for (n = 0; n < screen_lines; n++)
526                 if (line[n + 1] == '\n')
527                     break;
528                 else
529                     CharOf(newtext[n][0]) = line[n + 1];
530             break;
531
532         case 'o':               /* use following letters as text of old lines */
533             for (n = 0; n < screen_lines; n++)
534                 CharOf(oldtext[n][0]) = '.';
535             for (n = 0; n < screen_lines; n++)
536                 if (line[n + 1] == '\n')
537                     break;
538                 else
539                     CharOf(oldtext[n][0]) = line[n + 1];
540             break;
541
542         case 'd':               /* dump state of test arrays */
543 #ifdef TRACE
544             _nc_linedump();
545 #endif
546             (void) fputs("Old lines: [", stdout);
547             for (n = 0; n < screen_lines; n++)
548                 putchar(CharOf(oldtext[n][0]));
549             putchar(']');
550             putchar('\n');
551             (void) fputs("New lines: [", stdout);
552             for (n = 0; n < screen_lines; n++)
553                 putchar(CharOf(newtext[n][0]));
554             putchar(']');
555             putchar('\n');
556             break;
557
558         case 'h':               /* apply hash mapper and see scroll optimization */
559             _nc_hash_map();
560             (void) fputs("Result:\n", stderr);
561 #ifdef TRACE
562             _nc_linedump();
563 #endif
564             _nc_scroll_optimize();
565             (void) fputs("Done.\n", stderr);
566             break;
567         default:
568         case '?':
569             usage();
570             break;
571         }
572     }
573 #if NO_LEAKS
574     _nc_free_and_exit(EXIT_SUCCESS);
575 #else
576     return EXIT_SUCCESS;
577 #endif
578 }
579
580 #endif /* HASHDEBUG */
581
582 /* hashmap.c ends here */