X-Git-Url: https://ncurses.scripts.mit.edu/?p=ncurses.git;a=blobdiff_plain;f=ncurses%2Ftty%2Fhashmap.c;h=8ed2c3b4c09b887ec0ad6960c2ef48aac0917350;hp=1f482d4b6d0b4f1701b6bf766be870926bf5c68b;hb=cf94c7485f7b40ff7870b5bf9a65e7ab87481a76;hpb=027ae42953e3186daed8f3882da73de48291b606 diff --git a/ncurses/tty/hashmap.c b/ncurses/tty/hashmap.c index 1f482d4b..8ed2c3b4 100644 --- a/ncurses/tty/hashmap.c +++ b/ncurses/tty/hashmap.c @@ -1,5 +1,5 @@ /**************************************************************************** - * Copyright (c) 1998-2005,2006 Free Software Foundation, Inc. * + * Copyright (c) 1998-2007,2009 Free Software Foundation, Inc. * * * * Permission is hereby granted, free of charge, to any person obtaining a * * copy of this software and associated documentation files (the * @@ -68,9 +68,12 @@ AUTHOR *****************************************************************************/ #include -#include /* for back_color_erase */ -MODULE_ID("$Id: hashmap.c,v 1.49 2006/03/11 19:33:49 tom Exp $") +#ifndef CUR +#define CUR SP_TERMTYPE +#endif + +MODULE_ID("$Id: hashmap.c,v 1.61 2009/11/07 16:07:55 tom Exp $") #ifdef HASHDEBUG @@ -81,26 +84,27 @@ MODULE_ID("$Id: hashmap.c,v 1.49 2006/03/11 19:33:49 tom Exp $") # 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 OLDTEXT(n) oldtext[n] -# define NEWTEXT(m) newtext[m] -# define PENDING(n) 1 +static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH]; +static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH]; +# define OLDNUM(sp,n) oldnums[n] +# define OLDTEXT(sp,n) oldtext[n] +# define NEWTEXT(sp,m) newtext[m] +# define PENDING(sp,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) +# define OLDNUM(sp,n) (sp)->_oldnum_list[n] +# define OLDTEXT(sp,n) CurScreen(sp)->_line[n].text +# define NEWTEXT(sp,m) NewScreen(sp)->_line[m].text +# define TEXTWIDTH(sp) (CurScreen(sp)->_maxx + 1) +# define PENDING(sp,n) (NewScreen(sp)->_line[n].firstchar != _NOCHANGE) #endif /* !HASHDEBUG */ -#define oldhash (SP->oldhash) -#define newhash (SP->newhash) -#define hashtab (SP->hashtab) -#define lines_alloc (SP->hashtab_len) +#define oldhash(sp) ((sp)->oldhash) +#define newhash(sp) ((sp)->newhash) +#define hashtab(sp) ((sp)->hashtab) +#define lines_alloc(sp) ((sp)->hashtab_len) #if USE_WIDEC_SUPPORT #define HASH_VAL(ch) (ch.chars[0]) @@ -111,12 +115,12 @@ static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH]; static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT); static NCURSES_INLINE unsigned long -hash(NCURSES_CH_T * text) +hash(SCREEN *sp, NCURSES_CH_T * text) { int i; NCURSES_CH_T ch; unsigned long result = 0; - for (i = TEXTWIDTH; i > 0; i--) { + for (i = TEXTWIDTH(sp); i > 0; i--) { ch = *text++; result += (result << 5) + HASH_VAL(ch); } @@ -125,20 +129,20 @@ hash(NCURSES_CH_T * text) /* approximate update cost */ static int -update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to) +update_cost(SCREEN *sp, NCURSES_CH_T * from, NCURSES_CH_T * to) { int cost = 0; int i; - for (i = TEXTWIDTH; i > 0; i--) - if (!(CharEq(*from++, *to++))) + for (i = TEXTWIDTH(sp); i > 0; i--, from++, to++) + if (!(CharEq(*from, *to))) cost++; return cost; } static int -update_cost_from_blank(NCURSES_CH_T * to) +update_cost_from_blank(SCREEN *sp, NCURSES_CH_T * to) { int cost = 0; int i; @@ -147,8 +151,8 @@ update_cost_from_blank(NCURSES_CH_T * to) if (back_color_erase) SetPair(blank, GetPair(stdscr->_nc_bkgd)); - for (i = TEXTWIDTH; i > 0; i--) - if (!(CharEq(blank, *to++))) + for (i = TEXTWIDTH(sp); i > 0; i--, to++) + if (!(CharEq(blank, *to))) cost++; return cost; @@ -159,14 +163,14 @@ update_cost_from_blank(NCURSES_CH_T * to) * effective. 'blank' indicates whether the line 'to' would become blank. */ static NCURSES_INLINE bool -cost_effective(const int from, const int to, const bool blank) +cost_effective(SCREEN *sp, const int from, const int to, const bool blank) { int new_from; if (from == to) return FALSE; - new_from = OLDNUM(from); + new_from = OLDNUM(sp, from); if (new_from == _NEWINDEX) new_from = from; @@ -174,16 +178,17 @@ cost_effective(const int from, const int to, const bool blank) * On the left side of >= is the cost before moving; * on the right side -- cost after moving. */ - return (((blank ? update_cost_from_blank(NEWTEXT(to)) - : update_cost(OLDTEXT(to), NEWTEXT(to))) - + update_cost(OLDTEXT(new_from), NEWTEXT(from))) - >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from)) - : update_cost(OLDTEXT(new_from), NEWTEXT(from))) - + update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE; + return (((blank ? update_cost_from_blank(sp, NEWTEXT(sp, to)) + : update_cost(sp, OLDTEXT(sp, to), NEWTEXT(sp, to))) + + update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from))) + >= ((new_from == from ? update_cost_from_blank(sp, NEWTEXT(sp, from)) + : update_cost(sp, OLDTEXT(sp, new_from), NEWTEXT(sp, from))) + + update_cost(sp, OLDTEXT(sp, from), NEWTEXT(sp, to)))) + ? TRUE : FALSE; } static void -grow_hunks(void) +grow_hunks(SCREEN *sp) { int start, end, shift; int back_limit, forward_limit; /* limits for cells to fill */ @@ -199,35 +204,36 @@ grow_hunks(void) back_ref_limit = 0; i = 0; - while (i < screen_lines && OLDNUM(i) == _NEWINDEX) + while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX) i++; - for (; i < screen_lines; i = next_hunk) { + for (; i < screen_lines(sp); i = next_hunk) { start = i; - shift = OLDNUM(i) - i; + shift = OLDNUM(sp, i) - i; /* get forward limit */ i = start + 1; - while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i - == shift) + while (i < screen_lines(sp) + && OLDNUM(sp, i) != _NEWINDEX + && OLDNUM(sp, i) - i == shift) i++; end = i; - while (i < screen_lines && OLDNUM(i) == _NEWINDEX) + while (i < screen_lines(sp) && OLDNUM(sp, i) == _NEWINDEX) i++; next_hunk = i; forward_limit = i; - if (i >= screen_lines || OLDNUM(i) >= i) + if (i >= screen_lines(sp) || OLDNUM(sp, i) >= i) forward_ref_limit = i; else - forward_ref_limit = OLDNUM(i); + forward_ref_limit = OLDNUM(sp, i); i = start - 1; /* grow back */ if (shift < 0) back_limit = back_ref_limit + (-shift); while (i >= back_limit) { - if (newhash[i] == oldhash[i + shift] - || cost_effective(i + shift, i, shift < 0)) { - OLDNUM(i) = i + shift; + if (newhash(sp)[i] == oldhash(sp)[i + shift] + || cost_effective(sp, i + shift, i, shift < 0)) { + OLDNUM(sp, i) = i + shift; TR(TRACE_UPDATE | TRACE_MOVE, ("connected new line %d to old line %d (backward continuation)", i, i + shift)); @@ -245,9 +251,9 @@ grow_hunks(void) if (shift > 0) forward_limit = forward_ref_limit - shift; while (i < forward_limit) { - if (newhash[i] == oldhash[i + shift] - || cost_effective(i + shift, i, shift > 0)) { - OLDNUM(i) = i + shift; + if (newhash(sp)[i] == oldhash(sp)[i + shift] + || cost_effective(sp, i + shift, i, shift > 0)) { + OLDNUM(sp, i) = i + shift; TR(TRACE_UPDATE | TRACE_MOVE, ("connected new line %d to old line %d (forward continuation)", i, i + shift)); @@ -267,51 +273,53 @@ grow_hunks(void) } NCURSES_EXPORT(void) -_nc_hash_map(void) +NCURSES_SP_NAME(_nc_hash_map) (NCURSES_SP_DCL0) { - HASHMAP *sp; + HASHMAP *hsp; register int i; int start, shift, size; - if (screen_lines > lines_alloc) { - if (hashtab) - free(hashtab); - hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2); - if (!hashtab) { - if (oldhash) { - FreeAndNull(oldhash); + if (screen_lines(SP_PARM) > lines_alloc(SP_PARM)) { + if (hashtab(SP_PARM)) + free(hashtab(SP_PARM)); + hashtab(SP_PARM) = typeMalloc(HASHMAP, (screen_lines(SP_PARM) + 1) * 2); + if (!hashtab(SP_PARM)) { + if (oldhash(SP_PARM)) { + FreeAndNull(oldhash(SP_PARM)); } - lines_alloc = 0; + lines_alloc(SP_PARM) = 0; return; } - lines_alloc = screen_lines; + lines_alloc(SP_PARM) = screen_lines(SP_PARM); } - if (oldhash && newhash) { + if (oldhash(SP_PARM) && newhash(SP_PARM)) { /* re-hash only changed lines */ - for (i = 0; i < screen_lines; i++) { - if (PENDING(i)) - newhash[i] = hash(NEWTEXT(i)); + for (i = 0; i < screen_lines(SP_PARM); i++) { + if (PENDING(SP_PARM, i)) + newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i)); } } else { /* re-hash all */ - if (oldhash == 0) - oldhash = typeCalloc(unsigned long, (unsigned) screen_lines); - if (newhash == 0) - newhash = typeCalloc(unsigned long, (unsigned) screen_lines); - if (!oldhash || !newhash) + if (oldhash(SP_PARM) == 0) + oldhash(SP_PARM) = typeCalloc(unsigned long, + (unsigned) screen_lines(SP_PARM)); + if (newhash(SP_PARM) == 0) + newhash(SP_PARM) = typeCalloc(unsigned long, + (unsigned) screen_lines(SP_PARM)); + if (!oldhash(SP_PARM) || !newhash(SP_PARM)) return; /* malloc failure */ - for (i = 0; i < screen_lines; i++) { - newhash[i] = hash(NEWTEXT(i)); - oldhash[i] = hash(OLDTEXT(i)); + for (i = 0; i < screen_lines(SP_PARM); i++) { + newhash(SP_PARM)[i] = hash(SP_PARM, NEWTEXT(SP_PARM, i)); + oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i)); } } #ifdef HASH_VERIFY - for (i = 0; i < screen_lines; i++) { - if (newhash[i] != hash(NEWTEXT(i))) + for (i = 0; i < screen_lines(SP_PARM); i++) { + if (newhash(SP_PARM)[i] != hash(SP_PARM, NEWTEXT(SP_PARM, i))) fprintf(stderr, "error in newhash[%d]\n", i); - if (oldhash[i] != hash(OLDTEXT(i))) + if (oldhash(SP_PARM)[i] != hash(SP_PARM, OLDTEXT(SP_PARM, i))) fprintf(stderr, "error in oldhash[%d]\n", i); } #endif @@ -319,28 +327,29 @@ _nc_hash_map(void) /* * Set up and count line-hash values. */ - memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2); - for (i = 0; i < screen_lines; i++) { - unsigned long hashval = oldhash[i]; + memset(hashtab(SP_PARM), '\0', + sizeof(*(hashtab(SP_PARM))) * (screen_lines(SP_PARM) + 1) * 2); + for (i = 0; i < screen_lines(SP_PARM); i++) { + unsigned long hashval = oldhash(SP_PARM)[i]; - for (sp = hashtab; sp->hashval; sp++) - if (sp->hashval == hashval) + for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++) + if (hsp->hashval == hashval) break; - sp->hashval = hashval; /* in case this is a new entry */ - sp->oldcount++; - sp->oldindex = i; + hsp->hashval = hashval; /* in case this is a new entry */ + hsp->oldcount++; + hsp->oldindex = i; } - for (i = 0; i < screen_lines; i++) { - unsigned long hashval = newhash[i]; + for (i = 0; i < screen_lines(SP_PARM); i++) { + unsigned long hashval = newhash(SP_PARM)[i]; - for (sp = hashtab; sp->hashval; sp++) - if (sp->hashval == hashval) + for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++) + if (hsp->hashval == hashval) break; - sp->hashval = hashval; /* in case this is a new entry */ - sp->newcount++; - sp->newindex = i; + hsp->hashval = hashval; /* in case this is a new entry */ + hsp->newcount++; + hsp->newindex = i; - OLDNUM(i) = _NEWINDEX; /* initialize old indices array */ + OLDNUM(SP_PARM, i) = _NEWINDEX; /* initialize old indices array */ } /* @@ -350,16 +359,16 @@ _nc_hash_map(void) * extending hunks by cost_effective. Otherwise, it does not * have any side effects. */ - for (sp = hashtab; sp->hashval; sp++) - if (sp->oldcount == 1 && sp->newcount == 1 - && sp->oldindex != sp->newindex) { + for (hsp = hashtab(SP_PARM); hsp->hashval; hsp++) + if (hsp->oldcount == 1 && hsp->newcount == 1 + && hsp->oldindex != hsp->newindex) { TR(TRACE_UPDATE | TRACE_MOVE, ("new line %d is hash-identical to old line %d (unique)", - sp->newindex, sp->oldindex)); - OLDNUM(sp->newindex) = sp->oldindex; + hsp->newindex, hsp->oldindex)); + OLDNUM(SP_PARM, hsp->newindex) = hsp->oldindex; } - grow_hunks(); + grow_hunks(SP_PARM); /* * Eliminate bad or impossible shifts -- this includes removing @@ -367,58 +376,83 @@ _nc_hash_map(void) * those which are to be moved too far, they are likely to destroy * more than carry. */ - for (i = 0; i < screen_lines;) { - while (i < screen_lines && OLDNUM(i) == _NEWINDEX) + for (i = 0; i < screen_lines(SP_PARM);) { + while (i < screen_lines(SP_PARM) && OLDNUM(SP_PARM, i) == _NEWINDEX) i++; - if (i >= screen_lines) + if (i >= screen_lines(SP_PARM)) break; start = i; - shift = OLDNUM(i) - i; + shift = OLDNUM(SP_PARM, i) - i; i++; - while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i - == shift) + while (i < screen_lines(SP_PARM) + && OLDNUM(SP_PARM, i) != _NEWINDEX + && OLDNUM(SP_PARM, i) - i == shift) i++; size = i - start; if (size < 3 || size + min(size / 8, 2) < abs(shift)) { while (start < i) { - OLDNUM(start) = _NEWINDEX; + OLDNUM(SP_PARM, start) = _NEWINDEX; start++; } } } /* After clearing invalid hunks, try grow the rest. */ - grow_hunks(); + grow_hunks(SP_PARM); +} + +#if NCURSES_SP_FUNCS +NCURSES_EXPORT(void) +_nc_hash_map(void) +{ + NCURSES_SP_NAME(_nc_hash_map) (CURRENT_SCREEN); +} +#endif + +NCURSES_EXPORT(void) +NCURSES_SP_NAME(_nc_make_oldhash) (NCURSES_SP_DCLx int i) +{ + if (oldhash(SP_PARM)) + oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i)); } +#if NCURSES_SP_FUNCS NCURSES_EXPORT(void) _nc_make_oldhash(int i) { - if (oldhash) - oldhash[i] = hash(OLDTEXT(i)); + NCURSES_SP_NAME(_nc_make_oldhash) (CURRENT_SCREEN, i); } +#endif NCURSES_EXPORT(void) -_nc_scroll_oldhash(int n, int top, int bot) +NCURSES_SP_NAME(_nc_scroll_oldhash) (NCURSES_SP_DCLx int n, int top, int bot) { size_t size; int i; - if (!oldhash) + if (!oldhash(SP_PARM)) return; - size = sizeof(*oldhash) * (bot - top + 1 - abs(n)); + size = sizeof(*(oldhash(SP_PARM))) * (bot - top + 1 - abs(n)); if (n > 0) { - memmove(oldhash + top, oldhash + top + n, size); + memmove(oldhash(SP_PARM) + top, oldhash(SP_PARM) + top + n, size); for (i = bot; i > bot - n; i--) - oldhash[i] = hash(OLDTEXT(i)); + oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i)); } else { - memmove(oldhash + top - n, oldhash + top, size); + memmove(oldhash(SP_PARM) + top - n, oldhash(SP_PARM) + top, size); for (i = top; i < top - n; i++) - oldhash[i] = hash(OLDTEXT(i)); + oldhash(SP_PARM)[i] = hash(SP_PARM, OLDTEXT(SP_PARM, i)); } } +#if NCURSES_SP_FUNCS +NCURSES_EXPORT(void) +_nc_scroll_oldhash(int n, int top, int bot) +{ + NCURSES_SP_NAME(_nc_scroll_oldhash) (CURRENT_SCREEN, n, top, bot); +} +#endif + #ifdef HASHDEBUG static void usage(void) @@ -446,11 +480,14 @@ main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) char line[BUFSIZ], *st; int n; - SP = typeCalloc(SCREEN, 1); + if (setupterm(NULL, fileno(stdout), (int *) 0) == ERR) + return EXIT_FAILURE; + (void) _nc_alloc_screen(); + for (n = 0; n < screen_lines; n++) { reallines[n] = n; oldnums[n] = _NEWINDEX; - oldtext[n][0] = newtext[n][0] = '.'; + CharOf(oldtext[n][0]) = CharOf(newtext[n][0]) = '.'; } if (isatty(fileno(stdin))) @@ -462,7 +499,7 @@ main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) for (;;) { /* grab a test command */ if (fgets(line, sizeof(line), stdin) == (char *) NULL) - exit(EXIT_SUCCESS); + break; switch (line[0]) { case '#': /* comment */ @@ -484,22 +521,22 @@ main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) case 'n': /* use following letters as text of new lines */ for (n = 0; n < screen_lines; n++) - newtext[n][0] = '.'; + CharOf(newtext[n][0]) = '.'; for (n = 0; n < screen_lines; n++) if (line[n + 1] == '\n') break; else - newtext[n][0] = line[n + 1]; + CharOf(newtext[n][0]) = line[n + 1]; break; case 'o': /* use following letters as text of old lines */ for (n = 0; n < screen_lines; n++) - oldtext[n][0] = '.'; + CharOf(oldtext[n][0]) = '.'; for (n = 0; n < screen_lines; n++) if (line[n + 1] == '\n') break; else - oldtext[n][0] = line[n + 1]; + CharOf(oldtext[n][0]) = line[n + 1]; break; case 'd': /* dump state of test arrays */ @@ -508,12 +545,12 @@ main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) #endif (void) fputs("Old lines: [", stdout); for (n = 0; n < screen_lines; n++) - putchar(oldtext[n][0]); + putchar(CharOf(oldtext[n][0])); putchar(']'); putchar('\n'); (void) fputs("New lines: [", stdout); for (n = 0; n < screen_lines; n++) - putchar(newtext[n][0]); + putchar(CharOf(newtext[n][0])); putchar(']'); putchar('\n'); break; @@ -527,12 +564,17 @@ main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) _nc_scroll_optimize(); (void) fputs("Done.\n", stderr); break; + default: case '?': usage(); break; } } +#if NO_LEAKS + _nc_free_and_exit(EXIT_SUCCESS); +#else return EXIT_SUCCESS; +#endif } #endif /* HASHDEBUG */