1231990Smp/* $Header: /p/tcsh/cvsroot/tcsh/sh.hist.c,v 3.53 2011/01/24 18:10:26 christos Exp $ */ 259243Sobrien/* 359243Sobrien * sh.hist.c: Shell history expansions and substitutions 459243Sobrien */ 559243Sobrien/*- 659243Sobrien * Copyright (c) 1980, 1991 The Regents of the University of California. 759243Sobrien * All rights reserved. 859243Sobrien * 959243Sobrien * Redistribution and use in source and binary forms, with or without 1059243Sobrien * modification, are permitted provided that the following conditions 1159243Sobrien * are met: 1259243Sobrien * 1. Redistributions of source code must retain the above copyright 1359243Sobrien * notice, this list of conditions and the following disclaimer. 1459243Sobrien * 2. Redistributions in binary form must reproduce the above copyright 1559243Sobrien * notice, this list of conditions and the following disclaimer in the 1659243Sobrien * documentation and/or other materials provided with the distribution. 17100616Smp * 3. Neither the name of the University nor the names of its contributors 1859243Sobrien * may be used to endorse or promote products derived from this software 1959243Sobrien * without specific prior written permission. 2059243Sobrien * 2159243Sobrien * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2259243Sobrien * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2359243Sobrien * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2459243Sobrien * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2559243Sobrien * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2659243Sobrien * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2759243Sobrien * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2859243Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2959243Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3059243Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3159243Sobrien * SUCH DAMAGE. 3259243Sobrien */ 3359243Sobrien#include "sh.h" 3459243Sobrien 35231990SmpRCSID("$tcsh: sh.hist.c,v 3.53 2011/01/24 18:10:26 christos Exp $") 3659243Sobrien 37231990Smp#include <assert.h> 3859243Sobrien#include "tc.h" 3959243Sobrien 40145479Smpextern int histvalid; 41167465Smpextern struct Strbuf histline; 4259243SobrienChar HistLit = 0; 4359243Sobrien 44167465Smpstatic int heq (const struct wordent *, const struct wordent *); 45167465Smpstatic void hfree (struct Hist *); 4659243Sobrien 4759243Sobrien#define HIST_ONLY 0x01 4859243Sobrien#define HIST_SAVE 0x02 4959243Sobrien#define HIST_LOAD 0x04 5059243Sobrien#define HIST_REV 0x08 5159243Sobrien#define HIST_CLEAR 0x10 5259243Sobrien#define HIST_MERGE 0x20 5359243Sobrien#define HIST_TIME 0x40 5459243Sobrien 5559243Sobrien/* 5659243Sobrien * C shell 5759243Sobrien */ 5859243Sobrien 59231990Smp/* Static functions don't show up in gprof summaries. So eliminate "static" 60231990Smp * modifier from some frequently called functions. */ 61231990Smp#ifdef PROF 62231990Smp#define PG_STATIC 63231990Smp#else 64231990Smp#define PG_STATIC static 65231990Smp#endif 66231990Smp 67231990Smp/* #define DEBUG_HIST 1 */ 68231990Smp 69231990Smpstatic const int fastMergeErase = 1; 70231990Smpstatic unsigned histCount = 0; /* number elements on history list */ 71231990Smpstatic struct Hist *histTail = NULL; /* last element on history list */ 72231990Smpstatic struct Hist *histMerg = NULL; /* last element merged by Htime */ 73231990Smp 74231990Smpstatic void insertHistHashTable(struct Hist *, unsigned); 75231990Smp 76231990Smp 77231990Smp/* Insert new element (hp) in history list after specified predecessor (pp). */ 78231990Smpstatic void 79231990Smphinsert(struct Hist *hp, struct Hist *pp) 80231990Smp{ 81231990Smp struct Hist *fp = pp->Hnext; /* following element, if any */ 82231990Smp hp->Hnext = fp, hp->Hprev = pp; 83231990Smp pp->Hnext = hp; 84231990Smp if (fp) 85231990Smp fp->Hprev = hp; 86231990Smp else 87231990Smp histTail = hp; /* meaning hp->Hnext == NULL */ 88231990Smp histCount++; 89231990Smp} 90231990Smp 91231990Smp/* Remove the entry from the history list. */ 92231990Smpstatic void 93231990Smphremove(struct Hist *hp) 94231990Smp{ 95231990Smp struct Hist *pp = hp->Hprev; 96231990Smp assert(pp); /* elements always have a previous */ 97231990Smp pp->Hnext = hp->Hnext; 98231990Smp if (hp->Hnext) 99231990Smp hp->Hnext->Hprev = pp; 100231990Smp else 101231990Smp histTail = pp; /* we must have been last */ 102231990Smp if (hp == histMerg) /* deleting this hint from list */ 103231990Smp histMerg = NULL; 104231990Smp assert(histCount > 0); 105231990Smp histCount--; 106231990Smp} 107231990Smp 108231990Smp/* Prune length of history list to specified size by history variable. */ 109231990SmpPG_STATIC void 110231990SmpdiscardExcess(int histlen) 111231990Smp{ 112231990Smp struct Hist *hp, *np; 113231990Smp if (histTail == NULL) { 114231990Smp assert(histCount == 0); 115231990Smp return; /* no entries on history list */ 116231990Smp } 117231990Smp /* Prune dummy entries from the front, then old entries from the back. If 118231990Smp * the list is still too long scan the whole list as before. But only do a 119231990Smp * full scan if the list is more than 6% (1/16th) too long. */ 120231990Smp while (histCount > (unsigned)histlen && (np = Histlist.Hnext)) { 121231990Smp if (eventno - np->Href >= histlen || histlen == 0) 122231990Smp hremove(np), hfree(np); 123231990Smp else 124231990Smp break; 125231990Smp } 126231990Smp while (histCount > (unsigned)histlen && (np = histTail) != &Histlist) { 127231990Smp if (eventno - np->Href >= histlen || histlen == 0) 128231990Smp hremove(np), hfree(np); 129231990Smp else 130231990Smp break; 131231990Smp } 132231990Smp if (histCount - (histlen >> 4) <= (unsigned)histlen) 133231990Smp return; /* don't bother doing the full scan */ 134231990Smp for (hp = &Histlist; histCount > (unsigned)histlen && 135231990Smp (np = hp->Hnext) != NULL;) 136231990Smp if (eventno - np->Href >= histlen || histlen == 0) 137231990Smp hremove(np), hfree(np); 138231990Smp else 139231990Smp hp = np; 140231990Smp} 141231990Smp 142231990Smp/* Add the command "sp" to the history list. */ 14359243Sobrienvoid 144231990Smpsavehist( 145231990Smp struct wordent *sp, 146231990Smp int mflg) /* true if -m (merge) specified */ 14759243Sobrien{ 148145479Smp int histlen = 0; 14959243Sobrien Char *cp; 15059243Sobrien 15159243Sobrien /* throw away null lines */ 15259243Sobrien if (sp && sp->next->word[0] == '\n') 15359243Sobrien return; 15459243Sobrien cp = varval(STRhistory); 155167465Smp while (*cp) { 156167465Smp if (!Isdigit(*cp)) { 157167465Smp histlen = 0; 158167465Smp break; 15959243Sobrien } 160167465Smp histlen = histlen * 10 + *cp++ - '0'; 16159243Sobrien } 16259243Sobrien if (sp) 163231990Smp (void) enthist(++eventno, sp, 1, mflg, histlen); 164231990Smp discardExcess(histlen); 16559243Sobrien} 16659243Sobrien 167231990Smp#define USE_JENKINS_HASH 1 168231990Smp/* #define USE_ONE_AT_A_TIME 1 */ 169231990Smp#undef PRIME_LENGTH /* no need for good HTL */ 170231990Smp 171231990Smp#ifdef USE_JENKINS_HASH 172231990Smp#define hashFcnName "lookup3" 173231990Smp/* From: 174231990Smp lookup3.c, by Bob Jenkins, May 2006, Public Domain. 175231990Smp "... You can use this free for any purpose. It's in 176231990Smp the public domain. It has no warranty." 177231990Smp http://burtleburtle.net/bob/hash/index.html 178231990Smp */ 179231990Smp 180231990Smp#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 181231990Smp#define mix(a,b,c) \ 182231990Smp{ \ 183231990Smp a -= c; a ^= rot(c, 4); c += b; \ 184231990Smp b -= a; b ^= rot(a, 6); a += c; \ 185231990Smp c -= b; c ^= rot(b, 8); b += a; \ 186231990Smp a -= c; a ^= rot(c,16); c += b; \ 187231990Smp b -= a; b ^= rot(a,19); a += c; \ 188231990Smp c -= b; c ^= rot(b, 4); b += a; \ 189231990Smp} 190231990Smp#define final(a,b,c) \ 191231990Smp{ \ 192231990Smp c ^= b; c -= rot(b,14); \ 193231990Smp a ^= c; a -= rot(c,11); \ 194231990Smp b ^= a; b -= rot(a,25); \ 195231990Smp c ^= b; c -= rot(b,16); \ 196231990Smp a ^= c; a -= rot(c, 4); \ 197231990Smp b ^= a; b -= rot(a,14); \ 198231990Smp c ^= b; c -= rot(b,24); \ 199231990Smp} 200231990Smp 201231990Smpstruct hashValue /* State used to hash a wordend word list. */ 202231990Smp{ 203231990Smp uint32_t a, b, c; 204231990Smp}; 205231990Smp 206231990Smp/* Set up the internal state */ 207231990Smpstatic void 208231990SmpinitializeHash(struct hashValue *h) 209231990Smp{ 210231990Smp h->a = h->b = h->c = 0xdeadbeef; 211231990Smp} 212231990Smp 213231990Smp/* This does a partial hash of the Chars in a single word. For efficiency we 214231990Smp * include 3 versions of the code to pack Chars into 32-bit words for the 215231990Smp * mixing function. */ 216231990Smpstatic void 217231990SmpaddWordToHash(struct hashValue *h, const Char *word) 218231990Smp{ 219231990Smp uint32_t a = h->a, b = h->b, c = h->c; 220231990Smp#ifdef SHORT_STRINGS 221231990Smp#ifdef WIDE_STRINGS 222231990Smp assert(sizeof(Char) >= 4); 223231990Smp while (1) { 224231990Smp unsigned k; 225231990Smp if ((k = (uChar)*word++) == 0) break; a += k; 226231990Smp if ((k = (uChar)*word++) == 0) break; b += k; 227231990Smp if ((k = (uChar)*word++) == 0) break; c += k; 228231990Smp mix(a, b, c); 229231990Smp } 230231990Smp#else 231231990Smp assert(sizeof(Char) == 2); 232231990Smp while (1) { 233231990Smp unsigned k; 234231990Smp if ((k = (uChar)*word++) == 0) break; a += k; 235231990Smp if ((k = (uChar)*word++) == 0) break; a += k << 16; 236231990Smp if ((k = (uChar)*word++) == 0) break; b += k; 237231990Smp if ((k = (uChar)*word++) == 0) break; b += k << 16; 238231990Smp if ((k = (uChar)*word++) == 0) break; c += k; 239231990Smp if ((k = (uChar)*word++) == 0) break; c += k << 16; 240231990Smp mix(a, b, c); 241231990Smp } 242231990Smp#endif 243231990Smp#else 244231990Smp assert(sizeof(Char) == 1); 245231990Smp while (1) { 246231990Smp unsigned k; 247231990Smp if ((k = *word++) == 0) break; a += k; 248231990Smp if ((k = *word++) == 0) break; a += k << 8; 249231990Smp if ((k = *word++) == 0) break; a += k << 16; 250231990Smp if ((k = *word++) == 0) break; a += k << 24; 251231990Smp if ((k = *word++) == 0) break; b += k; 252231990Smp if ((k = *word++) == 0) break; b += k << 8; 253231990Smp if ((k = *word++) == 0) break; b += k << 16; 254231990Smp if ((k = *word++) == 0) break; b += k << 24; 255231990Smp if ((k = *word++) == 0) break; c += k; 256231990Smp if ((k = *word++) == 0) break; c += k << 8; 257231990Smp if ((k = *word++) == 0) break; c += k << 16; 258231990Smp if ((k = *word++) == 0) break; c += k << 24; 259231990Smp mix(a, b, c); 260231990Smp } 261231990Smp#endif 262231990Smp h->a = a, h->b = b, h->c = c; 263231990Smp} 264231990Smp 265231990Smpstatic void 266231990SmpaddCharToHash(struct hashValue *h, Char ch) 267231990Smp{ 268231990Smp /* The compiler (gcc -O2) seems to do a good job optimizing this without 269231990Smp * explicitly extracting into local variables. */ 270231990Smp h->a += (uChar)ch; 271231990Smp mix(h->a, h->b, h->c); 272231990Smp} 273231990Smp 274231990Smpstatic uint32_t 275231990SmpfinalizeHash(struct hashValue *h) 276231990Smp{ 277231990Smp uint32_t a = h->a, b = h->b, c = h->c; 278231990Smp final(a, b, c); 279231990Smp return c; 280231990Smp} 281231990Smp 282231990Smp#elif USE_ONE_AT_A_TIME 283231990Smp#define hashFcnName "one-at-a-time" 284231990Smp/* This one is also from Bob Jenkins, but is slower but simpler than lookup3. 285231990Smp "... The code given here are all public domain." 286231990Smp http://burtleburtle.net/bob/hash/doobs.html */ 287231990Smp 288231990Smp#if 0 289231990Smpub4 290231990Smpone_at_a_time(char *key, ub4 len) 291231990Smp{ 292231990Smp ub4 hash, i; 293231990Smp for (hash=0, i=0; i<len; ++i) 294231990Smp { 295231990Smp hash += key[i]; 296231990Smp hash += (hash << 10); 297231990Smp hash ^= (hash >> 6); 298231990Smp } 299231990Smp hash += (hash << 3); 300231990Smp hash ^= (hash >> 11); 301231990Smp hash += (hash << 15); 302231990Smp return (hash & mask); 303231990Smp} 304231990Smp#endif 305231990Smp 306231990Smpstruct hashValue { uint32_t h; }; 307231990Smpstatic void 308231990SmpinitializeHash(struct hashValue *h) 309231990Smp{ 310231990Smp h->h = 0; 311231990Smp} 312231990Smp 313231990Smpstatic void 314231990SmpaddWordToHash(struct hashValue *h, const Char *word) 315231990Smp{ 316231990Smp unsigned k; 317231990Smp uint32_t hash = h->h; 318231990Smp while (k = (uChar)*word++) 319231990Smp hash += k, hash += hash << 10, hash ^= hash >> 6; 320231990Smp h->h = hash; 321231990Smp} 322231990Smp 323231990Smpstatic void 324231990SmpaddCharToHash(struct hashValue *h, Char c) 325231990Smp{ 326231990Smp Char b[2] = { c, 0 }; 327231990Smp addWordToHash(h, b); 328231990Smp} 329231990Smp 330231990Smpstatic uint32_t 331231990SmpfinalizeHash(struct hashValue *h) 332231990Smp{ 333231990Smp unsigned hash = h->h; 334231990Smp hash += (hash << 3); 335231990Smp hash ^= (hash >> 11); 336231990Smp hash += (hash << 15); 337231990Smp return hash; 338231990Smp} 339231990Smp 340231990Smp#else 341231990Smp#define hashFcnName "add-mul" 342231990Smp/* Simple multipy and add hash. */ 343231990Smp#define PRIME_LENGTH 1 /* need "good" HTL */ 344231990Smpstruct hashValue { uint32_t h; }; 345231990Smpstatic void 346231990SmpinitializeHash(struct hashValue *h) 347231990Smp{ 348231990Smp h->h = 0xe13e2345; 349231990Smp} 350231990Smp 351231990Smpstatic void 352231990SmpaddWordToHash(struct hashValue *h, const Char *word) 353231990Smp{ 354231990Smp unsigned k; 355231990Smp uint32_t hash = h->h; 356231990Smp while (k = (uChar)*word++) 357231990Smp hash = hash * 0x9e4167b9 + k; 358231990Smp h->h = hash; 359231990Smp} 360231990Smp 361231990Smpstatic void 362231990SmpaddCharToHash(struct hashValue *h, Char c) 363231990Smp{ 364231990Smp h->h = h->h * 0x9e4167b9 + (uChar)c; 365231990Smp} 366231990Smp 367231990Smpstatic uint32_t 368231990SmpfinalizeHash(struct hashValue *h) 369231990Smp{ 370231990Smp return h->h; 371231990Smp} 372231990Smp#endif 373231990Smp 374231990Smpstatic unsigned 375231990Smphashhist(struct wordent *h0) 376231990Smp{ 377231990Smp struct hashValue s; 378231990Smp struct wordent *firstWord = h0->next; 379231990Smp struct wordent *h = firstWord; 380231990Smp unsigned hash = 0; 381231990Smp 382231990Smp initializeHash(&s); 383231990Smp for (; h != h0; h = h->next) { 384231990Smp if (h->word[0] == '\n') 385231990Smp break; /* don't hash newline */ 386231990Smp if (h != firstWord) 387231990Smp addCharToHash(&s, ' '); /* space between words */ 388231990Smp addWordToHash(&s, h->word); 389231990Smp } 390231990Smp hash = finalizeHash(&s); 391231990Smp /* Zero means no hash value, so never return zero as a hash value. */ 392231990Smp return hash ? hash : 0x7fffffff; /* prime! */ 393231990Smp} 394231990Smp 395231990Smp#if 0 396231990Smpunsigned 397231990SmphashStr(Char *str) 398231990Smp{ 399231990Smp struct hashValue s; 400231990Smp initializeHash(&s); 401231990Smp addWordToHash(&s, str); 402231990Smp return finalizeHash(&s); 403231990Smp} 404231990Smp#endif 405231990Smp 406231990Smp#ifdef PRIME_LENGTH /* need good HTL */ 407231990Smp#define hash2tableIndex(hash, len) ((hash) % len) 408231990Smp#else 409231990Smp#define hash2tableIndex(hash, len) ((hash) & (len-1)) 410231990Smp#endif 411231990Smp 412231990Smp/* This code can be enabled to test the above hash functions for speed and 413231990Smp * collision avoidance. The testing is enabled by "occasional" calls to 414231990Smp * displayHistStats(), see which. */ 415231990Smp#ifdef DEBUG_HIST 416231990Smp 417231990Smp#ifdef BSDTIMES 418231990Smpstatic double 419231990SmpdoTiming(int start) { 420231990Smp static struct timeval beginTime; 421231990Smp if (start) { 422231990Smp gettimeofday(&beginTime, NULL); 423231990Smp return 0.0; 424231990Smp } else { 425231990Smp struct timeval now; 426231990Smp gettimeofday(&now, NULL); 427231990Smp return (now.tv_sec-beginTime.tv_sec) + 428231990Smp (now.tv_usec-beginTime.tv_usec)/1e6; 429231990Smp } 430231990Smp} 431231990Smp#else 432231990Smpstatic double 433231990SmpdoTiming(int start) { 434231990Smp USE(start); 435231990Smp return 0.0; 436231990Smp} 437231990Smp#endif 438231990Smp 439231990Smpstatic void 440231990SmpgenerateHashes(int nChars, unsigned nWords, unsigned samples, unsigned *hashes, 441231990Smp unsigned length) 442231990Smp{ 443231990Smp if (nChars < 1) 444231990Smp return; 445231990Smp nWords = (nWords < 1) ? 1 : (nWords > 4) ? 4 : nWords; 446231990Smp Char *number = xmalloc((nChars+nWords)*sizeof(Char)); 447231990Smp struct wordent word[4]; 448231990Smp struct wordent base = { NULL, &word[0], &word[0] }; 449231990Smp word[0].word = number, word[0].next = &base, word[0].prev = &base; 450231990Smp unsigned w = 0; /* word number */ 451231990Smp /* Generate multiple words of length 2, 3, 5, then all the rest. */ 452231990Smp unsigned wBoundaries[4] = { 2-1, 2+3-1, 2+3+5-1, 0 }; 453231990Smp /* Ensure the last word has at least 4 Chars in it. */ 454231990Smp while (nWords >= 2 && nChars < (wBoundaries[nWords-2]+1) + 4) 455231990Smp nWords--; 456231990Smp wBoundaries[nWords-1] = 0xffffffff; /* don't end word past this point */ 457231990Smp unsigned i; 458231990Smp for (i = 0; i<nChars; i++) { 459231990Smp /* In deference to the gawd awful add-mul hash, we won't use the worse 460231990Smp * case here (setting all Chars to 1), but assume mostly (or at least 461231990Smp * initially) ASCII data. */ 462231990Smp number[i+w] = '!'; /* 0x21 = 33 */ 463231990Smp 464231990Smp if (i == wBoundaries[w]) { /* end a word here and move to next */ 465231990Smp w++; /* next word */ 466231990Smp number[i+w] = 0; /* terminate */ 467231990Smp word[w].word = &number[i+w+1]; 468231990Smp word[w].next = &base, word[w].prev = &word[w-1]; 469231990Smp word[w-1].next = &word[w], base.prev = &word[w]; 470231990Smp } 471231990Smp } 472231990Smp /* w is the index of the last word actually created. */ 473231990Smp number[nChars + w] = 0; /* terminate last word */ 474231990Smp unsigned timeLimit = !samples; 475231990Smp if (samples == 0) 476231990Smp samples = 1000000000; 477231990Smp doTiming(1); 478231990Smp double sec; 479231990Smp for (i = 0; i < samples; i++) { 480231990Smp /* increment 4 digit base 255 number; last characters vary fastest */ 481231990Smp unsigned j = nChars-1 + w; 482231990Smp while (1) { 483231990Smp if (++number[j] != 0) 484231990Smp break; 485231990Smp /* else reset this digit and proceed to next one */ 486231990Smp number[j] = 1; 487231990Smp if (&number[j] <= word[w].word) 488231990Smp break; /* stop at beginning of last word */ 489231990Smp j--; 490231990Smp } 491231990Smp if (word[w].word[0] == '\n') 492231990Smp word[w].word[0]++; /* suppress newline character */ 493231990Smp unsigned hash = hashhist(&base); 494231990Smp hashes[hash2tableIndex(hash, length)]++; 495231990Smp if (timeLimit && (i & 0x3ffff) == 0x3ffff) { 496231990Smp sec = doTiming(0); 497231990Smp if (sec > 10) 498231990Smp break; 499231990Smp } 500231990Smp } 501231990Smp if (i >= samples) 502231990Smp sec = doTiming(0); 503231990Smp else 504231990Smp samples = i; /* number we actually did */ 505231990Smp if (sec > 0.01) { 506231990Smp xprintf("Hash %d (%d Char %u words) with %s: %d nsec/hash, %d mcps\n", 507231990Smp samples, nChars, w+1, hashFcnName, (int)((sec/samples)*1e9), 508231990Smp (int)((double)samples*nChars/sec/1e6)); 509231990Smp } 510231990Smp} 511231990Smp#endif /* DEBUG_HIST */ 512231990Smp 513231990Smp#ifdef DEBUG_HIST 514231990Smpstatic void 515231990SmptestHash(void) 516231990Smp{ 517231990Smp static const Char STRtestHashTimings[] = 518231990Smp { 't','e','s','t','H','a','s','h','T','i','m','i','n','g','s', 0 }; 519231990Smp struct varent *vp = adrof(STRtestHashTimings); 520231990Smp if (vp && vp->vec) { 521231990Smp unsigned hashes[4]; /* dummy place to put hashes */ 522231990Smp Char **vals = vp->vec; 523231990Smp while (*vals) { 524231990Smp int length = getn(*vals); 525231990Smp unsigned words = 526231990Smp (length < 5) ? 1 : (length < 25) ? 2 : (length < 75) ? 3 : 4; 527231990Smp if (length > 0) 528231990Smp generateHashes(length, words, 0, hashes, 4); 529231990Smp vals++; 530231990Smp } 531231990Smp } 532231990Smp unsigned length = 1024; 533231990Smp#ifdef PRIME_LENGTH /* need good HTL */ 534231990Smp length = 1021; 535231990Smp#endif 536231990Smp unsigned *hashes = xmalloc(length*sizeof(unsigned)); 537231990Smp memset(hashes, 0, length*sizeof(unsigned)); 538231990Smp /* Compute collision statistics for half full hashes modulo "length". */ 539231990Smp generateHashes(4, 1, length/2, hashes, length); 540231990Smp /* Evaluate collisions by comparing occupancy rates (mean value 0.5). 541231990Smp * One bin for each number of hits. */ 542231990Smp unsigned bins[155]; 543231990Smp memset(bins, 0, sizeof(bins)); 544231990Smp unsigned highest = 0; 545231990Smp unsigned i; 546231990Smp for (i = 0; i<length; i++) { 547231990Smp unsigned hits = hashes[i]; 548231990Smp if (hits >= sizeof(bins)/sizeof(bins[0])) /* clip */ 549231990Smp hits = highest = sizeof(bins)/sizeof(bins[0]) - 1; 550231990Smp if (hits > highest) 551231990Smp highest = hits; 552231990Smp bins[hits]++; 553231990Smp } 554231990Smp xprintf("Occupancy of %d buckets by %d hashes %d Chars %d word with %s\n", 555231990Smp length, length/2, 4, 1, hashFcnName); 556231990Smp for (i = 0; i <= highest; i++) { 557231990Smp xprintf(" %d buckets (%d%%) with %d hits\n", 558231990Smp bins[i], bins[i]*100/length, i); 559231990Smp } 560231990Smp /* Count run lengths to evaluate linear rehashing effectiveness. Estimate 561231990Smp * a little corrupted by edge effects. */ 562231990Smp memset(bins, 0, sizeof(bins)); 563231990Smp highest = 0; 564231990Smp for (i = 0; hashes[i] == 0; i++); /* find first occupied bucket */ 565231990Smp unsigned run = 0; 566231990Smp unsigned rehashed = 0; 567231990Smp for (; i<length; i++) { 568231990Smp unsigned hits = hashes[i]; 569231990Smp if (hits == 0 && rehashed > 0) 570231990Smp hits = 1 && rehashed--; 571231990Smp else if (hits > 1) 572231990Smp rehashed += hits-1; 573231990Smp if (hits) 574231990Smp run++; 575231990Smp else { 576231990Smp /* a real free slot, count it */ 577231990Smp if (run >= sizeof(bins)/sizeof(bins[0])) /* clip */ 578231990Smp run = highest = sizeof(bins)/sizeof(bins[0]) - 1; 579231990Smp if (run > highest) 580231990Smp highest = run; 581231990Smp bins[run]++; 582231990Smp run = 0; 583231990Smp } 584231990Smp } 585231990Smp /* Ignore the partial run at end as we ignored the beginning. */ 586231990Smp double merit = 0.0, entries = 0; 587231990Smp for (i = 0; i <= highest; i++) { 588231990Smp entries += bins[i]*i; /* total hashed objects */ 589231990Smp merit += bins[i]*i*i; 590231990Smp } 591231990Smp xprintf("Rehash collision figure of merit %u (ideal=100), run lengths:\n", 592231990Smp (int)(100.0*merit/entries)); 593231990Smp for (i = 0; i <= highest; i++) { 594231990Smp if (bins[i] != 0) 595231990Smp xprintf(" %d runs of length %d buckets\n", bins[i], i); 596231990Smp } 597231990Smp xfree(hashes); 598231990Smp} 599231990Smp#endif /* DEBUG_HIST */ 600231990Smp 601231990Smp/* Compares two word lists for equality. */ 602145479Smpstatic int 603167465Smpheq(const struct wordent *a0, const struct wordent *b0) 60459243Sobrien{ 605167465Smp const struct wordent *a = a0->next, *b = b0->next; 60659243Sobrien 60759243Sobrien for (;;) { 60859243Sobrien if (Strcmp(a->word, b->word) != 0) 60959243Sobrien return 0; 61059243Sobrien a = a->next; 61159243Sobrien b = b->next; 61259243Sobrien if (a == a0) 61359243Sobrien return (b == b0) ? 1 : 0; 61459243Sobrien if (b == b0) 61559243Sobrien return 0; 616231990Smp } 61759243Sobrien} 61859243Sobrien 619231990Smp/* Renumber entries following p, which we will be deleting. */ 620231990SmpPG_STATIC void 621231990SmprenumberHist(struct Hist *p) 622231990Smp{ 623231990Smp int n = p->Href; 624231990Smp while ((p = p->Hnext)) 625231990Smp p->Href = n--; 626231990Smp} 62759243Sobrien 628231990Smp/* The hash table is implemented as an array of pointers to Hist entries. Each 629231990Smp * entry is located in the table using hash2tableIndex() and checking the 630231990Smp * following entries in case of a collision (linear rehash). Free entries in 631231990Smp * the table are zero (0, NULL, emptyHTE). Deleted entries that cannot yet be 632231990Smp * freed are set to one (deletedHTE). The Hist.Hhash member is non-zero iff 633231990Smp * the entry is in the hash table. When the hash table get too full, it is 634231990Smp * reallocated to be approximately twice the history length (see 635231990Smp * getHashTableSize). */ 636231990Smpstatic struct Hist **histHashTable = NULL; 637231990Smpstatic unsigned histHashTableLength = 0; /* number of Hist pointers in table */ 638231990Smp 639231990Smpstatic struct Hist * const emptyHTE = NULL; 640231990Smpstatic struct Hist * const deletedHTE = (struct Hist *)1; 641231990Smp 642231990Smpstatic struct { 643231990Smp unsigned insertCount; 644231990Smp unsigned removeCount; 645231990Smp unsigned rehashes; 646231990Smp int deleted; 647231990Smp} hashStats; 648231990Smp 649231990Smp#ifdef DEBUG_HIST 650231990Smpvoid 651231990SmpcheckHistHashTable(int print) 652231990Smp{ 653231990Smp unsigned occupied = 0; 654231990Smp unsigned deleted = 0; 655231990Smp unsigned i; 656231990Smp for (i = 0; i<histHashTableLength; i++) 657231990Smp if (histHashTable[i] == emptyHTE) 658231990Smp continue; 659231990Smp else if (histHashTable[i] == deletedHTE) 660231990Smp deleted++; 661231990Smp else 662231990Smp occupied++; 663231990Smp if (print) 664231990Smp xprintf(" found len %u occupied %u deleted %u\n", 665231990Smp histHashTableLength, occupied, deleted); 666231990Smp assert(deleted == hashStats.deleted); 667231990Smp} 668231990Smp 669231990Smpstatic int doneTest = 0; 670231990Smp 671231990Smp/* Main entry point for displaying history statistics and hash function 672231990Smp * behavior. */ 673231990Smpvoid 674231990SmpdisplayHistStats(const char *reason) 675231990Smp{ 676231990Smp /* Just hash statistics for now. */ 677231990Smp xprintf("%s history hash table len %u count %u (deleted %d)\n", reason, 678231990Smp histHashTableLength, histCount, hashStats.deleted); 679231990Smp xprintf(" inserts %u rehashes %u%% each\n", 680231990Smp hashStats.insertCount, 681231990Smp (hashStats.insertCount 682231990Smp ? 100*hashStats.rehashes/hashStats.insertCount : 0)); 683231990Smp xprintf(" removes %u net %u\n", 684231990Smp hashStats.removeCount, 685231990Smp hashStats.insertCount - hashStats.removeCount); 686231990Smp assert(hashStats.insertCount >= hashStats.removeCount); 687231990Smp checkHistHashTable(1); 688231990Smp memset(&hashStats, 0, sizeof(hashStats)); 689231990Smp if (!doneTest) { 690231990Smp testHash(); 691231990Smp doneTest = 1; 692231990Smp } 693231990Smp} 694231990Smp#else 695231990Smpvoid 696231990SmpdisplayHistStats(const char *reason) 697231990Smp{ 698231990Smp USE(reason); 699231990Smp} 700231990Smp#endif 701231990Smp 702231990Smpstatic void 703231990SmpdiscardHistHashTable(void) 704231990Smp{ 705231990Smp if (histHashTable == NULL) 706231990Smp return; 707231990Smp displayHistStats("Discarding"); 708231990Smp xfree(histHashTable); 709231990Smp histHashTable = NULL; 710231990Smp} 711231990Smp 712231990Smp/* Computes a new hash table size, when the current one is too small. */ 713231990Smpstatic unsigned 714231990SmpgetHashTableSize(int histlen) 715231990Smp{ 716231990Smp unsigned target = histlen * 2; 717231990Smp unsigned e = 5; 718231990Smp unsigned size; 719231990Smp while ((size = 1<<e) < target) 720231990Smp e++; 721231990Smp#ifdef PRIME_LENGTH /* need good HTL */ 722231990Smp /* Not all prime, but most are and none have factors smaller than 11. */ 723231990Smp return size+15; 724231990Smp#else 725231990Smp assert((size & (size-1)) == 0); /* must be a power of two */ 726231990Smp return size; 727231990Smp#endif 728231990Smp} 729231990Smp 730231990Smp/* Create the hash table or resize, if necessary. */ 731231990Smpstatic void 732231990SmpcreateHistHashTable(int histlen) 733231990Smp{ 734231990Smp if (histlen == 0) { 735231990Smp discardHistHashTable(); 736231990Smp return; 737231990Smp } 738231990Smp if (histlen < 0) { 739231990Smp histlen = getn(varval(STRhistory)); 740231990Smp if (histlen == 0) 741231990Smp return; /* no need for hash table */ 742231990Smp assert(histlen > 0); 743231990Smp } 744231990Smp if (histHashTable != NULL) { 745231990Smp if (histCount < histHashTableLength * 3 / 4) 746231990Smp return; /* good enough for now */ 747231990Smp discardHistHashTable(); /* too small */ 748231990Smp } 749231990Smp histHashTableLength = getHashTableSize( 750231990Smp histlen > (int)histCount ? histlen : (int)histCount); 751231990Smp histHashTable = xmalloc(histHashTableLength * sizeof(struct Hist *)); 752231990Smp memset(histHashTable, 0, histHashTableLength * sizeof(struct Hist *)); 753231990Smp assert(histHashTable[0] == emptyHTE); 754231990Smp 755231990Smp /* Now insert all the entries on the history list into the hash table. */ 756231990Smp { 757231990Smp struct Hist *hp; 758231990Smp for (hp = &Histlist; (hp = hp->Hnext) != NULL;) { 759231990Smp unsigned lpHash = hashhist(&hp->Hlex); 760231990Smp assert(!hp->Hhash || hp->Hhash == lpHash); 761231990Smp hp->Hhash = 0; /* force insert to new hash table */ 762231990Smp insertHistHashTable(hp, lpHash); 763231990Smp } 764231990Smp } 765231990Smp} 766231990Smp 767231990Smp/* Insert np into the hash table. We assume that np is already on the 768231990Smp * Histlist. The specified hashval matches the new Hist entry but has not yet 769231990Smp * been assigned to Hhash (or the element is already on the hash table). */ 770231990Smpstatic void 771231990SmpinsertHistHashTable(struct Hist *np, unsigned hashval) 772231990Smp{ 773231990Smp unsigned rehashes = 0; 774231990Smp unsigned hi = 0; 775231990Smp if (!histHashTable) 776231990Smp return; 777231990Smp if (np->Hhash != 0) { 778231990Smp /* already in hash table */ 779231990Smp assert(hashval == np->Hhash); 780231990Smp return; 781231990Smp } 782231990Smp assert(np != deletedHTE); 783231990Smp /* Find a free (empty or deleted) slot, using linear rehash. */ 784231990Smp assert(histHashTable); 785231990Smp for (rehashes = 0; 786231990Smp ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)), 787231990Smp histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE); 788231990Smp rehashes++) { 789231990Smp assert(np != histHashTable[hi]); 790231990Smp if (rehashes >= histHashTableLength / 10) { 791231990Smp /* Hash table is full, so grow it. We assume the create function 792231990Smp * will roughly double the size we give it. Create initializes the 793231990Smp * new table with everything on the Histlist, so we are done when 794231990Smp * it returns. */ 795231990Smp#ifdef DEBUG_HIST 796231990Smp xprintf("Growing history hash table from %d ...", 797231990Smp histHashTableLength); 798231990Smp flush(); 799231990Smp#endif 800231990Smp discardHistHashTable(); 801231990Smp createHistHashTable(histHashTableLength); 802231990Smp#ifdef DEBUG_HIST 803231990Smp xprintf("to %d.\n", histHashTableLength); 804231990Smp#endif 805231990Smp return; 806231990Smp } 807231990Smp } 808231990Smp /* Might be sensible to grow hash table if rehashes is "too big" here. */ 809231990Smp if (histHashTable[hi] == deletedHTE) 810231990Smp hashStats.deleted--; 811231990Smp histHashTable[hi] = np; 812231990Smp np->Hhash = hashval; 813231990Smp hashStats.insertCount++; 814231990Smp hashStats.rehashes += rehashes; 815231990Smp} 816231990Smp 817231990Smp/* Remove the 'np' entry from the hash table. */ 818231990Smpstatic void 819231990SmpremoveHistHashTable(struct Hist *np) 820231990Smp{ 821231990Smp unsigned hi = np->Hhash; 822231990Smp if (!histHashTable || !hi) 823231990Smp return; /* no hash table or not on it */ 824231990Smp /* find desired entry */ 825231990Smp while ((hi = hash2tableIndex(hi, histHashTableLength)), 826231990Smp histHashTable[hi] != emptyHTE) { 827231990Smp if (np == histHashTable[hi]) { 828231990Smp unsigned i; 829231990Smp unsigned deletes = 0; 830231990Smp histHashTable[hi] = deletedHTE; /* dummy, but non-zero entry */ 831231990Smp /* now peek ahead to see if the dummies are really necessary. */ 832231990Smp i = 1; 833231990Smp while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == 834231990Smp deletedHTE) 835231990Smp i++; 836231990Smp if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == 837231990Smp emptyHTE) { 838231990Smp /* dummies are no longer necessary placeholders. */ 839231990Smp deletes = i; 840231990Smp while (i-- > 0) { 841231990Smp histHashTable[hash2tableIndex(hi+i, histHashTableLength)] = 842231990Smp emptyHTE; 843231990Smp } 844231990Smp } 845231990Smp hashStats.deleted += 1 - deletes; /* delta deleted entries */ 846231990Smp hashStats.removeCount++; 847231990Smp return; 848231990Smp } 849231990Smp hi++; /* linear rehash */ 850231990Smp } 851231990Smp assert(!"Hist entry not found in hash table"); 852231990Smp} 853231990Smp 854231990Smp/* Search the history hash table for a command matching lp, using hashval as 855231990Smp * its hash value. */ 856231990Smpstatic struct Hist * 857231990SmpfindHistHashTable(struct wordent *lp, unsigned hashval) 858231990Smp{ 859231990Smp unsigned deleted = 0; /* number of deleted entries skipped */ 860231990Smp unsigned hi = hashval; 861231990Smp struct Hist *hp; 862231990Smp if (!histHashTable) 863231990Smp return NULL; 864231990Smp while ((hi = hash2tableIndex(hi, histHashTableLength)), 865231990Smp (hp = histHashTable[hi]) != emptyHTE) { 866231990Smp if (hp == deletedHTE) 867231990Smp deleted++; 868231990Smp else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex))) 869231990Smp return hp; 870231990Smp if (deleted > (histHashTableLength>>4)) { 871231990Smp /* lots of deletes, so we need a sparser table. */ 872231990Smp discardHistHashTable(); 873231990Smp createHistHashTable(histHashTableLength); 874231990Smp return findHistHashTable(lp, hashval); 875231990Smp } 876231990Smp hi++; /* linear rehash */ 877231990Smp } 878231990Smp return NULL; 879231990Smp} 880231990Smp 881231990Smp/* When merge semantics are in use, find the approximate predecessor for the 882231990Smp * new entry, so that the Htime entries are decreasing. Return the entry just 883231990Smp * before the first entry with equal times, so the caller can check for 884231990Smp * duplicates. When pTime is not NULL, use it as a starting point for search, 885231990Smp * otherwise search from beginning (largest time value) of history list. */ 886231990SmpPG_STATIC struct Hist * 887231990SmpmergeInsertionPoint( 888231990Smp struct Hist *np, /* new entry to be inserted */ 889231990Smp struct Hist *pTime) /* hint about where to insert */ 890231990Smp{ 891231990Smp struct Hist *pp, *p; 892231990Smp if (histTail && histTail->Htime >= np->Htime) 893231990Smp pTime = histTail; /* new entry goes at the end */ 894231990Smp if (histMerg && histMerg != &Histlist && histMerg != Histlist.Hnext) { 895231990Smp /* Check above and below previous insertion point, in case we're adding 896231990Smp * sequential times in the middle of the list (e.g. history -M). */ 897231990Smp if (histMerg->Htime >= np->Htime) 898231990Smp pTime = histMerg; 899231990Smp else if (histMerg->Hprev->Htime >= np->Htime) 900231990Smp pTime = histMerg->Hprev; 901231990Smp } 902231990Smp if (pTime) { 903231990Smp /* With hint, search up the list until Htime is greater. We skip past 904231990Smp * the equal ones, too, so our caller can elide duplicates. */ 905231990Smp pp = pTime; 906231990Smp while (pp != &Histlist && pp->Htime <= np->Htime) 907231990Smp pp = pp->Hprev; 908231990Smp } else 909231990Smp pp = &Histlist; 910231990Smp /* Search down the list while current entry's time is too large. */ 911231990Smp while ((p = pp->Hnext) && (p->Htime > np->Htime)) 912231990Smp pp = p; /* advance insertion point */ 913231990Smp /* Remember recent position as hint for next time */ 914231990Smp histMerg = pp; 915231990Smp return pp; 916231990Smp} 917231990Smp 918231990Smp/* Bubble Hnum & Href in new entry down to pp through earlier part of list. */ 919231990SmpPG_STATIC void bubbleHnumHrefDown(struct Hist *np, struct Hist *pp) 920231990Smp{ 921231990Smp struct Hist *p; 922231990Smp for (p = Histlist.Hnext; p != pp->Hnext; p = p->Hnext) { 923231990Smp /* swap Hnum & Href values of p and np. */ 924231990Smp int n = p->Hnum, r = p->Href; 925231990Smp p->Hnum = np->Hnum; p->Href = np->Href; 926231990Smp np->Hnum = n; np->Href = r; 927231990Smp } 928231990Smp} 929231990Smp 930231990Smp/* Enter new command into the history list according to current settings. */ 93159243Sobrienstruct Hist * 932231990Smpenthist( 933231990Smp int event, /* newly incremented global eventno */ 934231990Smp struct wordent *lp, 935231990Smp int docopy, 936231990Smp int mflg, /* true if merge requested */ 937231990Smp int histlen) /* -1 if unknown */ 93859243Sobrien{ 939231990Smp struct Hist *p = NULL, *pp = &Histlist, *pTime = NULL; 940145479Smp struct Hist *np; 941167465Smp const Char *dp; 942231990Smp unsigned lpHash = 0; /* non-zero if hashing entries */ 943231990Smp 94459243Sobrien if ((dp = varval(STRhistdup)) != STRNULL) { 94559243Sobrien if (eq(dp, STRerase)) { 94659243Sobrien /* masaoki@akebono.tky.hp.com (Kobayashi Masaoki) */ 947231990Smp createHistHashTable(histlen); 948231990Smp lpHash = hashhist(lp); 949231990Smp assert(lpHash != 0); 950231990Smp p = findHistHashTable(lp, lpHash); 951231990Smp if (p) { 952231990Smp if (Htime != 0 && p->Htime > Htime) 953231990Smp Htime = p->Htime; 954231990Smp /* If we are merging, and the old entry is at the place we want 955231990Smp * to insert the new entry, then remember the place. */ 956231990Smp if (mflg && Htime != 0 && p->Hprev->Htime >= Htime) 957231990Smp pTime = p->Hprev; 958231990Smp if (!fastMergeErase) 959231990Smp renumberHist(p); /* Reset Href of subsequent entries */ 960231990Smp hremove(p); 961231990Smp hfree(p); 962231990Smp p = NULL; /* so new entry is allocated below */ 963231990Smp } 96459243Sobrien } 96559243Sobrien else if (eq(dp, STRall)) { 966231990Smp createHistHashTable(histlen); 967231990Smp lpHash = hashhist(lp); 968231990Smp assert(lpHash != 0); 969231990Smp p = findHistHashTable(lp, lpHash); 970231990Smp if (p) /* p!=NULL, only update this entry's Htime below */ 971231990Smp eventno--; /* not adding a new event */ 97259243Sobrien } 97359243Sobrien else if (eq(dp, STRprev)) { 97459243Sobrien if (pp->Hnext && heq(lp, &(pp->Hnext->Hlex))) { 97559243Sobrien p = pp->Hnext; 97659243Sobrien eventno--; 97759243Sobrien } 97859243Sobrien } 97959243Sobrien } 98059243Sobrien 981167465Smp np = p ? p : xmalloc(sizeof(*np)); 98259243Sobrien 98359243Sobrien /* Pick up timestamp set by lex() in Htime if reading saved history */ 984167465Smp if (Htime != 0) { 98559243Sobrien np->Htime = Htime; 98659243Sobrien Htime = 0; 98759243Sobrien } 98859243Sobrien else 989231990Smp (void) time(&(np->Htime)); 99059243Sobrien 99159243Sobrien if (p == np) 992231990Smp return np; /* reused existing entry */ 99359243Sobrien 994231990Smp /* Initialize the new entry. */ 99559243Sobrien np->Hnum = np->Href = event; 99659243Sobrien if (docopy) { 997231990Smp copylex(&np->Hlex, lp); 99859243Sobrien if (histvalid) 999167465Smp np->histline = Strsave(histline.s); 100059243Sobrien else 100159243Sobrien np->histline = NULL; 100259243Sobrien } 100359243Sobrien else { 100459243Sobrien np->Hlex.next = lp->next; 100559243Sobrien lp->next->prev = &np->Hlex; 100659243Sobrien np->Hlex.prev = lp->prev; 1007231990Smp lp->prev->next = &np->Hlex; 1008231990Smp np->histline = NULL; 100959243Sobrien } 1010231990Smp np->Hhash = 0; 1011231990Smp 1012231990Smp /* The head of history list is the default insertion point. 1013231990Smp If merging, advance insertion point, in pp, according to Htime. */ 1014231990Smp /* XXX -- In histdup=all, Htime values can be non-monotonic. */ 1015231990Smp if (mflg) { /* merge according to np->Htime */ 1016231990Smp pp = mergeInsertionPoint(np, pTime); 1017231990Smp for (p = pp->Hnext; p && p->Htime == np->Htime; pp = p, p = p->Hnext) { 1018231990Smp if (heq(&p->Hlex, &np->Hlex)) { 1019231990Smp eventno--; /* duplicate, so don't add new event */ 1020231990Smp hfree(np); 1021231990Smp return (p); 1022231990Smp } 1023231990Smp } 1024231990Smp /* pp is now the last entry with time >= to np. */ 1025231990Smp if (!fastMergeErase) { /* renumber at end of loadhist */ 1026231990Smp /* Before inserting np after pp, bubble its Hnum & Href values down 1027231990Smp * through the earlier part of list. */ 1028231990Smp bubbleHnumHrefDown(np, pp); 1029231990Smp } 1030231990Smp } 1031231990Smp else 1032231990Smp pp = &Histlist; /* insert at beginning of history */ 1033231990Smp hinsert(np, pp); 1034231990Smp if (lpHash && histlen != 0) /* erase & all modes use hash table */ 1035231990Smp insertHistHashTable(np, lpHash); 1036231990Smp else 1037231990Smp discardHistHashTable(); 103859243Sobrien return (np); 103959243Sobrien} 104059243Sobrien 104159243Sobrienstatic void 1042167465Smphfree(struct Hist *hp) 104359243Sobrien{ 1044231990Smp assert(hp != histMerg); 1045231990Smp if (hp->Hhash) 1046231990Smp removeHistHashTable(hp); 104759243Sobrien freelex(&hp->Hlex); 104859243Sobrien if (hp->histline) 1049231990Smp xfree(hp->histline); 1050167465Smp xfree(hp); 105159243Sobrien} 105259243Sobrien 1053231990SmpPG_STATIC void 1054231990Smpphist(struct Hist *hp, int hflg) 1055231990Smp{ 1056231990Smp if (hflg & HIST_ONLY) { 1057231990Smp int old_output_raw; 105859243Sobrien 1059231990Smp /* 1060231990Smp * Control characters have to be written as is (output_raw). 1061231990Smp * This way one can preserve special characters (like tab) in 1062231990Smp * the history file. 1063231990Smp * From: mveksler@vnet.ibm.com (Veksler Michael) 1064231990Smp */ 1065231990Smp old_output_raw = output_raw; 1066231990Smp output_raw = 1; 1067231990Smp cleanup_push(&old_output_raw, output_raw_restore); 1068231990Smp if (hflg & HIST_TIME) 1069231990Smp /* 1070231990Smp * Make file entry with history time in format: 1071231990Smp * "+NNNNNNNNNN" (10 digits, left padded with ascii '0') 1072231990Smp */ 1073231990Smp 1074231990Smp xprintf("#+%010lu\n", (unsigned long)hp->Htime); 1075231990Smp 1076231990Smp if (HistLit && hp->histline) 1077231990Smp xprintf("%S\n", hp->histline); 1078231990Smp else 1079231990Smp prlex(&hp->Hlex); 1080231990Smp cleanup_until(&old_output_raw); 1081231990Smp } 1082231990Smp else { 1083231990Smp Char *cp = str2short("%h\t%T\t%R\n"); 1084231990Smp Char *p; 1085231990Smp struct varent *vp = adrof(STRhistory); 1086231990Smp 1087231990Smp if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1]) 1088231990Smp cp = vp->vec[1]; 1089231990Smp 1090231990Smp p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp); 1091231990Smp cleanup_push(p, xfree); 1092231990Smp for (cp = p; *cp;) 1093231990Smp xputwchar(*cp++); 1094231990Smp cleanup_until(p); 1095231990Smp } 1096231990Smp} 1097231990Smp 1098231990SmpPG_STATIC void 1099231990Smpdophist(int n, int hflg) 1100231990Smp{ 1101231990Smp struct Hist *hp; 1102231990Smp if (setintr) { 1103231990Smp int old_pintr_disabled; 1104231990Smp 1105231990Smp pintr_push_enable(&old_pintr_disabled); 1106231990Smp cleanup_until(&old_pintr_disabled); 1107231990Smp } 1108231990Smp if ((hflg & HIST_REV) == 0) { 1109231990Smp /* Since the history list is stored most recent first, non-reversing 1110231990Smp * print needs to print (backwards) up the list. */ 1111231990Smp if ((unsigned)n >= histCount) 1112231990Smp hp = histTail; 1113231990Smp else { 1114231990Smp for (hp = Histlist.Hnext; 1115231990Smp --n > 0 && hp->Hnext != NULL; 1116231990Smp hp = hp->Hnext) 1117231990Smp ; 1118231990Smp } 1119231990Smp if (hp == NULL) 1120231990Smp return; /* nothing to print */ 1121231990Smp for (; hp != &Histlist; hp = hp->Hprev) 1122231990Smp phist(hp, hflg); 1123231990Smp } else { 1124231990Smp for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext) 1125231990Smp phist(hp, hflg); 1126231990Smp } 1127231990Smp} 1128231990Smp 112959243Sobrien/*ARGSUSED*/ 113059243Sobrienvoid 1131167465Smpdohist(Char **vp, struct command *c) 113259243Sobrien{ 113359243Sobrien int n, hflg = 0; 113459243Sobrien 113559243Sobrien USE(c); 113659243Sobrien if (getn(varval(STRhistory)) == 0) 113759243Sobrien return; 113859243Sobrien while (*++vp && **vp == '-') { 113959243Sobrien Char *vp2 = *vp; 114059243Sobrien 114159243Sobrien while (*++vp2) 114259243Sobrien switch (*vp2) { 114359243Sobrien case 'c': 114459243Sobrien hflg |= HIST_CLEAR; 114559243Sobrien break; 114659243Sobrien case 'h': 114759243Sobrien hflg |= HIST_ONLY; 114859243Sobrien break; 114959243Sobrien case 'r': 115059243Sobrien hflg |= HIST_REV; 115159243Sobrien break; 115259243Sobrien case 'S': 115359243Sobrien hflg |= HIST_SAVE; 115459243Sobrien break; 115559243Sobrien case 'L': 115659243Sobrien hflg |= HIST_LOAD; 115759243Sobrien break; 115859243Sobrien case 'M': 115959243Sobrien hflg |= HIST_MERGE; 116059243Sobrien break; 116159243Sobrien case 'T': 116259243Sobrien hflg |= HIST_TIME; 116359243Sobrien break; 116459243Sobrien default: 116559243Sobrien stderror(ERR_HISTUS, "chrSLMT"); 116659243Sobrien break; 116759243Sobrien } 116859243Sobrien } 116959243Sobrien if (hflg & HIST_CLEAR) { 1170231990Smp struct Hist *np, *hp; 1171231990Smp for (hp = &Histlist; (np = hp->Hnext) != NULL;) 1172231990Smp hremove(np), hfree(np); 117359243Sobrien } 117459243Sobrien 1175167465Smp if (hflg & (HIST_LOAD | HIST_MERGE)) 117659243Sobrien loadhist(*vp, (hflg & HIST_MERGE) ? 1 : 0); 1177167465Smp else if (hflg & HIST_SAVE) 117859243Sobrien rechist(*vp, 1); 117959243Sobrien else { 1180167465Smp if (*vp) 1181167465Smp n = getn(*vp); 1182167465Smp else { 1183167465Smp n = getn(varval(STRhistory)); 1184167465Smp } 1185231990Smp dophist(n, hflg); 118659243Sobrien } 118759243Sobrien} 118859243Sobrien 118959243Sobrien 1190167465Smpchar * 1191167465Smpfmthist(int fmt, ptr_t ptr) 1192167465Smp{ 1193167465Smp struct Hist *hp = ptr; 119459243Sobrien char *buf; 1195167465Smp 119659243Sobrien switch (fmt) { 119759243Sobrien case 'h': 1198167465Smp return xasprintf("%6d", hp->Hnum); 119959243Sobrien case 'R': 120059243Sobrien if (HistLit && hp->histline) 1201167465Smp return xasprintf("%S", hp->histline); 120259243Sobrien else { 1203167465Smp Char *istr, *ip; 120459243Sobrien char *p; 1205145479Smp 1206167465Smp istr = sprlex(&hp->Hlex); 1207167465Smp buf = xmalloc(Strlen(istr) * MB_LEN_MAX + 1); 1208167465Smp 1209167465Smp for (p = buf, ip = istr; *ip != '\0'; ip++) 1210167465Smp p += one_wctomb(p, CHAR & *ip); 1211167465Smp 1212167465Smp *p = '\0'; 1213167465Smp xfree(istr); 1214167465Smp return buf; 121559243Sobrien } 121659243Sobrien default: 1217167465Smp buf = xmalloc(1); 121859243Sobrien buf[0] = '\0'; 1219167465Smp return buf; 122059243Sobrien } 122159243Sobrien} 122259243Sobrien 1223231990Smp/* Save history before exiting the shell. */ 122459243Sobrienvoid 1225167465Smprechist(Char *fname, int ref) 122659243Sobrien{ 122759243Sobrien Char *snum; 122859243Sobrien int fp, ftmp, oldidfds; 122959243Sobrien struct varent *shist; 123059243Sobrien static Char *dumphist[] = {STRhistory, STRmhT, 0, 0}; 123159243Sobrien 123259243Sobrien if (fname == NULL && !ref) 123359243Sobrien return; 123459243Sobrien /* 123559243Sobrien * If $savehist is just set, we use the value of $history 123659243Sobrien * else we use the value in $savehist 123759243Sobrien */ 123859243Sobrien if (((snum = varval(STRsavehist)) == STRNULL) && 123959243Sobrien ((snum = varval(STRhistory)) == STRNULL)) 124059243Sobrien snum = STRmaxint; 124159243Sobrien 124259243Sobrien 124359243Sobrien if (fname == NULL) { 124459243Sobrien if ((fname = varval(STRhistfile)) == STRNULL) 124559243Sobrien fname = Strspl(varval(STRhome), &STRtildothist[1]); 124659243Sobrien else 124759243Sobrien fname = Strsave(fname); 124859243Sobrien } 124959243Sobrien else 125059243Sobrien fname = globone(fname, G_ERROR); 1251167465Smp cleanup_push(fname, xfree); 125259243Sobrien 125359243Sobrien /* 125459243Sobrien * The 'savehist merge' feature is intended for an environment 1255167465Smp * with numerous shells being in simultaneous use. Imagine 125659243Sobrien * any kind of window system. All these shells 'share' the same 125759243Sobrien * ~/.history file for recording their command line history. 125859243Sobrien * Currently the automatic merge can only succeed when the shells 125959243Sobrien * nicely quit one after another. 126059243Sobrien * 126159243Sobrien * Users that like to nuke their environment require here an atomic 126259243Sobrien * loadhist-creat-dohist(dumphist)-close 126359243Sobrien * sequence. 126459243Sobrien * 126559243Sobrien * jw. 126659243Sobrien */ 126759243Sobrien /* 126859243Sobrien * We need the didfds stuff before loadhist otherwise 126959243Sobrien * exec in a script will fail to print if merge is set. 127059243Sobrien * From: mveksler@iil.intel.com (Veksler Michael) 127159243Sobrien */ 127259243Sobrien oldidfds = didfds; 127359243Sobrien didfds = 0; 1274100616Smp if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL) 127559243Sobrien if (shist->vec[1] && eq(shist->vec[1], STRmerge)) 127659243Sobrien loadhist(fname, 1); 1277231990Smp 1278167465Smp fp = xcreat(short2str(fname), 0600); 1279231990Smp cleanup_until(fname); 128059243Sobrien if (fp == -1) { 128159243Sobrien didfds = oldidfds; 128259243Sobrien return; 128359243Sobrien } 128459243Sobrien ftmp = SHOUT; 128559243Sobrien SHOUT = fp; 128659243Sobrien dumphist[2] = snum; 128759243Sobrien dohist(dumphist, NULL); 1288167465Smp xclose(fp); 128959243Sobrien SHOUT = ftmp; 129059243Sobrien didfds = oldidfds; 129159243Sobrien} 129259243Sobrien 129359243Sobrien 1294231990Smp/* This is the entry point for loading history data from a file. */ 129559243Sobrienvoid 1296167465Smploadhist(Char *fname, int mflg) 129759243Sobrien{ 129859243Sobrien static Char *loadhist_cmd[] = {STRsource, NULL, NULL, NULL}; 129959243Sobrien loadhist_cmd[1] = mflg ? STRmm : STRmh; 130059243Sobrien 130159243Sobrien if (fname != NULL) 130259243Sobrien loadhist_cmd[2] = fname; 130359243Sobrien else if ((fname = varval(STRhistfile)) != STRNULL) 130459243Sobrien loadhist_cmd[2] = fname; 130559243Sobrien else 130659243Sobrien loadhist_cmd[2] = STRtildothist; 130759243Sobrien 130859243Sobrien dosource(loadhist_cmd, NULL); 1309231990Smp 1310231990Smp /* During history merging (enthist sees mflg set), we disable management of 1311231990Smp * Hnum and Href (because fastMergeErase is true). So now reset all the 1312231990Smp * values based on the final ordering of the history list. */ 1313231990Smp if (mflg) { 1314231990Smp int n = eventno; 1315231990Smp struct Hist *hp = &Histlist; 1316231990Smp while ((hp = hp->Hnext)) 1317231990Smp hp->Hnum = hp->Href = n--; 1318231990Smp } 131959243Sobrien} 1320