Update to tcsh 6.18.01.

1 files changed, 1003 insertions, 142 deletions

diff --git a/contrib/tcsh/sh.hist.c b/contrib/tcsh/sh.hist.c
index 72b376a..6a12737 100644
--- a/contrib/tcsh/sh.hist.c
+++ b/contrib/tcsh/sh.hist.c
@@ -1,4 +1,4 @@
-/* $Header: /p/tcsh/cvsroot/tcsh/sh.hist.c,v 3.40 2007/03/01 17:14:51 christos Exp $ */
+/* $Header: /p/tcsh/cvsroot/tcsh/sh.hist.c,v 3.53 2011/01/24 18:10:26 christos Exp $ */
 /*
  * sh.hist.c: Shell history expansions and substitutions
  */
@@ -32,8 +32,9 @@
  */
 #include "sh.h"
 
-RCSID("$tcsh: sh.hist.c,v 3.40 2007/03/01 17:14:51 christos Exp $")
+RCSID("$tcsh: sh.hist.c,v 3.53 2011/01/24 18:10:26 christos Exp $")
 
+#include <assert.h>
 #include "tc.h"
 
 extern int histvalid;
@@ -42,8 +43,6 @@ Char HistLit = 0;
 
 static	int	heq	(const struct wordent *, const struct wordent *);
 static	void	hfree	(struct Hist *);
-static	void	dohist1	(struct Hist *, int *, int);
-static	void	phist	(struct Hist *, int);
 
 #define HIST_ONLY	0x01
 #define HIST_SAVE	0x02
@@ -57,10 +56,95 @@ static	void	phist	(struct Hist *, int);
  * C shell
  */
 
-void
-savehist(struct wordent *sp, int mflg)
+/* Static functions don't show up in gprof summaries.  So eliminate "static"
+ * modifier from some frequently called functions. */
+#ifdef PROF
+#define PG_STATIC
+#else
+#define PG_STATIC static
+#endif
+
+/* #define DEBUG_HIST 1 */
+
+static const int fastMergeErase = 1;
+static unsigned histCount = 0;		/* number elements on history list */
+static struct Hist *histTail = NULL;     /* last element on history list */
+static struct Hist *histMerg = NULL;	 /* last element merged by Htime */
+
+static void insertHistHashTable(struct Hist *, unsigned);
+
+
+/* Insert new element (hp) in history list after specified predecessor (pp). */
+static void
+hinsert(struct Hist *hp, struct Hist *pp)
+{
+    struct Hist *fp = pp->Hnext;        /* following element, if any */
+    hp->Hnext = fp, hp->Hprev = pp;
+    pp->Hnext = hp;
+    if (fp)
+        fp->Hprev = hp;
+    else
+        histTail = hp;                  /* meaning hp->Hnext == NULL */
+    histCount++;
+}
+
+/* Remove the entry from the history list. */
+static void
+hremove(struct Hist *hp)
+{
+    struct Hist *pp = hp->Hprev;
+    assert(pp);                         /* elements always have a previous */
+    pp->Hnext = hp->Hnext;
+    if (hp->Hnext)
+        hp->Hnext->Hprev = pp;
+    else
+        histTail = pp;                  /* we must have been last */
+    if (hp == histMerg)			/* deleting this hint from list */
+	histMerg = NULL;
+    assert(histCount > 0);
+    histCount--;
+}
+
+/* Prune length of history list to specified size by history variable. */
+PG_STATIC void
+discardExcess(int histlen)
 {
     struct Hist *hp, *np;
+    if (histTail == NULL) {
+        assert(histCount == 0);
+        return;                         /* no entries on history list */
+    }
+    /* Prune dummy entries from the front, then old entries from the back. If
+     * the list is still too long scan the whole list as before.  But only do a
+     * full scan if the list is more than 6% (1/16th) too long. */
+    while (histCount > (unsigned)histlen && (np = Histlist.Hnext)) {
+        if (eventno - np->Href >= histlen || histlen == 0)
+            hremove(np), hfree(np);
+        else
+            break;
+    }
+    while (histCount > (unsigned)histlen && (np = histTail) != &Histlist) {
+        if (eventno - np->Href >= histlen || histlen == 0)
+            hremove(np), hfree(np);
+        else
+            break;
+    }
+    if (histCount - (histlen >> 4) <= (unsigned)histlen)
+	return;				/* don't bother doing the full scan */
+    for (hp = &Histlist; histCount > (unsigned)histlen &&
+	(np = hp->Hnext) != NULL;)
+        if (eventno - np->Href >= histlen || histlen == 0)
+            hremove(np), hfree(np);
+        else
+            hp = np;
+}
+
+/* Add the command "sp" to the history list. */
+void
+savehist(
+  struct wordent *sp,
+  int mflg)				/* true if -m (merge) specified */
+{
     int histlen = 0;
     Char   *cp;
 
@@ -76,14 +160,445 @@ savehist(struct wordent *sp, int mflg)
 	histlen = histlen * 10 + *cp++ - '0';
     }
     if (sp)
