ncurses/tty/hashmap.c

   1 /****************************************************************************
   2  * Copyright (c) 1998-2007,2009 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
  72 MODULE_ID("$Id: hashmap.c,v 1.57 2009/04/18 19:03:50 tom Exp $")
  73
  74 #ifdef HASHDEBUG
  75
  76 # define _tracef        printf
  77 # undef TR
  78 # define TR(n, a)       if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
  79 # undef screen_lines
  80 # define screen_lines MAXLINES
  81 # define TEXTWIDTH      1
  82 int oldnums[MAXLINES], reallines[MAXLINES];
  83 static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH];
  84 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH];
  85 # define OLDNUM(sp,n)   oldnums[n]
  86 # define OLDTEXT(sp,n)  oldtext[n]
  87 # define NEWTEXT(sp,m)  newtext[m]
  88 # define PENDING(sp,n)  1
  89
  90 #else /* !HASHDEBUG */
  91
  92 # define OLDNUM(sp,n)   (sp)->_oldnum_list[n]
  93 # define OLDTEXT(sp,n)  (sp)->_curscr->_line[n].text
  94 # define NEWTEXT(sp,m)  (sp)->_newscr->_line[m].text
  95 # define TEXTWIDTH(sp)  ((sp)->_curscr->_maxx+1)
  96 # define PENDING(sp,n)  ((sp)->_newscr->_line[n].firstchar != _NOCHANGE)
  97
  98 #endif /* !HASHDEBUG */
  99
 100 #define oldhash(sp)     ((sp)->oldhash)
 101 #define newhash(sp)     ((sp)->newhash)
 102 #define hashtab(sp)     ((sp)->hashtab)
 103 #define lines_alloc(sp) ((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(SCREEN *sp, NCURSES_CH_T * text)
 115 {
 116     int i;
 117     NCURSES_CH_T ch;
 118     unsigned long result = 0;
 119     for (i = TEXTWIDTH(sp); 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(SCREEN *sp, NCURSES_CH_T * from, NCURSES_CH_T * to)
 129 {
 130     int cost = 0;
 131     int i;
 132
 133     for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
 134         if (!(CharEq(*from, *to)))
 135             cost++;
 136
 137     return cost;
 138 }
 139
 140 static int
 141 update_cost_from_blank(SCREEN *sp, 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(sp); i > 0; i--, to++)
 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(SCREEN *sp, 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(sp, 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(sp, NEWTEXT(sp, to))
 178               : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to)))
 179              + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
 180             >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from))
 181                  : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
 182                 + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to))))
 183         ? TRUE : FALSE;
 184 }
 185
 186 static void
 187 grow_hunks(SCREEN *sp)
 188 {
 189     int start, end, shift;
 190     int back_limit, forward_limit;      /* limits for cells to fill */
 191     int back_ref_limit, forward_ref_limit;      /* limits for refrences */
 192     int i;
 193     int next_hunk;
 194
 195     /*
 196      * This is tricky part.  We have unique pairs to use as anchors.
 197      * Use these to deduce the presence of spans of identical lines.
 198      */
 199     back_limit = 0;
 200     back_ref_limit = 0;
 201
 202     i = 0;
 203     while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
 204         i++;
 205     for (; i < screen_lines(sp); i = next_hunk) {
 206         start = i;
 207         shift = OLDNUM(sp, i) - i;
 208
 209         /* get forward limit */
 210         i = start + 1;
 211         while (i < screen_lines(sp)
 212                && OLDNUM(sp, i) != _NEWINDEX
 213                && OLDNUM(sp, i) - i == shift)
 214             i++;
 215         end = i;
 216         while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
 217             i++;
 218         next_hunk = i;
 219         forward_limit = i;
 220         if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
 221             forward_ref_limit = i;
 222         else
 223             forward_ref_limit = OLDNUM(sp, 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(sp)[i] == oldhash(sp)[i + shift]
 231                 || cost_effective(sp, i + shift, i, shift < 0)) {
 232                 OLDNUM(sp, 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(sp)[i] == oldhash(sp)[i + shift]
 251                 || cost_effective(sp, i + shift, i, shift > 0)) {
 252                 OLDNUM(sp, 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 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
 273 {
 274     HASHMAP *hsp;
 275     register int i;
 276     int start, shift, size;
 277
 278     if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
 279         if (hashtab(SP_PARM))
 280             free(hashtab(SP_PARM));
 281         hashtab(SP_PARM) = typeMalloc(HASHMAP, (screen_lines(SP_PARM) + 1) * 2);
 282         if (!hashtab(SP_PARM)) {
 283             if (oldhash(SP_PARM)) {
 284                 FreeAndNull(oldhash(SP_PARM));
 285             }
 286             lines_alloc(SP_PARM) = 0;
 287             return;
 288         }
 289         lines_alloc(SP_PARM) = screen_lines(SP_PARM);
 290     }
 291
 292     if (oldhash(SP_PARM) && newhash(SP_PARM)) {
 293         /* re-hash only changed lines */
 294         for (i = 0; i < screen_lines(SP_PARM); i++) {
 295             if (PENDING(SP_PARM, i))
 296                 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
 297         }
 298     } else {
 299         /* re-hash all */
 300         if (oldhash(SP_PARM) == 0)
 301             oldhash(SP_PARM) = typeCalloc(unsigned long,
 302                                             (unsigned) screen_lines(SP_PARM));
 303         if (newhash(SP_PARM) == 0)
 304             newhash(SP_PARM) = typeCalloc(unsigned long,
 305                                             (unsigned) screen_lines(SP_PARM));
 306         if (!oldhash(SP_PARM) || !newhash(SP_PARM))
 307             return;             /* malloc failure */
 308         for (i = 0; i < screen_lines(SP_PARM); i++) {
 309             newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
 310             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 311         }
 312     }
 313
 314 #ifdef HASH_VERIFY
 315     for (i = 0; i < screen_lines(SP_PARM); i++) {
 316         if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
 317             fprintf(stderr, "error in newhash[%d]\n", i);
 318         if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
 319             fprintf(stderr, "error in oldhash[%d]\n", i);
 320     }
 321 #endif
 322
 323     /*
 324      * Set up and count line-hash values.
 325      */
 326     memset(hashtab(SP_PARM), '\0',
 327            sizeof(*(hashtab(SP_PARM))) * (screen_lines(SP_PARM) + 1) * 2);
 328     for (i = 0; i < screen_lines(SP_PARM); i++) {
 329         unsigned long hashval = oldhash(SP_PARM)[i];
 330
 331         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 332             if (hsp->hashval == hashval)
 333                 break;
 334         hsp->hashval = hashval; /* in case this is a new entry */
 335         hsp->oldcount++;
 336         hsp->oldindex = i;
 337     }
 338     for (i = 0; i < screen_lines(SP_PARM); i++) {
 339         unsigned long hashval = newhash(SP_PARM)[i];
 340
 341         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 342             if (hsp->hashval == hashval)
 343                 break;
 344         hsp->hashval = hashval; /* in case this is a new entry */
 345         hsp->newcount++;
 346         hsp->newindex = i;
 347
 348         OLDNUM(SP_PARM, i) = _NEWINDEX;         /* initialize old indices array */
 349     }
 350
 351     /*
 352      * Mark line pairs corresponding to unique hash pairs.
 353      *
 354      * We don't mark lines with offset 0, because it can make fail
 355      * extending hunks by cost_effective. Otherwise, it does not
 356      * have any side effects.
 357      */
 358     for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 359         if (hsp->oldcount == 1 && hsp->newcount == 1
 360             && hsp->oldindex != hsp->newindex) {
 361             TR(TRACE_UPDATE | TRACE_MOVE,
 362                ("new line %d is hash-identical to old line %d (unique)",
 363                 hsp->newindex, hsp->oldindex));
 364             OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
 365         }
 366
 367     grow_hunks(SP_PARM);
 368
 369     /*
 370      * Eliminate bad or impossible shifts -- this includes removing
 371      * those hunks which could not grow because of conflicts, as well
 372      * those which are to be moved too far, they are likely to destroy
 373      * more than carry.
 374      */
 375     for (i = 0; i < screen_lines(SP_PARM);) {
 376         while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
 377             i++;
 378         if (i >= screen_lines(SP_PARM))
 379             break;
 380         start = i;
 381         shift = OLDNUM(SP_PARM, i) - i;
 382         i++;
 383         while (i < screen_lines(SP_PARM)
 384                && OLDNUM(SP_PARM, i) != _NEWINDEX
 385                && OLDNUM(SP_PARM, i) - i == shift)
 386             i++;
 387         size = i - start;
 388         if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
 389             while (start < i) {
 390                 OLDNUM(SP_PARM, start) = _NEWINDEX;
 391                 start++;
 392             }
 393         }
 394     }
 395
 396     /* After clearing invalid hunks, try grow the rest. */
 397     grow_hunks(SP_PARM);
 398 }
 399
 400 #if NCURSES_SP_FUNCS
 401 NCURSES_EXPORT(void)
 402 _nc_hash_map(void)
 403 {
 404     NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
 405 }
 406 #endif
 407
 408 NCURSES_EXPORT(void)
 409 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
 410 {
 411     if (oldhash(SP_PARM))
 412         oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 413 }
 414
 415 #if NCURSES_SP_FUNCS
 416 NCURSES_EXPORT(void)
 417 _nc_make_oldhash(int i)
 418 {
 419     NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
 420 }
 421 #endif
 422
 423 NCURSES_EXPORT(void)
 424 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
 425 {
 426     size_t size;
 427     int i;
 428
 429     if (!oldhash(SP_PARM))
 430         return;
 431
 432     size = sizeof(*(oldhash(SP_PARM))) * (bot - top + 1 - abs(n));
 433     if (n > 0) {
 434         memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
 435         for (i = bot; i > bot - n; i--)
 436             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 437     } else {
 438         memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
 439         for (i = top; i < top - n; i++)
 440             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 441     }
 442 }
 443
 444 #if NCURSES_SP_FUNCS
 445 NCURSES_EXPORT(void)
 446 _nc_scroll_oldhash(int n, int top, int bot)
 447 {
 448     NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
 449 }
 450 #endif
 451
 452 #ifdef HASHDEBUG
 453 static void
 454 usage(void)
 455 {
 456     static const char *table[] =
 457     {
 458         "hashmap test-driver",
 459         "",
 460         "#  comment",
 461         "l  get initial line number vector",
 462         "n  use following letters as text of new lines",
 463         "o  use following letters as text of old lines",
 464         "d  dump state of test arrays",
 465         "h  apply hash mapper and see scroll optimization",
 466         "?  this message"
 467     };
 468     size_t n;
 469     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
 470         fprintf(stderr, "%s\n", table[n]);
 471 }
 472
 473 int
 474 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
 475 {
 476     char line[BUFSIZ], *st;
 477     int n;
 478
 479     if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
 480         return EXIT_FAILURE;
 481     (void) _nc_alloc_screen();
 482
 483     for (n = 0; n < screen_lines; n++) {
 484         reallines[n] = n;
 485         oldnums[n] = _NEWINDEX;
 486         CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
 487     }
 488
 489     if (isatty(fileno(stdin)))
 490         usage();
 491
 492 #ifdef TRACE
 493     _nc_tracing = TRACE_MOVE;
 494 #endif
 495     for (;;) {
 496         /* grab a test command */
 497         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
 498             break;
 499
 500         switch (line[0]) {
 501         case '#':               /* comment */
 502             (void) fputs(line, stderr);
 503             break;
 504
 505         case 'l':               /* get initial line number vector */
 506             for (n = 0; n < screen_lines; n++) {
 507                 reallines[n] = n;
 508                 oldnums[n] = _NEWINDEX;
 509             }
 510             n = 0;
 511             st = strtok(line, " ");
 512             do {
 513                 oldnums[n++] = atoi(st);
 514             } while
 515                 ((st = strtok((char *) NULL, " ")) != 0);
 516             break;
 517
 518         case 'n':               /* use following letters as text of new lines */
 519             for (n = 0; n < screen_lines; n++)
 520                 CharOf(newtext[n][0]) = '.';
 521             for (n = 0; n < screen_lines; n++)
 522                 if (line[n + 1] == '\n')
 523                     break;
 524                 else
 525                     CharOf(newtext[n][0]) = line[n + 1];
 526             break;
 527
 528         case 'o':               /* use following letters as text of old lines */
 529             for (n = 0; n < screen_lines; n++)
 530                 CharOf(oldtext[n][0]) = '.';
 531             for (n = 0; n < screen_lines; n++)
 532                 if (line[n + 1] == '\n')
 533                     break;
 534                 else
 535                     CharOf(oldtext[n][0]) = line[n + 1];
 536             break;
 537
 538         case 'd':               /* dump state of test arrays */
 539 #ifdef TRACE
 540             _nc_linedump();
 541 #endif
 542             (void) fputs("Old lines: [", stdout);
 543             for (n = 0; n < screen_lines; n++)
 544                 putchar(CharOf(oldtext[n][0]));
 545             putchar(']');
 546             putchar('\n');
 547             (void) fputs("New lines: [", stdout);
 548             for (n = 0; n < screen_lines; n++)
 549                 putchar(CharOf(newtext[n][0]));
 550             putchar(']');
 551             putchar('\n');
 552             break;
 553
 554         case 'h':               /* apply hash mapper and see scroll optimization */
 555             _nc_hash_map();
 556             (void) fputs("Result:\n", stderr);
 557 #ifdef TRACE
 558             _nc_linedump();
 559 #endif
 560             _nc_scroll_optimize();
 561             (void) fputs("Done.\n", stderr);
 562             break;
 563         default:
 564         case '?':
 565             usage();
 566             break;
 567         }
 568     }
 569 #if NO_LEAKS
 570     _nc_free_and_exit(EXIT_SUCCESS);
 571 #else
 572     return EXIT_SUCCESS;
 573 #endif
 574 }
 575
 576 #endif /* HASHDEBUG */
 577
 578 /* hashmap.c ends here */