/[jscoverage]/trunk/js/jsdhash.cpp
ViewVC logotype

Contents of /trunk/js/jsdhash.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 507 - (show annotations)
Sun Jan 10 07:23:34 2010 UTC (9 years, 10 months ago) by siliconforks
File size: 30229 byte(s)
Update SpiderMonkey from Firefox 3.6rc1.

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

  ViewVC Help
Powered by ViewVC 1.1.24