1 /* $OpenBSD: hashmap.c,v 1.4 1999/03/18 16:46:58 millert Exp $ */ 2 3 /**************************************************************************** 4 * Copyright (c) 1998 Free Software Foundation, Inc. * 5 * * 6 * Permission is hereby granted, free of charge, to any person obtaining a * 7 * copy of this software and associated documentation files (the * 8 * "Software"), to deal in the Software without restriction, including * 9 * without limitation the rights to use, copy, modify, merge, publish, * 10 * distribute, distribute with modifications, sublicense, and/or sell * 11 * copies of the Software, and to permit persons to whom the Software is * 12 * furnished to do so, subject to the following conditions: * 13 * * 14 * The above copyright notice and this permission notice shall be included * 15 * in all copies or substantial portions of the Software. * 16 * * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 20 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 21 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 22 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 23 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 24 * * 25 * Except as contained in this notice, the name(s) of the above copyright * 26 * holders shall not be used in advertising or otherwise to promote the * 27 * sale, use or other dealings in this Software without prior written * 28 * authorization. * 29 ****************************************************************************/ 30 31 /**************************************************************************** 32 * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 * 33 * and: Eric S. Raymond <esr@snark.thyrsus.com> * 34 ****************************************************************************/ 35 36 /****************************************************************************** 37 38 NAME 39 hashmap.c -- fill in scramble vector based on text hashes 40 41 SYNOPSIS 42 void _nc_hash_map(void) 43 44 DESCRIPTION: 45 This code attempts to recognize pairs of old and new lines in the physical 46 and virtual screens. When a line pair is recognized, the old line index is 47 placed in the oldindex member of the virtual screen line, to be used by the 48 vertical-motion optimizer portion of the update logic (see hardscroll.c). 49 50 Line pairs are recognized by applying a modified Heckel's algorithm, 51 sped up by hashing. If a line hash is unique in both screens, those 52 lines must be a pair. Then if the lines just before or after the pair 53 are the same or similar, they are a pair too. 54 55 We don't worry about false pairs produced by hash collisions, on the 56 assumption that such cases are rare and will only make the latter stages 57 of update less efficient, not introduce errors. 58 59 HOW TO TEST THIS: 60 61 Use the following production: 62 63 hashmap: hashmap.c 64 $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap 65 66 AUTHOR 67 Eric S. Raymond <esr@snark.thyrsus.com>, May 1996 68 Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997 69 70 *****************************************************************************/ 71 72 #include <curses.priv.h> 73 #include <term.h> /* for back_color_erase */ 74 75 MODULE_ID("$From: hashmap.c,v 1.33 1999/03/18 02:09:45 Alexander.V.Lukyanov Exp $") 76 77 #ifdef HASHDEBUG 78 79 # define _tracef printf 80 # undef TR 81 # define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); } 82 # undef screen_lines 83 # define screen_lines MAXLINES 84 # define TEXTWIDTH 1 85 int oldnums[MAXLINES], reallines[MAXLINES]; 86 static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH]; 87 # define OLDNUM(n) oldnums[n] 88 # define OLDTEXT(n) oldtext[n] 89 # define NEWTEXT(m) newtext[m] 90 # define PENDING(n) 1 91 92 #else /* !HASHDEBUG */ 93 94 # define OLDNUM(n) _nc_oldnums[n] 95 # define OLDTEXT(n) curscr->_line[n].text 96 # define NEWTEXT(m) newscr->_line[m].text 97 # define TEXTWIDTH (curscr->_maxx+1) 98 # define PENDING(n) (newscr->_line[n].firstchar != _NOCHANGE) 99 100 #endif /* !HASHDEBUG */ 101 102 #define oldhash (SP->oldhash) 103 #define newhash (SP->newhash) 104 105 static inline unsigned long hash(chtype *text) 106 { 107 int i; 108 chtype ch; 109 unsigned long result = 0; 110 for (i = TEXTWIDTH; i>0; i--) 111 { 112 ch = *text++; 113 result += (result<<5) + ch; 114 } 115 return result; 116 } 117 118 /* approximate update cost */ 119 static int update_cost(chtype *from,chtype *to) 120 { 121 int cost=0; 122 int i; 123 124 for (i=TEXTWIDTH; i>0; i--) 125 if (*from++ != *to++) 126 cost++; 127 128 return cost; 129 } 130 static int update_cost_from_blank(chtype *to) 131 { 132 int cost=0; 133 int i; 134 chtype blank = BLANK; 135 136 if (back_color_erase) 137 blank |= (stdscr->_bkgd & A_COLOR); 138 139 for (i=TEXTWIDTH; i>0; i--) 140 if (blank != *to++) 141 cost++; 142 143 return cost; 144 } 145 146 /* 147 * Returns true when moving line 'from' to line 'to' seems to be cost 148 * effective. 'blank' indicates whether the line 'to' would become blank. 149 */ 150 static inline bool cost_effective(const int from, const int to, const bool blank) 151 { 152 int new_from; 153 154 if (from == to) 155 return FALSE; 156 157 new_from = OLDNUM(from); 158 if (new_from == _NEWINDEX) 159 new_from = from; 160 161 /* 162 * On the left side of >= is the cost before moving; 163 * on the right side -- cost after moving. 164 */ 165 return (((blank ? update_cost_from_blank(NEWTEXT(to)) 166 : update_cost(OLDTEXT(to),NEWTEXT(to))) 167 + update_cost(OLDTEXT(new_from),NEWTEXT(from))) 168 >= ((new_from==from ? update_cost_from_blank(NEWTEXT(from)) 169 : update_cost(OLDTEXT(new_from),NEWTEXT(from))) 170 + update_cost(OLDTEXT(from),NEWTEXT(to)))) ? TRUE : FALSE; 171 } 172 173 174 typedef struct 175 { 176 unsigned long hashval; 177 int oldcount, newcount; 178 int oldindex, newindex; 179 } 180 sym; 181 182 static sym *hashtab=0; 183 static int lines_alloc=0; 184 185 static void grow_hunks(void) 186 { 187 int start, end, shift; 188 int back_limit, forward_limit; /* limits for cells to fill */ 189 int back_ref_limit, forward_ref_limit; /* limits for refrences */ 190 int i; 191 int next_hunk; 192 193 /* 194 * This is tricky part. We have unique pairs to use as anchors. 195 * Use these to deduce the presence of spans of identical lines. 196 */ 197 back_limit = 0; 198 back_ref_limit = 0; 199 200 i = 0; 201 while (i < screen_lines && OLDNUM(i) == _NEWINDEX) 202 i++; 203 for ( ; i < screen_lines; i=next_hunk) 204 { 205 start = i; 206 shift = OLDNUM(i) - i; 207 208 /* get forward limit */ 209 i = start+1; 210 while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift) 211 i++; 212 end = i; 213 while (i < screen_lines && OLDNUM(i) == _NEWINDEX) 214 i++; 215 next_hunk = i; 216 forward_limit = i; 217 if (i >= screen_lines || OLDNUM(i) >= i) 218 forward_ref_limit = i; 219 else 220 forward_ref_limit = OLDNUM(i); 221 222 i = start-1; 223 /* grow back */ 224 if (shift < 0) 225 back_limit = back_ref_limit + (-shift); 226 while (i >= back_limit) 227 { 228 if(newhash[i] == oldhash[i+shift] 229 || cost_effective(i+shift, i, shift<0)) 230 { 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 } 236 else 237 { 238 TR(TRACE_UPDATE | TRACE_MOVE, 239 ("not connecting new line %d to old line %d (backward continuation)", 240 i, i+shift)); 241 break; 242 } 243 i--; 244 } 245 246 i = end; 247 /* grow forward */ 248 if (shift > 0) 249 forward_limit = forward_ref_limit - shift; 250 while (i < forward_limit) 251 { 252 if(newhash[i] == oldhash[i+shift] 253 || cost_effective(i+shift, i, shift>0)) 254 { 255 OLDNUM(i) = i+shift; 256 TR(TRACE_UPDATE | TRACE_MOVE, 257 ("connected new line %d to old line %d (forward continuation)", 258 i, i+shift)); 259 } 260 else 261 { 262 TR(TRACE_UPDATE | TRACE_MOVE, 263 ("not connecting new line %d to old line %d (forward continuation)", 264 i, i+shift)); 265 break; 266 } 267 i++; 268 } 269 270 back_ref_limit = back_limit = i; 271 if (shift > 0) 272 back_ref_limit += shift; 273 } 274 } 275 276 void _nc_hash_map(void) 277 { 278 sym *sp; 279 register int i; 280 int start, shift, size; 281 282 283 if (screen_lines > lines_alloc) 284 { 285 if (hashtab) 286 free (hashtab); 287 hashtab = typeMalloc(sym, (screen_lines+1)*2); 288 if (!hashtab) 289 { 290 if (oldhash) 291 FreeAndNull(oldhash); 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 */ 570