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