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