150276Speter/**************************************************************************** 2174993Srafan * Copyright (c) 1998-2006,2007 Free Software Foundation, Inc. * 350276Speter * * 450276Speter * Permission is hereby granted, free of charge, to any person obtaining a * 550276Speter * copy of this software and associated documentation files (the * 650276Speter * "Software"), to deal in the Software without restriction, including * 750276Speter * without limitation the rights to use, copy, modify, merge, publish, * 850276Speter * distribute, distribute with modifications, sublicense, and/or sell * 950276Speter * copies of the Software, and to permit persons to whom the Software is * 1050276Speter * furnished to do so, subject to the following conditions: * 1150276Speter * * 1250276Speter * The above copyright notice and this permission notice shall be included * 1350276Speter * in all copies or substantial portions of the Software. * 1450276Speter * * 1550276Speter * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 1650276Speter * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 1750276Speter * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 1850276Speter * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 1950276Speter * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 2050276Speter * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 2150276Speter * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 2250276Speter * * 2350276Speter * Except as contained in this notice, the name(s) of the above copyright * 2450276Speter * holders shall not be used in advertising or otherwise to promote the * 2550276Speter * sale, use or other dealings in this Software without prior written * 2650276Speter * authorization. * 2750276Speter ****************************************************************************/ 2850276Speter 2950276Speter/**************************************************************************** 3050276Speter * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 * 3150276Speter * and: Eric S. Raymond <esr@snark.thyrsus.com> * 3250276Speter ****************************************************************************/ 3350276Speter 3450276Speter/****************************************************************************** 3550276Speter 3650276SpeterNAME 3750276Speter hashmap.c -- fill in scramble vector based on text hashes 3850276Speter 3950276SpeterSYNOPSIS 4050276Speter void _nc_hash_map(void) 4150276Speter 4250276SpeterDESCRIPTION: 4350276Speter This code attempts to recognize pairs of old and new lines in the physical 4450276Speterand virtual screens. When a line pair is recognized, the old line index is 4550276Speterplaced in the oldindex member of the virtual screen line, to be used by the 4650276Spetervertical-motion optimizer portion of the update logic (see hardscroll.c). 4750276Speter 4850276Speter Line pairs are recognized by applying a modified Heckel's algorithm, 4950276Spetersped up by hashing. If a line hash is unique in both screens, those 5050276Speterlines must be a pair. Then if the lines just before or after the pair 5150276Speterare the same or similar, they are a pair too. 5250276Speter 5350276Speter We don't worry about false pairs produced by hash collisions, on the 5450276Speterassumption that such cases are rare and will only make the latter stages 5550276Speterof update less efficient, not introduce errors. 5650276Speter 5750276SpeterHOW TO TEST THIS: 5850276Speter 5950276SpeterUse the following production: 6050276Speter 6150276Speterhashmap: hashmap.c 6250276Speter $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap 6350276Speter 6450276SpeterAUTHOR 6550276Speter Eric S. Raymond <esr@snark.thyrsus.com>, May 1996 6650276Speter Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997 6750276Speter 6850276Speter*****************************************************************************/ 6950276Speter 7050276Speter#include <curses.priv.h> 7176726Speter#include <term.h> /* for back_color_erase */ 7250276Speter 73174993SrafanMODULE_ID("$Id: hashmap.c,v 1.56 2007/10/13 18:47:25 Miroslav.Lichvar Exp $") 7450276Speter 7550276Speter#ifdef HASHDEBUG 7650276Speter 7750276Speter# define _tracef printf 7850276Speter# undef TR 7950276Speter# define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); } 8050276Speter# undef screen_lines 8150276Speter# define screen_lines MAXLINES 8250276Speter# define TEXTWIDTH 1 8350276Speterint oldnums[MAXLINES], reallines[MAXLINES]; 84174993Srafanstatic NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH]; 85174993Srafanstatic NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH]; 8650276Speter# define OLDNUM(n) oldnums[n] 8750276Speter# define OLDTEXT(n) oldtext[n] 8850276Speter# define NEWTEXT(m) newtext[m] 8950276Speter# define PENDING(n) 1 9050276Speter 9150276Speter#else /* !HASHDEBUG */ 9250276Speter 93174993Srafan# define OLDNUM(n) SP->_oldnum_list[n] 9450276Speter# define OLDTEXT(n) curscr->_line[n].text 9550276Speter# define NEWTEXT(m) newscr->_line[m].text 9650276Speter# define TEXTWIDTH (curscr->_maxx+1) 9750276Speter# define PENDING(n) (newscr->_line[n].firstchar != _NOCHANGE) 9850276Speter 9950276Speter#endif /* !HASHDEBUG */ 10050276Speter 10197049Speter#define oldhash (SP->oldhash) 10297049Speter#define newhash (SP->newhash) 10397049Speter#define hashtab (SP->hashtab) 10497049Speter#define lines_alloc (SP->hashtab_len) 10550276Speter 10697049Speter#if USE_WIDEC_SUPPORT 10797049Speter#define HASH_VAL(ch) (ch.chars[0]) 10897049Speter#else 10997049Speter#define HASH_VAL(ch) (ch) 11097049Speter#endif 11197049Speter 112166124Srafanstatic const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT); 113166124Srafan 114166124Srafanstatic NCURSES_INLINE unsigned long 11597049Speterhash(NCURSES_CH_T * text) 11650276Speter{ 11750276Speter int i; 11897049Speter NCURSES_CH_T ch; 11950276Speter unsigned long result = 0; 12076726Speter for (i = TEXTWIDTH; i > 0; i--) { 12150276Speter ch = *text++; 12297049Speter result += (result << 5) + HASH_VAL(ch); 12350276Speter } 12450276Speter return result; 12550276Speter} 12650276Speter 12750276Speter/* approximate update cost */ 12876726Speterstatic int 12997049Speterupdate_cost(NCURSES_CH_T * from, NCURSES_CH_T * to) 13050276Speter{ 13176726Speter int cost = 0; 13250276Speter int i; 13350276Speter 134174993Srafan for (i = TEXTWIDTH; i > 0; i--, from++, to++) 135174993Srafan if (!(CharEq(*from, *to))) 13650276Speter cost++; 13750276Speter 13850276Speter return cost; 13950276Speter} 14097049Speter 14176726Speterstatic int 14297049Speterupdate_cost_from_blank(NCURSES_CH_T * to) 14350276Speter{ 14476726Speter int cost = 0; 14550276Speter int i; 146166124Srafan NCURSES_CH_T blank = blankchar; 14750276Speter 14850276Speter if (back_color_erase) 149166124Srafan SetPair(blank, GetPair(stdscr->_nc_bkgd)); 15050276Speter 151174993Srafan for (i = TEXTWIDTH; i > 0; i--, to++) 152174993Srafan if (!(CharEq(blank, *to))) 15350276Speter cost++; 15450276Speter 15550276Speter return cost; 15650276Speter} 15750276Speter 15850276Speter/* 15950276Speter * Returns true when moving line 'from' to line 'to' seems to be cost 16050276Speter * effective. 'blank' indicates whether the line 'to' would become blank. 16150276Speter */ 162166124Srafanstatic NCURSES_INLINE bool 16376726Spetercost_effective(const int from, const int to, const bool blank) 16450276Speter{ 16550276Speter int new_from; 16650276Speter 16750276Speter if (from == to) 16850276Speter return FALSE; 16950276Speter 17050276Speter new_from = OLDNUM(from); 17150276Speter if (new_from == _NEWINDEX) 17250276Speter new_from = from; 17350276Speter 17450276Speter /* 17550276Speter * On the left side of >= is the cost before moving; 17650276Speter * on the right side -- cost after moving. 17750276Speter */ 17850276Speter return (((blank ? update_cost_from_blank(NEWTEXT(to)) 17976726Speter : update_cost(OLDTEXT(to), NEWTEXT(to))) 18076726Speter + update_cost(OLDTEXT(new_from), NEWTEXT(from))) 18176726Speter >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from)) 18276726Speter : update_cost(OLDTEXT(new_from), NEWTEXT(from))) 18376726Speter + update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE; 18450276Speter} 18550276Speter 18676726Speterstatic void 18776726Spetergrow_hunks(void) 18850276Speter{ 18950276Speter int start, end, shift; 19076726Speter int back_limit, forward_limit; /* limits for cells to fill */ 19176726Speter int back_ref_limit, forward_ref_limit; /* limits for refrences */ 19250276Speter int i; 19350276Speter int next_hunk; 19450276Speter 19550276Speter /* 19650276Speter * This is tricky part. We have unique pairs to use as anchors. 19750276Speter * Use these to deduce the presence of spans of identical lines. 19850276Speter */ 19950276Speter back_limit = 0; 20050276Speter back_ref_limit = 0; 20150276Speter 20250276Speter i = 0; 20350276Speter while (i < screen_lines && OLDNUM(i) == _NEWINDEX) 20450276Speter i++; 20576726Speter for (; i < screen_lines; i = next_hunk) { 20650276Speter start = i; 20750276Speter shift = OLDNUM(i) - i; 20850276Speter 20950276Speter /* get forward limit */ 21076726Speter i = start + 1; 21176726Speter while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i 21276726Speter == shift) 21350276Speter i++; 21450276Speter end = i; 21550276Speter while (i < screen_lines && OLDNUM(i) == _NEWINDEX) 21650276Speter i++; 21750276Speter next_hunk = i; 21850276Speter forward_limit = i; 21950276Speter if (i >= screen_lines || OLDNUM(i) >= i) 22050276Speter forward_ref_limit = i; 22150276Speter else 22250276Speter forward_ref_limit = OLDNUM(i); 22350276Speter 22476726Speter i = start - 1; 22550276Speter /* grow back */ 22650276Speter if (shift < 0) 22750276Speter back_limit = back_ref_limit + (-shift); 22876726Speter while (i >= back_limit) { 22976726Speter if (newhash[i] == oldhash[i + shift] 23076726Speter || cost_effective(i + shift, i, shift < 0)) { 23176726Speter OLDNUM(i) = i + shift; 23250276Speter TR(TRACE_UPDATE | TRACE_MOVE, 23350276Speter ("connected new line %d to old line %d (backward continuation)", 23476726Speter i, i + shift)); 23576726Speter } else { 23650276Speter TR(TRACE_UPDATE | TRACE_MOVE, 23750276Speter ("not connecting new line %d to old line %d (backward continuation)", 23876726Speter i, i + shift)); 23950276Speter break; 24050276Speter } 24150276Speter i--; 24250276Speter } 24350276Speter 24450276Speter i = end; 24550276Speter /* grow forward */ 24650276Speter if (shift > 0) 24750276Speter forward_limit = forward_ref_limit - shift; 24876726Speter while (i < forward_limit) { 24976726Speter if (newhash[i] == oldhash[i + shift] 25076726Speter || cost_effective(i + shift, i, shift > 0)) { 25176726Speter OLDNUM(i) = i + shift; 25250276Speter TR(TRACE_UPDATE | TRACE_MOVE, 25350276Speter ("connected new line %d to old line %d (forward continuation)", 25476726Speter i, i + shift)); 25576726Speter } else { 25650276Speter TR(TRACE_UPDATE | TRACE_MOVE, 25750276Speter ("not connecting new line %d to old line %d (forward continuation)", 25876726Speter i, i + shift)); 25950276Speter break; 26050276Speter } 26150276Speter i++; 26250276Speter } 26350276Speter 26450276Speter back_ref_limit = back_limit = i; 26550276Speter if (shift > 0) 26650276Speter back_ref_limit += shift; 26750276Speter } 26850276Speter} 26950276Speter 27076726SpeterNCURSES_EXPORT(void) 27176726Speter_nc_hash_map(void) 27250276Speter{ 27397049Speter HASHMAP *sp; 27450276Speter register int i; 27550276Speter int start, shift, size; 27650276Speter 27776726Speter if (screen_lines > lines_alloc) { 27850276Speter if (hashtab) 27976726Speter free(hashtab); 28097049Speter hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2); 28176726Speter if (!hashtab) { 28276726Speter if (oldhash) { 28350276Speter FreeAndNull(oldhash); 28462449Speter } 28550276Speter lines_alloc = 0; 28650276Speter return; 28750276Speter } 28850276Speter lines_alloc = screen_lines; 28950276Speter } 29050276Speter 29176726Speter if (oldhash && newhash) { 29250276Speter /* re-hash only changed lines */ 29376726Speter for (i = 0; i < screen_lines; i++) { 29450276Speter if (PENDING(i)) 29550276Speter newhash[i] = hash(NEWTEXT(i)); 29650276Speter } 29776726Speter } else { 29850276Speter /* re-hash all */ 29950276Speter if (oldhash == 0) 300166124Srafan oldhash = typeCalloc(unsigned long, (unsigned) screen_lines); 30150276Speter if (newhash == 0) 302166124Srafan newhash = typeCalloc(unsigned long, (unsigned) screen_lines); 30350276Speter if (!oldhash || !newhash) 30476726Speter return; /* malloc failure */ 30576726Speter for (i = 0; i < screen_lines; i++) { 30650276Speter newhash[i] = hash(NEWTEXT(i)); 30750276Speter oldhash[i] = hash(OLDTEXT(i)); 30850276Speter } 30950276Speter } 31050276Speter 31150276Speter#ifdef HASH_VERIFY 31276726Speter for (i = 0; i < screen_lines; i++) { 31376726Speter if (newhash[i] != hash(NEWTEXT(i))) 31476726Speter fprintf(stderr, "error in newhash[%d]\n", i); 31576726Speter if (oldhash[i] != hash(OLDTEXT(i))) 31676726Speter fprintf(stderr, "error in oldhash[%d]\n", i); 31750276Speter } 31850276Speter#endif 31950276Speter 32050276Speter /* 32150276Speter * Set up and count line-hash values. 32250276Speter */ 32376726Speter memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2); 32476726Speter for (i = 0; i < screen_lines; i++) { 32550276Speter unsigned long hashval = oldhash[i]; 32650276Speter 32750276Speter for (sp = hashtab; sp->hashval; sp++) 32850276Speter if (sp->hashval == hashval) 32950276Speter break; 33050276Speter sp->hashval = hashval; /* in case this is a new entry */ 33150276Speter sp->oldcount++; 33250276Speter sp->oldindex = i; 33350276Speter } 33476726Speter for (i = 0; i < screen_lines; i++) { 33550276Speter unsigned long hashval = newhash[i]; 33650276Speter 33750276Speter for (sp = hashtab; sp->hashval; sp++) 33850276Speter if (sp->hashval == hashval) 33950276Speter break; 34050276Speter sp->hashval = hashval; /* in case this is a new entry */ 34150276Speter sp->newcount++; 34250276Speter sp->newindex = i; 34350276Speter 34450276Speter OLDNUM(i) = _NEWINDEX; /* initialize old indices array */ 34550276Speter } 34650276Speter 34750276Speter /* 34850276Speter * Mark line pairs corresponding to unique hash pairs. 34950276Speter * 35050276Speter * We don't mark lines with offset 0, because it can make fail 35150276Speter * extending hunks by cost_effective. Otherwise, it does not 35250276Speter * have any side effects. 35350276Speter */ 35450276Speter for (sp = hashtab; sp->hashval; sp++) 35550276Speter if (sp->oldcount == 1 && sp->newcount == 1 35676726Speter && sp->oldindex != sp->newindex) { 35750276Speter TR(TRACE_UPDATE | TRACE_MOVE, 35850276Speter ("new line %d is hash-identical to old line %d (unique)", 35976726Speter sp->newindex, sp->oldindex)); 36050276Speter OLDNUM(sp->newindex) = sp->oldindex; 36150276Speter } 36250276Speter 36350276Speter grow_hunks(); 36450276Speter 36550276Speter /* 36650276Speter * Eliminate bad or impossible shifts -- this includes removing 36750276Speter * those hunks which could not grow because of conflicts, as well 36850276Speter * those which are to be moved too far, they are likely to destroy 36950276Speter * more than carry. 37050276Speter */ 37176726Speter for (i = 0; i < screen_lines;) { 37250276Speter while (i < screen_lines && OLDNUM(i) == _NEWINDEX) 37350276Speter i++; 37450276Speter if (i >= screen_lines) 37550276Speter break; 37650276Speter start = i; 37750276Speter shift = OLDNUM(i) - i; 37850276Speter i++; 37976726Speter while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i 38076726Speter == shift) 38150276Speter i++; 38250276Speter size = i - start; 38376726Speter if (size < 3 || size + min(size / 8, 2) < abs(shift)) { 38476726Speter while (start < i) { 38550276Speter OLDNUM(start) = _NEWINDEX; 38650276Speter start++; 38750276Speter } 38850276Speter } 38950276Speter } 39050276Speter 39150276Speter /* After clearing invalid hunks, try grow the rest. */ 39250276Speter grow_hunks(); 39350276Speter} 39450276Speter 39576726SpeterNCURSES_EXPORT(void) 39676726Speter_nc_make_oldhash(int i) 39750276Speter{ 39850276Speter if (oldhash) 39950276Speter oldhash[i] = hash(OLDTEXT(i)); 40050276Speter} 40150276Speter 40276726SpeterNCURSES_EXPORT(void) 40376726Speter_nc_scroll_oldhash(int n, int top, int bot) 40450276Speter{ 40597049Speter size_t size; 40650276Speter int i; 40750276Speter 40850276Speter if (!oldhash) 40950276Speter return; 41050276Speter 41176726Speter size = sizeof(*oldhash) * (bot - top + 1 - abs(n)); 41276726Speter if (n > 0) { 41376726Speter memmove(oldhash + top, oldhash + top + n, size); 41476726Speter for (i = bot; i > bot - n; i--) 41550276Speter oldhash[i] = hash(OLDTEXT(i)); 41676726Speter } else { 41776726Speter memmove(oldhash + top - n, oldhash + top, size); 41876726Speter for (i = top; i < top - n; i++) 41950276Speter oldhash[i] = hash(OLDTEXT(i)); 42050276Speter } 42150276Speter} 42250276Speter 42350276Speter#ifdef HASHDEBUG 42450276Speterstatic void 42550276Speterusage(void) 42650276Speter{ 42776726Speter static const char *table[] = 42876726Speter { 42950276Speter "hashmap test-driver", 43050276Speter "", 43150276Speter "# comment", 43250276Speter "l get initial line number vector", 43350276Speter "n use following letters as text of new lines", 43450276Speter "o use following letters as text of old lines", 43550276Speter "d dump state of test arrays", 43650276Speter "h apply hash mapper and see scroll optimization", 43750276Speter "? this message" 43850276Speter }; 43950276Speter size_t n; 44076726Speter for (n = 0; n < sizeof(table) / sizeof(table[0]); n++) 44150276Speter fprintf(stderr, "%s\n", table[n]); 44250276Speter} 44350276Speter 44450276Speterint 44576726Spetermain(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) 44650276Speter{ 44776726Speter char line[BUFSIZ], *st; 44876726Speter int n; 44950276Speter 450174993Srafan if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR) 451174993Srafan return EXIT_FAILURE; 452174993Srafan (void) _nc_alloc_screen(); 453174993Srafan 45476726Speter for (n = 0; n < screen_lines; n++) { 45550276Speter reallines[n] = n; 45650276Speter oldnums[n] = _NEWINDEX; 457174993Srafan CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.'; 45850276Speter } 45950276Speter 46050276Speter if (isatty(fileno(stdin))) 46150276Speter usage(); 46250276Speter 46350276Speter#ifdef TRACE 46450276Speter _nc_tracing = TRACE_MOVE; 46550276Speter#endif 46676726Speter for (;;) { 46750276Speter /* grab a test command */ 46876726Speter if (fgets(line, sizeof(line), stdin) == (char *) NULL) 469174993Srafan break; 47050276Speter 47176726Speter switch (line[0]) { 47276726Speter case '#': /* comment */ 47350276Speter (void) fputs(line, stderr); 47450276Speter break; 47550276Speter 47676726Speter case 'l': /* get initial line number vector */ 47776726Speter for (n = 0; n < screen_lines; n++) { 47850276Speter reallines[n] = n; 47950276Speter oldnums[n] = _NEWINDEX; 48050276Speter } 48150276Speter n = 0; 48250276Speter st = strtok(line, " "); 48350276Speter do { 48450276Speter oldnums[n++] = atoi(st); 48550276Speter } while 48676726Speter ((st = strtok((char *) NULL, " ")) != 0); 48750276Speter break; 48850276Speter 48976726Speter case 'n': /* use following letters as text of new lines */ 49050276Speter for (n = 0; n < screen_lines; n++) 491174993Srafan CharOf(newtext[n][0]) = '.'; 49250276Speter for (n = 0; n < screen_lines; n++) 49376726Speter if (line[n + 1] == '\n') 49450276Speter break; 49550276Speter else 496174993Srafan CharOf(newtext[n][0]) = line[n + 1]; 49750276Speter break; 49850276Speter 49976726Speter case 'o': /* use following letters as text of old lines */ 50050276Speter for (n = 0; n < screen_lines; n++) 501174993Srafan CharOf(oldtext[n][0]) = '.'; 50250276Speter for (n = 0; n < screen_lines; n++) 50376726Speter if (line[n + 1] == '\n') 50450276Speter break; 50550276Speter else 506174993Srafan CharOf(oldtext[n][0]) = line[n + 1]; 50750276Speter break; 50850276Speter 50976726Speter case 'd': /* dump state of test arrays */ 51050276Speter#ifdef TRACE 51150276Speter _nc_linedump(); 51250276Speter#endif 51350276Speter (void) fputs("Old lines: [", stdout); 51450276Speter for (n = 0; n < screen_lines; n++) 515174993Srafan putchar(CharOf(oldtext[n][0])); 51650276Speter putchar(']'); 51750276Speter putchar('\n'); 51850276Speter (void) fputs("New lines: [", stdout); 51950276Speter for (n = 0; n < screen_lines; n++) 520174993Srafan putchar(CharOf(newtext[n][0])); 52150276Speter putchar(']'); 52250276Speter putchar('\n'); 52350276Speter break; 52450276Speter 52576726Speter case 'h': /* apply hash mapper and see scroll optimization */ 52650276Speter _nc_hash_map(); 52750276Speter (void) fputs("Result:\n", stderr); 52850276Speter#ifdef TRACE 52950276Speter _nc_linedump(); 53050276Speter#endif 53150276Speter _nc_scroll_optimize(); 53250276Speter (void) fputs("Done.\n", stderr); 53350276Speter break; 534174993Srafan default: 53550276Speter case '?': 53650276Speter usage(); 53750276Speter break; 53850276Speter } 53950276Speter } 540174993Srafan#if NO_LEAKS 541174993Srafan _nc_free_and_exit(EXIT_SUCCESS); 542174993Srafan#else 54350276Speter return EXIT_SUCCESS; 544174993Srafan#endif 54550276Speter} 54650276Speter 54750276Speter#endif /* HASHDEBUG */ 54850276Speter 54950276Speter/* hashmap.c ends here */ 550