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>
25 * L. David Baron <dbaron@dbaron.org>, Mozilla Corporation
27 * Alternatively, the contents of this file may be used under the terms of
28 * either of the GNU General Public License Version 2 or later (the "GPL"),
29 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30 * in which case the provisions of the GPL or the LGPL are applicable instead
31 * of those above. If you wish to allow use of your version of this file only
32 * under the terms of either the GPL or the LGPL, and not to allow others to
33 * use your version of this file under the terms of the MPL, indicate your
34 * decision by deleting the provisions above and replace them with the notice
35 * and other provisions required by the GPL or the LGPL. If you do not delete
36 * the provisions above, a recipient may use your version of this file under
37 * the terms of any one of the MPL, the GPL or the LGPL.
39 * ***** END LICENSE BLOCK ***** */
42 * Double hashing implementation.
49 #include "jsutil.h" /* for JS_ASSERT */
52 # if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
53 # include "nsTraceMalloc.h"
57 # define METER(x) /* nothing */
61 * The following DEBUG-only code is used to assert that calls to one of
62 * table->ops or to an enumerator do not cause re-entry into a call that
63 * can mutate the table. The recursion level is stored in additional
64 * space allocated at the end of the entry store to avoid changing
65 * JSDHashTable, which could cause issues when mixing DEBUG and
66 * non-DEBUG components.
70 #define RECURSION_LEVEL(table_) (*(uint32*)(table_->entryStore + \
71 JS_DHASH_TABLE_SIZE(table_) * \
74 #define ENTRY_STORE_EXTRA sizeof(uint32)
75 #define INCREMENT_RECURSION_LEVEL(table_) (++RECURSION_LEVEL(table_))
76 #define DECREMENT_RECURSION_LEVEL(table_) (--RECURSION_LEVEL(table_))
80 #define ENTRY_STORE_EXTRA 0
81 #define INCREMENT_RECURSION_LEVEL(table_) ((void)1)
82 #define DECREMENT_RECURSION_LEVEL(table_) ((void)0)
84 #endif /* defined(DEBUG) */
87 JS_DHashAllocTable(JSDHashTable
*table
, uint32 nbytes
)
89 return malloc(nbytes
);
93 JS_DHashFreeTable(JSDHashTable
*table
, void *ptr
)
98 JS_PUBLIC_API(JSDHashNumber
)
99 JS_DHashStringKey(JSDHashTable
*table
, const void *key
)
102 const unsigned char *s
;
105 for (s
= (const unsigned char *) key
; *s
!= '\0'; s
++)
106 h
= (h
>> (JS_DHASH_BITS
- 4)) ^ (h
<< 4) ^ *s
;
110 JS_PUBLIC_API(JSDHashNumber
)
111 JS_DHashVoidPtrKeyStub(JSDHashTable
*table
, const void *key
)
113 return (JSDHashNumber
)(unsigned long)key
>> 2;
116 JS_PUBLIC_API(JSBool
)
117 JS_DHashMatchEntryStub(JSDHashTable
*table
,
118 const JSDHashEntryHdr
*entry
,
121 const JSDHashEntryStub
*stub
= (const JSDHashEntryStub
*)entry
;
123 return stub
->key
== key
;
126 JS_PUBLIC_API(JSBool
)
127 JS_DHashMatchStringKey(JSDHashTable
*table
,
128 const JSDHashEntryHdr
*entry
,
131 const JSDHashEntryStub
*stub
= (const JSDHashEntryStub
*)entry
;
133 /* XXX tolerate null keys on account of sloppy Mozilla callers. */
134 return stub
->key
== key
||
136 strcmp((const char *) stub
->key
, (const char *) key
) == 0);
140 JS_DHashMoveEntryStub(JSDHashTable
*table
,
141 const JSDHashEntryHdr
*from
,
144 memcpy(to
, from
, table
->entrySize
);
148 JS_DHashClearEntryStub(JSDHashTable
*table
, JSDHashEntryHdr
*entry
)
150 memset(entry
, 0, table
->entrySize
);
154 JS_DHashFreeStringKey(JSDHashTable
*table
, JSDHashEntryHdr
*entry
)
156 const JSDHashEntryStub
*stub
= (const JSDHashEntryStub
*)entry
;
158 free((void *) stub
->key
);
159 memset(entry
, 0, table
->entrySize
);
163 JS_DHashFinalizeStub(JSDHashTable
*table
)
167 static const JSDHashTableOps stub_ops
= {
170 JS_DHashVoidPtrKeyStub
,
171 JS_DHashMatchEntryStub
,
172 JS_DHashMoveEntryStub
,
173 JS_DHashClearEntryStub
,
174 JS_DHashFinalizeStub
,
178 JS_PUBLIC_API(const JSDHashTableOps
*)
179 JS_DHashGetStubOps(void)
184 JS_PUBLIC_API(JSDHashTable
*)
185 JS_NewDHashTable(const JSDHashTableOps
*ops
, void *data
, uint32 entrySize
,
190 table
= (JSDHashTable
*) malloc(sizeof *table
);
193 if (!JS_DHashTableInit(table
, ops
, data
, entrySize
, capacity
)) {
201 JS_DHashTableDestroy(JSDHashTable
*table
)
203 JS_DHashTableFinish(table
);
207 JS_PUBLIC_API(JSBool
)
208 JS_DHashTableInit(JSDHashTable
*table
, const JSDHashTableOps
*ops
, void *data
,
209 uint32 entrySize
, uint32 capacity
)
215 if (entrySize
> 10 * sizeof(void *)) {
217 "jsdhash: for the table at address %p, the given entrySize"
218 " of %lu %s favors chaining over double hashing.\n",
220 (unsigned long) entrySize
,
221 (entrySize
> 16 * sizeof(void*)) ? "definitely" : "probably");
227 if (capacity
< JS_DHASH_MIN_SIZE
)
228 capacity
= JS_DHASH_MIN_SIZE
;
230 JS_CEILING_LOG2(log2
, capacity
);
232 capacity
= JS_BIT(log2
);
233 if (capacity
>= JS_DHASH_SIZE_LIMIT
)
235 table
->hashShift
= JS_DHASH_BITS
- log2
;
236 table
->maxAlphaFrac
= (uint8
)(0x100 * JS_DHASH_DEFAULT_MAX_ALPHA
);
237 table
->minAlphaFrac
= (uint8
)(0x100 * JS_DHASH_DEFAULT_MIN_ALPHA
);
238 table
->entrySize
= entrySize
;
239 table
->entryCount
= table
->removedCount
= 0;
240 table
->generation
= 0;
241 nbytes
= capacity
* entrySize
;
243 table
->entryStore
= (char *) ops
->allocTable(table
,
244 nbytes
+ ENTRY_STORE_EXTRA
);
245 if (!table
->entryStore
)
247 memset(table
->entryStore
, 0, nbytes
);
248 METER(memset(&table
->stats
, 0, sizeof table
->stats
));
251 RECURSION_LEVEL(table
) = 0;
258 * Compute max and min load numbers (entry counts) from table params.
260 #define MAX_LOAD(table, size) (((table)->maxAlphaFrac * (size)) >> 8)
261 #define MIN_LOAD(table, size) (((table)->minAlphaFrac * (size)) >> 8)
264 JS_DHashTableSetAlphaBounds(JSDHashTable
*table
,
271 * Reject obviously insane bounds, rather than trying to guess what the
272 * buggy caller intended.
274 JS_ASSERT(0.5 <= maxAlpha
&& maxAlpha
< 1 && 0 <= minAlpha
);
275 if (maxAlpha
< 0.5 || 1 <= maxAlpha
|| minAlpha
< 0)
279 * Ensure that at least one entry will always be free. If maxAlpha at
280 * minimum size leaves no entries free, reduce maxAlpha based on minimum
281 * size and the precision limit of maxAlphaFrac's fixed point format.
283 JS_ASSERT(JS_DHASH_MIN_SIZE
- (maxAlpha
* JS_DHASH_MIN_SIZE
) >= 1);
284 if (JS_DHASH_MIN_SIZE
- (maxAlpha
* JS_DHASH_MIN_SIZE
) < 1) {
286 (JS_DHASH_MIN_SIZE
- JS_MAX(JS_DHASH_MIN_SIZE
/ 256, 1))
291 * Ensure that minAlpha is strictly less than half maxAlpha. Take care
292 * not to truncate an entry's worth of alpha when storing in minAlphaFrac
293 * (8-bit fixed point format).
295 JS_ASSERT(minAlpha
< maxAlpha
/ 2);
296 if (minAlpha
>= maxAlpha
/ 2) {
297 size
= JS_DHASH_TABLE_SIZE(table
);
298 minAlpha
= (size
* maxAlpha
- JS_MAX(size
/ 256, 1)) / (2 * size
);
301 table
->maxAlphaFrac
= (uint8
)(maxAlpha
* 256);
302 table
->minAlphaFrac
= (uint8
)(minAlpha
* 256);
306 * Double hashing needs the second hash code to be relatively prime to table
307 * size, so we simply make hash2 odd.
309 #define HASH1(hash0, shift) ((hash0) >> (shift))
310 #define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
313 * Reserve keyHash 0 for free entries and 1 for removed-entry sentinels. Note
314 * that a removed-entry sentinel need be stored only if the removed entry had
315 * a colliding entry added after it. Therefore we can use 1 as the collision
316 * flag in addition to the removed-entry sentinel value. Multiplicative hash
317 * uses the high order bits of keyHash, so this least-significant reservation
318 * should not hurt the hash function's effectiveness much.
320 * If you change any of these magic numbers, also update JS_DHASH_ENTRY_IS_LIVE
321 * in jsdhash.h. It used to be private to jsdhash.c, but then became public to
322 * assist iterator writers who inspect table->entryStore directly.
324 #define COLLISION_FLAG ((JSDHashNumber) 1)
325 #define MARK_ENTRY_FREE(entry) ((entry)->keyHash = 0)
326 #define MARK_ENTRY_REMOVED(entry) ((entry)->keyHash = 1)
327 #define ENTRY_IS_REMOVED(entry) ((entry)->keyHash == 1)
328 #define ENTRY_IS_LIVE(entry) JS_DHASH_ENTRY_IS_LIVE(entry)
329 #define ENSURE_LIVE_KEYHASH(hash0) if (hash0 < 2) hash0 -= 2; else (void)0
331 /* Match an entry's keyHash against an unstored one computed from a key. */
332 #define MATCH_ENTRY_KEYHASH(entry,hash0) \
333 (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
335 /* Compute the address of the indexed entry in table. */
336 #define ADDRESS_ENTRY(table, index) \
337 ((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
340 JS_DHashTableFinish(JSDHashTable
*table
)
342 char *entryAddr
, *entryLimit
;
344 JSDHashEntryHdr
*entry
;
346 #ifdef DEBUG_XXXbrendan
347 static FILE *dumpfp
= NULL
;
348 if (!dumpfp
) dumpfp
= fopen("/tmp/jsdhash.bigdump", "w");
350 #ifdef MOZILLA_CLIENT
351 NS_TraceStack(1, dumpfp
);
353 JS_DHashTableDumpMeter(table
, NULL
, dumpfp
);
358 INCREMENT_RECURSION_LEVEL(table
);
360 /* Call finalize before clearing entries, so it can enumerate them. */
361 table
->ops
->finalize(table
);
363 /* Clear any remaining live entries. */
364 entryAddr
= table
->entryStore
;
365 entrySize
= table
->entrySize
;
366 entryLimit
= entryAddr
+ JS_DHASH_TABLE_SIZE(table
) * entrySize
;
367 while (entryAddr
< entryLimit
) {
368 entry
= (JSDHashEntryHdr
*)entryAddr
;
369 if (ENTRY_IS_LIVE(entry
)) {
370 METER(table
->stats
.removeEnums
++);
371 table
->ops
->clearEntry(table
, entry
);
373 entryAddr
+= entrySize
;
376 DECREMENT_RECURSION_LEVEL(table
);
377 JS_ASSERT(RECURSION_LEVEL(table
) == 0);
379 /* Free entry storage last. */
380 table
->ops
->freeTable(table
, table
->entryStore
);
383 static JSDHashEntryHdr
* JS_DHASH_FASTCALL
384 SearchTable(JSDHashTable
*table
, const void *key
, JSDHashNumber keyHash
,
387 JSDHashNumber hash1
, hash2
;
388 int hashShift
, sizeLog2
;
389 JSDHashEntryHdr
*entry
, *firstRemoved
;
390 JSDHashMatchEntry matchEntry
;
393 METER(table
->stats
.searches
++);
394 JS_ASSERT(!(keyHash
& COLLISION_FLAG
));
396 /* Compute the primary hash address. */
397 hashShift
= table
->hashShift
;
398 hash1
= HASH1(keyHash
, hashShift
);
399 entry
= ADDRESS_ENTRY(table
, hash1
);
401 /* Miss: return space for a new entry. */
402 if (JS_DHASH_ENTRY_IS_FREE(entry
)) {
403 METER(table
->stats
.misses
++);
407 /* Hit: return entry. */
408 matchEntry
= table
->ops
->matchEntry
;
409 if (MATCH_ENTRY_KEYHASH(entry
, keyHash
) && matchEntry(table
, entry
, key
)) {
410 METER(table
->stats
.hits
++);
414 /* Collision: double hash. */
415 sizeLog2
= JS_DHASH_BITS
- table
->hashShift
;
416 hash2
= HASH2(keyHash
, sizeLog2
, hashShift
);
417 sizeMask
= JS_BITMASK(sizeLog2
);
419 /* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
423 if (JS_UNLIKELY(ENTRY_IS_REMOVED(entry
))) {
425 firstRemoved
= entry
;
427 if (op
== JS_DHASH_ADD
)
428 entry
->keyHash
|= COLLISION_FLAG
;
431 METER(table
->stats
.steps
++);
435 entry
= ADDRESS_ENTRY(table
, hash1
);
436 if (JS_DHASH_ENTRY_IS_FREE(entry
)) {
437 METER(table
->stats
.misses
++);
438 return (firstRemoved
&& op
== JS_DHASH_ADD
) ? firstRemoved
: entry
;
441 if (MATCH_ENTRY_KEYHASH(entry
, keyHash
) &&
442 matchEntry(table
, entry
, key
)) {
443 METER(table
->stats
.hits
++);
453 * This is a copy of SearchTable, used by ChangeTable, hardcoded to
454 * 1. assume |op == PL_DHASH_ADD|,
455 * 2. assume that |key| will never match an existing entry, and
456 * 3. assume that no entries have been removed from the current table
458 * Avoiding the need for |key| means we can avoid needing a way to map
459 * entries to keys, which means callers can use complex key types more
462 static JSDHashEntryHdr
* JS_DHASH_FASTCALL
463 FindFreeEntry(JSDHashTable
*table
, JSDHashNumber keyHash
)
465 JSDHashNumber hash1
, hash2
;
466 int hashShift
, sizeLog2
;
467 JSDHashEntryHdr
*entry
;
470 METER(table
->stats
.searches
++);
471 JS_ASSERT(!(keyHash
& COLLISION_FLAG
));
473 /* Compute the primary hash address. */
474 hashShift
= table
->hashShift
;
475 hash1
= HASH1(keyHash
, hashShift
);
476 entry
= ADDRESS_ENTRY(table
, hash1
);
478 /* Miss: return space for a new entry. */
479 if (JS_DHASH_ENTRY_IS_FREE(entry
)) {
480 METER(table
->stats
.misses
++);
484 /* Collision: double hash. */
485 sizeLog2
= JS_DHASH_BITS
- table
->hashShift
;
486 hash2
= HASH2(keyHash
, sizeLog2
, hashShift
);
487 sizeMask
= JS_BITMASK(sizeLog2
);
490 JS_ASSERT(!ENTRY_IS_REMOVED(entry
));
491 entry
->keyHash
|= COLLISION_FLAG
;
493 METER(table
->stats
.steps
++);
497 entry
= ADDRESS_ENTRY(table
, hash1
);
498 if (JS_DHASH_ENTRY_IS_FREE(entry
)) {
499 METER(table
->stats
.misses
++);
509 ChangeTable(JSDHashTable
*table
, int deltaLog2
)
511 int oldLog2
, newLog2
;
512 uint32 oldCapacity
, newCapacity
;
513 char *newEntryStore
, *oldEntryStore
, *oldEntryAddr
;
514 uint32 entrySize
, i
, nbytes
;
515 JSDHashEntryHdr
*oldEntry
, *newEntry
;
516 JSDHashMoveEntry moveEntry
;
518 uint32 recursionLevel
;
521 /* Look, but don't touch, until we succeed in getting new entry store. */
522 oldLog2
= JS_DHASH_BITS
- table
->hashShift
;
523 newLog2
= oldLog2
+ deltaLog2
;
524 oldCapacity
= JS_BIT(oldLog2
);
525 newCapacity
= JS_BIT(newLog2
);
526 if (newCapacity
>= JS_DHASH_SIZE_LIMIT
)
528 entrySize
= table
->entrySize
;
529 nbytes
= newCapacity
* entrySize
;
531 newEntryStore
= (char *) table
->ops
->allocTable(table
,
532 nbytes
+ ENTRY_STORE_EXTRA
);
536 /* We can't fail from here on, so update table parameters. */
538 recursionLevel
= RECURSION_LEVEL(table
);
540 table
->hashShift
= JS_DHASH_BITS
- newLog2
;
541 table
->removedCount
= 0;
544 /* Assign the new entry store to table. */
545 memset(newEntryStore
, 0, nbytes
);
546 oldEntryAddr
= oldEntryStore
= table
->entryStore
;
547 table
->entryStore
= newEntryStore
;
548 moveEntry
= table
->ops
->moveEntry
;
550 RECURSION_LEVEL(table
) = recursionLevel
;
553 /* Copy only live entries, leaving removed ones behind. */
554 for (i
= 0; i
< oldCapacity
; i
++) {
555 oldEntry
= (JSDHashEntryHdr
*)oldEntryAddr
;
556 if (ENTRY_IS_LIVE(oldEntry
)) {
557 oldEntry
->keyHash
&= ~COLLISION_FLAG
;
558 newEntry
= FindFreeEntry(table
, oldEntry
->keyHash
);
559 JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry
));
560 moveEntry(table
, oldEntry
, newEntry
);
561 newEntry
->keyHash
= oldEntry
->keyHash
;
563 oldEntryAddr
+= entrySize
;
566 table
->ops
->freeTable(table
, oldEntryStore
);
570 JS_PUBLIC_API(JSDHashEntryHdr
*) JS_DHASH_FASTCALL
571 JS_DHashTableOperate(JSDHashTable
*table
, const void *key
, JSDHashOperator op
)
573 JSDHashNumber keyHash
;
574 JSDHashEntryHdr
*entry
;
578 JS_ASSERT(op
== JS_DHASH_LOOKUP
|| RECURSION_LEVEL(table
) == 0);
579 INCREMENT_RECURSION_LEVEL(table
);
581 keyHash
= table
->ops
->hashKey(table
, key
);
582 keyHash
*= JS_DHASH_GOLDEN_RATIO
;
584 /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
585 ENSURE_LIVE_KEYHASH(keyHash
);
586 keyHash
&= ~COLLISION_FLAG
;
589 case JS_DHASH_LOOKUP
:
590 METER(table
->stats
.lookups
++);
591 entry
= SearchTable(table
, key
, keyHash
, op
);
596 * If alpha is >= .75, grow or compress the table. If key is already
597 * in the table, we may grow once more than necessary, but only if we
598 * are on the edge of being overloaded.
600 size
= JS_DHASH_TABLE_SIZE(table
);
601 if (table
->entryCount
+ table
->removedCount
>= MAX_LOAD(table
, size
)) {
602 /* Compress if a quarter or more of all entries are removed. */
603 if (table
->removedCount
>= size
>> 2) {
604 METER(table
->stats
.compresses
++);
607 METER(table
->stats
.grows
++);
612 * Grow or compress table, returning null if ChangeTable fails and
613 * falling through might claim the last free entry.
615 if (!ChangeTable(table
, deltaLog2
) &&
616 table
->entryCount
+ table
->removedCount
== size
- 1) {
617 METER(table
->stats
.addFailures
++);
624 * Look for entry after possibly growing, so we don't have to add it,
625 * then skip it while growing the table and re-add it after.
627 entry
= SearchTable(table
, key
, keyHash
, op
);
628 if (!ENTRY_IS_LIVE(entry
)) {
629 /* Initialize the entry, indicating that it's no longer free. */
630 METER(table
->stats
.addMisses
++);
631 if (ENTRY_IS_REMOVED(entry
)) {
632 METER(table
->stats
.addOverRemoved
++);
633 table
->removedCount
--;
634 keyHash
|= COLLISION_FLAG
;
636 if (table
->ops
->initEntry
&&
637 !table
->ops
->initEntry(table
, entry
, key
)) {
638 /* We haven't claimed entry yet; fail with null return. */
639 memset(entry
+ 1, 0, table
->entrySize
- sizeof *entry
);
643 entry
->keyHash
= keyHash
;
646 METER(else table
->stats
.addHits
++);
649 case JS_DHASH_REMOVE
:
650 entry
= SearchTable(table
, key
, keyHash
, op
);
651 if (ENTRY_IS_LIVE(entry
)) {
652 /* Clear this entry and mark it as "removed". */
653 METER(table
->stats
.removeHits
++);
654 JS_DHashTableRawRemove(table
, entry
);
656 /* Shrink if alpha is <= .25 and table isn't too small already. */
657 size
= JS_DHASH_TABLE_SIZE(table
);
658 if (size
> JS_DHASH_MIN_SIZE
&&
659 table
->entryCount
<= MIN_LOAD(table
, size
)) {
660 METER(table
->stats
.shrinks
++);
661 (void) ChangeTable(table
, -1);
664 METER(else table
->stats
.removeMisses
++);
673 DECREMENT_RECURSION_LEVEL(table
);
679 JS_DHashTableRawRemove(JSDHashTable
*table
, JSDHashEntryHdr
*entry
)
681 JSDHashNumber keyHash
; /* load first in case clearEntry goofs it */
683 JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry
));
684 keyHash
= entry
->keyHash
;
685 table
->ops
->clearEntry(table
, entry
);
686 if (keyHash
& COLLISION_FLAG
) {
687 MARK_ENTRY_REMOVED(entry
);
688 table
->removedCount
++;
690 METER(table
->stats
.removeFrees
++);
691 MARK_ENTRY_FREE(entry
);
696 JS_PUBLIC_API(uint32
)
697 JS_DHashTableEnumerate(JSDHashTable
*table
, JSDHashEnumerator etor
, void *arg
)
699 char *entryAddr
, *entryLimit
;
700 uint32 i
, capacity
, entrySize
, ceiling
;
702 JSDHashEntryHdr
*entry
;
705 INCREMENT_RECURSION_LEVEL(table
);
707 entryAddr
= table
->entryStore
;
708 entrySize
= table
->entrySize
;
709 capacity
= JS_DHASH_TABLE_SIZE(table
);
710 entryLimit
= entryAddr
+ capacity
* entrySize
;
712 didRemove
= JS_FALSE
;
713 while (entryAddr
< entryLimit
) {
714 entry
= (JSDHashEntryHdr
*)entryAddr
;
715 if (ENTRY_IS_LIVE(entry
)) {
716 op
= etor(table
, entry
, i
++, arg
);
717 if (op
& JS_DHASH_REMOVE
) {
718 METER(table
->stats
.removeEnums
++);
719 JS_DHashTableRawRemove(table
, entry
);
722 if (op
& JS_DHASH_STOP
)
725 entryAddr
+= entrySize
;
728 JS_ASSERT(!didRemove
|| RECURSION_LEVEL(table
) == 1);
731 * Shrink or compress if a quarter or more of all entries are removed, or
732 * if the table is underloaded according to the configured minimum alpha,
733 * and is not minimal-size already. Do this only if we removed above, so
734 * non-removing enumerations can count on stable table->entryStore until
735 * the next non-lookup-Operate or removing-Enumerate.
738 (table
->removedCount
>= capacity
>> 2 ||
739 (capacity
> JS_DHASH_MIN_SIZE
&&
740 table
->entryCount
<= MIN_LOAD(table
, capacity
)))) {
741 METER(table
->stats
.enumShrinks
++);
742 capacity
= table
->entryCount
;
743 capacity
+= capacity
>> 1;
744 if (capacity
< JS_DHASH_MIN_SIZE
)
745 capacity
= JS_DHASH_MIN_SIZE
;
747 JS_CEILING_LOG2(ceiling
, capacity
);
748 ceiling
-= JS_DHASH_BITS
- table
->hashShift
;
750 (void) ChangeTable(table
, ceiling
);
753 DECREMENT_RECURSION_LEVEL(table
);
762 JS_DHashTableDumpMeter(JSDHashTable
*table
, JSDHashEnumerator dump
, FILE *fp
)
765 uint32 entrySize
, entryCount
;
766 int hashShift
, sizeLog2
;
767 uint32 i
, tableSize
, sizeMask
, chainLen
, maxChainLen
, chainCount
;
768 JSDHashNumber hash1
, hash2
, saveHash1
, maxChainHash1
, maxChainHash2
;
769 double sqsum
, mean
, variance
, sigma
;
770 JSDHashEntryHdr
*entry
, *probe
;
772 entryAddr
= table
->entryStore
;
773 entrySize
= table
->entrySize
;
774 hashShift
= table
->hashShift
;
775 sizeLog2
= JS_DHASH_BITS
- hashShift
;
776 tableSize
= JS_DHASH_TABLE_SIZE(table
);
777 sizeMask
= JS_BITMASK(sizeLog2
);
778 chainCount
= maxChainLen
= 0;
782 for (i
= 0; i
< tableSize
; i
++) {
783 entry
= (JSDHashEntryHdr
*)entryAddr
;
784 entryAddr
+= entrySize
;
785 if (!ENTRY_IS_LIVE(entry
))
787 hash1
= HASH1(entry
->keyHash
& ~COLLISION_FLAG
, hashShift
);
789 probe
= ADDRESS_ENTRY(table
, hash1
);
791 if (probe
== entry
) {
792 /* Start of a (possibly unit-length) chain. */
795 hash2
= HASH2(entry
->keyHash
& ~COLLISION_FLAG
, sizeLog2
,
801 probe
= ADDRESS_ENTRY(table
, hash1
);
802 } while (probe
!= entry
);
804 sqsum
+= chainLen
* chainLen
;
805 if (chainLen
> maxChainLen
) {
806 maxChainLen
= chainLen
;
807 maxChainHash1
= saveHash1
;
808 maxChainHash2
= hash2
;
812 entryCount
= table
->entryCount
;
813 if (entryCount
&& chainCount
) {
814 mean
= (double)entryCount
/ chainCount
;
815 variance
= chainCount
* sqsum
- entryCount
* entryCount
;
816 if (variance
< 0 || chainCount
== 1)
819 variance
/= chainCount
* (chainCount
- 1);
820 sigma
= sqrt(variance
);
825 fprintf(fp
, "Double hashing statistics:\n");
826 fprintf(fp
, " table size (in entries): %u\n", tableSize
);
827 fprintf(fp
, " number of entries: %u\n", table
->entryCount
);
828 fprintf(fp
, " number of removed entries: %u\n", table
->removedCount
);
829 fprintf(fp
, " number of searches: %u\n", table
->stats
.searches
);
830 fprintf(fp
, " number of hits: %u\n", table
->stats
.hits
);
831 fprintf(fp
, " number of misses: %u\n", table
->stats
.misses
);
832 fprintf(fp
, " mean steps per search: %g\n", table
->stats
.searches
?
833 (double)table
->stats
.steps
834 / table
->stats
.searches
:
836 fprintf(fp
, " mean hash chain length: %g\n", mean
);
837 fprintf(fp
, " standard deviation: %g\n", sigma
);
838 fprintf(fp
, " maximum hash chain length: %u\n", maxChainLen
);
839 fprintf(fp
, " number of lookups: %u\n", table
->stats
.lookups
);
840 fprintf(fp
, " adds that made a new entry: %u\n", table
->stats
.addMisses
);
841 fprintf(fp
, "adds that recycled removeds: %u\n", table
->stats
.addOverRemoved
);
842 fprintf(fp
, " adds that found an entry: %u\n", table
->stats
.addHits
);
843 fprintf(fp
, " add failures: %u\n", table
->stats
.addFailures
);
844 fprintf(fp
, " useful removes: %u\n", table
->stats
.removeHits
);
845 fprintf(fp
, " useless removes: %u\n", table
->stats
.removeMisses
);
846 fprintf(fp
, "removes that freed an entry: %u\n", table
->stats
.removeFrees
);
847 fprintf(fp
, " removes while enumerating: %u\n", table
->stats
.removeEnums
);
848 fprintf(fp
, " number of grows: %u\n", table
->stats
.grows
);
849 fprintf(fp
, " number of shrinks: %u\n", table
->stats
.shrinks
);
850 fprintf(fp
, " number of compresses: %u\n", table
->stats
.compresses
);
851 fprintf(fp
, "number of enumerate shrinks: %u\n", table
->stats
.enumShrinks
);
853 if (dump
&& maxChainLen
&& hash2
) {
854 fputs("Maximum hash chain:\n", fp
);
855 hash1
= maxChainHash1
;
856 hash2
= maxChainHash2
;
857 entry
= ADDRESS_ENTRY(table
, hash1
);
860 if (dump(table
, entry
, i
++, fp
) != JS_DHASH_NEXT
)
864 entry
= ADDRESS_ENTRY(table
, hash1
);
865 } while (JS_DHASH_ENTRY_IS_BUSY(entry
));
868 #endif /* JS_DHASHMETER */