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
4 *
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/
9 *
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
13 * License.
14 *
15 * The Original Code is Mozilla JavaScript code.
16 *
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.
21 *
22 * Contributor(s):
23 * Brendan Eich <brendan@mozilla.org> (Original Author)
24 * Chris Waterson <waterson@netscape.com>
25 *
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.
37 *
38 * ***** END LICENSE BLOCK ***** */
40 /*
41 * Double hashing implementation.
42 */
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46 #include "jsbit.h"
47 #include "jsdhash.h"
48 #include "jsutil.h" /* for JS_ASSERT */
50 #ifdef JS_DHASHMETER
51 # if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
52 # include "nsTraceMalloc.h"
53 # endif
54 # define METER(x) x
55 #else
56 # define METER(x) /* nothing */
57 #endif
59 JS_PUBLIC_API(void *)
60 JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes)
61 {
62 return malloc(nbytes);
63 }
65 JS_PUBLIC_API(void)
66 JS_DHashFreeTable(JSDHashTable *table, void *ptr)
67 {
68 free(ptr);
69 }
71 JS_PUBLIC_API(JSDHashNumber)
72 JS_DHashStringKey(JSDHashTable *table, const void *key)
73 {
74 JSDHashNumber h;
75 const unsigned char *s;
77 h = 0;
78 for (s = key; *s != '\0'; s++)
79 h = (h >> (JS_DHASH_BITS - 4)) ^ (h << 4) ^ *s;
80 return h;
81 }
83 JS_PUBLIC_API(const void *)
84 JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry)
85 {
86 JSDHashEntryStub *stub = (JSDHashEntryStub *)entry;
88 return stub->key;
89 }
91 JS_PUBLIC_API(JSDHashNumber)
92 JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
93 {
94 return (JSDHashNumber)key >> 2;
95 }
97 JS_PUBLIC_API(JSBool)
98 JS_DHashMatchEntryStub(JSDHashTable *table,
99 const JSDHashEntryHdr *entry,
100 const void *key)
101 {
102 const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
104 return stub->key == key;
105 }
107 JS_PUBLIC_API(JSBool)
108 JS_DHashMatchStringKey(JSDHashTable *table,
109 const JSDHashEntryHdr *entry,
110 const void *key)
111 {
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);
117 }
119 JS_PUBLIC_API(void)
120 JS_DHashMoveEntryStub(JSDHashTable *table,
121 const JSDHashEntryHdr *from,
122 JSDHashEntryHdr *to)
123 {
124 memcpy(to, from, table->entrySize);
125 }
127 JS_PUBLIC_API(void)
128 JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry)
129 {
130 memset(entry, 0, table->entrySize);
131 }
133 JS_PUBLIC_API(void)
134 JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry)
135 {
136 const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
138 free((void *) stub->key);
139 memset(entry, 0, table->entrySize);
140 }
142 JS_PUBLIC_API(void)
143 JS_DHashFinalizeStub(JSDHashTable *table)
144 {
145 }
147 static const JSDHashTableOps stub_ops = {
148 JS_DHashAllocTable,
149 JS_DHashFreeTable,
150 JS_DHashGetKeyStub,
151 JS_DHashVoidPtrKeyStub,
152 JS_DHashMatchEntryStub,
153 JS_DHashMoveEntryStub,
154 JS_DHashClearEntryStub,
155 JS_DHashFinalizeStub,
156 NULL
157 };
159 JS_PUBLIC_API(const JSDHashTableOps *)
160 JS_DHashGetStubOps(void)
161 {
162 return &stub_ops;
163 }
165 JS_PUBLIC_API(JSDHashTable *)
166 JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
167 uint32 capacity)
168 {
169 JSDHashTable *table;
171 table = (JSDHashTable *) malloc(sizeof *table);
172 if (!table)
173 return NULL;
174 if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
175 free(table);
176 return NULL;
177 }
178 return table;
179 }
181 JS_PUBLIC_API(void)
182 JS_DHashTableDestroy(JSDHashTable *table)
183 {
184 JS_DHashTableFinish(table);
185 free(table);
186 }
188 JS_PUBLIC_API(JSBool)
189 JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
190 uint32 entrySize, uint32 capacity)
191 {
192 int log2;
193 uint32 nbytes;
195 #ifdef DEBUG
196 if (entrySize > 10 * sizeof(void *)) {
197 fprintf(stderr,
198 "jsdhash: for the table at address %p, the given entrySize"
199 " of %lu %s favors chaining over double hashing.\n",
200 (void *)table,
201 (unsigned long) entrySize,
202 (entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
203 }
204 #endif
206 table->ops = ops;
207 table->data = data;
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)
213 return JS_FALSE;
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)
224 return JS_FALSE;
225 memset(table->entryStore, 0, nbytes);
226 METER(memset(&table->stats, 0, sizeof table->stats));
227 return JS_TRUE;
228 }
230 /*
231 * Compute max and min load numbers (entry counts) from table params.
232 */
233 #define MAX_LOAD(table, size) (((table)->maxAlphaFrac * (size)) >> 8)
234 #define MIN_LOAD(table, size) (((table)->minAlphaFrac * (size)) >> 8)
236 JS_PUBLIC_API(void)
237 JS_DHashTableSetAlphaBounds(JSDHashTable *table,
238 float maxAlpha,
239 float minAlpha)
240 {
241 uint32 size;
243 /*
244 * Reject obviously insane bounds, rather than trying to guess what the
245 * buggy caller intended.
246 */
247 JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
248 if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
249 return;
251 /*
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.
255 */
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) {
258 maxAlpha = (float)
259 (JS_DHASH_MIN_SIZE - JS_MAX(JS_DHASH_MIN_SIZE / 256, 1))
260 / JS_DHASH_MIN_SIZE;
261 }
263 /*
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).
267 */
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);
272 }
274 table->maxAlphaFrac = (uint8)(maxAlpha * 256);
275 table->minAlphaFrac = (uint8)(minAlpha * 256);
276 }
278 /*
279 * Double hashing needs the second hash code to be relatively prime to table
280 * size, so we simply make hash2 odd.
281 */
282 #define HASH1(hash0, shift) ((hash0) >> (shift))
283 #define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
285 /*
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.
292 *
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.
296 */
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))
312 JS_PUBLIC_API(void)
313 JS_DHashTableFinish(JSDHashTable *table)
314 {
315 char *entryAddr, *entryLimit;
316 uint32 entrySize;
317 JSDHashEntryHdr *entry;
319 #ifdef DEBUG_XXXbrendan
320 static FILE *dumpfp = NULL;
321 if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
322 if (dumpfp) {
323 #ifdef MOZILLA_CLIENT
324 NS_TraceStack(1, dumpfp);
325 #endif
326 JS_DHashTableDumpMeter(table, NULL, dumpfp);
327 fputc('\n', dumpfp);
328 }
329 #endif
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);
343 }
344 entryAddr += entrySize;
345 }
347 /* Free entry storage last. */
348 table->ops->freeTable(table, table->entryStore);
349 }
351 static JSDHashEntryHdr * JS_DHASH_FASTCALL
352 SearchTable(JSDHashTable *table, const void *key, JSDHashNumber keyHash,
353 JSDHashOperator op)
354 {
355 JSDHashNumber hash1, hash2;
356 int hashShift, sizeLog2;
357 JSDHashEntryHdr *entry, *firstRemoved;
358 JSDHashMatchEntry matchEntry;
359 uint32 sizeMask;
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++);
372 return entry;
373 }
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++);
379 return entry;
380 }
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;
390 } else {
391 firstRemoved = NULL;
392 if (op == JS_DHASH_ADD)
393 entry->keyHash |= COLLISION_FLAG;
394 }
396 for (;;) {
397 METER(table->stats.steps++);
398 hash1 -= hash2;
399 hash1 &= sizeMask;
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;
405 }
407 if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
408 matchEntry(table, entry, key)) {
409 METER(table->stats.hits++);
410 return entry;
411 }
413 if (ENTRY_IS_REMOVED(entry)) {
414 if (!firstRemoved)
415 firstRemoved = entry;
416 } else {
417 if (op == JS_DHASH_ADD)
418 entry->keyHash |= COLLISION_FLAG;
419 }
420 }
422 /* NOTREACHED */
423 return NULL;
424 }
426 static JSBool
427 ChangeTable(JSDHashTable *table, int deltaLog2)
428 {
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)
443 return JS_FALSE;
444 entrySize = table->entrySize;
445 nbytes = newCapacity * entrySize;
447 newEntryStore = table->ops->allocTable(table, nbytes);
448 if (!newEntryStore)
449 return JS_FALSE;
451 /* We can't fail from here on, so update table parameters. */
452 table->hashShift = JS_DHASH_BITS - newLog2;
453 table->removedCount = 0;
454 table->generation++;
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;
473 }
474 oldEntryAddr += entrySize;
475 }
477 table->ops->freeTable(table, oldEntryStore);
478 return JS_TRUE;
479 }
481 JS_PUBLIC_API(JSDHashEntryHdr *) JS_DHASH_FASTCALL
482 JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op)
483 {
484 JSDHashNumber keyHash;
485 JSDHashEntryHdr *entry;
486 uint32 size;
487 int deltaLog2;
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;
496 switch (op) {
497 case JS_DHASH_LOOKUP:
498 METER(table->stats.lookups++);
499 entry = SearchTable(table, key, keyHash, op);
500 break;
502 case JS_DHASH_ADD:
503 /*
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.
507 */
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++);
513 deltaLog2 = 0;
514 } else {
515 METER(table->stats.grows++);
516 deltaLog2 = 1;
517 }
519 /*
520 * Grow or compress table, returning null if ChangeTable fails and
521 * falling through might claim the last free entry.
522 */
523 if (!ChangeTable(table, deltaLog2) &&
524 table->entryCount + table->removedCount == size - 1) {
525 METER(table->stats.addFailures++);
526 return NULL;
527 }
528 }
530 /*
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.
533 */
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;
542 }
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);
547 return NULL;
548 }
549 entry->keyHash = keyHash;
550 table->entryCount++;
551 }
552 METER(else table->stats.addHits++);
553 break;
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);
568 }
569 }
570 METER(else table->stats.removeMisses++);
571 entry = NULL;
572 break;
574 default:
575 JS_ASSERT(0);
576 entry = NULL;
577 }
579 return entry;
580 }
582 JS_PUBLIC_API(void)
583 JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry)
584 {
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++;
593 } else {
594 METER(table->stats.removeFrees++);
595 MARK_ENTRY_FREE(entry);
596 }
597 table->entryCount--;
598 }
600 JS_PUBLIC_API(uint32)
601 JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg)
602 {
603 char *entryAddr, *entryLimit;
604 uint32 i, capacity, entrySize;
605 JSBool didRemove;
606 JSDHashEntryHdr *entry;
607 JSDHashOperator op;
609 entryAddr = table->entryStore;
610 entrySize = table->entrySize;
611 capacity = JS_DHASH_TABLE_SIZE(table);
612 entryLimit = entryAddr + capacity * entrySize;
613 i = 0;
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);
622 didRemove = JS_TRUE;
623 }
624 if (op & JS_DHASH_STOP)
625 break;
626 }
627 entryAddr += entrySize;
628 }
630 /*
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.
636 */
637 if (didRemove &&
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));
649 }
650 return i;
651 }
653 #ifdef JS_DHASHMETER
654 #include <math.h>
656 JS_PUBLIC_API(void)
657 JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp)
658 {
659 char *entryAddr;
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;
674 hash2 = 0;
675 sqsum = 0;
677 for (i = 0; i < tableSize; i++) {
678 entry = (JSDHashEntryHdr *)entryAddr;
679 entryAddr += entrySize;
680 if (!ENTRY_IS_LIVE(entry))
681 continue;
682 hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
683 saveHash1 = hash1;
684 probe = ADDRESS_ENTRY(table, hash1);
685 chainLen = 1;
686 if (probe == entry) {
687 /* Start of a (possibly unit-length) chain. */
688 chainCount++;
689 } else {
690 hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
691 hashShift);
692 do {
693 chainLen++;
694 hash1 -= hash2;
695 hash1 &= sizeMask;
696 probe = ADDRESS_ENTRY(table, hash1);
697 } while (probe != entry);
698 }
699 sqsum += chainLen * chainLen;
700 if (chainLen > maxChainLen) {
701 maxChainLen = chainLen;
702 maxChainHash1 = saveHash1;
703 maxChainHash2 = hash2;
704 }
705 }
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)
712 variance = 0;
713 else
714 variance /= chainCount * (chainCount - 1);
715 sigma = sqrt(variance);
716 } else {
717 mean = sigma = 0;
718 }
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 :
730 0.);
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);
753 i = 0;
754 do {
755 if (dump(table, entry, i++, fp) != JS_DHASH_NEXT)
756 break;
757 hash1 -= hash2;
758 hash1 &= sizeMask;
759 entry = ADDRESS_ENTRY(table, hash1);
760 } while (JS_DHASH_ENTRY_IS_BUSY(entry));
761 }
762 }
763 #endif /* JS_DHASHMETER */