1232633Smp/* $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 35232633SmpRCSID("$tcsh: sh.hist.c,v 3.53 2011/01/24 18:10:26 christos Exp $") 3659243Sobrien 37232633Smp#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 59232633Smp/* Static functions don't show up in gprof summaries. So eliminate "static" 60232633Smp * modifier from some frequently called functions. */ 61232633Smp#ifdef PROF 62232633Smp#define PG_STATIC 63232633Smp#else 64232633Smp#define PG_STATIC static 65232633Smp#endif 66232633Smp 67232633Smp/* #define DEBUG_HIST 1 */ 68232633Smp 69232633Smpstatic const int fastMergeErase = 1; 70232633Smpstatic unsigned histCount = 0; /* number elements on history list */ 71232633Smpstatic struct Hist *histTail = NULL; /* last element on history list */ 72232633Smpstatic struct Hist *histMerg = NULL; /* last element merged by Htime */ 73232633Smp 74232633Smpstatic void insertHistHashTable(struct Hist *, unsigned); 75232633Smp 76232633Smp 77232633Smp/* Insert new element (hp) in history list after specified predecessor (pp). */ 78232633Smpstatic void 79232633Smphinsert(struct Hist *hp, struct Hist *pp) 80232633Smp{ 81232633Smp struct Hist *fp = pp->Hnext; /* following element, if any */ 82232633Smp hp->Hnext = fp, hp->Hprev = pp; 83232633Smp pp->Hnext = hp; 84232633Smp if (fp) 85232633Smp fp->Hprev = hp; 86232633Smp else 87232633Smp histTail = hp; /* meaning hp->Hnext == NULL */ 88232633Smp histCount++; 89232633Smp} 90232633Smp 91232633Smp/* Remove the entry from the history list. */ 92232633Smpstatic void 93232633Smphremove(struct Hist *hp) 94232633Smp{ 95232633Smp struct Hist *pp = hp->Hprev; 96232633Smp assert(pp); /* elements always have a previous */ 97232633Smp pp->Hnext = hp->Hnext; 98232633Smp if (hp->Hnext) 99232633Smp hp->Hnext->Hprev = pp; 100232633Smp else 101232633Smp histTail = pp; /* we must have been last */ 102232633Smp if (hp == histMerg) /* deleting this hint from list */ 103232633Smp histMerg = NULL; 104232633Smp assert(histCount > 0); 105232633Smp histCount--; 106232633Smp} 107232633Smp 108232633Smp/* Prune length of history list to specified size by history variable. */ 109232633SmpPG_STATIC void 110232633SmpdiscardExcess(int histlen) 111232633Smp{ 112232633Smp struct Hist *hp, *np; 113232633Smp if (histTail == NULL) { 114232633Smp assert(histCount == 0); 115232633Smp return; /* no entries on history list */ 116232633Smp } 117232633Smp /* Prune dummy entries from the front, then old entries from the back. If 118232633Smp * the list is still too long scan the whole list as before. But only do a 119232633Smp * full scan if the list is more than 6% (1/16th) too long. */ 120232633Smp while (histCount > (unsigned)histlen && (np = Histlist.Hnext)) { 121232633Smp if (eventno - np->Href >= histlen || histlen == 0) 122232633Smp hremove(np), hfree(np); 123232633Smp else 124232633Smp break; 125232633Smp } 126232633Smp while (histCount > (unsigned)histlen && (np = histTail) != &Histlist) { 127232633Smp if (eventno - np->Href >= histlen || histlen == 0) 128232633Smp hremove(np), hfree(np); 129232633Smp else 130232633Smp break; 131232633Smp } 132232633Smp if (histCount - (histlen >> 4) <= (unsigned)histlen) 133232633Smp return; /* don't bother doing the full scan */ 134232633Smp for (hp = &Histlist; histCount > (unsigned)histlen && 135232633Smp (np = hp->Hnext) != NULL;) 136232633Smp if (eventno - np->Href >= histlen || histlen == 0) 137232633Smp hremove(np), hfree(np); 138232633Smp else 139232633Smp hp = np; 140232633Smp} 141232633Smp 142232633Smp/* Add the command "sp" to the history list. */ 14359243Sobrienvoid 144232633Smpsavehist( 145232633Smp struct wordent *sp, 146232633Smp 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) 163232633Smp (void) enthist(++eventno, sp, 1, mflg, histlen); 164232633Smp discardExcess(histlen); 16559243Sobrien} 16659243Sobrien 167232633Smp#define USE_JENKINS_HASH 1 168232633Smp/* #define USE_ONE_AT_A_TIME 1 */ 169232633Smp#undef PRIME_LENGTH /* no need for good HTL */ 170232633Smp 171232633Smp#ifdef USE_JENKINS_HASH 172232633Smp#define hashFcnName "lookup3" 173232633Smp/* From: 174232633Smp lookup3.c, by Bob Jenkins, May 2006, Public Domain. 175232633Smp "... You can use this free for any purpose. It's in 176232633Smp the public domain. It has no warranty." 177232633Smp http://burtleburtle.net/bob/hash/index.html 178232633Smp */ 179232633Smp 180232633Smp#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 181232633Smp#define mix(a,b,c) \ 182232633Smp{ \ 183232633Smp a -= c; a ^= rot(c, 4); c += b; \ 184232633Smp b -= a; b ^= rot(a, 6); a += c; \ 185232633Smp c -= b; c ^= rot(b, 8); b += a; \ 186232633Smp a -= c; a ^= rot(c,16); c += b; \ 187232633Smp b -= a; b ^= rot(a,19); a += c; \ 188232633Smp c -= b; c ^= rot(b, 4); b += a; \ 189232633Smp} 190232633Smp#define final(a,b,c) \ 191232633Smp{ \ 192232633Smp c ^= b; c -= rot(b,14); \ 193232633Smp a ^= c; a -= rot(c,11); \ 194232633Smp b ^= a; b -= rot(a,25); \ 195232633Smp c ^= b; c -= rot(b,16); \ 196232633Smp a ^= c; a -= rot(c, 4); \ 197232633Smp b ^= a; b -= rot(a,14); \ 198232633Smp c ^= b; c -= rot(b,24); \ 199232633Smp} 200232633Smp 201232633Smpstruct hashValue /* State used to hash a wordend word list. */ 202232633Smp{ 203232633Smp uint32_t a, b, c; 204232633Smp}; 205232633Smp 206232633Smp/* Set up the internal state */ 207232633Smpstatic void 208232633SmpinitializeHash(struct hashValue *h) 209232633Smp{ 210232633Smp h->a = h->b = h->c = 0xdeadbeef; 211232633Smp} 212232633Smp 213232633Smp/* This does a partial hash of the Chars in a single word. For efficiency we 214232633Smp * include 3 versions of the code to pack Chars into 32-bit words for the 215232633Smp * mixing function. */ 216232633Smpstatic void 217232633SmpaddWordToHash(struct hashValue *h, const Char *word) 218232633Smp{ 219232633Smp uint32_t a = h->a, b = h->b, c = h->c; 220232633Smp#ifdef SHORT_STRINGS 221232633Smp#ifdef WIDE_STRINGS 222232633Smp assert(sizeof(Char) >= 4); 223232633Smp while (1) { 224232633Smp unsigned k; 225232633Smp if ((k = (uChar)*word++) == 0) break; a += k; 226232633Smp if ((k = (uChar)*word++) == 0) break; b += k; 227232633Smp if ((k = (uChar)*word++) == 0) break; c += k; 228232633Smp mix(a, b, c); 229232633Smp } 230232633Smp#else 231232633Smp assert(sizeof(Char) == 2); 232232633Smp while (1) { 233232633Smp unsigned k; 234232633Smp if ((k = (uChar)*word++) == 0) break; a += k; 235232633Smp if ((k = (uChar)*word++) == 0) break; a += k << 16; 236232633Smp if ((k = (uChar)*word++) == 0) break; b += k; 237232633Smp if ((k = (uChar)*word++) == 0) break; b += k << 16; 238232633Smp if ((k = (uChar)*word++) == 0) break; c += k; 239232633Smp if ((k = (uChar)*word++) == 0) break; c += k << 16; 240232633Smp mix(a, b, c); 241232633Smp } 242232633Smp#endif 243232633Smp#else 244232633Smp assert(sizeof(Char) == 1); 245232633Smp while (1) { 246232633Smp unsigned k; 247232633Smp if ((k = *word++) == 0) break; a += k; 248232633Smp if ((k = *word++) == 0) break; a += k << 8; 249232633Smp if ((k = *word++) == 0) break; a += k << 16; 250232633Smp if ((k = *word++) == 0) break; a += k << 24; 251232633Smp if ((k = *word++) == 0) break; b += k; 252232633Smp if ((k = *word++) == 0) break; b += k << 8; 253232633Smp if ((k = *word++) == 0) break; b += k << 16; 254232633Smp if ((k = *word++) == 0) break; b += k << 24; 255232633Smp if ((k = *word++) == 0) break; c += k; 256232633Smp if ((k = *word++) == 0) break; c += k << 8; 257232633Smp if ((k = *word++) == 0) break; c += k << 16; 258232633Smp if ((k = *word++) == 0) break; c += k << 24; 259232633Smp mix(a, b, c); 260232633Smp } 261232633Smp#endif 262232633Smp h->a = a, h->b = b, h->c = c; 263232633Smp} 264232633Smp 265232633Smpstatic void 266232633SmpaddCharToHash(struct hashValue *h, Char ch) 267232633Smp{ 268232633Smp /* The compiler (gcc -O2) seems to do a good job optimizing this without 269232633Smp * explicitly extracting into local variables. */ 270232633Smp h->a += (uChar)ch; 271232633Smp mix(h->a, h->b, h->c); 272232633Smp} 273232633Smp 274232633Smpstatic uint32_t 275232633SmpfinalizeHash(struct hashValue *h) 276232633Smp{ 277232633Smp uint32_t a = h->a, b = h->b, c = h->c; 278232633Smp final(a, b, c); 279232633Smp return c; 280232633Smp} 281232633Smp 282232633Smp#elif USE_ONE_AT_A_TIME 283232633Smp#define hashFcnName "one-at-a-time" 284232633Smp/* This one is also from Bob Jenkins, but is slower but simpler than lookup3. 285232633Smp "... The code given here are all public domain." 286232633Smp http://burtleburtle.net/bob/hash/doobs.html */ 287232633Smp 288232633Smp#if 0 289232633Smpub4 290232633Smpone_at_a_time(char *key, ub4 len) 291232633Smp{ 292232633Smp ub4 hash, i; 293232633Smp for (hash=0, i=0; i<len; ++i) 294232633Smp { 295232633Smp hash += key[i]; 296232633Smp hash += (hash << 10); 297232633Smp hash ^= (hash >> 6); 298232633Smp } 299232633Smp hash += (hash << 3); 300232633Smp hash ^= (hash >> 11); 301232633Smp hash += (hash << 15); 302232633Smp return (hash & mask); 303232633Smp} 304232633Smp#endif 305232633Smp 306232633Smpstruct hashValue { uint32_t h; }; 307232633Smpstatic void 308232633SmpinitializeHash(struct hashValue *h) 309232633Smp{ 310232633Smp h->h = 0; 311232633Smp} 312232633Smp 313232633Smpstatic void 314232633SmpaddWordToHash(struct hashValue *h, const Char *word) 315232633Smp{ 316232633Smp unsigned k; 317232633Smp uint32_t hash = h->h; 318232633Smp while (k = (uChar)*word++) 319232633Smp hash += k, hash += hash << 10, hash ^= hash >> 6; 320232633Smp h->h = hash; 321232633Smp} 322232633Smp 323232633Smpstatic void 324232633SmpaddCharToHash(struct hashValue *h, Char c) 325232633Smp{ 326232633Smp Char b[2] = { c, 0 }; 327232633Smp addWordToHash(h, b); 328232633Smp} 329232633Smp 330232633Smpstatic uint32_t 331232633SmpfinalizeHash(struct hashValue *h) 332232633Smp{ 333232633Smp unsigned hash = h->h; 334232633Smp hash += (hash << 3); 335232633Smp hash ^= (hash >> 11); 336232633Smp hash += (hash << 15); 337232633Smp return hash; 338232633Smp} 339232633Smp 340232633Smp#else 341232633Smp#define hashFcnName "add-mul" 342232633Smp/* Simple multipy and add hash. */ 343232633Smp#define PRIME_LENGTH 1 /* need "good" HTL */ 344232633Smpstruct hashValue { uint32_t h; }; 345232633Smpstatic void 346232633SmpinitializeHash(struct hashValue *h) 347232633Smp{ 348232633Smp h->h = 0xe13e2345; 349232633Smp} 350232633Smp 351232633Smpstatic void 352232633SmpaddWordToHash(struct hashValue *h, const Char *word) 353232633Smp{ 354232633Smp unsigned k; 355232633Smp uint32_t hash = h->h; 356232633Smp while (k = (uChar)*word++) 357232633Smp hash = hash * 0x9e4167b9 + k; 358232633Smp h->h = hash; 359232633Smp} 360232633Smp 361232633Smpstatic void 362232633SmpaddCharToHash(struct hashValue *h, Char c) 363232633Smp{ 364232633Smp h->h = h->h * 0x9e4167b9 + (uChar)c; 365232633Smp} 366232633Smp 367232633Smpstatic uint32_t 368232633SmpfinalizeHash(struct hashValue *h) 369232633Smp{ 370232633Smp return h->h; 371232633Smp} 372232633Smp#endif 373232633Smp 374232633Smpstatic unsigned 375232633Smphashhist(struct wordent *h0) 376232633Smp{ 377232633Smp struct hashValue s; 378232633Smp struct wordent *firstWord = h0->next; 379232633Smp struct wordent *h = firstWord; 380232633Smp unsigned hash = 0; 381232633Smp 382232633Smp initializeHash(&s); 383232633Smp for (; h != h0; h = h->next) { 384232633Smp if (h->word[0] == '\n') 385232633Smp break; /* don't hash newline */ 386232633Smp if (h != firstWord) 387232633Smp addCharToHash(&s, ' '); /* space between words */ 388232633Smp addWordToHash(&s, h->word); 389232633Smp } 390232633Smp hash = finalizeHash(&s); 391232633Smp /* Zero means no hash value, so never return zero as a hash value. */ 392232633Smp return hash ? hash : 0x7fffffff; /* prime! */ 393232633Smp} 394232633Smp 395232633Smp#if 0 396232633Smpunsigned 397232633SmphashStr(Char *str) 398232633Smp{ 399232633Smp struct hashValue s; 400232633Smp initializeHash(&s); 401232633Smp addWordToHash(&s, str); 402232633Smp return finalizeHash(&s); 403232633Smp} 404232633Smp#endif 405232633Smp 406232633Smp#ifdef PRIME_LENGTH /* need good HTL */ 407232633Smp#define hash2tableIndex(hash, len) ((hash) % len) 408232633Smp#else 409232633Smp#define hash2tableIndex(hash, len) ((hash) & (len-1)) 410232633Smp#endif 411232633Smp 412232633Smp/* This code can be enabled to test the above hash functions for speed and 413232633Smp * collision avoidance. The testing is enabled by "occasional" calls to 414232633Smp * displayHistStats(), see which. */ 415232633Smp#ifdef DEBUG_HIST 416232633Smp 417232633Smp#ifdef BSDTIMES 418232633Smpstatic double 419232633SmpdoTiming(int start) { 420232633Smp static struct timeval beginTime; 421232633Smp if (start) { 422232633Smp gettimeofday(&beginTime, NULL); 423232633Smp return 0.0; 424232633Smp } else { 425232633Smp struct timeval now; 426232633Smp gettimeofday(&now, NULL); 427232633Smp return (now.tv_sec-beginTime.tv_sec) + 428232633Smp (now.tv_usec-beginTime.tv_usec)/1e6; 429232633Smp } 430232633Smp} 431232633Smp#else 432232633Smpstatic double 433232633SmpdoTiming(int start) { 434232633Smp USE(start); 435232633Smp return 0.0; 436232633Smp} 437232633Smp#endif 438232633Smp 439232633Smpstatic void 440232633SmpgenerateHashes(int nChars, unsigned nWords, unsigned samples, unsigned *hashes, 441232633Smp unsigned length) 442232633Smp{ 443232633Smp if (nChars < 1) 444232633Smp return; 445232633Smp nWords = (nWords < 1) ? 1 : (nWords > 4) ? 4 : nWords; 446232633Smp Char *number = xmalloc((nChars+nWords)*sizeof(Char)); 447232633Smp struct wordent word[4]; 448232633Smp struct wordent base = { NULL, &word[0], &word[0] }; 449232633Smp word[0].word = number, word[0].next = &base, word[0].prev = &base; 450232633Smp unsigned w = 0; /* word number */ 451232633Smp /* Generate multiple words of length 2, 3, 5, then all the rest. */ 452232633Smp unsigned wBoundaries[4] = { 2-1, 2+3-1, 2+3+5-1, 0 }; 453232633Smp /* Ensure the last word has at least 4 Chars in it. */ 454232633Smp while (nWords >= 2 && nChars < (wBoundaries[nWords-2]+1) + 4) 455232633Smp nWords--; 456232633Smp wBoundaries[nWords-1] = 0xffffffff; /* don't end word past this point */ 457232633Smp unsigned i; 458232633Smp for (i = 0; i<nChars; i++) { 459232633Smp /* In deference to the gawd awful add-mul hash, we won't use the worse 460232633Smp * case here (setting all Chars to 1), but assume mostly (or at least 461232633Smp * initially) ASCII data. */ 462232633Smp number[i+w] = '!'; /* 0x21 = 33 */ 463232633Smp 464232633Smp if (i == wBoundaries[w]) { /* end a word here and move to next */ 465232633Smp w++; /* next word */ 466232633Smp number[i+w] = 0; /* terminate */ 467232633Smp word[w].word = &number[i+w+1]; 468232633Smp word[w].next = &base, word[w].prev = &word[w-1]; 469232633Smp word[w-1].next = &word[w], base.prev = &word[w]; 470232633Smp } 471232633Smp } 472232633Smp /* w is the index of the last word actually created. */ 473232633Smp number[nChars + w] = 0; /* terminate last word */ 474232633Smp unsigned timeLimit = !samples; 475232633Smp if (samples == 0) 476232633Smp samples = 1000000000; 477232633Smp doTiming(1); 478232633Smp double sec; 479232633Smp for (i = 0; i < samples; i++) { 480232633Smp /* increment 4 digit base 255 number; last characters vary fastest */ 481232633Smp unsigned j = nChars-1 + w; 482232633Smp while (1) { 483232633Smp if (++number[j] != 0) 484232633Smp break; 485232633Smp /* else reset this digit and proceed to next one */ 486232633Smp number[j] = 1; 487232633Smp if (&number[j] <= word[w].word) 488232633Smp break; /* stop at beginning of last word */ 489232633Smp j--; 490232633Smp } 491232633Smp if (word[w].word[0] == '\n') 492232633Smp word[w].word[0]++; /* suppress newline character */ 493232633Smp unsigned hash = hashhist(&base); 494232633Smp hashes[hash2tableIndex(hash, length)]++; 495232633Smp if (timeLimit && (i & 0x3ffff) == 0x3ffff) { 496232633Smp sec = doTiming(0); 497232633Smp if (sec > 10) 498232633Smp break; 499232633Smp } 500232633Smp } 501232633Smp if (i >= samples) 502232633Smp sec = doTiming(0); 503232633Smp else 504232633Smp samples = i; /* number we actually did */ 505232633Smp if (sec > 0.01) { 506232633Smp xprintf("Hash %d (%d Char %u words) with %s: %d nsec/hash, %d mcps\n", 507232633Smp samples, nChars, w+1, hashFcnName, (int)((sec/samples)*1e9), 508232633Smp (int)((double)samples*nChars/sec/1e6)); 509232633Smp } 510232633Smp} 511232633Smp#endif /* DEBUG_HIST */ 512232633Smp 513232633Smp#ifdef DEBUG_HIST 514232633Smpstatic void 515232633SmptestHash(void) 516232633Smp{ 517232633Smp static const Char STRtestHashTimings[] = 518232633Smp { 't','e','s','t','H','a','s','h','T','i','m','i','n','g','s', 0 }; 519232633Smp struct varent *vp = adrof(STRtestHashTimings); 520232633Smp if (vp && vp->vec) { 521232633Smp unsigned hashes[4]; /* dummy place to put hashes */ 522232633Smp Char **vals = vp->vec; 523232633Smp while (*vals) { 524232633Smp int length = getn(*vals); 525232633Smp unsigned words = 526232633Smp (length < 5) ? 1 : (length < 25) ? 2 : (length < 75) ? 3 : 4; 527232633Smp if (length > 0) 528232633Smp generateHashes(length, words, 0, hashes, 4); 529232633Smp vals++; 530232633Smp } 531232633Smp } 532232633Smp unsigned length = 1024; 533232633Smp#ifdef PRIME_LENGTH /* need good HTL */ 534232633Smp length = 1021; 535232633Smp#endif 536232633Smp unsigned *hashes = xmalloc(length*sizeof(unsigned)); 537232633Smp memset(hashes, 0, length*sizeof(unsigned)); 538232633Smp /* Compute collision statistics for half full hashes modulo "length". */ 539232633Smp generateHashes(4, 1, length/2, hashes, length); 540232633Smp /* Evaluate collisions by comparing occupancy rates (mean value 0.5). 541232633Smp * One bin for each number of hits. */ 542232633Smp unsigned bins[155]; 543232633Smp memset(bins, 0, sizeof(bins)); 544232633Smp unsigned highest = 0; 545232633Smp unsigned i; 546232633Smp for (i = 0; i<length; i++) { 547232633Smp unsigned hits = hashes[i]; 548232633Smp if (hits >= sizeof(bins)/sizeof(bins[0])) /* clip */ 549232633Smp hits = highest = sizeof(bins)/sizeof(bins[0]) - 1; 550232633Smp if (hits > highest) 551232633Smp highest = hits; 552232633Smp bins[hits]++; 553232633Smp } 554232633Smp xprintf("Occupancy of %d buckets by %d hashes %d Chars %d word with %s\n", 555232633Smp length, length/2, 4, 1, hashFcnName); 556232633Smp for (i = 0; i <= highest; i++) { 557232633Smp xprintf(" %d buckets (%d%%) with %d hits\n", 558232633Smp bins[i], bins[i]*100/length, i); 559232633Smp } 560232633Smp /* Count run lengths to evaluate linear rehashing effectiveness. Estimate 561232633Smp * a little corrupted by edge effects. */ 562232633Smp memset(bins, 0, sizeof(bins)); 563232633Smp highest = 0; 564232633Smp for (i = 0; hashes[i] == 0; i++); /* find first occupied bucket */ 565232633Smp unsigned run = 0; 566232633Smp unsigned rehashed = 0; 567232633Smp for (; i<length; i++) { 568232633Smp unsigned hits = hashes[i]; 569232633Smp if (hits == 0 && rehashed > 0) 570232633Smp hits = 1 && rehashed--; 571232633Smp else if (hits > 1) 572232633Smp rehashed += hits-1; 573232633Smp if (hits) 574232633Smp run++; 575232633Smp else { 576232633Smp /* a real free slot, count it */ 577232633Smp if (run >= sizeof(bins)/sizeof(bins[0])) /* clip */ 578232633Smp run = highest = sizeof(bins)/sizeof(bins[0]) - 1; 579232633Smp if (run > highest) 580232633Smp highest = run; 581232633Smp bins[run]++; 582232633Smp run = 0; 583232633Smp } 584232633Smp } 585232633Smp /* Ignore the partial run at end as we ignored the beginning. */ 586232633Smp double merit = 0.0, entries = 0; 587232633Smp for (i = 0; i <= highest; i++) { 588232633Smp entries += bins[i]*i; /* total hashed objects */ 589232633Smp merit += bins[i]*i*i; 590232633Smp } 591232633Smp xprintf("Rehash collision figure of merit %u (ideal=100), run lengths:\n", 592232633Smp (int)(100.0*merit/entries)); 593232633Smp for (i = 0; i <= highest; i++) { 594232633Smp if (bins[i] != 0) 595232633Smp xprintf(" %d runs of length %d buckets\n", bins[i], i); 596232633Smp } 597232633Smp xfree(hashes); 598232633Smp} 599232633Smp#endif /* DEBUG_HIST */ 600232633Smp 601232633Smp/* 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; 616232633Smp } 61759243Sobrien} 61859243Sobrien 619232633Smp/* Renumber entries following p, which we will be deleting. */ 620232633SmpPG_STATIC void 621232633SmprenumberHist(struct Hist *p) 622232633Smp{ 623232633Smp int n = p->Href; 624232633Smp while ((p = p->Hnext)) 625232633Smp p->Href = n--; 626232633Smp} 62759243Sobrien 628232633Smp/* The hash table is implemented as an array of pointers to Hist entries. Each 629232633Smp * entry is located in the table using hash2tableIndex() and checking the 630232633Smp * following entries in case of a collision (linear rehash). Free entries in 631232633Smp * the table are zero (0, NULL, emptyHTE). Deleted entries that cannot yet be 632232633Smp * freed are set to one (deletedHTE). The Hist.Hhash member is non-zero iff 633232633Smp * the entry is in the hash table. When the hash table get too full, it is 634232633Smp * reallocated to be approximately twice the history length (see 635232633Smp * getHashTableSize). */ 636232633Smpstatic struct Hist **histHashTable = NULL; 637232633Smpstatic unsigned histHashTableLength = 0; /* number of Hist pointers in table */ 638232633Smp 639232633Smpstatic struct Hist * const emptyHTE = NULL; 640232633Smpstatic struct Hist * const deletedHTE = (struct Hist *)1; 641232633Smp 642232633Smpstatic struct { 643232633Smp unsigned insertCount; 644232633Smp unsigned removeCount; 645232633Smp unsigned rehashes; 646232633Smp int deleted; 647232633Smp} hashStats; 648232633Smp 649232633Smp#ifdef DEBUG_HIST 650232633Smpvoid 651232633SmpcheckHistHashTable(int print) 652232633Smp{ 653232633Smp unsigned occupied = 0; 654232633Smp unsigned deleted = 0; 655232633Smp unsigned i; 656232633Smp for (i = 0; i<histHashTableLength; i++) 657232633Smp if (histHashTable[i] == emptyHTE) 658232633Smp continue; 659232633Smp else if (histHashTable[i] == deletedHTE) 660232633Smp deleted++; 661232633Smp else 662232633Smp occupied++; 663232633Smp if (print) 664232633Smp xprintf(" found len %u occupied %u deleted %u\n", 665232633Smp histHashTableLength, occupied, deleted); 666232633Smp assert(deleted == hashStats.deleted); 667232633Smp} 668232633Smp 669232633Smpstatic int doneTest = 0; 670232633Smp 671232633Smp/* Main entry point for displaying history statistics and hash function 672232633Smp * behavior. */ 673232633Smpvoid 674232633SmpdisplayHistStats(const char *reason) 675232633Smp{ 676232633Smp /* Just hash statistics for now. */ 677232633Smp xprintf("%s history hash table len %u count %u (deleted %d)\n", reason, 678232633Smp histHashTableLength, histCount, hashStats.deleted); 679232633Smp xprintf(" inserts %u rehashes %u%% each\n", 680232633Smp hashStats.insertCount, 681232633Smp (hashStats.insertCount 682232633Smp ? 100*hashStats.rehashes/hashStats.insertCount : 0)); 683232633Smp xprintf(" removes %u net %u\n", 684232633Smp hashStats.removeCount, 685232633Smp hashStats.insertCount - hashStats.removeCount); 686232633Smp assert(hashStats.insertCount >= hashStats.removeCount); 687232633Smp checkHistHashTable(1); 688232633Smp memset(&hashStats, 0, sizeof(hashStats)); 689232633Smp if (!doneTest) { 690232633Smp testHash(); 691232633Smp doneTest = 1; 692232633Smp } 693232633Smp} 694232633Smp#else 695232633Smpvoid 696232633SmpdisplayHistStats(const char *reason) 697232633Smp{ 698232633Smp USE(reason); 699232633Smp} 700232633Smp#endif 701232633Smp 702232633Smpstatic void 703232633SmpdiscardHistHashTable(void) 704232633Smp{ 705232633Smp if (histHashTable == NULL) 706232633Smp return; 707232633Smp displayHistStats("Discarding"); 708232633Smp xfree(histHashTable); 709232633Smp histHashTable = NULL; 710232633Smp} 711232633Smp 712232633Smp/* Computes a new hash table size, when the current one is too small. */ 713232633Smpstatic unsigned 714232633SmpgetHashTableSize(int histlen) 715232633Smp{ 716232633Smp unsigned target = histlen * 2; 717232633Smp unsigned e = 5; 718232633Smp unsigned size; 719232633Smp while ((size = 1<<e) < target) 720232633Smp e++; 721232633Smp#ifdef PRIME_LENGTH /* need good HTL */ 722232633Smp /* Not all prime, but most are and none have factors smaller than 11. */ 723232633Smp return size+15; 724232633Smp#else 725232633Smp assert((size & (size-1)) == 0); /* must be a power of two */ 726232633Smp return size; 727232633Smp#endif 728232633Smp} 729232633Smp 730232633Smp/* Create the hash table or resize, if necessary. */ 731232633Smpstatic void 732232633SmpcreateHistHashTable(int histlen) 733232633Smp{ 734232633Smp if (histlen == 0) { 735232633Smp discardHistHashTable(); 736232633Smp return; 737232633Smp } 738232633Smp if (histlen < 0) { 739232633Smp histlen = getn(varval(STRhistory)); 740232633Smp if (histlen == 0) 741232633Smp return; /* no need for hash table */ 742232633Smp assert(histlen > 0); 743232633Smp } 744232633Smp if (histHashTable != NULL) { 745232633Smp if (histCount < histHashTableLength * 3 / 4) 746232633Smp return; /* good enough for now */ 747232633Smp discardHistHashTable(); /* too small */ 748232633Smp } 749232633Smp histHashTableLength = getHashTableSize( 750232633Smp histlen > (int)histCount ? histlen : (int)histCount); 751232633Smp histHashTable = xmalloc(histHashTableLength * sizeof(struct Hist *)); 752232633Smp memset(histHashTable, 0, histHashTableLength * sizeof(struct Hist *)); 753232633Smp assert(histHashTable[0] == emptyHTE); 754232633Smp 755232633Smp /* Now insert all the entries on the history list into the hash table. */ 756232633Smp { 757232633Smp struct Hist *hp; 758232633Smp for (hp = &Histlist; (hp = hp->Hnext) != NULL;) { 759232633Smp unsigned lpHash = hashhist(&hp->Hlex); 760232633Smp assert(!hp->Hhash || hp->Hhash == lpHash); 761232633Smp hp->Hhash = 0; /* force insert to new hash table */ 762232633Smp insertHistHashTable(hp, lpHash); 763232633Smp } 764232633Smp } 765232633Smp} 766232633Smp 767232633Smp/* Insert np into the hash table. We assume that np is already on the 768232633Smp * Histlist. The specified hashval matches the new Hist entry but has not yet 769232633Smp * been assigned to Hhash (or the element is already on the hash table). */ 770232633Smpstatic void 771232633SmpinsertHistHashTable(struct Hist *np, unsigned hashval) 772232633Smp{ 773232633Smp unsigned rehashes = 0; 774232633Smp unsigned hi = 0; 775232633Smp if (!histHashTable) 776232633Smp return; 777232633Smp if (np->Hhash != 0) { 778232633Smp /* already in hash table */ 779232633Smp assert(hashval == np->Hhash); 780232633Smp return; 781232633Smp } 782232633Smp assert(np != deletedHTE); 783232633Smp /* Find a free (empty or deleted) slot, using linear rehash. */ 784232633Smp assert(histHashTable); 785232633Smp for (rehashes = 0; 786232633Smp ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)), 787232633Smp histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE); 788232633Smp rehashes++) { 789232633Smp assert(np != histHashTable[hi]); 790232633Smp if (rehashes >= histHashTableLength / 10) { 791232633Smp /* Hash table is full, so grow it. We assume the create function 792232633Smp * will roughly double the size we give it. Create initializes the 793232633Smp * new table with everything on the Histlist, so we are done when 794232633Smp * it returns. */ 795232633Smp#ifdef DEBUG_HIST 796232633Smp xprintf("Growing history hash table from %d ...", 797232633Smp histHashTableLength); 798232633Smp flush(); 799232633Smp#endif 800232633Smp discardHistHashTable(); 801232633Smp createHistHashTable(histHashTableLength); 802232633Smp#ifdef DEBUG_HIST 803232633Smp xprintf("to %d.\n", histHashTableLength); 804232633Smp#endif 805232633Smp return; 806232633Smp } 807232633Smp } 808232633Smp /* Might be sensible to grow hash table if rehashes is "too big" here. */ 809232633Smp if (histHashTable[hi] == deletedHTE) 810232633Smp hashStats.deleted--; 811232633Smp histHashTable[hi] = np; 812232633Smp np->Hhash = hashval; 813232633Smp hashStats.insertCount++; 814232633Smp hashStats.rehashes += rehashes; 815232633Smp} 816232633Smp 817232633Smp/* Remove the 'np' entry from the hash table. */ 818232633Smpstatic void 819232633SmpremoveHistHashTable(struct Hist *np) 820232633Smp{ 821232633Smp unsigned hi = np->Hhash; 822232633Smp if (!histHashTable || !hi) 823232633Smp return; /* no hash table or not on it */ 824232633Smp /* find desired entry */ 825232633Smp while ((hi = hash2tableIndex(hi, histHashTableLength)), 826232633Smp histHashTable[hi] != emptyHTE) { 827232633Smp if (np == histHashTable[hi]) { 828232633Smp unsigned i; 829232633Smp unsigned deletes = 0; 830232633Smp histHashTable[hi] = deletedHTE; /* dummy, but non-zero entry */ 831232633Smp /* now peek ahead to see if the dummies are really necessary. */ 832232633Smp i = 1; 833232633Smp while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == 834232633Smp deletedHTE) 835232633Smp i++; 836232633Smp if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == 837232633Smp emptyHTE) { 838232633Smp /* dummies are no longer necessary placeholders. */ 839232633Smp deletes = i; 840232633Smp while (i-- > 0) { 841232633Smp histHashTable[hash2tableIndex(hi+i, histHashTableLength)] = 842232633Smp emptyHTE; 843232633Smp } 844232633Smp } 845232633Smp hashStats.deleted += 1 - deletes; /* delta deleted entries */ 846232633Smp hashStats.removeCount++; 847232633Smp return; 848232633Smp } 849232633Smp hi++; /* linear rehash */ 850232633Smp } 851232633Smp assert(!"Hist entry not found in hash table"); 852232633Smp} 853232633Smp 854232633Smp/* Search the history hash table for a command matching lp, using hashval as 855232633Smp * its hash value. */ 856232633Smpstatic struct Hist * 857232633SmpfindHistHashTable(struct wordent *lp, unsigned hashval) 858232633Smp{ 859232633Smp unsigned deleted = 0; /* number of deleted entries skipped */ 860232633Smp unsigned hi = hashval; 861232633Smp struct Hist *hp; 862232633Smp if (!histHashTable) 863232633Smp return NULL; 864232633Smp while ((hi = hash2tableIndex(hi, histHashTableLength)), 865232633Smp (hp = histHashTable[hi]) != emptyHTE) { 866232633Smp if (hp == deletedHTE) 867232633Smp deleted++; 868232633Smp else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex))) 869232633Smp return hp; 870232633Smp if (deleted > (histHashTableLength>>4)) { 871232633Smp /* lots of deletes, so we need a sparser table. */ 872232633Smp discardHistHashTable(); 873232633Smp createHistHashTable(histHashTableLength); 874232633Smp return findHistHashTable(lp, hashval); 875232633Smp } 876232633Smp hi++; /* linear rehash */ 877232633Smp } 878232633Smp return NULL; 879232633Smp} 880232633Smp 881232633Smp/* When merge semantics are in use, find the approximate predecessor for the 882232633Smp * new entry, so that the Htime entries are decreasing. Return the entry just 883232633Smp * before the first entry with equal times, so the caller can check for 884232633Smp * duplicates. When pTime is not NULL, use it as a starting point for search, 885232633Smp * otherwise search from beginning (largest time value) of history list. */ 886232633SmpPG_STATIC struct Hist * 887232633SmpmergeInsertionPoint( 888232633Smp struct Hist *np, /* new entry to be inserted */ 889232633Smp struct Hist *pTime) /* hint about where to insert */ 890232633Smp{ 891232633Smp struct Hist *pp, *p; 892232633Smp if (histTail && histTail->Htime >= np->Htime) 893232633Smp pTime = histTail; /* new entry goes at the end */ 894232633Smp if (histMerg && histMerg != &Histlist && histMerg != Histlist.Hnext) { 895232633Smp /* Check above and below previous insertion point, in case we're adding 896232633Smp * sequential times in the middle of the list (e.g. history -M). */ 897232633Smp if (histMerg->Htime >= np->Htime) 898232633Smp pTime = histMerg; 899232633Smp else if (histMerg->Hprev->Htime >= np->Htime) 900232633Smp pTime = histMerg->Hprev; 901232633Smp } 902232633Smp if (pTime) { 903232633Smp /* With hint, search up the list until Htime is greater. We skip past 904232633Smp * the equal ones, too, so our caller can elide duplicates. */ 905232633Smp pp = pTime; 906232633Smp while (pp != &Histlist && pp->Htime <= np->Htime) 907232633Smp pp = pp->Hprev; 908232633Smp } else 909232633Smp pp = &Histlist; 910232633Smp /* Search down the list while current entry's time is too large. */ 911232633Smp while ((p = pp->Hnext) && (p->Htime > np->Htime)) 912232633Smp pp = p; /* advance insertion point */ 913232633Smp /* Remember recent position as hint for next time */ 914232633Smp histMerg = pp; 915232633Smp return pp; 916232633Smp} 917232633Smp 918232633Smp/* Bubble Hnum & Href in new entry down to pp through earlier part of list. */ 919232633SmpPG_STATIC void bubbleHnumHrefDown(struct Hist *np, struct Hist *pp) 920232633Smp{ 921232633Smp struct Hist *p; 922232633Smp for (p = Histlist.Hnext; p != pp->Hnext; p = p->Hnext) { 923232633Smp /* swap Hnum & Href values of p and np. */ 924232633Smp int n = p->Hnum, r = p->Href; 925232633Smp p->Hnum = np->Hnum; p->Href = np->Href; 926232633Smp np->Hnum = n; np->Href = r; 927232633Smp } 928232633Smp} 929232633Smp 930232633Smp/* Enter new command into the history list according to current settings. */ 93159243Sobrienstruct Hist * 932232633Smpenthist( 933232633Smp int event, /* newly incremented global eventno */ 934232633Smp struct wordent *lp, 935232633Smp int docopy, 936232633Smp int mflg, /* true if merge requested */ 937232633Smp int histlen) /* -1 if unknown */ 93859243Sobrien{ 939232633Smp struct Hist *p = NULL, *pp = &Histlist, *pTime = NULL; 940145479Smp struct Hist *np; 941167465Smp const Char *dp; 942232633Smp unsigned lpHash = 0; /* non-zero if hashing entries */ 943232633Smp 94459243Sobrien if ((dp = varval(STRhistdup)) != STRNULL) { 94559243Sobrien if (eq(dp, STRerase)) { 94659243Sobrien /* masaoki@akebono.tky.hp.com (Kobayashi Masaoki) */ 947232633Smp createHistHashTable(histlen); 948232633Smp lpHash = hashhist(lp); 949232633Smp assert(lpHash != 0); 950232633Smp p = findHistHashTable(lp, lpHash); 951232633Smp if (p) { 952232633Smp if (Htime != 0 && p->Htime > Htime) 953232633Smp Htime = p->Htime; 954232633Smp /* If we are merging, and the old entry is at the place we want 955232633Smp * to insert the new entry, then remember the place. */ 956232633Smp if (mflg && Htime != 0 && p->Hprev->Htime >= Htime) 957232633Smp pTime = p->Hprev; 958232633Smp if (!fastMergeErase) 959232633Smp renumberHist(p); /* Reset Href of subsequent entries */ 960232633Smp hremove(p); 961232633Smp hfree(p); 962232633Smp p = NULL; /* so new entry is allocated below */ 963232633Smp } 96459243Sobrien } 96559243Sobrien else if (eq(dp, STRall)) { 966232633Smp createHistHashTable(histlen); 967232633Smp lpHash = hashhist(lp); 968232633Smp assert(lpHash != 0); 969232633Smp p = findHistHashTable(lp, lpHash); 970232633Smp if (p) /* p!=NULL, only update this entry's Htime below */ 971232633Smp 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 989232633Smp (void) time(&(np->Htime)); 99059243Sobrien 99159243Sobrien if (p == np) 992232633Smp return np; /* reused existing entry */ 99359243Sobrien 994232633Smp /* Initialize the new entry. */ 99559243Sobrien np->Hnum = np->Href = event; 99659243Sobrien if (docopy) { 997232633Smp 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; 1007232633Smp lp->prev->next = &np->Hlex; 1008232633Smp np->histline = NULL; 100959243Sobrien } 1010232633Smp np->Hhash = 0; 1011232633Smp 1012232633Smp /* The head of history list is the default insertion point. 1013232633Smp If merging, advance insertion point, in pp, according to Htime. */ 1014232633Smp /* XXX -- In histdup=all, Htime values can be non-monotonic. */ 1015232633Smp if (mflg) { /* merge according to np->Htime */ 1016232633Smp pp = mergeInsertionPoint(np, pTime); 1017232633Smp for (p = pp->Hnext; p && p->Htime == np->Htime; pp = p, p = p->Hnext) { 1018232633Smp if (heq(&p->Hlex, &np->Hlex)) { 1019232633Smp eventno--; /* duplicate, so don't add new event */ 1020232633Smp hfree(np); 1021232633Smp return (p); 1022232633Smp } 1023232633Smp } 1024232633Smp /* pp is now the last entry with time >= to np. */ 1025232633Smp if (!fastMergeErase) { /* renumber at end of loadhist */ 1026232633Smp /* Before inserting np after pp, bubble its Hnum & Href values down 1027232633Smp * through the earlier part of list. */ 1028232633Smp bubbleHnumHrefDown(np, pp); 1029232633Smp } 1030232633Smp } 1031232633Smp else 1032232633Smp pp = &Histlist; /* insert at beginning of history */ 1033232633Smp hinsert(np, pp); 1034232633Smp if (lpHash && histlen != 0) /* erase & all modes use hash table */ 1035232633Smp insertHistHashTable(np, lpHash); 1036232633Smp else 1037232633Smp discardHistHashTable(); 103859243Sobrien return (np); 103959243Sobrien} 104059243Sobrien 104159243Sobrienstatic void 1042167465Smphfree(struct Hist *hp) 104359243Sobrien{ 1044232633Smp assert(hp != histMerg); 1045232633Smp if (hp->Hhash) 1046232633Smp removeHistHashTable(hp); 104759243Sobrien freelex(&hp->Hlex); 104859243Sobrien if (hp->histline) 1049232633Smp xfree(hp->histline); 1050167465Smp xfree(hp); 105159243Sobrien} 105259243Sobrien 1053232633SmpPG_STATIC void 1054232633Smpphist(struct Hist *hp, int hflg) 1055232633Smp{ 1056232633Smp if (hflg & HIST_ONLY) { 1057232633Smp int old_output_raw; 105859243Sobrien 1059232633Smp /* 1060232633Smp * Control characters have to be written as is (output_raw). 1061232633Smp * This way one can preserve special characters (like tab) in 1062232633Smp * the history file. 1063232633Smp * From: mveksler@vnet.ibm.com (Veksler Michael) 1064232633Smp */ 1065232633Smp old_output_raw = output_raw; 1066232633Smp output_raw = 1; 1067232633Smp cleanup_push(&old_output_raw, output_raw_restore); 1068232633Smp if (hflg & HIST_TIME) 1069232633Smp /* 1070232633Smp * Make file entry with history time in format: 1071232633Smp * "+NNNNNNNNNN" (10 digits, left padded with ascii '0') 1072232633Smp */ 1073232633Smp 1074232633Smp xprintf("#+%010lu\n", (unsigned long)hp->Htime); 1075232633Smp 1076232633Smp if (HistLit && hp->histline) 1077232633Smp xprintf("%S\n", hp->histline); 1078232633Smp else 1079232633Smp prlex(&hp->Hlex); 1080232633Smp cleanup_until(&old_output_raw); 1081232633Smp } 1082232633Smp else { 1083232633Smp Char *cp = str2short("%h\t%T\t%R\n"); 1084232633Smp Char *p; 1085232633Smp struct varent *vp = adrof(STRhistory); 1086232633Smp 1087232633Smp if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1]) 1088232633Smp cp = vp->vec[1]; 1089232633Smp 1090232633Smp p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp); 1091232633Smp cleanup_push(p, xfree); 1092232633Smp for (cp = p; *cp;) 1093232633Smp xputwchar(*cp++); 1094232633Smp cleanup_until(p); 1095232633Smp } 1096232633Smp} 1097232633Smp 1098232633SmpPG_STATIC void 1099232633Smpdophist(int n, int hflg) 1100232633Smp{ 1101232633Smp struct Hist *hp; 1102232633Smp if (setintr) { 1103232633Smp int old_pintr_disabled; 1104232633Smp 1105232633Smp pintr_push_enable(&old_pintr_disabled); 1106232633Smp cleanup_until(&old_pintr_disabled); 1107232633Smp } 1108232633Smp if ((hflg & HIST_REV) == 0) { 1109232633Smp /* Since the history list is stored most recent first, non-reversing 1110232633Smp * print needs to print (backwards) up the list. */ 1111232633Smp if ((unsigned)n >= histCount) 1112232633Smp hp = histTail; 1113232633Smp else { 1114232633Smp for (hp = Histlist.Hnext; 1115232633Smp --n > 0 && hp->Hnext != NULL; 1116232633Smp hp = hp->Hnext) 1117232633Smp ; 1118232633Smp } 1119232633Smp if (hp == NULL) 1120232633Smp return; /* nothing to print */ 1121232633Smp for (; hp != &Histlist; hp = hp->Hprev) 1122232633Smp phist(hp, hflg); 1123232633Smp } else { 1124232633Smp for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext) 1125232633Smp phist(hp, hflg); 1126232633Smp } 1127232633Smp} 1128232633Smp 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) { 1170232633Smp struct Hist *np, *hp; 1171232633Smp for (hp = &Histlist; (np = hp->Hnext) != NULL;) 1172232633Smp 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 } 1185232633Smp 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 1223232633Smp/* 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); 1277232633Smp 1278167465Smp fp = xcreat(short2str(fname), 0600); 1279232633Smp 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 1294232633Smp/* 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); 1309232633Smp 1310232633Smp /* During history merging (enthist sees mflg set), we disable management of 1311232633Smp * Hnum and Href (because fastMergeErase is true). So now reset all the 1312232633Smp * values based on the final ordering of the history list. */ 1313232633Smp if (mflg) { 1314232633Smp int n = eventno; 1315232633Smp struct Hist *hp = &Histlist; 1316232633Smp while ((hp = hp->Hnext)) 1317232633Smp hp->Hnum = hp->Href = n--; 1318232633Smp } 131959243Sobrien} 1320