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