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

Annotation of /trunk/js/jsdhash.cpp

Parent Directory Parent Directory | Revision Log Revision Log


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

1 siliconforks 507 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 siliconforks 332 /* ***** 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 siliconforks 507 #include "jsstdint.h"
48 siliconforks 332 #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 siliconforks 507 /*
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 siliconforks 332
85 siliconforks 507 #define RECURSION_LEVEL_SAFE_TO_FINISH(table_) \
86     (RECURSION_LEVEL(table_) == 0 || \
87     RECURSION_LEVEL(table_) == IMMUTABLE_RECURSION_LEVEL)
88    
89 siliconforks 332 #define ENTRY_STORE_EXTRA sizeof(uint32)
90 siliconforks 507 #define INCREMENT_RECURSION_LEVEL(table_) \
91     JS_BEGIN_MACRO \
92     if (RECURSION_LEVEL(table_) != IMMUTABLE_RECURSION_LEVEL) \
93     ++RECURSION_LEVEL(table_); \
94 siliconforks 332 JS_END_MACRO
95 siliconforks 507 #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 siliconforks 332 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 siliconforks 507 return js_malloc(nbytes);
115 siliconforks 332 }
116    
117     JS_PUBLIC_API(void)
118     JS_DHashFreeTable(JSDHashTable *table, void *ptr)
119     {
120 siliconforks 507 js_free(ptr);
121 siliconforks 332 }
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 siliconforks 507 js_free((void *) stub->key);
184 siliconforks 332 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 siliconforks 507 table = (JSDHashTable *) js_malloc(sizeof *table);
216 siliconforks 332 if (!table)
217     return NULL;
218     if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
219 siliconforks 507 js_free(table);
220 siliconforks 332 return NULL;
221     }
222     return table;
223     }
224    
225     JS_PUBLIC_API(void)
226     JS_DHashTableDestroy(JSDHashTable *table)
227     {
228     JS_DHashTableFinish(table);
229 siliconforks 507 js_free(table);
230 siliconforks 332 }
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 siliconforks 507 JS_ASSERT(RECURSION_LEVEL_SAFE_TO_FINISH(table));
403 siliconforks 332
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 siliconforks 507 JS_ASSERT(RECURSION_LEVEL(table) != IMMUTABLE_RECURSION_LEVEL);
709    
710 siliconforks 332 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 siliconforks 507 #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 siliconforks 332 #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