X-Git-Url: https://ncurses.scripts.mit.edu/?p=ncurses.git;a=blobdiff_plain;f=ncurses%2Ftty%2Fhashmap.c;fp=ncurses%2Fhashmap.c;h=f6a58bc6e112390578e3ad12ef9287e4748baaa1;hp=7a929f89d7afce0473fb1520ac16e06ce56b3d78;hb=0eb88fc5281804773e2a0c7a488a4452463535ce;hpb=661078ddbde3ce0f3b06e95642fbb9b5fef7dca1 diff --git a/ncurses/hashmap.c b/ncurses/tty/hashmap.c similarity index 78% rename from ncurses/hashmap.c rename to ncurses/tty/hashmap.c index 7a929f89..f6a58bc6 100644 --- a/ncurses/hashmap.c +++ b/ncurses/tty/hashmap.c @@ -63,34 +63,42 @@ hashmap: hashmap.c AUTHOR Eric S. Raymond , May 1996 + Bug fixes and improvements by Alexander V. Lukyanov , 1997 *****************************************************************************/ #include +#include /* for back_color_erase */ -MODULE_ID("$Id: hashmap.c,v 1.24 1998/02/11 12:13:55 tom Exp $") +MODULE_ID("$Id: hashmap.c,v 1.33 1999/03/18 02:09:45 Alexander.V.Lukyanov Exp $") #ifdef HASHDEBUG -#define TEXTWIDTH 1 + +# define _tracef printf +# undef TR +# define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); } +# undef screen_lines +# define screen_lines MAXLINES +# define TEXTWIDTH 1 int oldnums[MAXLINES], reallines[MAXLINES]; static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH]; -#define OLDNUM(n) oldnums[n] -#define REAL(m) reallines[m] -#define OLDTEXT(n) oldtext[n] -#define NEWTEXT(m) newtext[m] -#undef T -#define T(x) (void) printf x ; (void) putchar('\n'); -#else -#include -#define OLDNUM(n) newscr->_line[n].oldindex -#define REAL(m) curscr->_line[m].oldindex -#define OLDTEXT(n) curscr->_line[n].text -#define NEWTEXT(m) newscr->_line[m].text -#define TEXTWIDTH (curscr->_maxx+1) -#ifndef _NEWINDEX -#define _NEWINDEX -1 -#endif /* _NEWINDEX */ -#endif /* HASHDEBUG */ +# define OLDNUM(n) oldnums[n] +# define OLDTEXT(n) oldtext[n] +# define NEWTEXT(m) newtext[m] +# define PENDING(n) 1 + +#else /* !HASHDEBUG */ + +# define OLDNUM(n) _nc_oldnums[n] +# define OLDTEXT(n) curscr->_line[n].text +# define NEWTEXT(m) newscr->_line[m].text +# define TEXTWIDTH (curscr->_maxx+1) +# define PENDING(n) (newscr->_line[n].firstchar != _NOCHANGE) + +#endif /* !HASHDEBUG */ + +#define oldhash (SP->oldhash) +#define newhash (SP->newhash) static inline unsigned long hash(chtype *text) { @@ -100,7 +108,7 @@ static inline unsigned long hash(chtype *text) for (i = TEXTWIDTH; i>0; i--) { ch = *text++; - result += (result<<5) + ch + (ch>>16); + result += (result<<5) + ch; } return result; } @@ -112,7 +120,7 @@ static int update_cost(chtype *from,chtype *to) int i; for (i=TEXTWIDTH; i>0; i--) - if (*from++ != *to++) + if (*from++ != *to++) cost++; return cost; @@ -121,10 +129,13 @@ static int update_cost_from_blank(chtype *to) { int cost=0; int i; + chtype blank = BLANK; + + if (back_color_erase) + blank |= (stdscr->_bkgd & A_COLOR); - /* FIXME: ClrBlank should be used */ for (i=TEXTWIDTH; i>0; i--) - if (BLANK != *to++) + if (blank != *to++) cost++; return cost; @@ -145,7 +156,7 @@ static inline bool cost_effective(const int from, const int to, const bool blank if (new_from == _NEWINDEX) new_from = from; - /* + /* * On the left side of >= is the cost before moving; * on the right side -- cost after moving. */ @@ -167,9 +178,7 @@ typedef struct sym; static sym *hashtab=0; -static int lines_alloc=0; -static long *oldhash=0; -static long *newhash=0; +static int lines_alloc=0; static void grow_hunks(void) { @@ -193,7 +202,7 @@ static void grow_hunks(void) { start = i; shift = OLDNUM(i) - i; - + /* get forward limit */ i = start+1; while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift) @@ -231,7 +240,7 @@ static void grow_hunks(void) } i--; } - + i = end; /* grow forward */ if (shift > 0) @@ -255,7 +264,7 @@ static void grow_hunks(void) } i++; } - + back_ref_limit = back_limit = i; if (shift > 0) back_ref_limit += shift; @@ -273,7 +282,7 @@ void _nc_hash_map(void) { if (hashtab) free (hashtab); - hashtab = malloc (sizeof(*hashtab)*(screen_lines+1)*2); + hashtab = typeMalloc(sym, (screen_lines+1)*2); if (!hashtab) { if (oldhash) @@ -281,21 +290,43 @@ void _nc_hash_map(void) lines_alloc = 0; return; } - - if (oldhash) - free (oldhash); - oldhash = malloc (sizeof(*oldhash)*screen_lines*2); - if (!oldhash) + lines_alloc = screen_lines; + } + + if (oldhash && newhash) + { + /* re-hash only changed lines */ + for (i = 0; i < screen_lines; i++) + { + if (PENDING(i)) + newhash[i] = hash(NEWTEXT(i)); + } + } + else + { + /* re-hash all */ + if (oldhash == 0) + oldhash = typeCalloc (unsigned long, screen_lines); + if (newhash == 0) + newhash = typeCalloc (unsigned long, screen_lines); + if (!oldhash || !newhash) + return; /* malloc failure */ + for (i = 0; i < screen_lines; i++) { - if (hashtab) - FreeAndNull(hashtab); - lines_alloc = 0; - return; + newhash[i] = hash(NEWTEXT(i)); + oldhash[i] = hash(OLDTEXT(i)); } - - lines_alloc = screen_lines; } - newhash = oldhash + screen_lines; /* two arrays in the same memory block */ + +#ifdef HASH_VERIFY + for (i = 0; i < screen_lines; i++) + { + if(newhash[i] != hash(NEWTEXT(i))) + fprintf(stderr,"error in newhash[%d]\n",i); + if(oldhash[i] != hash(OLDTEXT(i))) + fprintf(stderr,"error in oldhash[%d]\n",i); + } +#endif /* * Set up and count line-hash values. @@ -303,34 +334,32 @@ void _nc_hash_map(void) memset(hashtab, '\0', sizeof(*hashtab)*(screen_lines+1)*2); for (i = 0; i < screen_lines; i++) { - unsigned long hashval = hash(OLDTEXT(i)); + unsigned long hashval = oldhash[i]; for (sp = hashtab; sp->hashval; sp++) if (sp->hashval == hashval) break; sp->hashval = hashval; /* in case this is a new entry */ - oldhash[i] = hashval; sp->oldcount++; sp->oldindex = i; } for (i = 0; i < screen_lines; i++) { - unsigned long hashval = hash(NEWTEXT(i)); + unsigned long hashval = newhash[i]; for (sp = hashtab; sp->hashval; sp++) if (sp->hashval == hashval) break; sp->hashval = hashval; /* in case this is a new entry */ - newhash[i] = hashval; sp->newcount++; sp->newindex = i; - - OLDNUM(i) = _NEWINDEX; + + OLDNUM(i) = _NEWINDEX; /* initialize old indices array */ } /* * Mark line pairs corresponding to unique hash pairs. - * + * * We don't mark lines with offset 0, because it can make fail * extending hunks by cost_effective. Otherwise, it does not * have any side effects. @@ -365,7 +394,7 @@ void _nc_hash_map(void) while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift) i++; size = i - start; - if (size <= abs(shift)) + if (size < 3 || size+min(size/8,2) < abs(shift)) { while (start < i) { @@ -374,18 +403,65 @@ void _nc_hash_map(void) } } } - + /* After clearing invalid hunks, try grow the rest. */ grow_hunks(); #if NO_LEAKS FreeAndNull(hashtab); - FreeAndNull(oldhash); lines_alloc = 0; #endif } +void _nc_make_oldhash(int i) +{ + if (oldhash) + oldhash[i] = hash(OLDTEXT(i)); +} + +void _nc_scroll_oldhash(int n, int top, int bot) +{ + int size; + int i; + + if (!oldhash) + return; + + size = sizeof(*oldhash) * (bot-top+1-abs(n)); + if (n > 0) + { + memmove (oldhash+top, oldhash+top+n, size); + for (i = bot; i > bot-n; i--) + oldhash[i] = hash(OLDTEXT(i)); + } + else + { + memmove (oldhash+top-n, oldhash+top, size); + for (i = top; i < top-n; i++) + oldhash[i] = hash(OLDTEXT(i)); + } +} + + #ifdef HASHDEBUG +static void +usage(void) +{ + static const char *table[] = { + "hashmap test-driver", + "", + "# comment", + "l get initial line number vector", + "n use following letters as text of new lines", + "o use following letters as text of old lines", + "d dump state of test arrays", + "h apply hash mapper and see scroll optimization", + "? this message" + }; + size_t n; + for (n = 0; n < sizeof(table)/sizeof(table[0]); n++) + fprintf(stderr, "%s\n", table[n]); +} int main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED) @@ -393,6 +469,7 @@ main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED) char line[BUFSIZ], *st; int n; + SP = typeCalloc(SCREEN,1); for (n = 0; n < screen_lines; n++) { reallines[n] = n; @@ -400,6 +477,9 @@ main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED) oldtext[n][0] = newtext[n][0] = '.'; } + if (isatty(fileno(stdin))) + usage(); + #ifdef TRACE _nc_tracing = TRACE_MOVE; #endif @@ -474,6 +554,9 @@ main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED) _nc_scroll_optimize(); (void) fputs("Done.\n", stderr); break; + case '?': + usage(); + break; } } return EXIT_SUCCESS;