-	(void) enthist(++eventno, sp, 1, mflg);
-    for (hp = &Histlist; (np = hp->Hnext) != NULL;)
-	if (eventno - np->Href >= histlen || histlen == 0)
-	    hp->Hnext = np->Hnext, hfree(np);
-	else
-	    hp = np;
+        (void) enthist(++eventno, sp, 1, mflg, histlen);
+    discardExcess(histlen);
+}
+
+#define USE_JENKINS_HASH 1
+/* #define USE_ONE_AT_A_TIME 1 */
+#undef PRIME_LENGTH			/* no need for good HTL */
+
+#ifdef USE_JENKINS_HASH
+#define hashFcnName "lookup3"
+/* From:
+   lookup3.c, by Bob Jenkins, May 2006, Public Domain.
+   "...  You can use this free for any purpose.  It's in
+    the public domain.  It has no warranty."
+   http://burtleburtle.net/bob/hash/index.html
+ */
+
+#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
+#define mix(a,b,c) \
+{ \
+  a -= c;  a ^= rot(c, 4);  c += b; \
+  b -= a;  b ^= rot(a, 6);  a += c; \
+  c -= b;  c ^= rot(b, 8);  b += a; \
+  a -= c;  a ^= rot(c,16);  c += b; \
+  b -= a;  b ^= rot(a,19);  a += c; \
+  c -= b;  c ^= rot(b, 4);  b += a; \
+}
+#define final(a,b,c) \
+{ \
+  c ^= b; c -= rot(b,14); \
+  a ^= c; a -= rot(c,11); \
+  b ^= a; b -= rot(a,25); \
+  c ^= b; c -= rot(b,16); \
+  a ^= c; a -= rot(c, 4); \
+  b ^= a; b -= rot(a,14); \
+  c ^= b; c -= rot(b,24); \
 }
 
