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