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
hinsert(struct Hist * hp,struct Hist * pp)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
hremove(struct Hist * hp)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
discardExcess(int hlen)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
savehist(struct wordent * sp,int mflg)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
initializeHash(struct hashValue * h)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
addWordToHash(struct hashValue * h,const Char * word)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 #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
262 static void
addCharToHash(struct hashValue * h,Char ch)263 addCharToHash(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
271 static uint32_t
finalizeHash(struct hashValue * h)272 finalizeHash(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
286 ub4
287 one_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
303 struct hashValue { uint32_t h; };
304 static void
initializeHash(struct hashValue * h)305 initializeHash(struct hashValue *h)
306 {
307 h->h = 0;
308 }
309
310 static void
addWordToHash(struct hashValue * h,const Char * word)311 addWordToHash(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
320 static void
addCharToHash(struct hashValue * h,Char c)321 addCharToHash(struct hashValue *h, Char c)
322 {
323 Char b[2] = { c, 0 };
324 addWordToHash(h, b);
325 }
326
327 static uint32_t
finalizeHash(struct hashValue * h)328 finalizeHash(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 */
341 struct hashValue { uint32_t h; };
342 static void
initializeHash(struct hashValue * h)343 initializeHash(struct hashValue *h)
344 {
345 h->h = 0xe13e2345;
346 }
347
348 static void
addWordToHash(struct hashValue * h,const Char * word)349 addWordToHash(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
358 static void
addCharToHash(struct hashValue * h,Char c)359 addCharToHash(struct hashValue *h, Char c)
360 {
361 h->h = h->h * 0x9e4167b9 + (uChar)c;
362 }
363
364 static uint32_t
finalizeHash(struct hashValue * h)365 finalizeHash(struct hashValue *h)
366 {
367 return h->h;
368 }
369 #endif
370
371 static unsigned
hashhist(struct wordent * h0)372 hashhist(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
393 unsigned
394 hashStr(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
415 static double
doTiming(int start)416 doTiming(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
429 static double
doTiming(int start)430 doTiming(int start) {
431 USE(start);
432 return 0.0;
433 }
434 #endif
435
436 static void
generateHashes(int nChars,unsigned nWords,unsigned samples,unsigned * hashes,unsigned length)437 generateHashes(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
511 static void
testHash(void)512 testHash(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. */
599 static int
heq(const struct wordent * a0,const struct wordent * b0)600 heq(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. */
617 PG_STATIC void
renumberHist(struct Hist * p)618 renumberHist(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). */
633 static struct Hist **histHashTable = NULL;
634 static unsigned histHashTableLength = 0; /* number of Hist pointers in table */
635
636 static struct Hist * const emptyHTE = NULL;
637 static struct Hist * const deletedHTE = (struct Hist *)1;
638
639 static struct {
640 unsigned insertCount;
641 unsigned removeCount;
642 unsigned rehashes;
643 int deleted;
644 } hashStats;
645
646 #ifdef DEBUG_HIST
647 void
checkHistHashTable(int print)648 checkHistHashTable(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
666 static int doneTest = 0;
667
668 /* Main entry point for displaying history statistics and hash function
669 * behavior. */
670 void
displayHistStats(const char * reason)671 displayHistStats(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
692 void
displayHistStats(const char * reason)693 displayHistStats(const char *reason)
694 {
695 USE(reason);
696 }
697 #endif
698
699 static void
discardHistHashTable(void)700 discardHistHashTable(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. */
710 static unsigned
getHashTableSize(int hlen)711 getHashTableSize(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. */
728 static void
createHistHashTable(int hlen)729 createHistHashTable(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). */
766 static void
insertHistHashTable(struct Hist * np,unsigned hashval)767 insertHistHashTable(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. */
814 static void
removeHistHashTable(struct Hist * np)815 removeHistHashTable(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. */
852 static struct Hist *
findHistHashTable(struct wordent * lp,unsigned hashval)853 findHistHashTable(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. */
882 PG_STATIC struct Hist *
mergeInsertionPoint(struct Hist * np,struct Hist * pTime)883 mergeInsertionPoint(
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. */
bubbleHnumHrefDown(struct Hist * np,struct Hist * pp)915 PG_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. */
927 struct Hist *
enthist(int event,struct wordent * lp,int docopy,int mflg,int hlen)928 enthist(
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
1037 static void
hfree(struct Hist * hp)1038 hfree(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
1049 PG_STATIC void
phist(struct Hist * hp,int hflg)1050 phist(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
1096 PG_STATIC void
dophist(int n,int hflg)1097 dophist(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*/
1128 void
dohist(Char ** vp,struct command * c)1129 dohist(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
1188 char *
fmthist(int fmt,ptr_t ptr)1189 fmthist(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
1221 static void
dotlock_cleanup(void * lockpath)1222 dotlock_cleanup(void* lockpath)
1223 {
1224 dot_unlock((char*)lockpath);
1225 }
1226
1227 /* Save history before exiting the shell. */
1228 void
rechist(Char * xfname,int ref)1229 rechist(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. */
1354 void
loadhist(Char * fname,int mflg)1355 loadhist(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
1380 void
sethistory(int n)1381 sethistory(int n)
1382 {
1383 histlen = n;
1384 discardExcess(histlen);
1385 }
1386