1/*
2 * sh.hist.c: Shell history expansions and substitutions
3 */
4/*-
5 * Copyright (c) 1980, 1991 The Regents of the University of California.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32#include "sh.h"
33#include <stdio.h>	/* for rename(2), grr. */
34#include <assert.h>
35#include "tc.h"
36#include "dotlock.h"
37
38extern int histvalid;
39extern struct Strbuf histline;
40Char HistLit = 0;
41
42static	int	heq	(const struct wordent *, const struct wordent *);
43static	void	hfree	(struct Hist *);
44
45#define HIST_ONLY	0x01
46#define HIST_SAVE	0x02
47#define HIST_LOAD	0x04
48#define HIST_REV	0x08
49#define HIST_CLEAR	0x10
50#define HIST_MERGE	0x20
51#define HIST_TIME	0x40
52
53/*
54 * C shell
55 */
56
57/* Static functions don't show up in gprof summaries.  So eliminate "static"
58 * modifier from some frequently called functions. */
59#ifdef PROF
60#define PG_STATIC
61#else
62#define PG_STATIC static
63#endif
64
65/* #define DEBUG_HIST 1 */
66
67static const int fastMergeErase = 1;
68static unsigned histCount = 0;		/* number elements on history list */
69static int histlen = 0;
70static struct Hist *histTail = NULL;     /* last element on history list */
71static struct Hist *histMerg = NULL;	 /* last element merged by Htime */
72
73static void insertHistHashTable(struct Hist *, unsigned);
74
75/* Insert new element (hp) in history list after specified predecessor (pp). */
76static void
77hinsert(struct Hist *hp, struct Hist *pp)
78{
79    struct Hist *fp = pp->Hnext;        /* following element, if any */
80    hp->Hnext = fp, hp->Hprev = pp;
81    pp->Hnext = hp;
82    if (fp)
83        fp->Hprev = hp;
84    else
85        histTail = hp;                  /* meaning hp->Hnext == NULL */
86    histCount++;
87}
88
89/* Remove the entry from the history list. */
90static void
91hremove(struct Hist *hp)
92{
93    struct Hist *pp = hp->Hprev;
94    assert(pp);                         /* elements always have a previous */
95    pp->Hnext = hp->Hnext;
96    if (hp->Hnext)
97        hp->Hnext->Hprev = pp;
98    else
99        histTail = pp;                  /* we must have been last */
100    if (hp == histMerg)			/* deleting this hint from list */
101	histMerg = NULL;
102    assert(histCount > 0);
103    histCount--;
104}
105
106/* Prune length of history list to specified size by history variable. */
107PG_STATIC void
108discardExcess(int hlen)
109{
110    struct Hist *hp, *np;
111    if (histTail == NULL) {
112        assert(histCount == 0);
113        return;                         /* no entries on history list */
114    }
115    /* Prune dummy entries from the front, then old entries from the back. If
116     * the list is still too long scan the whole list as before.  But only do a
117     * full scan if the list is more than 6% (1/16th) too long. */
118    while (histCount > (unsigned)hlen && (np = Histlist.Hnext)) {
119        if (eventno - np->Href >= hlen || hlen == 0)
120            hremove(np), hfree(np);
121        else
122            break;
123    }
124    while (histCount > (unsigned)hlen && (np = histTail) != &Histlist) {
125        if (eventno - np->Href >= hlen || hlen == 0)
126            hremove(np), hfree(np);
127        else
128            break;
129    }
130    if (histCount - (hlen >> 4) <= (unsigned)hlen)
131	return;				/* don't bother doing the full scan */
132    for (hp = &Histlist; histCount > (unsigned)hlen &&
133	(np = hp->Hnext) != NULL;)
134        if (eventno - np->Href >= hlen || hlen == 0)
135            hremove(np), hfree(np);
136        else
137            hp = np;
138}
139
140/* Add the command "sp" to the history list. */
141void
142savehist(
143  struct wordent *sp,
144  int mflg)				/* true if -m (merge) specified */
145{
146    /* throw away null lines */
147    if (sp && sp->next->word[0] == '\n')
148	return;
149    if (sp)
150        (void) enthist(++eventno, sp, 1, mflg, histlen);
151    discardExcess(histlen);
152}
153
154#define USE_JENKINS_HASH 1
155/* #define USE_ONE_AT_A_TIME 1 */
156#undef PRIME_LENGTH			/* no need for good HTL */
157
158#ifdef USE_JENKINS_HASH
159#define hashFcnName "lookup3"
160/* From:
161   lookup3.c, by Bob Jenkins, May 2006, Public Domain.
162   "...  You can use this free for any purpose.  It's in
163    the public domain.  It has no warranty."
164   http://burtleburtle.net/bob/hash/index.html
165 */
166
167#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
168#define mix(a,b,c) \
169{ \
170  a -= c;  a ^= rot(c, 4);  c += b; \
171  b -= a;  b ^= rot(a, 6);  a += c; \
172  c -= b;  c ^= rot(b, 8);  b += a; \
173  a -= c;  a ^= rot(c,16);  c += b; \
174  b -= a;  b ^= rot(a,19);  a += c; \
175  c -= b;  c ^= rot(b, 4);  b += a; \
176}
177#define final(a,b,c) \
178{ \
179  c ^= b; c -= rot(b,14); \
180  a ^= c; a -= rot(c,11); \
181  b ^= a; b -= rot(a,25); \
182  c ^= b; c -= rot(b,16); \
183  a ^= c; a -= rot(c, 4); \
184  b ^= a; b -= rot(a,14); \
185  c ^= b; c -= rot(b,24); \
186}
187
188struct hashValue		  /* State used to hash a wordend word list. */
189{
190    uint32_t a, b, c;
191};
192
193/* Set up the internal state */
194static void
195initializeHash(struct hashValue *h)
196{
197    h->a = h->b = h->c = 0xdeadbeef;
198}
199
200/* This does a partial hash of the Chars in a single word.  For efficiency we
201 * include 3 versions of the code to pack Chars into 32-bit words for the
202 * mixing function. */
203static void
204addWordToHash(struct hashValue *h, const Char *word)
205{
206    uint32_t a = h->a, b = h->b, c = h->c;
207#ifdef SHORT_STRINGS
208#define GETK    if ((k = (uChar)*word++) == 0) break
209#ifdef WIDE_STRINGS
210    assert(sizeof(Char) >= 4);
211    while (1) {
212	unsigned k;
213	GETK;
214	a += k;
215	GETK;
216	b += k;
217	GETK;
218	c += k;
219	mix(a, b, c);
220    }
221#else
222    assert(sizeof(Char) == 2);
223    while (1) {
224	unsigned k;
225	GETK;
226	a += k;
227	GETK;
228	a += k << 16;
229	GETK;
230	b += k;
231	GETK;
232	b += k << 16;
233	GETK;
234	c += k;
235	GETK;
236	c += k << 16;
237	mix(a, b, c);
238    }
239#endif
240#else
241    assert(sizeof(Char) == 1);
242    while (1) {
243	unsigned k;
244	if ((k = *word++) == 0) break; a += k;
245	if ((k = *word++) == 0) break; a += k << 8;
246	if ((k = *word++) == 0) break; a += k << 16;
247	if ((k = *word++) == 0) break; a += k << 24;
248	if ((k = *word++) == 0) break; b += k;
249	if ((k = *word++) == 0) break; b += k << 8;
250	if ((k = *word++) == 0) break; b += k << 16;
251	if ((k = *word++) == 0) break; b += k << 24;
252	if ((k = *word++) == 0) break; c += k;
253	if ((k = *word++) == 0) break; c += k << 8;
254	if ((k = *word++) == 0) break; c += k << 16;
255	if ((k = *word++) == 0) break; c += k << 24;
256	mix(a, b, c);
257    }
258#endif
259    h->a = a, h->b = b, h->c = c;
260}
261
262static void
263addCharToHash(struct hashValue *h, Char ch)
264{
265    /* The compiler (gcc -O2) seems to do a good job optimizing this without
266     * explicitly extracting into local variables. */
267    h->a += (uChar)ch;
268    mix(h->a, h->b, h->c);
269}
270
271static uint32_t
272finalizeHash(struct hashValue *h)
273{
274    uint32_t a = h->a, b = h->b, c = h->c;
275    final(a, b, c);
276    return c;
277}
278
279#elif USE_ONE_AT_A_TIME
280#define hashFcnName "one-at-a-time"
281/* This one is also from Bob Jenkins, but is slower but simpler than lookup3.
282   "...  The code given here are all public domain."
283   http://burtleburtle.net/bob/hash/doobs.html */
284
285#if 0
286ub4
287one_at_a_time(char *key, ub4 len)
288{
289  ub4   hash, i;
290  for (hash=0, i=0; i<len; ++i)
291  {
292    hash += key[i];
293    hash += (hash << 10);
294    hash ^= (hash >> 6);
295  }
296  hash += (hash << 3);
297  hash ^= (hash >> 11);
298  hash += (hash << 15);
299  return (hash & mask);
300}
301#endif
302
303struct hashValue { uint32_t h; };
304static void
305initializeHash(struct hashValue *h)
306{
307    h->h = 0;
308}
309
310static void
311addWordToHash(struct hashValue *h, const Char *word)
312{
313    unsigned k;
314    uint32_t hash = h->h;
315    while (k = (uChar)*word++)
316	hash += k, hash += hash << 10, hash ^= hash >> 6;
317    h->h = hash;
318}
319
320static void
321addCharToHash(struct hashValue *h, Char c)
322{
323    Char b[2] = { c, 0 };
324    addWordToHash(h, b);
325}
326
327static uint32_t
328finalizeHash(struct hashValue *h)
329{
330    unsigned hash = h->h;
331    hash += (hash << 3);
332    hash ^= (hash >> 11);
333    hash += (hash << 15);
334    return hash;
335}
336
337#else
338#define hashFcnName "add-mul"
339/* Simple multipy and add hash. */
340#define PRIME_LENGTH 1			/* need "good" HTL */
341struct hashValue { uint32_t h; };
342static void
343initializeHash(struct hashValue *h)
344{
345    h->h = 0xe13e2345;
346}
347
348static void
349addWordToHash(struct hashValue *h, const Char *word)
350{
351    unsigned k;
352    uint32_t hash = h->h;
353    while (k = (uChar)*word++)
354	hash = hash * 0x9e4167b9 + k;
355    h->h = hash;
356}
357
358static void
359addCharToHash(struct hashValue *h, Char c)
360{
361    h->h = h->h * 0x9e4167b9 + (uChar)c;
362}
363
364static uint32_t
365finalizeHash(struct hashValue *h)
366{
367    return h->h;
368}
369#endif
370
371static unsigned
372hashhist(struct wordent *h0)
373{
374    struct hashValue s;
375    struct wordent *firstWord = h0->next;
376    struct wordent *h = firstWord;
377    unsigned hash = 0;
378
379    initializeHash(&s);
380    for (; h != h0; h = h->next) {
381        if (h->word[0] == '\n')
382            break;                      /* don't hash newline */
383        if (h != firstWord)
384            addCharToHash(&s, ' ');	/* space between words */
385	addWordToHash(&s, h->word);
386    }
387    hash = finalizeHash(&s);
388    /* Zero means no hash value, so never return zero as a hash value. */
389    return hash ? hash : 0x7fffffff;	/* prime! */
390}
391
392#if 0
393unsigned
394hashStr(Char *str)
395{
396    struct hashValue s;
397    initializeHash(&s);
398    addWordToHash(&s, str);
399    return finalizeHash(&s);
400}
401#endif
402
403#ifdef PRIME_LENGTH			/* need good HTL */
404#define hash2tableIndex(hash, len) ((hash) % len)
405#else
406#define hash2tableIndex(hash, len) ((hash) & (len-1))
407#endif
408
409/* This code can be enabled to test the above hash functions for speed and
410 * collision avoidance.  The testing is enabled by "occasional" calls to
411 * displayHistStats(), see which. */
412#ifdef DEBUG_HIST
413
414#ifdef BSDTIMES
415static double
416doTiming(int start) {
417    static struct timeval beginTime;
418    if (start) {
419	gettimeofday(&beginTime, NULL);
420	return 0.0;
421    } else {
422	struct timeval now;
423	gettimeofday(&now, NULL);
424	return (now.tv_sec-beginTime.tv_sec) +
425	    (now.tv_usec-beginTime.tv_usec)/1e6;
426    }
427}
428#else
429static double
430doTiming(int start) {
431    USE(start);
432    return 0.0;
433}
434#endif
435
436static void
437generateHashes(int nChars, unsigned nWords, unsigned samples, unsigned *hashes,
438    unsigned length)
439{
440    if (nChars < 1)
441	return;
442    nWords = (nWords < 1) ? 1 : (nWords > 4) ? 4 : nWords;
443    Char *number = xmalloc((nChars+nWords)*sizeof(Char));
444    struct wordent word[4];
445    struct wordent base = { NULL, &word[0], &word[0] };
446    word[0].word = number, word[0].next = &base, word[0].prev = &base;
447    unsigned w = 0;			/* word number */
448    /* Generate multiple words of length 2, 3, 5, then all the rest. */
449    unsigned wBoundaries[4] = { 2-1, 2+3-1, 2+3+5-1, 0 };
450    /* Ensure the last word has at least 4 Chars in it. */
451    while (nWords >= 2 && nChars < (wBoundaries[nWords-2]+1) + 4)
452	nWords--;
453    wBoundaries[nWords-1] = 0xffffffff;	/* don't end word past this point */
454    unsigned i;
455    for (i = 0; i<nChars; i++) {
456	/* In deference to the gawd awful add-mul hash, we won't use the worse
457	 * case here (setting all Chars to 1), but assume mostly (or at least
458	 * initially) ASCII data. */
459	number[i+w] = '!';		/* 0x21 = 33 */
460
461	if (i == wBoundaries[w]) {	/* end a word here and move to next */
462	    w++;			/* next word */
463	    number[i+w] = 0;		/* terminate */
464	    word[w].word = &number[i+w+1];
465	    word[w].next = &base, word[w].prev = &word[w-1];
466	    word[w-1].next = &word[w], base.prev = &word[w];
467	}
468    }
469    /* w is the index of the last word actually created. */
470    number[nChars + w] = 0;		/* terminate last word */
471    unsigned timeLimit = !samples;
472    if (samples == 0)
473	samples = 1000000000;
474    doTiming(1);
475    double sec;
476    for (i = 0; i < samples; i++) {
477	/* increment 4 digit base 255 number; last characters vary fastest */
478	unsigned j = nChars-1 + w;
479	while (1) {
480	    if (++number[j] != 0)
481		break;
482	    /* else reset this digit and proceed to next one */
483	    number[j] = 1;
484	    if (&number[j] <= word[w].word)
485		break;			/* stop at beginning of last word */
486	    j--;
487	}
488	if (word[w].word[0] == '\n')
489	    word[w].word[0]++;		/* suppress newline character */
490	unsigned hash = hashhist(&base);
491	hashes[hash2tableIndex(hash, length)]++;
492	if (timeLimit && (i & 0x3ffff) == 0x3ffff) {
493	    sec = doTiming(0);
494	    if (sec > 10)
495		break;
496	}
497    }
498    if (i >= samples)
499	sec = doTiming(0);
500    else
501	samples = i;			/* number we actually did */
502    if (sec > 0.01) {
503	xprintf("Hash %d (%d Char %u words) with %s: %d nsec/hash, %d mcps\n",
504		samples, nChars, w+1, hashFcnName, (int)((sec/samples)*1e9),
505		(int)((double)samples*nChars/sec/1e6));
506    }
507}
508#endif /* DEBUG_HIST */
509
510#ifdef DEBUG_HIST
511static void
512testHash(void)
513{
514    static const Char STRtestHashTimings[] =
515	{ 't','e','s','t','H','a','s','h','T','i','m','i','n','g','s', 0 };
516    struct varent *vp = adrof(STRtestHashTimings);
517    if (vp && vp->vec) {
518	unsigned hashes[4];		/* dummy place to put hashes */
519	Char **vals = vp->vec;
520	while (*vals) {
521	    int length = getn(*vals);
522	    unsigned words =
523		(length < 5) ? 1 : (length < 25) ? 2 : (length < 75) ? 3 : 4;
524	    if (length > 0)
525		generateHashes(length, words, 0, hashes, 4);
526	    vals++;
527	}
528    }
529    unsigned length = 1024;
530#ifdef PRIME_LENGTH			/* need good HTL */
531    length = 1021;
532#endif
533    unsigned *hashes = xmalloc(length*sizeof(unsigned));
534    memset(hashes, 0, length*sizeof(unsigned));
535    /* Compute collision statistics for half full hashes modulo "length". */
536    generateHashes(4, 1, length/2, hashes, length);
537    /* Evaluate collisions by comparing occupancy rates (mean value 0.5).
538     * One bin for each number of hits. */
539    unsigned bins[155];
540    memset(bins, 0, sizeof(bins));
541    unsigned highest = 0;
542    unsigned i;
543    for (i = 0; i<length; i++) {
544	unsigned hits = hashes[i];
545	if (hits >= sizeof(bins)/sizeof(bins[0])) /* clip */
546	    hits = highest = sizeof(bins)/sizeof(bins[0]) - 1;
547	if (hits > highest)
548	    highest = hits;
549	bins[hits]++;
550    }
551    xprintf("Occupancy of %d buckets by %d hashes %d Chars %d word with %s\n",
552	    length, length/2, 4, 1, hashFcnName);
553    for (i = 0; i <= highest; i++) {
554	xprintf(" %d buckets (%d%%) with %d hits\n",
555		bins[i], bins[i]*100/length, i);
556    }
557    /* Count run lengths to evaluate linear rehashing effectiveness.  Estimate
558     * a little corrupted by edge effects. */
559    memset(bins, 0, sizeof(bins));
560    highest = 0;
561    for (i = 0; hashes[i] == 0; i++);	/* find first occupied bucket */
562    unsigned run = 0;
563    unsigned rehashed = 0;
564    for (; i<length; i++) {
565	unsigned hits = hashes[i];
566	if (hits == 0 && rehashed > 0)
567	    hits = 1 && rehashed--;
568	else if (hits > 1)
569	    rehashed += hits-1;
570	if (hits)
571	    run++;
572	else {
573	    /* a real free slot, count it */
574	    if (run >= sizeof(bins)/sizeof(bins[0])) /* clip */
575		run = highest = sizeof(bins)/sizeof(bins[0]) - 1;
576	    if (run > highest)
577		highest = run;
578	    bins[run]++;
579	    run = 0;
580	}
581    }
582    /* Ignore the partial run at end as we ignored the beginning. */
583    double merit = 0.0, entries = 0;
584    for (i = 0; i <= highest; i++) {
585	entries += bins[i]*i;		/* total hashed objects */
586	merit += bins[i]*i*i;
587    }
588    xprintf("Rehash collision figure of merit %u (ideal=100), run lengths:\n",
589	    (int)(100.0*merit/entries));
590    for (i = 0; i <= highest; i++) {
591	if (bins[i] != 0)
592	    xprintf(" %d runs of length %d buckets\n", bins[i], i);
593    }
594    xfree(hashes);
595}
596#endif /* DEBUG_HIST */
597
598/* Compares two word lists for equality. */
599static int
600heq(const struct wordent *a0, const struct wordent *b0)
601{
602    const struct wordent *a = a0->next, *b = b0->next;
603
604    for (;;) {
605	if (Strcmp(a->word, b->word) != 0)
606	    return 0;
607	a = a->next;
608	b = b->next;
609	if (a == a0)
610	    return (b == b0) ? 1 : 0;
611	if (b == b0)
612	    return 0;
613    }
614}
615
616/* Renumber entries following p, which we will be deleting. */
617PG_STATIC void
618renumberHist(struct Hist *p)
619{
620    int n = p->Href;
621    while ((p = p->Hnext))
622        p->Href = n--;
623}
624
625/* The hash table is implemented as an array of pointers to Hist entries.  Each
626 * entry is located in the table using hash2tableIndex() and checking the
627 * following entries in case of a collision (linear rehash).  Free entries in
628 * the table are zero (0, NULL, emptyHTE).  Deleted entries that cannot yet be
629 * freed are set to one (deletedHTE).  The Hist.Hhash member is non-zero iff
630 * the entry is in the hash table.  When the hash table get too full, it is
631 * reallocated to be approximately twice the history length (see
632 * getHashTableSize). */
633static struct Hist **histHashTable = NULL;
634static unsigned histHashTableLength = 0; /* number of Hist pointers in table */
635
636static struct Hist * const emptyHTE = NULL;
637static struct Hist * const deletedHTE = (struct Hist *)1;
638
639static struct {
640    unsigned insertCount;
641    unsigned removeCount;
642    unsigned rehashes;
643    int deleted;
644} hashStats;
645
646#ifdef DEBUG_HIST
647void
648checkHistHashTable(int print)
649{
650    unsigned occupied = 0;
651    unsigned deleted = 0;
652    unsigned i;
653    for (i = 0; i<histHashTableLength; i++)
654	if (histHashTable[i] == emptyHTE)
655	    continue;
656	else if (histHashTable[i] == deletedHTE)
657	    deleted++;
658	else
659	    occupied++;
660    if (print)
661	xprintf("  found len %u occupied %u deleted %u\n",
662		histHashTableLength, occupied, deleted);
663    assert(deleted == hashStats.deleted);
664}
665
666static int doneTest = 0;
667
668/* Main entry point for displaying history statistics and hash function
669 * behavior. */
670void
671displayHistStats(const char *reason)
672{
673    /* Just hash statistics for now. */
674    xprintf("%s history hash table len %u count %u (deleted %d)\n", reason,
675	    histHashTableLength, histCount, hashStats.deleted);
676    xprintf("  inserts %u rehashes %u%% each\n",
677	    hashStats.insertCount,
678	    (hashStats.insertCount
679	     ? 100*hashStats.rehashes/hashStats.insertCount : 0));
680    xprintf("  removes %u net %u\n",
681	    hashStats.removeCount,
682	    hashStats.insertCount - hashStats.removeCount);
683    assert(hashStats.insertCount >= hashStats.removeCount);
684    checkHistHashTable(1);
685    memset(&hashStats, 0, sizeof(hashStats));
686    if (!doneTest) {
687	testHash();
688	doneTest = 1;
689    }
690}
691#else
692void
693displayHistStats(const char *reason)
694{
695    USE(reason);
696}
697#endif
698
699static void
700discardHistHashTable(void)
701{
702    if (histHashTable == NULL)
703        return;
704    displayHistStats("Discarding");
705    xfree(histHashTable);
706    histHashTable = NULL;
707}
708
709/* Computes a new hash table size, when the current one is too small. */
710static unsigned
711getHashTableSize(int hlen)
712{
713    unsigned target = hlen * 2;
714    unsigned e = 5;
715    unsigned size;
716    while ((size = 1<<e) < target)
717	e++;
718#ifdef PRIME_LENGTH			/* need good HTL */
719    /* Not all prime, but most are and none have factors smaller than 11. */
720    return size+15;
721#else
722    assert((size & (size-1)) == 0);	/* must be a power of two */
723    return size;
724#endif
725}
726
727/* Create the hash table or resize, if necessary. */
728static void
729createHistHashTable(int hlen)
730{
731    if (hlen == 0) {
732	discardHistHashTable();
733        return;
734    }
735    if (hlen < 0) {
736	if (histlen <= 0)
737	    return;			/* no need for hash table */
738	hlen = histlen;
739    }
740    if (histHashTable != NULL) {
741	if (histCount < histHashTableLength * 3 / 4)
742	    return;			/* good enough for now */
743	discardHistHashTable();		/* too small */
744    }
745    histHashTableLength = getHashTableSize(
746	hlen > (int)histCount ? hlen : (int)histCount);
747    histHashTable = xmalloc(histHashTableLength * sizeof(struct Hist *));
748    memset(histHashTable, 0, histHashTableLength * sizeof(struct Hist *));
749    assert(histHashTable[0] == emptyHTE);
750
751    /* Now insert all the entries on the history list into the hash table. */
752    {
753        struct Hist *hp;
754        for (hp = &Histlist; (hp = hp->Hnext) != NULL;) {
755            unsigned lpHash = hashhist(&hp->Hlex);
756            assert(!hp->Hhash || hp->Hhash == lpHash);
757            hp->Hhash = 0;              /* force insert to new hash table */
758            insertHistHashTable(hp, lpHash);
759        }
760    }
761}
762
763/* Insert np into the hash table.  We assume that np is already on the
764 * Histlist.  The specified hashval matches the new Hist entry but has not yet
765 * been assigned to Hhash (or the element is already on the hash table). */
766static void
767insertHistHashTable(struct Hist *np, unsigned hashval)
768{
769    unsigned rehashes = 0;
770    unsigned hi = 0;
771    if (!histHashTable)
772	return;
773    if (np->Hhash != 0) {
774        /* already in hash table */
775        assert(hashval == np->Hhash);
776        return;
777    }
778    assert(np != deletedHTE);
779    /* Find a free (empty or deleted) slot, using linear rehash. */
780    assert(histHashTable);
781    for (rehashes = 0;
782         ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)),
783          histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE);
784         rehashes++) {
785        assert(np != histHashTable[hi]);
786        if (rehashes >= histHashTableLength / 10) {
787            /* Hash table is full, so grow it.  We assume the create function
788             * will roughly double the size we give it.  Create initializes the
789             * new table with everything on the Histlist, so we are done when
790             * it returns.  */
791#ifdef DEBUG_HIST
792	    xprintf("Growing history hash table from %d ...",
793		histHashTableLength);
794	    flush();
795#endif
796            discardHistHashTable();
797            createHistHashTable(histHashTableLength);
798#ifdef DEBUG_HIST
799	    xprintf("to %d.\n", histHashTableLength);
800#endif
801            return;
802        }
803    }
804    /* Might be sensible to grow hash table if rehashes is "too big" here. */
805    if (histHashTable[hi] == deletedHTE)
806	hashStats.deleted--;
807    histHashTable[hi] = np;
808    np->Hhash = hashval;
809    hashStats.insertCount++;
810    hashStats.rehashes += rehashes;
811}
812
813/* Remove the 'np' entry from the hash table. */
814static void
815removeHistHashTable(struct Hist *np)
816{
817    unsigned hi = np->Hhash;
818    if (!histHashTable || !hi)
819        return;                         /* no hash table or not on it */
820    /* find desired entry */
821    while ((hi = hash2tableIndex(hi, histHashTableLength)),
822           histHashTable[hi] != emptyHTE) {
823        if (np == histHashTable[hi]) {
824	    unsigned i;
825	    unsigned deletes = 0;
826	    histHashTable[hi] = deletedHTE; /* dummy, but non-zero entry */
827	    /* now peek ahead to see if the dummies are really necessary. */
828	    i = 1;
829	    while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] ==
830		   deletedHTE)
831		i++;
832	    if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] ==
833		emptyHTE) {
834		/* dummies are no longer necessary placeholders. */
835		deletes = i;
836		while (i-- > 0) {
837		    histHashTable[hash2tableIndex(hi+i, histHashTableLength)] =
838			emptyHTE;
839		}
840	    }
841	    hashStats.deleted += 1 - deletes; /* delta deleted entries */
842	    hashStats.removeCount++;
843            return;
844        }
845        hi++;                           /* linear rehash */
846    }
847    assert(!"Hist entry not found in hash table");
848}
849
850/* Search the history hash table for a command matching lp, using hashval as
851 * its hash value. */
852static struct Hist *
853findHistHashTable(struct wordent *lp, unsigned hashval)
854{
855    unsigned deleted = 0;		/* number of deleted entries skipped */
856    unsigned hi = hashval;
857    struct Hist *hp;
858    if (!histHashTable)
859	return NULL;
860    while ((hi = hash2tableIndex(hi, histHashTableLength)),
861           (hp = histHashTable[hi]) != emptyHTE) {
862        if (hp == deletedHTE)
863	    deleted++;
864	else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex)))
865            return hp;
866	if (deleted > (histHashTableLength>>4)) {
867	    /* lots of deletes, so we need a sparser table. */
868            discardHistHashTable();
869            createHistHashTable(histHashTableLength);
870	    return findHistHashTable(lp, hashval);
871	}
872        hi++;                           /* linear rehash */
873    }
874    return NULL;
875}
876
877/* When merge semantics are in use, find the approximate predecessor for the
878 * new entry, so that the Htime entries are decreasing.  Return the entry just
879 * before the first entry with equal times, so the caller can check for
880 * duplicates.  When pTime is not NULL, use it as a starting point for search,
881 * otherwise search from beginning (largest time value) of history list. */
882PG_STATIC struct Hist *
883mergeInsertionPoint(
884    struct Hist *np,                      /* new entry to be inserted */
885    struct Hist *pTime)                   /* hint about where to insert */
886{
887    struct Hist *pp, *p;
888    if (histTail && histTail->Htime >= np->Htime)
889	pTime = histTail;		/* new entry goes at the end */
890    if (histMerg && histMerg != &Histlist && histMerg != Histlist.Hnext) {
891	/* Check above and below previous insertion point, in case we're adding
892	 * sequential times in the middle of the list (e.g. history -M). */
893	if (histMerg->Htime >= np->Htime)
894	    pTime = histMerg;
895	else if (histMerg->Hprev->Htime >= np->Htime)
896	    pTime = histMerg->Hprev;
897    }
898    if (pTime) {
899        /* With hint, search up the list until Htime is greater.  We skip past
900         * the equal ones, too, so our caller can elide duplicates. */
901        pp = pTime;
902        while (pp != &Histlist && pp->Htime <= np->Htime)
903            pp = pp->Hprev;
904    } else
905        pp = &Histlist;
906    /* Search down the list while current entry's time is too large. */
907    while ((p = pp->Hnext) && (p->Htime > np->Htime))
908            pp = p;                     /* advance insertion point */
909    /* Remember recent position as hint for next time */
910    histMerg = pp;
911    return pp;
912}
913
914/* Bubble Hnum & Href in new entry down to pp through earlier part of list. */
915PG_STATIC void bubbleHnumHrefDown(struct Hist *np, struct Hist *pp)
916{
917    struct Hist *p;
918    for (p = Histlist.Hnext; p != pp->Hnext; p = p->Hnext) {
919        /* swap Hnum & Href values of p and np. */
920        int n = p->Hnum, r = p->Href;
921        p->Hnum = np->Hnum; p->Href = np->Href;
922        np->Hnum = n; np->Href = r;
923    }
924}
925
926/* Enter new command into the history list according to current settings. */
927struct Hist *
928enthist(
929  int event,				/* newly incremented global eventno */
930  struct wordent *lp,
931  int docopy,
932  int mflg,				/* true if merge requested */
933  int hlen)				/* -1 if unknown */
934{
935    struct Hist *p = NULL, *pp = &Histlist, *pTime = NULL;
936    struct Hist *np;
937    const Char *dp;
938    unsigned lpHash = 0;                /* non-zero if hashing entries */
939
940    if ((dp = varval(STRhistdup)) != STRNULL) {
941	if (eq(dp, STRerase)) {
942	    /* masaoki@akebono.tky.hp.com (Kobayashi Masaoki) */
943            createHistHashTable(hlen);
944            lpHash = hashhist(lp);
945            assert(lpHash != 0);
946            p = findHistHashTable(lp, lpHash);
947            if (p) {
948		if (Htime != 0 && p->Htime > Htime)
949		    Htime = p->Htime;
950                /* If we are merging, and the old entry is at the place we want
951                 * to insert the new entry, then remember the place. */
952                if (mflg && Htime != 0 && p->Hprev->Htime >= Htime)
953                    pTime = p->Hprev;
954		if (!fastMergeErase)
955		    renumberHist(p);	/* Reset Href of subsequent entries */
956                hremove(p);
957		hfree(p);
958                p = NULL;               /* so new entry is allocated below */
959	    }
960	}
961	else if (eq(dp, STRall)) {
962            createHistHashTable(hlen);
963            lpHash = hashhist(lp);
964            assert(lpHash != 0);
965            p = findHistHashTable(lp, lpHash);
966	    if (p)   /* p!=NULL, only update this entry's Htime below */
967		eventno--;		/* not adding a new event */
968	}
969	else if (eq(dp, STRprev)) {
970	    if (pp->Hnext && heq(lp, &(pp->Hnext->Hlex))) {
971		p = pp->Hnext;
972		eventno--;
973	    }
974	}
975    }
976
977    np = p ? p : xmalloc(sizeof(*np));
978
979    /* Pick up timestamp set by lex() in Htime if reading saved history */
980    if (Htime != 0) {
981	np->Htime = Htime;
982	Htime = 0;
983    }
984    else
985        (void) time(&(np->Htime));
986
987    if (p == np)
988        return np;                      /* reused existing entry */
989
990    /* Initialize the new entry. */
991    np->Hnum = np->Href = event;
992    if (docopy) {
993        copylex(&np->Hlex, lp);
994	if (histvalid)
995	    np->histline = Strsave(histline.s);
996	else
997	    np->histline = NULL;
998    }
999    else {
1000	np->Hlex.next = lp->next;
1001	lp->next->prev = &np->Hlex;
1002	np->Hlex.prev = lp->prev;
1003        lp->prev->next = &np->Hlex;
1004        np->histline = NULL;
1005    }
1006    np->Hhash = 0;
1007
1008    /* The head of history list is the default insertion point.
1009       If merging, advance insertion point, in pp, according to Htime. */
1010    /* XXX -- In histdup=all, Htime values can be non-monotonic. */
1011    if (mflg) {                         /* merge according to np->Htime */
1012        pp = mergeInsertionPoint(np, pTime);
1013        for (p = pp->Hnext; p && p->Htime == np->Htime; pp = p, p = p->Hnext) {
1014            if (heq(&p->Hlex, &np->Hlex)) {
1015                eventno--;              /* duplicate, so don't add new event */
1016                hfree(np);
1017                return (p);
1018              }
1019          }
1020        /* pp is now the last entry with time >= to np. */
1021	if (!fastMergeErase) {		/* renumber at end of loadhist */
1022	    /* Before inserting np after pp, bubble its Hnum & Href values down
1023	     * through the earlier part of list. */
1024	    bubbleHnumHrefDown(np, pp);
1025	}
1026    }
1027    else
1028        pp = &Histlist;                 /* insert at beginning of history */
1029    hinsert(np, pp);
1030    if (lpHash && hlen != 0)		/* erase & all modes use hash table */
1031        insertHistHashTable(np, lpHash);
1032    else
1033        discardHistHashTable();
1034    return (np);
1035}
1036
1037static void
1038hfree(struct Hist *hp)
1039{
1040    assert(hp != histMerg);
1041    if (hp->Hhash)
1042        removeHistHashTable(hp);
1043    freelex(&hp->Hlex);
1044    if (hp->histline)
1045        xfree(hp->histline);
1046    xfree(hp);
1047}
1048
1049PG_STATIC void
1050phist(struct Hist *hp, int hflg)
1051{
1052    if (hp->Href < 0)
1053	return;
1054    if (hflg & HIST_ONLY) {
1055	int old_output_raw;
1056
1057       /*
1058        * Control characters have to be written as is (output_raw).
1059        * This way one can preserve special characters (like tab) in
1060        * the history file.
1061        * From: mveksler@vnet.ibm.com (Veksler Michael)
1062        */
1063	old_output_raw = output_raw;
1064        output_raw = 1;
1065	cleanup_push(&old_output_raw, output_raw_restore);
1066	if (hflg & HIST_TIME)
1067	    /*
1068	     * Make file entry with history time in format:
1069	     * "+NNNNNNNNNN" (10 digits, left padded with ascii '0')
1070	     */
1071
1072	    xprintf("#+%010lu\n", (unsigned long)hp->Htime);
1073
1074	if (HistLit && hp->histline)
1075	    xprintf("%S\n", hp->histline);
1076	else
1077	    prlex(&hp->Hlex);
1078        cleanup_until(&old_output_raw);
1079    }
1080    else {
1081	Char   *cp = str2short("%h\t%T\t%R\n");
1082	Char *p;
1083	struct varent *vp = adrof(STRhistory);
1084
1085	if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1])
1086	    cp = vp->vec[1];
1087
1088	p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp);
1089	cleanup_push(p, xfree);
1090	for (cp = p; *cp;)
1091	    xputwchar(*cp++);
1092	cleanup_until(p);
1093    }
1094}
1095
1096PG_STATIC void
1097dophist(int n, int hflg)
1098{
1099    struct Hist *hp;
1100    if (setintr) {
1101	int old_pintr_disabled;
1102
1103	pintr_push_enable(&old_pintr_disabled);
1104	cleanup_until(&old_pintr_disabled);
1105    }
1106    if ((hflg & HIST_REV) == 0) {
1107	/* Since the history list is stored most recent first, non-reversing
1108	 * print needs to print (backwards) up the list. */
1109	if ((unsigned)n >= histCount)
1110	    hp = histTail;
1111	else {
1112	    for (hp = Histlist.Hnext;
1113		 --n > 0 && hp->Hnext != NULL;
1114		 hp = hp->Hnext)
1115		;
1116	}
1117	if (hp == NULL)
1118	    return;			/* nothing to print */
1119	for (; hp != &Histlist; hp = hp->Hprev)
1120	    phist(hp, hflg);
1121    } else {
1122	for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext)
1123	    phist(hp, hflg);
1124    }
1125}
1126
1127/*ARGSUSED*/
1128void
1129dohist(Char **vp, struct command *c)
1130{
1131    int     n, hflg = 0;
1132
1133    USE(c);
1134    if (getn(varval(STRhistory)) == 0)
1135	return;
1136    while (*++vp && **vp == '-') {
1137	Char   *vp2 = *vp;
1138
1139	while (*++vp2)
1140	    switch (*vp2) {
1141	    case 'c':
1142		hflg |= HIST_CLEAR;
1143		break;
1144	    case 'h':
1145		hflg |= HIST_ONLY;
1146		break;
1147	    case 'r':
1148		hflg |= HIST_REV;
1149		break;
1150	    case 'S':
1151		hflg |= HIST_SAVE;
1152		break;
1153	    case 'L':
1154		hflg |= HIST_LOAD;
1155		break;
1156	    case 'M':
1157	    	hflg |= HIST_MERGE;
1158		break;
1159	    case 'T':
1160	    	hflg |= HIST_TIME;
1161		break;
1162	    default:
1163		stderror(ERR_HISTUS, "chrSLMT");
1164		break;
1165	    }
1166    }
1167    if (hflg & HIST_CLEAR) {
1168        struct Hist *np, *hp;
1169        for (hp = &Histlist; (np = hp->Hnext) != NULL;)
1170            hremove(np), hfree(np);
1171    }
1172
1173    if (hflg & (HIST_LOAD | HIST_MERGE))
1174	loadhist(*vp, (hflg & HIST_MERGE) ? 1 : 0);
1175    else if (hflg & HIST_SAVE)
1176	rechist(*vp, 1);
1177    else {
1178	if (*vp)
1179	    n = getn(*vp);
1180	else {
1181	    n = getn(varval(STRhistory));
1182	}
1183	dophist(n, hflg);
1184    }
1185}
1186
1187
1188char *
1189fmthist(int fmt, ptr_t ptr)
1190{
1191    struct Hist *hp = ptr;
1192    char *buf;
1193
1194    switch (fmt) {
1195    case 'h':
1196	return xasprintf("%6d", hp->Hnum);
1197    case 'R':
1198	if (HistLit && hp->histline)
1199	    return xasprintf("%S", hp->histline);
1200	else {
1201	    Char *istr, *ip;
1202	    char *p;
1203
1204	    istr = sprlex(&hp->Hlex);
1205	    buf = xmalloc(Strlen(istr) * MB_LEN_MAX + 1);
1206
1207	    for (p = buf, ip = istr; *ip != '\0'; ip++)
1208		p += one_wctomb(p, *ip);
1209
1210	    *p = '\0';
1211	    xfree(istr);
1212	    return buf;
1213	}
1214    default:
1215	buf = xmalloc(1);
1216	buf[0] = '\0';
1217	return buf;
1218    }
1219}
1220
1221static void
1222dotlock_cleanup(void* lockpath)
1223{
1224	dot_unlock((char*)lockpath);
1225}
1226
1227/* Save history before exiting the shell. */
1228void
1229rechist(Char *xfname, int ref)
1230{
1231    Char    *snum, *rs;
1232    int     fp, ftmp, oldidfds, ophup_disabled;
1233    struct varent *shist;
1234    char path[MAXPATHLEN];
1235    struct stat st;
1236    static Char *fname;
1237    static Char   *dumphist[] = {STRhistory, STRmhT, 0, 0};
1238
1239    if (fname == NULL && !ref)
1240	return;
1241
1242    fname = xfname;
1243    ophup_disabled = phup_disabled;
1244    phup_disabled = 1;
1245
1246    /*
1247     * If $savehist is just set, we use the value of $history
1248     * else we use the value in $savehist
1249     */
1250    if (((snum = varval(STRsavehist)) == STRNULL) &&
1251	((snum = varval(STRhistory)) == STRNULL))
1252	snum = STRmaxint;
1253
1254
1255    if (fname == NULL) {
1256	if ((fname = varval(STRhistfile)) == STRNULL)
1257	    fname = Strspl(varval(STRhome), &STRtildothist[1]);
1258	else
1259	    fname = Strsave(fname);
1260    }
1261    else
1262	fname = globone(fname, G_ERROR);
1263    cleanup_push(fname, xfree);
1264
1265    /*
1266     * The 'savehist merge' feature is intended for an environment
1267     * with numerous shells being in simultaneous use. Imagine
1268     * any kind of window system. All these shells 'share' the same
1269     * ~/.history file for recording their command line history.
1270     * We try to handle the case of multiple shells trying to merge
1271     * histories at the same time, by creating semi-unique filenames
1272     * and saving the history there first and then trying to rename
1273     * them in the proper history file.
1274     *
1275     * Users that like to nuke their environment require here an atomic
1276     * loadhist-creat-dohist(dumphist)-close sequence which is given
1277		 * by optional lock parameter to savehist.
1278     *
1279     * jw.
1280     */
1281    /*
1282     * We need the didfds stuff before loadhist otherwise
1283     * exec in a script will fail to print if merge is set.
1284     * From: mveksler@iil.intel.com (Veksler Michael)
1285     */
1286    oldidfds = didfds;
1287    didfds = 0;
1288    if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL) {
1289	size_t i;
1290	int merge = 0, lock = 0;
1291
1292	for (i = 1; shist->vec[i]; i++) {
1293	    if (eq(shist->vec[i], STRmerge))
1294		merge++;
1295	    if (eq(shist->vec[i], STRlock))
1296		lock++;
1297	}
1298
1299	if (merge) {
1300	    jmp_buf_t osetexit;
1301	    if (lock) {
1302#ifndef WINNT_NATIVE
1303		char *lockpath = strsave(short2str(fname));
1304		cleanup_push(lockpath, xfree);
1305		/* Poll in 100 miliseconds interval to obtain the lock. */
1306		if ((dot_lock(lockpath, 100) == 0))
1307		    cleanup_push(lockpath, dotlock_cleanup);
1308#endif
1309	    }
1310	    getexit(osetexit);
1311	    if (setexit() == 0)
1312		loadhist(fname, 1);
1313	    resexit(osetexit);
1314	}
1315    }
1316    rs = randsuf();
1317    xsnprintf(path, sizeof(path), "%S.%S", fname, rs);
1318    xfree(rs);
1319
1320    fp = xcreat(path, 0600);
1321    if (fp == -1) {
1322	didfds = oldidfds;
1323	cleanup_until(fname);
1324	phup_disabled = ophup_disabled;
1325	return;
1326    }
1327    /* Try to preserve ownership and permissions of the original history file */
1328#ifndef WINNT_NATIVE
1329    if (stat(short2str(fname), &st) != -1) {
1330	TCSH_IGNORE(fchown(fp, st.st_uid, st.st_gid));
1331	TCSH_IGNORE(fchmod(fp, st.st_mode));
1332    }
1333#else
1334    UNREFERENCED_PARAMETER(st);
1335#endif
1336    ftmp = SHOUT;
1337    SHOUT = fp;
1338    dumphist[2] = snum;
1339    dohist(dumphist, NULL);
1340    xclose(fp);
1341    SHOUT = ftmp;
1342    didfds = oldidfds;
1343#ifndef WINNT_NATIVE
1344    (void)rename(path, short2str(fname));
1345#else
1346    (void)ReplaceFile(short2str(fname), path, NULL, 0, NULL, NULL);
1347#endif
1348    cleanup_until(fname);
1349    phup_disabled = ophup_disabled;
1350}
1351
1352
1353/* This is the entry point for loading history data from a file. */
1354void
1355loadhist(Char *fname, int mflg)
1356{
1357    static Char   *loadhist_cmd[] = {STRsource, NULL, NULL, NULL};
1358    loadhist_cmd[1] = mflg ? STRmm : STRmh;
1359
1360    if (fname != NULL)
1361	loadhist_cmd[2] = fname;
1362    else if ((fname = varval(STRhistfile)) != STRNULL)
1363	loadhist_cmd[2] = fname;
1364    else
1365	loadhist_cmd[2] = STRtildothist;
1366
1367    dosource(loadhist_cmd, NULL);
1368
1369    /* During history merging (enthist sees mflg set), we disable management of
1370     * Hnum and Href (because fastMergeErase is true).  So now reset all the
1371     * values based on the final ordering of the history list. */
1372    if (mflg) {
1373	int n = eventno;
1374        struct Hist *hp = &Histlist;
1375        while ((hp = hp->Hnext))
1376	    hp->Hnum = hp->Href = n--;
1377    }
1378}
1379
1380void
1381sethistory(int n)
1382{
1383    histlen = n;
1384    discardExcess(histlen);
1385}
1386