2 * sh.hist.c: Shell history expansions and substitutions
5 * Copyright (c) 1980, 1991 The Regents of the University of California.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
33 #include <stdio.h> /* for rename(2), grr. */
39 extern struct Strbuf histline;
42 static int heq (const struct wordent *, const struct wordent *);
43 static void hfree (struct Hist *);
45 #define HIST_ONLY 0x01
46 #define HIST_SAVE 0x02
47 #define HIST_LOAD 0x04
49 #define HIST_CLEAR 0x10
50 #define HIST_MERGE 0x20
51 #define HIST_TIME 0x40
57 /* Static functions don't show up in gprof summaries. So eliminate "static"
58 * modifier from some frequently called functions. */
62 #define PG_STATIC static
65 /* #define DEBUG_HIST 1 */
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 */
73 static void insertHistHashTable(struct Hist *, unsigned);
75 /* Insert new element (hp) in history list after specified predecessor (pp). */
77 hinsert(struct Hist *hp, struct Hist *pp)
79 struct Hist *fp = pp->Hnext; /* following element, if any */
80 hp->Hnext = fp, hp->Hprev = pp;
85 histTail = hp; /* meaning hp->Hnext == NULL */
89 /* Remove the entry from the history list. */
91 hremove(struct Hist *hp)
93 struct Hist *pp = hp->Hprev;
94 assert(pp); /* elements always have a previous */
95 pp->Hnext = hp->Hnext;
97 hp->Hnext->Hprev = pp;
99 histTail = pp; /* we must have been last */
100 if (hp == histMerg) /* deleting this hint from list */
102 assert(histCount > 0);
106 /* Prune length of history list to specified size by history variable. */
108 discardExcess(int hlen)
110 struct Hist *hp, *np;
111 if (histTail == NULL) {
112 assert(histCount == 0);
113 return; /* no entries on history list */
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);
124 while (histCount > (unsigned)hlen && (np = histTail) != &Histlist) {
125 if (eventno - np->Href >= hlen || hlen == 0)
126 hremove(np), hfree(np);
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);
140 /* Add the command "sp" to the history list. */
144 int mflg) /* true if -m (merge) specified */
146 /* throw away null lines */
147 if (sp && sp->next->word[0] == '\n')
150 (void) enthist(++eventno, sp, 1, mflg, histlen);
151 discardExcess(histlen);
154 #define USE_JENKINS_HASH 1
155 /* #define USE_ONE_AT_A_TIME 1 */
156 #undef PRIME_LENGTH /* no need for good HTL */
158 #ifdef USE_JENKINS_HASH
159 #define hashFcnName "lookup3"
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
167 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
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; \
177 #define final(a,b,c) \
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); \
188 struct hashValue /* State used to hash a wordend word list. */
193 /* Set up the internal state */
195 initializeHash(struct hashValue *h)
197 h->a = h->b = h->c = 0xdeadbeef;
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. */
204 addWordToHash(struct hashValue *h, const Char *word)
206 uint32_t a = h->a, b = h->b, c = h->c;
208 #define GETK if ((k = (uChar)*word++) == 0) break
210 assert(sizeof(Char) >= 4);
222 assert(sizeof(Char) == 2);
241 assert(sizeof(Char) == 1);
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;
259 h->a = a, h->b = b, h->c = c;
263 addCharToHash(struct hashValue *h, Char ch)
265 /* The compiler (gcc -O2) seems to do a good job optimizing this without
266 * explicitly extracting into local variables. */
268 mix(h->a, h->b, h->c);
272 finalizeHash(struct hashValue *h)
274 uint32_t a = h->a, b = h->b, c = h->c;
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 */
287 one_at_a_time(char *key, ub4 len)
290 for (hash=0, i=0; i<len; ++i)
293 hash += (hash << 10);
297 hash ^= (hash >> 11);
298 hash += (hash << 15);
299 return (hash & mask);
303 struct hashValue { uint32_t h; };
305 initializeHash(struct hashValue *h)
311 addWordToHash(struct hashValue *h, const Char *word)
314 uint32_t hash = h->h;
315 while (k = (uChar)*word++)
316 hash += k, hash += hash << 10, hash ^= hash >> 6;
321 addCharToHash(struct hashValue *h, Char c)
323 Char b[2] = { c, 0 };
328 finalizeHash(struct hashValue *h)
330 unsigned hash = h->h;
332 hash ^= (hash >> 11);
333 hash += (hash << 15);
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; };
343 initializeHash(struct hashValue *h)
349 addWordToHash(struct hashValue *h, const Char *word)
352 uint32_t hash = h->h;
353 while (k = (uChar)*word++)
354 hash = hash * 0x9e4167b9 + k;
359 addCharToHash(struct hashValue *h, Char c)
361 h->h = h->h * 0x9e4167b9 + (uChar)c;
365 finalizeHash(struct hashValue *h)
372 hashhist(struct wordent *h0)
375 struct wordent *firstWord = h0->next;
376 struct wordent *h = firstWord;
380 for (; h != h0; h = h->next) {
381 if (h->word[0] == '\n')
382 break; /* don't hash newline */
384 addCharToHash(&s, ' '); /* space between words */
385 addWordToHash(&s, h->word);
387 hash = finalizeHash(&s);
388 /* Zero means no hash value, so never return zero as a hash value. */
389 return hash ? hash : 0x7fffffff; /* prime! */
398 addWordToHash(&s, str);
399 return finalizeHash(&s);
403 #ifdef PRIME_LENGTH /* need good HTL */
404 #define hash2tableIndex(hash, len) ((hash) % len)
406 #define hash2tableIndex(hash, len) ((hash) & (len-1))
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. */
416 doTiming(int start) {
417 static struct timeval beginTime;
419 gettimeofday(&beginTime, NULL);
423 gettimeofday(&now, NULL);
424 return (now.tv_sec-beginTime.tv_sec) +
425 (now.tv_usec-beginTime.tv_usec)/1e6;
430 doTiming(int start) {
437 generateHashes(int nChars, unsigned nWords, unsigned samples, unsigned *hashes,
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)
453 wBoundaries[nWords-1] = 0xffffffff; /* don't end word past this point */
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 */
461 if (i == wBoundaries[w]) { /* end a word here and move to next */
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];
469 /* w is the index of the last word actually created. */
470 number[nChars + w] = 0; /* terminate last word */
471 unsigned timeLimit = !samples;
473 samples = 1000000000;
476 for (i = 0; i < samples; i++) {
477 /* increment 4 digit base 255 number; last characters vary fastest */
478 unsigned j = nChars-1 + w;
480 if (++number[j] != 0)
482 /* else reset this digit and proceed to next one */
484 if (&number[j] <= word[w].word)
485 break; /* stop at beginning of last word */
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) {
501 samples = i; /* number we actually did */
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));
508 #endif /* DEBUG_HIST */
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);
518 unsigned hashes[4]; /* dummy place to put hashes */
519 Char **vals = vp->vec;
521 int length = getn(*vals);
523 (length < 5) ? 1 : (length < 25) ? 2 : (length < 75) ? 3 : 4;
525 generateHashes(length, words, 0, hashes, 4);
529 unsigned length = 1024;
530 #ifdef PRIME_LENGTH /* need good HTL */
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. */
540 memset(bins, 0, sizeof(bins));
541 unsigned highest = 0;
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;
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);
557 /* Count run lengths to evaluate linear rehashing effectiveness. Estimate
558 * a little corrupted by edge effects. */
559 memset(bins, 0, sizeof(bins));
561 for (i = 0; hashes[i] == 0; i++); /* find first occupied bucket */
563 unsigned rehashed = 0;
564 for (; i<length; i++) {
565 unsigned hits = hashes[i];
566 if (hits == 0 && rehashed > 0)
567 hits = 1 && rehashed--;
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;
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;
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++) {
592 xprintf(" %d runs of length %d buckets\n", bins[i], i);
596 #endif /* DEBUG_HIST */
598 /* Compares two word lists for equality. */
600 heq(const struct wordent *a0, const struct wordent *b0)
602 const struct wordent *a = a0->next, *b = b0->next;
605 if (Strcmp(a->word, b->word) != 0)
610 return (b == b0) ? 1 : 0;
616 /* Renumber entries following p, which we will be deleting. */
618 renumberHist(struct Hist *p)
621 while ((p = p->Hnext))
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 */
636 static struct Hist * const emptyHTE = NULL;
637 static struct Hist * const deletedHTE = (struct Hist *)1;
640 unsigned insertCount;
641 unsigned removeCount;
648 checkHistHashTable(int print)
650 unsigned occupied = 0;
651 unsigned deleted = 0;
653 for (i = 0; i<histHashTableLength; i++)
654 if (histHashTable[i] == emptyHTE)
656 else if (histHashTable[i] == deletedHTE)
661 xprintf(" found len %u occupied %u deleted %u\n",
662 histHashTableLength, occupied, deleted);
663 assert(deleted == hashStats.deleted);
666 static int doneTest = 0;
668 /* Main entry point for displaying history statistics and hash function
671 displayHistStats(const char *reason)
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));
693 displayHistStats(const char *reason)
700 discardHistHashTable(void)
702 if (histHashTable == NULL)
704 displayHistStats("Discarding");
705 xfree(histHashTable);
706 histHashTable = NULL;
709 /* Computes a new hash table size, when the current one is too small. */
711 getHashTableSize(int hlen)
713 unsigned target = hlen * 2;
716 while ((size = 1<<e) < target)
718 #ifdef PRIME_LENGTH /* need good HTL */
719 /* Not all prime, but most are and none have factors smaller than 11. */
722 assert((size & (size-1)) == 0); /* must be a power of two */
727 /* Create the hash table or resize, if necessary. */
729 createHistHashTable(int hlen)
732 discardHistHashTable();
737 return; /* no need for hash table */
740 if (histHashTable != NULL) {
741 if (histCount < histHashTableLength * 3 / 4)
742 return; /* good enough for now */
743 discardHistHashTable(); /* too small */
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);
751 /* Now insert all the entries on the history list into the hash table. */
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);
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). */
767 insertHistHashTable(struct Hist *np, unsigned hashval)
769 unsigned rehashes = 0;
773 if (np->Hhash != 0) {
774 /* already in hash table */
775 assert(hashval == np->Hhash);
778 assert(np != deletedHTE);
779 /* Find a free (empty or deleted) slot, using linear rehash. */
780 assert(histHashTable);
782 ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)),
783 histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE);
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
792 xprintf("Growing history hash table from %d ...",
793 histHashTableLength);
796 discardHistHashTable();
797 createHistHashTable(histHashTableLength);
799 xprintf("to %d.\n", histHashTableLength);
804 /* Might be sensible to grow hash table if rehashes is "too big" here. */
805 if (histHashTable[hi] == deletedHTE)
807 histHashTable[hi] = np;
809 hashStats.insertCount++;
810 hashStats.rehashes += rehashes;
813 /* Remove the 'np' entry from the hash table. */
815 removeHistHashTable(struct Hist *np)
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]) {
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. */
829 while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] ==
832 if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] ==
834 /* dummies are no longer necessary placeholders. */
837 histHashTable[hash2tableIndex(hi+i, histHashTableLength)] =
841 hashStats.deleted += 1 - deletes; /* delta deleted entries */
842 hashStats.removeCount++;
845 hi++; /* linear rehash */
847 assert(!"Hist entry not found in hash table");
850 /* Search the history hash table for a command matching lp, using hashval as
853 findHistHashTable(struct wordent *lp, unsigned hashval)
855 unsigned deleted = 0; /* number of deleted entries skipped */
856 unsigned hi = hashval;
860 while ((hi = hash2tableIndex(hi, histHashTableLength)),
861 (hp = histHashTable[hi]) != emptyHTE) {
862 if (hp == deletedHTE)
864 else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex)))
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);
872 hi++; /* linear rehash */
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 *
884 struct Hist *np, /* new entry to be inserted */
885 struct Hist *pTime) /* hint about where to insert */
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)
895 else if (histMerg->Hprev->Htime >= np->Htime)
896 pTime = histMerg->Hprev;
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. */
902 while (pp != &Histlist && pp->Htime <= np->Htime)
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 */
914 /* Bubble Hnum & Href in new entry down to pp through earlier part of list. */
915 PG_STATIC void bubbleHnumHrefDown(struct Hist *np, struct Hist *pp)
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;
926 /* Enter new command into the history list according to current settings. */
929 int event, /* newly incremented global eventno */
932 int mflg, /* true if merge requested */
933 int hlen) /* -1 if unknown */
935 struct Hist *p = NULL, *pp = &Histlist, *pTime = NULL;
938 unsigned lpHash = 0; /* non-zero if hashing entries */
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);
946 p = findHistHashTable(lp, lpHash);
948 if (Htime != 0 && p->Htime > 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)
955 renumberHist(p); /* Reset Href of subsequent entries */
958 p = NULL; /* so new entry is allocated below */
961 else if (eq(dp, STRall)) {
962 createHistHashTable(hlen);
963 lpHash = hashhist(lp);
965 p = findHistHashTable(lp, lpHash);
966 if (p) /* p!=NULL, only update this entry's Htime below */
967 eventno--; /* not adding a new event */
969 else if (eq(dp, STRprev)) {
970 if (pp->Hnext && heq(lp, &(pp->Hnext->Hlex))) {
977 np = p ? p : xmalloc(sizeof(*np));
979 /* Pick up timestamp set by lex() in Htime if reading saved history */
985 (void) time(&(np->Htime));
988 return np; /* reused existing entry */
990 /* Initialize the new entry. */
991 np->Hnum = np->Href = event;
993 copylex(&np->Hlex, lp);
995 np->histline = Strsave(histline.s);
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;
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 */
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);
1028 pp = &Histlist; /* insert at beginning of history */
1030 if (lpHash && hlen != 0) /* erase & all modes use hash table */
1031 insertHistHashTable(np, lpHash);
1033 discardHistHashTable();
1038 hfree(struct Hist *hp)
1040 assert(hp != histMerg);
1042 removeHistHashTable(hp);
1045 xfree(hp->histline);
1050 phist(struct Hist *hp, int hflg)
1054 if (hflg & HIST_ONLY) {
1058 * Control characters have to be written as is (output_raw).
1059 * This way one can preserve special characters (like tab) in
1061 * From: mveksler@vnet.ibm.com (Veksler Michael)
1063 old_output_raw = output_raw;
1065 cleanup_push(&old_output_raw, output_raw_restore);
1066 if (hflg & HIST_TIME)
1068 * Make file entry with history time in format:
1069 * "+NNNNNNNNNN" (10 digits, left padded with ascii '0')
1072 xprintf("#+%010lu\n", (unsigned long)hp->Htime);
1074 if (HistLit && hp->histline)
1075 xprintf("%S\n", hp->histline);
1078 cleanup_until(&old_output_raw);
1081 Char *cp = str2short("%h\t%T\t%R\n");
1083 struct varent *vp = adrof(STRhistory);
1085 if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1])
1088 p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp);
1089 cleanup_push(p, xfree);
1097 dophist(int n, int hflg)
1101 int old_pintr_disabled;
1103 pintr_push_enable(&old_pintr_disabled);
1104 cleanup_until(&old_pintr_disabled);
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)
1112 for (hp = Histlist.Hnext;
1113 --n > 0 && hp->Hnext != NULL;
1118 return; /* nothing to print */
1119 for (; hp != &Histlist; hp = hp->Hprev)
1122 for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext)
1129 dohist(Char **vp, struct command *c)
1134 if (getn(varval(STRhistory)) == 0)
1136 while (*++vp && **vp == '-') {
1163 stderror(ERR_HISTUS, "chrSLMT");
1167 if (hflg & HIST_CLEAR) {
1168 struct Hist *np, *hp;
1169 for (hp = &Histlist; (np = hp->Hnext) != NULL;)
1170 hremove(np), hfree(np);
1173 if (hflg & (HIST_LOAD | HIST_MERGE))
1174 loadhist(*vp, (hflg & HIST_MERGE) ? 1 : 0);
1175 else if (hflg & HIST_SAVE)
1181 n = getn(varval(STRhistory));
1189 fmthist(int fmt, ptr_t ptr)
1191 struct Hist *hp = ptr;
1196 return xasprintf("%6d", hp->Hnum);
1198 if (HistLit && hp->histline)
1199 return xasprintf("%S", hp->histline);
1204 istr = sprlex(&hp->Hlex);
1205 buf = xmalloc(Strlen(istr) * MB_LEN_MAX + 1);
1207 for (p = buf, ip = istr; *ip != '\0'; ip++)
1208 p += one_wctomb(p, *ip);
1222 dotlock_cleanup(void* lockpath)
1224 dot_unlock((char*)lockpath);
1227 /* Save history before exiting the shell. */
1229 rechist(Char *xfname, int ref)
1232 int fp, ftmp, oldidfds, ophup_disabled;
1233 struct varent *shist;
1234 char path[MAXPATHLEN];
1237 static Char *dumphist[] = {STRhistory, STRmhT, 0, 0};
1239 if (fname == NULL && !ref)
1243 ophup_disabled = phup_disabled;
1247 * If $savehist is just set, we use the value of $history
1248 * else we use the value in $savehist
1250 if (((snum = varval(STRsavehist)) == STRNULL) &&
1251 ((snum = varval(STRhistory)) == STRNULL))
1255 if (fname == NULL) {
1256 if ((fname = varval(STRhistfile)) == STRNULL)
1257 fname = Strspl(varval(STRhome), &STRtildothist[1]);
1259 fname = Strsave(fname);
1262 fname = globone(fname, G_ERROR);
1263 cleanup_push(fname, xfree);
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.
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.
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)
1288 if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL) {
1290 int merge = 0, lock = 0;
1292 for (i = 1; shist->vec[i]; i++) {
1293 if (eq(shist->vec[i], STRmerge))
1295 if (eq(shist->vec[i], STRlock))
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);
1317 xsnprintf(path, sizeof(path), "%S.%S", fname, rs);
1320 fp = xcreat(path, 0600);
1323 cleanup_until(fname);
1324 phup_disabled = ophup_disabled;
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));
1334 UNREFERENCED_PARAMETER(st);
1339 dohist(dumphist, NULL);
1343 #ifndef WINNT_NATIVE
1344 (void)rename(path, short2str(fname));
1346 (void)ReplaceFile(short2str(fname), path, NULL, 0, NULL, NULL);
1348 cleanup_until(fname);
1349 phup_disabled = ophup_disabled;
1353 /* This is the entry point for loading history data from a file. */
1355 loadhist(Char *fname, int mflg)
1357 static Char *loadhist_cmd[] = {STRsource, NULL, NULL, NULL};
1358 loadhist_cmd[1] = mflg ? STRmm : STRmh;
1361 loadhist_cmd[2] = fname;
1362 else if ((fname = varval(STRhistfile)) != STRNULL)
1363 loadhist_cmd[2] = fname;
1365 loadhist_cmd[2] = STRtildothist;
1367 dosource(loadhist_cmd, NULL);
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. */
1374 struct Hist *hp = &Histlist;
1375 while ((hp = hp->Hnext))
1376 hp->Hnum = hp->Href = n--;
1384 discardExcess(histlen);