ncurses/tty/hashmap.c

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