js/src/jsdhash.cpp

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