ncurses/tty/hashmap.c

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