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: #ifndef pldhash_h___ michael@0: #define pldhash_h___ michael@0: /* michael@0: * Double hashing, a la Knuth 6. michael@0: */ michael@0: #include "mozilla/fallible.h" michael@0: #include "mozilla/MemoryReporting.h" michael@0: #include "mozilla/Types.h" michael@0: #include "nscore.h" michael@0: michael@0: #if defined(__GNUC__) && defined(__i386__) michael@0: #define PL_DHASH_FASTCALL __attribute__ ((regparm (3),stdcall)) michael@0: #elif defined(XP_WIN) michael@0: #define PL_DHASH_FASTCALL __fastcall michael@0: #else michael@0: #define PL_DHASH_FASTCALL michael@0: #endif michael@0: michael@0: /* michael@0: * Table size limit; do not exceed. The max capacity used to be 1<<23 but that michael@0: * occasionally that wasn't enough. Making it much bigger than 1<<26 probably michael@0: * isn't worthwhile -- tables that big are kind of ridiculous. Also, the michael@0: * growth operation will (deliberately) fail if |capacity * entrySize| michael@0: * overflows a uint32_t, and entrySize is always at least 8 bytes. michael@0: */ michael@0: #undef PL_DHASH_MAX_SIZE michael@0: #define PL_DHASH_MAX_SIZE ((uint32_t)1 << 26) michael@0: michael@0: /* Minimum table size, or gross entry count (net is at most .75 loaded). */ michael@0: #ifndef PL_DHASH_MIN_SIZE michael@0: #define PL_DHASH_MIN_SIZE 16 michael@0: #elif (PL_DHASH_MIN_SIZE & (PL_DHASH_MIN_SIZE - 1)) != 0 michael@0: #error "PL_DHASH_MIN_SIZE must be a power of two!" michael@0: #endif michael@0: michael@0: /* michael@0: * Multiplicative hash uses an unsigned 32 bit integer and the golden ratio, michael@0: * expressed as a fixed-point 32-bit fraction. michael@0: */ michael@0: #define PL_DHASH_BITS 32 michael@0: #define PL_DHASH_GOLDEN_RATIO 0x9E3779B9U michael@0: michael@0: /* Primitive and forward-struct typedefs. */ michael@0: typedef uint32_t PLDHashNumber; michael@0: typedef struct PLDHashEntryHdr PLDHashEntryHdr; michael@0: typedef struct PLDHashEntryStub PLDHashEntryStub; michael@0: typedef struct PLDHashTable PLDHashTable; michael@0: typedef struct PLDHashTableOps PLDHashTableOps; michael@0: michael@0: /* michael@0: * Table entry header structure. michael@0: * michael@0: * In order to allow in-line allocation of key and value, we do not declare michael@0: * either here. Instead, the API uses const void *key as a formal parameter. michael@0: * The key need not be stored in the entry; it may be part of the value, but michael@0: * need not be stored at all. michael@0: * michael@0: * Callback types are defined below and grouped into the PLDHashTableOps michael@0: * structure, for single static initialization per hash table sub-type. michael@0: * michael@0: * Each hash table sub-type should nest the PLDHashEntryHdr structure at the michael@0: * front of its particular entry type. The keyHash member contains the result michael@0: * of multiplying the hash code returned from the hashKey callback (see below) michael@0: * by PL_DHASH_GOLDEN_RATIO, then constraining the result to avoid the magic 0 michael@0: * and 1 values. The stored keyHash value is table size invariant, and it is michael@0: * maintained automatically by PL_DHashTableOperate -- users should never set michael@0: * it, and its only uses should be via the entry macros below. michael@0: * michael@0: * The PL_DHASH_ENTRY_IS_LIVE function tests whether entry is neither free nor michael@0: * removed. An entry may be either busy or free; if busy, it may be live or michael@0: * removed. Consumers of this API should not access members of entries that michael@0: * are not live. michael@0: * michael@0: * However, use PL_DHASH_ENTRY_IS_BUSY for faster liveness testing of entries michael@0: * returned by PL_DHashTableOperate, as PL_DHashTableOperate never returns a michael@0: * non-live, busy (i.e., removed) entry pointer to its caller. See below for michael@0: * more details on PL_DHashTableOperate's calling rules. michael@0: */ michael@0: struct PLDHashEntryHdr { michael@0: PLDHashNumber keyHash; /* every entry must begin like this */ michael@0: }; michael@0: michael@0: MOZ_ALWAYS_INLINE bool michael@0: PL_DHASH_ENTRY_IS_FREE(PLDHashEntryHdr* entry) michael@0: { michael@0: return entry->keyHash == 0; michael@0: } michael@0: michael@0: MOZ_ALWAYS_INLINE bool michael@0: PL_DHASH_ENTRY_IS_BUSY(PLDHashEntryHdr* entry) michael@0: { michael@0: return !PL_DHASH_ENTRY_IS_FREE(entry); michael@0: } michael@0: michael@0: MOZ_ALWAYS_INLINE bool michael@0: PL_DHASH_ENTRY_IS_LIVE(PLDHashEntryHdr* entry) michael@0: { michael@0: return entry->keyHash >= 2; michael@0: } michael@0: michael@0: /* michael@0: * A PLDHashTable is currently 8 words (without the PL_DHASHMETER overhead) michael@0: * on most architectures, and may be allocated on the stack or within another michael@0: * structure or class (see below for the Init and Finish functions to use). michael@0: * michael@0: * To decide whether to use double hashing vs. chaining, we need to develop a michael@0: * trade-off relation, as follows: michael@0: * michael@0: * Let alpha be the load factor, esize the entry size in words, count the michael@0: * entry count, and pow2 the power-of-two table size in entries. michael@0: * michael@0: * (PLDHashTable overhead) > (PLHashTable overhead) michael@0: * (unused table entry space) > (malloc and .next overhead per entry) + michael@0: * (buckets overhead) michael@0: * (1 - alpha) * esize * pow2 > 2 * count + pow2 michael@0: * michael@0: * Notice that alpha is by definition (count / pow2): michael@0: * michael@0: * (1 - alpha) * esize * pow2 > 2 * alpha * pow2 + pow2 michael@0: * (1 - alpha) * esize > 2 * alpha + 1 michael@0: * michael@0: * esize > (1 + 2 * alpha) / (1 - alpha) michael@0: * michael@0: * This assumes both tables must keep keyHash, key, and value for each entry, michael@0: * where key and value point to separately allocated strings or structures. michael@0: * If key and value can be combined into one pointer, then the trade-off is: michael@0: * michael@0: * esize > (1 + 3 * alpha) / (1 - alpha) michael@0: * michael@0: * If the entry value can be a subtype of PLDHashEntryHdr, rather than a type michael@0: * that must be allocated separately and referenced by an entry.value pointer michael@0: * member, and provided key's allocation can be fused with its entry's, then michael@0: * k (the words wasted per entry with chaining) is 4. michael@0: * michael@0: * To see these curves, feed gnuplot input like so: michael@0: * michael@0: * gnuplot> f(x,k) = (1 + k * x) / (1 - x) michael@0: * gnuplot> plot [0:.75] f(x,2), f(x,3), f(x,4) michael@0: * michael@0: * For k of 2 and a well-loaded table (alpha > .5), esize must be more than 4 michael@0: * words for chaining to be more space-efficient than double hashing. michael@0: * michael@0: * Solving for alpha helps us decide when to shrink an underloaded table: michael@0: * michael@0: * esize > (1 + k * alpha) / (1 - alpha) michael@0: * esize - alpha * esize > 1 + k * alpha michael@0: * esize - 1 > (k + esize) * alpha michael@0: * (esize - 1) / (k + esize) > alpha michael@0: * michael@0: * alpha < (esize - 1) / (esize + k) michael@0: * michael@0: * Therefore double hashing should keep alpha >= (esize - 1) / (esize + k), michael@0: * assuming esize is not too large (in which case, chaining should probably be michael@0: * used for any alpha). For esize=2 and k=3, we want alpha >= .2; for esize=3 michael@0: * and k=2, we want alpha >= .4. For k=4, esize could be 6, and alpha >= .5 michael@0: * would still obtain. michael@0: * michael@0: * The current implementation uses a configurable lower bound on alpha, which michael@0: * defaults to .25, when deciding to shrink the table (while still respecting michael@0: * PL_DHASH_MIN_SIZE). michael@0: * michael@0: * Note a qualitative difference between chaining and double hashing: under michael@0: * chaining, entry addresses are stable across table shrinks and grows. With michael@0: * double hashing, you can't safely hold an entry pointer and use it after an michael@0: * ADD or REMOVE operation, unless you sample table->generation before adding michael@0: * or removing, and compare the sample after, dereferencing the entry pointer michael@0: * only if table->generation has not changed. michael@0: * michael@0: * The moral of this story: there is no one-size-fits-all hash table scheme, michael@0: * but for small table entry size, and assuming entry address stability is not michael@0: * required, double hashing wins. michael@0: */ michael@0: struct PLDHashTable { michael@0: const PLDHashTableOps *ops; /* virtual operations, see below */ michael@0: void *data; /* ops- and instance-specific data */ michael@0: int16_t hashShift; /* multiplicative hash shift */ michael@0: /* michael@0: * |recursionLevel| is only used in debug builds, but is present in opt michael@0: * builds to avoid binary compatibility problems when mixing DEBUG and michael@0: * non-DEBUG components. (Actually, even if it were removed, michael@0: * sizeof(PLDHashTable) wouldn't change, due to struct padding.) michael@0: */ michael@0: uint16_t recursionLevel; /* used to detect unsafe re-entry */ michael@0: uint32_t entrySize; /* number of bytes in an entry */ michael@0: uint32_t entryCount; /* number of entries in table */ michael@0: uint32_t removedCount; /* removed entry sentinels in table */ michael@0: uint32_t generation; /* entry storage generation number */ michael@0: char *entryStore; /* entry storage */ michael@0: #ifdef PL_DHASHMETER michael@0: struct PLDHashStats { michael@0: uint32_t searches; /* total number of table searches */ michael@0: uint32_t steps; /* hash chain links traversed */ michael@0: uint32_t hits; /* searches that found key */ michael@0: uint32_t misses; /* searches that didn't find key */ michael@0: uint32_t lookups; /* number of PL_DHASH_LOOKUPs */ michael@0: uint32_t addMisses; /* adds that miss, and do work */ michael@0: uint32_t addOverRemoved; /* adds that recycled a removed entry */ michael@0: uint32_t addHits; /* adds that hit an existing entry */ michael@0: uint32_t addFailures; /* out-of-memory during add growth */ michael@0: uint32_t removeHits; /* removes that hit, and do work */ michael@0: uint32_t removeMisses; /* useless removes that miss */ michael@0: uint32_t removeFrees; /* removes that freed entry directly */ michael@0: uint32_t removeEnums; /* removes done by Enumerate */ michael@0: uint32_t grows; /* table expansions */ michael@0: uint32_t shrinks; /* table contractions */ michael@0: uint32_t compresses; /* table compressions */ michael@0: uint32_t enumShrinks; /* contractions after Enumerate */ michael@0: } stats; michael@0: #endif michael@0: }; michael@0: michael@0: /* michael@0: * Size in entries (gross, not net of free and removed sentinels) for table. michael@0: * We store hashShift rather than sizeLog2 to optimize the collision-free case michael@0: * in SearchTable. michael@0: */ michael@0: #define PL_DHASH_TABLE_SIZE(table) \ michael@0: ((uint32_t)1 << (PL_DHASH_BITS - (table)->hashShift)) michael@0: michael@0: /* michael@0: * Table space at entryStore is allocated and freed using these callbacks. michael@0: * The allocator should return null on error only (not if called with nbytes michael@0: * equal to 0; but note that pldhash.c code will never call with 0 nbytes). michael@0: */ michael@0: typedef void * michael@0: (* PLDHashAllocTable)(PLDHashTable *table, uint32_t nbytes); michael@0: michael@0: typedef void michael@0: (* PLDHashFreeTable) (PLDHashTable *table, void *ptr); michael@0: michael@0: /* michael@0: * Compute the hash code for a given key to be looked up, added, or removed michael@0: * from table. A hash code may have any PLDHashNumber value. michael@0: */ michael@0: typedef PLDHashNumber michael@0: (* PLDHashHashKey) (PLDHashTable *table, const void *key); michael@0: michael@0: /* michael@0: * Compare the key identifying entry in table with the provided key parameter. michael@0: * Return true if keys match, false otherwise. michael@0: */ michael@0: typedef bool michael@0: (* PLDHashMatchEntry)(PLDHashTable *table, const PLDHashEntryHdr *entry, michael@0: const void *key); michael@0: michael@0: /* michael@0: * Copy the data starting at from to the new entry storage at to. Do not add michael@0: * reference counts for any strong references in the entry, however, as this michael@0: * is a "move" operation: the old entry storage at from will be freed without michael@0: * any reference-decrementing callback shortly. michael@0: */ michael@0: typedef void michael@0: (* PLDHashMoveEntry)(PLDHashTable *table, const PLDHashEntryHdr *from, michael@0: PLDHashEntryHdr *to); michael@0: michael@0: /* michael@0: * Clear the entry and drop any strong references it holds. This callback is michael@0: * invoked during a PL_DHASH_REMOVE operation (see below for operation codes), michael@0: * but only if the given key is found in the table. michael@0: */ michael@0: typedef void michael@0: (* PLDHashClearEntry)(PLDHashTable *table, PLDHashEntryHdr *entry); michael@0: michael@0: /* michael@0: * Called when a table (whether allocated dynamically by itself, or nested in michael@0: * a larger structure, or allocated on the stack) is finished. This callback michael@0: * allows table->ops-specific code to finalize table->data. michael@0: */ michael@0: typedef void michael@0: (* PLDHashFinalize) (PLDHashTable *table); michael@0: michael@0: /* michael@0: * Initialize a new entry, apart from keyHash. This function is called when michael@0: * PL_DHashTableOperate's PL_DHASH_ADD case finds no existing entry for the michael@0: * given key, and must add a new one. At that point, entry->keyHash is not michael@0: * set yet, to avoid claiming the last free entry in a severely overloaded michael@0: * table. michael@0: */ michael@0: typedef bool michael@0: (* PLDHashInitEntry)(PLDHashTable *table, PLDHashEntryHdr *entry, michael@0: const void *key); michael@0: michael@0: /* michael@0: * Finally, the "vtable" structure for PLDHashTable. The first eight hooks michael@0: * must be provided by implementations; they're called unconditionally by the michael@0: * generic pldhash.c code. Hooks after these may be null. michael@0: * michael@0: * Summary of allocation-related hook usage with C++ placement new emphasis: michael@0: * allocTable Allocate raw bytes with malloc, no ctors run. michael@0: * freeTable Free raw bytes with free, no dtors run. michael@0: * initEntry Call placement new using default key-based ctor. michael@0: * Return true on success, false on error. michael@0: * moveEntry Call placement new using copy ctor, run dtor on old michael@0: * entry storage. michael@0: * clearEntry Run dtor on entry. michael@0: * finalize Stub unless table->data was initialized and needs to michael@0: * be finalized. michael@0: * michael@0: * Note the reason why initEntry is optional: the default hooks (stubs) clear michael@0: * entry storage: On successful PL_DHashTableOperate(tbl, key, PL_DHASH_ADD), michael@0: * the returned entry pointer addresses an entry struct whose keyHash member michael@0: * has been set non-zero, but all other entry members are still clear (null). michael@0: * PL_DHASH_ADD callers can test such members to see whether the entry was michael@0: * newly created by the PL_DHASH_ADD call that just succeeded. If placement michael@0: * new or similar initialization is required, define an initEntry hook. Of michael@0: * course, the clearEntry hook must zero or null appropriately. michael@0: * michael@0: * XXX assumes 0 is null for pointer types. michael@0: */ michael@0: struct PLDHashTableOps { michael@0: /* Mandatory hooks. All implementations must provide these. */ michael@0: PLDHashAllocTable allocTable; michael@0: PLDHashFreeTable freeTable; michael@0: PLDHashHashKey hashKey; michael@0: PLDHashMatchEntry matchEntry; michael@0: PLDHashMoveEntry moveEntry; michael@0: PLDHashClearEntry clearEntry; michael@0: PLDHashFinalize finalize; michael@0: michael@0: /* Optional hooks start here. If null, these are not called. */ michael@0: PLDHashInitEntry initEntry; michael@0: }; michael@0: michael@0: /* michael@0: * Default implementations for the above ops. michael@0: */ michael@0: NS_COM_GLUE void * michael@0: PL_DHashAllocTable(PLDHashTable *table, uint32_t nbytes); michael@0: michael@0: NS_COM_GLUE void michael@0: PL_DHashFreeTable(PLDHashTable *table, void *ptr); michael@0: michael@0: NS_COM_GLUE PLDHashNumber michael@0: PL_DHashStringKey(PLDHashTable *table, const void *key); michael@0: michael@0: /* A minimal entry contains a keyHash header and a void key pointer. */ michael@0: struct PLDHashEntryStub { michael@0: PLDHashEntryHdr hdr; michael@0: const void *key; michael@0: }; michael@0: michael@0: NS_COM_GLUE PLDHashNumber michael@0: PL_DHashVoidPtrKeyStub(PLDHashTable *table, const void *key); michael@0: michael@0: NS_COM_GLUE bool michael@0: PL_DHashMatchEntryStub(PLDHashTable *table, michael@0: const PLDHashEntryHdr *entry, michael@0: const void *key); michael@0: michael@0: NS_COM_GLUE bool michael@0: PL_DHashMatchStringKey(PLDHashTable *table, michael@0: const PLDHashEntryHdr *entry, michael@0: const void *key); michael@0: michael@0: NS_COM_GLUE void michael@0: PL_DHashMoveEntryStub(PLDHashTable *table, michael@0: const PLDHashEntryHdr *from, michael@0: PLDHashEntryHdr *to); michael@0: michael@0: NS_COM_GLUE void michael@0: PL_DHashClearEntryStub(PLDHashTable *table, PLDHashEntryHdr *entry); michael@0: michael@0: NS_COM_GLUE void michael@0: PL_DHashFreeStringKey(PLDHashTable *table, PLDHashEntryHdr *entry); michael@0: michael@0: NS_COM_GLUE void michael@0: PL_DHashFinalizeStub(PLDHashTable *table); michael@0: michael@0: /* michael@0: * If you use PLDHashEntryStub or a subclass of it as your entry struct, and michael@0: * if your entries move via memcpy and clear via memset(0), you can use these michael@0: * stub operations. michael@0: */ michael@0: NS_COM_GLUE const PLDHashTableOps * michael@0: PL_DHashGetStubOps(void); michael@0: michael@0: /* michael@0: * Dynamically allocate a new PLDHashTable using malloc, initialize it using michael@0: * PL_DHashTableInit, and return its address. Return null on malloc failure. michael@0: * Note that the entry storage at table->entryStore will be allocated using michael@0: * the ops->allocTable callback. michael@0: */ michael@0: NS_COM_GLUE PLDHashTable * michael@0: PL_NewDHashTable(const PLDHashTableOps *ops, void *data, uint32_t entrySize, michael@0: uint32_t capacity); michael@0: michael@0: /* michael@0: * Finalize table's data, free its entry storage (via table->ops->freeTable), michael@0: * and return the memory starting at table to the malloc heap. michael@0: */ michael@0: NS_COM_GLUE void michael@0: PL_DHashTableDestroy(PLDHashTable *table); michael@0: michael@0: /* michael@0: * Initialize table with ops, data, entrySize, and capacity. Capacity is a michael@0: * guess for the smallest table size at which the table will usually be less michael@0: * than 75% loaded (the table will grow or shrink as needed; capacity serves michael@0: * only to avoid inevitable early growth from PL_DHASH_MIN_SIZE). This will michael@0: * crash if it can't allocate enough memory, or if entrySize or capacity are michael@0: * too large. michael@0: */ michael@0: NS_COM_GLUE void michael@0: PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops, void *data, michael@0: uint32_t entrySize, uint32_t capacity); michael@0: michael@0: /* michael@0: * Initialize table. This is the same as PL_DHashTableInit, except that it michael@0: * returns a boolean indicating success, rather than crashing on failure. michael@0: */ michael@0: NS_COM_GLUE bool michael@0: PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops, void *data, michael@0: uint32_t entrySize, uint32_t capacity, michael@0: const mozilla::fallible_t& ) MOZ_WARN_UNUSED_RESULT; michael@0: michael@0: /* michael@0: * Finalize table's data, free its entry storage using table->ops->freeTable, michael@0: * and leave its members unchanged from their last live values (which leaves michael@0: * pointers dangling). If you want to burn cycles clearing table, it's up to michael@0: * your code to call memset. michael@0: */ michael@0: NS_COM_GLUE void michael@0: PL_DHashTableFinish(PLDHashTable *table); michael@0: michael@0: /* michael@0: * To consolidate keyHash computation and table grow/shrink code, we use a michael@0: * single entry point for lookup, add, and remove operations. The operation michael@0: * codes are declared here, along with codes returned by PLDHashEnumerator michael@0: * functions, which control PL_DHashTableEnumerate's behavior. michael@0: */ michael@0: typedef enum PLDHashOperator { michael@0: PL_DHASH_LOOKUP = 0, /* lookup entry */ michael@0: PL_DHASH_ADD = 1, /* add entry */ michael@0: PL_DHASH_REMOVE = 2, /* remove entry, or enumerator says remove */ michael@0: PL_DHASH_NEXT = 0, /* enumerator says continue */ michael@0: PL_DHASH_STOP = 1 /* enumerator says stop */ michael@0: } PLDHashOperator; michael@0: michael@0: /* michael@0: * To lookup a key in table, call: michael@0: * michael@0: * entry = PL_DHashTableOperate(table, key, PL_DHASH_LOOKUP); michael@0: * michael@0: * If PL_DHASH_ENTRY_IS_BUSY(entry) is true, key was found and it identifies michael@0: * entry. If PL_DHASH_ENTRY_IS_FREE(entry) is true, key was not found. michael@0: * michael@0: * To add an entry identified by key to table, call: michael@0: * michael@0: * entry = PL_DHashTableOperate(table, key, PL_DHASH_ADD); michael@0: * michael@0: * If entry is null upon return, then either the table is severely overloaded, michael@0: * and memory can't be allocated for entry storage via table->ops->allocTable; michael@0: * Or if table->ops->initEntry is non-null, the table->ops->initEntry op may michael@0: * have returned false. michael@0: * michael@0: * Otherwise, entry->keyHash has been set so that PL_DHASH_ENTRY_IS_BUSY(entry) michael@0: * is true, and it is up to the caller to initialize the key and value parts michael@0: * of the entry sub-type, if they have not been set already (i.e. if entry was michael@0: * not already in the table, and if the optional initEntry hook was not used). michael@0: * michael@0: * To remove an entry identified by key from table, call: michael@0: * michael@0: * (void) PL_DHashTableOperate(table, key, PL_DHASH_REMOVE); michael@0: * michael@0: * If key's entry is found, it is cleared (via table->ops->clearEntry) and michael@0: * the entry is marked so that PL_DHASH_ENTRY_IS_FREE(entry). This operation michael@0: * returns null unconditionally; you should ignore its return value. michael@0: */ michael@0: NS_COM_GLUE PLDHashEntryHdr * PL_DHASH_FASTCALL michael@0: PL_DHashTableOperate(PLDHashTable *table, const void *key, PLDHashOperator op); michael@0: michael@0: /* michael@0: * Remove an entry already accessed via LOOKUP or ADD. michael@0: * michael@0: * NB: this is a "raw" or low-level routine, intended to be used only where michael@0: * the inefficiency of a full PL_DHashTableOperate (which rehashes in order michael@0: * to find the entry given its key) is not tolerable. This function does not michael@0: * shrink the table if it is underloaded. It does not update stats #ifdef michael@0: * PL_DHASHMETER, either. michael@0: */ michael@0: NS_COM_GLUE void michael@0: PL_DHashTableRawRemove(PLDHashTable *table, PLDHashEntryHdr *entry); michael@0: michael@0: /* michael@0: * Enumerate entries in table using etor: michael@0: * michael@0: * count = PL_DHashTableEnumerate(table, etor, arg); michael@0: * michael@0: * PL_DHashTableEnumerate calls etor like so: michael@0: * michael@0: * op = etor(table, entry, number, arg); michael@0: * michael@0: * where number is a zero-based ordinal assigned to live entries according to michael@0: * their order in table->entryStore. michael@0: * michael@0: * The return value, op, is treated as a set of flags. If op is PL_DHASH_NEXT, michael@0: * then continue enumerating. If op contains PL_DHASH_REMOVE, then clear (via michael@0: * table->ops->clearEntry) and free entry. Then we check whether op contains michael@0: * PL_DHASH_STOP; if so, stop enumerating and return the number of live entries michael@0: * that were enumerated so far. Return the total number of live entries when michael@0: * enumeration completes normally. michael@0: * michael@0: * If etor calls PL_DHashTableOperate on table with op != PL_DHASH_LOOKUP, it michael@0: * must return PL_DHASH_STOP; otherwise undefined behavior results. michael@0: * michael@0: * If any enumerator returns PL_DHASH_REMOVE, table->entryStore may be shrunk michael@0: * or compressed after enumeration, but before PL_DHashTableEnumerate returns. michael@0: * Such an enumerator therefore can't safely set aside entry pointers, but an michael@0: * enumerator that never returns PL_DHASH_REMOVE can set pointers to entries michael@0: * aside, e.g., to avoid copying live entries into an array of the entry type. michael@0: * Copying entry pointers is cheaper, and safe so long as the caller of such a michael@0: * "stable" Enumerate doesn't use the set-aside pointers after any call either michael@0: * to PL_DHashTableOperate, or to an "unstable" form of Enumerate, which might michael@0: * grow or shrink entryStore. michael@0: * michael@0: * If your enumerator wants to remove certain entries, but set aside pointers michael@0: * to other entries that it retains, it can use PL_DHashTableRawRemove on the michael@0: * entries to be removed, returning PL_DHASH_NEXT to skip them. Likewise, if michael@0: * you want to remove entries, but for some reason you do not want entryStore michael@0: * to be shrunk or compressed, you can call PL_DHashTableRawRemove safely on michael@0: * the entry being enumerated, rather than returning PL_DHASH_REMOVE. michael@0: */ michael@0: typedef PLDHashOperator michael@0: (* PLDHashEnumerator)(PLDHashTable *table, PLDHashEntryHdr *hdr, uint32_t number, michael@0: void *arg); michael@0: michael@0: NS_COM_GLUE uint32_t michael@0: PL_DHashTableEnumerate(PLDHashTable *table, PLDHashEnumerator etor, void *arg); michael@0: michael@0: typedef size_t michael@0: (* PLDHashSizeOfEntryExcludingThisFun)(PLDHashEntryHdr *hdr, michael@0: mozilla::MallocSizeOf mallocSizeOf, michael@0: void *arg); michael@0: michael@0: /** michael@0: * Measure the size of the table's entry storage, and if michael@0: * |sizeOfEntryExcludingThis| is non-nullptr, measure the size of things michael@0: * pointed to by entries. Doesn't measure |ops| because it's often shared michael@0: * between tables, nor |data| because it's opaque. michael@0: */ michael@0: NS_COM_GLUE size_t michael@0: PL_DHashTableSizeOfExcludingThis(const PLDHashTable *table, michael@0: PLDHashSizeOfEntryExcludingThisFun sizeOfEntryExcludingThis, michael@0: mozilla::MallocSizeOf mallocSizeOf, michael@0: void *arg = nullptr); michael@0: michael@0: /** michael@0: * Like PL_DHashTableSizeOfExcludingThis, but includes sizeof(*this). michael@0: */ michael@0: NS_COM_GLUE size_t michael@0: PL_DHashTableSizeOfIncludingThis(const PLDHashTable *table, michael@0: PLDHashSizeOfEntryExcludingThisFun sizeOfEntryExcludingThis, michael@0: mozilla::MallocSizeOf mallocSizeOf, michael@0: void *arg = nullptr); michael@0: michael@0: #ifdef DEBUG michael@0: /** michael@0: * Mark a table as immutable for the remainder of its lifetime. This michael@0: * changes the implementation from ASSERTing one set of invariants to michael@0: * ASSERTing a different set. michael@0: * michael@0: * When a table is NOT marked as immutable, the table implementation michael@0: * asserts that the table is not mutated from its own callbacks. It michael@0: * assumes the caller protects the table from being accessed on multiple michael@0: * threads simultaneously. michael@0: * michael@0: * When the table is marked as immutable, the re-entry assertions will michael@0: * no longer trigger erroneously due to multi-threaded access. Instead, michael@0: * mutations will cause assertions. michael@0: */ michael@0: NS_COM_GLUE void michael@0: PL_DHashMarkTableImmutable(PLDHashTable *table); michael@0: #endif michael@0: michael@0: #ifdef PL_DHASHMETER michael@0: #include michael@0: michael@0: NS_COM_GLUE void michael@0: PL_DHashTableDumpMeter(PLDHashTable *table, PLDHashEnumerator dump, FILE *fp); michael@0: #endif michael@0: michael@0: #endif /* pldhash_h___ */