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