| 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 <[email protected]> (Original Author)
|
|---|
| 24 | *
|
|---|
| 25 | * Alternatively, the contents of this file may be used under the terms of
|
|---|
| 26 | * either of the GNU General Public License Version 2 or later (the "GPL"),
|
|---|
| 27 | * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
|
|---|
| 28 | * in which case the provisions of the GPL or the LGPL are applicable instead
|
|---|
| 29 | * of those above. If you wish to allow use of your version of this file only
|
|---|
| 30 | * under the terms of either the GPL or the LGPL, and not to allow others to
|
|---|
| 31 | * use your version of this file under the terms of the MPL, indicate your
|
|---|
| 32 | * decision by deleting the provisions above and replace them with the notice
|
|---|
| 33 | * and other provisions required by the GPL or the LGPL. If you do not delete
|
|---|
| 34 | * the provisions above, a recipient may use your version of this file under
|
|---|
| 35 | * the terms of any one of the MPL, the GPL or the LGPL.
|
|---|
| 36 | *
|
|---|
| 37 | * ***** END LICENSE BLOCK ***** */
|
|---|
| 38 |
|
|---|
| 39 | #ifndef pldhash_h___
|
|---|
| 40 | #define pldhash_h___
|
|---|
| 41 | /*
|
|---|
| 42 | * Double hashing, a la Knuth 6.
|
|---|
| 43 | * GENERATED BY js/src/plify_jsdhash.sed -- DO NOT EDIT!!!
|
|---|
| 44 | */
|
|---|
| 45 | #include "prtypes.h"
|
|---|
| 46 |
|
|---|
| 47 | #ifdef VBOX_WITH_XPCOM_NAMESPACE_CLEANUP
|
|---|
| 48 | #define PL_DHashTableInit VBoxNsplPL_DHashTableInit
|
|---|
| 49 | #define PL_DHashTableFinish VBoxNsplPL_DHashTableFinish
|
|---|
| 50 | #define PL_DHashTableOperate VBoxNsplPL_DHashTableOperate
|
|---|
| 51 | #define PL_DHashTableEnumerate VBoxNsplPL_DHashTableEnumerate
|
|---|
| 52 | #define PL_DHashAllocTable VBoxNsplPL_DHashAllocTable
|
|---|
| 53 | #define PL_DHashFreeTable VBoxNsplPL_DHashFreeTable
|
|---|
| 54 | #define PL_DHashMoveEntryStub VBoxNsplPL_DHashMoveEntryStub
|
|---|
| 55 | #define PL_DHashFinalizeStub VBoxNsplPL_DHashFinalizeStub
|
|---|
| 56 | #define PL_DHashClearEntryStub VBoxNsplPL_DHashClearEntryStub
|
|---|
| 57 | #define PL_DHashFreeStringKey VBoxNsplPL_DHashFreeStringKey
|
|---|
| 58 | #define PL_DHashGetKeyStub VBoxNsplPL_DHashGetKeyStub
|
|---|
| 59 | #define PL_DHashGetStubOps VBoxNsplPL_DHashGetStubOps
|
|---|
| 60 | #define PL_DHashMatchEntryStub VBoxNsplPL_DHashMatchEntryStub
|
|---|
| 61 | #define PL_DHashMatchStringKey VBoxNsplPL_DHashMatchStringKey
|
|---|
| 62 | #define PL_DHashStringKey VBoxNsplPL_DHashStringKey
|
|---|
| 63 | #define PL_DHashTableDestroy VBoxNsplPL_DHashTableDestroy
|
|---|
| 64 | #define PL_DHashTableRawRemove VBoxNsplPL_DHashTableRawRemove
|
|---|
| 65 | #define PL_DHashTableSetAlphaBounds VBoxNsplPL_DHashTableSetAlphaBounds
|
|---|
| 66 | #define PL_DHashVoidPtrKeyStub VBoxNsplPL_DHashVoidPtrKeyStub
|
|---|
| 67 | #define PL_NewDHashTable VBoxNsplPL_NewDHashTable
|
|---|
| 68 | #endif /* VBOX_WITH_XPCOM_NAMESPACE_CLEANUP */
|
|---|
| 69 |
|
|---|
| 70 | PR_BEGIN_EXTERN_C
|
|---|
| 71 |
|
|---|
| 72 | #ifdef DEBUG_XXXbrendan
|
|---|
| 73 | #define PL_DHASHMETER 1
|
|---|
| 74 | #endif
|
|---|
| 75 |
|
|---|
| 76 | #if defined(__GNUC__) && defined(__i386__) && (__GNUC__ >= 3) && !defined(XP_OS2)
|
|---|
| 77 | #define PL_DHASH_FASTCALL __attribute__ ((regparm (3),stdcall))
|
|---|
| 78 | #else
|
|---|
| 79 | #define PL_DHASH_FASTCALL
|
|---|
| 80 | #endif
|
|---|
| 81 |
|
|---|
| 82 | /* Table size limit, do not equal or exceed (see min&maxAlphaFrac, below). */
|
|---|
| 83 | #undef PL_DHASH_SIZE_LIMIT
|
|---|
| 84 | #define PL_DHASH_SIZE_LIMIT PR_BIT(24)
|
|---|
| 85 |
|
|---|
| 86 | /* Minimum table size, or gross entry count (net is at most .75 loaded). */
|
|---|
| 87 | #ifndef PL_DHASH_MIN_SIZE
|
|---|
| 88 | #define PL_DHASH_MIN_SIZE 16
|
|---|
| 89 | #elif (PL_DHASH_MIN_SIZE & (PL_DHASH_MIN_SIZE - 1)) != 0
|
|---|
| 90 | #error "PL_DHASH_MIN_SIZE must be a power of two!"
|
|---|
| 91 | #endif
|
|---|
| 92 |
|
|---|
| 93 | /*
|
|---|
| 94 | * Multiplicative hash uses an unsigned 32 bit integer and the golden ratio,
|
|---|
| 95 | * expressed as a fixed-point 32-bit fraction.
|
|---|
| 96 | */
|
|---|
| 97 | #define PL_DHASH_BITS 32
|
|---|
| 98 | #define PL_DHASH_GOLDEN_RATIO 0x9E3779B9U
|
|---|
| 99 |
|
|---|
| 100 | /* Primitive and forward-struct typedefs. */
|
|---|
| 101 | typedef PRUint32 PLDHashNumber;
|
|---|
| 102 | typedef struct PLDHashEntryHdr PLDHashEntryHdr;
|
|---|
| 103 | typedef struct PLDHashEntryStub PLDHashEntryStub;
|
|---|
| 104 | typedef struct PLDHashTable PLDHashTable;
|
|---|
| 105 | typedef struct PLDHashTableOps PLDHashTableOps;
|
|---|
| 106 |
|
|---|
| 107 | /*
|
|---|
| 108 | * Table entry header structure.
|
|---|
| 109 | *
|
|---|
| 110 | * In order to allow in-line allocation of key and value, we do not declare
|
|---|
| 111 | * either here. Instead, the API uses const void *key as a formal parameter,
|
|---|
| 112 | * and asks each entry for its key when necessary via a getKey callback, used
|
|---|
| 113 | * when growing or shrinking the table. Other callback types are defined
|
|---|
| 114 | * below and grouped into the PLDHashTableOps structure, for single static
|
|---|
| 115 | * initialization per hash table sub-type.
|
|---|
| 116 | *
|
|---|
| 117 | * Each hash table sub-type should nest the PLDHashEntryHdr structure at the
|
|---|
| 118 | * front of its particular entry type. The keyHash member contains the result
|
|---|
| 119 | * of multiplying the hash code returned from the hashKey callback (see below)
|
|---|
| 120 | * by PL_DHASH_GOLDEN_RATIO, then constraining the result to avoid the magic 0
|
|---|
| 121 | * and 1 values. The stored keyHash value is table size invariant, and it is
|
|---|
| 122 | * maintained automatically by PL_DHashTableOperate -- users should never set
|
|---|
| 123 | * it, and its only uses should be via the entry macros below.
|
|---|
| 124 | *
|
|---|
| 125 | * The PL_DHASH_ENTRY_IS_LIVE macro tests whether entry is neither free nor
|
|---|
| 126 | * removed. An entry may be either busy or free; if busy, it may be live or
|
|---|
| 127 | * removed. Consumers of this API should not access members of entries that
|
|---|
| 128 | * are not live.
|
|---|
| 129 | *
|
|---|
| 130 | * However, use PL_DHASH_ENTRY_IS_BUSY for faster liveness testing of entries
|
|---|
| 131 | * returned by PL_DHashTableOperate, as PL_DHashTableOperate never returns a
|
|---|
| 132 | * non-live, busy (i.e., removed) entry pointer to its caller. See below for
|
|---|
| 133 | * more details on PL_DHashTableOperate's calling rules.
|
|---|
| 134 | */
|
|---|
| 135 | struct PLDHashEntryHdr {
|
|---|
| 136 | PLDHashNumber keyHash; /* every entry must begin like this */
|
|---|
| 137 | };
|
|---|
| 138 |
|
|---|
| 139 | #define PL_DHASH_ENTRY_IS_FREE(entry) ((entry)->keyHash == 0)
|
|---|
| 140 | #define PL_DHASH_ENTRY_IS_BUSY(entry) (!PL_DHASH_ENTRY_IS_FREE(entry))
|
|---|
| 141 | #define PL_DHASH_ENTRY_IS_LIVE(entry) ((entry)->keyHash >= 2)
|
|---|
| 142 |
|
|---|
| 143 | /*
|
|---|
| 144 | * A PLDHashTable is currently 8 words (without the PL_DHASHMETER overhead)
|
|---|
| 145 | * on most architectures, and may be allocated on the stack or within another
|
|---|
| 146 | * structure or class (see below for the Init and Finish functions to use).
|
|---|
| 147 | *
|
|---|
| 148 | * To decide whether to use double hashing vs. chaining, we need to develop a
|
|---|
| 149 | * trade-off relation, as follows:
|
|---|
| 150 | *
|
|---|
| 151 | * Let alpha be the load factor, esize the entry size in words, count the
|
|---|
| 152 | * entry count, and pow2 the power-of-two table size in entries.
|
|---|
| 153 | *
|
|---|
| 154 | * (PLDHashTable overhead) > (PLHashTable overhead)
|
|---|
| 155 | * (unused table entry space) > (malloc and .next overhead per entry) +
|
|---|
| 156 | * (buckets overhead)
|
|---|
| 157 | * (1 - alpha) * esize * pow2 > 2 * count + pow2
|
|---|
| 158 | *
|
|---|
| 159 | * Notice that alpha is by definition (count / pow2):
|
|---|
| 160 | *
|
|---|
| 161 | * (1 - alpha) * esize * pow2 > 2 * alpha * pow2 + pow2
|
|---|
| 162 | * (1 - alpha) * esize > 2 * alpha + 1
|
|---|
| 163 | *
|
|---|
| 164 | * esize > (1 + 2 * alpha) / (1 - alpha)
|
|---|
| 165 | *
|
|---|
| 166 | * This assumes both tables must keep keyHash, key, and value for each entry,
|
|---|
| 167 | * where key and value point to separately allocated strings or structures.
|
|---|
| 168 | * If key and value can be combined into one pointer, then the trade-off is:
|
|---|
| 169 | *
|
|---|
| 170 | * esize > (1 + 3 * alpha) / (1 - alpha)
|
|---|
| 171 | *
|
|---|
| 172 | * If the entry value can be a subtype of PLDHashEntryHdr, rather than a type
|
|---|
| 173 | * that must be allocated separately and referenced by an entry.value pointer
|
|---|
| 174 | * member, and provided key's allocation can be fused with its entry's, then
|
|---|
| 175 | * k (the words wasted per entry with chaining) is 4.
|
|---|
| 176 | *
|
|---|
| 177 | * To see these curves, feed gnuplot input like so:
|
|---|
| 178 | *
|
|---|
| 179 | * gnuplot> f(x,k) = (1 + k * x) / (1 - x)
|
|---|
| 180 | * gnuplot> plot [0:.75] f(x,2), f(x,3), f(x,4)
|
|---|
| 181 | *
|
|---|
| 182 | * For k of 2 and a well-loaded table (alpha > .5), esize must be more than 4
|
|---|
| 183 | * words for chaining to be more space-efficient than double hashing.
|
|---|
| 184 | *
|
|---|
| 185 | * Solving for alpha helps us decide when to shrink an underloaded table:
|
|---|
| 186 | *
|
|---|
| 187 | * esize > (1 + k * alpha) / (1 - alpha)
|
|---|
| 188 | * esize - alpha * esize > 1 + k * alpha
|
|---|
| 189 | * esize - 1 > (k + esize) * alpha
|
|---|
| 190 | * (esize - 1) / (k + esize) > alpha
|
|---|
| 191 | *
|
|---|
| 192 | * alpha < (esize - 1) / (esize + k)
|
|---|
| 193 | *
|
|---|
| 194 | * Therefore double hashing should keep alpha >= (esize - 1) / (esize + k),
|
|---|
| 195 | * assuming esize is not too large (in which case, chaining should probably be
|
|---|
| 196 | * used for any alpha). For esize=2 and k=3, we want alpha >= .2; for esize=3
|
|---|
| 197 | * and k=2, we want alpha >= .4. For k=4, esize could be 6, and alpha >= .5
|
|---|
| 198 | * would still obtain. See the PL_DHASH_MIN_ALPHA macro further below.
|
|---|
| 199 | *
|
|---|
| 200 | * The current implementation uses a configurable lower bound on alpha, which
|
|---|
| 201 | * defaults to .25, when deciding to shrink the table (while still respecting
|
|---|
| 202 | * PL_DHASH_MIN_SIZE).
|
|---|
| 203 | *
|
|---|
| 204 | * Note a qualitative difference between chaining and double hashing: under
|
|---|
| 205 | * chaining, entry addresses are stable across table shrinks and grows. With
|
|---|
| 206 | * double hashing, you can't safely hold an entry pointer and use it after an
|
|---|
| 207 | * ADD or REMOVE operation, unless you sample table->generation before adding
|
|---|
| 208 | * or removing, and compare the sample after, dereferencing the entry pointer
|
|---|
| 209 | * only if table->generation has not changed.
|
|---|
| 210 | *
|
|---|
| 211 | * The moral of this story: there is no one-size-fits-all hash table scheme,
|
|---|
| 212 | * but for small table entry size, and assuming entry address stability is not
|
|---|
| 213 | * required, double hashing wins.
|
|---|
| 214 | */
|
|---|
| 215 | struct PLDHashTable {
|
|---|
| 216 | const PLDHashTableOps *ops; /* virtual operations, see below */
|
|---|
| 217 | void *data; /* ops- and instance-specific data */
|
|---|
| 218 | PRInt16 hashShift; /* multiplicative hash shift */
|
|---|
| 219 | uint8 maxAlphaFrac; /* 8-bit fixed point max alpha */
|
|---|
| 220 | uint8 minAlphaFrac; /* 8-bit fixed point min alpha */
|
|---|
| 221 | PRUint32 entrySize; /* number of bytes in an entry */
|
|---|
| 222 | PRUint32 entryCount; /* number of entries in table */
|
|---|
| 223 | PRUint32 removedCount; /* removed entry sentinels in table */
|
|---|
| 224 | PRUint32 generation; /* entry storage generation number */
|
|---|
| 225 | char *entryStore; /* entry storage */
|
|---|
| 226 | #ifdef PL_DHASHMETER
|
|---|
| 227 | struct PLDHashStats {
|
|---|
| 228 | PRUint32 searches; /* total number of table searches */
|
|---|
| 229 | PRUint32 steps; /* hash chain links traversed */
|
|---|
| 230 | PRUint32 hits; /* searches that found key */
|
|---|
| 231 | PRUint32 misses; /* searches that didn't find key */
|
|---|
| 232 | PRUint32 lookups; /* number of PL_DHASH_LOOKUPs */
|
|---|
| 233 | PRUint32 addMisses; /* adds that miss, and do work */
|
|---|
| 234 | PRUint32 addOverRemoved; /* adds that recycled a removed entry */
|
|---|
| 235 | PRUint32 addHits; /* adds that hit an existing entry */
|
|---|
| 236 | PRUint32 addFailures; /* out-of-memory during add growth */
|
|---|
| 237 | PRUint32 removeHits; /* removes that hit, and do work */
|
|---|
| 238 | PRUint32 removeMisses; /* useless removes that miss */
|
|---|
| 239 | PRUint32 removeFrees; /* removes that freed entry directly */
|
|---|
| 240 | PRUint32 removeEnums; /* removes done by Enumerate */
|
|---|
| 241 | PRUint32 grows; /* table expansions */
|
|---|
| 242 | PRUint32 shrinks; /* table contractions */
|
|---|
| 243 | PRUint32 compresses; /* table compressions */
|
|---|
| 244 | PRUint32 enumShrinks; /* contractions after Enumerate */
|
|---|
| 245 | } stats;
|
|---|
| 246 | #endif
|
|---|
| 247 | };
|
|---|
| 248 |
|
|---|
| 249 | /*
|
|---|
| 250 | * Size in entries (gross, not net of free and removed sentinels) for table.
|
|---|
| 251 | * We store hashShift rather than sizeLog2 to optimize the collision-free case
|
|---|
| 252 | * in SearchTable.
|
|---|
| 253 | */
|
|---|
| 254 | #define PL_DHASH_TABLE_SIZE(table) PR_BIT(PL_DHASH_BITS - (table)->hashShift)
|
|---|
| 255 |
|
|---|
| 256 | /*
|
|---|
| 257 | * Table space at entryStore is allocated and freed using these callbacks.
|
|---|
| 258 | * The allocator should return null on error only (not if called with nbytes
|
|---|
| 259 | * equal to 0; but note that pldhash.c code will never call with 0 nbytes).
|
|---|
| 260 | */
|
|---|
| 261 | typedef void *
|
|---|
| 262 | (* PR_CALLBACK PLDHashAllocTable)(PLDHashTable *table, PRUint32 nbytes);
|
|---|
| 263 |
|
|---|
| 264 | typedef void
|
|---|
| 265 | (* PR_CALLBACK PLDHashFreeTable) (PLDHashTable *table, void *ptr);
|
|---|
| 266 |
|
|---|
| 267 | /*
|
|---|
| 268 | * When a table grows or shrinks, each entry is queried for its key using this
|
|---|
| 269 | * callback. NB: in that event, entry is not in table any longer; it's in the
|
|---|
| 270 | * old entryStore vector, which is due to be freed once all entries have been
|
|---|
| 271 | * moved via moveEntry callbacks.
|
|---|
| 272 | */
|
|---|
| 273 | typedef const void *
|
|---|
| 274 | (* PR_CALLBACK PLDHashGetKey) (PLDHashTable *table,
|
|---|
| 275 | PLDHashEntryHdr *entry);
|
|---|
| 276 |
|
|---|
| 277 | /*
|
|---|
| 278 | * Compute the hash code for a given key to be looked up, added, or removed
|
|---|
| 279 | * from table. A hash code may have any PLDHashNumber value.
|
|---|
| 280 | */
|
|---|
| 281 | typedef PLDHashNumber
|
|---|
| 282 | (* PR_CALLBACK PLDHashHashKey) (PLDHashTable *table, const void *key);
|
|---|
| 283 |
|
|---|
| 284 | /*
|
|---|
| 285 | * Compare the key identifying entry in table with the provided key parameter.
|
|---|
| 286 | * Return PR_TRUE if keys match, PR_FALSE otherwise.
|
|---|
| 287 | */
|
|---|
| 288 | typedef PRBool
|
|---|
| 289 | (* PR_CALLBACK PLDHashMatchEntry)(PLDHashTable *table,
|
|---|
| 290 | const PLDHashEntryHdr *entry,
|
|---|
| 291 | const void *key);
|
|---|
| 292 |
|
|---|
| 293 | /*
|
|---|
| 294 | * Copy the data starting at from to the new entry storage at to. Do not add
|
|---|
| 295 | * reference counts for any strong references in the entry, however, as this
|
|---|
| 296 | * is a "move" operation: the old entry storage at from will be freed without
|
|---|
| 297 | * any reference-decrementing callback shortly.
|
|---|
| 298 | */
|
|---|
| 299 | typedef void
|
|---|
| 300 | (* PR_CALLBACK PLDHashMoveEntry)(PLDHashTable *table,
|
|---|
| 301 | const PLDHashEntryHdr *from,
|
|---|
| 302 | PLDHashEntryHdr *to);
|
|---|
| 303 |
|
|---|
| 304 | /*
|
|---|
| 305 | * Clear the entry and drop any strong references it holds. This callback is
|
|---|
| 306 | * invoked during a PL_DHASH_REMOVE operation (see below for operation codes),
|
|---|
| 307 | * but only if the given key is found in the table.
|
|---|
| 308 | */
|
|---|
| 309 | typedef void
|
|---|
| 310 | (* PR_CALLBACK PLDHashClearEntry)(PLDHashTable *table,
|
|---|
| 311 | PLDHashEntryHdr *entry);
|
|---|
| 312 |
|
|---|
| 313 | /*
|
|---|
| 314 | * Called when a table (whether allocated dynamically by itself, or nested in
|
|---|
| 315 | * a larger structure, or allocated on the stack) is finished. This callback
|
|---|
| 316 | * allows table->ops-specific code to finalize table->data.
|
|---|
| 317 | */
|
|---|
| 318 | typedef void
|
|---|
| 319 | (* PR_CALLBACK PLDHashFinalize) (PLDHashTable *table);
|
|---|
| 320 |
|
|---|
| 321 | /*
|
|---|
| 322 | * Initialize a new entry, apart from keyHash. This function is called when
|
|---|
| 323 | * PL_DHashTableOperate's PL_DHASH_ADD case finds no existing entry for the
|
|---|
| 324 | * given key, and must add a new one. At that point, entry->keyHash is not
|
|---|
| 325 | * set yet, to avoid claiming the last free entry in a severely overloaded
|
|---|
| 326 | * table.
|
|---|
| 327 | */
|
|---|
| 328 | typedef PRBool
|
|---|
| 329 | (* PR_CALLBACK PLDHashInitEntry)(PLDHashTable *table,
|
|---|
| 330 | PLDHashEntryHdr *entry,
|
|---|
| 331 | const void *key);
|
|---|
| 332 |
|
|---|
| 333 | /*
|
|---|
| 334 | * Finally, the "vtable" structure for PLDHashTable. The first eight hooks
|
|---|
| 335 | * must be provided by implementations; they're called unconditionally by the
|
|---|
| 336 | * generic pldhash.c code. Hooks after these may be null.
|
|---|
| 337 | *
|
|---|
| 338 | * Summary of allocation-related hook usage with C++ placement new emphasis:
|
|---|
| 339 | * allocTable Allocate raw bytes with malloc, no ctors run.
|
|---|
| 340 | * freeTable Free raw bytes with free, no dtors run.
|
|---|
| 341 | * initEntry Call placement new using default key-based ctor.
|
|---|
| 342 | * Return PR_TRUE on success, PR_FALSE on error.
|
|---|
| 343 | * moveEntry Call placement new using copy ctor, run dtor on old
|
|---|
| 344 | * entry storage.
|
|---|
| 345 | * clearEntry Run dtor on entry.
|
|---|
| 346 | * finalize Stub unless table->data was initialized and needs to
|
|---|
| 347 | * be finalized.
|
|---|
| 348 | *
|
|---|
| 349 | * Note the reason why initEntry is optional: the default hooks (stubs) clear
|
|---|
| 350 | * entry storage: On successful PL_DHashTableOperate(tbl, key, PL_DHASH_ADD),
|
|---|
| 351 | * the returned entry pointer addresses an entry struct whose keyHash member
|
|---|
| 352 | * has been set non-zero, but all other entry members are still clear (null).
|
|---|
| 353 | * PL_DHASH_ADD callers can test such members to see whether the entry was
|
|---|
| 354 | * newly created by the PL_DHASH_ADD call that just succeeded. If placement
|
|---|
| 355 | * new or similar initialization is required, define an initEntry hook. Of
|
|---|
| 356 | * course, the clearEntry hook must zero or null appropriately.
|
|---|
| 357 | *
|
|---|
| 358 | * XXX assumes 0 is null for pointer types.
|
|---|
| 359 | */
|
|---|
| 360 | struct PLDHashTableOps {
|
|---|
| 361 | /* Mandatory hooks. All implementations must provide these. */
|
|---|
| 362 | PLDHashAllocTable allocTable;
|
|---|
| 363 | PLDHashFreeTable freeTable;
|
|---|
| 364 | PLDHashGetKey getKey;
|
|---|
| 365 | PLDHashHashKey hashKey;
|
|---|
| 366 | PLDHashMatchEntry matchEntry;
|
|---|
| 367 | PLDHashMoveEntry moveEntry;
|
|---|
| 368 | PLDHashClearEntry clearEntry;
|
|---|
| 369 | PLDHashFinalize finalize;
|
|---|
| 370 |
|
|---|
| 371 | /* Optional hooks start here. If null, these are not called. */
|
|---|
| 372 | PLDHashInitEntry initEntry;
|
|---|
| 373 | };
|
|---|
| 374 |
|
|---|
| 375 | /*
|
|---|
| 376 | * Default implementations for the above ops.
|
|---|
| 377 | */
|
|---|
| 378 | PR_EXTERN(void *)
|
|---|
| 379 | PL_DHashAllocTable(PLDHashTable *table, PRUint32 nbytes);
|
|---|
| 380 |
|
|---|
| 381 | PR_EXTERN(void)
|
|---|
| 382 | PL_DHashFreeTable(PLDHashTable *table, void *ptr);
|
|---|
| 383 |
|
|---|
| 384 | PR_EXTERN(PLDHashNumber)
|
|---|
| 385 | PL_DHashStringKey(PLDHashTable *table, const void *key);
|
|---|
| 386 |
|
|---|
| 387 | /* A minimal entry contains a keyHash header and a void key pointer. */
|
|---|
| 388 | struct PLDHashEntryStub {
|
|---|
| 389 | PLDHashEntryHdr hdr;
|
|---|
| 390 | const void *key;
|
|---|
| 391 | };
|
|---|
| 392 |
|
|---|
| 393 | PR_EXTERN(const void *)
|
|---|
| 394 | PL_DHashGetKeyStub(PLDHashTable *table, PLDHashEntryHdr *entry);
|
|---|
| 395 |
|
|---|
| 396 | PR_EXTERN(PLDHashNumber)
|
|---|
| 397 | PL_DHashVoidPtrKeyStub(PLDHashTable *table, const void *key);
|
|---|
| 398 |
|
|---|
| 399 | PR_EXTERN(PRBool)
|
|---|
| 400 | PL_DHashMatchEntryStub(PLDHashTable *table,
|
|---|
| 401 | const PLDHashEntryHdr *entry,
|
|---|
| 402 | const void *key);
|
|---|
| 403 |
|
|---|
| 404 | PR_EXTERN(PRBool)
|
|---|
| 405 | PL_DHashMatchStringKey(PLDHashTable *table,
|
|---|
| 406 | const PLDHashEntryHdr *entry,
|
|---|
| 407 | const void *key);
|
|---|
| 408 |
|
|---|
| 409 | PR_EXTERN(void)
|
|---|
| 410 | PL_DHashMoveEntryStub(PLDHashTable *table,
|
|---|
| 411 | const PLDHashEntryHdr *from,
|
|---|
| 412 | PLDHashEntryHdr *to);
|
|---|
| 413 |
|
|---|
| 414 | PR_EXTERN(void)
|
|---|
| 415 | PL_DHashClearEntryStub(PLDHashTable *table, PLDHashEntryHdr *entry);
|
|---|
| 416 |
|
|---|
| 417 | PR_EXTERN(void)
|
|---|
| 418 | PL_DHashFreeStringKey(PLDHashTable *table, PLDHashEntryHdr *entry);
|
|---|
| 419 |
|
|---|
| 420 | PR_EXTERN(void)
|
|---|
| 421 | PL_DHashFinalizeStub(PLDHashTable *table);
|
|---|
| 422 |
|
|---|
| 423 | /*
|
|---|
| 424 | * If you use PLDHashEntryStub or a subclass of it as your entry struct, and
|
|---|
| 425 | * if your entries move via memcpy and clear via memset(0), you can use these
|
|---|
| 426 | * stub operations.
|
|---|
| 427 | */
|
|---|
| 428 | PR_EXTERN(const PLDHashTableOps *)
|
|---|
| 429 | PL_DHashGetStubOps(void);
|
|---|
| 430 |
|
|---|
| 431 | /*
|
|---|
| 432 | * Dynamically allocate a new PLDHashTable using malloc, initialize it using
|
|---|
| 433 | * PL_DHashTableInit, and return its address. Return null on malloc failure.
|
|---|
| 434 | * Note that the entry storage at table->entryStore will be allocated using
|
|---|
| 435 | * the ops->allocTable callback.
|
|---|
| 436 | */
|
|---|
| 437 | PR_EXTERN(PLDHashTable *)
|
|---|
| 438 | PL_NewDHashTable(const PLDHashTableOps *ops, void *data, PRUint32 entrySize,
|
|---|
| 439 | PRUint32 capacity);
|
|---|
| 440 |
|
|---|
| 441 | /*
|
|---|
| 442 | * Finalize table's data, free its entry storage (via table->ops->freeTable),
|
|---|
| 443 | * and return the memory starting at table to the malloc heap.
|
|---|
| 444 | */
|
|---|
| 445 | PR_EXTERN(void)
|
|---|
| 446 | PL_DHashTableDestroy(PLDHashTable *table);
|
|---|
| 447 |
|
|---|
| 448 | /*
|
|---|
| 449 | * Initialize table with ops, data, entrySize, and capacity. Capacity is a
|
|---|
| 450 | * guess for the smallest table size at which the table will usually be less
|
|---|
| 451 | * than 75% loaded (the table will grow or shrink as needed; capacity serves
|
|---|
| 452 | * only to avoid inevitable early growth from PL_DHASH_MIN_SIZE).
|
|---|
| 453 | */
|
|---|
| 454 | PR_EXTERN(PRBool)
|
|---|
| 455 | PL_DHashTableInit(PLDHashTable *table, const PLDHashTableOps *ops, void *data,
|
|---|
| 456 | PRUint32 entrySize, PRUint32 capacity);
|
|---|
| 457 |
|
|---|
| 458 | /*
|
|---|
| 459 | * Set maximum and minimum alpha for table. The defaults are 0.75 and .25.
|
|---|
| 460 | * maxAlpha must be in [0.5, 0.9375] for the default PL_DHASH_MIN_SIZE; or if
|
|---|
| 461 | * MinSize=PL_DHASH_MIN_SIZE <= 256, in [0.5, (float)(MinSize-1)/MinSize]; or
|
|---|
| 462 | * else in [0.5, 255.0/256]. minAlpha must be in [0, maxAlpha / 2), so that
|
|---|
| 463 | * we don't shrink on the very next remove after growing a table upon adding
|
|---|
| 464 | * an entry that brings entryCount past maxAlpha * tableSize.
|
|---|
| 465 | */
|
|---|
| 466 | PR_IMPLEMENT(void)
|
|---|
| 467 | PL_DHashTableSetAlphaBounds(PLDHashTable *table,
|
|---|
| 468 | float maxAlpha,
|
|---|
| 469 | float minAlpha);
|
|---|
| 470 |
|
|---|
| 471 | /*
|
|---|
| 472 | * Call this macro with k, the number of pointer-sized words wasted per entry
|
|---|
| 473 | * under chaining, to compute the minimum alpha at which double hashing still
|
|---|
| 474 | * beats chaining.
|
|---|
| 475 | */
|
|---|
| 476 | #define PL_DHASH_MIN_ALPHA(table, k) \
|
|---|
| 477 | ((float)((table)->entrySize / sizeof(void *) - 1) \
|
|---|
| 478 | / ((table)->entrySize / sizeof(void *) + (k)))
|
|---|
| 479 |
|
|---|
| 480 | /*
|
|---|
| 481 | * Finalize table's data, free its entry storage using table->ops->freeTable,
|
|---|
| 482 | * and leave its members unchanged from their last live values (which leaves
|
|---|
| 483 | * pointers dangling). If you want to burn cycles clearing table, it's up to
|
|---|
| 484 | * your code to call memset.
|
|---|
| 485 | */
|
|---|
| 486 | PR_EXTERN(void)
|
|---|
| 487 | PL_DHashTableFinish(PLDHashTable *table);
|
|---|
| 488 |
|
|---|
| 489 | /*
|
|---|
| 490 | * To consolidate keyHash computation and table grow/shrink code, we use a
|
|---|
| 491 | * single entry point for lookup, add, and remove operations. The operation
|
|---|
| 492 | * codes are declared here, along with codes returned by PLDHashEnumerator
|
|---|
| 493 | * functions, which control PL_DHashTableEnumerate's behavior.
|
|---|
| 494 | */
|
|---|
| 495 | typedef enum PLDHashOperator {
|
|---|
| 496 | PL_DHASH_LOOKUP = 0, /* lookup entry */
|
|---|
| 497 | PL_DHASH_ADD = 1, /* add entry */
|
|---|
| 498 | PL_DHASH_REMOVE = 2, /* remove entry, or enumerator says remove */
|
|---|
| 499 | PL_DHASH_NEXT = 0, /* enumerator says continue */
|
|---|
| 500 | PL_DHASH_STOP = 1 /* enumerator says stop */
|
|---|
| 501 | } PLDHashOperator;
|
|---|
| 502 |
|
|---|
| 503 | /*
|
|---|
| 504 | * To lookup a key in table, call:
|
|---|
| 505 | *
|
|---|
| 506 | * entry = PL_DHashTableOperate(table, key, PL_DHASH_LOOKUP);
|
|---|
| 507 | *
|
|---|
| 508 | * If PL_DHASH_ENTRY_IS_BUSY(entry) is true, key was found and it identifies
|
|---|
| 509 | * entry. If PL_DHASH_ENTRY_IS_FREE(entry) is true, key was not found.
|
|---|
| 510 | *
|
|---|
| 511 | * To add an entry identified by key to table, call:
|
|---|
| 512 | *
|
|---|
| 513 | * entry = PL_DHashTableOperate(table, key, PL_DHASH_ADD);
|
|---|
| 514 | *
|
|---|
| 515 | * If entry is null upon return, then either the table is severely overloaded,
|
|---|
| 516 | * and memory can't be allocated for entry storage via table->ops->allocTable;
|
|---|
| 517 | * Or if table->ops->initEntry is non-null, the table->ops->initEntry op may
|
|---|
| 518 | * have returned false.
|
|---|
| 519 | *
|
|---|
| 520 | * Otherwise, entry->keyHash has been set so that PL_DHASH_ENTRY_IS_BUSY(entry)
|
|---|
| 521 | * is true, and it is up to the caller to initialize the key and value parts
|
|---|
| 522 | * of the entry sub-type, if they have not been set already (i.e. if entry was
|
|---|
| 523 | * not already in the table, and if the optional initEntry hook was not used).
|
|---|
| 524 | *
|
|---|
| 525 | * To remove an entry identified by key from table, call:
|
|---|
| 526 | *
|
|---|
| 527 | * (void) PL_DHashTableOperate(table, key, PL_DHASH_REMOVE);
|
|---|
| 528 | *
|
|---|
| 529 | * If key's entry is found, it is cleared (via table->ops->clearEntry) and
|
|---|
| 530 | * the entry is marked so that PL_DHASH_ENTRY_IS_FREE(entry). This operation
|
|---|
| 531 | * returns null unconditionally; you should ignore its return value.
|
|---|
| 532 | */
|
|---|
| 533 | PR_EXTERN(PLDHashEntryHdr *) PL_DHASH_FASTCALL
|
|---|
| 534 | PL_DHashTableOperate(PLDHashTable *table, const void *key, PLDHashOperator op);
|
|---|
| 535 |
|
|---|
| 536 | /*
|
|---|
| 537 | * Remove an entry already accessed via LOOKUP or ADD.
|
|---|
| 538 | *
|
|---|
| 539 | * NB: this is a "raw" or low-level routine, intended to be used only where
|
|---|
| 540 | * the inefficiency of a full PL_DHashTableOperate (which rehashes in order
|
|---|
| 541 | * to find the entry given its key) is not tolerable. This function does not
|
|---|
| 542 | * shrink the table if it is underloaded. It does not update stats #ifdef
|
|---|
| 543 | * PL_DHASHMETER, either.
|
|---|
| 544 | */
|
|---|
| 545 | PR_EXTERN(void)
|
|---|
| 546 | PL_DHashTableRawRemove(PLDHashTable *table, PLDHashEntryHdr *entry);
|
|---|
| 547 |
|
|---|
| 548 | /*
|
|---|
| 549 | * Enumerate entries in table using etor:
|
|---|
| 550 | *
|
|---|
| 551 | * count = PL_DHashTableEnumerate(table, etor, arg);
|
|---|
| 552 | *
|
|---|
| 553 | * PL_DHashTableEnumerate calls etor like so:
|
|---|
| 554 | *
|
|---|
| 555 | * op = etor(table, entry, number, arg);
|
|---|
| 556 | *
|
|---|
| 557 | * where number is a zero-based ordinal assigned to live entries according to
|
|---|
| 558 | * their order in table->entryStore.
|
|---|
| 559 | *
|
|---|
| 560 | * The return value, op, is treated as a set of flags. If op is PL_DHASH_NEXT,
|
|---|
| 561 | * then continue enumerating. If op contains PL_DHASH_REMOVE, then clear (via
|
|---|
| 562 | * table->ops->clearEntry) and free entry. Then we check whether op contains
|
|---|
| 563 | * PL_DHASH_STOP; if so, stop enumerating and return the number of live entries
|
|---|
| 564 | * that were enumerated so far. Return the total number of live entries when
|
|---|
| 565 | * enumeration completes normally.
|
|---|
| 566 | *
|
|---|
| 567 | * If etor calls PL_DHashTableOperate on table with op != PL_DHASH_LOOKUP, it
|
|---|
| 568 | * must return PL_DHASH_STOP; otherwise undefined behavior results.
|
|---|
| 569 | *
|
|---|
| 570 | * If any enumerator returns PL_DHASH_REMOVE, table->entryStore may be shrunk
|
|---|
| 571 | * or compressed after enumeration, but before PL_DHashTableEnumerate returns.
|
|---|
| 572 | * Such an enumerator therefore can't safely set aside entry pointers, but an
|
|---|
| 573 | * enumerator that never returns PL_DHASH_REMOVE can set pointers to entries
|
|---|
| 574 | * aside, e.g., to avoid copying live entries into an array of the entry type.
|
|---|
| 575 | * Copying entry pointers is cheaper, and safe so long as the caller of such a
|
|---|
| 576 | * "stable" Enumerate doesn't use the set-aside pointers after any call either
|
|---|
| 577 | * to PL_DHashTableOperate, or to an "unstable" form of Enumerate, which might
|
|---|
| 578 | * grow or shrink entryStore.
|
|---|
| 579 | *
|
|---|
| 580 | * If your enumerator wants to remove certain entries, but set aside pointers
|
|---|
| 581 | * to other entries that it retains, it can use PL_DHashTableRawRemove on the
|
|---|
| 582 | * entries to be removed, returning PL_DHASH_NEXT to skip them. Likewise, if
|
|---|
| 583 | * you want to remove entries, but for some reason you do not want entryStore
|
|---|
| 584 | * to be shrunk or compressed, you can call PL_DHashTableRawRemove safely on
|
|---|
| 585 | * the entry being enumerated, rather than returning PL_DHASH_REMOVE.
|
|---|
| 586 | */
|
|---|
| 587 | typedef PLDHashOperator
|
|---|
| 588 | (* PR_CALLBACK PLDHashEnumerator)(PLDHashTable *table, PLDHashEntryHdr *hdr,
|
|---|
| 589 | PRUint32 number, void *arg);
|
|---|
| 590 |
|
|---|
| 591 | PR_EXTERN(PRUint32)
|
|---|
| 592 | PL_DHashTableEnumerate(PLDHashTable *table, PLDHashEnumerator etor, void *arg);
|
|---|
| 593 |
|
|---|
| 594 | #ifdef PL_DHASHMETER
|
|---|
| 595 | #include <stdio.h>
|
|---|
| 596 |
|
|---|
| 597 | PR_EXTERN(void)
|
|---|
| 598 | PL_DHashTableDumpMeter(PLDHashTable *table, PLDHashEnumerator dump, FILE *fp);
|
|---|
| 599 | #endif
|
|---|
| 600 |
|
|---|
| 601 | PR_END_EXTERN_C
|
|---|
| 602 |
|
|---|
| 603 | #endif /* pldhash_h___ */
|
|---|
