ncurses 5.9 - patch 20140823
[ncurses.git] / ncurses / tty / hashmap.c
index a2c368769f87d8392c599764ca16c177ee80a6cf..9282276110aa3155748996e6134b97008a24f061 100644 (file)
@@ -1,5 +1,5 @@
 /****************************************************************************
- * Copyright (c) 1998-2006,2007 Free Software Foundation, Inc.                   *
+ * Copyright (c) 1998-2011,2014 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 <curses.priv.h>
-#include <term.h>              /* for back_color_erase */
 
-MODULE_ID("$Id: hashmap.c,v 1.51 2007/04/28 20:14:15 tom Exp $")
+#ifndef CUR
+#define CUR SP_TERMTYPE
+#endif
+
+MODULE_ID("$Id: hashmap.c,v 1.64 2014/04/26 18:48:44 juergen Exp $")
 
 #ifdef HASHDEBUG
 
@@ -81,28 +84,27 @@ MODULE_ID("$Id: hashmap.c,v 1.51 2007/04/28 20:14:15 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
-
-extern NCURSES_EXPORT_VAR(unsigned)     _nc_tracing;
+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)     SP->_oldnum_list[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])
@@ -113,34 +115,34 @@ extern NCURSES_EXPORT_VAR(unsigned)     _nc_tracing;
 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);
+       result += (result << 5) + (unsigned long) HASH_VAL(ch);
     }
     return result;
 }
 
 /* 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;
@@ -149,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;
@@ -161,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 int 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;
 
@@ -176,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 */
@@ -201,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));
@@ -247,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));
@@ -269,51 +273,54 @@ 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,
+                                     ((size_t) 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,
+                                           (size_t) screen_lines(SP_PARM));
+       if (newhash(SP_PARM) == 0)
+           newhash(SP_PARM) = typeCalloc(unsigned long,
+                                           (size_t) 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
@@ -321,28 +328,30 @@ _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];
-
-       for (sp = hashtab; sp->hashval; sp++)
-           if (sp->hashval == hashval)
+    memset(hashtab(SP_PARM), '\0',
+          sizeof(*(hashtab(SP_PARM)))
+          * ((size_t) screen_lines(SP_PARM) + 1) * 2);
+    for (i = 0; i < screen_lines(SP_PARM); i++) {
+       unsigned long hashval = oldhash(SP_PARM)[i];
+
+       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 */
     }
 
     /*
@@ -352,16 +361,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
@@ -369,58 +378,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))) * (size_t) (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)
@@ -448,14 +482,17 @@ 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)))
+    if (NC_ISATTY(fileno(stdin)))
        usage();
 
 #ifdef TRACE
@@ -464,7 +501,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 */
@@ -486,22 +523,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 */
@@ -510,12 +547,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;
@@ -529,12 +566,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 */