1
/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2
/* ***** BEGIN LICENSE BLOCK *****
3
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
5
* The contents of this file are subject to the Mozilla Public License Version
6
* 1.1 (the "License"); you may not use this file except in compliance with
7
* the License. You may obtain a copy of the License at
8
* http://www.mozilla.org/MPL/
10
* Software distributed under the License is distributed on an "AS IS" basis,
11
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12
* for the specific language governing rights and limitations under the
15
* The Original Code is Mozilla JavaScript code.
17
* The Initial Developer of the Original Code is
18
* Netscape Communications Corporation.
19
* Portions created by the Initial Developer are Copyright (C) 1999-2001
20
* the Initial Developer. All Rights Reserved.
23
* Brendan Eich <brendan@mozilla.org> (Original Author)
24
* Chris Waterson <waterson@netscape.com>
26
* Alternatively, the contents of this file may be used under the terms of
27
* either of the GNU General Public License Version 2 or later (the "GPL"),
28
* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29
* in which case the provisions of the GPL or the LGPL are applicable instead
30
* of those above. If you wish to allow use of your version of this file only
31
* under the terms of either the GPL or the LGPL, and not to allow others to
32
* use your version of this file under the terms of the MPL, indicate your
33
* decision by deleting the provisions above and replace them with the notice
34
* and other provisions required by the GPL or the LGPL. If you do not delete
35
* the provisions above, a recipient may use your version of this file under
36
* the terms of any one of the MPL, the GPL or the LGPL.
38
* ***** END LICENSE BLOCK ***** */
41
* Double hashing implementation.
48
#include "jsutil.h" /* for JS_ASSERT */
51
# if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
52
# include "nsTraceMalloc.h"
56
# define METER(x) /* nothing */
60
JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes)
62
return malloc(nbytes);
66
JS_DHashFreeTable(JSDHashTable *table, void *ptr)
71
JS_PUBLIC_API(JSDHashNumber)
72
JS_DHashStringKey(JSDHashTable *table, const void *key)
75
const unsigned char *s;
78
for (s = key; *s != '\0'; s++)
79
h = (h >> (JS_DHASH_BITS - 4)) ^ (h << 4) ^ *s;
83
JS_PUBLIC_API(const void *)
84
JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry)
86
JSDHashEntryStub *stub = (JSDHashEntryStub *)entry;
91
JS_PUBLIC_API(JSDHashNumber)
92
JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
94
return (JSDHashNumber)key >> 2;
98
JS_DHashMatchEntryStub(JSDHashTable *table,
99
const JSDHashEntryHdr *entry,
102
const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
104
return stub->key == key;
107
JS_PUBLIC_API(JSBool)
108
JS_DHashMatchStringKey(JSDHashTable *table,
109
const JSDHashEntryHdr *entry,
112
const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
114
/* XXX tolerate null keys on account of sloppy Mozilla callers. */
115
return stub->key == key ||
116
(stub->key && key && strcmp(stub->key, key) == 0);
120
JS_DHashMoveEntryStub(JSDHashTable *table,
121
const JSDHashEntryHdr *from,
124
memcpy(to, from, table->entrySize);
128
JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry)
130
memset(entry, 0, table->entrySize);
134
JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry)
136
const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
138
free((void *) stub->key);
139
memset(entry, 0, table->entrySize);
143
JS_DHashFinalizeStub(JSDHashTable *table)
147
static const JSDHashTableOps stub_ops = {
151
JS_DHashVoidPtrKeyStub,
152
JS_DHashMatchEntryStub,
153
JS_DHashMoveEntryStub,
154
JS_DHashClearEntryStub,
155
JS_DHashFinalizeStub,
159
JS_PUBLIC_API(const JSDHashTableOps *)
160
JS_DHashGetStubOps(void)
165
JS_PUBLIC_API(JSDHashTable *)
166
JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
171
table = (JSDHashTable *) malloc(sizeof *table);
174
if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
182
JS_DHashTableDestroy(JSDHashTable *table)
184
JS_DHashTableFinish(table);
188
JS_PUBLIC_API(JSBool)
189
JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
190
uint32 entrySize, uint32 capacity)
196
if (entrySize > 10 * sizeof(void *)) {
198
"jsdhash: for the table at address %p, the given entrySize"
199
" of %lu %s favors chaining over double hashing.\n",
201
(unsigned long) entrySize,
202
(entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
208
if (capacity < JS_DHASH_MIN_SIZE)
209
capacity = JS_DHASH_MIN_SIZE;
210
log2 = JS_CeilingLog2(capacity);
211
capacity = JS_BIT(log2);
212
if (capacity >= JS_DHASH_SIZE_LIMIT)
214
table->hashShift = JS_DHASH_BITS - log2;
215
table->maxAlphaFrac = 0xC0; /* .75 */
216
table->minAlphaFrac = 0x40; /* .25 */
217
table->entrySize = entrySize;
218
table->entryCount = table->removedCount = 0;
219
table->generation = 0;
220
nbytes = capacity * entrySize;
222
table->entryStore = ops->allocTable(table, nbytes);
223
if (!table->entryStore)
225
memset(table->entryStore, 0, nbytes);
226
METER(memset(&table->stats, 0, sizeof table->stats));
231
* Compute max and min load numbers (entry counts) from table params.
233
#define MAX_LOAD(table, size) (((table)->maxAlphaFrac * (size)) >> 8)
234
#define MIN_LOAD(table, size) (((table)->minAlphaFrac * (size)) >> 8)
237
JS_DHashTableSetAlphaBounds(JSDHashTable *table,
244
* Reject obviously insane bounds, rather than trying to guess what the
245
* buggy caller intended.
247
JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
248
if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
252
* Ensure that at least one entry will always be free. If maxAlpha at
253
* minimum size leaves no entries free, reduce maxAlpha based on minimum
254
* size and the precision limit of maxAlphaFrac's fixed point format.
256
JS_ASSERT(JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) >= 1);
257
if (JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) < 1) {
259
(JS_DHASH_MIN_SIZE - JS_MAX(JS_DHASH_MIN_SIZE / 256, 1))
264
* Ensure that minAlpha is strictly less than half maxAlpha. Take care
265
* not to truncate an entry's worth of alpha when storing in minAlphaFrac
266
* (8-bit fixed point format).
268
JS_ASSERT(minAlpha < maxAlpha / 2);
269
if (minAlpha >= maxAlpha / 2) {
270
size = JS_DHASH_TABLE_SIZE(table);
271
minAlpha = (size * maxAlpha - JS_MAX(size / 256, 1)) / (2 * size);
274
table->maxAlphaFrac = (uint8)(maxAlpha * 256);
275
table->minAlphaFrac = (uint8)(minAlpha * 256);
279
* Double hashing needs the second hash code to be relatively prime to table
280
* size, so we simply make hash2 odd.
282
#define HASH1(hash0, shift) ((hash0) >> (shift))
283
#define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
286
* Reserve keyHash 0 for free entries and 1 for removed-entry sentinels. Note
287
* that a removed-entry sentinel need be stored only if the removed entry had
288
* a colliding entry added after it. Therefore we can use 1 as the collision
289
* flag in addition to the removed-entry sentinel value. Multiplicative hash
290
* uses the high order bits of keyHash, so this least-significant reservation
291
* should not hurt the hash function's effectiveness much.
293
* If you change any of these magic numbers, also update JS_DHASH_ENTRY_IS_LIVE
294
* in jsdhash.h. It used to be private to jsdhash.c, but then became public to
295
* assist iterator writers who inspect table->entryStore directly.
297
#define COLLISION_FLAG ((JSDHashNumber) 1)
298
#define MARK_ENTRY_FREE(entry) ((entry)->keyHash = 0)
299
#define MARK_ENTRY_REMOVED(entry) ((entry)->keyHash = 1)
300
#define ENTRY_IS_REMOVED(entry) ((entry)->keyHash == 1)
301
#define ENTRY_IS_LIVE(entry) JS_DHASH_ENTRY_IS_LIVE(entry)
302
#define ENSURE_LIVE_KEYHASH(hash0) if (hash0 < 2) hash0 -= 2; else (void)0
304
/* Match an entry's keyHash against an unstored one computed from a key. */
305
#define MATCH_ENTRY_KEYHASH(entry,hash0) \
306
(((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
308
/* Compute the address of the indexed entry in table. */
309
#define ADDRESS_ENTRY(table, index) \
310
((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
313
JS_DHashTableFinish(JSDHashTable *table)
315
char *entryAddr, *entryLimit;
317
JSDHashEntryHdr *entry;
319
#ifdef DEBUG_XXXbrendan
320
static FILE *dumpfp = NULL;
321
if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
323
#ifdef MOZILLA_CLIENT
324
NS_TraceStack(1, dumpfp);
326
JS_DHashTableDumpMeter(table, NULL, dumpfp);
331
/* Call finalize before clearing entries, so it can enumerate them. */
332
table->ops->finalize(table);
334
/* Clear any remaining live entries. */
335
entryAddr = table->entryStore;
336
entrySize = table->entrySize;
337
entryLimit = entryAddr + JS_DHASH_TABLE_SIZE(table) * entrySize;
338
while (entryAddr < entryLimit) {
339
entry = (JSDHashEntryHdr *)entryAddr;
340
if (ENTRY_IS_LIVE(entry)) {
341
METER(table->stats.removeEnums++);
342
table->ops->clearEntry(table, entry);
344
entryAddr += entrySize;
347
/* Free entry storage last. */
348
table->ops->freeTable(table, table->entryStore);
351
static JSDHashEntryHdr * JS_DHASH_FASTCALL
352
SearchTable(JSDHashTable *table, const void *key, JSDHashNumber keyHash,
355
JSDHashNumber hash1, hash2;
356
int hashShift, sizeLog2;
357
JSDHashEntryHdr *entry, *firstRemoved;
358
JSDHashMatchEntry matchEntry;
361
METER(table->stats.searches++);
362
JS_ASSERT(!(keyHash & COLLISION_FLAG));
364
/* Compute the primary hash address. */
365
hashShift = table->hashShift;
366
hash1 = HASH1(keyHash, hashShift);
367
entry = ADDRESS_ENTRY(table, hash1);
369
/* Miss: return space for a new entry. */
370
if (JS_DHASH_ENTRY_IS_FREE(entry)) {
371
METER(table->stats.misses++);
375
/* Hit: return entry. */
376
matchEntry = table->ops->matchEntry;
377
if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
378
METER(table->stats.hits++);
382
/* Collision: double hash. */
383
sizeLog2 = JS_DHASH_BITS - table->hashShift;
384
hash2 = HASH2(keyHash, sizeLog2, hashShift);
385
sizeMask = JS_BITMASK(sizeLog2);
387
/* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
388
if (ENTRY_IS_REMOVED(entry)) {
389
firstRemoved = entry;
392
if (op == JS_DHASH_ADD)
393
entry->keyHash |= COLLISION_FLAG;
397
METER(table->stats.steps++);
401
entry = ADDRESS_ENTRY(table, hash1);
402
if (JS_DHASH_ENTRY_IS_FREE(entry)) {
403
METER(table->stats.misses++);
404
return (firstRemoved && op == JS_DHASH_ADD) ? firstRemoved : entry;
407
if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
408
matchEntry(table, entry, key)) {
409
METER(table->stats.hits++);
413
if (ENTRY_IS_REMOVED(entry)) {
415
firstRemoved = entry;
417
if (op == JS_DHASH_ADD)
418
entry->keyHash |= COLLISION_FLAG;
427
ChangeTable(JSDHashTable *table, int deltaLog2)
429
int oldLog2, newLog2;
430
uint32 oldCapacity, newCapacity;
431
char *newEntryStore, *oldEntryStore, *oldEntryAddr;
432
uint32 entrySize, i, nbytes;
433
JSDHashEntryHdr *oldEntry, *newEntry;
434
JSDHashGetKey getKey;
435
JSDHashMoveEntry moveEntry;
437
/* Look, but don't touch, until we succeed in getting new entry store. */
438
oldLog2 = JS_DHASH_BITS - table->hashShift;
439
newLog2 = oldLog2 + deltaLog2;
440
oldCapacity = JS_BIT(oldLog2);
441
newCapacity = JS_BIT(newLog2);
442
if (newCapacity >= JS_DHASH_SIZE_LIMIT)
444
entrySize = table->entrySize;
445
nbytes = newCapacity * entrySize;
447
newEntryStore = table->ops->allocTable(table, nbytes);
451
/* We can't fail from here on, so update table parameters. */
452
table->hashShift = JS_DHASH_BITS - newLog2;
453
table->removedCount = 0;
456
/* Assign the new entry store to table. */
457
memset(newEntryStore, 0, nbytes);
458
oldEntryAddr = oldEntryStore = table->entryStore;
459
table->entryStore = newEntryStore;
460
getKey = table->ops->getKey;
461
moveEntry = table->ops->moveEntry;
463
/* Copy only live entries, leaving removed ones behind. */
464
for (i = 0; i < oldCapacity; i++) {
465
oldEntry = (JSDHashEntryHdr *)oldEntryAddr;
466
if (ENTRY_IS_LIVE(oldEntry)) {
467
oldEntry->keyHash &= ~COLLISION_FLAG;
468
newEntry = SearchTable(table, getKey(table, oldEntry),
469
oldEntry->keyHash, JS_DHASH_ADD);
470
JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry));
471
moveEntry(table, oldEntry, newEntry);
472
newEntry->keyHash = oldEntry->keyHash;
474
oldEntryAddr += entrySize;
477
table->ops->freeTable(table, oldEntryStore);
481
JS_PUBLIC_API(JSDHashEntryHdr *) JS_DHASH_FASTCALL
482
JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op)
484
JSDHashNumber keyHash;
485
JSDHashEntryHdr *entry;
489
keyHash = table->ops->hashKey(table, key);
490
keyHash *= JS_DHASH_GOLDEN_RATIO;
492
/* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
493
ENSURE_LIVE_KEYHASH(keyHash);
494
keyHash &= ~COLLISION_FLAG;
497
case JS_DHASH_LOOKUP:
498
METER(table->stats.lookups++);
499
entry = SearchTable(table, key, keyHash, op);
504
* If alpha is >= .75, grow or compress the table. If key is already
505
* in the table, we may grow once more than necessary, but only if we
506
* are on the edge of being overloaded.
508
size = JS_DHASH_TABLE_SIZE(table);
509
if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
510
/* Compress if a quarter or more of all entries are removed. */
511
if (table->removedCount >= size >> 2) {
512
METER(table->stats.compresses++);
515
METER(table->stats.grows++);
520
* Grow or compress table, returning null if ChangeTable fails and
521
* falling through might claim the last free entry.
523
if (!ChangeTable(table, deltaLog2) &&
524
table->entryCount + table->removedCount == size - 1) {
525
METER(table->stats.addFailures++);
531
* Look for entry after possibly growing, so we don't have to add it,
532
* then skip it while growing the table and re-add it after.
534
entry = SearchTable(table, key, keyHash, op);
535
if (!ENTRY_IS_LIVE(entry)) {
536
/* Initialize the entry, indicating that it's no longer free. */
537
METER(table->stats.addMisses++);
538
if (ENTRY_IS_REMOVED(entry)) {
539
METER(table->stats.addOverRemoved++);
540
table->removedCount--;
541
keyHash |= COLLISION_FLAG;
543
if (table->ops->initEntry &&
544
!table->ops->initEntry(table, entry, key)) {
545
/* We haven't claimed entry yet; fail with null return. */
546
memset(entry + 1, 0, table->entrySize - sizeof *entry);
549
entry->keyHash = keyHash;
552
METER(else table->stats.addHits++);
555
case JS_DHASH_REMOVE:
556
entry = SearchTable(table, key, keyHash, op);
557
if (ENTRY_IS_LIVE(entry)) {
558
/* Clear this entry and mark it as "removed". */
559
METER(table->stats.removeHits++);
560
JS_DHashTableRawRemove(table, entry);
562
/* Shrink if alpha is <= .25 and table isn't too small already. */
563
size = JS_DHASH_TABLE_SIZE(table);
564
if (size > JS_DHASH_MIN_SIZE &&
565
table->entryCount <= MIN_LOAD(table, size)) {
566
METER(table->stats.shrinks++);
567
(void) ChangeTable(table, -1);
570
METER(else table->stats.removeMisses++);
583
JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry)
585
JSDHashNumber keyHash; /* load first in case clearEntry goofs it */
587
JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry));
588
keyHash = entry->keyHash;
589
table->ops->clearEntry(table, entry);
590
if (keyHash & COLLISION_FLAG) {
591
MARK_ENTRY_REMOVED(entry);
592
table->removedCount++;
594
METER(table->stats.removeFrees++);
595
MARK_ENTRY_FREE(entry);
600
JS_PUBLIC_API(uint32)
601
JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg)
603
char *entryAddr, *entryLimit;
604
uint32 i, capacity, entrySize;
606
JSDHashEntryHdr *entry;
609
entryAddr = table->entryStore;
610
entrySize = table->entrySize;
611
capacity = JS_DHASH_TABLE_SIZE(table);
612
entryLimit = entryAddr + capacity * entrySize;
614
didRemove = JS_FALSE;
615
while (entryAddr < entryLimit) {
616
entry = (JSDHashEntryHdr *)entryAddr;
617
if (ENTRY_IS_LIVE(entry)) {
618
op = etor(table, entry, i++, arg);
619
if (op & JS_DHASH_REMOVE) {
620
METER(table->stats.removeEnums++);
621
JS_DHashTableRawRemove(table, entry);
624
if (op & JS_DHASH_STOP)
627
entryAddr += entrySize;
631
* Shrink or compress if a quarter or more of all entries are removed, or
632
* if the table is underloaded according to the configured minimum alpha,
633
* and is not minimal-size already. Do this only if we removed above, so
634
* non-removing enumerations can count on stable table->entryStore until
635
* the next non-lookup-Operate or removing-Enumerate.
638
(table->removedCount >= capacity >> 2 ||
639
(capacity > JS_DHASH_MIN_SIZE &&
640
table->entryCount <= MIN_LOAD(table, capacity)))) {
641
METER(table->stats.enumShrinks++);
642
capacity = table->entryCount;
643
capacity += capacity >> 1;
644
if (capacity < JS_DHASH_MIN_SIZE)
645
capacity = JS_DHASH_MIN_SIZE;
646
(void) ChangeTable(table,
647
JS_CeilingLog2(capacity)
648
- (JS_DHASH_BITS - table->hashShift));
657
JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp)
660
uint32 entrySize, entryCount;
661
int hashShift, sizeLog2;
662
uint32 i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
663
JSDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
664
double sqsum, mean, variance, sigma;
665
JSDHashEntryHdr *entry, *probe;
667
entryAddr = table->entryStore;
668
entrySize = table->entrySize;
669
hashShift = table->hashShift;
670
sizeLog2 = JS_DHASH_BITS - hashShift;
671
tableSize = JS_DHASH_TABLE_SIZE(table);
672
sizeMask = JS_BITMASK(sizeLog2);
673
chainCount = maxChainLen = 0;
677
for (i = 0; i < tableSize; i++) {
678
entry = (JSDHashEntryHdr *)entryAddr;
679
entryAddr += entrySize;
680
if (!ENTRY_IS_LIVE(entry))
682
hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
684
probe = ADDRESS_ENTRY(table, hash1);
686
if (probe == entry) {
687
/* Start of a (possibly unit-length) chain. */
690
hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
696
probe = ADDRESS_ENTRY(table, hash1);
697
} while (probe != entry);
699
sqsum += chainLen * chainLen;
700
if (chainLen > maxChainLen) {
701
maxChainLen = chainLen;
702
maxChainHash1 = saveHash1;
703
maxChainHash2 = hash2;
707
entryCount = table->entryCount;
708
if (entryCount && chainCount) {
709
mean = (double)entryCount / chainCount;
710
variance = chainCount * sqsum - entryCount * entryCount;
711
if (variance < 0 || chainCount == 1)
714
variance /= chainCount * (chainCount - 1);
715
sigma = sqrt(variance);
720
fprintf(fp, "Double hashing statistics:\n");
721
fprintf(fp, " table size (in entries): %u\n", tableSize);
722
fprintf(fp, " number of entries: %u\n", table->entryCount);
723
fprintf(fp, " number of removed entries: %u\n", table->removedCount);
724
fprintf(fp, " number of searches: %u\n", table->stats.searches);
725
fprintf(fp, " number of hits: %u\n", table->stats.hits);
726
fprintf(fp, " number of misses: %u\n", table->stats.misses);
727
fprintf(fp, " mean steps per search: %g\n", table->stats.searches ?
728
(double)table->stats.steps
729
/ table->stats.searches :
731
fprintf(fp, " mean hash chain length: %g\n", mean);
732
fprintf(fp, " standard deviation: %g\n", sigma);
733
fprintf(fp, " maximum hash chain length: %u\n", maxChainLen);
734
fprintf(fp, " number of lookups: %u\n", table->stats.lookups);
735
fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
736
fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
737
fprintf(fp, " adds that found an entry: %u\n", table->stats.addHits);
738
fprintf(fp, " add failures: %u\n", table->stats.addFailures);
739
fprintf(fp, " useful removes: %u\n", table->stats.removeHits);
740
fprintf(fp, " useless removes: %u\n", table->stats.removeMisses);
741
fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
742
fprintf(fp, " removes while enumerating: %u\n", table->stats.removeEnums);
743
fprintf(fp, " number of grows: %u\n", table->stats.grows);
744
fprintf(fp, " number of shrinks: %u\n", table->stats.shrinks);
745
fprintf(fp, " number of compresses: %u\n", table->stats.compresses);
746
fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
748
if (dump && maxChainLen && hash2) {
749
fputs("Maximum hash chain:\n", fp);
750
hash1 = maxChainHash1;
751
hash2 = maxChainHash2;
752
entry = ADDRESS_ENTRY(table, hash1);
755
if (dump(table, entry, i++, fp) != JS_DHASH_NEXT)
759
entry = ADDRESS_ENTRY(table, hash1);
760
} while (JS_DHASH_ENTRY_IS_BUSY(entry));
763
#endif /* JS_DHASHMETER */
added
removed
src/dom/js/jsdhash.c