+struct hashValue		  /* State used to hash a wordend word list. */
+{
+    uint32_t a, b, c;
+};
+
+/* Set up the internal state */
+static void
+initializeHash(struct hashValue *h)
+{
+    h->a = h->b = h->c = 0xdeadbeef;
+}
+
+/* This does a partial hash of the Chars in a single word.  For efficiency we
+ * include 3 versions of the code to pack Chars into 32-bit words for the
+ * mixing function. */
+static void
+addWordToHash(struct hashValue *h, const Char *word)
+{
+    uint32_t a = h->a, b = h->b, c = h->c;
+#ifdef SHORT_STRINGS
+#ifdef WIDE_STRINGS
+    assert(sizeof(Char) >= 4);
+    while (1) {
+	unsigned k;
+	if ((k = (uChar)*word++) == 0) break; a += k;
+	if ((k = (uChar)*word++) == 0) break; b += k;
+	if ((k = (uChar)*word++) == 0) break; c += k;
+	mix(a, b, c);
+    }
+#else
+    assert(sizeof(Char) == 2);
+    while (1) {
+	unsigned k;
+	if ((k = (uChar)*word++) == 0) break; a += k;
+	if ((k = (uChar)*word++) == 0) break; a += k << 16;
+	if ((k = (uChar)*word++) == 0) break; b += k;
+	if ((k = (uChar)*word++) == 0) break; b += k << 16;
+	if ((k = (uChar)*word++) == 0) break; c += k;
+	if ((k = (uChar)*word++) == 0) break; c += k << 16;
+	mix(a, b, c);
+    }
+#endif
+#else
+    assert(sizeof(Char) == 1);
+    while (1) {
+	unsigned k;
+	if ((k = *word++) == 0) break; a += k;
+	if ((k = *word++) == 0) break; a += k << 8;
+	if ((k = *word++) == 0) break; a += k << 16;
+	if ((k = *word++) == 0) break; a += k << 24;
+	if ((k = *word++) == 0) break; b += k;
+	if ((k = *word++) == 0) break; b += k << 8;
+	if ((k = *word++) == 0) break; b += k << 16;
+	if ((k = *word++) == 0) break; b += k << 24;
+	if ((k = *word++) == 0) break; c += k;
+	if ((k = *word++) == 0) break; c += k << 8;
+	if ((k = *word++) == 0) break; c += k << 16;
+	if ((k = *word++) == 0) break; c += k << 24;
+	mix(a, b, c);
+    }
+#endif
+    h->a = a, h->b = b, h->c = c;
+}
+
+static void
+addCharToHash(struct hashValue *h, Char ch)
+{
+    /* The compiler (gcc -O2) seems to do a good job optimizing this without
+     * explicitly extracting into local variables. */
+    h->a += (uChar)ch;
+    mix(h->a, h->b, h->c);
+}
+
+static uint32_t
+finalizeHash(struct hashValue *h)
+{
+    uint32_t a = h->a, b = h->b, c = h->c;
+    final(a, b, c);
+    return c;
+}
+
+#elif USE_ONE_AT_A_TIME
+#define hashFcnName "one-at-a-time"
+/* This one is also from Bob Jenkins, but is slower but simpler than lookup3.
+   "...  The code given here are all public domain."
+   http://burtleburtle.net/bob/hash/doobs.html */
+
+#if 0
+ub4
+one_at_a_time(char *key, ub4 len)
+{
+  ub4   hash, i;
+  for (hash=0, i=0; i<len; ++i)
+  {
+    hash += key[i];
+    hash += (hash << 10);
+    hash ^= (hash >> 6);
+  }
+  hash += (hash << 3);
+  hash ^= (hash >> 11);
+  hash += (hash << 15);
+  return (hash & mask);
+}
+#endif
+
+struct hashValue { uint32_t h; };
+static void
+initializeHash(struct hashValue *h)
+{
+    h->h = 0;
+}
+
+static void
+addWordToHash(struct hashValue *h, const Char *word)
+{
+    unsigned k;
+    uint32_t hash = h->h;
+    while (k = (uChar)*word++)
+	hash += k, hash += hash << 10, hash ^= hash >> 6;
+    h->h = hash;
+}
+
+static void
+addCharToHash(struct hashValue *h, Char c)
+{
+    Char b[2] = { c, 0 };
+    addWordToHash(h, b);
+}
+
+static uint32_t
+finalizeHash(struct hashValue *h)
+{
+    unsigned hash = h->h;
+    hash += (hash << 3);
+    hash ^= (hash >> 11);
+    hash += (hash << 15);
+    return hash;
+}
+
+#else
+#define hashFcnName "add-mul"
+/* Simple multipy and add hash. */
+#define PRIME_LENGTH 1			/* need "good" HTL */
+struct hashValue { uint32_t h; };
+static void
+initializeHash(struct hashValue *h)
+{
+    h->h = 0xe13e2345;
+}
+
+static void
+addWordToHash(struct hashValue *h, const Char *word)
+{
+    unsigned k;
+    uint32_t hash = h->h;
+    while (k = (uChar)*word++)
+	hash = hash * 0x9e4167b9 + k;
+    h->h = hash;
+}
+
+static void
+addCharToHash(struct hashValue *h, Char c)
+{
+    h->h = h->h * 0x9e4167b9 + (uChar)c;
+}
+
+static uint32_t
+finalizeHash(struct hashValue *h)
+{
+    return h->h;
+}
+#endif
+
+static unsigned
+hashhist(struct wordent *h0)
+{
+    struct hashValue s;
+    struct wordent *firstWord = h0->next;
+    struct wordent *h = firstWord;
+    unsigned hash = 0;
+
+    initializeHash(&s);
+    for (; h != h0; h = h->next) {
+        if (h->word[0] == '\n')
+            break;                      /* don't hash newline */
+        if (h != firstWord)
+            addCharToHash(&s, ' ');	/* space between words */
+	addWordToHash(&s, h->word);
+    }
+    hash = finalizeHash(&s);
+    /* Zero means no hash value, so never return zero as a hash value. */
+    return hash ? hash : 0x7fffffff;	/* prime! */
+}
+
+#if 0
+unsigned
+hashStr(Char *str)
+{
+    struct hashValue s;
+    initializeHash(&s);
+    addWordToHash(&s, str);
+    return finalizeHash(&s);
+}
+#endif
+
+#ifdef PRIME_LENGTH			/* need good HTL */
+#define hash2tableIndex(hash, len) ((hash) % len)
+#else
+#define hash2tableIndex(hash, len) ((hash) & (len-1))
+#endif
+
+/* This code can be enabled to test the above hash functions for speed and
+ * collision avoidance.  The testing is enabled by "occasional" calls to
+ * displayHistStats(), see which. */
+#ifdef DEBUG_HIST
+
+#ifdef BSDTIMES
+static double
+doTiming(int start) {
+    static struct timeval beginTime;
+    if (start) {
+	gettimeofday(&beginTime, NULL);
+	return 0.0;
+    } else {
+	struct timeval now;
+	gettimeofday(&now, NULL);
+	return (now.tv_sec-beginTime.tv_sec) +
+	    (now.tv_usec-beginTime.tv_usec)/1e6;
+    }
+}
+#else
+static double
+doTiming(int start) {
+    USE(start);
+    return 0.0;
+}
+#endif
+
+static void
+generateHashes(int nChars, unsigned nWords, unsigned samples, unsigned *hashes,
+    unsigned length)
+{
+    if (nChars < 1)
+	return;
+    nWords = (nWords < 1) ? 1 : (nWords > 4) ? 4 : nWords;
+    Char *number = xmalloc((nChars+nWords)*sizeof(Char));
+    struct wordent word[4];
+    struct wordent base = { NULL, &word[0], &word[0] };
+    word[0].word = number, word[0].next = &base, word[0].prev = &base;
+    unsigned w = 0;			/* word number */
+    /* Generate multiple words of length 2, 3, 5, then all the rest. */
+    unsigned wBoundaries[4] = { 2-1, 2+3-1, 2+3+5-1, 0 };
+    /* Ensure the last word has at least 4 Chars in it. */
+    while (nWords >= 2 && nChars < (wBoundaries[nWords-2]+1) + 4)
+	nWords--;
+    wBoundaries[nWords-1] = 0xffffffff;	/* don't end word past this point */
+    unsigned i;
+    for (i = 0; i<nChars; i++) {
+	/* In deference to the gawd awful add-mul hash, we won't use the worse
+	 * case here (setting all Chars to 1), but assume mostly (or at least
+	 * initially) ASCII data. */
+	number[i+w] = '!';		/* 0x21 = 33 */
+
+	if (i == wBoundaries[w]) {	/* end a word here and move to next */
+	    w++;			/* next word */
+	    number[i+w] = 0;		/* terminate */
+	    word[w].word = &number[i+w+1];
+	    word[w].next = &base, word[w].prev = &word[w-1];
+	    word[w-1].next = &word[w], base.prev = &word[w];
+	}
+    }
+    /* w is the index of the last word actually created. */
+    number[nChars + w] = 0;		/* terminate last word */
+    unsigned timeLimit = !samples;
+    if (samples == 0)
+	samples = 1000000000;
+    doTiming(1);
+    double sec;
+    for (i = 0; i < samples; i++) {
+	/* increment 4 digit base 255 number; last characters vary fastest */
+	unsigned j = nChars-1 + w;
+	while (1) {
+	    if (++number[j] != 0)
+		break;
+	    /* else reset this digit and proceed to next one */
+	    number[j] = 1;
+	    if (&number[j] <= word[w].word)
+		break;			/* stop at beginning of last word */
+	    j--;
+	}
+	if (word[w].word[0] == '\n')
+	    word[w].word[0]++;		/* suppress newline character */
+	unsigned hash = hashhist(&base);
+	hashes[hash2tableIndex(hash, length)]++;
+	if (timeLimit && (i & 0x3ffff) == 0x3ffff) {
+	    sec = doTiming(0);
+	    if (sec > 10)
+		break;
+	}
+    }
+    if (i >= samples)
+	sec = doTiming(0);
+    else
+	samples = i;			/* number we actually did */
+    if (sec > 0.01) {
+	xprintf("Hash %d (%d Char %u words) with %s: %d nsec/hash, %d mcps\n",
+		samples, nChars, w+1, hashFcnName, (int)((sec/samples)*1e9),
+		(int)((double)samples*nChars/sec/1e6));
+    }
+}
+#endif /* DEBUG_HIST */
+
+#ifdef DEBUG_HIST
+static void
+testHash(void)
+{
+    static const Char STRtestHashTimings[] =
+	{ 't','e','s','t','H','a','s','h','T','i','m','i','n','g','s', 0 };
+    struct varent *vp = adrof(STRtestHashTimings);
+    if (vp && vp->vec) {
+	unsigned hashes[4];		/* dummy place to put hashes */
+	Char **vals = vp->vec;
+	while (*vals) {
+	    int length = getn(*vals);
+	    unsigned words =
+		(length < 5) ? 1 : (length < 25) ? 2 : (length < 75) ? 3 : 4;
+	    if (length > 0)
+		generateHashes(length, words, 0, hashes, 4);
+	    vals++;
+	}
+    }
+    unsigned length = 1024;
+#ifdef PRIME_LENGTH			/* need good HTL */
+    length = 1021;
+#endif
+    unsigned *hashes = xmalloc(length*sizeof(unsigned));
+    memset(hashes, 0, length*sizeof(unsigned));
+    /* Compute collision statistics for half full hashes modulo "length". */
+    generateHashes(4, 1, length/2, hashes, length);
+    /* Evaluate collisions by comparing occupancy rates (mean value 0.5).
+     * One bin for each number of hits. */
+    unsigned bins[155];
+    memset(bins, 0, sizeof(bins));
+    unsigned highest = 0;
+    unsigned i;
+    for (i = 0; i<length; i++) {
+	unsigned hits = hashes[i];
+	if (hits >= sizeof(bins)/sizeof(bins[0])) /* clip */
+	    hits = highest = sizeof(bins)/sizeof(bins[0]) - 1;
+	if (hits > highest)
+	    highest = hits;
+	bins[hits]++;
+    }
+    xprintf("Occupancy of %d buckets by %d hashes %d Chars %d word with %s\n",
+	    length, length/2, 4, 1, hashFcnName);
+    for (i = 0; i <= highest; i++) {
+	xprintf(" %d buckets (%d%%) with %d hits\n",
+		bins[i], bins[i]*100/length, i);
+    }
+    /* Count run lengths to evaluate linear rehashing effectiveness.  Estimate
+     * a little corrupted by edge effects. */
+    memset(bins, 0, sizeof(bins));
+    highest = 0;
+    for (i = 0; hashes[i] == 0; i++);	/* find first occupied bucket */
+    unsigned run = 0;
+    unsigned rehashed = 0;
+    for (; i<length; i++) {
+	unsigned hits = hashes[i];
+	if (hits == 0 && rehashed > 0)
+	    hits = 1 && rehashed--;
+	else if (hits > 1)
+	    rehashed += hits-1;
+	if (hits)
+	    run++;
+	else {
+	    /* a real free slot, count it */
+	    if (run >= sizeof(bins)/sizeof(bins[0])) /* clip */
+		run = highest = sizeof(bins)/sizeof(bins[0]) - 1;
+	    if (run > highest)
+		highest = run;
+	    bins[run]++;
+	    run = 0;
+	}
+    }
+    /* Ignore the partial run at end as we ignored the beginning. */
+    double merit = 0.0, entries = 0;
+    for (i = 0; i <= highest; i++) {
+	entries += bins[i]*i;		/* total hashed objects */
+	merit += bins[i]*i*i;
+    }
+    xprintf("Rehash collision figure of merit %u (ideal=100), run lengths:\n",
+	    (int)(100.0*merit/entries));
+    for (i = 0; i <= highest; i++) {
+	if (bins[i] != 0)
+	    xprintf(" %d runs of length %d buckets\n", bins[i], i);
+    }
+    xfree(hashes);
+}
+#endif /* DEBUG_HIST */
+
+/* Compares two word lists for equality. */
 static int
 heq(const struct wordent *a0, const struct wordent *b0)
 {
@@ -98,40 +613,362 @@ heq(const struct wordent *a0, const struct wordent *b0)
 	    return (b == b0) ? 1 : 0;
 	if (b == b0)
 	    return 0;
-    } 
+    }
+}
+
+/* Renumber entries following p, which we will be deleting. */
+PG_STATIC void
+renumberHist(struct Hist *p)
+{
+    int n = p->Href;
+    while ((p = p->Hnext))
+        p->Href = n--;
+}
+
+/* The hash table is implemented as an array of pointers to Hist entries.  Each
+ * entry is located in the table using hash2tableIndex() and checking the
+ * following entries in case of a collision (linear rehash).  Free entries in
+ * the table are zero (0, NULL, emptyHTE).  Deleted entries that cannot yet be
+ * freed are set to one (deletedHTE).  The Hist.Hhash member is non-zero iff
+ * the entry is in the hash table.  When the hash table get too full, it is
+ * reallocated to be approximately twice the history length (see
+ * getHashTableSize). */
+static struct Hist **histHashTable = NULL;
+static unsigned histHashTableLength = 0; /* number of Hist pointers in table */
+
+static struct Hist * const emptyHTE = NULL;
+static struct Hist * const deletedHTE = (struct Hist *)1;
+
+static struct {
+    unsigned insertCount;
+    unsigned removeCount;
+    unsigned rehashes;
+    int deleted;
+} hashStats;
+
+#ifdef DEBUG_HIST
+void
+checkHistHashTable(int print)
+{
+    unsigned occupied = 0;
+    unsigned deleted = 0;
+    unsigned i;
+    for (i = 0; i<histHashTableLength; i++)
+	if (histHashTable[i] == emptyHTE)
+	    continue;
+	else if (histHashTable[i] == deletedHTE)
+	    deleted++;
+	else
+	    occupied++;
+    if (print)
+	xprintf("  found len %u occupied %u deleted %u\n",
+		histHashTableLength, occupied, deleted);
+    assert(deleted == hashStats.deleted);
+}
+
+static int doneTest = 0;
+
+/* Main entry point for displaying history statistics and hash function
+ * behavior. */
+void
+displayHistStats(const char *reason)
+{
+    /* Just hash statistics for now. */
+    xprintf("%s history hash table len %u count %u (deleted %d)\n", reason,
+	    histHashTableLength, histCount, hashStats.deleted);
+    xprintf("  inserts %u rehashes %u%% each\n",
+	    hashStats.insertCount,
+	    (hashStats.insertCount
+	     ? 100*hashStats.rehashes/hashStats.insertCount : 0));
+    xprintf("  removes %u net %u\n",
+	    hashStats.removeCount,
+	    hashStats.insertCount - hashStats.removeCount);
+    assert(hashStats.insertCount >= hashStats.removeCount);
+    checkHistHashTable(1);
+    memset(&hashStats, 0, sizeof(hashStats));
+    if (!doneTest) {
+	testHash();
+	doneTest = 1;
+    }
+}
+#else
+void
+displayHistStats(const char *reason)
+{
+    USE(reason);
+}
+#endif
+
+static void
+discardHistHashTable(void)
+{
+    if (histHashTable == NULL)
+        return;
+    displayHistStats("Discarding");
+    xfree(histHashTable);
+    histHashTable = NULL;
+}
+
+/* Computes a new hash table size, when the current one is too small. */
+static unsigned
+getHashTableSize(int histlen)
+{
+    unsigned target = histlen * 2;
+    unsigned e = 5;
+    unsigned size;
+    while ((size = 1<<e) < target)
+	e++;
+#ifdef PRIME_LENGTH			/* need good HTL */
+    /* Not all prime, but most are and none have factors smaller than 11. */
+    return size+15;
+#else
+    assert((size & (size-1)) == 0);	/* must be a power of two */
+    return size;
+#endif
+}
+
+/* Create the hash table or resize, if necessary. */
+static void
+createHistHashTable(int histlen)
+{
+    if (histlen == 0) {
+	discardHistHashTable();
+        return;
+    }
+    if (histlen < 0) {
+        histlen = getn(varval(STRhistory));
+	if (histlen == 0)
+	    return;			/* no need for hash table */
+	assert(histlen > 0);
+    }
+    if (histHashTable != NULL) {
+	if (histCount < histHashTableLength * 3 / 4)
+	    return;			/* good enough for now */
+	discardHistHashTable();		/* too small */
+    }
+    histHashTableLength = getHashTableSize(
+	histlen > (int)histCount ? histlen : (int)histCount);
+    histHashTable = xmalloc(histHashTableLength * sizeof(struct Hist *));
+    memset(histHashTable, 0, histHashTableLength * sizeof(struct Hist *));
+    assert(histHashTable[0] == emptyHTE);
+
+    /* Now insert all the entries on the history list into the hash table. */
+    {
+        struct Hist *hp;
+        for (hp = &Histlist; (hp = hp->Hnext) != NULL;) {
+            unsigned lpHash = hashhist(&hp->Hlex);
+            assert(!hp->Hhash || hp->Hhash == lpHash);
+            hp->Hhash = 0;              /* force insert to new hash table */
+            insertHistHashTable(hp, lpHash);
+        }
+    }
+}
+
+/* Insert np into the hash table.  We assume that np is already on the
+ * Histlist.  The specified hashval matches the new Hist entry but has not yet
+ * been assigned to Hhash (or the element is already on the hash table). */
+static void
+insertHistHashTable(struct Hist *np, unsigned hashval)
+{
+    unsigned rehashes = 0;
+    unsigned hi = 0;
+    if (!histHashTable)
+	return;
+    if (np->Hhash != 0) {
+        /* already in hash table */
+        assert(hashval == np->Hhash);
+        return;
+    }
+    assert(np != deletedHTE);
+    /* Find a free (empty or deleted) slot, using linear rehash. */
+    assert(histHashTable);
+    for (rehashes = 0;
+         ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)),
+          histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE);
+         rehashes++) {
+        assert(np != histHashTable[hi]);
+        if (rehashes >= histHashTableLength / 10) {
+            /* Hash table is full, so grow it.  We assume the create function
+             * will roughly double the size we give it.  Create initializes the
+             * new table with everything on the Histlist, so we are done when
+             * it returns.  */
+#ifdef DEBUG_HIST
+	    xprintf("Growing history hash table from %d ...",
+		histHashTableLength);
+	    flush();
+#endif
+            discardHistHashTable();
+            createHistHashTable(histHashTableLength);
+#ifdef DEBUG_HIST
+	    xprintf("to %d.\n", histHashTableLength);
+#endif
+            return;
+        }
+    }
+    /* Might be sensible to grow hash table if rehashes is "too big" here. */
+    if (histHashTable[hi] == deletedHTE)
+	hashStats.deleted--;
+    histHashTable[hi] = np;
+    np->Hhash = hashval;
+    hashStats.insertCount++;
+    hashStats.rehashes += rehashes;
+}
+
+/* Remove the 'np' entry from the hash table. */
+static void
+removeHistHashTable(struct Hist *np)
+{
+    unsigned hi = np->Hhash;
+    if (!histHashTable || !hi)
+        return;                         /* no hash table or not on it */
+    /* find desired entry */
+    while ((hi = hash2tableIndex(hi, histHashTableLength)),
+           histHashTable[hi] != emptyHTE) {
+        if (np == histHashTable[hi]) {
+	    unsigned i;
+	    unsigned deletes = 0;
+	    histHashTable[hi] = deletedHTE; /* dummy, but non-zero entry */
+	    /* now peek ahead to see if the dummies are really necessary. */
+	    i = 1;
+	    while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] ==
+		   deletedHTE)
+		i++;
+	    if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] ==
+		emptyHTE) {
+		/* dummies are no longer necessary placeholders. */
+		deletes = i;
+		while (i-- > 0) {
+		    histHashTable[hash2tableIndex(hi+i, histHashTableLength)] =
+			emptyHTE;
+		}
+	    }
+	    hashStats.deleted += 1 - deletes; /* delta deleted entries */
+	    hashStats.removeCount++;
+            return;
+        }
+        hi++;                           /* linear rehash */
+    }
+    assert(!"Hist entry not found in hash table");
 }
 
