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