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 ***** */
39
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 */
49
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
58
59 JS_PUBLIC_API(void *)
60 JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes)
61 487 {
62 487 return malloc(nbytes);
63 }
64
65 JS_PUBLIC_API(void)
66 JS_DHashFreeTable(JSDHashTable *table, void *ptr)
67 487 {
68 487 free(ptr);
69 487 }
70
71 JS_PUBLIC_API(JSDHashNumber)
72 JS_DHashStringKey(JSDHashTable *table, const void *key)
73 0 {
74 JSDHashNumber h;
75 const unsigned char *s;
76
77 0 h = 0;
78 0 for (s = key; *s != '\0'; s++)
79 0 h = (h >> (JS_DHASH_BITS - 4)) ^ (h << 4) ^ *s;
80 0 return h;
81 }
82
83 JS_PUBLIC_API(const void *)
84 JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry)
85 70155 {
86 70155 JSDHashEntryStub *stub = (JSDHashEntryStub *)entry;
87
88 70155 return stub->key;
89 }
90
91 JS_PUBLIC_API(JSDHashNumber)
92 JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
93 61532 {
94 61532 return (JSDHashNumber)(unsigned long)key >> 2;
95 }
96
97 JS_PUBLIC_API(JSBool)
98 JS_DHashMatchEntryStub(JSDHashTable *table,
99 const JSDHashEntryHdr *entry,
100 const void *key)
101 30766 {
102 30766 const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
103
104 30766 return stub->key == key;
105 }
106
107 JS_PUBLIC_API(JSBool)
108 JS_DHashMatchStringKey(JSDHashTable *table,
109 const JSDHashEntryHdr *entry,
110 const void *key)
111 0 {
112 0 const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
113
114 /* XXX tolerate null keys on account of sloppy Mozilla callers. */
115 0 return stub->key == key ||
116 (stub->key && key && strcmp(stub->key, key) == 0);
117 }
118
119 JS_PUBLIC_API(void)
120 JS_DHashMoveEntryStub(JSDHashTable *table,
121 const JSDHashEntryHdr *from,
122 JSDHashEntryHdr *to)
123 70155 {
124 70155 memcpy(to, from, table->entrySize);
125 70155 }
126
127 JS_PUBLIC_API(void)
128 JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry)
129 699839 {
130 699839 memset(entry, 0, table->entrySize);
131 699839 }
132
133 JS_PUBLIC_API(void)
134 JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry)
135 0 {
136 0 const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
137
138 0 free((void *) stub->key);
139 0 memset(entry, 0, table->entrySize);
140 0 }
141
142 JS_PUBLIC_API(void)
143 JS_DHashFinalizeStub(JSDHashTable *table)
144 102 {
145 102 }
146
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 };
158
159 JS_PUBLIC_API(const JSDHashTableOps *)
160 JS_DHashGetStubOps(void)
161 34 {
162 34 return &stub_ops;
163 }
164
165 JS_PUBLIC_API(JSDHashTable *)
166 JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
167 uint32 capacity)
168 34 {
169 JSDHashTable *table;
170
171 34 table = (JSDHashTable *) malloc(sizeof *table);
172 34 if (!table)
173 0 return NULL;
174 34 if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
175 0 free(table);
176 0 return NULL;
177 }
178 34 return table;
179 }
180
181 JS_PUBLIC_API(void)
182 JS_DHashTableDestroy(JSDHashTable *table)
183 34 {
184 34 JS_DHashTableFinish(table);
185 34 free(table);
186 34 }
187
188 JS_PUBLIC_API(JSBool)
189 JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
190 uint32 entrySize, uint32 capacity)
191 102 {
192 int log2;
193 uint32 nbytes;
194
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
205
206 102 table->ops = ops;
207 102 table->data = data;
208 102 if (capacity < JS_DHASH_MIN_SIZE)
209 0 capacity = JS_DHASH_MIN_SIZE;
210
211 102 JS_CEILING_LOG2(log2, capacity);
212
213 102 capacity = JS_BIT(log2);
214 102 if (capacity >= JS_DHASH_SIZE_LIMIT)
215 0 return JS_FALSE;
216 102 table->hashShift = JS_DHASH_BITS - log2;
217 102 table->maxAlphaFrac = 0xC0; /* .75 */
218 102 table->minAlphaFrac = 0x40; /* .25 */
219 102 table->entrySize = entrySize;
220 102 table->entryCount = table->removedCount = 0;
221 102 table->generation = 0;
222 102 nbytes = capacity * entrySize;
223
224 102 table->entryStore = ops->allocTable(table, nbytes);
225 102 if (!table->entryStore)
226 0 return JS_FALSE;
227 102 memset(table->entryStore, 0, nbytes);
228 METER(memset(&table->stats, 0, sizeof table->stats));
229 102 return JS_TRUE;
230 }
231
232 /*
233 * Compute max and min load numbers (entry counts) from table params.
234 */
235 #define MAX_LOAD(table, size) (((table)->maxAlphaFrac * (size)) >> 8)
236 #define MIN_LOAD(table, size) (((table)->minAlphaFrac * (size)) >> 8)
237
238 JS_PUBLIC_API(void)
239 JS_DHashTableSetAlphaBounds(JSDHashTable *table,
240 float maxAlpha,
241 float minAlpha)
242 0 {
243 uint32 size;
244
245 /*
246 * Reject obviously insane bounds, rather than trying to guess what the
247 * buggy caller intended.
248 */
249 JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
250 0 if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
251 0 return;
252
253 /*
254 * Ensure that at least one entry will always be free. If maxAlpha at
255 * minimum size leaves no entries free, reduce maxAlpha based on minimum
256 * size and the precision limit of maxAlphaFrac's fixed point format.
257 */
258 JS_ASSERT(JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) >= 1);
259 0 if (JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) < 1) {
260 0 maxAlpha = (float)
261 (JS_DHASH_MIN_SIZE - JS_MAX(JS_DHASH_MIN_SIZE / 256, 1))
262 / JS_DHASH_MIN_SIZE;
263 }
264
265 /*
266 * Ensure that minAlpha is strictly less than half maxAlpha. Take care
267 * not to truncate an entry's worth of alpha when storing in minAlphaFrac
268 * (8-bit fixed point format).
269 */
270 JS_ASSERT(minAlpha < maxAlpha / 2);
271 0 if (minAlpha >= maxAlpha / 2) {
272 0 size = JS_DHASH_TABLE_SIZE(table);
273 0 minAlpha = (size * maxAlpha - JS_MAX(size / 256, 1)) / (2 * size);
274 }
275
276 0 table->maxAlphaFrac = (uint8)(maxAlpha * 256);
277 0 table->minAlphaFrac = (uint8)(minAlpha * 256);
278 }
279
280 /*
281 * Double hashing needs the second hash code to be relatively prime to table
282 * size, so we simply make hash2 odd.
283 */
284 #define HASH1(hash0, shift) ((hash0) >> (shift))
285 #define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
286
287 /*
288 * Reserve keyHash 0 for free entries and 1 for removed-entry sentinels. Note
289 * that a removed-entry sentinel need be stored only if the removed entry had
290 * a colliding entry added after it. Therefore we can use 1 as the collision
291 * flag in addition to the removed-entry sentinel value. Multiplicative hash
292 * uses the high order bits of keyHash, so this least-significant reservation
293 * should not hurt the hash function's effectiveness much.
294 *
295 * If you change any of these magic numbers, also update JS_DHASH_ENTRY_IS_LIVE
296 * in jsdhash.h. It used to be private to jsdhash.c, but then became public to
297 * assist iterator writers who inspect table->entryStore directly.
298 */
299 #define COLLISION_FLAG ((JSDHashNumber) 1)
300 #define MARK_ENTRY_FREE(entry) ((entry)->keyHash = 0)
301 #define MARK_ENTRY_REMOVED(entry) ((entry)->keyHash = 1)
302 #define ENTRY_IS_REMOVED(entry) ((entry)->keyHash == 1)
303 #define ENTRY_IS_LIVE(entry) JS_DHASH_ENTRY_IS_LIVE(entry)
304 #define ENSURE_LIVE_KEYHASH(hash0) if (hash0 < 2) hash0 -= 2; else (void)0
305
306 /* Match an entry's keyHash against an unstored one computed from a key. */
307 #define MATCH_ENTRY_KEYHASH(entry,hash0) \
308 (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
309
310 /* Compute the address of the indexed entry in table. */
311 #define ADDRESS_ENTRY(table, index) \
312 ((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
313
314 JS_PUBLIC_API(void)
315 JS_DHashTableFinish(JSDHashTable *table)
316 102 {
317 char *entryAddr, *entryLimit;
318 uint32 entrySize;
319 JSDHashEntryHdr *entry;
320
321 #ifdef DEBUG_XXXbrendan
322 static FILE *dumpfp = NULL;
323 if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
324 if (dumpfp) {
325 #ifdef MOZILLA_CLIENT
326 NS_TraceStack(1, dumpfp);
327 #endif
328 JS_DHashTableDumpMeter(table, NULL, dumpfp);
329 fputc('\n', dumpfp);
330 }
331 #endif
332
333 /* Call finalize before clearing entries, so it can enumerate them. */
334 102 table->ops->finalize(table);
335
336 /* Clear any remaining live entries. */
337 102 entryAddr = table->entryStore;
338 102 entrySize = table->entrySize;
339 102 entryLimit = entryAddr + JS_DHASH_TABLE_SIZE(table) * entrySize;
340 7308 while (entryAddr < entryLimit) {
341 7104 entry = (JSDHashEntryHdr *)entryAddr;
342 7104 if (ENTRY_IS_LIVE(entry)) {
343 METER(table->stats.removeEnums++);
344 0 table->ops->clearEntry(table, entry);
345 }
346 7104 entryAddr += entrySize;
347 }
348
349 /* Free entry storage last. */
350 102 table->ops->freeTable(table, table->entryStore);
351 102 }
352
353 static JSDHashEntryHdr * JS_DHASH_FASTCALL
354 SearchTable(JSDHashTable *table, const void *key, JSDHashNumber keyHash,
355 JSDHashOperator op)
356 1132334 {
357 JSDHashNumber hash1, hash2;
358 int hashShift, sizeLog2;
359 JSDHashEntryHdr *entry, *firstRemoved;
360 JSDHashMatchEntry matchEntry;
361 uint32 sizeMask;
362
363 METER(table->stats.searches++);
364 JS_ASSERT(!(keyHash & COLLISION_FLAG));
365
366 /* Compute the primary hash address. */
367 1132334 hashShift = table->hashShift;
368 1132334 hash1 = HASH1(keyHash, hashShift);
369 1132334 entry = ADDRESS_ENTRY(table, hash1);
370
371 /* Miss: return space for a new entry. */
372 1132334 if (JS_DHASH_ENTRY_IS_FREE(entry)) {
373 METER(table->stats.misses++);
374 711594 return entry;
375 }
376
377 /* Hit: return entry. */
378 420740 matchEntry = table->ops->matchEntry;
379 420740 if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
380 METER(table->stats.hits++);
381 283199 return entry;
382 }
383
384 /* Collision: double hash. */
385 137541 sizeLog2 = JS_DHASH_BITS - table->hashShift;
386 137541 hash2 = HASH2(keyHash, sizeLog2, hashShift);
387 137541 sizeMask = JS_BITMASK(sizeLog2);
388
389 /* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
390 137541 if (ENTRY_IS_REMOVED(entry)) {
391 17595 firstRemoved = entry;
392 } else {
393 119946 firstRemoved = NULL;
394 119946 if (op == JS_DHASH_ADD)
395 102564 entry->keyHash |= COLLISION_FLAG;
396 }
397
398 for (;;) {
399 METER(table->stats.steps++);
400 241728 hash1 -= hash2;
401 241728 hash1 &= sizeMask;
402
403 241728 entry = ADDRESS_ENTRY(table, hash1);
404 241728 if (JS_DHASH_ENTRY_IS_FREE(entry)) {
405 METER(table->stats.misses++);
406 58500 return (firstRemoved && op == JS_DHASH_ADD) ? firstRemoved : entry;
407 }
408
409 183228 if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
410 matchEntry(table, entry, key)) {
411 METER(table->stats.hits++);
412 79041 return entry;
413 }
414
415 104187 if (ENTRY_IS_REMOVED(entry)) {
416 19936 if (!firstRemoved)
417 3861 firstRemoved = entry;
418 } else {
419 84251 if (op == JS_DHASH_ADD)
420 74859 entry->keyHash |= COLLISION_FLAG;
421 }
422 104187 }
423
424 /* NOTREACHED */
425 return NULL;
426 }
427
428 static JSBool
429 ChangeTable(JSDHashTable *table, int deltaLog2)
430 385 {
431 int oldLog2, newLog2;
432 uint32 oldCapacity, newCapacity;
433 char *newEntryStore, *oldEntryStore, *oldEntryAddr;
434 uint32 entrySize, i, nbytes;
435 JSDHashEntryHdr *oldEntry, *newEntry;
436 JSDHashGetKey getKey;
437 JSDHashMoveEntry moveEntry;
438
439 /* Look, but don't touch, until we succeed in getting new entry store. */
440 385 oldLog2 = JS_DHASH_BITS - table->hashShift;
441 385 newLog2 = oldLog2 + deltaLog2;
442 385 oldCapacity = JS_BIT(oldLog2);
443 385 newCapacity = JS_BIT(newLog2);
444 385 if (newCapacity >= JS_DHASH_SIZE_LIMIT)
445 0 return JS_FALSE;
446 385 entrySize = table->entrySize;
447 385 nbytes = newCapacity * entrySize;
448
449 385 newEntryStore = table->ops->allocTable(table, nbytes);
450 385 if (!newEntryStore)
451 0 return JS_FALSE;
452
453 /* We can't fail from here on, so update table parameters. */
454 385 table->hashShift = JS_DHASH_BITS - newLog2;
455 385 table->removedCount = 0;
456 385 table->generation++;
457
458 /* Assign the new entry store to table. */
459 385 memset(newEntryStore, 0, nbytes);
460 385 oldEntryAddr = oldEntryStore = table->entryStore;
461 385 table->entryStore = newEntryStore;
462 385 getKey = table->ops->getKey;
463 385 moveEntry = table->ops->moveEntry;
464
465 /* Copy only live entries, leaving removed ones behind. */
466 171937 for (i = 0; i < oldCapacity; i++) {
467 171552 oldEntry = (JSDHashEntryHdr *)oldEntryAddr;
468 171552 if (ENTRY_IS_LIVE(oldEntry)) {
469 70155 oldEntry->keyHash &= ~COLLISION_FLAG;
470 70155 newEntry = SearchTable(table, getKey(table, oldEntry),
471 oldEntry->keyHash, JS_DHASH_ADD);
472 JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry));
473 70155 moveEntry(table, oldEntry, newEntry);
474 70155 newEntry->keyHash = oldEntry->keyHash;
475 }
476 171552 oldEntryAddr += entrySize;
477 }
478
479 385 table->ops->freeTable(table, oldEntryStore);
480 385 return JS_TRUE;
481 }
482
483 JS_PUBLIC_API(JSDHashEntryHdr *) JS_DHASH_FASTCALL
484 JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op)
485 1062179 {
486 JSDHashNumber keyHash;
487 JSDHashEntryHdr *entry;
488 uint32 size;
489 int deltaLog2;
490
491 1062179 keyHash = table->ops->hashKey(table, key);
492 1062179 keyHash *= JS_DHASH_GOLDEN_RATIO;
493
494 /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
495 1062179 ENSURE_LIVE_KEYHASH(keyHash);
496 1062179 keyHash &= ~COLLISION_FLAG;
497
498 1062179 switch (op) {
499 case JS_DHASH_LOOKUP:
500 METER(table->stats.lookups++);
501 59699 entry = SearchTable(table, key, keyHash, op);
502 59699 break;
503
504 case JS_DHASH_ADD:
505 /*
506 * If alpha is >= .75, grow or compress the table. If key is already
507 * in the table, we may grow once more than necessary, but only if we
508 * are on the edge of being overloaded.
509 */
510 971564 size = JS_DHASH_TABLE_SIZE(table);
511 971564 if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
512 /* Compress if a quarter or more of all entries are removed. */
513 188 if (table->removedCount >= size >> 2) {
514 METER(table->stats.compresses++);
515 12 deltaLog2 = 0;
516 } else {
517 METER(table->stats.grows++);
518 176 deltaLog2 = 1;
519 }
520
521 /*
522 * Grow or compress table, returning null if ChangeTable fails and
523 * falling through might claim the last free entry.
524 */
525 188 if (!ChangeTable(table, deltaLog2) &&
526 table->entryCount + table->removedCount == size - 1) {
527 METER(table->stats.addFailures++);
528 0 return NULL;
529 }
530 }
531
532 /*
533 * Look for entry after possibly growing, so we don't have to add it,
534 * then skip it while growing the table and re-add it after.
535 */
536 971564 entry = SearchTable(table, key, keyHash, op);
537 971564 if (!ENTRY_IS_LIVE(entry)) {
538 /* Initialize the entry, indicating that it's no longer free. */
539 METER(table->stats.addMisses++);
540 699839 if (ENTRY_IS_REMOVED(entry)) {
541 METER(table->stats.addOverRemoved++);
542 18049 table->removedCount--;
543 18049 keyHash |= COLLISION_FLAG;
544 }
545 699839 if (table->ops->initEntry &&
546 !table->ops->initEntry(table, entry, key)) {
547 /* We haven't claimed entry yet; fail with null return. */
548 0 memset(entry + 1, 0, table->entrySize - sizeof *entry);
549 0 return NULL;
550 }
551 699839 entry->keyHash = keyHash;
552 699839 table->entryCount++;
553 }
554 METER(else table->stats.addHits++);
555 971564 break;
556
557 case JS_DHASH_REMOVE:
558 30916 entry = SearchTable(table, key, keyHash, op);
559 30916 if (ENTRY_IS_LIVE(entry)) {
560 /* Clear this entry and mark it as "removed". */
561 METER(table->stats.removeHits++);
562 30916 JS_DHashTableRawRemove(table, entry);
563
564 /* Shrink if alpha is <= .25 and table isn't too small already. */
565 30916 size = JS_DHASH_TABLE_SIZE(table);
566 30916 if (size > JS_DHASH_MIN_SIZE &&
567 table->entryCount <= MIN_LOAD(table, size)) {
568 METER(table->stats.shrinks++);
569 197 (void) ChangeTable(table, -1);
570 }
571 }
572 METER(else table->stats.removeMisses++);
573 30916 entry = NULL;
574 30916 break;
575
576 default:
577 JS_ASSERT(0);
578 0 entry = NULL;
579 }
580
581 1062179 return entry;
582 }
583
584 JS_PUBLIC_API(void)
585 JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry)
586 699839 {
587 JSDHashNumber keyHash; /* load first in case clearEntry goofs it */
588
589 JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry));
590 699839 keyHash = entry->keyHash;
591 699839 table->ops->clearEntry(table, entry);
592 699839 if (keyHash & COLLISION_FLAG) {
593 33037 MARK_ENTRY_REMOVED(entry);
594 33037 table->removedCount++;
595 } else {
596 METER(table->stats.removeFrees++);
597 666802 MARK_ENTRY_FREE(entry);
598 }
599 699839 table->entryCount--;
600 699839 }
601
602 JS_PUBLIC_API(uint32)
603 JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg)
604 68 {
605 char *entryAddr, *entryLimit;
606 uint32 i, capacity, entrySize, ceiling;
607 JSBool didRemove;
608 JSDHashEntryHdr *entry;
609 JSDHashOperator op;
610
611 68 entryAddr = table->entryStore;
612 68 entrySize = table->entrySize;
613 68 capacity = JS_DHASH_TABLE_SIZE(table);
614 68 entryLimit = entryAddr + capacity * entrySize;
615 68 i = 0;
616 68 didRemove = JS_FALSE;
617 58280 while (entryAddr < entryLimit) {
618 58144 entry = (JSDHashEntryHdr *)entryAddr;
619 58144 if (ENTRY_IS_LIVE(entry)) {
620 30732 op = etor(table, entry, i++, arg);
621 30732 if (op & JS_DHASH_REMOVE) {
622 METER(table->stats.removeEnums++);
623 0 JS_DHashTableRawRemove(table, entry);
624 0 didRemove = JS_TRUE;
625 }
626 30732 if (op & JS_DHASH_STOP)
627 0 break;
628 }
629 58144 entryAddr += entrySize;
630 }
631
632 /*
633 * Shrink or compress if a quarter or more of all entries are removed, or
634 * if the table is underloaded according to the configured minimum alpha,
635 * and is not minimal-size already. Do this only if we removed above, so
636 * non-removing enumerations can count on stable table->entryStore until
637 * the next non-lookup-Operate or removing-Enumerate.
638 */
639 68 if (didRemove &&
640 (table->removedCount >= capacity >> 2 ||
641 (capacity > JS_DHASH_MIN_SIZE &&
642 table->entryCount <= MIN_LOAD(table, capacity)))) {
643 METER(table->stats.enumShrinks++);
644 0 capacity = table->entryCount;
645 0 capacity += capacity >> 1;
646 0 if (capacity < JS_DHASH_MIN_SIZE)
647 0 capacity = JS_DHASH_MIN_SIZE;
648
649 0 JS_CEILING_LOG2(ceiling, capacity);
650 0 ceiling -= JS_DHASH_BITS - table->hashShift;
651
652 0 (void) ChangeTable(table, ceiling);
653 }
654 68 return i;
655 }
656
657 #ifdef JS_DHASHMETER
658 #include <math.h>
659
660 JS_PUBLIC_API(void)
661 JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp)
662 {
663 char *entryAddr;
664 uint32 entrySize, entryCount;
665 int hashShift, sizeLog2;
666 uint32 i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
667 JSDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
668 double sqsum, mean, variance, sigma;
669 JSDHashEntryHdr *entry, *probe;
670
671 entryAddr = table->entryStore;
672 entrySize = table->entrySize;
673 hashShift = table->hashShift;
674 sizeLog2 = JS_DHASH_BITS - hashShift;
675 tableSize = JS_DHASH_TABLE_SIZE(table);
676 sizeMask = JS_BITMASK(sizeLog2);
677 chainCount = maxChainLen = 0;
678 hash2 = 0;
679 sqsum = 0;
680
681 for (i = 0; i < tableSize; i++) {
682 entry = (JSDHashEntryHdr *)entryAddr;
683 entryAddr += entrySize;
684 if (!ENTRY_IS_LIVE(entry))
685 continue;
686 hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
687 saveHash1 = hash1;
688 probe = ADDRESS_ENTRY(table, hash1);
689 chainLen = 1;
690 if (probe == entry) {
691 /* Start of a (possibly unit-length) chain. */
692 chainCount++;
693 } else {
694 hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
695 hashShift);
696 do {
697 chainLen++;
698 hash1 -= hash2;
699 hash1 &= sizeMask;
700 probe = ADDRESS_ENTRY(table, hash1);
701 } while (probe != entry);
702 }
703 sqsum += chainLen * chainLen;
704 if (chainLen > maxChainLen) {
705 maxChainLen = chainLen;
706 maxChainHash1 = saveHash1;
707 maxChainHash2 = hash2;
708 }
709 }
710
711 entryCount = table->entryCount;
712 if (entryCount && chainCount) {
713 mean = (double)entryCount / chainCount;
714 variance = chainCount * sqsum - entryCount * entryCount;
715 if (variance < 0 || chainCount == 1)
716 variance = 0;
717 else
718 variance /= chainCount * (chainCount - 1);
719 sigma = sqrt(variance);
720 } else {
721 mean = sigma = 0;
722 }
723
724 fprintf(fp, "Double hashing statistics:\n");
725 fprintf(fp, " table size (in entries): %u\n", tableSize);
726 fprintf(fp, " number of entries: %u\n", table->entryCount);
727 fprintf(fp, " number of removed entries: %u\n", table->removedCount);
728 fprintf(fp, " number of searches: %u\n", table->stats.searches);
729 fprintf(fp, " number of hits: %u\n", table->stats.hits);
730 fprintf(fp, " number of misses: %u\n", table->stats.misses);
731 fprintf(fp, " mean steps per search: %g\n", table->stats.searches ?
732 (double)table->stats.steps
733 / table->stats.searches :
734 0.);
735 fprintf(fp, " mean hash chain length: %g\n", mean);
736 fprintf(fp, " standard deviation: %g\n", sigma);
737 fprintf(fp, " maximum hash chain length: %u\n", maxChainLen);
738 fprintf(fp, " number of lookups: %u\n", table->stats.lookups);
739 fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
740 fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
741 fprintf(fp, " adds that found an entry: %u\n", table->stats.addHits);
742 fprintf(fp, " add failures: %u\n", table->stats.addFailures);
743 fprintf(fp, " useful removes: %u\n", table->stats.removeHits);
744 fprintf(fp, " useless removes: %u\n", table->stats.removeMisses);
745 fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
746 fprintf(fp, " removes while enumerating: %u\n", table->stats.removeEnums);
747 fprintf(fp, " number of grows: %u\n", table->stats.grows);
748 fprintf(fp, " number of shrinks: %u\n", table->stats.shrinks);
749 fprintf(fp, " number of compresses: %u\n", table->stats.compresses);
750 fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
751
752 if (dump && maxChainLen && hash2) {
753 fputs("Maximum hash chain:\n", fp);
754 hash1 = maxChainHash1;
755 hash2 = maxChainHash2;
756 entry = ADDRESS_ENTRY(table, hash1);
757 i = 0;
758 do {
759 if (dump(table, entry, i++, fp) != JS_DHASH_NEXT)
760 break;
761 hash1 -= hash2;
762 hash1 &= sizeMask;
763 entry = ADDRESS_ENTRY(table, hash1);
764 } while (JS_DHASH_ENTRY_IS_BUSY(entry));
765 }
766 }