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

Annotation of /trunk/js/jsdhash.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 332 - (hide annotations)
Thu Oct 23 19:03:33 2008 UTC (11 years, 8 months ago) by siliconforks
File size: 28971 byte(s)
Add SpiderMonkey from Firefox 3.1b1.

The following directories and files were removed:
correct/, correct.js
liveconnect/
nanojit/
t/
v8/
vprof/
xpconnect/
all JavaScript files (Y.js, call.js, if.js, math-partial-sums.js, md5.js, perfect.js, trace-test.js, trace.js)


1 siliconforks 332 /* -*- 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 */

  ViewVC Help
Powered by ViewVC 1.1.24