+/* Search the history hash table for a command matching lp, using hashval as
+ * its hash value. */
+static struct Hist *
+findHistHashTable(struct wordent *lp, unsigned hashval)
+{
+    unsigned deleted = 0;		/* number of deleted entries skipped */
+    unsigned hi = hashval;
+    struct Hist *hp;
+    if (!histHashTable)
+	return NULL;
+    while ((hi = hash2tableIndex(hi, histHashTableLength)),
+           (hp = histHashTable[hi]) != emptyHTE) {
+        if (hp == deletedHTE)
+	    deleted++;
+	else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex)))
+            return hp;
+	if (deleted > (histHashTableLength>>4)) {
+	    /* lots of deletes, so we need a sparser table. */
+            discardHistHashTable();
+            createHistHashTable(histHashTableLength);
+	    return findHistHashTable(lp, hashval);
+	}
+        hi++;                           /* linear rehash */
+    }
+    return NULL;
+}
+
+/* When merge semantics are in use, find the approximate predecessor for the
+ * new entry, so that the Htime entries are decreasing.  Return the entry just
+ * before the first entry with equal times, so the caller can check for
+ * duplicates.  When pTime is not NULL, use it as a starting point for search,
+ * otherwise search from beginning (largest time value) of history list. */
+PG_STATIC struct Hist *
+mergeInsertionPoint(
+    struct Hist *np,                      /* new entry to be inserted */
+    struct Hist *pTime)                   /* hint about where to insert */
+{
+    struct Hist *pp, *p;
+    if (histTail && histTail->Htime >= np->Htime)
+	pTime = histTail;		/* new entry goes at the end */
+    if (histMerg && histMerg != &Histlist && histMerg != Histlist.Hnext) {
+	/* Check above and below previous insertion point, in case we're adding
+	 * sequential times in the middle of the list (e.g. history -M). */
+	if (histMerg->Htime >= np->Htime)
+	    pTime = histMerg;
+	else if (histMerg->Hprev->Htime >= np->Htime)
+	    pTime = histMerg->Hprev;
+    }
+    if (pTime) {
+        /* With hint, search up the list until Htime is greater.  We skip past
+         * the equal ones, too, so our caller can elide duplicates. */
+        pp = pTime;
+        while (pp != &Histlist && pp->Htime <= np->Htime)
+            pp = pp->Hprev;
+    } else
+        pp = &Histlist;
+    /* Search down the list while current entry's time is too large. */
+    while ((p = pp->Hnext) && (p->Htime > np->Htime))
+            pp = p;                     /* advance insertion point */
+    /* Remember recent position as hint for next time */
+    histMerg = pp;
+    return pp;
+}
+
+/* Bubble Hnum & Href in new entry down to pp through earlier part of list. */
+PG_STATIC void bubbleHnumHrefDown(struct Hist *np, struct Hist *pp)
+{
+    struct Hist *p;
+    for (p = Histlist.Hnext; p != pp->Hnext; p = p->Hnext) {
+        /* swap Hnum & Href values of p and np. */
+        int n = p->Hnum, r = p->Href;
+        p->Hnum = np->Hnum; p->Href = np->Href;
+        np->Hnum = n; np->Href = r;
+    }
+}
 
