ncurses/tty/hashmap.c

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