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