+/* Enter new command into the history list according to current settings. */
 struct Hist *
-enthist(int event, struct wordent *lp, int docopy, int mflg)
+enthist(
+  int event,				/* newly incremented global eventno */
+  struct wordent *lp,
+  int docopy,
+  int mflg,				/* true if merge requested */
+  int histlen)				/* -1 if unknown */
 {
-    struct Hist *p = NULL, *pp = &Histlist;
-    int n, r;
+    struct Hist *p = NULL, *pp = &Histlist, *pTime = NULL;
     struct Hist *np;
     const Char *dp;
-    
+    unsigned lpHash = 0;                /* non-zero if hashing entries */
+
     if ((dp = varval(STRhistdup)) != STRNULL) {
 	if (eq(dp, STRerase)) {
 	    /* masaoki@akebono.tky.hp.com (Kobayashi Masaoki) */
-	    struct Hist *px;
-	    for (p = pp; (px = p, p = p->Hnext) != NULL;)
-		if (heq(lp, &(p->Hlex))){
-		    px->Hnext = p->Hnext;
-		    if (Htime != 0 && p->Htime > Htime)
-			Htime = p->Htime;
-		    n = p->Href;
-		    hfree(p);
-		    for (p = px->Hnext; p != NULL; p = p->Hnext)
-			p->Href = n--;
-		    break;
-		}
+            createHistHashTable(histlen);
+            lpHash = hashhist(lp);
+            assert(lpHash != 0);
+            p = findHistHashTable(lp, lpHash);
+            if (p) {
+		if (Htime != 0 && p->Htime > Htime)
+		    Htime = p->Htime;
+                /* If we are merging, and the old entry is at the place we want
+                 * to insert the new entry, then remember the place. */
+                if (mflg && Htime != 0 && p->Hprev->Htime >= Htime)
+                    pTime = p->Hprev;
+		if (!fastMergeErase)
+		    renumberHist(p);	/* Reset Href of subsequent entries */
+                hremove(p);
+		hfree(p);
+                p = NULL;               /* so new entry is allocated below */
+	    }
 	}
 	else if (eq(dp, STRall)) {
-	    for (p = pp; (p = p->Hnext) != NULL;)
-		if (heq(lp, &(p->Hlex))) {
-		    eventno--;
-		    break;
-		}
+            createHistHashTable(histlen);
+            lpHash = hashhist(lp);
+            assert(lpHash != 0);
+            p = findHistHashTable(lp, lpHash);
+	    if (p)   /* p!=NULL, only update this entry's Htime below */
+		eventno--;		/* not adding a new event */
 	}
 	else if (eq(dp, STRprev)) {
 	    if (pp->Hnext && heq(lp, &(pp->Hnext->Hlex))) {
@@ -149,14 +986,15 @@ enthist(int event, struct wordent *lp, int docopy, int mflg)
 	Htime = 0;
     }
     else
-	(void) time(&(np->Htime));
+        (void) time(&(np->Htime));
 
     if (p == np)
-	return np;
+        return np;                      /* reused existing entry */
 
+    /* Initialize the new entry. */
     np->Hnum = np->Href = event;
     if (docopy) {
-	copylex(&np->Hlex, lp);
+        copylex(&np->Hlex, lp);
 	if (histvalid)
 	    np->histline = Strsave(histline.s);
 	else
@@ -166,46 +1004,127 @@ enthist(int event, struct wordent *lp, int docopy, int mflg)
 	np->Hlex.next = lp->next;
 	lp->next->prev = &np->Hlex;
 	np->Hlex.prev = lp->prev;
-	lp->prev->next = &np->Hlex;
-	np->histline = NULL;
-    }
-    if (mflg)
-      {
-        while ((p = pp->Hnext) && (p->Htime > np->Htime))
-	  pp = p;
-	while (p && p->Htime == np->Htime)
-	  {
-	    if (heq(&p->Hlex, &np->Hlex))
-	      {
-	        eventno--;
-		hfree(np);
-	        return (p);
-	      }
-	    pp = p;
-	    p = p->Hnext;
-	  }
-	for (p = Histlist.Hnext; p != pp->Hnext; p = p->Hnext)
-	  {
-	    n = p->Hnum; r = p->Href;
-	    p->Hnum = np->Hnum; p->Href = np->Href;
-	    np->Hnum = n; np->Href = r;
-	  }
-      }
-    np->Hnext = pp->Hnext;
-    pp->Hnext = np;
+        lp->prev->next = &np->Hlex;
+        np->histline = NULL;
+    }
+    np->Hhash = 0;
+
+    /* The head of history list is the default insertion point.
+       If merging, advance insertion point, in pp, according to Htime. */
+    /* XXX -- In histdup=all, Htime values can be non-monotonic. */
+    if (mflg) {                         /* merge according to np->Htime */
+        pp = mergeInsertionPoint(np, pTime);
+        for (p = pp->Hnext; p && p->Htime == np->Htime; pp = p, p = p->Hnext) {
+            if (heq(&p->Hlex, &np->Hlex)) {
+                eventno--;              /* duplicate, so don't add new event */
+                hfree(np);
+                return (p);
+              }
+          }
+        /* pp is now the last entry with time >= to np. */
+	if (!fastMergeErase) {		/* renumber at end of loadhist */
+	    /* Before inserting np after pp, bubble its Hnum & Href values down
+	     * through the earlier part of list. */
+	    bubbleHnumHrefDown(np, pp);
+	}
+    }
+    else
+        pp = &Histlist;                 /* insert at beginning of history */
+    hinsert(np, pp);
+    if (lpHash && histlen != 0)		/* erase & all modes use hash table */
+        insertHistHashTable(np, lpHash);
+    else
+        discardHistHashTable();
     return (np);
 }
 
 static void
 hfree(struct Hist *hp)
 {
-
+    assert(hp != histMerg);
+    if (hp->Hhash)
+        removeHistHashTable(hp);
     freelex(&hp->Hlex);
     if (hp->histline)
-	xfree(hp->histline);
+        xfree(hp->histline);
     xfree(hp);
 }
 
+PG_STATIC void
+phist(struct Hist *hp, int hflg)
+{
+    if (hflg & HIST_ONLY) {
+	int old_output_raw;
+
+       /*
+        * Control characters have to be written as is (output_raw).
+        * This way one can preserve special characters (like tab) in
+        * the history file.
+        * From: mveksler@vnet.ibm.com (Veksler Michael)
+        */
+	old_output_raw = output_raw;
+        output_raw = 1;
+	cleanup_push(&old_output_raw, output_raw_restore);
+	if (hflg & HIST_TIME)
+	    /* 
+	     * Make file entry with history time in format:
+	     * "+NNNNNNNNNN" (10 digits, left padded with ascii '0') 
+	     */
+
+	    xprintf("#+%010lu\n", (unsigned long)hp->Htime);
+
+	if (HistLit && hp->histline)
+	    xprintf("%S\n", hp->histline);
+	else
+	    prlex(&hp->Hlex);
+        cleanup_until(&old_output_raw);
+    }
+    else {
+	Char   *cp = str2short("%h\t%T\t%R\n");
+	Char *p;
+	struct varent *vp = adrof(STRhistory);
+
+	if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1])
+	    cp = vp->vec[1];
+
+	p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp);
+	cleanup_push(p, xfree);
+	for (cp = p; *cp;)
+	    xputwchar(*cp++);
+	cleanup_until(p);
+    }
+}
+
+PG_STATIC void
+dophist(int n, int hflg)
+{
+    struct Hist *hp;
+    if (setintr) {
+	int old_pintr_disabled;
+
+	pintr_push_enable(&old_pintr_disabled);
+	cleanup_until(&old_pintr_disabled);
+    }
+    if ((hflg & HIST_REV) == 0) {
+	/* Since the history list is stored most recent first, non-reversing
+	 * print needs to print (backwards) up the list. */
+	if ((unsigned)n >= histCount)
+	    hp = histTail;
+	else {
+	    for (hp = Histlist.Hnext;
+		 --n > 0 && hp->Hnext != NULL;
+		 hp = hp->Hnext)
+		;
+	}
+	if (hp == NULL)
+	    return;			/* nothing to print */
+	for (; hp != &Histlist; hp = hp->Hprev)
+	    phist(hp, hflg);
+    } else {
+	for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext)
+	    phist(hp, hflg);
+    }
+}
 
 /*ARGSUSED*/
 void
