src/dom/js/jsdhash.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is Mozilla JavaScript code.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Netscape Communications Corporation.
  19  * Portions created by the Initial Developer are Copyright (C) 1999-2001
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   Brendan Eich <brendan@mozilla.org> (Original Author)
  24  *   Chris Waterson <waterson@netscape.com>
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 /*
  41  * Double hashing implementation.
  42  */
  43 #include <stdio.h>
  44 #include <stdlib.h>
  45 #include <string.h>
  46 #include "jsbit.h"
  47 #include "jsdhash.h"
  48 #include "jsutil.h"     /* for JS_ASSERT */
  49
  50 #ifdef JS_DHASHMETER
  51 # if defined MOZILLA_CLIENT && defined DEBUG_XXXbrendan
  52 #  include "nsTraceMalloc.h"
  53 # endif
  54 # define METER(x)       x
  55 #else
  56 # define METER(x)       /* nothing */
  57 #endif
  58
  59 JS_PUBLIC_API(void *)
  60 JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes)
  61 {
  62     return malloc(nbytes);
  63 }
  64
  65 JS_PUBLIC_API(void)
  66 JS_DHashFreeTable(JSDHashTable *table, void *ptr)
  67 {
  68     free(ptr);
  69 }
  70
  71 JS_PUBLIC_API(JSDHashNumber)
  72 JS_DHashStringKey(JSDHashTable *table, const void *key)
  73 {
  74     JSDHashNumber h;
  75     const unsigned char *s;
  76
  77     h = 0;
  78     for (s = key; *s != '\0'; s++)
  79         h = (h >> (JS_DHASH_BITS - 4)) ^ (h << 4) ^ *s;
  80     return h;
  81 }
  82
  83 JS_PUBLIC_API(const void *)
  84 JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry)
  85 {
  86     JSDHashEntryStub *stub = (JSDHashEntryStub *)entry;
  87
  88     return stub->key;
  89 }
  90
  91 JS_PUBLIC_API(JSDHashNumber)
  92 JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key)
  93 {
  94     return (JSDHashNumber)key >> 2;
  95 }
  96
  97 JS_PUBLIC_API(JSBool)
  98 JS_DHashMatchEntryStub(JSDHashTable *table,
  99                        const JSDHashEntryHdr *entry,
 100                        const void *key)
 101 {
 102     const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
 103
 104     return stub->key == key;
 105 }
 106
 107 JS_PUBLIC_API(JSBool)
 108 JS_DHashMatchStringKey(JSDHashTable *table,
 109                        const JSDHashEntryHdr *entry,
 110                        const void *key)
 111 {
 112     const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
 113
 114     /* XXX tolerate null keys on account of sloppy Mozilla callers. */
 115     return stub->key == key ||
 116            (stub->key && key && strcmp(stub->key, key) == 0);
 117 }
 118
 119 JS_PUBLIC_API(void)
 120 JS_DHashMoveEntryStub(JSDHashTable *table,
 121                       const JSDHashEntryHdr *from,
 122                       JSDHashEntryHdr *to)
 123 {
 124     memcpy(to, from, table->entrySize);
 125 }
 126
 127 JS_PUBLIC_API(void)
 128 JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry)
 129 {
 130     memset(entry, 0, table->entrySize);
 131 }
 132
 133 JS_PUBLIC_API(void)
 134 JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry)
 135 {
 136     const JSDHashEntryStub *stub = (const JSDHashEntryStub *)entry;
 137
 138     free((void *) stub->key);
 139     memset(entry, 0, table->entrySize);
 140 }
 141
 142 JS_PUBLIC_API(void)
 143 JS_DHashFinalizeStub(JSDHashTable *table)
 144 {
 145 }
 146
 147 static const JSDHashTableOps stub_ops = {
 148     JS_DHashAllocTable,
 149     JS_DHashFreeTable,
 150     JS_DHashGetKeyStub,
 151     JS_DHashVoidPtrKeyStub,
 152     JS_DHashMatchEntryStub,
 153     JS_DHashMoveEntryStub,
 154     JS_DHashClearEntryStub,
 155     JS_DHashFinalizeStub,
 156     NULL
 157 };
 158
 159 JS_PUBLIC_API(const JSDHashTableOps *)
 160 JS_DHashGetStubOps(void)
 161 {
 162     return &stub_ops;
 163 }
 164
 165 JS_PUBLIC_API(JSDHashTable *)
 166 JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
 167                  uint32 capacity)
 168 {
 169     JSDHashTable *table;
 170
 171     table = (JSDHashTable *) malloc(sizeof *table);
 172     if (!table)
 173         return NULL;
 174     if (!JS_DHashTableInit(table, ops, data, entrySize, capacity)) {
 175         free(table);
 176         return NULL;
 177     }
 178     return table;
 179 }
 180
 181 JS_PUBLIC_API(void)
 182 JS_DHashTableDestroy(JSDHashTable *table)
 183 {
 184     JS_DHashTableFinish(table);
 185     free(table);
 186 }
 187
 188 JS_PUBLIC_API(JSBool)
 189 JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
 190                   uint32 entrySize, uint32 capacity)
 191 {
 192     int log2;
 193     uint32 nbytes;
 194
 195 #ifdef DEBUG
 196     if (entrySize > 10 * sizeof(void *)) {
 197         fprintf(stderr,
 198                 "jsdhash: for the table at address %p, the given entrySize"
 199                 " of %lu %s favors chaining over double hashing.\n",
 200                 (void *)table,
 201                 (unsigned long) entrySize,
 202                 (entrySize > 16 * sizeof(void*)) ? "definitely" : "probably");
 203     }
 204 #endif
 205
 206     table->ops = ops;
 207     table->data = data;
 208     if (capacity < JS_DHASH_MIN_SIZE)
 209         capacity = JS_DHASH_MIN_SIZE;
 210     log2 = JS_CeilingLog2(capacity);
 211     capacity = JS_BIT(log2);
 212     if (capacity >= JS_DHASH_SIZE_LIMIT)
 213         return JS_FALSE;
 214     table->hashShift = JS_DHASH_BITS - log2;
 215     table->maxAlphaFrac = 0xC0;                 /* .75 */
 216     table->minAlphaFrac = 0x40;                 /* .25 */
 217     table->entrySize = entrySize;
 218     table->entryCount = table->removedCount = 0;
 219     table->generation = 0;
 220     nbytes = capacity * entrySize;
 221
 222     table->entryStore = ops->allocTable(table, nbytes);
 223     if (!table->entryStore)
 224         return JS_FALSE;
 225     memset(table->entryStore, 0, nbytes);
 226     METER(memset(&table->stats, 0, sizeof table->stats));
 227     return JS_TRUE;
 228 }
 229
 230 /*
 231  * Compute max and min load numbers (entry counts) from table params.
 232  */
 233 #define MAX_LOAD(table, size)   (((table)->maxAlphaFrac * (size)) >> 8)
 234 #define MIN_LOAD(table, size)   (((table)->minAlphaFrac * (size)) >> 8)
 235
 236 JS_PUBLIC_API(void)
 237 JS_DHashTableSetAlphaBounds(JSDHashTable *table,
 238                             float maxAlpha,
 239                             float minAlpha)
 240 {
 241     uint32 size;
 242
 243     /*
 244      * Reject obviously insane bounds, rather than trying to guess what the
 245      * buggy caller intended.
 246      */
 247     JS_ASSERT(0.5 <= maxAlpha && maxAlpha < 1 && 0 <= minAlpha);
 248     if (maxAlpha < 0.5 || 1 <= maxAlpha || minAlpha < 0)
 249         return;
 250
 251     /*
 252      * Ensure that at least one entry will always be free.  If maxAlpha at
 253      * minimum size leaves no entries free, reduce maxAlpha based on minimum
 254      * size and the precision limit of maxAlphaFrac's fixed point format.
 255      */
 256     JS_ASSERT(JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) >= 1);
 257     if (JS_DHASH_MIN_SIZE - (maxAlpha * JS_DHASH_MIN_SIZE) < 1) {
 258         maxAlpha = (float)
 259                    (JS_DHASH_MIN_SIZE - JS_MAX(JS_DHASH_MIN_SIZE / 256, 1))
 260                    / JS_DHASH_MIN_SIZE;
 261     }
 262
 263     /*
 264      * Ensure that minAlpha is strictly less than half maxAlpha.  Take care
 265      * not to truncate an entry's worth of alpha when storing in minAlphaFrac
 266      * (8-bit fixed point format).
 267      */
 268     JS_ASSERT(minAlpha < maxAlpha / 2);
 269     if (minAlpha >= maxAlpha / 2) {
 270         size = JS_DHASH_TABLE_SIZE(table);
 271         minAlpha = (size * maxAlpha - JS_MAX(size / 256, 1)) / (2 * size);
 272     }
 273
 274     table->maxAlphaFrac = (uint8)(maxAlpha * 256);
 275     table->minAlphaFrac = (uint8)(minAlpha * 256);
 276 }
 277
 278 /*
 279  * Double hashing needs the second hash code to be relatively prime to table
 280  * size, so we simply make hash2 odd.
 281  */
 282 #define HASH1(hash0, shift)         ((hash0) >> (shift))
 283 #define HASH2(hash0,log2,shift)     ((((hash0) << (log2)) >> (shift)) | 1)
 284
 285 /*
 286  * Reserve keyHash 0 for free entries and 1 for removed-entry sentinels.  Note
 287  * that a removed-entry sentinel need be stored only if the removed entry had
 288  * a colliding entry added after it.  Therefore we can use 1 as the collision
 289  * flag in addition to the removed-entry sentinel value.  Multiplicative hash
 290  * uses the high order bits of keyHash, so this least-significant reservation
 291  * should not hurt the hash function's effectiveness much.
 292  *
 293  * If you change any of these magic numbers, also update JS_DHASH_ENTRY_IS_LIVE
 294  * in jsdhash.h.  It used to be private to jsdhash.c, but then became public to
 295  * assist iterator writers who inspect table->entryStore directly.
 296  */
 297 #define COLLISION_FLAG              ((JSDHashNumber) 1)
 298 #define MARK_ENTRY_FREE(entry)      ((entry)->keyHash = 0)
 299 #define MARK_ENTRY_REMOVED(entry)   ((entry)->keyHash = 1)
 300 #define ENTRY_IS_REMOVED(entry)     ((entry)->keyHash == 1)
 301 #define ENTRY_IS_LIVE(entry)        JS_DHASH_ENTRY_IS_LIVE(entry)
 302 #define ENSURE_LIVE_KEYHASH(hash0)  if (hash0 < 2) hash0 -= 2; else (void)0
 303
 304 /* Match an entry's keyHash against an unstored one computed from a key. */
 305 #define MATCH_ENTRY_KEYHASH(entry,hash0) \
 306     (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
 307
 308 /* Compute the address of the indexed entry in table. */
 309 #define ADDRESS_ENTRY(table, index) \
 310     ((JSDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
 311
 312 JS_PUBLIC_API(void)
 313 JS_DHashTableFinish(JSDHashTable *table)
 314 {
 315     char *entryAddr, *entryLimit;
 316     uint32 entrySize;
 317     JSDHashEntryHdr *entry;
 318
 319 #ifdef DEBUG_XXXbrendan
 320     static FILE *dumpfp = NULL;
 321     if (!dumpfp) dumpfp = fopen("/tmp/jsdhash.bigdump", "w");
 322     if (dumpfp) {
 323 #ifdef MOZILLA_CLIENT
 324         NS_TraceStack(1, dumpfp);
 325 #endif
 326         JS_DHashTableDumpMeter(table, NULL, dumpfp);
 327         fputc('\n', dumpfp);
 328     }
 329 #endif
 330
 331     /* Call finalize before clearing entries, so it can enumerate them. */
 332     table->ops->finalize(table);
 333
 334     /* Clear any remaining live entries. */
 335     entryAddr = table->entryStore;
 336     entrySize = table->entrySize;
 337     entryLimit = entryAddr + JS_DHASH_TABLE_SIZE(table) * entrySize;
 338     while (entryAddr < entryLimit) {
 339         entry = (JSDHashEntryHdr *)entryAddr;
 340         if (ENTRY_IS_LIVE(entry)) {
 341             METER(table->stats.removeEnums++);
 342             table->ops->clearEntry(table, entry);
 343         }
 344         entryAddr += entrySize;
 345     }
 346
 347     /* Free entry storage last. */
 348     table->ops->freeTable(table, table->entryStore);
 349 }
 350
 351 static JSDHashEntryHdr *
 352 SearchTable(JSDHashTable *table, const void *key, JSDHashNumber keyHash,
 353             JSDHashOperator op)
 354 {
 355     JSDHashNumber hash1, hash2;
 356     int hashShift, sizeLog2;
 357     JSDHashEntryHdr *entry, *firstRemoved;
 358     JSDHashMatchEntry matchEntry;
 359     uint32 sizeMask;
 360
 361     METER(table->stats.searches++);
 362     JS_ASSERT(!(keyHash & COLLISION_FLAG));
 363
 364     /* Compute the primary hash address. */
 365     hashShift = table->hashShift;
 366     hash1 = HASH1(keyHash, hashShift);
 367     entry = ADDRESS_ENTRY(table, hash1);
 368
 369     /* Miss: return space for a new entry. */
 370     if (JS_DHASH_ENTRY_IS_FREE(entry)) {
 371         METER(table->stats.misses++);
 372         return entry;
 373     }
 374
 375     /* Hit: return entry. */
 376     matchEntry = table->ops->matchEntry;
 377     if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
 378         METER(table->stats.hits++);
 379         return entry;
 380     }
 381
 382     /* Collision: double hash. */
 383     sizeLog2 = JS_DHASH_BITS - table->hashShift;
 384     hash2 = HASH2(keyHash, sizeLog2, hashShift);
 385     sizeMask = JS_BITMASK(sizeLog2);
 386
 387     /* Save the first removed entry pointer so JS_DHASH_ADD can recycle it. */
 388     if (ENTRY_IS_REMOVED(entry)) {
 389         firstRemoved = entry;
 390     } else {
 391         firstRemoved = NULL;
 392         if (op == JS_DHASH_ADD)
 393             entry->keyHash |= COLLISION_FLAG;
 394     }
 395
 396     for (;;) {
 397         METER(table->stats.steps++);
 398         hash1 -= hash2;
 399         hash1 &= sizeMask;
 400
 401         entry = ADDRESS_ENTRY(table, hash1);
 402         if (JS_DHASH_ENTRY_IS_FREE(entry)) {
 403             METER(table->stats.misses++);
 404             return (firstRemoved && op == JS_DHASH_ADD) ? firstRemoved : entry;
 405         }
 406
 407         if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
 408             matchEntry(table, entry, key)) {
 409             METER(table->stats.hits++);
 410             return entry;
 411         }
 412
 413         if (ENTRY_IS_REMOVED(entry)) {
 414             if (!firstRemoved)
 415                 firstRemoved = entry;
 416         } else {
 417             if (op == JS_DHASH_ADD)
 418                 entry->keyHash |= COLLISION_FLAG;
 419         }
 420     }
 421
 422     /* NOTREACHED */
 423     return NULL;
 424 }
 425
 426 static JSBool
 427 ChangeTable(JSDHashTable *table, int deltaLog2)
 428 {
 429     int oldLog2, newLog2;
 430     uint32 oldCapacity, newCapacity;
 431     char *newEntryStore, *oldEntryStore, *oldEntryAddr;
 432     uint32 entrySize, i, nbytes;
 433     JSDHashEntryHdr *oldEntry, *newEntry;
 434     JSDHashGetKey getKey;
 435     JSDHashMoveEntry moveEntry;
 436
 437     /* Look, but don't touch, until we succeed in getting new entry store. */
 438     oldLog2 = JS_DHASH_BITS - table->hashShift;
 439     newLog2 = oldLog2 + deltaLog2;
 440     oldCapacity = JS_BIT(oldLog2);
 441     newCapacity = JS_BIT(newLog2);
 442     if (newCapacity >= JS_DHASH_SIZE_LIMIT)
 443         return JS_FALSE;
 444     entrySize = table->entrySize;
 445     nbytes = newCapacity * entrySize;
 446
 447     newEntryStore = table->ops->allocTable(table, nbytes);
 448     if (!newEntryStore)
 449         return JS_FALSE;
 450
 451     /* We can't fail from here on, so update table parameters. */
 452     table->hashShift = JS_DHASH_BITS - newLog2;
 453     table->removedCount = 0;
 454     table->generation++;
 455
 456     /* Assign the new entry store to table. */
 457     memset(newEntryStore, 0, nbytes);
 458     oldEntryAddr = oldEntryStore = table->entryStore;
 459     table->entryStore = newEntryStore;
 460     getKey = table->ops->getKey;
 461     moveEntry = table->ops->moveEntry;
 462
 463     /* Copy only live entries, leaving removed ones behind. */
 464     for (i = 0; i < oldCapacity; i++) {
 465         oldEntry = (JSDHashEntryHdr *)oldEntryAddr;
 466         if (ENTRY_IS_LIVE(oldEntry)) {
 467             oldEntry->keyHash &= ~COLLISION_FLAG;
 468             newEntry = SearchTable(table, getKey(table, oldEntry),
 469                                    oldEntry->keyHash, JS_DHASH_ADD);
 470             JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(newEntry));
 471             moveEntry(table, oldEntry, newEntry);
 472             newEntry->keyHash = oldEntry->keyHash;
 473         }
 474         oldEntryAddr += entrySize;
 475     }
 476
 477     table->ops->freeTable(table, oldEntryStore);
 478     return JS_TRUE;
 479 }
 480
 481 JS_PUBLIC_API(JSDHashEntryHdr *)
 482 JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op)
 483 {
 484     JSDHashNumber keyHash;
 485     JSDHashEntryHdr *entry;
 486     uint32 size;
 487     int deltaLog2;
 488
 489     keyHash = table->ops->hashKey(table, key);
 490     keyHash *= JS_DHASH_GOLDEN_RATIO;
 491
 492     /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
 493     ENSURE_LIVE_KEYHASH(keyHash);
 494     keyHash &= ~COLLISION_FLAG;
 495
 496     switch (op) {
 497       case JS_DHASH_LOOKUP:
 498         METER(table->stats.lookups++);
 499         entry = SearchTable(table, key, keyHash, op);
 500         break;
 501
 502       case JS_DHASH_ADD:
 503         /*
 504          * If alpha is >= .75, grow or compress the table.  If key is already
 505          * in the table, we may grow once more than necessary, but only if we
 506          * are on the edge of being overloaded.
 507          */
 508         size = JS_DHASH_TABLE_SIZE(table);
 509         if (table->entryCount + table->removedCount >= MAX_LOAD(table, size)) {
 510             /* Compress if a quarter or more of all entries are removed. */
 511             if (table->removedCount >= size >> 2) {
 512                 METER(table->stats.compresses++);
 513                 deltaLog2 = 0;
 514             } else {
 515                 METER(table->stats.grows++);
 516                 deltaLog2 = 1;
 517             }
 518
 519             /*
 520              * Grow or compress table, returning null if ChangeTable fails and
 521              * falling through might claim the last free entry.
 522              */
 523             if (!ChangeTable(table, deltaLog2) &&
 524                 table->entryCount + table->removedCount == size - 1) {
 525                 METER(table->stats.addFailures++);
 526                 return NULL;
 527             }
 528         }
 529
 530         /*
 531          * Look for entry after possibly growing, so we don't have to add it,
 532          * then skip it while growing the table and re-add it after.
 533          */
 534         entry = SearchTable(table, key, keyHash, op);
 535         if (!ENTRY_IS_LIVE(entry)) {
 536             /* Initialize the entry, indicating that it's no longer free. */
 537             METER(table->stats.addMisses++);
 538             if (ENTRY_IS_REMOVED(entry)) {
 539                 METER(table->stats.addOverRemoved++);
 540                 table->removedCount--;
 541                 keyHash |= COLLISION_FLAG;
 542             }
 543             if (table->ops->initEntry &&
 544                 !table->ops->initEntry(table, entry, key)) {
 545                 /* We haven't claimed entry yet; fail with null return. */
 546                 memset(entry + 1, 0, table->entrySize - sizeof *entry);
 547                 return NULL;
 548             }
 549             entry->keyHash = keyHash;
 550             table->entryCount++;
 551         }
 552         METER(else table->stats.addHits++);
 553         break;
 554
 555       case JS_DHASH_REMOVE:
 556         entry = SearchTable(table, key, keyHash, op);
 557         if (ENTRY_IS_LIVE(entry)) {
 558             /* Clear this entry and mark it as "removed". */
 559             METER(table->stats.removeHits++);
 560             JS_DHashTableRawRemove(table, entry);
 561
 562             /* Shrink if alpha is <= .25 and table isn't too small already. */
 563             size = JS_DHASH_TABLE_SIZE(table);
 564             if (size > JS_DHASH_MIN_SIZE &&
 565                 table->entryCount <= MIN_LOAD(table, size)) {
 566                 METER(table->stats.shrinks++);
 567                 (void) ChangeTable(table, -1);
 568             }
 569         }
 570         METER(else table->stats.removeMisses++);
 571         entry = NULL;
 572         break;
 573
 574       default:
 575         JS_ASSERT(0);
 576         entry = NULL;
 577     }
 578
 579     return entry;
 580 }
 581
 582 JS_PUBLIC_API(void)
 583 JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry)
 584 {
 585     JSDHashNumber keyHash;      /* load first in case clearEntry goofs it */
 586
 587     JS_ASSERT(JS_DHASH_ENTRY_IS_LIVE(entry));
 588     keyHash = entry->keyHash;
 589     table->ops->clearEntry(table, entry);
 590     if (keyHash & COLLISION_FLAG) {
 591         MARK_ENTRY_REMOVED(entry);
 592         table->removedCount++;
 593     } else {
 594         METER(table->stats.removeFrees++);
 595         MARK_ENTRY_FREE(entry);
 596     }
 597     table->entryCount--;
 598 }
 599
 600 JS_PUBLIC_API(uint32)
 601 JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg)
 602 {
 603     char *entryAddr, *entryLimit;
 604     uint32 i, capacity, entrySize;
 605     JSBool didRemove;
 606     JSDHashEntryHdr *entry;
 607     JSDHashOperator op;
 608
 609     entryAddr = table->entryStore;
 610     entrySize = table->entrySize;
 611     capacity = JS_DHASH_TABLE_SIZE(table);
 612     entryLimit = entryAddr + capacity * entrySize;
 613     i = 0;
 614     didRemove = JS_FALSE;
 615     while (entryAddr < entryLimit) {
 616         entry = (JSDHashEntryHdr *)entryAddr;
 617         if (ENTRY_IS_LIVE(entry)) {
 618             op = etor(table, entry, i++, arg);
 619             if (op & JS_DHASH_REMOVE) {
 620                 METER(table->stats.removeEnums++);
 621                 JS_DHashTableRawRemove(table, entry);
 622                 didRemove = JS_TRUE;
 623             }
 624             if (op & JS_DHASH_STOP)
 625                 break;
 626         }
 627         entryAddr += entrySize;
 628     }
 629
 630     /*
 631      * Shrink or compress if a quarter or more of all entries are removed, or
 632      * if the table is underloaded according to the configured minimum alpha,
 633      * and is not minimal-size already.  Do this only if we removed above, so
 634      * non-removing enumerations can count on stable table->entryStore until
 635      * the next non-lookup-Operate or removing-Enumerate.
 636      */
 637     if (didRemove &&
 638         (table->removedCount >= capacity >> 2 ||
 639          (capacity > JS_DHASH_MIN_SIZE &&
 640           table->entryCount <= MIN_LOAD(table, capacity)))) {
 641         METER(table->stats.enumShrinks++);
 642         capacity = table->entryCount;
 643         capacity += capacity >> 1;
 644         if (capacity < JS_DHASH_MIN_SIZE)
 645             capacity = JS_DHASH_MIN_SIZE;
 646         (void) ChangeTable(table,
 647                            JS_CeilingLog2(capacity)
 648                            - (JS_DHASH_BITS - table->hashShift));
 649     }
 650     return i;
 651 }
 652
 653 #ifdef JS_DHASHMETER
 654 #include <math.h>
 655
 656 JS_PUBLIC_API(void)
 657 JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp)
 658 {
 659     char *entryAddr;
 660     uint32 entrySize, entryCount;
 661     int hashShift, sizeLog2;
 662     uint32 i, tableSize, sizeMask, chainLen, maxChainLen, chainCount;
 663     JSDHashNumber hash1, hash2, saveHash1, maxChainHash1, maxChainHash2;
 664     double sqsum, mean, variance, sigma;
 665     JSDHashEntryHdr *entry, *probe;
 666
 667     entryAddr = table->entryStore;
 668     entrySize = table->entrySize;
 669     hashShift = table->hashShift;
 670     sizeLog2 = JS_DHASH_BITS - hashShift;
 671     tableSize = JS_DHASH_TABLE_SIZE(table);
 672     sizeMask = JS_BITMASK(sizeLog2);
 673     chainCount = maxChainLen = 0;
 674     hash2 = 0;
 675     sqsum = 0;
 676
 677     for (i = 0; i < tableSize; i++) {
 678         entry = (JSDHashEntryHdr *)entryAddr;
 679         entryAddr += entrySize;
 680         if (!ENTRY_IS_LIVE(entry))
 681             continue;
 682         hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
 683         saveHash1 = hash1;
 684         probe = ADDRESS_ENTRY(table, hash1);
 685         chainLen = 1;
 686         if (probe == entry) {
 687             /* Start of a (possibly unit-length) chain. */
 688             chainCount++;
 689         } else {
 690             hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
 691                           hashShift);
 692             do {
 693                 chainLen++;
 694                 hash1 -= hash2;
 695                 hash1 &= sizeMask;
 696                 probe = ADDRESS_ENTRY(table, hash1);
 697             } while (probe != entry);
 698         }
 699         sqsum += chainLen * chainLen;
 700         if (chainLen > maxChainLen) {
 701             maxChainLen = chainLen;
 702             maxChainHash1 = saveHash1;
 703             maxChainHash2 = hash2;
 704         }
 705     }
 706
 707     entryCount = table->entryCount;
 708     if (entryCount && chainCount) {
 709         mean = (double)entryCount / chainCount;
 710         variance = chainCount * sqsum - entryCount * entryCount;
 711         if (variance < 0 || chainCount == 1)
 712             variance = 0;
 713         else
 714             variance /= chainCount * (chainCount - 1);
 715         sigma = sqrt(variance);
 716     } else {
 717         mean = sigma = 0;
 718     }
 719
 720     fprintf(fp, "Double hashing statistics:\n");
 721     fprintf(fp, "    table size (in entries): %u\n", tableSize);
 722     fprintf(fp, "          number of entries: %u\n", table->entryCount);
 723     fprintf(fp, "  number of removed entries: %u\n", table->removedCount);
 724     fprintf(fp, "         number of searches: %u\n", table->stats.searches);
 725     fprintf(fp, "             number of hits: %u\n", table->stats.hits);
 726     fprintf(fp, "           number of misses: %u\n", table->stats.misses);
 727     fprintf(fp, "      mean steps per search: %g\n", table->stats.searches ?
 728                                                      (double)table->stats.steps
 729                                                      / table->stats.searches :
 730                                                      0.);
 731     fprintf(fp, "     mean hash chain length: %g\n", mean);
 732     fprintf(fp, "         standard deviation: %g\n", sigma);
 733     fprintf(fp, "  maximum hash chain length: %u\n", maxChainLen);
 734     fprintf(fp, "          number of lookups: %u\n", table->stats.lookups);
 735     fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
 736     fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
 737     fprintf(fp, "   adds that found an entry: %u\n", table->stats.addHits);
 738     fprintf(fp, "               add failures: %u\n", table->stats.addFailures);
 739     fprintf(fp, "             useful removes: %u\n", table->stats.removeHits);
 740     fprintf(fp, "            useless removes: %u\n", table->stats.removeMisses);
 741     fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
 742     fprintf(fp, "  removes while enumerating: %u\n", table->stats.removeEnums);
 743     fprintf(fp, "            number of grows: %u\n", table->stats.grows);
 744     fprintf(fp, "          number of shrinks: %u\n", table->stats.shrinks);
 745     fprintf(fp, "       number of compresses: %u\n", table->stats.compresses);
 746     fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
 747
 748     if (dump && maxChainLen && hash2) {
 749         fputs("Maximum hash chain:\n", fp);
 750         hash1 = maxChainHash1;
 751         hash2 = maxChainHash2;
 752         entry = ADDRESS_ENTRY(table, hash1);
 753         i = 0;
 754         do {
 755             if (dump(table, entry, i++, fp) != JS_DHASH_NEXT)
 756                 break;
 757             hash1 -= hash2;
 758             hash1 &= sizeMask;
 759             entry = ADDRESS_ENTRY(table, hash1);
 760         } while (JS_DHASH_ENTRY_IS_BUSY(entry));
 761     }
 762 }
 763 #endif /* JS_DHASHMETER */