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 */