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;
209 assert(sizeof(Char) >= 4);
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;
218 assert(sizeof(Char) == 2);
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;
231 assert(sizeof(Char) == 1);
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;
249 h->a = a, h->b = b, h->c = c;
253 addCharToHash(struct hashValue *h, Char ch)
255 /* The compiler (gcc -O2) seems to do a good job optimizing this without
256 * explicitly extracting into local variables. */
258 mix(h->a, h->b, h->c);
262 finalizeHash(struct hashValue *h)
264 uint32_t a = h->a, b = h->b, c = h->c;
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 */
277 one_at_a_time(char *key, ub4 len)
280 for (hash=0, i=0; i<len; ++i)
283 hash += (hash << 10);
287 hash ^= (hash >> 11);
288 hash += (hash << 15);
289 return (hash & mask);
293 struct hashValue { uint32_t h; };
295 initializeHash(struct hashValue *h)
301 addWordToHash(struct hashValue *h, const Char *word)
304 uint32_t hash = h->h;
305 while (k = (uChar)*word++)
306 hash += k, hash += hash << 10, hash ^= hash >> 6;
311 addCharToHash(struct hashValue *h, Char c)
313 Char b[2] = { c, 0 };
318 finalizeHash(struct hashValue *h)
320 unsigned hash = h->h;
322 hash ^= (hash >> 11);
323 hash += (hash << 15);
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; };
333 initializeHash(struct hashValue *h)
339 addWordToHash(struct hashValue *h, const Char *word)
342 uint32_t hash = h->h;
343 while (k = (uChar)*word++)
344 hash = hash * 0x9e4167b9 + k;
349 addCharToHash(struct hashValue *h, Char c)
351 h->h = h->h * 0x9e4167b9 + (uChar)c;
355 finalizeHash(struct hashValue *h)
362 hashhist(struct wordent *h0)
365 struct wordent *firstWord = h0->next;
366 struct wordent *h = firstWord;
370 for (; h != h0; h = h->next) {
371 if (h->word[0] == '\n')
372 break; /* don't hash newline */
374 addCharToHash(&s, ' '); /* space between words */
375 addWordToHash(&s, h->word);
377 hash = finalizeHash(&s);
378 /* Zero means no hash value, so never return zero as a hash value. */
379 return hash ? hash : 0x7fffffff; /* prime! */
388 addWordToHash(&s, str);
389 return finalizeHash(&s);
393 #ifdef PRIME_LENGTH /* need good HTL */
394 #define hash2tableIndex(hash, len) ((hash) % len)
396 #define hash2tableIndex(hash, len) ((hash) & (len-1))
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. */
406 doTiming(int start) {
407 static struct timeval beginTime;
409 gettimeofday(&beginTime, NULL);
413 gettimeofday(&now, NULL);
414 return (now.tv_sec-beginTime.tv_sec) +
415 (now.tv_usec-beginTime.tv_usec)/1e6;
420 doTiming(int start) {
427 generateHashes(int nChars, unsigned nWords, unsigned samples, unsigned *hashes,
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)
443 wBoundaries[nWords-1] = 0xffffffff; /* don't end word past this point */
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 */
451 if (i == wBoundaries[w]) { /* end a word here and move to next */
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];
459 /* w is the index of the last word actually created. */
460 number[nChars + w] = 0; /* terminate last word */
461 unsigned timeLimit = !samples;
463 samples = 1000000000;
466 for (i = 0; i < samples; i++) {
467 /* increment 4 digit base 255 number; last characters vary fastest */
468 unsigned j = nChars-1 + w;
470 if (++number[j] != 0)
472 /* else reset this digit and proceed to next one */
474 if (&number[j] <= word[w].word)
475 break; /* stop at beginning of last word */
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) {
491 samples = i; /* number we actually did */
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));
498 #endif /* DEBUG_HIST */
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);
508 unsigned hashes[4]; /* dummy place to put hashes */
509 Char **vals = vp->vec;
511 int length = getn(*vals);
513 (length < 5) ? 1 : (length < 25) ? 2 : (length < 75) ? 3 : 4;
515 generateHashes(length, words, 0, hashes, 4);
519 unsigned length = 1024;
520 #ifdef PRIME_LENGTH /* need good HTL */
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. */
530 memset(bins, 0, sizeof(bins));
531 unsigned highest = 0;
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;
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);
547 /* Count run lengths to evaluate linear rehashing effectiveness. Estimate
548 * a little corrupted by edge effects. */
549 memset(bins, 0, sizeof(bins));
551 for (i = 0; hashes[i] == 0; i++); /* find first occupied bucket */
553 unsigned rehashed = 0;
554 for (; i<length; i++) {
555 unsigned hits = hashes[i];
556 if (hits == 0 && rehashed > 0)
557 hits = 1 && rehashed--;
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;
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;
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++) {
582 xprintf(" %d runs of length %d buckets\n", bins[i], i);
586 #endif /* DEBUG_HIST */
588 /* Compares two word lists for equality. */
590 heq(const struct wordent *a0, const struct wordent *b0)
592 const struct wordent *a = a0->next, *b = b0->next;
595 if (Strcmp(a->word, b->word) != 0)
600 return (b == b0) ? 1 : 0;
606 /* Renumber entries following p, which we will be deleting. */
608 renumberHist(struct Hist *p)
611 while ((p = p->Hnext))
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 */
626 static struct Hist * const emptyHTE = NULL;
627 static struct Hist * const deletedHTE = (struct Hist *)1;
630 unsigned insertCount;
631 unsigned removeCount;
638 checkHistHashTable(int print)
640 unsigned occupied = 0;
641 unsigned deleted = 0;
643 for (i = 0; i<histHashTableLength; i++)
644 if (histHashTable[i] == emptyHTE)
646 else if (histHashTable[i] == deletedHTE)
651 xprintf(" found len %u occupied %u deleted %u\n",
652 histHashTableLength, occupied, deleted);
653 assert(deleted == hashStats.deleted);
656 static int doneTest = 0;
658 /* Main entry point for displaying history statistics and hash function
661 displayHistStats(const char *reason)
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));
683 displayHistStats(const char *reason)
690 discardHistHashTable(void)
692 if (histHashTable == NULL)
694 displayHistStats("Discarding");
695 xfree(histHashTable);
696 histHashTable = NULL;
699 /* Computes a new hash table size, when the current one is too small. */
701 getHashTableSize(int hlen)
703 unsigned target = hlen * 2;
706 while ((size = 1<<e) < target)
708 #ifdef PRIME_LENGTH /* need good HTL */
709 /* Not all prime, but most are and none have factors smaller than 11. */
712 assert((size & (size-1)) == 0); /* must be a power of two */
717 /* Create the hash table or resize, if necessary. */
719 createHistHashTable(int hlen)
722 discardHistHashTable();
727 return; /* no need for hash table */
730 if (histHashTable != NULL) {
731 if (histCount < histHashTableLength * 3 / 4)
732 return; /* good enough for now */
733 discardHistHashTable(); /* too small */
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);
741 /* Now insert all the entries on the history list into the hash table. */
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);
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). */
757 insertHistHashTable(struct Hist *np, unsigned hashval)
759 unsigned rehashes = 0;
763 if (np->Hhash != 0) {
764 /* already in hash table */
765 assert(hashval == np->Hhash);
768 assert(np != deletedHTE);
769 /* Find a free (empty or deleted) slot, using linear rehash. */
770 assert(histHashTable);
772 ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)),
773 histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE);
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
782 xprintf("Growing history hash table from %d ...",
783 histHashTableLength);
786 discardHistHashTable();
787 createHistHashTable(histHashTableLength);
789 xprintf("to %d.\n", histHashTableLength);
794 /* Might be sensible to grow hash table if rehashes is "too big" here. */
795 if (histHashTable[hi] == deletedHTE)
797 histHashTable[hi] = np;
799 hashStats.insertCount++;
800 hashStats.rehashes += rehashes;
803 /* Remove the 'np' entry from the hash table. */
805 removeHistHashTable(struct Hist *np)
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]) {
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. */
819 while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] ==
822 if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] ==
824 /* dummies are no longer necessary placeholders. */
827 histHashTable[hash2tableIndex(hi+i, histHashTableLength)] =
831 hashStats.deleted += 1 - deletes; /* delta deleted entries */
832 hashStats.removeCount++;
835 hi++; /* linear rehash */
837 assert(!"Hist entry not found in hash table");
840 /* Search the history hash table for a command matching lp, using hashval as
843 findHistHashTable(struct wordent *lp, unsigned hashval)
845 unsigned deleted = 0; /* number of deleted entries skipped */
846 unsigned hi = hashval;
850 while ((hi = hash2tableIndex(hi, histHashTableLength)),
851 (hp = histHashTable[hi]) != emptyHTE) {
852 if (hp == deletedHTE)
854 else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex)))
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);
862 hi++; /* linear rehash */
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 *
874 struct Hist *np, /* new entry to be inserted */
875 struct Hist *pTime) /* hint about where to insert */
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)
885 else if (histMerg->Hprev->Htime >= np->Htime)
886 pTime = histMerg->Hprev;
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. */
892 while (pp != &Histlist && pp->Htime <= np->Htime)
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 */
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)
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;
916 /* Enter new command into the history list according to current settings. */
919 int event, /* newly incremented global eventno */
922 int mflg, /* true if merge requested */
923 int hlen) /* -1 if unknown */
925 struct Hist *p = NULL, *pp = &Histlist, *pTime = NULL;
928 unsigned lpHash = 0; /* non-zero if hashing entries */
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);
936 p = findHistHashTable(lp, lpHash);
938 if (Htime != 0 && p->Htime > 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)
945 renumberHist(p); /* Reset Href of subsequent entries */
948 p = NULL; /* so new entry is allocated below */
951 else if (eq(dp, STRall)) {
952 createHistHashTable(hlen);
953 lpHash = hashhist(lp);
955 p = findHistHashTable(lp, lpHash);
956 if (p) /* p!=NULL, only update this entry's Htime below */
957 eventno--; /* not adding a new event */
959 else if (eq(dp, STRprev)) {
960 if (pp->Hnext && heq(lp, &(pp->Hnext->Hlex))) {
967 np = p ? p : xmalloc(sizeof(*np));
969 /* Pick up timestamp set by lex() in Htime if reading saved history */
975 (void) time(&(np->Htime));
978 return np; /* reused existing entry */
980 /* Initialize the new entry. */
981 np->Hnum = np->Href = event;
983 copylex(&np->Hlex, lp);
985 np->histline = Strsave(histline.s);
990 np->Hlex.next = lp->next;
991 lp->next->prev = &np->Hlex;
992 np->Hlex.prev = lp->prev;
993 lp->prev->next = &np->Hlex;
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 */
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);
1018 pp = &Histlist; /* insert at beginning of history */
1020 if (lpHash && hlen != 0) /* erase & all modes use hash table */
1021 insertHistHashTable(np, lpHash);
1023 discardHistHashTable();
1028 hfree(struct Hist *hp)
1030 assert(hp != histMerg);
1032 removeHistHashTable(hp);
1035 xfree(hp->histline);
1040 phist(struct Hist *hp, int hflg)
1044 if (hflg & HIST_ONLY) {
1048 * Control characters have to be written as is (output_raw).
1049 * This way one can preserve special characters (like tab) in
1051 * From: mveksler@vnet.ibm.com (Veksler Michael)
1053 old_output_raw = output_raw;
1055 cleanup_push(&old_output_raw, output_raw_restore);
1056 if (hflg & HIST_TIME)
1058 * Make file entry with history time in format:
1059 * "+NNNNNNNNNN" (10 digits, left padded with ascii '0')
1062 xprintf("#+%010lu\n", (unsigned long)hp->Htime);
1064 if (HistLit && hp->histline)
1065 xprintf("%S\n", hp->histline);
1068 cleanup_until(&old_output_raw);
1071 Char *cp = str2short("%h\t%T\t%R\n");
1073 struct varent *vp = adrof(STRhistory);
1075 if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1])
1078 p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp);
1079 cleanup_push(p, xfree);
1087 dophist(int n, int hflg)
1091 int old_pintr_disabled;
1093 pintr_push_enable(&old_pintr_disabled);
1094 cleanup_until(&old_pintr_disabled);
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)
1102 for (hp = Histlist.Hnext;
1103 --n > 0 && hp->Hnext != NULL;
1108 return; /* nothing to print */
1109 for (; hp != &Histlist; hp = hp->Hprev)
1112 for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext)
1119 dohist(Char **vp, struct command *c)
1124 if (getn(varval(STRhistory)) == 0)
1126 while (*++vp && **vp == '-') {
1153 stderror(ERR_HISTUS, "chrSLMT");
1157 if (hflg & HIST_CLEAR) {
1158 struct Hist *np, *hp;
1159 for (hp = &Histlist; (np = hp->Hnext) != NULL;)
1160 hremove(np), hfree(np);
1163 if (hflg & (HIST_LOAD | HIST_MERGE))
1164 loadhist(*vp, (hflg & HIST_MERGE) ? 1 : 0);
1165 else if (hflg & HIST_SAVE)
1171 n = getn(varval(STRhistory));
1179 fmthist(int fmt, ptr_t ptr)
1181 struct Hist *hp = ptr;
1186 return xasprintf("%6d", hp->Hnum);
1188 if (HistLit && hp->histline)
1189 return xasprintf("%S", hp->histline);
1194 istr = sprlex(&hp->Hlex);
1195 buf = xmalloc(Strlen(istr) * MB_LEN_MAX + 1);
1197 for (p = buf, ip = istr; *ip != '\0'; ip++)
1198 p += one_wctomb(p, *ip);
1212 dotlock_cleanup(void* lockpath)
1214 dot_unlock((char*)lockpath);
1217 /* Save history before exiting the shell. */
1219 rechist(Char *fname, int ref)
1222 int fp, ftmp, oldidfds;
1223 struct varent *shist;
1224 char path[MAXPATHLEN];
1226 static Char *dumphist[] = {STRhistory, STRmhT, 0, 0};
1228 if (fname == NULL && !ref)
1231 * If $savehist is just set, we use the value of $history
1232 * else we use the value in $savehist
1234 if (((snum = varval(STRsavehist)) == STRNULL) &&
1235 ((snum = varval(STRhistory)) == STRNULL))
1239 if (fname == NULL) {
1240 if ((fname = varval(STRhistfile)) == STRNULL)
1241 fname = Strspl(varval(STRhome), &STRtildothist[1]);
1243 fname = Strsave(fname);
1246 fname = globone(fname, G_ERROR);
1247 cleanup_push(fname, xfree);
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.
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.
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)
1272 if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL) {
1274 int merge = 0, lock = 0;
1276 for (i = 1; shist->vec[i]; i++) {
1277 if (eq(shist->vec[i], STRmerge))
1279 if (eq(shist->vec[i], STRlock))
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);
1301 xsnprintf(path, sizeof(path), "%S.%S", fname, rs);
1304 fp = xcreat(path, 0600);
1307 cleanup_until(fname);
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));
1317 UNREFERENCED_PARAMETER(st);
1322 dohist(dumphist, NULL);
1326 #ifndef WINNT_NATIVE
1327 (void)rename(path, short2str(fname));
1329 (void)ReplaceFile( short2str(fname),path,NULL,0,NULL,NULL);
1331 cleanup_until(fname);
1335 /* This is the entry point for loading history data from a file. */
1337 loadhist(Char *fname, int mflg)
1339 static Char *loadhist_cmd[] = {STRsource, NULL, NULL, NULL};
1340 loadhist_cmd[1] = mflg ? STRmm : STRmh;
1343 loadhist_cmd[2] = fname;
1344 else if ((fname = varval(STRhistfile)) != STRNULL)
1345 loadhist_cmd[2] = fname;
1347 loadhist_cmd[2] = STRtildothist;
1349 dosource(loadhist_cmd, NULL);
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. */
1356 struct Hist *hp = &Histlist;
1357 while ((hp = hp->Hnext))
1358 hp->Hnum = hp->Href = n--;
1366 discardExcess(histlen);