Back to index

lightning-sunbird  0.9+nobinonly
jsdhash.c
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is Mozilla JavaScript code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1999-2001
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Brendan Eich <brendan@mozilla.org> (Original Author)
00024  *   Chris Waterson <waterson@netscape.com>
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either of the GNU General Public License Version 2 or later (the "GPL"),
00028  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 /*
00041  * Double hashing implementation.
00042  */
00043 #include <stdio.h>
00044 #include <stdlib.h>
00045 #include <string.h>
00046 #include "jsbit.h"
00047 #include "jsdhash.h"
00048 #include "jsutil.h"     /* for JS_ASSERT */
00049 
00050 #ifdef JS_DHASHMETER
00051 # if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
00052 #  include "nsTraceMalloc.h"
00053 # endif
00054 # define METER(x)       x
00055 #else
00056 # define METER(x)       /* nothing */
00057 #endif
00058 
00059 /*
00060  * The following DEBUG-only code is used to assert that calls to one of
00061  * table->ops or to an enumerator do not cause re-entry into a call that
00062  * can mutate the table.  The recursion level is stored in additional
00063  * space allocated at the end of the entry store to avoid changing
00064  * JSDHashTable, which could cause issues when mixing DEBUG and
00065  * non-DEBUG components.
00066  */
00067 #ifdef DEBUG
00068 
00069 #define RECURSION_LEVEL(table_) (*(uint32*)(table_->entryStore + \
00070                                             JS_DHASH_TABLE_SIZE(table_) * \
00071                                             table_->entrySize))
00072 
00073 #define ENTRY_STORE_EXTRA                   sizeof(uint32)
00074 #define INCREMENT_RECURSION_LEVEL(table_)   (++RECURSION_LEVEL(table_))
00075 #define DECREMENT_RECURSION_LEVEL(table_)   (--RECURSION_LEVEL(table_))
00076 
00077 #else
00078 
00079 #define ENTRY_STORE_EXTRA 0
00080 #define INCREMENT_RECURSION_LEVEL(table_)   ((void)1)
00081 #define DECREMENT_RECURSION_LEVEL(table_)   ((void)0)
00082 
00083 #endif /* defined(DEBUG) */
00084 
00085 JS_PUBLIC_API(void *)
00086 JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes)
00087 {
00088     return malloc(nbytes);
00089 }
00090 
00091 JS_PUBLIC_API(void)
00092 JS_DHashFreeTable(JSDHashTable *table, void *ptr)
00093 {
00094     free(ptr);
00095 }
00096 
00097 JS_PUBLIC_API(JSDHashNumber)
00098 JS_DHashStringKey(JSDHashTable *table, const void *key)
00099 {
00100     JSDHashNumber h;
00101     const unsigned char *s;
00102 
00103     h = 0;
00104     for (s = key; *s != '\0'; s++)
00105         h = (h >> (JS_DHASH_BITS - 4)) ^ (h << 4) ^ *s;
00106     return h;
00107 }
00108 
00109 JS_PUBLIC_API(const void *)
00110 JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry)
00111 {
00112     JSDHashEntryStub *stub = (JSDHashEntryStub *)entry;
00113 
00114     return stub->key;
00115 }
00116 
00117 JS_PUBLIC_API(JSDHashNumber)
00118 JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
00119 {
00120     return (JSDHashNumber)(unsigned long)key >> 2;
00121 }
00122 
00123 JS_PUBLIC_API(JSBool)
00124 JS_DHashMatchEntryStub(JSDHashTable *table,
00125                        const JSDHashEntryHdr *entry,
00126                        const void *key)
00127 {
00128     const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
00129 
00130     return stub->key == key;
00131 }
00132 
00133 JS_PUBLIC_API(JSBool)
00134 JS_DHashMatchStringKey(JSDHashTable *table,
00135                        const JSDHashEntryHdr *entry,
00136                        const void *key)
00137 {
00138     const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
00139 
00140     /* XXX tolerate null keys on account of sloppy Mozilla callers. */
00141     return stub->key == key ||
00142            (stub->key && key && strcmp(stub->key, key) == 0);
00143 }
00144 
00145 JS_PUBLIC_API(void)
00146 JS_DHashMoveEntryStub(JSDHashTable *table,
00147                       const JSDHashEntryHdr *from,
00148                       JSDHashEntryHdr *to)
00149 {
00150     memcpy(to, from, table->entrySize);
00151 }
00152 
00153 JS_PUBLIC_API(void)
00154 JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry)
00155 {
00156     memset(entry, 0, table->entrySize);
00157 }
00158 
00159 JS_PUBLIC_API(void)
00160 JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry)
00161 {
00162     const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
00163 
00164     free((void *) stub->key);
00165     memset(entry, 0, table->entrySize);
00166 }
00167 
00168 JS_PUBLIC_API(void)
00169 JS_DHashFinalizeStub(JSDHashTable *table)
00170 {
00171 }
00172 
00173 static const JSDHashTableOps stub_ops = {
00174     JS_DHashAllocTable,
00175     JS_DHashFreeTable,
00176     JS_DHashGetKeyStub,
00177     JS_DHashVoidPtrKeyStub,
00178     JS_DHashMatchEntryStub,
00179     JS_DHashMoveEntryStub,
00180     JS_DHashClearEntryStub,
00181     JS_DHashFinalizeStub,
00182     NULL
00183 };
00184 
00185 JS_PUBLIC_API(const JSDHashTableOps *)
00186 JS_DHashGetStubOps(void)
00187 {
00188     return &stub_ops;
00189 }
00190 
00191 JS_PUBLIC_API(JSDHashTable *)
00192 JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
00193                  uint32 capacity)
00194 {
00195     JSDHashTable *table;
00196 
00197     table = (JSDHashTable *) malloc(sizeof *table);
00198     if (!table)
00199         return NULL;
00200     if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
00201         free(table);
00202         return NULL;
00203     }
00204     return table;
00205 }
00206 
00207 JS_PUBLIC_API(void)
00208 JS_DHashTableDestroy(JSDHashTable *table)
00209 {
00210     JS_DHashTableFinish(table);
00211     free(table);
00212 }
00213 
00214 JS_PUBLIC_API(JSBool)
00215 JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
00216                   uint32 entrySize, uint32 capacity)
00217 {
00218     int log2;
00219     uint32 nbytes;
00220 
00221 #ifdef DEBUG
00222     if (entrySize > 10 * sizeof(void *)) {
00223         fprintf(stderr,
00224                 "jsdhash: for the table at address %p, the given entrySize"
00225                 " of %lu %s favors chaining over double hashing.\n",
00226                 (void *)table,
00227                 (unsigned long) entrySize,
00228                 (entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
00229     }
00230 #endif
00231 
00232     table->ops = ops;
00233     table->data = data;
00234     if (capacity < JS_DHASH_MIN_SIZE)
00235         capacity = JS_DHASH_MIN_SIZE;
00236 
00237     JS_CEILING_LOG2(log2, capacity);
00238 
00239     capacity = JS_BIT(log2);
00240     if (capacity >= JS_DHASH_SIZE_LIMIT)
00241         return JS_FALSE;
00242     table->hashShift = JS_DHASH_BITS - log2;
00243     table->maxAlphaFrac = 0xC0;                 /* .75 */
00244     table->minAlphaFrac = 0x40;                 /* .25 */
00245     table->entrySize = entrySize;
00246     table->entryCount = table->removedCount = 0;
00247     table->generation = 0;
00248     nbytes = capacity * entrySize;
00249 
00250     table->entryStore = ops->allocTable(table, nbytes + ENTRY_STORE_EXTRA);
00251     if (!table->entryStore)
00252         return JS_FALSE;
00253     memset(table->entryStore, 0, nbytes);
00254     METER(memset(&table->stats, 0, sizeof table->stats));
00255 
00256 #ifdef DEBUG
00257     RECURSION_LEVEL(table) = 0;
00258 #endif
00259 
00260     return JS_TRUE;
00261 }
00262 
00263 /*
00264  * Compute max and min load numbers (entry counts) from table params.
00265  */
00266 #define MAX_LOAD(table, size)   (((table)->maxAlphaFrac * (size)) >> 8)
00267 #define MIN_LOAD(table, size)   (((table)->minAlphaFrac * (size)) >> 8)
00268 
00269 JS_PUBLIC_API(void)
00270 JS_DHashTableSetAlphaBounds(JSDHashTable *table,
00271                             float maxAlpha,
00272                             float minAlpha)
00273 {
00274     uint32 size;
00275 
00276     /*
00277      * Reject obviously insane bounds, rather than trying to guess what the
00278      * buggy caller intended.
00279      */
00280     JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
00281     if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
00282         return;
00283 
00284     /*
00285      * Ensure that at least one entry will always be free.  If maxAlpha at
00286      * minimum size leaves no entries free, reduce maxAlpha based on minimum
00287      * size and the precision limit of maxAlphaFrac's fixed point format.
00288      */
00289     JS_ASSERT(JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) >= 1);
00290     if (JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) < 1) {
00291         maxAlpha = (float)
00292                    (JS_DHASH_MIN_SIZE - JS_MAX(JS_DHASH_MIN_SIZE / 256, 1))
00293                    / JS_DHASH_MIN_SIZE;
00294     }
00295 
00296     /*
00297      * Ensure that minAlpha is strictly less than half maxAlpha.  Take care
00298      * not to truncate an entry's worth of alpha when storing in minAlphaFrac
00299      * (8-bit fixed point format).
00300      */
00301     JS_ASSERT(minAlpha < maxAlpha / 2);
00302     if (minAlpha >= maxAlpha / 2) {
00303         size = JS_DHASH_TABLE_SIZE(table);
00304         minAlpha = (size * maxAlpha - JS_MAX(size / 256, 1)) / (2 * size);
00305     }
00306 
00307     table->maxAlphaFrac = (uint8)(maxAlpha * 256);
00308     table->minAlphaFrac = (uint8)(minAlpha * 256);
00309 }
00310 
00311 /*
00312  * Double hashing needs the second hash code to be relatively prime to table
00313  * size, so we simply make hash2 odd.
00314  */
00315 #define HASH1(hash0, shift)         ((hash0) >> (shift))
00316 #define HASH2(hash0,log2,shift)     ((((hash0) << (log2)) >> (shift)) | 1)
00317 
00318 /*
00319  * Reserve keyHash 0 for free entries and 1 for removed-entry sentinels.  Note
00320  * that a removed-entry sentinel need be stored only if the removed entry had
00321  * a colliding entry added after it.  Therefore we can use 1 as the collision
00322  * flag in addition to the removed-entry sentinel value.  Multiplicative hash
00323  * uses the high order bits of keyHash, so this least-significant reservation
00324  * should not hurt the hash function's effectiveness much.
00325  *
00326  * If you change any of these magic numbers, also update JS_DHASH_ENTRY_IS_LIVE
00327  * in jsdhash.h.  It used to be private to jsdhash.c, but then became public to
00328  * assist iterator writers who inspect table->entryStore directly.
00329  */
00330 #define COLLISION_FLAG              ((JSDHashNumber) 1)
00331 #define MARK_ENTRY_FREE(entry)      ((entry)->keyHash = 0)
00332 #define MARK_ENTRY_REMOVED(entry)   ((entry)->keyHash = 1)
00333 #define ENTRY_IS_REMOVED(entry)     ((entry)->keyHash == 1)
00334 #define ENTRY_IS_LIVE(entry)        JS_DHASH_ENTRY_IS_LIVE(entry)
00335 #define ENSURE_LIVE_KEYHASH(hash0)  if (hash0 < 2) hash0 -= 2; else (void)0
00336 
00337 /* Match an entry's keyHash against an unstored one computed from a key. */
00338 #define MATCH_ENTRY_KEYHASH(entry,hash0) \
00339     (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
00340 
00341 /* Compute the address of the indexed entry in table. */
00342 #define ADDRESS_ENTRY(table, index) \
00343     ((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
00344 
00345 JS_PUBLIC_API(void)
00346 JS_DHashTableFinish(JSDHashTable *table)
00347 {
00348     char *entryAddr, *entryLimit;
00349     uint32 entrySize;
00350     JSDHashEntryHdr *entry;
00351 
00352 #ifdef DEBUG_XXXbrendan
00353     static FILE *dumpfp = NULL;
00354     if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
00355     if (dumpfp) {
00356 #ifdef MOZILLA_CLIENT
00357         NS_TraceStack(1, dumpfp);
00358 #endif
00359         JS_DHashTableDumpMeter(table, NULL, dumpfp);
00360         fputc('\n', dumpfp);
00361     }
00362 #endif
00363 
00364     INCREMENT_RECURSION_LEVEL(table);
00365 
00366     /* Call finalize before clearing entries, so it can enumerate them. */
00367     table->ops->finalize(table);
00368 
00369     /* Clear any remaining live entries. */
00370     entryAddr = table->entryStore;
00371     entrySize = table->entrySize;
00372     entryLimit = entryAddr + JS_DHASH_TABLE_SIZE(table) * entrySize;
00373     while (entryAddr < entryLimit) {
00374         entry = (JSDHashEntryHdr *)entryAddr;
00375         if (ENTRY_IS_LIVE(entry)) {
00376             METER(table->stats.removeEnums++);
00377             table->ops->clearEntry(table, entry);
00378         }
00379         entryAddr += entrySize;
00380     }
00381 
00382     DECREMENT_RECURSION_LEVEL(table);
00383     JS_ASSERT(RECURSION_LEVEL(table) == 0);
00384 
00385     /* Free entry storage last. */
00386     table->ops->freeTable(table, table->entryStore);
00387 }
00388 
00389 static JSDHashEntryHdr * JS_DHASH_FASTCALL
00390 SearchTable(JSDHashTable *table, const void *key, JSDHashNumber keyHash,
00391             JSDHashOperator op)
00392 {
00393     JSDHashNumber hash1, hash2;
00394     int hashShift, sizeLog2;
00395     JSDHashEntryHdr *entry, *firstRemoved;
00396     JSDHashMatchEntry matchEntry;
00397     uint32 sizeMask;
00398 
00399     METER(table->stats.searches++);
00400     JS_ASSERT(!(keyHash & COLLISION_FLAG));
00401 
00402     /* Compute the primary hash address. */
00403     hashShift = table->hashShift;
00404     hash1 = HASH1(keyHash, hashShift);
00405     entry = ADDRESS_ENTRY(table, hash1);
00406 
00407     /* Miss: return space for a new entry. */
00408     if (JS_DHASH_ENTRY_IS_FREE(entry)) {
00409         METER(table->stats.misses++);
00410         return entry;
00411     }
00412 
00413     /* Hit: return entry. */
00414     matchEntry = table->ops->matchEntry;
00415     if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
00416         METER(table->stats.hits++);
00417         return entry;
00418     }
00419 
00420     /* Collision: double hash. */
00421     sizeLog2 = JS_DHASH_BITS - table->hashShift;
00422     hash2 = HASH2(keyHash, sizeLog2, hashShift);
00423     sizeMask = JS_BITMASK(sizeLog2);
00424 
00425     /* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
00426     if (ENTRY_IS_REMOVED(entry)) {
00427         firstRemoved = entry;
00428     } else {
00429         firstRemoved = NULL;
00430         if (op == JS_DHASH_ADD)
00431             entry->keyHash |= COLLISION_FLAG;
00432     }
00433 
00434     for (;;) {
00435         METER(table->stats.steps++);
00436         hash1 -= hash2;
00437         hash1 &= sizeMask;
00438 
00439         entry = ADDRESS_ENTRY(table, hash1);
00440         if (JS_DHASH_ENTRY_IS_FREE(entry)) {
00441             METER(table->stats.misses++);
00442             return (firstRemoved && op == JS_DHASH_ADD) ? firstRemoved : entry;
00443         }
00444 
00445         if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
00446             matchEntry(table, entry, key)) {
00447             METER(table->stats.hits++);
00448             return entry;
00449         }
00450 
00451         if (ENTRY_IS_REMOVED(entry)) {
00452             if (!firstRemoved)
00453                 firstRemoved = entry;
00454         } else {
00455             if (op == JS_DHASH_ADD)
00456                 entry->keyHash |= COLLISION_FLAG;
00457         }
00458     }
00459 
00460     /* NOTREACHED */
00461     return NULL;
00462 }
00463 
00464 static JSBool
00465 ChangeTable(JSDHashTable *table, int deltaLog2)
00466 {
00467     int oldLog2, newLog2;
00468     uint32 oldCapacity, newCapacity;
00469     char *newEntryStore, *oldEntryStore, *oldEntryAddr;
00470     uint32 entrySize, i, nbytes;
00471     JSDHashEntryHdr *oldEntry, *newEntry;
00472     JSDHashGetKey getKey;
00473     JSDHashMoveEntry moveEntry;
00474 #ifdef DEBUG
00475     uint32 recursionLevel;
00476 #endif
00477 
00478     /* Look, but don't touch, until we succeed in getting new entry store. */
00479     oldLog2 = JS_DHASH_BITS - table->hashShift;
00480     newLog2 = oldLog2 + deltaLog2;
00481     oldCapacity = JS_BIT(oldLog2);
00482     newCapacity = JS_BIT(newLog2);
00483     if (newCapacity >= JS_DHASH_SIZE_LIMIT)
00484         return JS_FALSE;
00485     entrySize = table->entrySize;
00486     nbytes = newCapacity * entrySize;
00487 
00488     newEntryStore = table->ops->allocTable(table, nbytes + ENTRY_STORE_EXTRA);
00489     if (!newEntryStore)
00490         return JS_FALSE;
00491 
00492     /* We can't fail from here on, so update table parameters. */
00493 #ifdef DEBUG
00494     recursionLevel = RECURSION_LEVEL(table);
00495 #endif
00496     table->hashShift = JS_DHASH_BITS - newLog2;
00497     table->removedCount = 0;
00498     table->generation++;
00499 
00500     /* Assign the new entry store to table. */
00501     memset(newEntryStore, 0, nbytes);
00502     oldEntryAddr = oldEntryStore = table->entryStore;
00503     table->entryStore = newEntryStore;
00504     getKey = table->ops->getKey;
00505     moveEntry = table->ops->moveEntry;
00506 #ifdef DEBUG
00507     RECURSION_LEVEL(table) = recursionLevel;
00508 #endif
00509 
00510     /* Copy only live entries, leaving removed ones behind. */
00511     for (i = 0; i < oldCapacity; i++) {
00512         oldEntry = (JSDHashEntryHdr *)oldEntryAddr;
00513         if (ENTRY_IS_LIVE(oldEntry)) {
00514             oldEntry->keyHash &= ~COLLISION_FLAG;
00515             newEntry = SearchTable(table, getKey(table, oldEntry),
00516                                    oldEntry->keyHash, JS_DHASH_ADD);
00517             JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry));
00518             moveEntry(table, oldEntry, newEntry);
00519             newEntry->keyHash = oldEntry->keyHash;
00520         }
00521         oldEntryAddr += entrySize;
00522     }
00523 
00524     table->ops->freeTable(table, oldEntryStore);
00525     return JS_TRUE;
00526 }
00527 
00528 JS_PUBLIC_API(JSDHashEntryHdr *) JS_DHASH_FASTCALL
00529 JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op)
00530 {
00531     JSDHashNumber keyHash;
00532     JSDHashEntryHdr *entry;
00533     uint32 size;
00534     int deltaLog2;
00535 
00536     JS_ASSERT(op == JS_DHASH_LOOKUP || RECURSION_LEVEL(table) == 0);
00537     INCREMENT_RECURSION_LEVEL(table);
00538 
00539     keyHash = table->ops->hashKey(table, key);
00540     keyHash *= JS_DHASH_GOLDEN_RATIO;
00541 
00542     /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
00543     ENSURE_LIVE_KEYHASH(keyHash);
00544     keyHash &= ~COLLISION_FLAG;
00545 
00546     switch (op) {
00547       case JS_DHASH_LOOKUP:
00548         METER(table->stats.lookups++);
00549         entry = SearchTable(table, key, keyHash, op);
00550         break;
00551 
00552       case JS_DHASH_ADD:
00553         /*
00554          * If alpha is >= .75, grow or compress the table.  If key is already
00555          * in the table, we may grow once more than necessary, but only if we
00556          * are on the edge of being overloaded.
00557          */
00558         size = JS_DHASH_TABLE_SIZE(table);
00559         if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
00560             /* Compress if a quarter or more of all entries are removed. */
00561             if (table->removedCount >= size >> 2) {
00562                 METER(table->stats.compresses++);
00563                 deltaLog2 = 0;
00564             } else {
00565                 METER(table->stats.grows++);
00566                 deltaLog2 = 1;
00567             }
00568 
00569             /*
00570              * Grow or compress table, returning null if ChangeTable fails and
00571              * falling through might claim the last free entry.
00572              */
00573             if (!ChangeTable(table, deltaLog2) &&
00574                 table->entryCount + table->removedCount == size - 1) {
00575                 METER(table->stats.addFailures++);
00576                 entry = NULL;
00577                 break;
00578             }
00579         }
00580 
00581         /*
00582          * Look for entry after possibly growing, so we don't have to add it,
00583          * then skip it while growing the table and re-add it after.
00584          */
00585         entry = SearchTable(table, key, keyHash, op);
00586         if (!ENTRY_IS_LIVE(entry)) {
00587             /* Initialize the entry, indicating that it's no longer free. */
00588             METER(table->stats.addMisses++);
00589             if (ENTRY_IS_REMOVED(entry)) {
00590                 METER(table->stats.addOverRemoved++);
00591                 table->removedCount--;
00592                 keyHash |= COLLISION_FLAG;
00593             }
00594             if (table->ops->initEntry &&
00595                 !table->ops->initEntry(table, entry, key)) {
00596                 /* We haven't claimed entry yet; fail with null return. */
00597                 memset(entry + 1, 0, table->entrySize - sizeof *entry);
00598                 entry = NULL;
00599                 break;
00600             }
00601             entry->keyHash = keyHash;
00602             table->entryCount++;
00603         }
00604         METER(else table->stats.addHits++);
00605         break;
00606 
00607       case JS_DHASH_REMOVE:
00608         entry = SearchTable(table, key, keyHash, op);
00609         if (ENTRY_IS_LIVE(entry)) {
00610             /* Clear this entry and mark it as "removed". */
00611             METER(table->stats.removeHits++);
00612             JS_DHashTableRawRemove(table, entry);
00613 
00614             /* Shrink if alpha is <= .25 and table isn't too small already. */
00615             size = JS_DHASH_TABLE_SIZE(table);
00616             if (size > JS_DHASH_MIN_SIZE &&
00617                 table->entryCount <= MIN_LOAD(table, size)) {
00618                 METER(table->stats.shrinks++);
00619                 (void) ChangeTable(table, -1);
00620             }
00621         }
00622         METER(else table->stats.removeMisses++);
00623         entry = NULL;
00624         break;
00625 
00626       default:
00627         JS_ASSERT(0);
00628         entry = NULL;
00629     }
00630 
00631     DECREMENT_RECURSION_LEVEL(table);
00632 
00633     return entry;
00634 }
00635 
00636 JS_PUBLIC_API(void)
00637 JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry)
00638 {
00639     JSDHashNumber keyHash;      /* load first in case clearEntry goofs it */
00640 
00641     JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry));
00642     keyHash = entry->keyHash;
00643     table->ops->clearEntry(table, entry);
00644     if (keyHash & COLLISION_FLAG) {
00645         MARK_ENTRY_REMOVED(entry);
00646         table->removedCount++;
00647     } else {
00648         METER(table->stats.removeFrees++);
00649         MARK_ENTRY_FREE(entry);
00650     }
00651     table->entryCount--;
00652 }
00653 
00654 JS_PUBLIC_API(uint32)
00655 JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg)
00656 {
00657     char *entryAddr, *entryLimit;
00658     uint32 i, capacity, entrySize, ceiling;
00659     JSBool didRemove;
00660     JSDHashEntryHdr *entry;
00661     JSDHashOperator op;
00662 
00663     INCREMENT_RECURSION_LEVEL(table);
00664 
00665     entryAddr = table->entryStore;
00666     entrySize = table->entrySize;
00667     capacity = JS_DHASH_TABLE_SIZE(table);
00668     entryLimit = entryAddr + capacity * entrySize;
00669     i = 0;
00670     didRemove = JS_FALSE;
00671     while (entryAddr < entryLimit) {
00672         entry = (JSDHashEntryHdr *)entryAddr;
00673         if (ENTRY_IS_LIVE(entry)) {
00674             op = etor(table, entry, i++, arg);
00675             if (op & JS_DHASH_REMOVE) {
00676                 METER(table->stats.removeEnums++);
00677                 JS_DHashTableRawRemove(table, entry);
00678                 didRemove = JS_TRUE;
00679             }
00680             if (op & JS_DHASH_STOP)
00681                 break;
00682         }
00683         entryAddr += entrySize;
00684     }
00685 
00686     JS_ASSERT(!didRemove || RECURSION_LEVEL(table) == 1);
00687 
00688     /*
00689      * Shrink or compress if a quarter or more of all entries are removed, or
00690      * if the table is underloaded according to the configured minimum alpha,
00691      * and is not minimal-size already.  Do this only if we removed above, so
00692      * non-removing enumerations can count on stable table->entryStore until
00693      * the next non-lookup-Operate or removing-Enumerate.
00694      */
00695     if (didRemove &&
00696         (table->removedCount >= capacity >> 2 ||
00697          (capacity > JS_DHASH_MIN_SIZE &&
00698           table->entryCount <= MIN_LOAD(table, capacity)))) {
00699         METER(table->stats.enumShrinks++);
00700         capacity = table->entryCount;
00701         capacity += capacity >> 1;
00702         if (capacity < JS_DHASH_MIN_SIZE)
00703             capacity = JS_DHASH_MIN_SIZE;
00704 
00705         JS_CEILING_LOG2(ceiling, capacity);
00706         ceiling -= JS_DHASH_BITS - table->hashShift;
00707 
00708         (void) ChangeTable(table, ceiling);
00709     }
00710 
00711     DECREMENT_RECURSION_LEVEL(table);
00712 
00713     return i;
00714 }
00715 
00716 #ifdef JS_DHASHMETER
00717 #include <math.h>
00718 
00719 JS_PUBLIC_API(void)
00720 JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp)
00721 {
00722     char *entryAddr;
00723     uint32 entrySize, entryCount;
00724     int hashShift, sizeLog2;
00725     uint32 i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
00726     JSDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
00727     double sqsum, mean, variance, sigma;
00728     JSDHashEntryHdr *entry, *probe;
00729 
00730     entryAddr = table->entryStore;
00731     entrySize = table->entrySize;
00732     hashShift = table->hashShift;
00733     sizeLog2 = JS_DHASH_BITS - hashShift;
00734     tableSize = JS_DHASH_TABLE_SIZE(table);
00735     sizeMask = JS_BITMASK(sizeLog2);
00736     chainCount = maxChainLen = 0;
00737     hash2 = 0;
00738     sqsum = 0;
00739 
00740     for (i = 0; i < tableSize; i++) {
00741         entry = (JSDHashEntryHdr *)entryAddr;
00742         entryAddr += entrySize;
00743         if (!ENTRY_IS_LIVE(entry))
00744             continue;
00745         hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
00746         saveHash1 = hash1;
00747         probe = ADDRESS_ENTRY(table, hash1);
00748         chainLen = 1;
00749         if (probe == entry) {
00750             /* Start of a (possibly unit-length) chain. */
00751             chainCount++;
00752         } else {
00753             hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
00754                           hashShift);
00755             do {
00756                 chainLen++;
00757                 hash1 -= hash2;
00758                 hash1 &= sizeMask;
00759                 probe = ADDRESS_ENTRY(table, hash1);
00760             } while (probe != entry);
00761         }
00762         sqsum += chainLen * chainLen;
00763         if (chainLen > maxChainLen) {
00764             maxChainLen = chainLen;
00765             maxChainHash1 = saveHash1;
00766             maxChainHash2 = hash2;
00767         }
00768     }
00769 
00770     entryCount = table->entryCount;
00771     if (entryCount && chainCount) {
00772         mean = (double)entryCount / chainCount;
00773         variance = chainCount * sqsum - entryCount * entryCount;
00774         if (variance < 0 || chainCount == 1)
00775             variance = 0;
00776         else
00777             variance /= chainCount * (chainCount - 1);
00778         sigma = sqrt(variance);
00779     } else {
00780         mean = sigma = 0;
00781     }
00782 
00783     fprintf(fp, "Double hashing statistics:\n");
00784     fprintf(fp, "    table size (in entries): %u\n", tableSize);
00785     fprintf(fp, "          number of entries: %u\n", table->entryCount);
00786     fprintf(fp, "  number of removed entries: %u\n", table->removedCount);
00787     fprintf(fp, "         number of searches: %u\n", table->stats.searches);
00788     fprintf(fp, "             number of hits: %u\n", table->stats.hits);
00789     fprintf(fp, "           number of misses: %u\n", table->stats.misses);
00790     fprintf(fp, "      mean steps per search: %g\n", table->stats.searches ?
00791                                                      (double)table->stats.steps
00792                                                      / table->stats.searches :
00793                                                      0.);
00794     fprintf(fp, "     mean hash chain length: %g\n", mean);
00795     fprintf(fp, "         standard deviation: %g\n", sigma);
00796     fprintf(fp, "  maximum hash chain length: %u\n", maxChainLen);
00797     fprintf(fp, "          number of lookups: %u\n", table->stats.lookups);
00798     fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
00799     fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
00800     fprintf(fp, "   adds that found an entry: %u\n", table->stats.addHits);
00801     fprintf(fp, "               add failures: %u\n", table->stats.addFailures);
00802     fprintf(fp, "             useful removes: %u\n", table->stats.removeHits);
00803     fprintf(fp, "            useless removes: %u\n", table->stats.removeMisses);
00804     fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
00805     fprintf(fp, "  removes while enumerating: %u\n", table->stats.removeEnums);
00806     fprintf(fp, "            number of grows: %u\n", table->stats.grows);
00807     fprintf(fp, "          number of shrinks: %u\n", table->stats.shrinks);
00808     fprintf(fp, "       number of compresses: %u\n", table->stats.compresses);
00809     fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
00810 
00811     if (dump && maxChainLen && hash2) {
00812         fputs("Maximum hash chain:\n", fp);
00813         hash1 = maxChainHash1;
00814         hash2 = maxChainHash2;
00815         entry = ADDRESS_ENTRY(table, hash1);
00816         i = 0;
00817         do {
00818             if (dump(table, entry, i++, fp) != JS_DHASH_NEXT)
00819                 break;
00820             hash1 -= hash2;
00821             hash1 &= sizeMask;
00822             entry = ADDRESS_ENTRY(table, hash1);
00823         } while (JS_DHASH_ENTRY_IS_BUSY(entry));
00824     }
00825 }
00826 #endif /* JS_DHASHMETER */