@@ -247,11 +1166,10 @@ dohist(Char **vp, struct command *c)
 		break;
 	    }
     }
-
     if (hflg & HIST_CLEAR) {
-	struct Hist *np, *hp;
-	for (hp = &Histlist; (np = hp->Hnext) != NULL;)
-	    hp->Hnext = np->Hnext, hfree(np);
+        struct Hist *np, *hp;
+        for (hp = &Histlist; (np = hp->Hnext) != NULL;)
+            hremove(np), hfree(np);
     }
 
     if (hflg & (HIST_LOAD | HIST_MERGE))
@@ -264,76 +1182,7 @@ dohist(Char **vp, struct command *c)
 	else {
 	    n = getn(varval(STRhistory));
 	}
-	dohist1(Histlist.Hnext, &n, hflg);
-    }
-}
-
-static void
-dohist1(struct Hist *hp, int *np, int hflg)
-{
-    int    print = (*np) > 0;
-
-    for (; hp != 0; hp = hp->Hnext) {
-	if (setintr) {
-	    int old_pintr_disabled;
-
-	    pintr_push_enable(&old_pintr_disabled);
-	    cleanup_until(&old_pintr_disabled);
-	}
-	(*np)--;
-	if ((hflg & HIST_REV) == 0) {
-	    dohist1(hp->Hnext, np, hflg);
-	    if (print)
-		phist(hp, hflg);
-	    return;
-	}
-	if (*np >= 0)
-	    phist(hp, hflg);
-    }
-}
-
-static void
-phist(struct Hist *hp, int hflg)
-{
-    if (hflg & HIST_ONLY) {
-	int old_output_raw;
-
-       /*
-        * Control characters have to be written as is (output_raw).
-        * This way one can preserve special characters (like tab) in
-        * the history file.
-        * From: mveksler@vnet.ibm.com (Veksler Michael)
-        */
-	old_output_raw = output_raw;
-        output_raw = 1;
-	cleanup_push(&old_output_raw, output_raw_restore);
-	if (hflg & HIST_TIME)
-	    /* 
-	     * Make file entry with history time in format:
-	     * "+NNNNNNNNNN" (10 digits, left padded with ascii '0') 
-	     */
-
-	    xprintf("#+%010lu\n", (unsigned long)hp->Htime);
-
-	if (HistLit && hp->histline)
-	    xprintf("%S\n", hp->histline);
-	else
-	    prlex(&hp->Hlex);
-        cleanup_until(&old_output_raw);
-    }
-    else {
-	Char   *cp = str2short("%h\t%T\t%R\n");
-	Char *p;
-	struct varent *vp = adrof(STRhistory);
-
-	if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1])
-	    cp = vp->vec[1];
-
-	p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp);
-	cleanup_push(p, xfree);
-	for (cp = p; *cp;)
-	    xputwchar(*cp++);
-	cleanup_until(p);
+	dophist(n, hflg);
     }
 }
 
