ncurses/tty/hashmap.c

   1 /****************************************************************************
   2  * Copyright (c) 1998-2014,2015 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.65 2015/07/25 20:13:56 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 start, end, shift;
 202     int back_limit, forward_limit;      /* limits for cells to fill */
 203     int back_ref_limit, forward_ref_limit;      /* limits for refrences */
 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         start = i;
 219         shift = OLDNUM(sp, i) - i;
 220
 221         /* get forward limit */
 222         i = start + 1;
 223         while (i < screen_lines(sp)
 224                && OLDNUM(sp, i) != _NEWINDEX
 225                && OLDNUM(sp, i) - i == shift)
 226             i++;
 227         end = i;
 228         while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX)
 229             i++;
 230         next_hunk = i;
 231         forward_limit = i;
 232         if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i)
 233             forward_ref_limit = i;
 234         else
 235             forward_ref_limit = OLDNUM(sp, i);
 236
 237         i = start - 1;
 238         /* grow back */
 239         if (shift < 0)
 240             back_limit = back_ref_limit + (-shift);
 241         while (i >= back_limit) {
 242             if (newhash(sp)[i] == oldhash(sp)[i + shift]
 243                 || cost_effective(sp, i + shift, i, shift < 0)) {
 244                 OLDNUM(sp, i) = i + shift;
 245                 TR(TRACE_UPDATE | TRACE_MOVE,
 246                    ("connected new line %d to old line %d (backward continuation)",
 247                     i, i + shift));
 248             } else {
 249                 TR(TRACE_UPDATE | TRACE_MOVE,
 250                    ("not connecting new line %d to old line %d (backward continuation)",
 251                     i, i + shift));
 252                 break;
 253             }
 254             i--;
 255         }
 256
 257         i = end;
 258         /* grow forward */
 259         if (shift > 0)
 260             forward_limit = forward_ref_limit - shift;
 261         while (i < forward_limit) {
 262             if (newhash(sp)[i] == oldhash(sp)[i + shift]
 263                 || cost_effective(sp, i + shift, i, shift > 0)) {
 264                 OLDNUM(sp, i) = i + shift;
 265                 TR(TRACE_UPDATE | TRACE_MOVE,
 266                    ("connected new line %d to old line %d (forward continuation)",
 267                     i, i + shift));
 268             } else {
 269                 TR(TRACE_UPDATE | TRACE_MOVE,
 270                    ("not connecting new line %d to old line %d (forward continuation)",
 271                     i, i + shift));
 272                 break;
 273             }
 274             i++;
 275         }
 276
 277         back_ref_limit = back_limit = i;
 278         if (shift > 0)
 279             back_ref_limit += shift;
 280     }
 281 }
 282
 283 NCURSES_EXPORT(void)
 284 NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0)
 285 {
 286     HASHMAP *hsp;
 287     register int i;
 288     int start, shift, size;
 289
 290     if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) {
 291         if (hashtab(SP_PARM))
 292             free(hashtab(SP_PARM));
 293         hashtab(SP_PARM) = typeMalloc(HASHMAP,
 294                                       ((size_t) screen_lines(SP_PARM) + 1) * 2);
 295         if (!hashtab(SP_PARM)) {
 296             if (oldhash(SP_PARM)) {
 297                 FreeAndNull(oldhash(SP_PARM));
 298             }
 299             lines_alloc(SP_PARM) = 0;
 300             return;
 301         }
 302         lines_alloc(SP_PARM) = screen_lines(SP_PARM);
 303     }
 304
 305     if (oldhash(SP_PARM) && newhash(SP_PARM)) {
 306         /* re-hash only changed lines */
 307         for (i = 0; i < screen_lines(SP_PARM); i++) {
 308             if (PENDING(SP_PARM, i))
 309                 newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
 310         }
 311     } else {
 312         /* re-hash all */
 313         if (oldhash(SP_PARM) == 0)
 314             oldhash(SP_PARM) = typeCalloc(unsigned long,
 315                                             (size_t) screen_lines(SP_PARM));
 316         if (newhash(SP_PARM) == 0)
 317             newhash(SP_PARM) = typeCalloc(unsigned long,
 318                                             (size_t) screen_lines(SP_PARM));
 319         if (!oldhash(SP_PARM) || !newhash(SP_PARM))
 320             return;             /* malloc failure */
 321         for (i = 0; i < screen_lines(SP_PARM); i++) {
 322             newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i));
 323             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 324         }
 325     }
 326
 327 #ifdef HASH_VERIFY
 328     for (i = 0; i < screen_lines(SP_PARM); i++) {
 329         if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i)))
 330             fprintf(stderr, "error in newhash[%d]\n", i);
 331         if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i)))
 332             fprintf(stderr, "error in oldhash[%d]\n", i);
 333     }
 334 #endif
 335
 336     /*
 337      * Set up and count line-hash values.
 338      */
 339     memset(hashtab(SP_PARM), '\0',
 340            sizeof(*(hashtab(SP_PARM)))
 341            * ((size_t) screen_lines(SP_PARM) + 1) * 2);
 342     for (i = 0; i < screen_lines(SP_PARM); i++) {
 343         unsigned long hashval = oldhash(SP_PARM)[i];
 344
 345         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 346             if (hsp->hashval == hashval)
 347                 break;
 348         hsp->hashval = hashval; /* in case this is a new entry */
 349         hsp->oldcount++;
 350         hsp->oldindex = i;
 351     }
 352     for (i = 0; i < screen_lines(SP_PARM); i++) {
 353         unsigned long hashval = newhash(SP_PARM)[i];
 354
 355         for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 356             if (hsp->hashval == hashval)
 357                 break;
 358         hsp->hashval = hashval; /* in case this is a new entry */
 359         hsp->newcount++;
 360         hsp->newindex = i;
 361
 362         OLDNUM(SP_PARM, i) = _NEWINDEX;         /* initialize old indices array */
 363     }
 364
 365     /*
 366      * Mark line pairs corresponding to unique hash pairs.
 367      *
 368      * We don't mark lines with offset 0, because it can make fail
 369      * extending hunks by cost_effective. Otherwise, it does not
 370      * have any side effects.
 371      */
 372     for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++)
 373         if (hsp->oldcount == 1 && hsp->newcount == 1
 374             && hsp->oldindex != hsp->newindex) {
 375             TR(TRACE_UPDATE | TRACE_MOVE,
 376                ("new line %d is hash-identical to old line %d (unique)",
 377                 hsp->newindex, hsp->oldindex));
 378             OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex;
 379         }
 380
 381     grow_hunks(SP_PARM);
 382
 383     /*
 384      * Eliminate bad or impossible shifts -- this includes removing
 385      * those hunks which could not grow because of conflicts, as well
 386      * those which are to be moved too far, they are likely to destroy
 387      * more than carry.
 388      */
 389     for (i = 0; i < screen_lines(SP_PARM);) {
 390         while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX)
 391             i++;
 392         if (i >= screen_lines(SP_PARM))
 393             break;
 394         start = i;
 395         shift = OLDNUM(SP_PARM, i) - i;
 396         i++;
 397         while (i < screen_lines(SP_PARM)
 398                && OLDNUM(SP_PARM, i) != _NEWINDEX
 399                && OLDNUM(SP_PARM, i) - i == shift)
 400             i++;
 401         size = i - start;
 402         if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
 403             while (start < i) {
 404                 OLDNUM(SP_PARM, start) = _NEWINDEX;
 405                 start++;
 406             }
 407         }
 408     }
 409
 410     /* After clearing invalid hunks, try grow the rest. */
 411     grow_hunks(SP_PARM);
 412 }
 413
 414 #if NCURSES_SP_FUNCS
 415 NCURSES_EXPORT(void)
 416 _nc_hash_map(void)
 417 {
 418     NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN);
 419 }
 420 #endif
 421
 422 NCURSES_EXPORT(void)
 423 NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i)
 424 {
 425     if (oldhash(SP_PARM))
 426         oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 427 }
 428
 429 #if NCURSES_SP_FUNCS
 430 NCURSES_EXPORT(void)
 431 _nc_make_oldhash(int i)
 432 {
 433     NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i);
 434 }
 435 #endif
 436
 437 NCURSES_EXPORT(void)
 438 NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot)
 439 {
 440     size_t size;
 441     int i;
 442
 443     if (!oldhash(SP_PARM))
 444         return;
 445
 446     size = sizeof(*(oldhash(SP_PARM))) * (size_t) (bot - top + 1 - abs(n));
 447     if (n > 0) {
 448         memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size);
 449         for (i = bot; i > bot - n; i--)
 450             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 451     } else {
 452         memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size);
 453         for (i = top; i < top - n; i++)
 454             oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i));
 455     }
 456 }
 457
 458 #if NCURSES_SP_FUNCS
 459 NCURSES_EXPORT(void)
 460 _nc_scroll_oldhash(int n, int top, int bot)
 461 {
 462     NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot);
 463 }
 464 #endif
 465
 466 #ifdef HASHDEBUG
 467 static void
 468 usage(void)
 469 {
 470     static const char *table[] =
 471     {
 472         "hashmap test-driver",
 473         "",
 474         "#  comment",
 475         "l  get initial line number vector",
 476         "n  use following letters as text of new lines",
 477         "o  use following letters as text of old lines",
 478         "d  dump state of test arrays",
 479         "h  apply hash mapper and see scroll optimization",
 480         "?  this message"
 481     };
 482     size_t n;
 483     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
 484         fprintf(stderr, "%s\n", table[n]);
 485 }
 486
 487 int
 488 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
 489 {
 490     char line[BUFSIZ], *st;
 491     int n;
 492
 493     if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR)
 494         return EXIT_FAILURE;
 495     (void) _nc_alloc_screen();
 496
 497     for (n = 0; n < screen_lines(sp); n++) {
 498         reallines[n] = n;
 499         oldnums[n] = _NEWINDEX;
 500         CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.';
 501     }
 502
 503     if (NC_ISATTY(fileno(stdin)))
 504         usage();
 505
 506 #ifdef TRACE
 507     _nc_tracing = TRACE_MOVE;
 508 #endif
 509     for (;;) {
 510         /* grab a test command */
 511         if (fgets(line, sizeof(line), stdin) == (char *) NULL)
 512             break;
 513
 514         switch (line[0]) {
 515         case '#':               /* comment */
 516             (void) fputs(line, stderr);
 517             break;
 518
 519         case 'l':               /* get initial line number vector */
 520             for (n = 0; n < screen_lines(sp); n++) {
 521                 reallines[n] = n;
 522                 oldnums[n] = _NEWINDEX;
 523             }
 524             n = 0;
 525             st = strtok(line, " ");
 526             do {
 527                 oldnums[n++] = atoi(st);
 528             } while
 529                 ((st = strtok((char *) NULL, " ")) != 0);
 530             break;
 531
 532         case 'n':               /* use following letters as text of new lines */
 533             for (n = 0; n < screen_lines(sp); n++)
 534                 CharOf(newtext[n][0]) = '.';
 535             for (n = 0; n < screen_lines(sp); n++)
 536                 if (line[n + 1] == '\n')
 537                     break;
 538                 else
 539                     CharOf(newtext[n][0]) = line[n + 1];
 540             break;
 541
 542         case 'o':               /* use following letters as text of old lines */
 543             for (n = 0; n < screen_lines(sp); n++)
 544                 CharOf(oldtext[n][0]) = '.';
 545             for (n = 0; n < screen_lines(sp); n++)
 546                 if (line[n + 1] == '\n')
 547                     break;
 548                 else
 549                     CharOf(oldtext[n][0]) = line[n + 1];
 550             break;
 551
 552         case 'd':               /* dump state of test arrays */
 553 #ifdef TRACE
 554             _nc_linedump();
 555 #endif
 556             (void) fputs("Old lines: [", stdout);
 557             for (n = 0; n < screen_lines(sp); n++)
 558                 putchar(CharOf(oldtext[n][0]));
 559             putchar(']');
 560             putchar('\n');
 561             (void) fputs("New lines: [", stdout);
 562             for (n = 0; n < screen_lines(sp); n++)
 563                 putchar(CharOf(newtext[n][0]));
 564             putchar(']');
 565             putchar('\n');
 566             break;
 567
 568         case 'h':               /* apply hash mapper and see scroll optimization */
 569             _nc_hash_map();
 570             (void) fputs("Result:\n", stderr);
 571 #ifdef TRACE
 572             _nc_linedump();
 573 #endif
 574             _nc_scroll_optimize();
 575             (void) fputs("Done.\n", stderr);
 576             break;
 577         default:
 578         case '?':
 579             usage();
 580             break;
 581         }
 582     }
 583 #if NO_LEAKS
 584     _nc_free_and_exit(EXIT_SUCCESS);
 585 #else
 586     return EXIT_SUCCESS;
 587 #endif
 588 }
 589
 590 #endif /* HASHDEBUG */
 591
 592 /* hashmap.c ends here */