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