X-Git-Url: https://ncurses.scripts.mit.edu/?p=ncurses.git;a=blobdiff_plain;f=ncurses%2Ftty%2Fhashmap.c;h=9b60df62d5cfbd1941f38c933cd4da544c35e65e;hp=f6a58bc6e112390578e3ad12ef9287e4748baaa1;hb=1c2ec25b8186b7973aeb06ec4da6b63656e12f7d;hpb=0eb88fc5281804773e2a0c7a488a4452463535ce diff --git a/ncurses/tty/hashmap.c b/ncurses/tty/hashmap.c index f6a58bc6..9b60df62 100644 --- a/ncurses/tty/hashmap.c +++ b/ncurses/tty/hashmap.c @@ -1,5 +1,5 @@ /**************************************************************************** - * Copyright (c) 1998 Free Software Foundation, Inc. * + * Copyright (c) 1998-2006,2007 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,9 @@ AUTHOR *****************************************************************************/ #include -#include /* for back_color_erase */ +#include /* for back_color_erase */ -MODULE_ID("$Id: hashmap.c,v 1.33 1999/03/18 02:09:45 Alexander.V.Lukyanov Exp $") +MODULE_ID("$Id: hashmap.c,v 1.56 2007/10/13 18:47:25 Miroslav.Lichvar Exp $") #ifdef HASHDEBUG @@ -81,7 +81,8 @@ MODULE_ID("$Id: hashmap.c,v 1.33 1999/03/18 02:09:45 Alexander.V.Lukyanov Exp $" # define screen_lines MAXLINES # define TEXTWIDTH 1 int oldnums[MAXLINES], reallines[MAXLINES]; -static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH]; +static NCURSES_CH_T oldtext[MAXLINES][TEXTWIDTH]; +static NCURSES_CH_T newtext[MAXLINES][TEXTWIDTH]; # define OLDNUM(n) oldnums[n] # define OLDTEXT(n) oldtext[n] # define NEWTEXT(m) newtext[m] @@ -89,7 +90,7 @@ static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH]; #else /* !HASHDEBUG */ -# define OLDNUM(n) _nc_oldnums[n] +# define OLDNUM(n) SP->_oldnum_list[n] # define OLDTEXT(n) curscr->_line[n].text # define NEWTEXT(m) newscr->_line[m].text # define TEXTWIDTH (curscr->_maxx+1) @@ -97,45 +98,58 @@ static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH]; #endif /* !HASHDEBUG */ -#define oldhash (SP->oldhash) -#define newhash (SP->newhash) +#define oldhash (SP->oldhash) +#define newhash (SP->newhash) +#define hashtab (SP->hashtab) +#define lines_alloc (SP->hashtab_len) -static inline unsigned long hash(chtype *text) +#if USE_WIDEC_SUPPORT +#define HASH_VAL(ch) (ch.chars[0]) +#else +#define HASH_VAL(ch) (ch) +#endif + +static const NCURSES_CH_T blankchar = NewChar(BLANK_TEXT); + +static NCURSES_INLINE unsigned long +hash(NCURSES_CH_T * text) { int i; - chtype ch; + NCURSES_CH_T ch; unsigned long result = 0; - for (i = TEXTWIDTH; i>0; i--) - { + for (i = TEXTWIDTH; i > 0; i--) { ch = *text++; - result += (result<<5) + ch; + result += (result << 5) + HASH_VAL(ch); } return result; } /* approximate update cost */ -static int update_cost(chtype *from,chtype *to) +static int +update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to) { - int cost=0; + int cost = 0; int i; - for (i=TEXTWIDTH; i>0; i--) - if (*from++ != *to++) + for (i = TEXTWIDTH; i > 0; i--, from++, to++) + if (!(CharEq(*from, *to))) cost++; return cost; } -static int update_cost_from_blank(chtype *to) + +static int +update_cost_from_blank(NCURSES_CH_T * to) { - int cost=0; + int cost = 0; int i; - chtype blank = BLANK; + NCURSES_CH_T blank = blankchar; if (back_color_erase) - blank |= (stdscr->_bkgd & A_COLOR); + SetPair(blank, GetPair(stdscr->_nc_bkgd)); - for (i=TEXTWIDTH; i>0; i--) - if (blank != *to++) + for (i = TEXTWIDTH; i > 0; i--, to++) + if (!(CharEq(blank, *to))) cost++; return cost; @@ -145,7 +159,8 @@ static int update_cost_from_blank(chtype *to) * Returns true when moving line 'from' to line 'to' seems to be cost * effective. 'blank' indicates whether the line 'to' would become blank. */ -static inline bool cost_effective(const int from, const int to, const bool blank) +static NCURSES_INLINE bool +cost_effective(const int from, const int to, const bool blank) { int new_from; @@ -161,30 +176,19 @@ static inline bool cost_effective(const int from, const int to, const bool blank * 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; + : 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; } - -typedef struct -{ - unsigned long hashval; - int oldcount, newcount; - int oldindex, newindex; -} - sym; - -static sym *hashtab=0; -static int lines_alloc=0; - -static void grow_hunks(void) +static void +grow_hunks(void) { int start, end, shift; - int back_limit, forward_limit; /* limits for cells to fill */ - int back_ref_limit, forward_ref_limit; /* limits for refrences */ + int back_limit, forward_limit; /* limits for cells to fill */ + int back_ref_limit, forward_ref_limit; /* limits for refrences */ int i; int next_hunk; @@ -198,14 +202,14 @@ static void grow_hunks(void) i = 0; while (i < screen_lines && OLDNUM(i) == _NEWINDEX) i++; - for ( ; i < screen_lines; i=next_hunk) - { + for (; i < screen_lines; i = next_hunk) { start = i; shift = OLDNUM(i) - i; /* get forward limit */ - i = start+1; - while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift) + i = start + 1; + while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i + == shift) i++; end = i; while (i < screen_lines && OLDNUM(i) == _NEWINDEX) @@ -217,25 +221,21 @@ static void grow_hunks(void) else forward_ref_limit = OLDNUM(i); - i = start-1; + 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; + while (i >= back_limit) { + if (newhash[i] == oldhash[i + shift] + || cost_effective(i + shift, i, shift < 0)) { + OLDNUM(i) = i + shift; TR(TRACE_UPDATE | TRACE_MOVE, ("connected new line %d to old line %d (backward continuation)", - i, i+shift)); - } - else - { + i, i + shift)); + } else { TR(TRACE_UPDATE | TRACE_MOVE, ("not connecting new line %d to old line %d (backward continuation)", - i, i+shift)); + i, i + shift)); break; } i--; @@ -245,21 +245,17 @@ static void grow_hunks(void) /* grow forward */ 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; + while (i < forward_limit) { + if (newhash[i] == oldhash[i + shift] + || cost_effective(i + shift, i, shift > 0)) { + OLDNUM(i) = i + shift; TR(TRACE_UPDATE | TRACE_MOVE, ("connected new line %d to old line %d (forward continuation)", - i, i+shift)); - } - else - { + i, i + shift)); + } else { TR(TRACE_UPDATE | TRACE_MOVE, ("not connecting new line %d to old line %d (forward continuation)", - i, i+shift)); + i, i + shift)); break; } i++; @@ -271,69 +267,61 @@ static void grow_hunks(void) } } -void _nc_hash_map(void) +NCURSES_EXPORT(void) +_nc_hash_map(void) { - sym *sp; + HASHMAP *sp; register int i; int start, shift, size; - - if (screen_lines > lines_alloc) - { + if (screen_lines > lines_alloc) { if (hashtab) - free (hashtab); - hashtab = typeMalloc(sym, (screen_lines+1)*2); - if (!hashtab) - { - if (oldhash) + free(hashtab); + hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2); + if (!hashtab) { + if (oldhash) { FreeAndNull(oldhash); + } lines_alloc = 0; return; } lines_alloc = screen_lines; } - if (oldhash && newhash) - { + if (oldhash && newhash) { /* re-hash only changed lines */ - for (i = 0; i < screen_lines; i++) - { + for (i = 0; i < screen_lines; i++) { if (PENDING(i)) newhash[i] = hash(NEWTEXT(i)); } - } - else - { + } else { /* re-hash all */ if (oldhash == 0) - oldhash = typeCalloc (unsigned long, screen_lines); + oldhash = typeCalloc(unsigned long, (unsigned) screen_lines); if (newhash == 0) - newhash = typeCalloc (unsigned long, screen_lines); + newhash = typeCalloc(unsigned long, (unsigned) screen_lines); if (!oldhash || !newhash) - return; /* malloc failure */ - for (i = 0; i < screen_lines; i++) - { + return; /* malloc failure */ + for (i = 0; i < screen_lines; i++) { newhash[i] = hash(NEWTEXT(i)); oldhash[i] = hash(OLDTEXT(i)); } } #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); + 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. */ - memset(hashtab, '\0', sizeof(*hashtab)*(screen_lines+1)*2); - for (i = 0; i < screen_lines; i++) - { + memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2); + for (i = 0; i < screen_lines; i++) { unsigned long hashval = oldhash[i]; for (sp = hashtab; sp->hashval; sp++) @@ -343,8 +331,7 @@ void _nc_hash_map(void) sp->oldcount++; sp->oldindex = i; } - for (i = 0; i < screen_lines; i++) - { + for (i = 0; i < screen_lines; i++) { unsigned long hashval = newhash[i]; for (sp = hashtab; sp->hashval; sp++) @@ -366,11 +353,10 @@ void _nc_hash_map(void) */ for (sp = hashtab; sp->hashval; sp++) if (sp->oldcount == 1 && sp->newcount == 1 - && sp->oldindex != sp->newindex) - { + && sp->oldindex != sp->newindex) { TR(TRACE_UPDATE | TRACE_MOVE, ("new line %d is hash-identical to old line %d (unique)", - sp->newindex, sp->oldindex)); + sp->newindex, sp->oldindex)); OLDNUM(sp->newindex) = sp->oldindex; } @@ -382,8 +368,7 @@ void _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; ) - { + for (i = 0; i < screen_lines;) { while (i < screen_lines && OLDNUM(i) == _NEWINDEX) i++; if (i >= screen_lines) @@ -391,13 +376,12 @@ void _nc_hash_map(void) start = i; shift = OLDNUM(i) - i; i++; - while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift) + while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i + == shift) i++; size = i - start; - if (size < 3 || size+min(size/8,2) < abs(shift)) - { - while (start < i) - { + if (size < 3 || size + min(size / 8, 2) < abs(shift)) { + while (start < i) { OLDNUM(start) = _NEWINDEX; start++; } @@ -406,48 +390,42 @@ void _nc_hash_map(void) /* After clearing invalid hunks, try grow the rest. */ grow_hunks(); - -#if NO_LEAKS - FreeAndNull(hashtab); - lines_alloc = 0; -#endif } -void _nc_make_oldhash(int i) +NCURSES_EXPORT(void) +_nc_make_oldhash(int i) { if (oldhash) oldhash[i] = hash(OLDTEXT(i)); } -void _nc_scroll_oldhash(int n, int top, int bot) +NCURSES_EXPORT(void) +_nc_scroll_oldhash(int n, int top, int bot) { - int size; + size_t 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--) + 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++) + } 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[] = { + static const char *table[] = + { "hashmap test-driver", "", "# comment", @@ -459,22 +437,24 @@ usage(void) "? this message" }; size_t n; - for (n = 0; n < sizeof(table)/sizeof(table[0]); 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) +main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) { - char line[BUFSIZ], *st; - int n; + char line[BUFSIZ], *st; + int n; - SP = typeCalloc(SCREEN,1); - for (n = 0; n < screen_lines; n++) - { + 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))) @@ -483,21 +463,18 @@ main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED) #ifdef TRACE _nc_tracing = TRACE_MOVE; #endif - for (;;) - { + for (;;) { /* grab a test command */ - if (fgets(line, sizeof(line), stdin) == (char *)NULL) - exit(EXIT_SUCCESS); + if (fgets(line, sizeof(line), stdin) == (char *) NULL) + break; - switch(line[0]) - { - case '#': /* comment */ + switch (line[0]) { + case '#': /* comment */ (void) fputs(line, stderr); break; - case 'l': /* get initial line number vector */ - for (n = 0; n < screen_lines; n++) - { + case 'l': /* get initial line number vector */ + for (n = 0; n < screen_lines; n++) { reallines[n] = n; oldnums[n] = _NEWINDEX; } @@ -506,46 +483,46 @@ main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED) do { oldnums[n++] = atoi(st); } while - ((st = strtok((char *)NULL, " ")) != 0); + ((st = strtok((char *) NULL, " ")) != 0); break; - case 'n': /* use following letters as text of new lines */ + 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') + 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 */ + 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') + 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 */ + case 'd': /* dump state of test arrays */ #ifdef TRACE _nc_linedump(); #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; - case 'h': /* apply hash mapper and see scroll optimization */ + case 'h': /* apply hash mapper and see scroll optimization */ _nc_hash_map(); (void) fputs("Result:\n", stderr); #ifdef TRACE @@ -554,12 +531,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 */