Back to index

tetex-bin  3.0
Defines | Functions
hashmap.c File Reference
#include <curses.priv.h>
#include <term.h>

Go to the source code of this file.

Defines

#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 oldhash   (SP->oldhash)
#define newhash   (SP->newhash)
#define hashtab   (SP->hashtab)
#define lines_alloc   (SP->hashtab_len)
#define HASH_VAL(ch)   (ch)

Functions

static unsigned long hash (NCURSES_CH_T *text)
static int update_cost (NCURSES_CH_T *from, NCURSES_CH_T *to)
static int update_cost_from_blank (NCURSES_CH_T *to)
static bool cost_effective (const int from, const int to, const bool blank)
static void grow_hunks (void)
 _nc_hash_map (void)
 _nc_make_oldhash (int i)
 _nc_scroll_oldhash (int n, int top, int bot)

Define Documentation

#define HASH_VAL (   ch)    (ch)

Definition at line 108 of file hashmap.c.

#define hashtab   (SP->hashtab)

Definition at line 102 of file hashmap.c.

#define lines_alloc   (SP->hashtab_len)

Definition at line 103 of file hashmap.c.

#define newhash   (SP->newhash)

Definition at line 101 of file hashmap.c.

#define NEWTEXT (   m)    newscr->_line[m].text

Definition at line 94 of file hashmap.c.

#define oldhash   (SP->oldhash)

Definition at line 100 of file hashmap.c.

#define OLDNUM (   n)    _nc_oldnums[n]

Definition at line 92 of file hashmap.c.

#define OLDTEXT (   n)    curscr->_line[n].text

Definition at line 93 of file hashmap.c.

#define PENDING (   n)    (newscr->_line[n].firstchar != _NOCHANGE)

Definition at line 96 of file hashmap.c.

#define TEXTWIDTH   (curscr->_maxx+1)

Definition at line 95 of file hashmap.c.


Function Documentation

Definition at line 268 of file hashmap.c.

{
    HASHMAP *sp;
    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);
           }
           lines_alloc = 0;
           return;
       }
       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, (unsigned) screen_lines);
       if (newhash == 0)
           newhash = typeCalloc(unsigned long, (unsigned) screen_lines);
       if (!oldhash || !newhash)
           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);
    }
#endif

    /*
     * 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];

       for (sp = hashtab; sp->hashval; sp++)
           if (sp->hashval == hashval)
              break;
       sp->hashval = hashval;      /* in case this is a new entry */
       sp->oldcount++;
       sp->oldindex = i;
    }
    for (i = 0; i < screen_lines; 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 */
       sp->newcount++;
       sp->newindex = i;

       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.
     */
    for (sp = hashtab; sp->hashval; sp++)
       if (sp->oldcount == 1 && sp->newcount == 1
           && sp->oldindex != sp->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;
       }

    grow_hunks();

    /*
     * Eliminate bad or impossible shifts -- this includes removing
     * those hunks which could not grow because of conflicts, as well
     * 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)
           i++;
       if (i >= screen_lines)
           break;
       start = i;
       shift = OLDNUM(i) - i;
       i++;
       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) {
              OLDNUM(start) = _NEWINDEX;
              start++;
           }
       }
    }

    /* After clearing invalid hunks, try grow the rest. */
    grow_hunks();
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 393 of file hashmap.c.

{
    if (oldhash)
       oldhash[i] = hash(OLDTEXT(i));
}

Here is the caller graph for this function:

_nc_scroll_oldhash ( int  n,
int  top,
int  bot 
)

Definition at line 400 of file hashmap.c.

{
    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--)
           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));
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static bool cost_effective ( const int  from,
const int  to,
const bool  blank 
) [inline, static]

Definition at line 160 of file hashmap.c.

{
    int new_from;

    if (from == to)
       return FALSE;

    new_from = OLDNUM(from);
    if (new_from == _NEWINDEX)
       new_from = from;

    /*
     * 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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void grow_hunks ( void  ) [static]

Definition at line 184 of file hashmap.c.

{
    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 i;
    int next_hunk;

    /*
     * This is tricky part.  We have unique pairs to use as anchors.
     * Use these to deduce the presence of spans of identical lines.
     */
    back_limit = 0;
    back_ref_limit = 0;

    i = 0;
    while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
       i++;
    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++;
       end = i;
       while (i < screen_lines && OLDNUM(i) == _NEWINDEX)
           i++;
       next_hunk = i;
       forward_limit = i;
       if (i >= screen_lines || OLDNUM(i) >= i)
           forward_ref_limit = i;
       else
           forward_ref_limit = OLDNUM(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;
              TR(TRACE_UPDATE | TRACE_MOVE,
                 ("connected new line %d to old line %d (backward continuation)",
                  i, i + shift));
           } else {
              TR(TRACE_UPDATE | TRACE_MOVE,
                 ("not connecting new line %d to old line %d (backward continuation)",
                  i, i + shift));
              break;
           }
           i--;
       }

       i = end;
       /* 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;
              TR(TRACE_UPDATE | TRACE_MOVE,
                 ("connected new line %d to old line %d (forward continuation)",
                  i, i + shift));
           } else {
              TR(TRACE_UPDATE | TRACE_MOVE,
                 ("not connecting new line %d to old line %d (forward continuation)",
                  i, i + shift));
              break;
           }
           i++;
       }

       back_ref_limit = back_limit = i;
       if (shift > 0)
           back_ref_limit += shift;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static unsigned long hash ( NCURSES_CH_T text) [inline, static]

Definition at line 112 of file hashmap.c.

{
    int i;
    NCURSES_CH_T ch;
    unsigned long result = 0;
    for (i = TEXTWIDTH; i > 0; i--) {
       ch = *text++;
       result += (result << 5) + HASH_VAL(ch);
    }
    return result;
}
static int update_cost ( NCURSES_CH_T from,
NCURSES_CH_T to 
) [static]

Definition at line 126 of file hashmap.c.

{
    int cost = 0;
    int i;

    for (i = TEXTWIDTH; i > 0; i--)
       if (!(CharEq(*from++, *to++)))
           cost++;

    return cost;
}

Here is the caller graph for this function:

static int update_cost_from_blank ( NCURSES_CH_T to) [static]

Definition at line 139 of file hashmap.c.

{
    int cost = 0;
    int i;
    NCURSES_CH_T blank = NewChar2(BLANK_TEXT, BLANK_ATTR);

    if (back_color_erase)
       AddAttr(blank, (AttrOf(stdscr->_nc_bkgd) & A_COLOR));

    for (i = TEXTWIDTH; i > 0; i--)
       if (!(CharEq(blank, *to++)))
           cost++;

    return cost;
}

Here is the caller graph for this function: