Back to index

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