contrib/tcsh/sh.hist.c

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