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