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