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