@@ -371,6 +1220,7 @@ fmthist(int fmt, ptr_t ptr)
     }
 }
 
+/* Save history before exiting the shell. */
 void
 rechist(Char *fname, int ref)
 {
@@ -424,10 +1274,11 @@ rechist(Char *fname, int ref)
     if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL)
 	if (shist->vec[1] && eq(shist->vec[1], STRmerge))
 	    loadhist(fname, 1);
+
     fp = xcreat(short2str(fname), 0600);
+    cleanup_until(fname);
     if (fp == -1) {
 	didfds = oldidfds;
-	cleanup_until(fname);
 	return;
     }
     ftmp = SHOUT;
@@ -437,10 +1288,10 @@ rechist(Char *fname, int ref)
     xclose(fp);
     SHOUT = ftmp;
     didfds = oldidfds;
-    cleanup_until(fname);
 }
 
 
+/* This is the entry point for loading history data from a file. */
 void
 loadhist(Char *fname, int mflg)
 {
@@ -455,4 +1306,14 @@ loadhist(Char *fname, int mflg)
 	loadhist_cmd[2] = STRtildothist;
 
     dosource(loadhist_cmd, NULL);
+
+    /* During history merging (enthist sees mflg set), we disable management of
+     * Hnum and Href (because fastMergeErase is true).  So now reset all the
+     * values based on the final ordering of the history list. */
+    if (mflg) {
+	int n = eventno;
+        struct Hist *hp = &Histlist;
+        while ((hp = hp->Hnext))
+	    hp->Hnum = hp->Href = n--;
+    }
 }