ncurses 4.1
[ncurses.git] / ncurses / hashmap.c
1
2 /***************************************************************************
3 *                            COPYRIGHT NOTICE                              *
4 ****************************************************************************
5 *                ncurses is copyright (C) 1992-1995                        *
6 *                          Zeyd M. Ben-Halim                               *
7 *                          zmbenhal@netcom.com                             *
8 *                          Eric S. Raymond                                 *
9 *                          esr@snark.thyrsus.com                           *
10 *                                                                          *
11 *        Permission is hereby granted to reproduce and distribute ncurses  *
12 *        by any means and for any fee, whether alone or as part of a       *
13 *        larger distribution, in source or in binary form, PROVIDED        *
14 *        this notice is included with any such distribution, and is not    *
15 *        removed from any of its header files. Mention of ncurses in any   *
16 *        applications linked with it is highly appreciated.                *
17 *                                                                          *
18 *        ncurses comes AS IS with no warranty, implied or expressed.       *
19 *                                                                          *
20 ***************************************************************************/
21
22 /******************************************************************************
23
24 NAME
25    hashmap.c -- fill in scramble vector based on text hashes
26
27 SYNOPSIS
28    void _nc_hash_map(void)
29
30 DESCRIPTION:
31    This code attempts to recognize pairs of old and new lines in the physical
32 and virtual screens.  When a line pair is recognized, the old line index is
33 placed in the oldindex member of the virtual screen line, to be used by the
34 vertical-motion optimizer portion of the update logic (see hardscroll.c).
35
36    Line pairs are recognized by applying a modified Heckel's algorithm,
37 sped up by hashing.  If a line hash is unique in both screens, those
38 lines must be a pair.  If the hashes of the two lines immediately following
39 lines known to be a pair are the same, the following lines are also a pair.
40 We apply these rules repeatedly until no more pairs are found.  The
41 modifications stem from the fact that there may already be oldindex info
42 associated with the virtual screen, which has to be respected.
43
44    We don't worry about false pairs produced by hash collisions, on the
45 assumption that such cases are rare and will only make the latter stages
46 of update less efficient, not introduce errors.
47
48 HOW TO TEST THIS:
49
50 Use the following production:
51
52 hashmap: hashmap.c
53         $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
54
55 AUTHOR
56     Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
57
58 *****************************************************************************/
59
60 #include <curses.priv.h>
61
62 MODULE_ID("$Id: hashmap.c,v 1.12 1997/05/03 20:30:06 tom Exp $")
63
64 #ifdef HASHDEBUG
65 #define LINES   24
66 #define TEXTWIDTH       1
67 int oldnums[LINES], reallines[LINES];
68 static chtype oldtext[LINES][TEXTWIDTH], newtext[LINES][TEXTWIDTH];
69 #define OLDNUM(n)       oldnums[n]
70 #define REAL(m)         reallines[m]
71 #define OLDTEXT(n)      oldtext[n]
72 #define NEWTEXT(m)      newtext[m]
73 #undef T
74 #define T(x)            (void) printf x ; (void) putchar('\n');
75 #else
76 #include <curses.h>
77 #define OLDNUM(n)       newscr->_line[n].oldindex
78 #define REAL(m)         curscr->_line[m].oldindex
79 #define OLDTEXT(n)      curscr->_line[n].text
80 #define NEWTEXT(m)      newscr->_line[m].text
81 #define TEXTWIDTH       (curscr->_maxx+1)
82 #ifndef _NEWINDEX
83 #define _NEWINDEX       -1
84 #endif /* _NEWINDEX */
85 #endif /* HASHDEBUG */
86
87 /* Chris Torek's hash function (from his DB package). */
88 static inline unsigned long hash4(const void *key, size_t len)
89 {
90     register long h, loop;
91     register unsigned const char *k;
92
93 #define HASH4a   h = (h << 5) - h + *k++;
94 #define HASH4b   h = (h << 5) + h + *k++;
95 #define HASH4 HASH4b
96     h = 0;
97     k = (unsigned const char *)key;
98     if (len > 0) {
99         loop = (len + 8 - 1) >> 3;
100         switch (len & (8 - 1)) {
101         case 0:
102             do {        /* All fall throughs */
103                 HASH4;
104             case 7:
105                 HASH4;
106             case 6:
107                 HASH4;
108             case 5:
109                 HASH4;
110             case 4:
111                 HASH4;
112             case 3:
113                 HASH4;
114             case 2:
115                 HASH4;
116             case 1:
117                 HASH4;
118             } while (--loop);
119         }
120     }
121     return ((unsigned long)h);
122 }
123
124 static inline unsigned long hash(chtype *text)
125 {
126     return(hash4(text, TEXTWIDTH*sizeof(*text)));
127 }
128
129 void _nc_hash_map(void)
130 {
131     typedef struct
132     {
133         unsigned long   hashval;
134         int             oldcount, newcount;
135         int             oldindex, newindex;
136     }
137     sym;
138     sym hashtab[MAXLINES*2], *sp;
139     register int i;
140     long oldhash[MAXLINES], newhash[MAXLINES];
141     bool keepgoing;
142
143     /*
144      * Set up and count line-hash values.
145      */
146     memset(hashtab, '\0', sizeof(sym) * MAXLINES);
147     for (i = 0; i < LINES; i++)
148     {
149         unsigned long hashval = hash(OLDTEXT(i));
150
151         for (sp = hashtab; sp->hashval; sp++)
152             if (sp->hashval == hashval)
153                 break;
154         sp->hashval = hashval;  /* in case this is a new entry */
155         oldhash[i] = hashval;
156         sp->oldcount++;
157         sp->oldindex = i;
158     }
159     for (i = 0; i < LINES; i++)
160     {
161         unsigned long hashval = hash(NEWTEXT(i));
162
163         for (sp = hashtab; sp->hashval; sp++)
164             if (sp->hashval == hashval)
165                 break;
166         sp->hashval = hashval;  /* in case this is a new entry */
167         newhash[i] = hashval;
168         sp->newcount++;
169         sp->newindex = i;
170     
171         OLDNUM(i) = _NEWINDEX;
172     }
173
174     /*
175      * Mark line pairs corresponding to unique hash pairs.
176      * Note: we only do this where the new line doesn't
177      * already have a valid oldindex -- this way we preserve the
178      * information left in place by the software scrolling functions.
179      */
180     for (sp = hashtab; sp->hashval; sp++)
181         if (sp->oldcount == 1 && sp->newcount == 1
182             && OLDNUM(sp->newindex) == _NEWINDEX)
183         {
184             TR(TRACE_UPDATE | TRACE_MOVE,
185                ("new line %d is hash-identical to old line %d (unique)",
186                    sp->newindex, sp->oldindex));
187             OLDNUM(sp->newindex) = sp->oldindex;
188         }
189
190     /*
191      * Now for the tricky part.  We have unique pairs to use as anchors.
192      * Use these to deduce the presence of spans of identical lines.
193      */
194     do {
195         keepgoing = FALSE;
196
197         for (i = 0; i < LINES-1; i++)
198             if (OLDNUM(i) != _NEWINDEX && OLDNUM(i+1) == _NEWINDEX)
199             {
200                 if (OLDNUM(i) + 1 < LINES
201                             && newhash[i+1] == oldhash[OLDNUM(i) + 1])
202                 {
203                     OLDNUM(i+1) = OLDNUM(i) + 1;
204                     TR(TRACE_UPDATE | TRACE_MOVE,
205                        ("new line %d is hash-identical to old line %d (forward continuation)",
206                         i+1, OLDNUM(i) + 1));
207                     keepgoing = TRUE;
208                 }
209             }
210
211         for (i = 0; i < LINES-1; i++)
212             if (OLDNUM(i) != _NEWINDEX && OLDNUM(i-1) == _NEWINDEX)
213             {
214                 if (OLDNUM(i) - 1 >= 0
215                             && newhash[i-1] == oldhash[OLDNUM(i) - 1])
216                 {
217                     OLDNUM(i-1) = OLDNUM(i) - 1;
218                     TR(TRACE_UPDATE | TRACE_MOVE,
219                        ("new line %d is hash-identical to old line %d (backward continuation)",
220                         i-1, OLDNUM(i) - 1));
221                     keepgoing = TRUE;
222                 }
223             }
224     } while
225         (keepgoing);
226 }
227
228 #ifdef HASHDEBUG
229
230 int
231 main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED)
232 {
233     extern void _nc_linedump(void);
234     char        line[BUFSIZ], *st;
235     int         n;
236
237     for (n = 0; n < LINES; n++)
238     {
239         reallines[n] = n;
240         oldnums[n] = _NEWINDEX;
241         oldtext[n][0] = newtext[n][0] = '.';
242     }
243
244     _nc_tracing = TRACE_MOVE;
245     for (;;)
246     {
247         /* grab a test command */
248         if (fgets(line, sizeof(line), stdin) == (char *)NULL)
249             exit(EXIT_SUCCESS);
250
251         switch(line[0])
252         {
253         case '#':       /* comment */
254             (void) fputs(line, stderr);
255             break;
256
257         case 'l':       /* get initial line number vector */
258             for (n = 0; n < LINES; n++)
259             {
260                 reallines[n] = n;
261                 oldnums[n] = _NEWINDEX;
262             }
263             n = 0;
264             st = strtok(line, " ");
265             do {
266                 oldnums[n++] = atoi(st);
267             } while
268                 ((st = strtok((char *)NULL, " ")) != 0);
269             break;
270
271         case 'n':       /* use following letters as text of new lines */
272             for (n = 0; n < LINES; n++)
273                 newtext[n][0] = '.';
274             for (n = 0; n < LINES; n++)
275                 if (line[n+1] == '\n')
276                     break;
277                 else
278                     newtext[n][0] = line[n+1];
279             break;
280
281         case 'o':       /* use following letters as text of old lines */
282             for (n = 0; n < LINES; n++)
283                 oldtext[n][0] = '.';
284             for (n = 0; n < LINES; n++)
285                 if (line[n+1] == '\n')
286                     break;
287                 else
288                     oldtext[n][0] = line[n+1];
289             break;
290
291         case 'd':       /* dump state of test arrays */
292             _nc_linedump();
293             (void) fputs("Old lines: [", stdout);
294             for (n = 0; n < LINES; n++)
295                 putchar(oldtext[n][0]);
296             putchar(']');
297             putchar('\n');
298             (void) fputs("New lines: [", stdout);
299             for (n = 0; n < LINES; n++)
300                 putchar(newtext[n][0]);
301             putchar(']');
302             putchar('\n');
303             break;
304
305         case 'h':       /* apply hash mapper and see scroll optimization */
306             _nc_hash_map();
307             (void) fputs("Result:\n", stderr);
308             _nc_linedump();
309             _nc_scroll_optimize();
310             (void) fputs("Done.\n", stderr);
311             break;
312         }
313     }
314     return EXIT_SUCCESS;
315 }
316
317 #endif /* HASHDEBUG */
318
319 /* hashmap.c ends here */