Back to index

tetex-bin  3.0
hashmap.c
Go to the documentation of this file.
00001 /****************************************************************************
00002  * Copyright (c) 1998-2001,2002 Free Software Foundation, Inc.                   *
00003  *                                                                          *
00004  * Permission is hereby granted, free of charge, to any person obtaining a  *
00005  * copy of this software and associated documentation files (the            *
00006  * "Software"), to deal in the Software without restriction, including      *
00007  * without limitation the rights to use, copy, modify, merge, publish,      *
00008  * distribute, distribute with modifications, sublicense, and/or sell       *
00009  * copies of the Software, and to permit persons to whom the Software is    *
00010  * furnished to do so, subject to the following conditions:                 *
00011  *                                                                          *
00012  * The above copyright notice and this permission notice shall be included  *
00013  * in all copies or substantial portions of the Software.                   *
00014  *                                                                          *
00015  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
00016  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
00017  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
00018  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
00019  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
00020  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
00021  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
00022  *                                                                          *
00023  * Except as contained in this notice, the name(s) of the above copyright   *
00024  * holders shall not be used in advertising or otherwise to promote the     *
00025  * sale, use or other dealings in this Software without prior written       *
00026  * authorization.                                                           *
00027  ****************************************************************************/
00028 
00029 /****************************************************************************
00030  *  Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995               *
00031  *     and: Eric S. Raymond <esr@snark.thyrsus.com>                         *
00032  ****************************************************************************/
00033 
00034 /******************************************************************************
00035 
00036 NAME
00037    hashmap.c -- fill in scramble vector based on text hashes
00038 
00039 SYNOPSIS
00040    void _nc_hash_map(void)
00041 
00042 DESCRIPTION:
00043    This code attempts to recognize pairs of old and new lines in the physical
00044 and virtual screens.  When a line pair is recognized, the old line index is
00045 placed in the oldindex member of the virtual screen line, to be used by the
00046 vertical-motion optimizer portion of the update logic (see hardscroll.c).
00047 
00048    Line pairs are recognized by applying a modified Heckel's algorithm,
00049 sped up by hashing.  If a line hash is unique in both screens, those
00050 lines must be a pair. Then if the lines just before or after the pair
00051 are the same or similar, they are a pair too.
00052 
00053    We don't worry about false pairs produced by hash collisions, on the
00054 assumption that such cases are rare and will only make the latter stages
00055 of update less efficient, not introduce errors.
00056 
00057 HOW TO TEST THIS:
00058 
00059 Use the following production:
00060 
00061 hashmap: hashmap.c
00062        $(CC) -g -DHASHDEBUG hashmap.c hardscroll.c ../objects/lib_trace.o -o hashmap
00063 
00064 AUTHOR
00065     Eric S. Raymond <esr@snark.thyrsus.com>, May 1996
00066     Bug fixes and improvements by Alexander V. Lukyanov <lav@yars.free.net>, 1997
00067 
00068 *****************************************************************************/
00069 
00070 #include <curses.priv.h>
00071 #include <term.h>           /* for back_color_erase */
00072 
00073 MODULE_ID("$Id: hashmap.c,v 1.46 2002/09/07 18:13:15 tom Exp $")
00074 
00075 #ifdef HASHDEBUG
00076 
00077 # define _tracef     printf
00078 # undef TR
00079 # define TR(n, a)    if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
00080 # undef screen_lines
00081 # define screen_lines MAXLINES
00082 # define TEXTWIDTH   1
00083 int oldnums[MAXLINES], reallines[MAXLINES];
00084 static chtype oldtext[MAXLINES][TEXTWIDTH], newtext[MAXLINES][TEXTWIDTH];
00085 # define OLDNUM(n)   oldnums[n]
00086 # define OLDTEXT(n)  oldtext[n]
00087 # define NEWTEXT(m)  newtext[m]
00088 # define PENDING(n)     1
00089 
00090 #else /* !HASHDEBUG */
00091 
00092 # define OLDNUM(n)   _nc_oldnums[n]
00093 # define OLDTEXT(n)  curscr->_line[n].text
00094 # define NEWTEXT(m)  newscr->_line[m].text
00095 # define TEXTWIDTH   (curscr->_maxx+1)
00096 # define PENDING(n)     (newscr->_line[n].firstchar != _NOCHANGE)
00097 
00098 #endif /* !HASHDEBUG */
00099 
00100 #define oldhash             (SP->oldhash)
00101 #define newhash             (SP->newhash)
00102 #define hashtab             (SP->hashtab)
00103 #define lines_alloc  (SP->hashtab_len)
00104 
00105 #if USE_WIDEC_SUPPORT
00106 #define HASH_VAL(ch) (ch.chars[0])
00107 #else
00108 #define HASH_VAL(ch) (ch)
00109 #endif
00110 
00111 static inline unsigned long
00112 hash(NCURSES_CH_T * text)
00113 {
00114     int i;
00115     NCURSES_CH_T ch;
00116     unsigned long result = 0;
00117     for (i = TEXTWIDTH; i > 0; i--) {
00118        ch = *text++;
00119        result += (result << 5) + HASH_VAL(ch);
00120     }
00121     return result;
00122 }
00123 
00124 /* approximate update cost */
00125 static int
00126 update_cost(NCURSES_CH_T * from, NCURSES_CH_T * to)
00127 {
00128     int cost = 0;
00129     int i;
00130 
00131     for (i = TEXTWIDTH; i > 0; i--)
00132        if (!(CharEq(*from++, *to++)))
00133            cost++;
00134 
00135     return cost;
00136 }
00137 
00138 static int
00139 update_cost_from_blank(NCURSES_CH_T * to)
00140 {
00141     int cost = 0;
00142     int i;
00143     NCURSES_CH_T blank = NewChar2(BLANK_TEXT, BLANK_ATTR);
00144 
00145     if (back_color_erase)
00146        AddAttr(blank, (AttrOf(stdscr->_nc_bkgd) & A_COLOR));
00147 
00148     for (i = TEXTWIDTH; i > 0; i--)
00149        if (!(CharEq(blank, *to++)))
00150            cost++;
00151 
00152     return cost;
00153 }
00154 
00155 /*
00156  * Returns true when moving line 'from' to line 'to' seems to be cost
00157  * effective. 'blank' indicates whether the line 'to' would become blank.
00158  */
00159 static inline bool
00160 cost_effective(const int from, const int to, const bool blank)
00161 {
00162     int new_from;
00163 
00164     if (from == to)
00165        return FALSE;
00166 
00167     new_from = OLDNUM(from);
00168     if (new_from == _NEWINDEX)
00169        new_from = from;
00170 
00171     /*
00172      * On the left side of >= is the cost before moving;
00173      * on the right side -- cost after moving.
00174      */
00175     return (((blank ? update_cost_from_blank(NEWTEXT(to))
00176              : update_cost(OLDTEXT(to), NEWTEXT(to)))
00177             + update_cost(OLDTEXT(new_from), NEWTEXT(from)))
00178            >= ((new_from == from ? update_cost_from_blank(NEWTEXT(from))
00179                : update_cost(OLDTEXT(new_from), NEWTEXT(from)))
00180               + update_cost(OLDTEXT(from), NEWTEXT(to)))) ? TRUE : FALSE;
00181 }
00182 
00183 static void
00184 grow_hunks(void)
00185 {
00186     int start, end, shift;
00187     int back_limit, forward_limit; /* limits for cells to fill */
00188     int back_ref_limit, forward_ref_limit;       /* limits for refrences */
00189     int i;
00190     int next_hunk;
00191 
00192     /*
00193      * This is tricky part.  We have unique pairs to use as anchors.
00194      * Use these to deduce the presence of spans of identical lines.
00195      */
00196     back_limit = 0;
00197     back_ref_limit = 0;
00198 
00199     i = 0;
00200     while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
00201        i++;
00202     for (; i < screen_lines; i = next_hunk) {
00203        start = i;
00204        shift = OLDNUM(i) - i;
00205 
00206        /* get forward limit */
00207        i = start + 1;
00208        while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
00209               == shift)
00210            i++;
00211        end = i;
00212        while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
00213            i++;
00214        next_hunk = i;
00215        forward_limit = i;
00216        if (i >= screen_lines || OLDNUM(i) >= i)
00217            forward_ref_limit = i;
00218        else
00219            forward_ref_limit = OLDNUM(i);
00220 
00221        i = start - 1;
00222        /* grow back */
00223        if (shift < 0)
00224            back_limit = back_ref_limit + (-shift);
00225        while (i >= back_limit) {
00226            if (newhash[i] == oldhash[i + shift]
00227               || cost_effective(i + shift, i, shift < 0)) {
00228               OLDNUM(i) = i + shift;
00229               TR(TRACE_UPDATE | TRACE_MOVE,
00230                  ("connected new line %d to old line %d (backward continuation)",
00231                   i, i + shift));
00232            } else {
00233               TR(TRACE_UPDATE | TRACE_MOVE,
00234                  ("not connecting new line %d to old line %d (backward continuation)",
00235                   i, i + shift));
00236               break;
00237            }
00238            i--;
00239        }
00240 
00241        i = end;
00242        /* grow forward */
00243        if (shift > 0)
00244            forward_limit = forward_ref_limit - shift;
00245        while (i < forward_limit) {
00246            if (newhash[i] == oldhash[i + shift]
00247               || cost_effective(i + shift, i, shift > 0)) {
00248               OLDNUM(i) = i + shift;
00249               TR(TRACE_UPDATE | TRACE_MOVE,
00250                  ("connected new line %d to old line %d (forward continuation)",
00251                   i, i + shift));
00252            } else {
00253               TR(TRACE_UPDATE | TRACE_MOVE,
00254                  ("not connecting new line %d to old line %d (forward continuation)",
00255                   i, i + shift));
00256               break;
00257            }
00258            i++;
00259        }
00260 
00261        back_ref_limit = back_limit = i;
00262        if (shift > 0)
00263            back_ref_limit += shift;
00264     }
00265 }
00266 
00267 NCURSES_EXPORT(void)
00268 _nc_hash_map(void)
00269 {
00270     HASHMAP *sp;
00271     register int i;
00272     int start, shift, size;
00273 
00274     if (screen_lines > lines_alloc) {
00275        if (hashtab)
00276            free(hashtab);
00277        hashtab = typeMalloc(HASHMAP, (screen_lines + 1) * 2);
00278        if (!hashtab) {
00279            if (oldhash) {
00280               FreeAndNull(oldhash);
00281            }
00282            lines_alloc = 0;
00283            return;
00284        }
00285        lines_alloc = screen_lines;
00286     }
00287 
00288     if (oldhash && newhash) {
00289        /* re-hash only changed lines */
00290        for (i = 0; i < screen_lines; i++) {
00291            if (PENDING(i))
00292               newhash[i] = hash(NEWTEXT(i));
00293        }
00294     } else {
00295        /* re-hash all */
00296        if (oldhash == 0)
00297            oldhash = typeCalloc(unsigned long, (unsigned) screen_lines);
00298        if (newhash == 0)
00299            newhash = typeCalloc(unsigned long, (unsigned) screen_lines);
00300        if (!oldhash || !newhash)
00301            return;          /* malloc failure */
00302        for (i = 0; i < screen_lines; i++) {
00303            newhash[i] = hash(NEWTEXT(i));
00304            oldhash[i] = hash(OLDTEXT(i));
00305        }
00306     }
00307 
00308 #ifdef HASH_VERIFY
00309     for (i = 0; i < screen_lines; i++) {
00310        if (newhash[i] != hash(NEWTEXT(i)))
00311            fprintf(stderr, "error in newhash[%d]\n", i);
00312        if (oldhash[i] != hash(OLDTEXT(i)))
00313            fprintf(stderr, "error in oldhash[%d]\n", i);
00314     }
00315 #endif
00316 
00317     /*
00318      * Set up and count line-hash values.
00319      */
00320     memset(hashtab, '\0', sizeof(*hashtab) * (screen_lines + 1) * 2);
00321     for (i = 0; i < screen_lines; i++) {
00322        unsigned long hashval = oldhash[i];
00323 
00324        for (sp = hashtab; sp->hashval; sp++)
00325            if (sp->hashval == hashval)
00326               break;
00327        sp->hashval = hashval;      /* in case this is a new entry */
00328        sp->oldcount++;
00329        sp->oldindex = i;
00330     }
00331     for (i = 0; i < screen_lines; i++) {
00332        unsigned long hashval = newhash[i];
00333 
00334        for (sp = hashtab; sp->hashval; sp++)
00335            if (sp->hashval == hashval)
00336               break;
00337        sp->hashval = hashval;      /* in case this is a new entry */
00338        sp->newcount++;
00339        sp->newindex = i;
00340 
00341        OLDNUM(i) = _NEWINDEX;      /* initialize old indices array */
00342     }
00343 
00344     /*
00345      * Mark line pairs corresponding to unique hash pairs.
00346      *
00347      * We don't mark lines with offset 0, because it can make fail
00348      * extending hunks by cost_effective. Otherwise, it does not
00349      * have any side effects.
00350      */
00351     for (sp = hashtab; sp->hashval; sp++)
00352        if (sp->oldcount == 1 && sp->newcount == 1
00353            && sp->oldindex != sp->newindex) {
00354            TR(TRACE_UPDATE | TRACE_MOVE,
00355               ("new line %d is hash-identical to old line %d (unique)",
00356               sp->newindex, sp->oldindex));
00357            OLDNUM(sp->newindex) = sp->oldindex;
00358        }
00359 
00360     grow_hunks();
00361 
00362     /*
00363      * Eliminate bad or impossible shifts -- this includes removing
00364      * those hunks which could not grow because of conflicts, as well
00365      * those which are to be moved too far, they are likely to destroy
00366      * more than carry.
00367      */
00368     for (i = 0; i < screen_lines;) {
00369        while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
00370            i++;
00371        if (i >= screen_lines)
00372            break;
00373        start = i;
00374        shift = OLDNUM(i) - i;
00375        i++;
00376        while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
00377               == shift)
00378            i++;
00379        size = i - start;
00380        if (size < 3 || size + min(size / 8, 2) < abs(shift)) {
00381            while (start < i) {
00382               OLDNUM(start) = _NEWINDEX;
00383               start++;
00384            }
00385        }
00386     }
00387 
00388     /* After clearing invalid hunks, try grow the rest. */
00389     grow_hunks();
00390 }
00391 
00392 NCURSES_EXPORT(void)
00393 _nc_make_oldhash(int i)
00394 {
00395     if (oldhash)
00396        oldhash[i] = hash(OLDTEXT(i));
00397 }
00398 
00399 NCURSES_EXPORT(void)
00400 _nc_scroll_oldhash(int n, int top, int bot)
00401 {
00402     size_t size;
00403     int i;
00404 
00405     if (!oldhash)
00406        return;
00407 
00408     size = sizeof(*oldhash) * (bot - top + 1 - abs(n));
00409     if (n > 0) {
00410        memmove(oldhash + top, oldhash + top + n, size);
00411        for (i = bot; i > bot - n; i--)
00412            oldhash[i] = hash(OLDTEXT(i));
00413     } else {
00414        memmove(oldhash + top - n, oldhash + top, size);
00415        for (i = top; i < top - n; i++)
00416            oldhash[i] = hash(OLDTEXT(i));
00417     }
00418 }
00419 
00420 #ifdef HASHDEBUG
00421 static void
00422 usage(void)
00423 {
00424     static const char *table[] =
00425     {
00426        "hashmap test-driver",
00427        "",
00428        "#  comment",
00429        "l  get initial line number vector",
00430        "n  use following letters as text of new lines",
00431        "o  use following letters as text of old lines",
00432        "d  dump state of test arrays",
00433        "h  apply hash mapper and see scroll optimization",
00434        "?  this message"
00435     };
00436     size_t n;
00437     for (n = 0; n < sizeof(table) / sizeof(table[0]); n++)
00438        fprintf(stderr, "%s\n", table[n]);
00439 }
00440 
00441 int
00442 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
00443 {
00444     char line[BUFSIZ], *st;
00445     int n;
00446 
00447     SP = typeCalloc(SCREEN, 1);
00448     for (n = 0; n < screen_lines; n++) {
00449        reallines[n] = n;
00450        oldnums[n] = _NEWINDEX;
00451        oldtext[n][0] = newtext[n][0] = '.';
00452     }
00453 
00454     if (isatty(fileno(stdin)))
00455        usage();
00456 
00457 #ifdef TRACE
00458     _nc_tracing = TRACE_MOVE;
00459 #endif
00460     for (;;) {
00461        /* grab a test command */
00462        if (fgets(line, sizeof(line), stdin) == (char *) NULL)
00463            exit(EXIT_SUCCESS);
00464 
00465        switch (line[0]) {
00466        case '#':            /* comment */
00467            (void) fputs(line, stderr);
00468            break;
00469 
00470        case 'l':            /* get initial line number vector */
00471            for (n = 0; n < screen_lines; n++) {
00472               reallines[n] = n;
00473               oldnums[n] = _NEWINDEX;
00474            }
00475            n = 0;
00476            st = strtok(line, " ");
00477            do {
00478               oldnums[n++] = atoi(st);
00479            } while
00480               ((st = strtok((char *) NULL, " ")) != 0);
00481            break;
00482 
00483        case 'n':            /* use following letters as text of new lines */
00484            for (n = 0; n < screen_lines; n++)
00485               newtext[n][0] = '.';
00486            for (n = 0; n < screen_lines; n++)
00487               if (line[n + 1] == '\n')
00488                   break;
00489               else
00490                   newtext[n][0] = line[n + 1];
00491            break;
00492 
00493        case 'o':            /* use following letters as text of old lines */
00494            for (n = 0; n < screen_lines; n++)
00495               oldtext[n][0] = '.';
00496            for (n = 0; n < screen_lines; n++)
00497               if (line[n + 1] == '\n')
00498                   break;
00499               else
00500                   oldtext[n][0] = line[n + 1];
00501            break;
00502 
00503        case 'd':            /* dump state of test arrays */
00504 #ifdef TRACE
00505            _nc_linedump();
00506 #endif
00507            (void) fputs("Old lines: [", stdout);
00508            for (n = 0; n < screen_lines; n++)
00509               putchar(oldtext[n][0]);
00510            putchar(']');
00511            putchar('\n');
00512            (void) fputs("New lines: [", stdout);
00513            for (n = 0; n < screen_lines; n++)
00514               putchar(newtext[n][0]);
00515            putchar(']');
00516            putchar('\n');
00517            break;
00518 
00519        case 'h':            /* apply hash mapper and see scroll optimization */
00520            _nc_hash_map();
00521            (void) fputs("Result:\n", stderr);
00522 #ifdef TRACE
00523            _nc_linedump();
00524 #endif
00525            _nc_scroll_optimize();
00526            (void) fputs("Done.\n", stderr);
00527            break;
00528        case '?':
00529            usage();
00530            break;
00531        }
00532     }
00533     return EXIT_SUCCESS;
00534 }
00535 
00536 #endif /* HASHDEBUG */
00537 
00538 /* hashmap.c ends here */