ncurses/tty/hashmap.c

   1 /****************************************************************************
   2  * Copyright 2019-2020,2023 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.71 2023/09/16 16:28:53 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             FreeAndNull(oldhash(SP_PARM));
 323             FreeAndNull(newhash(SP_PARM));
 324             return;             /* malloc failure */
 325         }
 326         for (i = 0; i < screen_lines(SP_PARM); i++) {
 327             newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
 328             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 329         }
 330     }
 331
 332 #ifdef HASH_VERIFY
 333     for (i = 0; i < screen_lines(SP_PARM); i++) {
 334         if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
 335             fprintf(stderr, "error in newhash[%d]\n", i);
 336         if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
 337             fprintf(stderr, "error in oldhash[%d]\n", i);
 338     }
 339 #endif
 340
 341     /*
 342      * Set up and count line-hash values.
 343      */
 344     memset(hashtab(SP_PARM), '\0',
 345            sizeof(*(hashtab(SP_PARM)))
 346            * ((size_t) screen_lines(SP_PARM) + 1) * 2);
 347     for (i = 0; i < screen_lines(SP_PARM); i++) {
 348         unsigned long hashval = oldhash(SP_PARM)[i];
 349
 350         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 351             if (hsp->hashval == hashval)
 352                 break;
 353         hsp->hashval = hashval; /* in case this is a new entry */
 354         hsp->oldcount++;
 355         hsp->oldindex = i;
 356     }
 357     for (i = 0; i < screen_lines(SP_PARM); i++) {
 358         unsigned long hashval = newhash(SP_PARM)[i];
 359
 360         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 361             if (hsp->hashval == hashval)
 362                 break;
 363         hsp->hashval = hashval; /* in case this is a new entry */
 364         hsp->newcount++;
 365         hsp->newindex = i;
 366
 367         OLDNUM(SP_PARM, i) = _NEWINDEX;         /* initialize old indices array */
 368     }
 369
 370     /*
 371      * Mark line pairs corresponding to unique hash pairs.
 372      *
 373      * We don't mark lines with offset 0, because it can make fail
 374      * extending hunks by cost_effective. Otherwise, it does not
 375      * have any side effects.
 376      */
 377     for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 378         if (hsp->oldcount == 1 && hsp->newcount == 1
 379             && hsp->oldindex != hsp->newindex) {
 380             TR(TRACE_UPDATE | TRACE_MOVE,
 381                ("new line %d is hash-identical to old line %d (unique)",
 382                 hsp->newindex, hsp->oldindex));
 383             OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
 384         }
 385
 386     grow_hunks(SP_PARM);
 387
 388     /*
 389      * Eliminate bad or impossible shifts -- this includes removing
 390      * those hunks which could not grow because of conflicts, as well
 391      * those which are to be moved too far, they are likely to destroy
 392      * more than carry.
 393      */
 394     for (i = 0; i < screen_lines(SP_PARM);) {
 395         int start, shift, size;
 396
 397         while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
 398             i++;
 399         if (i >= screen_lines(SP_PARM))
 400             break;
 401         start = i;
 402         shift = OLDNUM(SP_PARM, i) - i;
 403         i++;
 404         while (i < screen_lines(SP_PARM)
 405                && OLDNUM(SP_PARM, i) != _NEWINDEX
 406                && OLDNUM(SP_PARM, i) - i == shift)
 407             i++;
 408         size = i - start;
 409         if (size < 3 || size + Min(size / 8, 2) < abs(shift)) {
 410             while (start < i) {
 411                 OLDNUM(SP_PARM, start) = _NEWINDEX;
 412                 start++;
 413             }
 414         }
 415     }
 416
 417     /* After clearing invalid hunks, try grow the rest. */
 418     grow_hunks(SP_PARM);
 419 }
 420
 421 #if NCURSES_SP_FUNCS
 422 NCURSES_EXPORT(void)
 423 _nc_hash_map(void)
 424 {
 425     NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
 426 }
 427 #endif
 428
 429 NCURSES_EXPORT(void)
 430 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
 431 {
 432     if (oldhash(SP_PARM))
 433         oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 434 }
 435
 436 #if NCURSES_SP_FUNCS
 437 NCURSES_EXPORT(void)
 438 _nc_make_oldhash(int i)
 439 {
 440     NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
 441 }
 442 #endif
 443
 444 NCURSES_EXPORT(void)
 445 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
 446 {
 447     size_t size;
 448     int i;
 449
 450     if (!oldhash(SP_PARM))
 451         return;
 452
 453     size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
 454     if (n > 0) {
 455         memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
 456         for (i = bot; i > bot - n; i--)
 457             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 458     } else {
 459         memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
 460         for (i = top; i < top - n; i++)
 461             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 462     }
 463 }
 464
 465 #if NCURSES_SP_FUNCS
 466 NCURSES_EXPORT(void)
 467 _nc_scroll_oldhash(int n, int top, int bot)
 468 {
 469     NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
 470 }
 471 #endif
 472
 473 #ifdef HASHDEBUG
 474 static void
 475 usage(void)
 476 {
 477     static const char *table[] =
 478     {
 479         "hashmap test-driver",
 480         "",
 481         "#  comment",
 482         "l  get initial line number vector",
 483         "n  use following letters as text of new lines",
 484         "o  use following letters as text of old lines",
 485         "d  dump state of test arrays",
 486         "h  apply hash mapper and see scroll optimization",
 487         "?  this message"
 488     };
 489     size_t n;
 490     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
 491         fprintf(stderr, "%s\n", table[n]);
 492 }
 493
 494 int
 495 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
 496 {
 497     char line[BUFSIZ], *st;
 498     int n;
 499
 500     if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
 501         return EXIT_FAILURE;
 502     (void) _nc_alloc_screen();
 503
 504     for (n = 0; n < screen_lines(sp); n++) {
 505         reallines[n] = n;
 506         oldnums[n] = _NEWINDEX;
 507         CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
 508     }
 509
 510     if (NC_ISATTY(fileno(stdin)))
 511         usage();
 512
 513 #ifdef TRACE
 514     _nc_tracing = TRACE_MOVE;
 515 #endif
 516     for (;;) {
 517         /* grab a test command */
 518         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
 519             break;
 520
 521         switch (line[0]) {
 522         case '#':               /* comment */
 523             (void) fputs(line, stderr);
 524             break;
 525
 526         case 'l':               /* get initial line number vector */
 527             for (n = 0; n < screen_lines(sp); n++) {
 528                 reallines[n] = n;
 529                 oldnums[n] = _NEWINDEX;
 530             }
 531             n = 0;
 532             st = strtok(line, " ");
 533             do {
 534                 oldnums[n++] = atoi(st);
 535             } while
 536                 ((st = strtok((char *) NULL, " ")) != 0);
 537             break;
 538
 539         case 'n':               /* use following letters as text of new lines */
 540             for (n = 0; n < screen_lines(sp); n++)
 541                 CharOf(newtext[n][0]) = '.';
 542             for (n = 0; n < screen_lines(sp); n++)
 543                 if (line[n + 1] == '\n')
 544                     break;
 545                 else
 546                     CharOf(newtext[n][0]) = line[n + 1];
 547             break;
 548
 549         case 'o':               /* use following letters as text of old lines */
 550             for (n = 0; n < screen_lines(sp); n++)
 551                 CharOf(oldtext[n][0]) = '.';
 552             for (n = 0; n < screen_lines(sp); n++)
 553                 if (line[n + 1] == '\n')
 554                     break;
 555                 else
 556                     CharOf(oldtext[n][0]) = line[n + 1];
 557             break;
 558
 559         case 'd':               /* dump state of test arrays */
 560 #ifdef TRACE
 561             _nc_linedump();
 562 #endif
 563             (void) fputs("Old lines: [", stdout);
 564             for (n = 0; n < screen_lines(sp); n++)
 565                 putchar(CharOf(oldtext[n][0]));
 566             putchar(']');
 567             putchar('\n');
 568             (void) fputs("New lines: [", stdout);
 569             for (n = 0; n < screen_lines(sp); n++)
 570                 putchar(CharOf(newtext[n][0]));
 571             putchar(']');
 572             putchar('\n');
 573             break;
 574
 575         case 'h':               /* apply hash mapper and see scroll optimization */
 576             _nc_hash_map();
 577             (void) fputs("Result:\n", stderr);
 578 #ifdef TRACE
 579             _nc_linedump();
 580 #endif
 581             _nc_scroll_optimize();
 582             (void) fputs("Done.\n", stderr);
 583             break;
 584         default:
 585         case '?':
 586             usage();
 587             break;
 588         }
 589     }
 590     exit_curses(EXIT_SUCCESS);
 591 }
 592
 593 #endif /* HASHDEBUG */
 594
 595 /* hashmap.c ends here */