159243Sobrien/* 259243Sobrien * sh.hist.c: Shell history expansions and substitutions 359243Sobrien */ 459243Sobrien/*- 559243Sobrien * Copyright (c) 1980, 1991 The Regents of the University of California. 659243Sobrien * All rights reserved. 759243Sobrien * 859243Sobrien * Redistribution and use in source and binary forms, with or without 959243Sobrien * modification, are permitted provided that the following conditions 1059243Sobrien * are met: 1159243Sobrien * 1. Redistributions of source code must retain the above copyright 1259243Sobrien * notice, this list of conditions and the following disclaimer. 1359243Sobrien * 2. Redistributions in binary form must reproduce the above copyright 1459243Sobrien * notice, this list of conditions and the following disclaimer in the 1559243Sobrien * documentation and/or other materials provided with the distribution. 16100616Smp * 3. Neither the name of the University nor the names of its contributors 1759243Sobrien * may be used to endorse or promote products derived from this software 1859243Sobrien * without specific prior written permission. 1959243Sobrien * 2059243Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2159243Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2259243Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2359243Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2459243Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2559243Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2659243Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2759243Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2859243Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2959243Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3059243Sobrien * SUCH DAMAGE. 3159243Sobrien */ 3259243Sobrien#include "sh.h" 33316957Sdchagin#include <stdio.h> /* for rename(2), grr. */ 34231990Smp#include <assert.h> 3559243Sobrien#include "tc.h" 36316957Sdchagin#include "dotlock.h" 3759243Sobrien 38145479Smpextern int histvalid; 39167465Smpextern struct Strbuf histline; 4059243SobrienChar HistLit = 0; 4159243Sobrien 42167465Smpstatic int heq (const struct wordent *, const struct wordent *); 43167465Smpstatic void hfree (struct Hist *); 4459243Sobrien 4559243Sobrien#define HIST_ONLY 0x01 4659243Sobrien#define HIST_SAVE 0x02 4759243Sobrien#define HIST_LOAD 0x04 4859243Sobrien#define HIST_REV 0x08 4959243Sobrien#define HIST_CLEAR 0x10 5059243Sobrien#define HIST_MERGE 0x20 5159243Sobrien#define HIST_TIME 0x40 5259243Sobrien 5359243Sobrien/* 5459243Sobrien * C shell 5559243Sobrien */ 5659243Sobrien 57231990Smp/* Static functions don't show up in gprof summaries. So eliminate "static" 58231990Smp * modifier from some frequently called functions. */ 59231990Smp#ifdef PROF 60231990Smp#define PG_STATIC 61231990Smp#else 62231990Smp#define PG_STATIC static 63231990Smp#endif 64231990Smp 65231990Smp/* #define DEBUG_HIST 1 */ 66231990Smp 67231990Smpstatic const int fastMergeErase = 1; 68231990Smpstatic unsigned histCount = 0; /* number elements on history list */ 69316957Sdchaginstatic int histlen = 0; 70231990Smpstatic struct Hist *histTail = NULL; /* last element on history list */ 71231990Smpstatic struct Hist *histMerg = NULL; /* last element merged by Htime */ 72231990Smp 73231990Smpstatic void insertHistHashTable(struct Hist *, unsigned); 74231990Smp 75231990Smp/* Insert new element (hp) in history list after specified predecessor (pp). */ 76231990Smpstatic void 77231990Smphinsert(struct Hist *hp, struct Hist *pp) 78231990Smp{ 79231990Smp struct Hist *fp = pp->Hnext; /* following element, if any */ 80231990Smp hp->Hnext = fp, hp->Hprev = pp; 81231990Smp pp->Hnext = hp; 82231990Smp if (fp) 83231990Smp fp->Hprev = hp; 84231990Smp else 85231990Smp histTail = hp; /* meaning hp->Hnext == NULL */ 86231990Smp histCount++; 87231990Smp} 88231990Smp 89231990Smp/* Remove the entry from the history list. */ 90231990Smpstatic void 91231990Smphremove(struct Hist *hp) 92231990Smp{ 93231990Smp struct Hist *pp = hp->Hprev; 94231990Smp assert(pp); /* elements always have a previous */ 95231990Smp pp->Hnext = hp->Hnext; 96231990Smp if (hp->Hnext) 97231990Smp hp->Hnext->Hprev = pp; 98231990Smp else 99231990Smp histTail = pp; /* we must have been last */ 100231990Smp if (hp == histMerg) /* deleting this hint from list */ 101231990Smp histMerg = NULL; 102231990Smp assert(histCount > 0); 103231990Smp histCount--; 104231990Smp} 105231990Smp 106231990Smp/* Prune length of history list to specified size by history variable. */ 107231990SmpPG_STATIC void 108316957SdchagindiscardExcess(int hlen) 109231990Smp{ 110231990Smp struct Hist *hp, *np; 111231990Smp if (histTail == NULL) { 112231990Smp assert(histCount == 0); 113231990Smp return; /* no entries on history list */ 114231990Smp } 115231990Smp /* Prune dummy entries from the front, then old entries from the back. If 116231990Smp * the list is still too long scan the whole list as before. But only do a 117231990Smp * full scan if the list is more than 6% (1/16th) too long. */ 118316957Sdchagin while (histCount > (unsigned)hlen && (np = Histlist.Hnext)) { 119316957Sdchagin if (eventno - np->Href >= hlen || hlen == 0) 120231990Smp hremove(np), hfree(np); 121231990Smp else 122231990Smp break; 123231990Smp } 124316957Sdchagin while (histCount > (unsigned)hlen && (np = histTail) != &Histlist) { 125316957Sdchagin if (eventno - np->Href >= hlen || hlen == 0) 126231990Smp hremove(np), hfree(np); 127231990Smp else 128231990Smp break; 129231990Smp } 130316957Sdchagin if (histCount - (hlen >> 4) <= (unsigned)hlen) 131231990Smp return; /* don't bother doing the full scan */ 132316957Sdchagin for (hp = &Histlist; histCount > (unsigned)hlen && 133231990Smp (np = hp->Hnext) != NULL;) 134316957Sdchagin if (eventno - np->Href >= hlen || hlen == 0) 135231990Smp hremove(np), hfree(np); 136231990Smp else 137231990Smp hp = np; 138231990Smp} 139231990Smp 140231990Smp/* Add the command "sp" to the history list. */ 14159243Sobrienvoid 142231990Smpsavehist( 143231990Smp struct wordent *sp, 144231990Smp int mflg) /* true if -m (merge) specified */ 14559243Sobrien{ 14659243Sobrien /* throw away null lines */ 14759243Sobrien if (sp && sp->next->word[0] == '\n') 14859243Sobrien return; 14959243Sobrien if (sp) 150231990Smp (void) enthist(++eventno, sp, 1, mflg, histlen); 151231990Smp discardExcess(histlen); 15259243Sobrien} 15359243Sobrien 154231990Smp#define USE_JENKINS_HASH 1 155231990Smp/* #define USE_ONE_AT_A_TIME 1 */ 156231990Smp#undef PRIME_LENGTH /* no need for good HTL */ 157231990Smp 158231990Smp#ifdef USE_JENKINS_HASH 159231990Smp#define hashFcnName "lookup3" 160231990Smp/* From: 161231990Smp lookup3.c, by Bob Jenkins, May 2006, Public Domain. 162231990Smp "... You can use this free for any purpose. It's in 163231990Smp the public domain. It has no warranty." 164231990Smp http://burtleburtle.net/bob/hash/index.html 165231990Smp */ 166231990Smp 167231990Smp#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 168231990Smp#define mix(a,b,c) \ 169231990Smp{ \ 170231990Smp a -= c; a ^= rot(c, 4); c += b; \ 171231990Smp b -= a; b ^= rot(a, 6); a += c; \ 172231990Smp c -= b; c ^= rot(b, 8); b += a; \ 173231990Smp a -= c; a ^= rot(c,16); c += b; \ 174231990Smp b -= a; b ^= rot(a,19); a += c; \ 175231990Smp c -= b; c ^= rot(b, 4); b += a; \ 176231990Smp} 177231990Smp#define final(a,b,c) \ 178231990Smp{ \ 179231990Smp c ^= b; c -= rot(b,14); \ 180231990Smp a ^= c; a -= rot(c,11); \ 181231990Smp b ^= a; b -= rot(a,25); \ 182231990Smp c ^= b; c -= rot(b,16); \ 183231990Smp a ^= c; a -= rot(c, 4); \ 184231990Smp b ^= a; b -= rot(a,14); \ 185231990Smp c ^= b; c -= rot(b,24); \ 186231990Smp} 187231990Smp 188231990Smpstruct hashValue /* State used to hash a wordend word list. */ 189231990Smp{ 190231990Smp uint32_t a, b, c; 191231990Smp}; 192231990Smp 193231990Smp/* Set up the internal state */ 194231990Smpstatic void 195231990SmpinitializeHash(struct hashValue *h) 196231990Smp{ 197231990Smp h->a = h->b = h->c = 0xdeadbeef; 198231990Smp} 199231990Smp 200231990Smp/* This does a partial hash of the Chars in a single word. For efficiency we 201231990Smp * include 3 versions of the code to pack Chars into 32-bit words for the 202231990Smp * mixing function. */ 203231990Smpstatic void 204231990SmpaddWordToHash(struct hashValue *h, const Char *word) 205231990Smp{ 206231990Smp uint32_t a = h->a, b = h->b, c = h->c; 207231990Smp#ifdef SHORT_STRINGS 208231990Smp#ifdef WIDE_STRINGS 209231990Smp assert(sizeof(Char) >= 4); 210231990Smp while (1) { 211231990Smp unsigned k; 212231990Smp if ((k = (uChar)*word++) == 0) break; a += k; 213231990Smp if ((k = (uChar)*word++) == 0) break; b += k; 214231990Smp if ((k = (uChar)*word++) == 0) break; c += k; 215231990Smp mix(a, b, c); 216231990Smp } 217231990Smp#else 218231990Smp assert(sizeof(Char) == 2); 219231990Smp while (1) { 220231990Smp unsigned k; 221231990Smp if ((k = (uChar)*word++) == 0) break; a += k; 222231990Smp if ((k = (uChar)*word++) == 0) break; a += k << 16; 223231990Smp if ((k = (uChar)*word++) == 0) break; b += k; 224231990Smp if ((k = (uChar)*word++) == 0) break; b += k << 16; 225231990Smp if ((k = (uChar)*word++) == 0) break; c += k; 226231990Smp if ((k = (uChar)*word++) == 0) break; c += k << 16; 227231990Smp mix(a, b, c); 228231990Smp } 229231990Smp#endif 230231990Smp#else 231231990Smp assert(sizeof(Char) == 1); 232231990Smp while (1) { 233231990Smp unsigned k; 234231990Smp if ((k = *word++) == 0) break; a += k; 235231990Smp if ((k = *word++) == 0) break; a += k << 8; 236231990Smp if ((k = *word++) == 0) break; a += k << 16; 237231990Smp if ((k = *word++) == 0) break; a += k << 24; 238231990Smp if ((k = *word++) == 0) break; b += k; 239231990Smp if ((k = *word++) == 0) break; b += k << 8; 240231990Smp if ((k = *word++) == 0) break; b += k << 16; 241231990Smp if ((k = *word++) == 0) break; b += k << 24; 242231990Smp if ((k = *word++) == 0) break; c += k; 243231990Smp if ((k = *word++) == 0) break; c += k << 8; 244231990Smp if ((k = *word++) == 0) break; c += k << 16; 245231990Smp if ((k = *word++) == 0) break; c += k << 24; 246231990Smp mix(a, b, c); 247231990Smp } 248231990Smp#endif 249231990Smp h->a = a, h->b = b, h->c = c; 250231990Smp} 251231990Smp 252231990Smpstatic void 253231990SmpaddCharToHash(struct hashValue *h, Char ch) 254231990Smp{ 255231990Smp /* The compiler (gcc -O2) seems to do a good job optimizing this without 256231990Smp * explicitly extracting into local variables. */ 257231990Smp h->a += (uChar)ch; 258231990Smp mix(h->a, h->b, h->c); 259231990Smp} 260231990Smp 261231990Smpstatic uint32_t 262231990SmpfinalizeHash(struct hashValue *h) 263231990Smp{ 264231990Smp uint32_t a = h->a, b = h->b, c = h->c; 265231990Smp final(a, b, c); 266231990Smp return c; 267231990Smp} 268231990Smp 269231990Smp#elif USE_ONE_AT_A_TIME 270231990Smp#define hashFcnName "one-at-a-time" 271231990Smp/* This one is also from Bob Jenkins, but is slower but simpler than lookup3. 272231990Smp "... The code given here are all public domain." 273231990Smp http://burtleburtle.net/bob/hash/doobs.html */ 274231990Smp 275231990Smp#if 0 276231990Smpub4 277231990Smpone_at_a_time(char *key, ub4 len) 278231990Smp{ 279231990Smp ub4 hash, i; 280231990Smp for (hash=0, i=0; i<len; ++i) 281231990Smp { 282231990Smp hash += key[i]; 283231990Smp hash += (hash << 10); 284231990Smp hash ^= (hash >> 6); 285231990Smp } 286231990Smp hash += (hash << 3); 287231990Smp hash ^= (hash >> 11); 288231990Smp hash += (hash << 15); 289231990Smp return (hash & mask); 290231990Smp} 291231990Smp#endif 292231990Smp 293231990Smpstruct hashValue { uint32_t h; }; 294231990Smpstatic void 295231990SmpinitializeHash(struct hashValue *h) 296231990Smp{ 297231990Smp h->h = 0; 298231990Smp} 299231990Smp 300231990Smpstatic void 301231990SmpaddWordToHash(struct hashValue *h, const Char *word) 302231990Smp{ 303231990Smp unsigned k; 304231990Smp uint32_t hash = h->h; 305231990Smp while (k = (uChar)*word++) 306231990Smp hash += k, hash += hash << 10, hash ^= hash >> 6; 307231990Smp h->h = hash; 308231990Smp} 309231990Smp 310231990Smpstatic void 311231990SmpaddCharToHash(struct hashValue *h, Char c) 312231990Smp{ 313231990Smp Char b[2] = { c, 0 }; 314231990Smp addWordToHash(h, b); 315231990Smp} 316231990Smp 317231990Smpstatic uint32_t 318231990SmpfinalizeHash(struct hashValue *h) 319231990Smp{ 320231990Smp unsigned hash = h->h; 321231990Smp hash += (hash << 3); 322231990Smp hash ^= (hash >> 11); 323231990Smp hash += (hash << 15); 324231990Smp return hash; 325231990Smp} 326231990Smp 327231990Smp#else 328231990Smp#define hashFcnName "add-mul" 329231990Smp/* Simple multipy and add hash. */ 330231990Smp#define PRIME_LENGTH 1 /* need "good" HTL */ 331231990Smpstruct hashValue { uint32_t h; }; 332231990Smpstatic void 333231990SmpinitializeHash(struct hashValue *h) 334231990Smp{ 335231990Smp h->h = 0xe13e2345; 336231990Smp} 337231990Smp 338231990Smpstatic void 339231990SmpaddWordToHash(struct hashValue *h, const Char *word) 340231990Smp{ 341231990Smp unsigned k; 342231990Smp uint32_t hash = h->h; 343231990Smp while (k = (uChar)*word++) 344231990Smp hash = hash * 0x9e4167b9 + k; 345231990Smp h->h = hash; 346231990Smp} 347231990Smp 348231990Smpstatic void 349231990SmpaddCharToHash(struct hashValue *h, Char c) 350231990Smp{ 351231990Smp h->h = h->h * 0x9e4167b9 + (uChar)c; 352231990Smp} 353231990Smp 354231990Smpstatic uint32_t 355231990SmpfinalizeHash(struct hashValue *h) 356231990Smp{ 357231990Smp return h->h; 358231990Smp} 359231990Smp#endif 360231990Smp 361231990Smpstatic unsigned 362231990Smphashhist(struct wordent *h0) 363231990Smp{ 364231990Smp struct hashValue s; 365231990Smp struct wordent *firstWord = h0->next; 366231990Smp struct wordent *h = firstWord; 367231990Smp unsigned hash = 0; 368231990Smp 369231990Smp initializeHash(&s); 370231990Smp for (; h != h0; h = h->next) { 371231990Smp if (h->word[0] == '\n') 372231990Smp break; /* don't hash newline */ 373231990Smp if (h != firstWord) 374231990Smp addCharToHash(&s, ' '); /* space between words */ 375231990Smp addWordToHash(&s, h->word); 376231990Smp } 377231990Smp hash = finalizeHash(&s); 378231990Smp /* Zero means no hash value, so never return zero as a hash value. */ 379231990Smp return hash ? hash : 0x7fffffff; /* prime! */ 380231990Smp} 381231990Smp 382231990Smp#if 0 383231990Smpunsigned 384231990SmphashStr(Char *str) 385231990Smp{ 386231990Smp struct hashValue s; 387231990Smp initializeHash(&s); 388231990Smp addWordToHash(&s, str); 389231990Smp return finalizeHash(&s); 390231990Smp} 391231990Smp#endif 392231990Smp 393231990Smp#ifdef PRIME_LENGTH /* need good HTL */ 394231990Smp#define hash2tableIndex(hash, len) ((hash) % len) 395231990Smp#else 396231990Smp#define hash2tableIndex(hash, len) ((hash) & (len-1)) 397231990Smp#endif 398231990Smp 399231990Smp/* This code can be enabled to test the above hash functions for speed and 400231990Smp * collision avoidance. The testing is enabled by "occasional" calls to 401231990Smp * displayHistStats(), see which. */ 402231990Smp#ifdef DEBUG_HIST 403231990Smp 404231990Smp#ifdef BSDTIMES 405231990Smpstatic double 406231990SmpdoTiming(int start) { 407231990Smp static struct timeval beginTime; 408231990Smp if (start) { 409231990Smp gettimeofday(&beginTime, NULL); 410231990Smp return 0.0; 411231990Smp } else { 412231990Smp struct timeval now; 413231990Smp gettimeofday(&now, NULL); 414231990Smp return (now.tv_sec-beginTime.tv_sec) + 415231990Smp (now.tv_usec-beginTime.tv_usec)/1e6; 416231990Smp } 417231990Smp} 418231990Smp#else 419231990Smpstatic double 420231990SmpdoTiming(int start) { 421231990Smp USE(start); 422231990Smp return 0.0; 423231990Smp} 424231990Smp#endif 425231990Smp 426231990Smpstatic void 427231990SmpgenerateHashes(int nChars, unsigned nWords, unsigned samples, unsigned *hashes, 428231990Smp unsigned length) 429231990Smp{ 430231990Smp if (nChars < 1) 431231990Smp return; 432231990Smp nWords = (nWords < 1) ? 1 : (nWords > 4) ? 4 : nWords; 433231990Smp Char *number = xmalloc((nChars+nWords)*sizeof(Char)); 434231990Smp struct wordent word[4]; 435231990Smp struct wordent base = { NULL, &word[0], &word[0] }; 436231990Smp word[0].word = number, word[0].next = &base, word[0].prev = &base; 437231990Smp unsigned w = 0; /* word number */ 438231990Smp /* Generate multiple words of length 2, 3, 5, then all the rest. */ 439231990Smp unsigned wBoundaries[4] = { 2-1, 2+3-1, 2+3+5-1, 0 }; 440231990Smp /* Ensure the last word has at least 4 Chars in it. */ 441231990Smp while (nWords >= 2 && nChars < (wBoundaries[nWords-2]+1) + 4) 442231990Smp nWords--; 443231990Smp wBoundaries[nWords-1] = 0xffffffff; /* don't end word past this point */ 444231990Smp unsigned i; 445231990Smp for (i = 0; i<nChars; i++) { 446231990Smp /* In deference to the gawd awful add-mul hash, we won't use the worse 447231990Smp * case here (setting all Chars to 1), but assume mostly (or at least 448231990Smp * initially) ASCII data. */ 449231990Smp number[i+w] = '!'; /* 0x21 = 33 */ 450231990Smp 451231990Smp if (i == wBoundaries[w]) { /* end a word here and move to next */ 452231990Smp w++; /* next word */ 453231990Smp number[i+w] = 0; /* terminate */ 454231990Smp word[w].word = &number[i+w+1]; 455231990Smp word[w].next = &base, word[w].prev = &word[w-1]; 456231990Smp word[w-1].next = &word[w], base.prev = &word[w]; 457231990Smp } 458231990Smp } 459231990Smp /* w is the index of the last word actually created. */ 460231990Smp number[nChars + w] = 0; /* terminate last word */ 461231990Smp unsigned timeLimit = !samples; 462231990Smp if (samples == 0) 463231990Smp samples = 1000000000; 464231990Smp doTiming(1); 465231990Smp double sec; 466231990Smp for (i = 0; i < samples; i++) { 467231990Smp /* increment 4 digit base 255 number; last characters vary fastest */ 468231990Smp unsigned j = nChars-1 + w; 469231990Smp while (1) { 470231990Smp if (++number[j] != 0) 471231990Smp break; 472231990Smp /* else reset this digit and proceed to next one */ 473231990Smp number[j] = 1; 474231990Smp if (&number[j] <= word[w].word) 475231990Smp break; /* stop at beginning of last word */ 476231990Smp j--; 477231990Smp } 478231990Smp if (word[w].word[0] == '\n') 479231990Smp word[w].word[0]++; /* suppress newline character */ 480231990Smp unsigned hash = hashhist(&base); 481231990Smp hashes[hash2tableIndex(hash, length)]++; 482231990Smp if (timeLimit && (i & 0x3ffff) == 0x3ffff) { 483231990Smp sec = doTiming(0); 484231990Smp if (sec > 10) 485231990Smp break; 486231990Smp } 487231990Smp } 488231990Smp if (i >= samples) 489231990Smp sec = doTiming(0); 490231990Smp else 491231990Smp samples = i; /* number we actually did */ 492231990Smp if (sec > 0.01) { 493231990Smp xprintf("Hash %d (%d Char %u words) with %s: %d nsec/hash, %d mcps\n", 494231990Smp samples, nChars, w+1, hashFcnName, (int)((sec/samples)*1e9), 495231990Smp (int)((double)samples*nChars/sec/1e6)); 496231990Smp } 497231990Smp} 498231990Smp#endif /* DEBUG_HIST */ 499231990Smp 500231990Smp#ifdef DEBUG_HIST 501231990Smpstatic void 502231990SmptestHash(void) 503231990Smp{ 504231990Smp static const Char STRtestHashTimings[] = 505231990Smp { 't','e','s','t','H','a','s','h','T','i','m','i','n','g','s', 0 }; 506231990Smp struct varent *vp = adrof(STRtestHashTimings); 507231990Smp if (vp && vp->vec) { 508231990Smp unsigned hashes[4]; /* dummy place to put hashes */ 509231990Smp Char **vals = vp->vec; 510231990Smp while (*vals) { 511231990Smp int length = getn(*vals); 512231990Smp unsigned words = 513231990Smp (length < 5) ? 1 : (length < 25) ? 2 : (length < 75) ? 3 : 4; 514231990Smp if (length > 0) 515231990Smp generateHashes(length, words, 0, hashes, 4); 516231990Smp vals++; 517231990Smp } 518231990Smp } 519231990Smp unsigned length = 1024; 520231990Smp#ifdef PRIME_LENGTH /* need good HTL */ 521231990Smp length = 1021; 522231990Smp#endif 523231990Smp unsigned *hashes = xmalloc(length*sizeof(unsigned)); 524231990Smp memset(hashes, 0, length*sizeof(unsigned)); 525231990Smp /* Compute collision statistics for half full hashes modulo "length". */ 526231990Smp generateHashes(4, 1, length/2, hashes, length); 527231990Smp /* Evaluate collisions by comparing occupancy rates (mean value 0.5). 528231990Smp * One bin for each number of hits. */ 529231990Smp unsigned bins[155]; 530231990Smp memset(bins, 0, sizeof(bins)); 531231990Smp unsigned highest = 0; 532231990Smp unsigned i; 533231990Smp for (i = 0; i<length; i++) { 534231990Smp unsigned hits = hashes[i]; 535231990Smp if (hits >= sizeof(bins)/sizeof(bins[0])) /* clip */ 536231990Smp hits = highest = sizeof(bins)/sizeof(bins[0]) - 1; 537231990Smp if (hits > highest) 538231990Smp highest = hits; 539231990Smp bins[hits]++; 540231990Smp } 541231990Smp xprintf("Occupancy of %d buckets by %d hashes %d Chars %d word with %s\n", 542231990Smp length, length/2, 4, 1, hashFcnName); 543231990Smp for (i = 0; i <= highest; i++) { 544231990Smp xprintf(" %d buckets (%d%%) with %d hits\n", 545231990Smp bins[i], bins[i]*100/length, i); 546231990Smp } 547231990Smp /* Count run lengths to evaluate linear rehashing effectiveness. Estimate 548231990Smp * a little corrupted by edge effects. */ 549231990Smp memset(bins, 0, sizeof(bins)); 550231990Smp highest = 0; 551231990Smp for (i = 0; hashes[i] == 0; i++); /* find first occupied bucket */ 552231990Smp unsigned run = 0; 553231990Smp unsigned rehashed = 0; 554231990Smp for (; i<length; i++) { 555231990Smp unsigned hits = hashes[i]; 556231990Smp if (hits == 0 && rehashed > 0) 557231990Smp hits = 1 && rehashed--; 558231990Smp else if (hits > 1) 559231990Smp rehashed += hits-1; 560231990Smp if (hits) 561231990Smp run++; 562231990Smp else { 563231990Smp /* a real free slot, count it */ 564231990Smp if (run >= sizeof(bins)/sizeof(bins[0])) /* clip */ 565231990Smp run = highest = sizeof(bins)/sizeof(bins[0]) - 1; 566231990Smp if (run > highest) 567231990Smp highest = run; 568231990Smp bins[run]++; 569231990Smp run = 0; 570231990Smp } 571231990Smp } 572231990Smp /* Ignore the partial run at end as we ignored the beginning. */ 573231990Smp double merit = 0.0, entries = 0; 574231990Smp for (i = 0; i <= highest; i++) { 575231990Smp entries += bins[i]*i; /* total hashed objects */ 576231990Smp merit += bins[i]*i*i; 577231990Smp } 578231990Smp xprintf("Rehash collision figure of merit %u (ideal=100), run lengths:\n", 579231990Smp (int)(100.0*merit/entries)); 580231990Smp for (i = 0; i <= highest; i++) { 581231990Smp if (bins[i] != 0) 582231990Smp xprintf(" %d runs of length %d buckets\n", bins[i], i); 583231990Smp } 584231990Smp xfree(hashes); 585231990Smp} 586231990Smp#endif /* DEBUG_HIST */ 587231990Smp 588231990Smp/* Compares two word lists for equality. */ 589145479Smpstatic int 590167465Smpheq(const struct wordent *a0, const struct wordent *b0) 59159243Sobrien{ 592167465Smp const struct wordent *a = a0->next, *b = b0->next; 59359243Sobrien 59459243Sobrien for (;;) { 59559243Sobrien if (Strcmp(a->word, b->word) != 0) 59659243Sobrien return 0; 59759243Sobrien a = a->next; 59859243Sobrien b = b->next; 59959243Sobrien if (a == a0) 60059243Sobrien return (b == b0) ? 1 : 0; 60159243Sobrien if (b == b0) 60259243Sobrien return 0; 603231990Smp } 60459243Sobrien} 60559243Sobrien 606231990Smp/* Renumber entries following p, which we will be deleting. */ 607231990SmpPG_STATIC void 608231990SmprenumberHist(struct Hist *p) 609231990Smp{ 610231990Smp int n = p->Href; 611231990Smp while ((p = p->Hnext)) 612231990Smp p->Href = n--; 613231990Smp} 61459243Sobrien 615231990Smp/* The hash table is implemented as an array of pointers to Hist entries. Each 616231990Smp * entry is located in the table using hash2tableIndex() and checking the 617231990Smp * following entries in case of a collision (linear rehash). Free entries in 618231990Smp * the table are zero (0, NULL, emptyHTE). Deleted entries that cannot yet be 619231990Smp * freed are set to one (deletedHTE). The Hist.Hhash member is non-zero iff 620231990Smp * the entry is in the hash table. When the hash table get too full, it is 621231990Smp * reallocated to be approximately twice the history length (see 622231990Smp * getHashTableSize). */ 623231990Smpstatic struct Hist **histHashTable = NULL; 624231990Smpstatic unsigned histHashTableLength = 0; /* number of Hist pointers in table */ 625231990Smp 626231990Smpstatic struct Hist * const emptyHTE = NULL; 627231990Smpstatic struct Hist * const deletedHTE = (struct Hist *)1; 628231990Smp 629231990Smpstatic struct { 630231990Smp unsigned insertCount; 631231990Smp unsigned removeCount; 632231990Smp unsigned rehashes; 633231990Smp int deleted; 634231990Smp} hashStats; 635231990Smp 636231990Smp#ifdef DEBUG_HIST 637231990Smpvoid 638231990SmpcheckHistHashTable(int print) 639231990Smp{ 640231990Smp unsigned occupied = 0; 641231990Smp unsigned deleted = 0; 642231990Smp unsigned i; 643231990Smp for (i = 0; i<histHashTableLength; i++) 644231990Smp if (histHashTable[i] == emptyHTE) 645231990Smp continue; 646231990Smp else if (histHashTable[i] == deletedHTE) 647231990Smp deleted++; 648231990Smp else 649231990Smp occupied++; 650231990Smp if (print) 651231990Smp xprintf(" found len %u occupied %u deleted %u\n", 652231990Smp histHashTableLength, occupied, deleted); 653231990Smp assert(deleted == hashStats.deleted); 654231990Smp} 655231990Smp 656231990Smpstatic int doneTest = 0; 657231990Smp 658231990Smp/* Main entry point for displaying history statistics and hash function 659231990Smp * behavior. */ 660231990Smpvoid 661231990SmpdisplayHistStats(const char *reason) 662231990Smp{ 663231990Smp /* Just hash statistics for now. */ 664231990Smp xprintf("%s history hash table len %u count %u (deleted %d)\n", reason, 665231990Smp histHashTableLength, histCount, hashStats.deleted); 666231990Smp xprintf(" inserts %u rehashes %u%% each\n", 667231990Smp hashStats.insertCount, 668231990Smp (hashStats.insertCount 669231990Smp ? 100*hashStats.rehashes/hashStats.insertCount : 0)); 670231990Smp xprintf(" removes %u net %u\n", 671231990Smp hashStats.removeCount, 672231990Smp hashStats.insertCount - hashStats.removeCount); 673231990Smp assert(hashStats.insertCount >= hashStats.removeCount); 674231990Smp checkHistHashTable(1); 675231990Smp memset(&hashStats, 0, sizeof(hashStats)); 676231990Smp if (!doneTest) { 677231990Smp testHash(); 678231990Smp doneTest = 1; 679231990Smp } 680231990Smp} 681231990Smp#else 682231990Smpvoid 683231990SmpdisplayHistStats(const char *reason) 684231990Smp{ 685231990Smp USE(reason); 686231990Smp} 687231990Smp#endif 688231990Smp 689231990Smpstatic void 690231990SmpdiscardHistHashTable(void) 691231990Smp{ 692231990Smp if (histHashTable == NULL) 693231990Smp return; 694231990Smp displayHistStats("Discarding"); 695231990Smp xfree(histHashTable); 696231990Smp histHashTable = NULL; 697231990Smp} 698231990Smp 699231990Smp/* Computes a new hash table size, when the current one is too small. */ 700231990Smpstatic unsigned 701316957SdchagingetHashTableSize(int hlen) 702231990Smp{ 703316957Sdchagin unsigned target = hlen * 2; 704231990Smp unsigned e = 5; 705231990Smp unsigned size; 706231990Smp while ((size = 1<<e) < target) 707231990Smp e++; 708231990Smp#ifdef PRIME_LENGTH /* need good HTL */ 709231990Smp /* Not all prime, but most are and none have factors smaller than 11. */ 710231990Smp return size+15; 711231990Smp#else 712231990Smp assert((size & (size-1)) == 0); /* must be a power of two */ 713231990Smp return size; 714231990Smp#endif 715231990Smp} 716231990Smp 717231990Smp/* Create the hash table or resize, if necessary. */ 718231990Smpstatic void 719316957SdchagincreateHistHashTable(int hlen) 720231990Smp{ 721316957Sdchagin if (hlen == 0) { 722231990Smp discardHistHashTable(); 723231990Smp return; 724231990Smp } 725316957Sdchagin if (hlen < 0) { 726316957Sdchagin if (histlen <= 0) 727231990Smp return; /* no need for hash table */ 728316957Sdchagin hlen = histlen; 729231990Smp } 730231990Smp if (histHashTable != NULL) { 731231990Smp if (histCount < histHashTableLength * 3 / 4) 732231990Smp return; /* good enough for now */ 733231990Smp discardHistHashTable(); /* too small */ 734231990Smp } 735231990Smp histHashTableLength = getHashTableSize( 736316957Sdchagin hlen > (int)histCount ? hlen : (int)histCount); 737231990Smp histHashTable = xmalloc(histHashTableLength * sizeof(struct Hist *)); 738231990Smp memset(histHashTable, 0, histHashTableLength * sizeof(struct Hist *)); 739231990Smp assert(histHashTable[0] == emptyHTE); 740231990Smp 741231990Smp /* Now insert all the entries on the history list into the hash table. */ 742231990Smp { 743231990Smp struct Hist *hp; 744231990Smp for (hp = &Histlist; (hp = hp->Hnext) != NULL;) { 745231990Smp unsigned lpHash = hashhist(&hp->Hlex); 746231990Smp assert(!hp->Hhash || hp->Hhash == lpHash); 747231990Smp hp->Hhash = 0; /* force insert to new hash table */ 748231990Smp insertHistHashTable(hp, lpHash); 749231990Smp } 750231990Smp } 751231990Smp} 752231990Smp 753231990Smp/* Insert np into the hash table. We assume that np is already on the 754231990Smp * Histlist. The specified hashval matches the new Hist entry but has not yet 755231990Smp * been assigned to Hhash (or the element is already on the hash table). */ 756231990Smpstatic void 757231990SmpinsertHistHashTable(struct Hist *np, unsigned hashval) 758231990Smp{ 759231990Smp unsigned rehashes = 0; 760231990Smp unsigned hi = 0; 761231990Smp if (!histHashTable) 762231990Smp return; 763231990Smp if (np->Hhash != 0) { 764231990Smp /* already in hash table */ 765231990Smp assert(hashval == np->Hhash); 766231990Smp return; 767231990Smp } 768231990Smp assert(np != deletedHTE); 769231990Smp /* Find a free (empty or deleted) slot, using linear rehash. */ 770231990Smp assert(histHashTable); 771231990Smp for (rehashes = 0; 772231990Smp ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)), 773231990Smp histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE); 774231990Smp rehashes++) { 775231990Smp assert(np != histHashTable[hi]); 776231990Smp if (rehashes >= histHashTableLength / 10) { 777231990Smp /* Hash table is full, so grow it. We assume the create function 778231990Smp * will roughly double the size we give it. Create initializes the 779231990Smp * new table with everything on the Histlist, so we are done when 780231990Smp * it returns. */ 781231990Smp#ifdef DEBUG_HIST 782231990Smp xprintf("Growing history hash table from %d ...", 783231990Smp histHashTableLength); 784231990Smp flush(); 785231990Smp#endif 786231990Smp discardHistHashTable(); 787231990Smp createHistHashTable(histHashTableLength); 788231990Smp#ifdef DEBUG_HIST 789231990Smp xprintf("to %d.\n", histHashTableLength); 790231990Smp#endif 791231990Smp return; 792231990Smp } 793231990Smp } 794231990Smp /* Might be sensible to grow hash table if rehashes is "too big" here. */ 795231990Smp if (histHashTable[hi] == deletedHTE) 796231990Smp hashStats.deleted--; 797231990Smp histHashTable[hi] = np; 798231990Smp np->Hhash = hashval; 799231990Smp hashStats.insertCount++; 800231990Smp hashStats.rehashes += rehashes; 801231990Smp} 802231990Smp 803231990Smp/* Remove the 'np' entry from the hash table. */ 804231990Smpstatic void 805231990SmpremoveHistHashTable(struct Hist *np) 806231990Smp{ 807231990Smp unsigned hi = np->Hhash; 808231990Smp if (!histHashTable || !hi) 809231990Smp return; /* no hash table or not on it */ 810231990Smp /* find desired entry */ 811231990Smp while ((hi = hash2tableIndex(hi, histHashTableLength)), 812231990Smp histHashTable[hi] != emptyHTE) { 813231990Smp if (np == histHashTable[hi]) { 814231990Smp unsigned i; 815231990Smp unsigned deletes = 0; 816231990Smp histHashTable[hi] = deletedHTE; /* dummy, but non-zero entry */ 817231990Smp /* now peek ahead to see if the dummies are really necessary. */ 818231990Smp i = 1; 819231990Smp while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == 820231990Smp deletedHTE) 821231990Smp i++; 822231990Smp if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == 823231990Smp emptyHTE) { 824231990Smp /* dummies are no longer necessary placeholders. */ 825231990Smp deletes = i; 826231990Smp while (i-- > 0) { 827231990Smp histHashTable[hash2tableIndex(hi+i, histHashTableLength)] = 828231990Smp emptyHTE; 829231990Smp } 830231990Smp } 831231990Smp hashStats.deleted += 1 - deletes; /* delta deleted entries */ 832231990Smp hashStats.removeCount++; 833231990Smp return; 834231990Smp } 835231990Smp hi++; /* linear rehash */ 836231990Smp } 837231990Smp assert(!"Hist entry not found in hash table"); 838231990Smp} 839231990Smp 840231990Smp/* Search the history hash table for a command matching lp, using hashval as 841231990Smp * its hash value. */ 842231990Smpstatic struct Hist * 843231990SmpfindHistHashTable(struct wordent *lp, unsigned hashval) 844231990Smp{ 845231990Smp unsigned deleted = 0; /* number of deleted entries skipped */ 846231990Smp unsigned hi = hashval; 847231990Smp struct Hist *hp; 848231990Smp if (!histHashTable) 849231990Smp return NULL; 850231990Smp while ((hi = hash2tableIndex(hi, histHashTableLength)), 851231990Smp (hp = histHashTable[hi]) != emptyHTE) { 852231990Smp if (hp == deletedHTE) 853231990Smp deleted++; 854231990Smp else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex))) 855231990Smp return hp; 856231990Smp if (deleted > (histHashTableLength>>4)) { 857231990Smp /* lots of deletes, so we need a sparser table. */ 858231990Smp discardHistHashTable(); 859231990Smp createHistHashTable(histHashTableLength); 860231990Smp return findHistHashTable(lp, hashval); 861231990Smp } 862231990Smp hi++; /* linear rehash */ 863231990Smp } 864231990Smp return NULL; 865231990Smp} 866231990Smp 867231990Smp/* When merge semantics are in use, find the approximate predecessor for the 868231990Smp * new entry, so that the Htime entries are decreasing. Return the entry just 869231990Smp * before the first entry with equal times, so the caller can check for 870231990Smp * duplicates. When pTime is not NULL, use it as a starting point for search, 871231990Smp * otherwise search from beginning (largest time value) of history list. */ 872231990SmpPG_STATIC struct Hist * 873231990SmpmergeInsertionPoint( 874231990Smp struct Hist *np, /* new entry to be inserted */ 875231990Smp struct Hist *pTime) /* hint about where to insert */ 876231990Smp{ 877231990Smp struct Hist *pp, *p; 878231990Smp if (histTail && histTail->Htime >= np->Htime) 879231990Smp pTime = histTail; /* new entry goes at the end */ 880231990Smp if (histMerg && histMerg != &Histlist && histMerg != Histlist.Hnext) { 881231990Smp /* Check above and below previous insertion point, in case we're adding 882231990Smp * sequential times in the middle of the list (e.g. history -M). */ 883231990Smp if (histMerg->Htime >= np->Htime) 884231990Smp pTime = histMerg; 885231990Smp else if (histMerg->Hprev->Htime >= np->Htime) 886231990Smp pTime = histMerg->Hprev; 887231990Smp } 888231990Smp if (pTime) { 889231990Smp /* With hint, search up the list until Htime is greater. We skip past 890231990Smp * the equal ones, too, so our caller can elide duplicates. */ 891231990Smp pp = pTime; 892231990Smp while (pp != &Histlist && pp->Htime <= np->Htime) 893231990Smp pp = pp->Hprev; 894231990Smp } else 895231990Smp pp = &Histlist; 896231990Smp /* Search down the list while current entry's time is too large. */ 897231990Smp while ((p = pp->Hnext) && (p->Htime > np->Htime)) 898231990Smp pp = p; /* advance insertion point */ 899231990Smp /* Remember recent position as hint for next time */ 900231990Smp histMerg = pp; 901231990Smp return pp; 902231990Smp} 903231990Smp 904231990Smp/* Bubble Hnum & Href in new entry down to pp through earlier part of list. */ 905231990SmpPG_STATIC void bubbleHnumHrefDown(struct Hist *np, struct Hist *pp) 906231990Smp{ 907231990Smp struct Hist *p; 908231990Smp for (p = Histlist.Hnext; p != pp->Hnext; p = p->Hnext) { 909231990Smp /* swap Hnum & Href values of p and np. */ 910231990Smp int n = p->Hnum, r = p->Href; 911231990Smp p->Hnum = np->Hnum; p->Href = np->Href; 912231990Smp np->Hnum = n; np->Href = r; 913231990Smp } 914231990Smp} 915231990Smp 916231990Smp/* Enter new command into the history list according to current settings. */ 91759243Sobrienstruct Hist * 918231990Smpenthist( 919231990Smp int event, /* newly incremented global eventno */ 920231990Smp struct wordent *lp, 921231990Smp int docopy, 922231990Smp int mflg, /* true if merge requested */ 923316957Sdchagin int hlen) /* -1 if unknown */ 92459243Sobrien{ 925231990Smp struct Hist *p = NULL, *pp = &Histlist, *pTime = NULL; 926145479Smp struct Hist *np; 927167465Smp const Char *dp; 928231990Smp unsigned lpHash = 0; /* non-zero if hashing entries */ 929231990Smp 93059243Sobrien if ((dp = varval(STRhistdup)) != STRNULL) { 93159243Sobrien if (eq(dp, STRerase)) { 93259243Sobrien /* masaoki@akebono.tky.hp.com (Kobayashi Masaoki) */ 933316957Sdchagin createHistHashTable(hlen); 934231990Smp lpHash = hashhist(lp); 935231990Smp assert(lpHash != 0); 936231990Smp p = findHistHashTable(lp, lpHash); 937231990Smp if (p) { 938231990Smp if (Htime != 0 && p->Htime > Htime) 939231990Smp Htime = p->Htime; 940231990Smp /* If we are merging, and the old entry is at the place we want 941231990Smp * to insert the new entry, then remember the place. */ 942231990Smp if (mflg && Htime != 0 && p->Hprev->Htime >= Htime) 943231990Smp pTime = p->Hprev; 944231990Smp if (!fastMergeErase) 945231990Smp renumberHist(p); /* Reset Href of subsequent entries */ 946231990Smp hremove(p); 947231990Smp hfree(p); 948231990Smp p = NULL; /* so new entry is allocated below */ 949231990Smp } 95059243Sobrien } 95159243Sobrien else if (eq(dp, STRall)) { 952316957Sdchagin createHistHashTable(hlen); 953231990Smp lpHash = hashhist(lp); 954231990Smp assert(lpHash != 0); 955231990Smp p = findHistHashTable(lp, lpHash); 956231990Smp if (p) /* p!=NULL, only update this entry's Htime below */ 957231990Smp eventno--; /* not adding a new event */ 95859243Sobrien } 95959243Sobrien else if (eq(dp, STRprev)) { 96059243Sobrien if (pp->Hnext && heq(lp, &(pp->Hnext->Hlex))) { 96159243Sobrien p = pp->Hnext; 96259243Sobrien eventno--; 96359243Sobrien } 96459243Sobrien } 96559243Sobrien } 96659243Sobrien 967167465Smp np = p ? p : xmalloc(sizeof(*np)); 96859243Sobrien 96959243Sobrien /* Pick up timestamp set by lex() in Htime if reading saved history */ 970167465Smp if (Htime != 0) { 97159243Sobrien np->Htime = Htime; 97259243Sobrien Htime = 0; 97359243Sobrien } 97459243Sobrien else 975231990Smp (void) time(&(np->Htime)); 97659243Sobrien 97759243Sobrien if (p == np) 978231990Smp return np; /* reused existing entry */ 97959243Sobrien 980231990Smp /* Initialize the new entry. */ 98159243Sobrien np->Hnum = np->Href = event; 98259243Sobrien if (docopy) { 983231990Smp copylex(&np->Hlex, lp); 98459243Sobrien if (histvalid) 985167465Smp np->histline = Strsave(histline.s); 98659243Sobrien else 98759243Sobrien np->histline = NULL; 98859243Sobrien } 98959243Sobrien else { 99059243Sobrien np->Hlex.next = lp->next; 99159243Sobrien lp->next->prev = &np->Hlex; 99259243Sobrien np->Hlex.prev = lp->prev; 993231990Smp lp->prev->next = &np->Hlex; 994231990Smp np->histline = NULL; 99559243Sobrien } 996231990Smp np->Hhash = 0; 997231990Smp 998231990Smp /* The head of history list is the default insertion point. 999231990Smp If merging, advance insertion point, in pp, according to Htime. */ 1000231990Smp /* XXX -- In histdup=all, Htime values can be non-monotonic. */ 1001231990Smp if (mflg) { /* merge according to np->Htime */ 1002231990Smp pp = mergeInsertionPoint(np, pTime); 1003231990Smp for (p = pp->Hnext; p && p->Htime == np->Htime; pp = p, p = p->Hnext) { 1004231990Smp if (heq(&p->Hlex, &np->Hlex)) { 1005231990Smp eventno--; /* duplicate, so don't add new event */ 1006231990Smp hfree(np); 1007231990Smp return (p); 1008231990Smp } 1009231990Smp } 1010231990Smp /* pp is now the last entry with time >= to np. */ 1011231990Smp if (!fastMergeErase) { /* renumber at end of loadhist */ 1012231990Smp /* Before inserting np after pp, bubble its Hnum & Href values down 1013231990Smp * through the earlier part of list. */ 1014231990Smp bubbleHnumHrefDown(np, pp); 1015231990Smp } 1016231990Smp } 1017231990Smp else 1018231990Smp pp = &Histlist; /* insert at beginning of history */ 1019231990Smp hinsert(np, pp); 1020316957Sdchagin if (lpHash && hlen != 0) /* erase & all modes use hash table */ 1021231990Smp insertHistHashTable(np, lpHash); 1022231990Smp else 1023231990Smp discardHistHashTable(); 102459243Sobrien return (np); 102559243Sobrien} 102659243Sobrien 102759243Sobrienstatic void 1028167465Smphfree(struct Hist *hp) 102959243Sobrien{ 1030231990Smp assert(hp != histMerg); 1031231990Smp if (hp->Hhash) 1032231990Smp removeHistHashTable(hp); 103359243Sobrien freelex(&hp->Hlex); 103459243Sobrien if (hp->histline) 1035231990Smp xfree(hp->histline); 1036167465Smp xfree(hp); 103759243Sobrien} 103859243Sobrien 1039231990SmpPG_STATIC void 1040231990Smpphist(struct Hist *hp, int hflg) 1041231990Smp{ 1042316957Sdchagin if (hp->Href < 0) 1043316957Sdchagin return; 1044231990Smp if (hflg & HIST_ONLY) { 1045231990Smp int old_output_raw; 104659243Sobrien 1047231990Smp /* 1048231990Smp * Control characters have to be written as is (output_raw). 1049231990Smp * This way one can preserve special characters (like tab) in 1050231990Smp * the history file. 1051231990Smp * From: mveksler@vnet.ibm.com (Veksler Michael) 1052231990Smp */ 1053231990Smp old_output_raw = output_raw; 1054231990Smp output_raw = 1; 1055231990Smp cleanup_push(&old_output_raw, output_raw_restore); 1056231990Smp if (hflg & HIST_TIME) 1057231990Smp /* 1058231990Smp * Make file entry with history time in format: 1059231990Smp * "+NNNNNNNNNN" (10 digits, left padded with ascii '0') 1060231990Smp */ 1061231990Smp 1062231990Smp xprintf("#+%010lu\n", (unsigned long)hp->Htime); 1063231990Smp 1064231990Smp if (HistLit && hp->histline) 1065231990Smp xprintf("%S\n", hp->histline); 1066231990Smp else 1067231990Smp prlex(&hp->Hlex); 1068231990Smp cleanup_until(&old_output_raw); 1069231990Smp } 1070231990Smp else { 1071231990Smp Char *cp = str2short("%h\t%T\t%R\n"); 1072231990Smp Char *p; 1073231990Smp struct varent *vp = adrof(STRhistory); 1074231990Smp 1075231990Smp if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1]) 1076231990Smp cp = vp->vec[1]; 1077231990Smp 1078231990Smp p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp); 1079231990Smp cleanup_push(p, xfree); 1080231990Smp for (cp = p; *cp;) 1081231990Smp xputwchar(*cp++); 1082231990Smp cleanup_until(p); 1083231990Smp } 1084231990Smp} 1085231990Smp 1086231990SmpPG_STATIC void 1087231990Smpdophist(int n, int hflg) 1088231990Smp{ 1089231990Smp struct Hist *hp; 1090231990Smp if (setintr) { 1091231990Smp int old_pintr_disabled; 1092231990Smp 1093231990Smp pintr_push_enable(&old_pintr_disabled); 1094231990Smp cleanup_until(&old_pintr_disabled); 1095231990Smp } 1096231990Smp if ((hflg & HIST_REV) == 0) { 1097231990Smp /* Since the history list is stored most recent first, non-reversing 1098231990Smp * print needs to print (backwards) up the list. */ 1099231990Smp if ((unsigned)n >= histCount) 1100231990Smp hp = histTail; 1101231990Smp else { 1102231990Smp for (hp = Histlist.Hnext; 1103231990Smp --n > 0 && hp->Hnext != NULL; 1104231990Smp hp = hp->Hnext) 1105231990Smp ; 1106231990Smp } 1107231990Smp if (hp == NULL) 1108231990Smp return; /* nothing to print */ 1109231990Smp for (; hp != &Histlist; hp = hp->Hprev) 1110231990Smp phist(hp, hflg); 1111231990Smp } else { 1112231990Smp for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext) 1113231990Smp phist(hp, hflg); 1114231990Smp } 1115231990Smp} 1116231990Smp 111759243Sobrien/*ARGSUSED*/ 111859243Sobrienvoid 1119167465Smpdohist(Char **vp, struct command *c) 112059243Sobrien{ 112159243Sobrien int n, hflg = 0; 112259243Sobrien 112359243Sobrien USE(c); 112459243Sobrien if (getn(varval(STRhistory)) == 0) 112559243Sobrien return; 112659243Sobrien while (*++vp && **vp == '-') { 112759243Sobrien Char *vp2 = *vp; 112859243Sobrien 112959243Sobrien while (*++vp2) 113059243Sobrien switch (*vp2) { 113159243Sobrien case 'c': 113259243Sobrien hflg |= HIST_CLEAR; 113359243Sobrien break; 113459243Sobrien case 'h': 113559243Sobrien hflg |= HIST_ONLY; 113659243Sobrien break; 113759243Sobrien case 'r': 113859243Sobrien hflg |= HIST_REV; 113959243Sobrien break; 114059243Sobrien case 'S': 114159243Sobrien hflg |= HIST_SAVE; 114259243Sobrien break; 114359243Sobrien case 'L': 114459243Sobrien hflg |= HIST_LOAD; 114559243Sobrien break; 114659243Sobrien case 'M': 114759243Sobrien hflg |= HIST_MERGE; 114859243Sobrien break; 114959243Sobrien case 'T': 115059243Sobrien hflg |= HIST_TIME; 115159243Sobrien break; 115259243Sobrien default: 115359243Sobrien stderror(ERR_HISTUS, "chrSLMT"); 115459243Sobrien break; 115559243Sobrien } 115659243Sobrien } 115759243Sobrien if (hflg & HIST_CLEAR) { 1158231990Smp struct Hist *np, *hp; 1159231990Smp for (hp = &Histlist; (np = hp->Hnext) != NULL;) 1160231990Smp hremove(np), hfree(np); 116159243Sobrien } 116259243Sobrien 1163167465Smp if (hflg & (HIST_LOAD | HIST_MERGE)) 116459243Sobrien loadhist(*vp, (hflg & HIST_MERGE) ? 1 : 0); 1165167465Smp else if (hflg & HIST_SAVE) 116659243Sobrien rechist(*vp, 1); 116759243Sobrien else { 1168167465Smp if (*vp) 1169167465Smp n = getn(*vp); 1170167465Smp else { 1171167465Smp n = getn(varval(STRhistory)); 1172167465Smp } 1173231990Smp dophist(n, hflg); 117459243Sobrien } 117559243Sobrien} 117659243Sobrien 117759243Sobrien 1178167465Smpchar * 1179167465Smpfmthist(int fmt, ptr_t ptr) 1180167465Smp{ 1181167465Smp struct Hist *hp = ptr; 118259243Sobrien char *buf; 1183167465Smp 118459243Sobrien switch (fmt) { 118559243Sobrien case 'h': 1186167465Smp return xasprintf("%6d", hp->Hnum); 118759243Sobrien case 'R': 118859243Sobrien if (HistLit && hp->histline) 1189167465Smp return xasprintf("%S", hp->histline); 119059243Sobrien else { 1191167465Smp Char *istr, *ip; 119259243Sobrien char *p; 1193145479Smp 1194167465Smp istr = sprlex(&hp->Hlex); 1195167465Smp buf = xmalloc(Strlen(istr) * MB_LEN_MAX + 1); 1196167465Smp 1197167465Smp for (p = buf, ip = istr; *ip != '\0'; ip++) 1198316957Sdchagin p += one_wctomb(p, *ip); 1199167465Smp 1200167465Smp *p = '\0'; 1201167465Smp xfree(istr); 1202167465Smp return buf; 120359243Sobrien } 120459243Sobrien default: 1205167465Smp buf = xmalloc(1); 120659243Sobrien buf[0] = '\0'; 1207167465Smp return buf; 120859243Sobrien } 120959243Sobrien} 121059243Sobrien 1211316957Sdchaginstatic void 1212316957Sdchagindotlock_cleanup(void* lockpath) 1213316957Sdchagin{ 1214316957Sdchagin dot_unlock((char*)lockpath); 1215316957Sdchagin} 1216316957Sdchagin 1217231990Smp/* Save history before exiting the shell. */ 121859243Sobrienvoid 1219167465Smprechist(Char *fname, int ref) 122059243Sobrien{ 1221316957Sdchagin Char *snum, *rs; 122259243Sobrien int fp, ftmp, oldidfds; 122359243Sobrien struct varent *shist; 1224316957Sdchagin char path[MAXPATHLEN]; 1225316957Sdchagin struct stat st; 122659243Sobrien static Char *dumphist[] = {STRhistory, STRmhT, 0, 0}; 122759243Sobrien 122859243Sobrien if (fname == NULL && !ref) 122959243Sobrien return; 123059243Sobrien /* 123159243Sobrien * If $savehist is just set, we use the value of $history 123259243Sobrien * else we use the value in $savehist 123359243Sobrien */ 123459243Sobrien if (((snum = varval(STRsavehist)) == STRNULL) && 123559243Sobrien ((snum = varval(STRhistory)) == STRNULL)) 123659243Sobrien snum = STRmaxint; 123759243Sobrien 123859243Sobrien 123959243Sobrien if (fname == NULL) { 124059243Sobrien if ((fname = varval(STRhistfile)) == STRNULL) 124159243Sobrien fname = Strspl(varval(STRhome), &STRtildothist[1]); 124259243Sobrien else 124359243Sobrien fname = Strsave(fname); 124459243Sobrien } 124559243Sobrien else 124659243Sobrien fname = globone(fname, G_ERROR); 1247167465Smp cleanup_push(fname, xfree); 124859243Sobrien 124959243Sobrien /* 125059243Sobrien * The 'savehist merge' feature is intended for an environment 1251167465Smp * with numerous shells being in simultaneous use. Imagine 125259243Sobrien * any kind of window system. All these shells 'share' the same 125359243Sobrien * ~/.history file for recording their command line history. 1254316957Sdchagin * We try to handle the case of multiple shells trying to merge 1255316957Sdchagin * histories at the same time, by creating semi-unique filenames 1256316957Sdchagin * and saving the history there first and then trying to rename 1257316957Sdchagin * them in the proper history file. 125859243Sobrien * 125959243Sobrien * Users that like to nuke their environment require here an atomic 1260316957Sdchagin * loadhist-creat-dohist(dumphist)-close sequence which is given 1261316957Sdchagin * by optional lock parameter to savehist. 126259243Sobrien * 126359243Sobrien * jw. 126459243Sobrien */ 126559243Sobrien /* 126659243Sobrien * We need the didfds stuff before loadhist otherwise 126759243Sobrien * exec in a script will fail to print if merge is set. 126859243Sobrien * From: mveksler@iil.intel.com (Veksler Michael) 126959243Sobrien */ 127059243Sobrien oldidfds = didfds; 127159243Sobrien didfds = 0; 1272316957Sdchagin if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL) { 1273316957Sdchagin size_t i; 1274316957Sdchagin int merge = 0, lock = 0; 1275316957Sdchagin 1276316957Sdchagin for (i = 1; shist->vec[i]; i++) { 1277316957Sdchagin if (eq(shist->vec[i], STRmerge)) 1278316957Sdchagin merge++; 1279316957Sdchagin if (eq(shist->vec[i], STRlock)) 1280316957Sdchagin lock++; 1281316957Sdchagin } 1282316957Sdchagin 1283316957Sdchagin if (merge) { 1284354195Sbrooks jmp_buf_t osetexit; 1285316957Sdchagin if (lock) { 1286316957Sdchagin#ifndef WINNT_NATIVE 1287316957Sdchagin char *lockpath = strsave(short2str(fname)); 1288316957Sdchagin cleanup_push(lockpath, xfree); 1289316957Sdchagin /* Poll in 100 miliseconds interval to obtain the lock. */ 1290316957Sdchagin if ((dot_lock(lockpath, 100) == 0)) 1291316957Sdchagin cleanup_push(lockpath, dotlock_cleanup); 1292316957Sdchagin#endif 1293316957Sdchagin } 1294354195Sbrooks getexit(osetexit); 1295354195Sbrooks if (setexit()) 1296354195Sbrooks loadhist(fname, 1); 1297354195Sbrooks resexit(osetexit); 1298316957Sdchagin } 1299316957Sdchagin } 1300316957Sdchagin rs = randsuf(); 1301316957Sdchagin xsnprintf(path, sizeof(path), "%S.%S", fname, rs); 1302316957Sdchagin xfree(rs); 1303231990Smp 1304316957Sdchagin fp = xcreat(path, 0600); 130559243Sobrien if (fp == -1) { 130659243Sobrien didfds = oldidfds; 1307316957Sdchagin cleanup_until(fname); 130859243Sobrien return; 130959243Sobrien } 1310316957Sdchagin /* Try to preserve ownership and permissions of the original history file */ 1311316957Sdchagin#ifndef WINNT_NATIVE 1312316957Sdchagin if (stat(short2str(fname), &st) != -1) { 1313316957Sdchagin TCSH_IGNORE(fchown(fp, st.st_uid, st.st_gid)); 1314316957Sdchagin TCSH_IGNORE(fchmod(fp, st.st_mode)); 1315316957Sdchagin } 1316316957Sdchagin#else 1317316957Sdchagin UNREFERENCED_PARAMETER(st); 1318316957Sdchagin#endif 131959243Sobrien ftmp = SHOUT; 132059243Sobrien SHOUT = fp; 132159243Sobrien dumphist[2] = snum; 132259243Sobrien dohist(dumphist, NULL); 1323167465Smp xclose(fp); 132459243Sobrien SHOUT = ftmp; 132559243Sobrien didfds = oldidfds; 1326354195Sbrooks#ifndef WINNT_NATIVE 1327316957Sdchagin (void)rename(path, short2str(fname)); 1328354195Sbrooks#else 1329354195Sbrooks (void)ReplaceFile( short2str(fname),path,NULL,0,NULL,NULL); 1330354195Sbrooks#endif 1331316957Sdchagin cleanup_until(fname); 133259243Sobrien} 133359243Sobrien 133459243Sobrien 1335231990Smp/* This is the entry point for loading history data from a file. */ 133659243Sobrienvoid 1337167465Smploadhist(Char *fname, int mflg) 133859243Sobrien{ 133959243Sobrien static Char *loadhist_cmd[] = {STRsource, NULL, NULL, NULL}; 134059243Sobrien loadhist_cmd[1] = mflg ? STRmm : STRmh; 134159243Sobrien 134259243Sobrien if (fname != NULL) 134359243Sobrien loadhist_cmd[2] = fname; 134459243Sobrien else if ((fname = varval(STRhistfile)) != STRNULL) 134559243Sobrien loadhist_cmd[2] = fname; 134659243Sobrien else 134759243Sobrien loadhist_cmd[2] = STRtildothist; 134859243Sobrien 134959243Sobrien dosource(loadhist_cmd, NULL); 1350231990Smp 1351231990Smp /* During history merging (enthist sees mflg set), we disable management of 1352231990Smp * Hnum and Href (because fastMergeErase is true). So now reset all the 1353231990Smp * values based on the final ordering of the history list. */ 1354231990Smp if (mflg) { 1355231990Smp int n = eventno; 1356231990Smp struct Hist *hp = &Histlist; 1357231990Smp while ((hp = hp->Hnext)) 1358231990Smp hp->Hnum = hp->Href = n--; 1359231990Smp } 136059243Sobrien} 1361316957Sdchagin 1362316957Sdchaginvoid 1363316957Sdchaginsethistory(int n) 1364316957Sdchagin{ 1365316957Sdchagin histlen = n; 1366316957Sdchagin discardExcess(histlen); 1367316957Sdchagin} 1368