ncurses/tty/hashmap.c

   1 /****************************************************************************
   2  * Copyright 2019,2020 Thomas E. Dickey                                     *
   3  * Copyright 1998-2015,2016 Free Software Foundation, Inc.                  *
   4  *                                                                          *
   5  * Permission is hereby granted, free of charge, to any person obtaining a  *
   6  * copy of this software and associated documentation files (the            *
   7  * "Software"), to deal in the Software without restriction, including      *
   8  * without limitation the rights to use, copy, modify, merge, publish,      *
   9  * distribute, distribute with modifications, sublicense, and/or sell       *
  10  * copies of the Software, and to permit persons to whom the Software is    *
  11  * furnished to do so, subject to the following conditions:                 *
  12  *                                                                          *
  13  * The above copyright notice and this permission notice shall be included  *
  14  * in all copies or substantial portions of the Software.                   *
  15  *                                                                          *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
  17  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
  18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
  19  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
  20  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
  21  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
  22  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
  23  *                                                                          *
  24  * Except as contained in this notice, the name(s) of the above copyright   *
  25  * holders shall not be used in advertising or otherwise to promote the     *
  26  * sale, use or other dealings in this Software without prior written       *
  27  * authorization.                                                           *
  28  ****************************************************************************/
  29
  30 /****************************************************************************
  31  *  Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995               *
  32  *     and: Eric S. Raymond <esr@snark.thyrsus.com>                         *
  33  ****************************************************************************/
  34
  35 /******************************************************************************
  36
  37 NAME
  38    hashmap.c -- fill in scramble vector based on text hashes
  39
  40 SYNOPSIS
  41    void _nc_hash_map(void)
  42
  43 DESCRIPTION:
  44    This code attempts to recognize pairs of old and new lines in the physical
  45 and virtual screens.  When a line pair is recognized, the old line index is
  46 placed in the oldindex member of the virtual screen line, to be used by the
  47 vertical-motion optimizer portion of the update logic (see hardscroll.c).
  48
  49    Line pairs are recognized by applying a modified Heckel's algorithm,
  50 sped up by hashing.  If a line hash is unique in both screens, those
  51 lines must be a pair. Then if the lines just before or after the pair
  52 are the same or similar, they are a pair too.
  53
  54    We don't worry about false pairs produced by hash collisions, on the
  55 assumption that such cases are rare and will only make the latter stages
  56 of update less efficient, not introduce errors.
  57
  58 HOW TO TEST THIS:
  59
  60 Use the following production:
  61
  62 hashmap: hashmap.c
  63         $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
  64
  65 AUTHOR
  66     Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
  67     Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997
  68
  69 *****************************************************************************/
  70
  71 #include <curses.priv.h>
  72
  73 #ifndef CUR
  74 #define CUR SP_TERMTYPE
  75 #endif
  76
  77 MODULE_ID("$Id: hashmap.c,v 1.69 2020/05/31 17:50:48 tom Exp $")
  78
  79 #ifdef HASHDEBUG
  80
  81 # define _tracef        printf
  82 # undef TR
  83 # ifdef TRACE
  84 # define TR(n, a)       if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
  85 # else
  86 # define TR(n, a)       { _tracef a ; putchar('\n'); }
  87 # endif
  88 # undef screen_lines
  89 # define screen_lines(sp) MAXLINES
  90 # define TEXTWIDTH(sp)  1
  91 static int oldnums[MAXLINES], reallines[MAXLINES];
  92 static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH(sp)];
  93 static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH(sp)];
  94 # define OLDNUM(sp,n)   oldnums[n]
  95 # define OLDTEXT(sp,n)  oldtext[n]
  96 # define NEWTEXT(sp,m)  newtext[m]
  97 # define PENDING(sp,n)  1
  98
  99 #else /* !HASHDEBUG */
 100
 101 # define OLDNUM(sp,n)   (sp)->_oldnum_list[n]
 102 # define OLDTEXT(sp,n)  CurScreen(sp)->_line[n].text
 103 # define NEWTEXT(sp,m)  NewScreen(sp)->_line[m].text
 104 # define TEXTWIDTH(sp)  (CurScreen(sp)->_maxx + 1)
 105 # define PENDING(sp,n)  (NewScreen(sp)->_line[n].firstchar != _NOCHANGE)
 106
 107 #endif /* !HASHDEBUG */
 108
 109 #define oldhash(sp)     ((sp)->oldhash)
 110 #define newhash(sp)     ((sp)->newhash)
 111 #define hashtab(sp)     ((sp)->hashtab)
 112 #define lines_alloc(sp) ((sp)->hashtab_len)
 113
 114 #if USE_WIDEC_SUPPORT
 115 #define HASH_VAL(ch) (ch.chars[0])
 116 #else
 117 #define HASH_VAL(ch) (ch)
 118 #endif
 119
 120 static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT);
 121
 122 static NCURSES_INLINE unsigned long
 123 hash(SCREEN *sp, NCURSES_CH_T *text)
 124 {
 125     int i;
 126     NCURSES_CH_T ch;
 127     unsigned long result = 0;
 128     (void) sp;
 129
 130     for (i = TEXTWIDTH(sp); i > 0; i--) {
 131         ch = *text++;
 132         result += (result << 5) + (unsigned long) HASH_VAL(ch);
 133     }
 134     return result;
 135 }
 136
 137 /* approximate update cost */
 138 static int
 139 update_cost(SCREEN *sp, NCURSES_CH_T *from, NCURSES_CH_T *to)
 140 {
 141     int cost = 0;
 142     int i;
 143     (void) sp;
 144
 145     for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++)
 146         if (!(CharEq(*from, *to)))
 147             cost++;
 148
 149     return cost;
 150 }
 151
 152 static int
 153 update_cost_from_blank(SCREEN *sp, NCURSES_CH_T *to)
 154 {
 155     int cost = 0;
 156     int i;
 157     NCURSES_CH_T blank = blankchar;
 158     (void) sp;
 159
 160     if (back_color_erase)
 161         SetPair(blank, GetPair(stdscr->_nc_bkgd));
 162
 163     for (i = TEXTWIDTH(sp); i > 0; i--, to++)
 164         if (!(CharEq(blank, *to)))
 165             cost++;
 166
 167     return cost;
 168 }
 169
 170 /*
 171  * Returns true when moving line 'from' to line 'to' seems to be cost
 172  * effective. 'blank' indicates whether the line 'to' would become blank.
 173  */
 174 static NCURSES_INLINE bool
 175 cost_effective(SCREEN *sp, const int from, const int to, const int blank)
 176 {
 177     int new_from;
 178
 179     if (from == to)
 180         return FALSE;
 181
 182     new_from = OLDNUM(sp, from);
 183     if (new_from == _NEWINDEX)
 184         new_from = from;
 185
 186     /*
 187      * On the left side of >= is the cost before moving;
 188      * on the right side -- cost after moving.
 189      */
 190     return (((blank ? update_cost_from_blank(sp, NEWTEXT(sp, to))
 191               : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to)))
 192              + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
 193             >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from))
 194                  : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from)))
 195                 + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to))))
 196         ? TRUE : FALSE;
 197 }
 198
 199 static void
 200 grow_hunks(SCREEN *sp)
 201 {
 202     int back_limit;             /* limits for cells to fill */
 203     int back_ref_limit;         /* limit for references */
 204     int i;
 205     int next_hunk;
 206
 207     /*
 208      * This is tricky part.  We have unique pairs to use as anchors.
 209      * Use these to deduce the presence of spans of identical lines.
 210      */
 211     back_limit = 0;
 212     back_ref_limit = 0;
 213
 214     i = 0;
 215     while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
 216         i++;
 217     for (; i < screen_lines(sp); i = next_hunk) {
 218         int forward_limit;
 219         int forward_ref_limit;
 220         int end;
 221         int start = i;
 222         int shift = OLDNUM(sp, i) - i;
 223
 224         /* get forward limit */
 225         i = start + 1;
 226         while (i < screen_lines(sp)
 227                && OLDNUM(sp, i) != _NEWINDEX
 228                && OLDNUM(sp, i) - i == shift)
 229             i++;
 230         end = i;
 231         while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
 232             i++;
 233         next_hunk = i;
 234         forward_limit = i;
 235         if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
 236             forward_ref_limit = i;
 237         else
 238             forward_ref_limit = OLDNUM(sp, i);
 239
 240         i = start - 1;
 241         /* grow back */
 242         if (shift < 0)
 243             back_limit = back_ref_limit + (-shift);
 244         while (i >= back_limit) {
 245             if (newhash(sp)[i] == oldhash(sp)[i + shift]
 246                 || cost_effective(sp, i + shift, i, shift < 0)) {
 247                 OLDNUM(sp, i) = i + shift;
 248                 TR(TRACE_UPDATE | TRACE_MOVE,
 249                    ("connected new line %d to old line %d (backward continuation)",
 250                     i, i + shift));
 251             } else {
 252                 TR(TRACE_UPDATE | TRACE_MOVE,
 253                    ("not connecting new line %d to old line %d (backward continuation)",
 254                     i, i + shift));
 255                 break;
 256             }
 257             i--;
 258         }
 259
 260         i = end;
 261         /* grow forward */
 262         if (shift > 0)
 263             forward_limit = forward_ref_limit - shift;
 264         while (i < forward_limit) {
 265             if (newhash(sp)[i] == oldhash(sp)[i + shift]
 266                 || cost_effective(sp, i + shift, i, shift > 0)) {
 267                 OLDNUM(sp, i) = i + shift;
 268                 TR(TRACE_UPDATE | TRACE_MOVE,
 269                    ("connected new line %d to old line %d (forward continuation)",
 270                     i, i + shift));
 271             } else {
 272                 TR(TRACE_UPDATE | TRACE_MOVE,
 273                    ("not connecting new line %d to old line %d (forward continuation)",
 274                     i, i + shift));
 275                 break;
 276             }
 277             i++;
 278         }
 279
 280         back_ref_limit = back_limit = i;
 281         if (shift > 0)
 282             back_ref_limit += shift;
 283     }
 284 }
 285
 286 NCURSES_EXPORT(void)
 287 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
 288 {
 289     HASHMAP *hsp;
 290     register int i;
 291
 292     if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
 293         if (hashtab(SP_PARM))
 294             free(hashtab(SP_PARM));
 295         hashtab(SP_PARM) = typeMalloc(HASHMAP,
 296                                       ((size_t) screen_lines(SP_PARM) + 1) * 2);
 297         if (!hashtab(SP_PARM)) {
 298             if (oldhash(SP_PARM)) {
 299                 FreeAndNull(oldhash(SP_PARM));
 300             }
 301             lines_alloc(SP_PARM) = 0;
 302             return;
 303         }
 304         lines_alloc(SP_PARM) = screen_lines(SP_PARM);
 305     }
 306
 307     if (oldhash(SP_PARM) && newhash(SP_PARM)) {
 308         /* re-hash only changed lines */
 309         for (i = 0; i < screen_lines(SP_PARM); i++) {
 310             if (PENDING(SP_PARM, i))
 311                 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
 312         }
 313     } else {
 314         /* re-hash all */
 315         if (oldhash(SP_PARM) == 0)
 316             oldhash(SP_PARM) = typeCalloc(unsigned long,
 317                                             (size_t) screen_lines(SP_PARM));
 318         if (newhash(SP_PARM) == 0)
 319             newhash(SP_PARM) = typeCalloc(unsigned long,
 320                                             (size_t) screen_lines(SP_PARM));
 321         if (!oldhash(SP_PARM) || !newhash(SP_PARM))
 322             return;             /* malloc failure */
 323         for (i = 0; i < screen_lines(SP_PARM); i++) {
 324             newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
 325             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 326         }
 327     }
 328
 329 #ifdef HASH_VERIFY
 330     for (i = 0; i < screen_lines(SP_PARM); i++) {
 331         if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
 332             fprintf(stderr, "error in newhash[%d]\n", i);
 333         if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
 334             fprintf(stderr, "error in oldhash[%d]\n", i);
 335     }
 336 #endif
 337
 338     /*
 339      * Set up and count line-hash values.
 340      */
 341     memset(hashtab(SP_PARM), '\0',
 342            sizeof(*(hashtab(SP_PARM)))
 343            * ((size_t) screen_lines(SP_PARM) + 1) * 2);
 344     for (i = 0; i < screen_lines(SP_PARM); i++) {
 345         unsigned long hashval = oldhash(SP_PARM)[i];
 346
 347         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 348             if (hsp->hashval == hashval)
 349                 break;
 350         hsp->hashval = hashval; /* in case this is a new entry */
 351         hsp->oldcount++;
 352         hsp->oldindex = i;
 353     }
 354     for (i = 0; i < screen_lines(SP_PARM); i++) {
 355         unsigned long hashval = newhash(SP_PARM)[i];
 356
 357         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 358             if (hsp->hashval == hashval)
 359                 break;
 360         hsp->hashval = hashval; /* in case this is a new entry */
 361         hsp->newcount++;
 362         hsp->newindex = i;
 363
 364         OLDNUM(SP_PARM, i) = _NEWINDEX;         /* initialize old indices array */
 365     }
 366
 367     /*
 368      * Mark line pairs corresponding to unique hash pairs.
 369      *
 370      * We don't mark lines with offset 0, because it can make fail
 371      * extending hunks by cost_effective. Otherwise, it does not
 372      * have any side effects.
 373      */
 374     for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 375         if (hsp->oldcount == 1 && hsp->newcount == 1
 376             && hsp->oldindex != hsp->newindex) {
 377             TR(TRACE_UPDATE | TRACE_MOVE,
 378                ("new line %d is hash-identical to old line %d (unique)",
 379                 hsp->newindex, hsp->oldindex));
 380             OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
 381         }
 382
 383     grow_hunks(SP_PARM);
 384
 385     /*
 386      * Eliminate bad or impossible shifts -- this includes removing
 387      * those hunks which could not grow because of conflicts, as well
 388      * those which are to be moved too far, they are likely to destroy
 389      * more than carry.
 390      */
 391     for (i = 0; i < screen_lines(SP_PARM);) {
 392         int start, shift, size;
 393
 394         while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
 395             i++;
 396         if (i >= screen_lines(SP_PARM))
 397             break;
 398         start = i;
 399         shift = OLDNUM(SP_PARM, i) - i;
 400         i++;
 401         while (i < screen_lines(SP_PARM)
 402                && OLDNUM(SP_PARM, i) != _NEWINDEX
 403                && OLDNUM(SP_PARM, i) - i == shift)
 404             i++;
 405         size = i - start;
 406         if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
 407             while (start < i) {
 408                 OLDNUM(SP_PARM, start) = _NEWINDEX;
 409                 start++;
 410             }
 411         }
 412     }
 413
 414     /* After clearing invalid hunks, try grow the rest. */
 415     grow_hunks(SP_PARM);
 416 }
 417
 418 #if NCURSES_SP_FUNCS
 419 NCURSES_EXPORT(void)
 420 _nc_hash_map(void)
 421 {
 422     NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
 423 }
 424 #endif
 425
 426 NCURSES_EXPORT(void)
 427 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
 428 {
 429     if (oldhash(SP_PARM))
 430         oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 431 }
 432
 433 #if NCURSES_SP_FUNCS
 434 NCURSES_EXPORT(void)
 435 _nc_make_oldhash(int i)
 436 {
 437     NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
 438 }
 439 #endif
 440
 441 NCURSES_EXPORT(void)
 442 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
 443 {
 444     size_t size;
 445     int i;
 446
 447     if (!oldhash(SP_PARM))
 448         return;
 449
 450     size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
 451     if (n > 0) {
 452         memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
 453         for (i = bot; i > bot - n; i--)
 454             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 455     } else {
 456         memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
 457         for (i = top; i < top - n; i++)
 458             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 459     }
 460 }
 461
 462 #if NCURSES_SP_FUNCS
 463 NCURSES_EXPORT(void)
 464 _nc_scroll_oldhash(int n, int top, int bot)
 465 {
 466     NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
 467 }
 468 #endif
 469
 470 #ifdef HASHDEBUG
 471 static void
 472 usage(void)
 473 {
 474     static const char *table[] =
 475     {
 476         "hashmap test-driver",
 477         "",
 478         "#  comment",
 479         "l  get initial line number vector",
 480         "n  use following letters as text of new lines",
 481         "o  use following letters as text of old lines",
 482         "d  dump state of test arrays",
 483         "h  apply hash mapper and see scroll optimization",
 484         "?  this message"
 485     };
 486     size_t n;
 487     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
 488         fprintf(stderr, "%s\n", table[n]);
 489 }
 490
 491 int
 492 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
 493 {
 494     char line[BUFSIZ], *st;
 495     int n;
 496
 497     if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
 498         return EXIT_FAILURE;
 499     (void) _nc_alloc_screen();
 500
 501     for (n = 0; n < screen_lines(sp); n++) {
 502         reallines[n] = n;
 503         oldnums[n] = _NEWINDEX;
 504         CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
 505     }
 506
 507     if (NC_ISATTY(fileno(stdin)))
 508         usage();
 509
 510 #ifdef TRACE
 511     _nc_tracing = TRACE_MOVE;
 512 #endif
 513     for (;;) {
 514         /* grab a test command */
 515         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
 516             break;
 517
 518         switch (line[0]) {
 519         case '#':               /* comment */
 520             (void) fputs(line, stderr);
 521             break;
 522
 523         case 'l':               /* get initial line number vector */
 524             for (n = 0; n < screen_lines(sp); n++) {
 525                 reallines[n] = n;
 526                 oldnums[n] = _NEWINDEX;
 527             }
 528             n = 0;
 529             st = strtok(line, " ");
 530             do {
 531                 oldnums[n++] = atoi(st);
 532             } while
 533                 ((st = strtok((char *) NULL, " ")) != 0);
 534             break;
 535
 536         case 'n':               /* use following letters as text of new lines */
 537             for (n = 0; n < screen_lines(sp); n++)
 538                 CharOf(newtext[n][0]) = '.';
 539             for (n = 0; n < screen_lines(sp); n++)
 540                 if (line[n + 1] == '\n')
 541                     break;
 542                 else
 543                     CharOf(newtext[n][0]) = line[n + 1];
 544             break;
 545
 546         case 'o':               /* use following letters as text of old lines */
 547             for (n = 0; n < screen_lines(sp); n++)
 548                 CharOf(oldtext[n][0]) = '.';
 549             for (n = 0; n < screen_lines(sp); n++)
 550                 if (line[n + 1] == '\n')
 551                     break;
 552                 else
 553                     CharOf(oldtext[n][0]) = line[n + 1];
 554             break;
 555
 556         case 'd':               /* dump state of test arrays */
 557 #ifdef TRACE
 558             _nc_linedump();
 559 #endif
 560             (void) fputs("Old lines: [", stdout);
 561             for (n = 0; n < screen_lines(sp); n++)
 562                 putchar(CharOf(oldtext[n][0]));
 563             putchar(']');
 564             putchar('\n');
 565             (void) fputs("New lines: [", stdout);
 566             for (n = 0; n < screen_lines(sp); n++)
 567                 putchar(CharOf(newtext[n][0]));
 568             putchar(']');
 569             putchar('\n');
 570             break;
 571
 572         case 'h':               /* apply hash mapper and see scroll optimization */
 573             _nc_hash_map();
 574             (void) fputs("Result:\n", stderr);
 575 #ifdef TRACE
 576             _nc_linedump();
 577 #endif
 578             _nc_scroll_optimize();
 579             (void) fputs("Done.\n", stderr);
 580             break;
 581         default:
 582         case '?':
 583             usage();
 584             break;
 585         }
 586     }
 587     exit_curses(EXIT_SUCCESS);
 588 }
 589
 590 #endif /* HASHDEBUG */
 591
 592 /* hashmap.c ends here */