contrib/ncurses/ncurses/tty/hashmap.c

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