ncurses/tty/hashmap.c

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