ncurses/tty/hashmap.c

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