"Fossies" - the Fresh Open Source Software Archive

Member "tcsh-6.22.03/sh.hist.c" (18 Nov 2020, 38840 Bytes) of package /linux/misc/tcsh-6.22.03.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "sh.hist.c": 6.22.02_vs_6.22.03.

    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, ophup_disabled;
 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     ophup_disabled = phup_disabled;
 1232     phup_disabled = 1;
 1233 
 1234     /*
 1235      * If $savehist is just set, we use the value of $history
 1236      * else we use the value in $savehist
 1237      */
 1238     if (((snum = varval(STRsavehist)) == STRNULL) &&
 1239     ((snum = varval(STRhistory)) == STRNULL))
 1240     snum = STRmaxint;
 1241 
 1242 
 1243     if (fname == NULL) {
 1244     if ((fname = varval(STRhistfile)) == STRNULL)
 1245         fname = Strspl(varval(STRhome), &STRtildothist[1]);
 1246     else
 1247         fname = Strsave(fname);
 1248     }
 1249     else
 1250     fname = globone(fname, G_ERROR);
 1251     cleanup_push(fname, xfree);
 1252 
 1253     /*
 1254      * The 'savehist merge' feature is intended for an environment
 1255      * with numerous shells being in simultaneous use. Imagine
 1256      * any kind of window system. All these shells 'share' the same 
 1257      * ~/.history file for recording their command line history. 
 1258      * We try to handle the case of multiple shells trying to merge
 1259      * histories at the same time, by creating semi-unique filenames
 1260      * and saving the history there first and then trying to rename
 1261      * them in the proper history file.
 1262      *
 1263      * Users that like to nuke their environment require here an atomic
 1264      * loadhist-creat-dohist(dumphist)-close sequence which is given
 1265          * by optional lock parameter to savehist.
 1266      *
 1267      * jw.
 1268      */ 
 1269     /*
 1270      * We need the didfds stuff before loadhist otherwise
 1271      * exec in a script will fail to print if merge is set.
 1272      * From: mveksler@iil.intel.com (Veksler Michael)
 1273      */
 1274     oldidfds = didfds;
 1275     didfds = 0;
 1276     if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL) {
 1277     size_t i;
 1278     int merge = 0, lock = 0;
 1279 
 1280     for (i = 1; shist->vec[i]; i++) {
 1281         if (eq(shist->vec[i], STRmerge))
 1282         merge++;
 1283         if (eq(shist->vec[i], STRlock))
 1284         lock++;
 1285     }
 1286 
 1287     if (merge) {
 1288         jmp_buf_t osetexit;
 1289         if (lock) {
 1290 #ifndef WINNT_NATIVE
 1291         char *lockpath = strsave(short2str(fname));
 1292         cleanup_push(lockpath, xfree);
 1293         /* Poll in 100 miliseconds interval to obtain the lock. */
 1294         if ((dot_lock(lockpath, 100) == 0))
 1295             cleanup_push(lockpath, dotlock_cleanup);
 1296 #endif
 1297         }
 1298         getexit(osetexit);
 1299         if (setexit() == 0)
 1300         loadhist(fname, 1);
 1301         resexit(osetexit);
 1302     }
 1303     }
 1304     rs = randsuf();
 1305     xsnprintf(path, sizeof(path), "%S.%S", fname, rs);
 1306     xfree(rs);
 1307 
 1308     fp = xcreat(path, 0600);
 1309     if (fp == -1) {
 1310     didfds = oldidfds;
 1311     cleanup_until(fname);
 1312     phup_disabled = ophup_disabled;
 1313     return;
 1314     }
 1315     /* Try to preserve ownership and permissions of the original history file */
 1316 #ifndef WINNT_NATIVE
 1317     if (stat(short2str(fname), &st) != -1) {
 1318     TCSH_IGNORE(fchown(fp, st.st_uid, st.st_gid));
 1319     TCSH_IGNORE(fchmod(fp, st.st_mode));
 1320     }
 1321 #else
 1322     UNREFERENCED_PARAMETER(st);
 1323 #endif
 1324     ftmp = SHOUT;
 1325     SHOUT = fp;
 1326     dumphist[2] = snum;
 1327     dohist(dumphist, NULL);
 1328     xclose(fp);
 1329     SHOUT = ftmp;
 1330     didfds = oldidfds;
 1331 #ifndef WINNT_NATIVE
 1332     (void)rename(path, short2str(fname));
 1333 #else
 1334     (void)ReplaceFile( short2str(fname),path,NULL,0,NULL,NULL);
 1335 #endif
 1336     cleanup_until(fname);
 1337     phup_disabled = ophup_disabled;
 1338 }
 1339 
 1340 
 1341 /* This is the entry point for loading history data from a file. */
 1342 void
 1343 loadhist(Char *fname, int mflg)
 1344 {
 1345     static Char   *loadhist_cmd[] = {STRsource, NULL, NULL, NULL};
 1346     loadhist_cmd[1] = mflg ? STRmm : STRmh;
 1347 
 1348     if (fname != NULL)
 1349     loadhist_cmd[2] = fname;
 1350     else if ((fname = varval(STRhistfile)) != STRNULL)
 1351     loadhist_cmd[2] = fname;
 1352     else
 1353     loadhist_cmd[2] = STRtildothist;
 1354 
 1355     dosource(loadhist_cmd, NULL);
 1356 
 1357     /* During history merging (enthist sees mflg set), we disable management of
 1358      * Hnum and Href (because fastMergeErase is true).  So now reset all the
 1359      * values based on the final ordering of the history list. */
 1360     if (mflg) {
 1361     int n = eventno;
 1362         struct Hist *hp = &Histlist;
 1363         while ((hp = hp->Hnext))
 1364         hp->Hnum = hp->Href = n--;
 1365     }
 1366 }
 1367 
 1368 void
 1369 sethistory(int n)
 1370 {
 1371     histlen = n;
 1372     discardExcess(histlen);
 1373 }