michael@0: /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0:  * Double hashing implementation.
michael@0:  */
michael@0: #include <stdio.h>
michael@0: #include <stdlib.h>
michael@0: #include <string.h>
michael@0: #include "pldhash.h"
michael@0: #include "mozilla/HashFunctions.h"
michael@0: #include "mozilla/MathAlgorithms.h"
michael@0: #include "nsDebug.h"     /* for PR_ASSERT */
michael@0: #include "nsAlgorithm.h"
michael@0: #include "mozilla/Likely.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include "mozilla/ChaosMode.h"
michael@0: 
michael@0: #ifdef PL_DHASHMETER
michael@0: # define METER(x)       x
michael@0: #else
michael@0: # define METER(x)       /* nothing */
michael@0: #endif
michael@0: 
michael@0: /*
michael@0:  * The following DEBUG-only code is used to assert that calls to one of
michael@0:  * table->ops or to an enumerator do not cause re-entry into a call that
michael@0:  * can mutate the table.
michael@0:  */
michael@0: #ifdef DEBUG
michael@0: 
michael@0: /*
michael@0:  * Most callers that assert about the recursion level don't care about
michael@0:  * this magical value because they are asserting that mutation is
michael@0:  * allowed (and therefore the level is 0 or 1, depending on whether they
michael@0:  * incremented it).
michael@0:  *
michael@0:  * Only PL_DHashTableFinish needs to allow this special value.
michael@0:  */
michael@0: #define IMMUTABLE_RECURSION_LEVEL ((uint16_t)-1)
michael@0: 
michael@0: #define RECURSION_LEVEL_SAFE_TO_FINISH(table_)                                \
michael@0:     (table_->recursionLevel == 0 ||                                           \
michael@0:      table_->recursionLevel == IMMUTABLE_RECURSION_LEVEL)
michael@0: 
michael@0: #define INCREMENT_RECURSION_LEVEL(table_)                                     \
michael@0:     do {                                                                      \
michael@0:         if (table_->recursionLevel != IMMUTABLE_RECURSION_LEVEL)              \
michael@0:             ++table_->recursionLevel;                                         \
michael@0:     } while(0)
michael@0: #define DECREMENT_RECURSION_LEVEL(table_)                                     \
michael@0:     do {                                                                      \
michael@0:         if (table->recursionLevel != IMMUTABLE_RECURSION_LEVEL) {             \
michael@0:             MOZ_ASSERT(table->recursionLevel > 0);                            \
michael@0:             --table->recursionLevel;                                          \
michael@0:         }                                                                     \
michael@0:     } while(0)
michael@0: 
michael@0: #else
michael@0: 
michael@0: #define INCREMENT_RECURSION_LEVEL(table_)   do { } while(0)
michael@0: #define DECREMENT_RECURSION_LEVEL(table_)   do { } while(0)
michael@0: 
michael@0: #endif /* defined(DEBUG) */
michael@0: 
michael@0: using namespace mozilla;
michael@0: 
michael@0: void *
michael@0: PL_DHashAllocTable(PLDHashTable *table, uint32_t nbytes)
michael@0: {
michael@0:     return malloc(nbytes);
michael@0: }
michael@0: 
michael@0: void
michael@0: PL_DHashFreeTable(PLDHashTable *table, void *ptr)
michael@0: {
michael@0:     free(ptr);
michael@0: }
michael@0: 
michael@0: PLDHashNumber
michael@0: PL_DHashStringKey(PLDHashTable *table, const void *key)
michael@0: {
michael@0:     return HashString(static_cast<const char*>(key));
michael@0: }
michael@0: 
michael@0: PLDHashNumber
michael@0: PL_DHashVoidPtrKeyStub(PLDHashTable *table, const void *key)
michael@0: {
michael@0:     return (PLDHashNumber)(ptrdiff_t)key >> 2;
michael@0: }
michael@0: 
michael@0: bool
michael@0: PL_DHashMatchEntryStub(PLDHashTable *table,
michael@0:                        const PLDHashEntryHdr *entry,
michael@0:                        const void *key)
michael@0: {
michael@0:     const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
michael@0: 
michael@0:     return stub->key == key;
michael@0: }
michael@0: 
michael@0: bool
michael@0: PL_DHashMatchStringKey(PLDHashTable *table,
michael@0:                        const PLDHashEntryHdr *entry,
michael@0:                        const void *key)
michael@0: {
michael@0:     const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
michael@0: 
michael@0:     /* XXX tolerate null keys on account of sloppy Mozilla callers. */
michael@0:     return stub->key == key ||
michael@0:            (stub->key && key &&
michael@0:             strcmp((const char *) stub->key, (const char *) key) == 0);
michael@0: }
michael@0: 
michael@0: void
michael@0: PL_DHashMoveEntryStub(PLDHashTable *table,
michael@0:                       const PLDHashEntryHdr *from,
michael@0:                       PLDHashEntryHdr *to)
michael@0: {
michael@0:     memcpy(to, from, table->entrySize);
michael@0: }
michael@0: 
michael@0: void
michael@0: PL_DHashClearEntryStub(PLDHashTable *table, PLDHashEntryHdr *entry)
michael@0: {
michael@0:     memset(entry, 0, table->entrySize);
michael@0: }
michael@0: 
michael@0: void
michael@0: PL_DHashFreeStringKey(PLDHashTable *table, PLDHashEntryHdr *entry)
michael@0: {
michael@0:     const PLDHashEntryStub *stub = (const PLDHashEntryStub *)entry;
michael@0: 
michael@0:     free((void *) stub->key);
michael@0:     memset(entry, 0, table->entrySize);
michael@0: }
michael@0: 
michael@0: void
michael@0: PL_DHashFinalizeStub(PLDHashTable *table)
michael@0: {
michael@0: }
michael@0: 
michael@0: static const PLDHashTableOps stub_ops = {
michael@0:     PL_DHashAllocTable,
michael@0:     PL_DHashFreeTable,
michael@0:     PL_DHashVoidPtrKeyStub,
michael@0:     PL_DHashMatchEntryStub,
michael@0:     PL_DHashMoveEntryStub,
michael@0:     PL_DHashClearEntryStub,
michael@0:     PL_DHashFinalizeStub,
michael@0:     nullptr
michael@0: };
michael@0: 
michael@0: const PLDHashTableOps *
michael@0: PL_DHashGetStubOps(void)
michael@0: {
michael@0:     return &stub_ops;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: SizeOfEntryStore(uint32_t capacity, uint32_t entrySize, uint32_t *nbytes)
michael@0: {
michael@0:     uint64_t nbytes64 = uint64_t(capacity) * uint64_t(entrySize);
michael@0:     *nbytes = capacity * entrySize;
michael@0:     return uint64_t(*nbytes) == nbytes64;   // returns false on overflow
michael@0: }
michael@0: 
michael@0: PLDHashTable *
michael@0: PL_NewDHashTable(const PLDHashTableOps *ops, void *data, uint32_t entrySize,
michael@0:                  uint32_t capacity)
michael@0: {
michael@0:     PLDHashTable *table = (PLDHashTable *) malloc(sizeof *table);
michael@0:     if (!table)
michael@0:         return nullptr;
michael@0:     if (!PL_DHashTableInit(table, ops, data, entrySize, capacity, fallible_t())) {
michael@0:         free(table);
michael@0:         return nullptr;
michael@0:     }
michael@0:     return table;
michael@0: }
michael@0: 
michael@0: void
michael@0: PL_DHashTableDestroy(PLDHashTable *table)
michael@0: {
michael@0:     PL_DHashTableFinish(table);
michael@0:     free(table);
michael@0: }
michael@0: 
michael@0: bool
michael@0: PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops,
michael@0:                   void *data, uint32_t entrySize, uint32_t capacity,
michael@0:                   const fallible_t& )
michael@0: {
michael@0: #ifdef DEBUG
michael@0:     if (entrySize > 16 * sizeof(void *)) {
michael@0:         printf_stderr(
michael@0:                 "pldhash: for the table at address %p, the given entrySize"
michael@0:                 " of %lu definitely favors chaining over double hashing.\n",
michael@0:                 (void *) table,
michael@0:                 (unsigned long) entrySize);
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     table->ops = ops;
michael@0:     table->data = data;
michael@0:     if (capacity < PL_DHASH_MIN_SIZE)
michael@0:         capacity = PL_DHASH_MIN_SIZE;
michael@0: 
michael@0:     int log2 = CeilingLog2(capacity);
michael@0: 
michael@0:     capacity = 1u << log2;
michael@0:     if (capacity > PL_DHASH_MAX_SIZE)
michael@0:         return false;
michael@0:     table->hashShift = PL_DHASH_BITS - log2;
michael@0:     table->entrySize = entrySize;
michael@0:     table->entryCount = table->removedCount = 0;
michael@0:     table->generation = 0;
michael@0:     uint32_t nbytes;
michael@0:     if (!SizeOfEntryStore(capacity, entrySize, &nbytes))
michael@0:         return false;   // overflowed
michael@0: 
michael@0:     table->entryStore = (char *) ops->allocTable(table, nbytes);
michael@0:     if (!table->entryStore)
michael@0:         return false;
michael@0:     memset(table->entryStore, 0, nbytes);
michael@0:     METER(memset(&table->stats, 0, sizeof table->stats));
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     table->recursionLevel = 0;
michael@0: #endif
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void
michael@0: PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops, void *data,
michael@0:                   uint32_t entrySize, uint32_t capacity)
michael@0: {
michael@0:     if (!PL_DHashTableInit(table, ops, data, entrySize, capacity, fallible_t())) {
michael@0:         if (capacity > PL_DHASH_MAX_SIZE) {
michael@0:             MOZ_CRASH();
michael@0:         }
michael@0:         uint32_t nbytes;
michael@0:         if (!SizeOfEntryStore(capacity, entrySize, &nbytes)) {
michael@0:             MOZ_CRASH();
michael@0:         }
michael@0:         NS_ABORT_OOM(nbytes);
michael@0:     }
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Compute max and min load numbers (entry counts).  We have a secondary max
michael@0:  * that allows us to overload a table reasonably if it cannot be grown further
michael@0:  * (i.e. if ChangeTable() fails).  The table slows down drastically if the
michael@0:  * secondary max is too close to 1, but 0.96875 gives only a slight slowdown
michael@0:  * while allowing 1.3x more elements.
michael@0:  */
michael@0: static inline uint32_t MaxLoad(uint32_t size) {
michael@0:     return size - (size >> 2);  // == size * 0.75
michael@0: }
michael@0: static inline uint32_t MaxLoadOnGrowthFailure(uint32_t size) {
michael@0:     return size - (size >> 5);  // == size * 0.96875
michael@0: }
michael@0: static inline uint32_t MinLoad(uint32_t size) {
michael@0:     return size >> 2;           // == size * 0.25
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Double hashing needs the second hash code to be relatively prime to table
michael@0:  * size, so we simply make hash2 odd.
michael@0:  */
michael@0: #define HASH1(hash0, shift)         ((hash0) >> (shift))
michael@0: #define HASH2(hash0,log2,shift)     ((((hash0) << (log2)) >> (shift)) | 1)
michael@0: 
michael@0: /*
michael@0:  * Reserve keyHash 0 for free entries and 1 for removed-entry sentinels.  Note
michael@0:  * that a removed-entry sentinel need be stored only if the removed entry had
michael@0:  * a colliding entry added after it.  Therefore we can use 1 as the collision
michael@0:  * flag in addition to the removed-entry sentinel value.  Multiplicative hash
michael@0:  * uses the high order bits of keyHash, so this least-significant reservation
michael@0:  * should not hurt the hash function's effectiveness much.
michael@0:  *
michael@0:  * If you change any of these magic numbers, also update PL_DHASH_ENTRY_IS_LIVE
michael@0:  * in pldhash.h.  It used to be private to pldhash.c, but then became public to
michael@0:  * assist iterator writers who inspect table->entryStore directly.
michael@0:  */
michael@0: #define COLLISION_FLAG              ((PLDHashNumber) 1)
michael@0: #define MARK_ENTRY_FREE(entry)      ((entry)->keyHash = 0)
michael@0: #define MARK_ENTRY_REMOVED(entry)   ((entry)->keyHash = 1)
michael@0: #define ENTRY_IS_REMOVED(entry)     ((entry)->keyHash == 1)
michael@0: #define ENTRY_IS_LIVE(entry)        PL_DHASH_ENTRY_IS_LIVE(entry)
michael@0: #define ENSURE_LIVE_KEYHASH(hash0)  if (hash0 < 2) hash0 -= 2; else (void)0
michael@0: 
michael@0: /* Match an entry's keyHash against an unstored one computed from a key. */
michael@0: #define MATCH_ENTRY_KEYHASH(entry,hash0) \
michael@0:     (((entry)->keyHash & ~COLLISION_FLAG) == (hash0))
michael@0: 
michael@0: /* Compute the address of the indexed entry in table. */
michael@0: #define ADDRESS_ENTRY(table, index) \
michael@0:     ((PLDHashEntryHdr *)((table)->entryStore + (index) * (table)->entrySize))
michael@0: 
michael@0: void
michael@0: PL_DHashTableFinish(PLDHashTable *table)
michael@0: {
michael@0:     INCREMENT_RECURSION_LEVEL(table);
michael@0: 
michael@0:     /* Call finalize before clearing entries, so it can enumerate them. */
michael@0:     table->ops->finalize(table);
michael@0: 
michael@0:     /* Clear any remaining live entries. */
michael@0:     char *entryAddr = table->entryStore;
michael@0:     uint32_t entrySize = table->entrySize;
michael@0:     char *entryLimit = entryAddr + PL_DHASH_TABLE_SIZE(table) * entrySize;
michael@0:     while (entryAddr < entryLimit) {
michael@0:         PLDHashEntryHdr *entry = (PLDHashEntryHdr *)entryAddr;
michael@0:         if (ENTRY_IS_LIVE(entry)) {
michael@0:             METER(table->stats.removeEnums++);
michael@0:             table->ops->clearEntry(table, entry);
michael@0:         }
michael@0:         entryAddr += entrySize;
michael@0:     }
michael@0: 
michael@0:     DECREMENT_RECURSION_LEVEL(table);
michael@0:     MOZ_ASSERT(RECURSION_LEVEL_SAFE_TO_FINISH(table));
michael@0: 
michael@0:     /* Free entry storage last. */
michael@0:     table->ops->freeTable(table, table->entryStore);
michael@0: }
michael@0: 
michael@0: static PLDHashEntryHdr * PL_DHASH_FASTCALL
michael@0: SearchTable(PLDHashTable *table, const void *key, PLDHashNumber keyHash,
michael@0:             PLDHashOperator op)
michael@0: {
michael@0:     METER(table->stats.searches++);
michael@0:     NS_ASSERTION(!(keyHash & COLLISION_FLAG),
michael@0:                  "!(keyHash & COLLISION_FLAG)");
michael@0: 
michael@0:     /* Compute the primary hash address. */
michael@0:     int hashShift = table->hashShift;
michael@0:     PLDHashNumber hash1 = HASH1(keyHash, hashShift);
michael@0:     PLDHashEntryHdr *entry = ADDRESS_ENTRY(table, hash1);
michael@0: 
michael@0:     /* Miss: return space for a new entry. */
michael@0:     if (PL_DHASH_ENTRY_IS_FREE(entry)) {
michael@0:         METER(table->stats.misses++);
michael@0:         return entry;
michael@0:     }
michael@0: 
michael@0:     /* Hit: return entry. */
michael@0:     PLDHashMatchEntry matchEntry = table->ops->matchEntry;
michael@0:     if (MATCH_ENTRY_KEYHASH(entry, keyHash) && matchEntry(table, entry, key)) {
michael@0:         METER(table->stats.hits++);
michael@0:         return entry;
michael@0:     }
michael@0: 
michael@0:     /* Collision: double hash. */
michael@0:     int sizeLog2 = PL_DHASH_BITS - table->hashShift;
michael@0:     PLDHashNumber hash2 = HASH2(keyHash, sizeLog2, hashShift);
michael@0:     uint32_t sizeMask = (1u << sizeLog2) - 1;
michael@0: 
michael@0:     /* Save the first removed entry pointer so PL_DHASH_ADD can recycle it. */
michael@0:     PLDHashEntryHdr *firstRemoved = nullptr;
michael@0: 
michael@0:     for (;;) {
michael@0:         if (MOZ_UNLIKELY(ENTRY_IS_REMOVED(entry))) {
michael@0:             if (!firstRemoved)
michael@0:                 firstRemoved = entry;
michael@0:         } else {
michael@0:             if (op == PL_DHASH_ADD)
michael@0:                 entry->keyHash |= COLLISION_FLAG;
michael@0:         }
michael@0: 
michael@0:         METER(table->stats.steps++);
michael@0:         hash1 -= hash2;
michael@0:         hash1 &= sizeMask;
michael@0: 
michael@0:         entry = ADDRESS_ENTRY(table, hash1);
michael@0:         if (PL_DHASH_ENTRY_IS_FREE(entry)) {
michael@0:             METER(table->stats.misses++);
michael@0:             return (firstRemoved && op == PL_DHASH_ADD) ? firstRemoved : entry;
michael@0:         }
michael@0: 
michael@0:         if (MATCH_ENTRY_KEYHASH(entry, keyHash) &&
michael@0:             matchEntry(table, entry, key)) {
michael@0:             METER(table->stats.hits++);
michael@0:             return entry;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* NOTREACHED */
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This is a copy of SearchTable, used by ChangeTable, hardcoded to
michael@0:  *   1. assume |op == PL_DHASH_ADD|,
michael@0:  *   2. assume that |key| will never match an existing entry, and
michael@0:  *   3. assume that no entries have been removed from the current table
michael@0:  *      structure.
michael@0:  * Avoiding the need for |key| means we can avoid needing a way to map
michael@0:  * entries to keys, which means callers can use complex key types more
michael@0:  * easily.
michael@0:  */
michael@0: static PLDHashEntryHdr * PL_DHASH_FASTCALL
michael@0: FindFreeEntry(PLDHashTable *table, PLDHashNumber keyHash)
michael@0: {
michael@0:     METER(table->stats.searches++);
michael@0:     NS_ASSERTION(!(keyHash & COLLISION_FLAG),
michael@0:                  "!(keyHash & COLLISION_FLAG)");
michael@0: 
michael@0:     /* Compute the primary hash address. */
michael@0:     int hashShift = table->hashShift;
michael@0:     PLDHashNumber hash1 = HASH1(keyHash, hashShift);
michael@0:     PLDHashEntryHdr *entry = ADDRESS_ENTRY(table, hash1);
michael@0: 
michael@0:     /* Miss: return space for a new entry. */
michael@0:     if (PL_DHASH_ENTRY_IS_FREE(entry)) {
michael@0:         METER(table->stats.misses++);
michael@0:         return entry;
michael@0:     }
michael@0: 
michael@0:     /* Collision: double hash. */
michael@0:     int sizeLog2 = PL_DHASH_BITS - table->hashShift;
michael@0:     PLDHashNumber hash2 = HASH2(keyHash, sizeLog2, hashShift);
michael@0:     uint32_t sizeMask = (1u << sizeLog2) - 1;
michael@0: 
michael@0:     for (;;) {
michael@0:         NS_ASSERTION(!ENTRY_IS_REMOVED(entry),
michael@0:                      "!ENTRY_IS_REMOVED(entry)");
michael@0:         entry->keyHash |= COLLISION_FLAG;
michael@0: 
michael@0:         METER(table->stats.steps++);
michael@0:         hash1 -= hash2;
michael@0:         hash1 &= sizeMask;
michael@0: 
michael@0:         entry = ADDRESS_ENTRY(table, hash1);
michael@0:         if (PL_DHASH_ENTRY_IS_FREE(entry)) {
michael@0:             METER(table->stats.misses++);
michael@0:             return entry;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* NOTREACHED */
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: static bool
michael@0: ChangeTable(PLDHashTable *table, int deltaLog2)
michael@0: {
michael@0:     /* Look, but don't touch, until we succeed in getting new entry store. */
michael@0:     int oldLog2 = PL_DHASH_BITS - table->hashShift;
michael@0:     int newLog2 = oldLog2 + deltaLog2;
michael@0:     uint32_t newCapacity = 1u << newLog2;
michael@0:     if (newCapacity > PL_DHASH_MAX_SIZE)
michael@0:         return false;
michael@0: 
michael@0:     uint32_t entrySize = table->entrySize;
michael@0:     uint32_t nbytes;
michael@0:     if (!SizeOfEntryStore(newCapacity, entrySize, &nbytes))
michael@0:         return false;   // overflowed
michael@0: 
michael@0:     char *newEntryStore = (char *) table->ops->allocTable(table, nbytes);
michael@0:     if (!newEntryStore)
michael@0:         return false;
michael@0: 
michael@0:     /* We can't fail from here on, so update table parameters. */
michael@0: #ifdef DEBUG
michael@0:     uint32_t recursionLevel = table->recursionLevel;
michael@0: #endif
michael@0:     table->hashShift = PL_DHASH_BITS - newLog2;
michael@0:     table->removedCount = 0;
michael@0:     table->generation++;
michael@0: 
michael@0:     /* Assign the new entry store to table. */
michael@0:     memset(newEntryStore, 0, nbytes);
michael@0:     char *oldEntryStore, *oldEntryAddr;
michael@0:     oldEntryAddr = oldEntryStore = table->entryStore;
michael@0:     table->entryStore = newEntryStore;
michael@0:     PLDHashMoveEntry moveEntry = table->ops->moveEntry;
michael@0: #ifdef DEBUG
michael@0:     table->recursionLevel = recursionLevel;
michael@0: #endif
michael@0: 
michael@0:     /* Copy only live entries, leaving removed ones behind. */
michael@0:     uint32_t oldCapacity = 1u << oldLog2;
michael@0:     for (uint32_t i = 0; i < oldCapacity; i++) {
michael@0:         PLDHashEntryHdr *oldEntry = (PLDHashEntryHdr *)oldEntryAddr;
michael@0:         if (ENTRY_IS_LIVE(oldEntry)) {
michael@0:             oldEntry->keyHash &= ~COLLISION_FLAG;
michael@0:             PLDHashEntryHdr *newEntry = FindFreeEntry(table, oldEntry->keyHash);
michael@0:             NS_ASSERTION(PL_DHASH_ENTRY_IS_FREE(newEntry),
michael@0:                          "PL_DHASH_ENTRY_IS_FREE(newEntry)");
michael@0:             moveEntry(table, oldEntry, newEntry);
michael@0:             newEntry->keyHash = oldEntry->keyHash;
michael@0:         }
michael@0:         oldEntryAddr += entrySize;
michael@0:     }
michael@0: 
michael@0:     table->ops->freeTable(table, oldEntryStore);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: PLDHashEntryHdr * PL_DHASH_FASTCALL
michael@0: PL_DHashTableOperate(PLDHashTable *table, const void *key, PLDHashOperator op)
michael@0: {
michael@0:     PLDHashEntryHdr *entry;
michael@0: 
michael@0:     MOZ_ASSERT(op == PL_DHASH_LOOKUP || table->recursionLevel == 0);
michael@0:     INCREMENT_RECURSION_LEVEL(table);
michael@0: 
michael@0:     PLDHashNumber keyHash = table->ops->hashKey(table, key);
michael@0:     keyHash *= PL_DHASH_GOLDEN_RATIO;
michael@0: 
michael@0:     /* Avoid 0 and 1 hash codes, they indicate free and removed entries. */
michael@0:     ENSURE_LIVE_KEYHASH(keyHash);
michael@0:     keyHash &= ~COLLISION_FLAG;
michael@0: 
michael@0:     switch (op) {
michael@0:       case PL_DHASH_LOOKUP:
michael@0:         METER(table->stats.lookups++);
michael@0:         entry = SearchTable(table, key, keyHash, op);
michael@0:         break;
michael@0: 
michael@0:       case PL_DHASH_ADD: {
michael@0:         /*
michael@0:          * If alpha is >= .75, grow or compress the table.  If key is already
michael@0:          * in the table, we may grow once more than necessary, but only if we
michael@0:          * are on the edge of being overloaded.
michael@0:          */
michael@0:         uint32_t size = PL_DHASH_TABLE_SIZE(table);
michael@0:         if (table->entryCount + table->removedCount >= MaxLoad(size)) {
michael@0:             /* Compress if a quarter or more of all entries are removed. */
michael@0:             int deltaLog2;
michael@0:             if (table->removedCount >= size >> 2) {
michael@0:                 METER(table->stats.compresses++);
michael@0:                 deltaLog2 = 0;
michael@0:             } else {
michael@0:                 METER(table->stats.grows++);
michael@0:                 deltaLog2 = 1;
michael@0:             }
michael@0: 
michael@0:             /*
michael@0:              * Grow or compress table.  If ChangeTable() fails, allow
michael@0:              * overloading up to the secondary max.  Once we hit the secondary
michael@0:              * max, return null.
michael@0:              */
michael@0:             if (!ChangeTable(table, deltaLog2) &&
michael@0:                 table->entryCount + table->removedCount >=
michael@0:                     MaxLoadOnGrowthFailure(size))
michael@0:             {
michael@0:                 METER(table->stats.addFailures++);
michael@0:                 entry = nullptr;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         /*
michael@0:          * Look for entry after possibly growing, so we don't have to add it,
michael@0:          * then skip it while growing the table and re-add it after.
michael@0:          */
michael@0:         entry = SearchTable(table, key, keyHash, op);
michael@0:         if (!ENTRY_IS_LIVE(entry)) {
michael@0:             /* Initialize the entry, indicating that it's no longer free. */
michael@0:             METER(table->stats.addMisses++);
michael@0:             if (ENTRY_IS_REMOVED(entry)) {
michael@0:                 METER(table->stats.addOverRemoved++);
michael@0:                 table->removedCount--;
michael@0:                 keyHash |= COLLISION_FLAG;
michael@0:             }
michael@0:             if (table->ops->initEntry &&
michael@0:                 !table->ops->initEntry(table, entry, key)) {
michael@0:                 /* We haven't claimed entry yet; fail with null return. */
michael@0:                 memset(entry + 1, 0, table->entrySize - sizeof *entry);
michael@0:                 entry = nullptr;
michael@0:                 break;
michael@0:             }
michael@0:             entry->keyHash = keyHash;
michael@0:             table->entryCount++;
michael@0:         }
michael@0:         METER(else table->stats.addHits++);
michael@0:         break;
michael@0:       }
michael@0: 
michael@0:       case PL_DHASH_REMOVE:
michael@0:         entry = SearchTable(table, key, keyHash, op);
michael@0:         if (ENTRY_IS_LIVE(entry)) {
michael@0:             /* Clear this entry and mark it as "removed". */
michael@0:             METER(table->stats.removeHits++);
michael@0:             PL_DHashTableRawRemove(table, entry);
michael@0: 
michael@0:             /* Shrink if alpha is <= .25 and table isn't too small already. */
michael@0:             uint32_t size = PL_DHASH_TABLE_SIZE(table);
michael@0:             if (size > PL_DHASH_MIN_SIZE &&
michael@0:                 table->entryCount <= MinLoad(size)) {
michael@0:                 METER(table->stats.shrinks++);
michael@0:                 (void) ChangeTable(table, -1);
michael@0:             }
michael@0:         }
michael@0:         METER(else table->stats.removeMisses++);
michael@0:         entry = nullptr;
michael@0:         break;
michael@0: 
michael@0:       default:
michael@0:         NS_NOTREACHED("0");
michael@0:         entry = nullptr;
michael@0:     }
michael@0: 
michael@0:     DECREMENT_RECURSION_LEVEL(table);
michael@0: 
michael@0:     return entry;
michael@0: }
michael@0: 
michael@0: void
michael@0: PL_DHashTableRawRemove(PLDHashTable *table, PLDHashEntryHdr *entry)
michael@0: {
michael@0:     MOZ_ASSERT(table->recursionLevel != IMMUTABLE_RECURSION_LEVEL);
michael@0: 
michael@0:     NS_ASSERTION(PL_DHASH_ENTRY_IS_LIVE(entry),
michael@0:                  "PL_DHASH_ENTRY_IS_LIVE(entry)");
michael@0: 
michael@0:     /* Load keyHash first in case clearEntry() goofs it. */
michael@0:     PLDHashNumber keyHash = entry->keyHash;
michael@0:     table->ops->clearEntry(table, entry);
michael@0:     if (keyHash & COLLISION_FLAG) {
michael@0:         MARK_ENTRY_REMOVED(entry);
michael@0:         table->removedCount++;
michael@0:     } else {
michael@0:         METER(table->stats.removeFrees++);
michael@0:         MARK_ENTRY_FREE(entry);
michael@0:     }
michael@0:     table->entryCount--;
michael@0: }
michael@0: 
michael@0: uint32_t
michael@0: PL_DHashTableEnumerate(PLDHashTable *table, PLDHashEnumerator etor, void *arg)
michael@0: {
michael@0:     INCREMENT_RECURSION_LEVEL(table);
michael@0: 
michael@0:     char *entryAddr = table->entryStore;
michael@0:     uint32_t entrySize = table->entrySize;
michael@0:     uint32_t capacity = PL_DHASH_TABLE_SIZE(table);
michael@0:     uint32_t tableSize = capacity * entrySize;
michael@0:     char *entryLimit = entryAddr + tableSize;
michael@0:     uint32_t i = 0;
michael@0:     bool didRemove = false;
michael@0: 
michael@0:     if (ChaosMode::isActive()) {
michael@0:         // Start iterating at a random point in the hashtable. It would be
michael@0:         // even more chaotic to iterate in fully random order, but that's a lot
michael@0:         // more work.
michael@0:         entryAddr += ChaosMode::randomUint32LessThan(capacity) * entrySize;
michael@0:         if (entryAddr >= entryLimit) {
michael@0:             entryAddr -= tableSize;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     for (uint32_t e = 0; e < capacity; ++e) {
michael@0:         PLDHashEntryHdr *entry = (PLDHashEntryHdr *)entryAddr;
michael@0:         if (ENTRY_IS_LIVE(entry)) {
michael@0:             PLDHashOperator op = etor(table, entry, i++, arg);
michael@0:             if (op & PL_DHASH_REMOVE) {
michael@0:                 METER(table->stats.removeEnums++);
michael@0:                 PL_DHashTableRawRemove(table, entry);
michael@0:                 didRemove = true;
michael@0:             }
michael@0:             if (op & PL_DHASH_STOP)
michael@0:                 break;
michael@0:         }
michael@0:         entryAddr += entrySize;
michael@0:         if (entryAddr >= entryLimit) {
michael@0:             entryAddr -= tableSize;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     MOZ_ASSERT(!didRemove || table->recursionLevel == 1);
michael@0: 
michael@0:     /*
michael@0:      * Shrink or compress if a quarter or more of all entries are removed, or
michael@0:      * if the table is underloaded according to the minimum alpha, and is not
michael@0:      * minimal-size already.  Do this only if we removed above, so non-removing
michael@0:      * enumerations can count on stable table->entryStore until the next
michael@0:      * non-lookup-Operate or removing-Enumerate.
michael@0:      */
michael@0:     if (didRemove &&
michael@0:         (table->removedCount >= capacity >> 2 ||
michael@0:          (capacity > PL_DHASH_MIN_SIZE &&
michael@0:           table->entryCount <= MinLoad(capacity)))) {
michael@0:         METER(table->stats.enumShrinks++);
michael@0:         capacity = table->entryCount;
michael@0:         capacity += capacity >> 1;
michael@0:         if (capacity < PL_DHASH_MIN_SIZE)
michael@0:             capacity = PL_DHASH_MIN_SIZE;
michael@0: 
michael@0:         uint32_t ceiling = CeilingLog2(capacity);
michael@0:         ceiling -= PL_DHASH_BITS - table->hashShift;
michael@0: 
michael@0:         (void) ChangeTable(table, ceiling);
michael@0:     }
michael@0: 
michael@0:     DECREMENT_RECURSION_LEVEL(table);
michael@0: 
michael@0:     return i;
michael@0: }
michael@0: 
michael@0: struct SizeOfEntryExcludingThisArg
michael@0: {
michael@0:     size_t total;
michael@0:     PLDHashSizeOfEntryExcludingThisFun sizeOfEntryExcludingThis;
michael@0:     MallocSizeOf mallocSizeOf;
michael@0:     void *arg;      // the arg passed by the user
michael@0: };
michael@0: 
michael@0: static PLDHashOperator
michael@0: SizeOfEntryExcludingThisEnumerator(PLDHashTable *table, PLDHashEntryHdr *hdr,
michael@0:                                    uint32_t number, void *arg)
michael@0: {
michael@0:     SizeOfEntryExcludingThisArg *e = (SizeOfEntryExcludingThisArg *)arg;
michael@0:     e->total += e->sizeOfEntryExcludingThis(hdr, e->mallocSizeOf, e->arg);
michael@0:     return PL_DHASH_NEXT;
michael@0: }
michael@0: 
michael@0: size_t
michael@0: PL_DHashTableSizeOfExcludingThis(const PLDHashTable *table,
michael@0:                                  PLDHashSizeOfEntryExcludingThisFun sizeOfEntryExcludingThis,
michael@0:                                  MallocSizeOf mallocSizeOf,
michael@0:                                  void *arg /* = nullptr */)
michael@0: {
michael@0:     size_t n = 0;
michael@0:     n += mallocSizeOf(table->entryStore);
michael@0:     if (sizeOfEntryExcludingThis) {
michael@0:         SizeOfEntryExcludingThisArg arg2 = { 0, sizeOfEntryExcludingThis, mallocSizeOf, arg };
michael@0:         PL_DHashTableEnumerate(const_cast<PLDHashTable *>(table),
michael@0:                                SizeOfEntryExcludingThisEnumerator, &arg2);
michael@0:         n += arg2.total;
michael@0:     }
michael@0:     return n;
michael@0: }
michael@0: 
michael@0: size_t
michael@0: PL_DHashTableSizeOfIncludingThis(const PLDHashTable *table,
michael@0:                                  PLDHashSizeOfEntryExcludingThisFun sizeOfEntryExcludingThis,
michael@0:                                  MallocSizeOf mallocSizeOf,
michael@0:                                  void *arg /* = nullptr */)
michael@0: {
michael@0:     return mallocSizeOf(table) +
michael@0:            PL_DHashTableSizeOfExcludingThis(table, sizeOfEntryExcludingThis,
michael@0:                                             mallocSizeOf, arg);
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG
michael@0: void
michael@0: PL_DHashMarkTableImmutable(PLDHashTable *table)
michael@0: {
michael@0:     table->recursionLevel = IMMUTABLE_RECURSION_LEVEL;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: #ifdef PL_DHASHMETER
michael@0: #include <math.h>
michael@0: 
michael@0: void
michael@0: PL_DHashTableDumpMeter(PLDHashTable *table, PLDHashEnumerator dump, FILE *fp)
michael@0: {
michael@0:     PLDHashNumber hash1, hash2, maxChainHash1, maxChainHash2;
michael@0:     double sqsum, mean, variance, sigma;
michael@0:     PLDHashEntryHdr *entry;
michael@0: 
michael@0:     char *entryAddr = table->entryStore;
michael@0:     uint32_t entrySize = table->entrySize;
michael@0:     int hashShift = table->hashShift;
michael@0:     int sizeLog2 = PL_DHASH_BITS - hashShift;
michael@0:     uint32_t tableSize = PL_DHASH_TABLE_SIZE(table);
michael@0:     uint32_t sizeMask = (1u << sizeLog2) - 1;
michael@0:     uint32_t chainCount = 0, maxChainLen = 0;
michael@0:     hash2 = 0;
michael@0:     sqsum = 0;
michael@0: 
michael@0:     for (uint32_t i = 0; i < tableSize; i++) {
michael@0:         entry = (PLDHashEntryHdr *)entryAddr;
michael@0:         entryAddr += entrySize;
michael@0:         if (!ENTRY_IS_LIVE(entry))
michael@0:             continue;
michael@0:         hash1 = HASH1(entry->keyHash & ~COLLISION_FLAG, hashShift);
michael@0:         PLDHashNumber saveHash1 = hash1;
michael@0:         PLDHashEntryHdr *probe = ADDRESS_ENTRY(table, hash1);
michael@0:         uint32_t chainLen = 1;
michael@0:         if (probe == entry) {
michael@0:             /* Start of a (possibly unit-length) chain. */
michael@0:             chainCount++;
michael@0:         } else {
michael@0:             hash2 = HASH2(entry->keyHash & ~COLLISION_FLAG, sizeLog2,
michael@0:                           hashShift);
michael@0:             do {
michael@0:                 chainLen++;
michael@0:                 hash1 -= hash2;
michael@0:                 hash1 &= sizeMask;
michael@0:                 probe = ADDRESS_ENTRY(table, hash1);
michael@0:             } while (probe != entry);
michael@0:         }
michael@0:         sqsum += chainLen * chainLen;
michael@0:         if (chainLen > maxChainLen) {
michael@0:             maxChainLen = chainLen;
michael@0:             maxChainHash1 = saveHash1;
michael@0:             maxChainHash2 = hash2;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     uint32_t entryCount = table->entryCount;
michael@0:     if (entryCount && chainCount) {
michael@0:         mean = (double)entryCount / chainCount;
michael@0:         variance = chainCount * sqsum - entryCount * entryCount;
michael@0:         if (variance < 0 || chainCount == 1)
michael@0:             variance = 0;
michael@0:         else
michael@0:             variance /= chainCount * (chainCount - 1);
michael@0:         sigma = sqrt(variance);
michael@0:     } else {
michael@0:         mean = sigma = 0;
michael@0:     }
michael@0: 
michael@0:     fprintf(fp, "Double hashing statistics:\n");
michael@0:     fprintf(fp, "    table size (in entries): %u\n", tableSize);
michael@0:     fprintf(fp, "          number of entries: %u\n", table->entryCount);
michael@0:     fprintf(fp, "  number of removed entries: %u\n", table->removedCount);
michael@0:     fprintf(fp, "         number of searches: %u\n", table->stats.searches);
michael@0:     fprintf(fp, "             number of hits: %u\n", table->stats.hits);
michael@0:     fprintf(fp, "           number of misses: %u\n", table->stats.misses);
michael@0:     fprintf(fp, "      mean steps per search: %g\n", table->stats.searches ?
michael@0:                                                      (double)table->stats.steps
michael@0:                                                      / table->stats.searches :
michael@0:                                                      0.);
michael@0:     fprintf(fp, "     mean hash chain length: %g\n", mean);
michael@0:     fprintf(fp, "         standard deviation: %g\n", sigma);
michael@0:     fprintf(fp, "  maximum hash chain length: %u\n", maxChainLen);
michael@0:     fprintf(fp, "          number of lookups: %u\n", table->stats.lookups);
michael@0:     fprintf(fp, " adds that made a new entry: %u\n", table->stats.addMisses);
michael@0:     fprintf(fp, "adds that recycled removeds: %u\n", table->stats.addOverRemoved);
michael@0:     fprintf(fp, "   adds that found an entry: %u\n", table->stats.addHits);
michael@0:     fprintf(fp, "               add failures: %u\n", table->stats.addFailures);
michael@0:     fprintf(fp, "             useful removes: %u\n", table->stats.removeHits);
michael@0:     fprintf(fp, "            useless removes: %u\n", table->stats.removeMisses);
michael@0:     fprintf(fp, "removes that freed an entry: %u\n", table->stats.removeFrees);
michael@0:     fprintf(fp, "  removes while enumerating: %u\n", table->stats.removeEnums);
michael@0:     fprintf(fp, "            number of grows: %u\n", table->stats.grows);
michael@0:     fprintf(fp, "          number of shrinks: %u\n", table->stats.shrinks);
michael@0:     fprintf(fp, "       number of compresses: %u\n", table->stats.compresses);
michael@0:     fprintf(fp, "number of enumerate shrinks: %u\n", table->stats.enumShrinks);
michael@0: 
michael@0:     if (dump && maxChainLen && hash2) {
michael@0:         fputs("Maximum hash chain:\n", fp);
michael@0:         hash1 = maxChainHash1;
michael@0:         hash2 = maxChainHash2;
michael@0:         entry = ADDRESS_ENTRY(table, hash1);
michael@0:         uint32_t i = 0;
michael@0:         do {
michael@0:             if (dump(table, entry, i++, fp) != PL_DHASH_NEXT)
michael@0:                 break;
michael@0:             hash1 -= hash2;
michael@0:             hash1 &= sizeMask;
michael@0:             entry = ADDRESS_ENTRY(table, hash1);
michael@0:         } while (PL_DHASH_ENTRY_IS_BUSY(entry));
michael@0:     }
michael@0: }
michael@0: #endif /* PL_DHASHMETER */