ncurses/tty/hashmap.c

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