Lines Matching +full:hi +full:- +full:speed
4 /*-
79 struct Hist *fp = pp->Hnext; /* following element, if any */ in hinsert()
80 hp->Hnext = fp, hp->Hprev = pp; in hinsert()
81 pp->Hnext = hp; in hinsert()
83 fp->Hprev = hp; in hinsert()
85 histTail = hp; /* meaning hp->Hnext == NULL */ in hinsert()
93 struct Hist *pp = hp->Hprev; in hremove()
95 pp->Hnext = hp->Hnext; in hremove()
96 if (hp->Hnext) in hremove()
97 hp->Hnext->Hprev = pp; in hremove()
103 histCount--; in hremove()
119 if (eventno - np->Href >= hlen || hlen == 0) in discardExcess()
125 if (eventno - np->Href >= hlen || hlen == 0) in discardExcess()
130 if (histCount - (hlen >> 4) <= (unsigned)hlen) in discardExcess()
133 (np = hp->Hnext) != NULL;) in discardExcess()
134 if (eventno - np->Href >= hlen || hlen == 0) in discardExcess()
144 int mflg) /* true if -m (merge) specified */ in savehist()
147 if (sp && sp->next->word[0] == '\n') in savehist()
167 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
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; \
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); \
197 h->a = h->b = h->c = 0xdeadbeef; in initializeHash()
201 * include 3 versions of the code to pack Chars into 32-bit words for the
206 uint32_t a = h->a, b = h->b, c = h->c; in addWordToHash()
259 h->a = a, h->b = b, h->c = c; in addWordToHash()
265 /* The compiler (gcc -O2) seems to do a good job optimizing this without in addCharToHash()
267 h->a += (uChar)ch; in addCharToHash()
268 mix(h->a, h->b, h->c); in addCharToHash()
274 uint32_t a = h->a, b = h->b, c = h->c; in finalizeHash()
280 #define hashFcnName "one-at-a-time"
307 h->h = 0; in initializeHash()
314 uint32_t hash = h->h; in addWordToHash()
317 h->h = hash; in addWordToHash()
330 unsigned hash = h->h; in finalizeHash()
338 #define hashFcnName "add-mul"
345 h->h = 0xe13e2345; in initializeHash()
352 uint32_t hash = h->h; in addWordToHash()
355 h->h = hash; in addWordToHash()
361 h->h = h->h * 0x9e4167b9 + (uChar)c; in addCharToHash()
367 return h->h; in finalizeHash()
375 struct wordent *firstWord = h0->next; in hashhist()
380 for (; h != h0; h = h->next) { in hashhist()
381 if (h->word[0] == '\n') in hashhist()
385 addWordToHash(&s, h->word); in hashhist()
406 #define hash2tableIndex(hash, len) ((hash) & (len-1))
409 /* This code can be enabled to test the above hash functions for speed and
424 return (now.tv_sec-beginTime.tv_sec) + in doTiming()
425 (now.tv_usec-beginTime.tv_usec)/1e6; in doTiming()
449 unsigned wBoundaries[4] = { 2-1, 2+3-1, 2+3+5-1, 0 }; in generateHashes()
451 while (nWords >= 2 && nChars < (wBoundaries[nWords-2]+1) + 4) in generateHashes()
452 nWords--; in generateHashes()
453 wBoundaries[nWords-1] = 0xffffffff; /* don't end word past this point */ in generateHashes()
456 /* In deference to the gawd awful add-mul hash, we won't use the worse in generateHashes()
465 word[w].next = &base, word[w].prev = &word[w-1]; in generateHashes()
466 word[w-1].next = &word[w], base.prev = &word[w]; in generateHashes()
478 unsigned j = nChars-1 + w; in generateHashes()
486 j--; in generateHashes()
517 if (vp && vp->vec) { in testHash()
519 Char **vals = vp->vec; in testHash()
546 hits = highest = sizeof(bins)/sizeof(bins[0]) - 1; in testHash()
567 hits = 1 && rehashed--; in testHash()
569 rehashed += hits-1; in testHash()
575 run = highest = sizeof(bins)/sizeof(bins[0]) - 1; in testHash()
602 const struct wordent *a = a0->next, *b = b0->next; in heq()
605 if (Strcmp(a->word, b->word) != 0) in heq()
607 a = a->next; in heq()
608 b = b->next; in heq()
620 int n = p->Href; in renumberHist()
621 while ((p = p->Hnext)) in renumberHist()
622 p->Href = n--; in renumberHist()
629 * freed are set to one (deletedHTE). The Hist.Hhash member is non-zero iff
682 hashStats.insertCount - hashStats.removeCount); in displayHistStats()
722 assert((size & (size-1)) == 0); /* must be a power of two */ in getHashTableSize()
754 for (hp = &Histlist; (hp = hp->Hnext) != NULL;) { in createHistHashTable()
755 unsigned lpHash = hashhist(&hp->Hlex); in createHistHashTable()
756 assert(!hp->Hhash || hp->Hhash == lpHash); in createHistHashTable()
757 hp->Hhash = 0; /* force insert to new hash table */ in createHistHashTable()
770 unsigned hi = 0; in insertHistHashTable() local
773 if (np->Hhash != 0) { in insertHistHashTable()
775 assert(hashval == np->Hhash); in insertHistHashTable()
782 ((hi = hash2tableIndex(hashval + rehashes, histHashTableLength)), in insertHistHashTable()
783 histHashTable[hi] != emptyHTE && histHashTable[hi] != deletedHTE); in insertHistHashTable()
785 assert(np != histHashTable[hi]); in insertHistHashTable()
805 if (histHashTable[hi] == deletedHTE) in insertHistHashTable()
806 hashStats.deleted--; in insertHistHashTable()
807 histHashTable[hi] = np; in insertHistHashTable()
808 np->Hhash = hashval; in insertHistHashTable()
817 unsigned hi = np->Hhash; in removeHistHashTable() local
818 if (!histHashTable || !hi) in removeHistHashTable()
821 while ((hi = hash2tableIndex(hi, histHashTableLength)), in removeHistHashTable()
822 histHashTable[hi] != emptyHTE) { in removeHistHashTable()
823 if (np == histHashTable[hi]) { in removeHistHashTable()
826 histHashTable[hi] = deletedHTE; /* dummy, but non-zero entry */ in removeHistHashTable()
829 while (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == in removeHistHashTable()
832 if (histHashTable[hash2tableIndex(hi+i, histHashTableLength)] == in removeHistHashTable()
836 while (i-- > 0) { in removeHistHashTable()
837 histHashTable[hash2tableIndex(hi+i, histHashTableLength)] = in removeHistHashTable()
841 hashStats.deleted += 1 - deletes; /* delta deleted entries */ in removeHistHashTable()
845 hi++; /* linear rehash */ in removeHistHashTable()
856 unsigned hi = hashval; in findHistHashTable() local
860 while ((hi = hash2tableIndex(hi, histHashTableLength)), in findHistHashTable()
861 (hp = histHashTable[hi]) != emptyHTE) { in findHistHashTable()
864 else if (hp->Hhash == hashval && heq(lp, &(hp->Hlex))) in findHistHashTable()
872 hi++; /* linear rehash */ in findHistHashTable()
888 if (histTail && histTail->Htime >= np->Htime) in mergeInsertionPoint()
892 * sequential times in the middle of the list (e.g. history -M). */ in mergeInsertionPoint()
893 if (histMerg->Htime >= np->Htime) in mergeInsertionPoint()
895 else if (histMerg->Hprev->Htime >= np->Htime) in mergeInsertionPoint()
896 pTime = histMerg->Hprev; in mergeInsertionPoint()
902 while (pp != &Histlist && pp->Htime <= np->Htime) in mergeInsertionPoint()
903 pp = pp->Hprev; in mergeInsertionPoint()
907 while ((p = pp->Hnext) && (p->Htime > np->Htime)) in mergeInsertionPoint()
918 for (p = Histlist.Hnext; p != pp->Hnext; p = p->Hnext) { in bubbleHnumHrefDown()
920 int n = p->Hnum, r = p->Href; in bubbleHnumHrefDown()
921 p->Hnum = np->Hnum; p->Href = np->Href; in bubbleHnumHrefDown()
922 np->Hnum = n; np->Href = r; in bubbleHnumHrefDown()
933 int hlen) /* -1 if unknown */ in enthist()
938 unsigned lpHash = 0; /* non-zero if hashing entries */ in enthist()
948 if (Htime != 0 && p->Htime > Htime) in enthist()
949 Htime = p->Htime; in enthist()
952 if (mflg && Htime != 0 && p->Hprev->Htime >= Htime) in enthist()
953 pTime = p->Hprev; in enthist()
967 eventno--; /* not adding a new event */ in enthist()
970 if (pp->Hnext && heq(lp, &(pp->Hnext->Hlex))) { in enthist()
971 p = pp->Hnext; in enthist()
972 eventno--; in enthist()
981 np->Htime = Htime; in enthist()
985 (void) time(&(np->Htime)); in enthist()
991 np->Hnum = np->Href = event; in enthist()
993 copylex(&np->Hlex, lp); in enthist()
995 np->histline = Strsave(histline.s); in enthist()
997 np->histline = NULL; in enthist()
1000 np->Hlex.next = lp->next; in enthist()
1001 lp->next->prev = &np->Hlex; in enthist()
1002 np->Hlex.prev = lp->prev; in enthist()
1003 lp->prev->next = &np->Hlex; in enthist()
1004 np->histline = NULL; in enthist()
1006 np->Hhash = 0; in enthist()
1010 /* XXX -- In histdup=all, Htime values can be non-monotonic. */ in enthist()
1011 if (mflg) { /* merge according to np->Htime */ in enthist()
1013 for (p = pp->Hnext; p && p->Htime == np->Htime; pp = p, p = p->Hnext) { in enthist()
1014 if (heq(&p->Hlex, &np->Hlex)) { in enthist()
1015 eventno--; /* duplicate, so don't add new event */ in enthist()
1041 if (hp->Hhash) in hfree()
1043 freelex(&hp->Hlex); in hfree()
1044 if (hp->histline) in hfree()
1045 xfree(hp->histline); in hfree()
1052 if (hp->Href < 0) in phist()
1072 xprintf("#+%010lu\n", (unsigned long)hp->Htime); in phist()
1074 if (HistLit && hp->histline) in phist()
1075 xprintf("%S\n", hp->histline); in phist()
1077 prlex(&hp->Hlex); in phist()
1085 if (vp && vp->vec != NULL && vp->vec[0] && vp->vec[1]) in phist()
1086 cp = vp->vec[1]; in phist()
1088 p = tprintf(FMT_HISTORY, cp, NULL, hp->Htime, hp); in phist()
1107 /* Since the history list is stored most recent first, non-reversing in dophist()
1113 --n > 0 && hp->Hnext != NULL; in dophist()
1114 hp = hp->Hnext) in dophist()
1119 for (; hp != &Histlist; hp = hp->Hprev) in dophist()
1122 for (hp = Histlist.Hnext; n-- > 0 && hp != NULL; hp = hp->Hnext) in dophist()
1136 while (*++vp && **vp == '-') { in dohist()
1169 for (hp = &Histlist; (np = hp->Hnext) != NULL;) in dohist()
1196 return xasprintf("%6d", hp->Hnum); in fmthist()
1198 if (HistLit && hp->histline) in fmthist()
1199 return xasprintf("%S", hp->histline); in fmthist()
1204 istr = sprlex(&hp->Hlex); in fmthist()
1271 * histories at the same time, by creating semi-unique filenames in rechist()
1276 * loadhist-creat-dohist(dumphist)-close sequence which is given in rechist()
1288 if ((shist = adrof(STRsavehist)) != NULL && shist->vec != NULL) { in rechist()
1292 for (i = 1; shist->vec[i]; i++) { in rechist()
1293 if (eq(shist->vec[i], STRmerge)) in rechist()
1295 if (eq(shist->vec[i], STRlock)) in rechist()
1321 if (fp == -1) { in rechist()
1329 if (stat(short2str(fname), &st) != -1) { in rechist()
1375 while ((hp = hp->Hnext)) in loadhist()
1376 hp->Hnum = hp->Href = n--; in loadhist()