1 /* $Header: /p/tcsh/cvsroot/tcsh/sh.hist.c,v 3.53 2011/01/24 18:10:26 christos Exp $ */ 2 /* 3 * sh.hist.c: Shell history expansions and substitutions 4 */ 5 /*- 6 * Copyright (c) 1980, 1991 The Regents of the University of California. 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 #include "sh.h" 34 35 RCSID("$tcsh: sh.hist.c,v 3.53 2011/01/24 18:10:26 christos Exp $") 36 37 #include <assert.h> 38 #include "tc.h" 39 40 extern int histvalid; 41 extern struct Strbuf histline; 42 Char HistLit = 0; 43 44 static int heq (const struct wordent *, const struct wordent *); 45 static void hfree (struct Hist *); 46 47 #define HIST_ONLY 0x01 48 #define HIST_SAVE 0x02 49 #define HIST_LOAD 0x04 50 #define HIST_REV 0x08 51 #define HIST_CLEAR 0x10 52 #define HIST_MERGE 0x20 53 #define HIST_TIME 0x40 54 55 /* 56 * C shell 57 */ 58 59 /* Static functions don't show up in gprof summaries. So eliminate "static" 60 * modifier from some frequently called functions. */ 61 #ifdef PROF 62 #define PG_STATIC 63 #else 64 #define PG_STATIC static 65 #endif 66 67 /* #define DEBUG_HIST 1 */ 68 69 static const int fastMergeErase = 1; 70 static unsigned histCount = 0; /* number elements on history list */ 71 static struct Hist *histTail = NULL; /* last element on history list */ 72 static struct Hist *histMerg = NULL; /* last element merged by Htime */ 73 74 static void insertHistHashTable(struct Hist *, unsigned); 75 76 77 /* Insert new element (hp) in history list after specified predecessor (pp). */ 78 static void 79 hinsert(struct Hist *hp, struct Hist *pp) 80 { 81 struct Hist *fp = pp->Hnext; /* following element, if any */ 82 hp->Hnext = fp, hp->Hprev = pp; 83 pp->Hnext = hp; 84 if (fp) 85 fp->Hprev = hp; 86 else 87 histTail = hp; /* meaning hp->Hnext == NULL */ 88 histCount++; 89 } 90 91 /* Remove the entry from the history list. */ 92 static void 93 hremove(struct Hist *hp) 94 { 95 struct Hist *pp = hp->Hprev; 96 assert(pp); /* elements always have a previous */ 97 pp->Hnext = hp->Hnext; 98 if (hp->Hnext) 99 hp->Hnext->Hprev = pp; 100 else 101 histTail = pp; /* we must have been last */ 102 if (hp == histMerg) /* deleting this hint from list */ 103 histMerg = NULL; 104 assert(histCount > 0); 105 histCount--; 106 } 107 108 /* Prune length of history list to specified size by history variable. */ 109 PG_STATIC void 110 discardExcess(int histlen) 111 { 112 struct Hist *hp, *np; 113 if (histTail == NULL) { 114 assert(histCount == 0); 115 return; /* no entries on history list */ 116 } 117 /* Prune dummy entries from the front, then old entries from the back. If 118 * the list is still too long scan the whole list as before. But only do a 119 * full scan if the list is more than 6% (1/16th) too long. */ 120 while (histCount > (unsigned)histlen && (np = Histlist.Hnext)) { 121 if (eventno - np->Href >= histlen || histlen == 0) 122 hremove(np), hfree(np); 123 else 124 break; 125 } 126 while (histCount > (unsigned)histlen && (np = histTail) != &Histlist) { 127 if (eventno - np->Href >= histlen || histlen == 0) 128 hremove(np), hfree(np); 129 else 130 break; 131 } 132 if (histCount - (histlen >> 4) <= (unsigned)histlen) 133 return; /* don't bother doing the full scan */ 134 for (hp = &Histlist; histCount > (unsigned)histlen && 135 (np = hp->Hnext) != NULL;) 136 if (eventno - np->Href >= histlen || histlen == 0) 137 hremove(np), hfree(np); 138 else 139 hp = np; 140 } 141 142 /* Add the command "sp" to the history list. */ 143 void 144 savehist( 145 struct wordent *sp, 146 int mflg) /* true if -m (merge) specified */ 147 { 148 int histlen = 0; 149 Char *cp; 150 151 /* throw away null lines */ 152 if (sp && sp->next->word[0] == '\n') 153 return; 154 cp = varval(STRhistory); 155 while (*cp) { 156 if (!Isdigit(*cp)) { 157 histlen = 0; 158 break; 159 } 160 histlen = histlen * 10 + *cp++ - '0'; 161 } 162 if (sp) 163 (void) enthist(++eventno, sp, 1, mflg, histlen); 164 discardExcess(histlen); 165 } 166 167 #define USE_JENKINS_HASH 1 168 /* #define USE_ONE_AT_A_TIME 1 */ 169 #undef PRIME_LENGTH /* no need for good HTL */ 170 171 #ifdef USE_JENKINS_HASH 172 #define hashFcnName "lookup3" 173 /* From: 174 lookup3.c, by Bob Jenkins, May 2006, Public Domain. 175 "... You can use this free for any purpose. It's in 176 the public domain. It has no warranty." 177 http://burtleburtle.net/bob/hash/index.html 178 */ 179 180 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 181 #define mix(a,b,c) \ 182 { \ 183 a -= c; a ^= rot(c, 4); c += b; \ 184 b -= a; b ^= rot(a, 6); a += c; \ 185 c -= b; c ^= rot(b, 8); b += a; \ 186 a -= c; a ^= rot(c,16); c += b; \ 187 b -= a; b ^= rot(a,19); a += c; \ 188 c -= b; c ^= rot(b, 4); b += a; \ 189 } 190 #define final(a,b,c) \ 191 { \ 192 c ^= b; c -= rot(b,14); \ 193 a ^= c; a -= rot(c,11); \ 194 b ^= a; b -= rot(a,25); \ 195 c ^= b; c -= rot(b,16); \ 196 a ^= c; a -= rot(c, 4); \ 197 b ^= a; b -= rot(a,14); \ 198 c ^= b; c -= rot(b,24); \ 199 } 200 201 struct hashValue /* State used to hash a wordend word list. */ 202 { 203 uint32_t a, b, c; 204 }; 205 206 /* Set up the internal state */ 207 static void 208 initializeHash(struct hashValue *h) 209 { 210 h->a = h->b = h->c = 0xdeadbeef; 211 } 212 213 /* This does a partial hash of the Chars in a single word. For efficiency we 214 * include 3 versions of the code to pack Chars into 32-bit words for the 215 * mixing function. */ 216 static void 217 addWordToHash(struct hashValue *h, const Char *word) 218 { 219 uint32_t a = h->a, b = h->b, c = h->c; 220 #ifdef SHORT_STRINGS 221 #ifdef WIDE_STRINGS 222 assert(sizeof(Char) >= 4); 223 while (1) { 224 unsigned k; 225 if ((k = (uChar)*word++) == 0) break; a += k; 226 if ((k = (uChar)*word++) == 0) break; b += k; 227 if ((k = (uChar)*word++) == 0) break; c += k; 228 mix(a, b, c); 229 } 230 #else 231 assert(sizeof(Char) == 2); 232 while (1) { 233 unsigned k; 234 if ((k = (uChar)*word++) == 0) break; a += k; 235 if ((k = (uChar)*word++) == 0) break; a += k << 16; 236 if ((k = (uChar)*word++) == 0) break; b += k; 237 if ((k = (uChar)*word++) == 0) break; b += k << 16; 238 if ((k = (uChar)*word++) == 0) break; c += k; 239 if ((k = (uChar)*word++) == 0) break; c += k << 16; 240 mix(a, b, c); 241 } 242 #endif 243 #else 244 assert(sizeof(Char) == 1); 245 while (1) { 246 unsigned k; 247 if ((k = *word++) == 0) break; a += k; 248 if ((k = *word++) == 0) break; a += k << 8; 249 if ((k = *word++) == 0) break; a += k << 16; 250 if ((k = *word++) == 0) break; a += k << 24; 251 if ((k = *word++) == 0) break; b += k; 252 if ((k = *word++) == 0) break; b += k << 8; 253 if ((k = *word++) == 0) break; b += k << 16; 254 if ((k = *word++) == 0) break; b += k << 24; 255 if ((k = *word++) == 0) break; c += k; 256 if ((k = *word++) == 0) break; c += k << 8; 257 if ((k = *word++) == 0) break; c += k << 16; 258 if ((k = *word++) == 0) break; c += k << 24; 259 mix(a, b, c); 260 } 261 #endif 262 h->a = a, h->b = b, h->c = c; 263 } 264 265 static void 266 addCharToHash(struct hashValue *h, Char ch) 267 { 268 /* The compiler (gcc -O2) seems to do a good job optimizing this without 269 * explicitly extracting into local variables. */ 270 h->a += (uChar)ch; 271 mix(h->a, h->b, h->c); 272 } 273 274 static uint32_t 275 finalizeHash(struct hashValue *h) 276 { 277 uint32_t a = h->a, b = h->b, c = h->c; 278 final(a, b, c); 279 return c; 280 } 281 282 #elif USE_ONE_AT_A_TIME 283 #define hashFcnName "one-at-a-time" 284 /* This one is also from Bob Jenkins, but is slower but simpler than lookup3. 285 "... The code given here are all public domain." 286 http://burtleburtle.net/bob/hash/doobs.html */ 287 288 #if 0 289 ub4 290 one_at_a_time(char *key, ub4 len) 291 { 292 ub4 hash, i; 293 for (hash=0, i=0; i<len; ++i) 294 { 295 hash += key[i]; 296 hash += (hash << 10); 297 hash ^= (hash >> 6); 298 } 299 hash += (hash << 3); 300 hash ^= (hash >> 11); 301 hash += (hash << 15); 302 return (hash & mask); 303 } 304 #endif 305 306 struct hashValue { uint32_t h; }; 307 static void 308 initializeHash(struct hashValue *h) 309 { 310 h->h = 0; 311 } 312 313 static void 314 addWordToHash(struct hashValue *h, const Char *word) 315 { 316 unsigned k; 317 uint32_t hash = h->h; 318 while (k = (uChar)*word++) 319 hash += k, hash += hash << 10, hash ^= hash >> 6; 320 h->h = hash; 321 } 322 323 static void 324 addCharToHash(struct hashValue *h, Char c) 325 { 326 Char b[2] = { c, 0 }; 327 addWordToHash(h, b); 328 } 329 330 static uint32_t 331 finalizeHash(struct hashValue *h) 332 { 333 unsigned hash = h->h; 334 hash += (hash << 3); 335 hash ^= (hash >> 11); 336 hash += (hash << 15); 337 return hash; 338 } 339 340 #else 341 #define hashFcnName "add-mul" 342 /* Simple multipy and add hash. */ 343 #define PRIME_LENGTH 1 /* need "good" HTL */ 344 struct hashValue { uint32_t h; }; 345 static void 346 initializeHash(struct hashValue *h) 347 { 348 h->h = 0xe13e2345; 349 } 350 351 static void 352 addWordToHash(struct hashValue *h, const Char *word) 353 { 354 unsigned k; 355 uint32_t hash = h->h; 356 while (k = (uChar)*word++) 357 hash = hash * 0x9e4167b9 + k; 358 h->h = hash; 359 } 360 361 static void 362 addCharToHash(struct hashValue *h, Char c) 363 { 364 h->h = h->h * 0x9e4167b9 + (uChar)c; 365 } 366 367 static uint32_t 368 finalizeHash(struct hashValue *h) 369 { 370 return h->h; 371 } 372 #endif 373 374 static unsigned 375 hashhist(struct wordent *h0) 376 { 377 struct hashValue s; 378 struct wordent *firstWord = h0->next; 379 struct wordent *h = firstWord; 380 unsigned hash = 0; 381 382 initializeHash(&s); 383 for (; h != h0; h = h->next) { 384 if (h->word[0] == '\n') 385 break; /* don't hash newline */ 386 if (h != firstWord) 387 addCharToHash(&s, ' '); /* space between words */ 388 addWordToHash(&s, h->word); 389 } 390 hash = finalizeHash(&s); 391 /* Zero means no hash value, so never return zero as a hash value. */ 392 return hash ? hash : 0x7fffffff; /* prime! */ 393 } 394 395 #if 0 396 unsigned 397 hashStr(Char *str) 398 { 399 struct hashValue s; 400 initializeHash(&s); 401 addWordToHash(&s, str); 402 return finalizeHash(&s); 403 } 404 #endif 405 406 #ifdef PRIME_LENGTH /* need good HTL */ 407 #define hash2tableIndex(hash, len) ((hash) % len) 408 #else 409 #define hash2tableIndex(hash, len) ((hash) & (len-1)) 410 #endif 411 412 /* This code can be enabled to test the above hash functions for speed and 413 * collision avoidance. The testing is enabled by "occasional" calls to 414 * displayHistStats(), see which. */ 415 #ifdef DEBUG_HIST 416 417 #ifdef BSDTIMES 418 static double 419 doTiming(int start) { 420 static struct timeval beginTime; 421 if (start) { 422 gettimeofday(&beginTime, NULL); 423 return 0.0; 424 } else { 425 struct timeval now; 426 gettimeofday(&now, NULL); 427 return (now.tv_sec-beginTime.tv_sec) + 428 (now.tv_usec-beginTime.tv_usec)/1e6; 429 } 430 } 431 #else 432 static double 433 doTiming(int start) { 434 USE(start); 435 return 0.0; 436 } 437 #endif 438 439 static void 440 generateHashes(int nChars, unsigned nWords, unsigned samples, unsigned *hashes, 441 unsigned length) 442 { 443 if (nChars < 1) 444 return; 445 nWords = (nWords < 1) ? 1 : (nWords > 4) ? 4 : nWords; 446 Char *number = xmalloc((nChars+nWords)*sizeof(Char)); 447 struct wordent word[4]; 448 struct wordent base = { NULL, &word[0], &word[0] }; 449 word[0].word = number, word[0].next = &base, word[0].prev = &base; 450 unsigned w = 0; /* word number */ 451 /* Generate multiple words of length 2, 3, 5, then all the rest. */ 452 unsigned wBoundaries[4] = { 2-1, 2+3-1, 2+3+5-1, 0 }; 453 /* Ensure the last word has at least 4 Chars in it. */ 454 while (nWords >= 2 && nChars < (wBoundaries[nWords-2]+1) + 4) 455 nWords--; 456 wBoundaries[nWords-1] = 0xffffffff; /* don't end word past this point */ 457 unsigned i; 458 for (i = 0; i<nChars; i++) { 459 /* In deference to the gawd awful add-mul hash, we won't use the worse 460 * case here (setting all Chars to 1), but assume mostly (or at least 461 * initially) ASCII data. */ 462 number[i+w] = '!'; /* 0x21 = 33 */ 463 464 if (i == wBoundaries[w]) { /* end a word here and move to next */ 465 w++; /* next word */ 466 number[i+w] = 0; /* terminate */ 467 word[w].word = &number[i+w+1]; 468 word[w].next = &base, word[w].prev = &word[w-1]; 469 word[w-1].next = &word[w], base.prev = &word[w]; 470 } 471 } 472 /* w is the index of the last word actually created. */ 473 number[nChars + w] = 0; /* terminate last word */ 474 unsigned timeLimit = !samples; 475 if (samples == 0) 476 samples = 1000000000; 477 doTiming(1); 478 double sec; 479 for (i = 0; i < samples; i++) { 480 /* increment 4 digit base 255 number; last characters vary fastest */ 481 unsigned j = nChars-1 + w; 482 while (1) { 483 if (++number[j] != 0) 484 break; 485 /* else reset this digit and proceed to next one */ 486 number[j] = 1; 487 if (&number[j] <= word[w].word) 488 break; /* stop at beginning of last word */ 489 j--; 490 } 491 if (word[w].word[0] == '\n') 492 word[w].word[0]++; /* suppress newline character */ 493 unsigned hash = hashhist(&base); 494 hashes[hash2tableIndex(hash, length)]++; 495 if (timeLimit && (i & 0x3ffff) == 0x3ffff) { 496 sec = doTiming(0); 497 if (sec > 10) 498 break; 499 } 500 } 501 if (i >= samples) 502 sec = doTiming(0); 503 else 504 samples = i; /* number we actually did */ 505 if (sec > 0.01) { 506 xprintf("Hash %d (%d Char %u words) with %s: %d nsec/hash, %d mcps\n", 507 samples, nChars, w+1, hashFcnName, (int)((sec/samples)*1e9), 508 (int)((double)samples*nChars/sec/1e6)); 509 } 510 } 511 #endif /* DEBUG_HIST */ 512 513 #ifdef DEBUG_HIST 514 static void 515 testHash(void) 516 { 517 static const Char STRtestHashTimings[] = 518 { 't','e','s','t','H','a','s','h','T','i','m','i','n','g','s', 0 }; 519 struct varent *vp = adrof(STRtestHashTimings); 520 if (vp && vp->vec) { 521 unsigned hashes[4]; /* dummy place to put hashes */ 522 Char **vals = vp->vec; 523 while (*vals) { 524 int length = getn(*vals); 525 unsigned words = 526 (length < 5) ? 1 : (length < 25) ? 2 : (length < 75) ? 3 : 4; 527 if (length > 0) 528 generateHashes(length, words, 0, hashes, 4); 529 vals++; 530 } 531 } 532 unsigned length = 1024; 533 #ifdef PRIME_LENGTH /* need good HTL */ 534 length = 1021; 535 #endif 536 unsigned *hashes = xmalloc(length*sizeof(unsigned)); 537 memset(hashes, 0, length*sizeof(unsigned)); 538 /* Compute collision statistics for half full hashes modulo "length". */ 539 generateHashes(4, 1, length/2, hashes, length); 540 /* Evaluate collisions by comparing occupancy rates (mean value 0.5). 541 * One bin for each number of hits. */ 542 unsigned bins[155]; 543 memset(bins, 0, sizeof(bins)); 544 unsigned highest = 0; 545 unsigned i; 546 for (i = 0; i<length; i++) { 547 unsigned hits = hashes[i]; 548 if (hits >= sizeof(bins)/sizeof(bins[0])) /* clip */ 549 hits = highest = sizeof(bins)/sizeof(bins[0]) - 1; 550 if (hits > highest) 551 highest = hits; 552 bins[hits]++; 553 } 554 xprintf("Occupancy of %d buckets by %d hashes %d Chars %d word with %s\n", 555 length, length/2, 4, 1, hashFcnName); 556 for (i = 0; i <= highest; i++) { 557 xprintf(" %d buckets (%d%%) with %d hits\n", 558 bins[i], bins[i]*100/length, i); 559 } 560 /* Count run lengths to evaluate linear rehashing effectiveness. Estimate 561 * a little corrupted by edge effects. */ 562 memset(bins, 0, sizeof(bins)); 563 highest = 0; 564 for (i = 0; hashes[i] == 0; i++); /* find first occupied bucket */ 565 unsigned run = 0; 566 unsigned rehashed = 0; 567 for (; i<length; i++) { 568 unsigned hits = hashes[i]; 569 if (hits == 0 && rehashed > 0) 570 hits = 1 && rehashed--; 571 else if (hits > 1) 572 rehashed += hits-1; 573 if (hits) 574 run++; 575 else { 576 /* a real free slot, count it */ 577 if (run >= sizeof(bins)/sizeof(bins[0])) /* clip */ 578 run = highest = sizeof(bins)/sizeof(bins[0]) - 1; 579 if (run > highest) 580 highest = run; 581 bins[run]++; 582 run = 0; 583 } 584 } 585 /* Ignore the partial run at end as we ignored the beginning. */ 586 double merit = 0.0, entries = 0; 587 for (i = 0; i <= highest; i++) { 588 entries += bins[i]*i; /* total hashed objects */ 589 merit += bins[i]*i*i; 590 } 591 xprintf("Rehash collision figure of merit %u (ideal=100), run lengths:\n", 592 (int)(100.0*merit/entries)); 593 for (i = 0; i <= highest; i++) { 594 if (bins[i] != 0) 595 xprintf(" %d runs of length %d buckets\n", bins[i], i); 596 } 597 xfree(hashes); 598 } 599 #endif /* DEBUG_HIST */ 600 601 /* Compares two word lists for equality. */ 602 static int 603 heq(const struct wordent *a0, const struct wordent *b0) 604 { 605 const struct wordent *a = a0->next, *b = b0->next; 606 607 for (;;) { 608 if (Strcmp(a->word, b->word) != 0) 609 return 0; 610 a = a->next; 611 b = b->next; 612 if (a == a0) 613 return (b == b0) ? 1 : 0; 614 if (b == b0) 615 return 0; 616 } 617 } 618 619 /* Renumber entries following p, which we will be deleting. */ 620 PG_STATIC void 621 renumberHist(struct Hist *p) 622 { 623 int n = p->Href; 624 while ((p = p->Hnext)) 625 p->Href = n--; 626 } 627 628 /* The hash table is implemented as an array of pointers to Hist entries. Each 629 * entry is located in the table using hash2tableIndex() and checking the 630 * following entries in case of a collision (linear rehash). Free entries in 631 * the table are zero (0, NULL, emptyHTE). Deleted entries that cannot yet be 632 * freed are set to one (deletedHTE). The Hist.Hhash member is non-zero iff 633 * the entry is in the hash table. When the hash table get too full, it is 634 * reallocated to be approximately twice the history length (see 635 * getHashTableSize). */ 636 static struct Hist **histHashTable = NULL; 637 static unsigned histHashTableLength = 0; /* number of Hist pointers in table */ 638 639 static struct Hist * const emptyHTE = NULL; 640 static struct Hist * const deletedHTE = (struct Hist *)1; 641 642 static struct { 643 unsigned insertCount; 644 unsigned removeCount; 645 unsigned rehashes; 646 int deleted; 647 } hashStats; 648 649 #ifdef DEBUG_HIST 650 void 651 checkHistHashTable(int print) 652 { 653 unsigned occupied = 0; 654 unsigned deleted = 0; 655 unsigned i; 656 for (i = 0; i<histHashTableLength; i++) 657 if (histHashTable[i] == emptyHTE) 658 continue; 659 else if (histHashTable[i] == deletedHTE) 660 deleted++; 661 else 662 occupied++; 663 if (print) 664 xprintf(" found len %u occupied %u deleted %u\n", 665 histHashTableLength, occupied, deleted); 666 assert(deleted == hashStats.deleted); 667 } 668 669 static int doneTest = 0; 670 671 /* Main entry point for displaying history statistics and hash function 672 * behavior. */ 673 void 674 displayHistStats(const char *reason) 675 { 676 /* Just hash statistics for now. */ 677 xprintf("%s history hash table len %u count %u (deleted %d)\n", reason, 678 histHashTableLength, histCount, hashStats.deleted); 679 xprintf(" inserts %u rehashes %u%% each\n", 680 hashStats.insertCount, 681 (hashStats.insertCount 682 ? 100*hashStats.rehashes/hashStats.insertCount : 0)); 683 xprintf(" removes %u net %u\n", 684 hashStats.removeCount, 685 hashStats.insertCount - hashStats.removeCount); 686 assert(hashStats.insertCount >= hashStats.removeCount); 687 checkHistHashTable(1); 688 memset(&hashStats, 0, sizeof(hashStats)); 689 if (!doneTest) { 690 testHash(); 691 doneTest = 1; 692 } 693 } 694 #else 695 void 696 displayHistStats(const char *reason) 697 { 698 USE(reason); 699 } 700 #endif 701 702 static void 703 discardHistHashTable(void) 704 { 705 if (histHashTable == NULL) 706 return; 707 displayHistStats("Discarding"); 708 xfree(histHashTable); 709 histHashTable = NULL; 710 } 711 712 /* Computes a new hash table size, when the current one is too small. */ 713 static unsigned 714 getHashTableSize(int histlen) 715 { 716 unsigned target = histlen * 2; 717 unsigned e = 5; 718 unsigned size; 719 while ((size = 1<<e) < target) 720 e++; 721 #ifdef PRIME_LENGTH /* need good HTL */ 722 /* Not all prime, but most are and none have factors smaller than 11. */ 723 return size+15; 724 #else 725 assert((size & (size-1)) == 0); /* must be a power of two */ 726 return size; 727 #endif 728 } 729 730 /* Create the hash table or resize, if necessary. */ 731 static void 732 createHistHashTable(int histlen) 733 { 734 if (histlen == 0) { 735 discardHistHashTable(); 736 return; 737 } 738 if (histlen < 0) { 739 histlen = getn(varval(STRhistory)); 740 if (histlen == 0) 741 return; /* no need for hash table */ 742 assert(histlen > 0); 743 } 744 if (histHashTable != NULL) { 745 if (histCount < histHashTableLength * 3 / 4) 746 return; /* good enough for now */ 747 discardHistHashTable(); /* too small */ 748 } 749 histHashTableLength = getHashTableSize( 750 histlen > (int)histCount ? histlen : (int)histCount); 751 histHashTable = xmalloc(histHashTableLength * sizeof(struct Hist *)); 752 memset(histHashTable, 0, histHashTableLength * sizeof(struct Hist *)); 753 assert(histHashTable[0] == emptyHTE); 754 755 /* Now insert all the entries on the history list into the hash table. */ 756 { 757 struct Hist *hp; 758 for (hp = &Histlist; (hp = hp->Hnext) != NULL;) { 759 unsigned lpHash = hashhist(&hp->Hlex); 760 assert(!hp->Hhash || hp->Hhash == lpHash); 761 hp->Hhash = 0; /* force insert to new hash table */ 762 insertHistHashTable(hp, lpHash); 763 } 764 } 765 } 766 767 /* Insert np into the hash table. We assume that np is already on the 768 * Histlist. The specified hashval matches the new Hist entry but has not yet 769 * been assigned to Hhash (or the element is already on the hash table). */ 770 static void 771 insertHistHashTable(struct Hist *np, unsigned hashval) 772 { 773 unsigned rehashes = 0; 774 unsigned hi = 0; 775 if (!histHashTable) 776 return; 777 if (np->Hhash != 0) { 778 /* already in hash table */ 779 assert(hashval == np->Hhash); 780 return; 781 } 782 assert(np != deletedHTE); 783 /* Find a free (empty or deleted) slot, using linear rehash. */ 784 assert(histHashTable); 785 for (rehashes = 0; 786 ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)), 787 histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE); 788 rehashes++) { 789 assert(np != histHashTable[hi]); 790 if (rehashes >= histHashTableLength / 10) { 791 /* Hash table is full, so grow it. We assume the create function 792 * will roughly double the size we give it. Create initializes the 793 * new table with everything on the Histlist, so we are done when 794 * it returns. */ 795 #ifdef DEBUG_HIST 796 xprintf("Growing history hash table from %d ...", 797 histHashTableLength); 798 flush(); 799 #endif 800 discardHistHashTable(); 801 createHistHashTable(histHashTableLength); 802 #ifdef DEBUG_HIST 803 xprintf("to %d.\n", histHashTableLength); 804 #endif 805 return; 806 } 807 } 808 /* Might be sensible to grow hash table if rehashes is "too big" here. */ 809 if (histHashTable[hi] == deletedHTE) 810 hashStats.deleted--; 811 histHashTable[hi] = np; 812 np->Hhash = hashval; 813 hashStats.insertCount++; 814 hashStats.rehashes += rehashes; 815 } 816 817 /* Remove the 'np' entry from the hash table. */ 818 static void 819 removeHistHashTable(struct Hist *np) 820 { 821 unsigned hi = np->Hhash; 822 if (!histHashTable || !hi) 823 return; /* no hash table or not on it */ 824 /* find desired entry */ 825 while ((hi = hash2tableIndex(hi, histHashTableLength)), 826 histHashTable[hi] != emptyHTE) { 827 if (np == histHashTable[hi]) { 828 unsigned i; 829 unsigned deletes = 0; 830 histHashTable[hi] = deletedHTE; /* dummy, but non-zero entry */ 831 /* now peek ahead to see if the dummies are really necessary. */ 832 i = 1; 833 while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == 834 deletedHTE) 835 i++; 836 if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == 837 emptyHTE) { 838 /* dummies are no longer necessary placeholders. */ 839 deletes = i; 840 while (i-- > 0) { 841 histHashTable[hash2tableIndex(hi+i, histHashTableLength)] = 842 emptyHTE; 843 } 844 } 845 hashStats.deleted += 1 - deletes; /* delta deleted entries */ 846 hashStats.removeCount++; 847 return; 848 } 849 hi++; /* linear rehash */ 850 } 851 assert(!"Hist entry not found in hash table"); 852 } 853 854 /* Search the history hash table for a command matching lp, using hashval as 855 * its hash value. */ 856 static struct Hist * 857 findHistHashTable(struct wordent *lp, unsigned hashval) 858 { 859 unsigned deleted = 0; /* number of deleted entries skipped */ 860 unsigned hi = hashval; 861 struct Hist *hp; 862 if (!histHashTable) 863 return NULL; 864 while ((hi = hash2tableIndex(hi, histHashTableLength)), 865 (hp = histHashTable[hi]) != emptyHTE) { 866 if (hp == deletedHTE) 867 deleted++; 868 else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex))) 869 return hp; 870 if (deleted > (histHashTableLength>>4)) { 871 /* lots of deletes, so we need a sparser table. */ 872 discardHistHashTable(); 873 createHistHashTable(histHashTableLength); 874 return findHistHashTable(lp, hashval); 875 } 876 hi++; /* linear rehash */ 877 } 878 return NULL; 879 } 880 881 /* When merge semantics are in use, find the approximate predecessor for the 882 * new entry, so that the Htime entries are decreasing. Return the entry just 883 * before the first entry with equal times, so the caller can check for 884 * duplicates. When pTime is not NULL, use it as a starting point for search, 885 * otherwise search from beginning (largest time value) of history list. */ 886 PG_STATIC struct Hist * 887 mergeInsertionPoint( 888 struct Hist *np, /* new entry to be inserted */ 889 struct Hist *pTime) /* hint about where to insert */ 890 { 891 struct Hist *pp, *p; 892 if (histTail && histTail->Htime >= np->Htime) 893 pTime = histTail; /* new entry goes at the end */ 894 if (histMerg && histMerg != &Histlist && histMerg != Histlist.Hnext) { 895 /* Check above and below previous insertion point, in case we're adding 896 * sequential times in the middle of the list (e.g. history -M). */ 897 if (histMerg->Htime >= np->Htime) 898 pTime = histMerg; 899 else if (histMerg->Hprev->Htime >= np->Htime) 900 pTime = histMerg->Hprev; 901 } 902 if (pTime) { 903 /* With hint, search up the list until Htime is greater. We skip past 904 * the equal ones, too, so our caller can elide duplicates. */ 905 pp = pTime; 906 while (pp != &Histlist && pp->Htime <= np->Htime) 907 pp = pp->Hprev; 908 } else 909 pp = &Histlist; 910 /* Search down the list while current entry's time is too large. */ 911 while ((p = pp->Hnext) && (p->Htime > np->Htime)) 912 pp = p; /* advance insertion point */ 913 /* Remember recent position as hint for next time */ 914 histMerg = pp; 915 return pp; 916 } 917 918 /* Bubble Hnum & Href in new entry down to pp through earlier part of list. */ 919 PG_STATIC void bubbleHnumHrefDown(struct Hist *np, struct Hist *pp) 920 { 921 struct Hist *p; 922 for (p = Histlist.Hnext; p != pp->Hnext; p = p->Hnext) { 923 /* swap Hnum & Href values of p and np. */ 924 int n = p->Hnum, r = p->Href; 925 p->Hnum = np->Hnum; p->Href = np->Href; 926 np->Hnum = n; np->Href = r; 927 } 928 } 929 930 /* Enter new command into the history list according to current settings. */ 931 struct Hist * 932 enthist( 933 int event, /* newly incremented global eventno */ 934 struct wordent *lp, 935 int docopy, 936 int mflg, /* true if merge requested */ 937 int histlen) /* -1 if unknown */ 938 { 939 struct Hist *p = NULL, *pp = &Histlist, *pTime = NULL; 940 struct Hist *np; 941 const Char *dp; 942 unsigned lpHash = 0; /* non-zero if hashing entries */ 943 944 if ((dp = varval(STRhistdup)) != STRNULL) { 945 if (eq(dp, STRerase)) { 946 /* masaoki@akebono.tky.hp.com (Kobayashi Masaoki) */ 947 createHistHashTable(histlen); 948 lpHash = hashhist(lp); 949 assert(lpHash != 0); 950 p = findHistHashTable(lp, lpHash); 951 if (p) { 952 if (Htime != 0 && p->Htime > Htime) 953 Htime = p->Htime; 954 /* If we are merging, and the old entry is at the place we want 955 * to insert the new entry, then remember the place. */ 956 if (mflg && Htime != 0 && p->Hprev->Htime >= Htime) 957 pTime = p->Hprev; 958 if (!fastMergeErase) 959 renumberHist(p); /* Reset Href of subsequent entries */ 960 hremove(p); 961 hfree(p); 962 p = NULL; /* so new entry is allocated below */ 963 } 964 } 965 else if (eq(dp, STRall)) { 966 createHistHashTable(histlen); 967 lpHash = hashhist(lp); 968 assert(lpHash != 0); 969 p = findHistHashTable(lp, lpHash); 970 if (p) /* p!=NULL, only update this entry's Htime below */ 971 eventno--; /* not adding a new event */ 972 } 973 else if (eq(dp, STRprev)) { 974 if (pp->Hnext && heq(lp, &(pp->Hnext->Hlex))) { 975 p = pp->Hnext; 976 eventno--; 977 } 978 } 979 } 980 981 np = p ? p : xmalloc(sizeof(*np)); 982 983 /* Pick up timestamp set by lex() in Htime if reading saved history */ 984 if (Htime != 0) { 985 np->Htime = Htime; 986 Htime = 0; 987 } 988 else 989 (void) time(&(np->Htime)); 990 991 if (p == np) 992 return np; /* reused existing entry */ 993 994 /* Initialize the new entry. */ 995 np->Hnum = np->Href = event; 996 if (docopy) { 997 copylex(&np->Hlex, lp); 998 if (histvalid) 999 np->histline = Strsave(histline.s); 1000 else 1001 np->histline = NULL; 1002 } 1003 else { 1004 np->Hlex.next = lp->next; 1005 lp->next->prev = &np->Hlex; 1006 np->Hlex.prev = lp->prev; 1007 lp->prev->next = &np->Hlex; 1008 np->histline = NULL; 1009 } 1010 np->Hhash = 0; 1011 1012 /* The head of history list is the default insertion point. 1013 If merging, advance insertion point, in pp, according to Htime. */ 1014 /* XXX -- In histdup=all, Htime values can be non-monotonic. */ 1015 if (mflg) { /* merge according to np->Htime */ 1016 pp = mergeInsertionPoint(np, pTime); 1017 for (p = pp->Hnext; p && p->Htime == np->Htime; pp = p, p = p->Hnext) { 1018 if (heq(&p->Hlex, &np->Hlex)) { 1019 eventno--; /* duplicate, so don't add new event */ 1020 hfree(np); 1021 return (p); 1022 } 1023 } 1024 /* pp is now the last entry with time >= to np. */ 1025 if (!fastMergeErase) { /* renumber at end of loadhist */ 1026 /* Before inserting np after pp, bubble its Hnum & Href values down 1027 * through the earlier part of list. */ 1028 bubbleHnumHrefDown(np, pp); 1029 } 1030 } 1031 else 1032 pp = &Histlist; /* insert at beginning of history */ 1033 hinsert(np, pp); 1034 if (lpHash && histlen != 0) /* erase & all modes use hash table */ 1035 insertHistHashTable(np, lpHash); 1036 else 1037 discardHistHashTable(); 1038 return (np); 1039 } 1040 1041 static void 1042 hfree(struct Hist *hp) 1043 { 1044 assert(hp != histMerg); 1045 if (hp->Hhash) 1046 removeHistHashTable(hp); 1047 freelex(&hp->Hlex); 1048 if (hp->histline) 1049 xfree(hp->histline); 1050 xfree(hp); 1051 } 1052 1053 PG_STATIC void 1054 phist(struct Hist *hp, int hflg) 1055 { 1056 if (hflg & HIST_ONLY) { 1057 int old_output_raw; 1058 1059 /* 1060 * Control characters have to be written as is (output_raw). 1061 * This way one can preserve special characters (like tab) in 1062 * the history file. 1063 * From: mveksler@vnet.ibm.com (Veksler Michael) 1064 */ 1065 old_output_raw = output_raw; 1066 output_raw = 1; 1067 cleanup_push(&old_output_raw, output_raw_restore); 1068 if (hflg & HIST_TIME) 1069 /* 1070 * Make file entry with history time in format: 1071 * "+NNNNNNNNNN" (10 digits, left padded with ascii '0') 1072 */ 1073 1074 xprintf("#+%010lu\n", (unsigned long)hp->Htime); 1075 1076 if (HistLit && hp->histline) 1077 xprintf("%S\n", hp->histline); 1078 else 1079 prlex(&hp->Hlex); 1080 cleanup_until(&old_output_raw); 1081 } 1082 else { 1083 Char *cp = str2short("%h\t%T\t%R\n"); 1084 Char *p; 1085 struct varent *vp = adrof(STRhistory); 1086 1087 if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1]) 1088 cp = vp->vec[1]; 1089 1090 p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp); 1091 cleanup_push(p, xfree); 1092 for (cp = p; *cp;) 1093 xputwchar(*cp++); 1094 cleanup_until(p); 1095 } 1096 } 1097 1098 PG_STATIC void 1099 dophist(int n, int hflg) 1100 { 1101 struct Hist *hp; 1102 if (setintr) { 1103 int old_pintr_disabled; 1104 1105 pintr_push_enable(&old_pintr_disabled); 1106 cleanup_until(&old_pintr_disabled); 1107 } 1108 if ((hflg & HIST_REV) == 0) { 1109 /* Since the history list is stored most recent first, non-reversing 1110 * print needs to print (backwards) up the list. */ 1111 if ((unsigned)n >= histCount) 1112 hp = histTail; 1113 else { 1114 for (hp = Histlist.Hnext; 1115 --n > 0 && hp->Hnext != NULL; 1116 hp = hp->Hnext) 1117 ; 1118 } 1119 if (hp == NULL) 1120 return; /* nothing to print */ 1121 for (; hp != &Histlist; hp = hp->Hprev) 1122 phist(hp, hflg); 1123 } else { 1124 for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext) 1125 phist(hp, hflg); 1126 } 1127 } 1128 1129 /*ARGSUSED*/ 1130 void 1131 dohist(Char **vp, struct command *c) 1132 { 1133 int n, hflg = 0; 1134 1135 USE(c); 1136 if (getn(varval(STRhistory)) == 0) 1137 return; 1138 while (*++vp && **vp == '-') { 1139 Char *vp2 = *vp; 1140 1141 while (*++vp2) 1142 switch (*vp2) { 1143 case 'c': 1144 hflg |= HIST_CLEAR; 1145 break; 1146 case 'h': 1147 hflg |= HIST_ONLY; 1148 break; 1149 case 'r': 1150 hflg |= HIST_REV; 1151 break; 1152 case 'S': 1153 hflg |= HIST_SAVE; 1154 break; 1155 case 'L': 1156 hflg |= HIST_LOAD; 1157 break; 1158 case 'M': 1159 hflg |= HIST_MERGE; 1160 break; 1161 case 'T': 1162 hflg |= HIST_TIME; 1163 break; 1164 default: 1165 stderror(ERR_HISTUS, "chrSLMT"); 1166 break; 1167 } 1168 } 1169 if (hflg & HIST_CLEAR) { 1170 struct Hist *np, *hp; 1171 for (hp = &Histlist; (np = hp->Hnext) != NULL;) 1172 hremove(np), hfree(np); 1173 } 1174 1175 if (hflg & (HIST_LOAD | HIST_MERGE)) 1176 loadhist(*vp, (hflg & HIST_MERGE) ? 1 : 0); 1177 else if (hflg & HIST_SAVE) 1178 rechist(*vp, 1); 1179 else { 1180 if (*vp) 1181 n = getn(*vp); 1182 else { 1183 n = getn(varval(STRhistory)); 1184 } 1185 dophist(n, hflg); 1186 } 1187 } 1188 1189 1190 char * 1191 fmthist(int fmt, ptr_t ptr) 1192 { 1193 struct Hist *hp = ptr; 1194 char *buf; 1195 1196 switch (fmt) { 1197 case 'h': 1198 return xasprintf("%6d", hp->Hnum); 1199 case 'R': 1200 if (HistLit && hp->histline) 1201 return xasprintf("%S", hp->histline); 1202 else { 1203 Char *istr, *ip; 1204 char *p; 1205 1206 istr = sprlex(&hp->Hlex); 1207 buf = xmalloc(Strlen(istr) * MB_LEN_MAX + 1); 1208 1209 for (p = buf, ip = istr; *ip != '\0'; ip++) 1210 p += one_wctomb(p, CHAR & *ip); 1211 1212 *p = '\0'; 1213 xfree(istr); 1214 return buf; 1215 } 1216 default: 1217 buf = xmalloc(1); 1218 buf[0] = '\0'; 1219 return buf; 1220 } 1221 } 1222 1223 /* Save history before exiting the shell. */ 1224 void 1225 rechist(Char *fname, int ref) 1226 { 1227 Char *snum; 1228 int fp, ftmp, oldidfds; 1229 struct varent *shist; 1230 static Char *dumphist[] = {STRhistory, STRmhT, 0, 0}; 1231 1232 if (fname == NULL && !ref) 1233 return; 1234 /* 1235 * If $savehist is just set, we use the value of $history 1236 * else we use the value in $savehist 1237 */ 1238 if (((snum = varval(STRsavehist)) == STRNULL) && 1239 ((snum = varval(STRhistory)) == STRNULL)) 1240 snum = STRmaxint; 1241 1242 1243 if (fname == NULL) { 1244 if ((fname = varval(STRhistfile)) == STRNULL) 1245 fname = Strspl(varval(STRhome), &STRtildothist[1]); 1246 else 1247 fname = Strsave(fname); 1248 } 1249 else 1250 fname = globone(fname, G_ERROR); 1251 cleanup_push(fname, xfree); 1252 1253 /* 1254 * The 'savehist merge' feature is intended for an environment 1255 * with numerous shells being in simultaneous use. Imagine 1256 * any kind of window system. All these shells 'share' the same 1257 * ~/.history file for recording their command line history. 1258 * Currently the automatic merge can only succeed when the shells 1259 * nicely quit one after another. 1260 * 1261 * Users that like to nuke their environment require here an atomic 1262 * loadhist-creat-dohist(dumphist)-close 1263 * sequence. 1264 * 1265 * jw. 1266 */ 1267 /* 1268 * We need the didfds stuff before loadhist otherwise 1269 * exec in a script will fail to print if merge is set. 1270 * From: mveksler@iil.intel.com (Veksler Michael) 1271 */ 1272 oldidfds = didfds; 1273 didfds = 0; 1274 if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL) 1275 if (shist->vec[1] && eq(shist->vec[1], STRmerge)) 1276 loadhist(fname, 1); 1277 1278 fp = xcreat(short2str(fname), 0600); 1279 cleanup_until(fname); 1280 if (fp == -1) { 1281 didfds = oldidfds; 1282 return; 1283 } 1284 ftmp = SHOUT; 1285 SHOUT = fp; 1286 dumphist[2] = snum; 1287 dohist(dumphist, NULL); 1288 xclose(fp); 1289 SHOUT = ftmp; 1290 didfds = oldidfds; 1291 } 1292 1293 1294 /* This is the entry point for loading history data from a file. */ 1295 void 1296 loadhist(Char *fname, int mflg) 1297 { 1298 static Char *loadhist_cmd[] = {STRsource, NULL, NULL, NULL}; 1299 loadhist_cmd[1] = mflg ? STRmm : STRmh; 1300 1301 if (fname != NULL) 1302 loadhist_cmd[2] = fname; 1303 else if ((fname = varval(STRhistfile)) != STRNULL) 1304 loadhist_cmd[2] = fname; 1305 else 1306 loadhist_cmd[2] = STRtildothist; 1307 1308 dosource(loadhist_cmd, NULL); 1309 1310 /* During history merging (enthist sees mflg set), we disable management of 1311 * Hnum and Href (because fastMergeErase is true). So now reset all the 1312 * values based on the final ordering of the history list. */ 1313 if (mflg) { 1314 int n = eventno; 1315 struct Hist *hp = &Histlist; 1316 while ((hp = hp->Hnext)) 1317 hp->Hnum = hp->Href = n--; 1318 } 1319 } 1320