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