39982ce05eab4cc494827831e486a787c9d800b9
1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /* ***** BEGIN LICENSE BLOCK *****
3 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
4 *
5 * The contents of this file are subject to the Mozilla Public License Version
6 * 1.1 (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 * http://www.mozilla.org/MPL/
9 *
10 * Software distributed under the License is distributed on an "AS IS" basis,
11 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12 * for the specific language governing rights and limitations under the
13 * License.
14 *
15 * The Original Code is Mozilla JavaScript code.
16 *
17 * The Initial Developer of the Original Code is
18 * Netscape Communications Corporation.
19 * Portions created by the Initial Developer are Copyright (C) 1999-2001
20 * the Initial Developer. All Rights Reserved.
21 *
22 * Contributor(s):
23 * Brendan Eich <brendan@mozilla.org> (Original Author)
24 *
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 ***** */
39 #ifndef jsdhash_h___
40 #define jsdhash_h___
41 /*
42 * Double hashing, a la Knuth 6.
43 */
44 #include "jstypes.h"
46 JS_BEGIN_EXTERN_C
48 #ifdef DEBUG_XXXbrendan
49 #define JS_DHASHMETER 1
50 #endif
52 /* Table size limit, do not equal or exceed (see min&maxAlphaFrac, below). */
53 #undef JS_DHASH_SIZE_LIMIT
54 #define JS_DHASH_SIZE_LIMIT JS_BIT(24)
56 /* Minimum table size, or gross entry count (net is at most .75 loaded). */
57 #ifndef JS_DHASH_MIN_SIZE
58 #define JS_DHASH_MIN_SIZE 16
59 #elif (JS_DHASH_MIN_SIZE & (JS_DHASH_MIN_SIZE - 1)) != 0
60 #error "JS_DHASH_MIN_SIZE must be a power of two!"
61 #endif
63 /*
64 * Multiplicative hash uses an unsigned 32 bit integer and the golden ratio,
65 * expressed as a fixed-point 32-bit fraction.
66 */
67 #define JS_DHASH_BITS 32
68 #define JS_DHASH_GOLDEN_RATIO 0x9E3779B9U
70 /* Primitive and forward-struct typedefs. */
71 typedef uint32 JSDHashNumber;
72 typedef struct JSDHashEntryHdr JSDHashEntryHdr;
73 typedef struct JSDHashEntryStub JSDHashEntryStub;
74 typedef struct JSDHashTable JSDHashTable;
75 typedef struct JSDHashTableOps JSDHashTableOps;
77 /*
78 * Table entry header structure.
79 *
80 * In order to allow in-line allocation of key and value, we do not declare
81 * either here. Instead, the API uses const void *key as a formal parameter,
82 * and asks each entry for its key when necessary via a getKey callback, used
83 * when growing or shrinking the table. Other callback types are defined
84 * below and grouped into the JSDHashTableOps structure, for single static
85 * initialization per hash table sub-type.
86 *
87 * Each hash table sub-type should nest the JSDHashEntryHdr structure at the
88 * front of its particular entry type. The keyHash member contains the result
89 * of multiplying the hash code returned from the hashKey callback (see below)
90 * by JS_DHASH_GOLDEN_RATIO, then constraining the result to avoid the magic 0
91 * and 1 values. The stored keyHash value is table size invariant, and it is
92 * maintained automatically by JS_DHashTableOperate -- users should never set
93 * it, and its only uses should be via the entry macros below.
94 *
95 * The JS_DHASH_ENTRY_IS_LIVE macro tests whether entry is neither free nor
96 * removed. An entry may be either busy or free; if busy, it may be live or
97 * removed. Consumers of this API should not access members of entries that
98 * are not live.
99 *
100 * However, use JS_DHASH_ENTRY_IS_BUSY for faster liveness testing of entries
101 * returned by JS_DHashTableOperate, as JS_DHashTableOperate never returns a
102 * non-live, busy (i.e., removed) entry pointer to its caller. See below for
103 * more details on JS_DHashTableOperate's calling rules.
104 */
105 struct JSDHashEntryHdr {
106 JSDHashNumber keyHash; /* every entry must begin like this */
107 };
109 #define JS_DHASH_ENTRY_IS_FREE(entry) ((entry)->keyHash == 0)
110 #define JS_DHASH_ENTRY_IS_BUSY(entry) (!JS_DHASH_ENTRY_IS_FREE(entry))
111 #define JS_DHASH_ENTRY_IS_LIVE(entry) ((entry)->keyHash >= 2)
113 /*
114 * A JSDHashTable is currently 8 words (without the JS_DHASHMETER overhead)
115 * on most architectures, and may be allocated on the stack or within another
116 * structure or class (see below for the Init and Finish functions to use).
117 *
118 * To decide whether to use double hashing vs. chaining, we need to develop a
119 * trade-off relation, as follows:
120 *
121 * Let alpha be the load factor, esize the entry size in words, count the
122 * entry count, and pow2 the power-of-two table size in entries.
123 *
124 * (JSDHashTable overhead) > (JSHashTable overhead)
125 * (unused table entry space) > (malloc and .next overhead per entry) +
126 * (buckets overhead)
127 * (1 - alpha) * esize * pow2 > 2 * count + pow2
128 *
129 * Notice that alpha is by definition (count / pow2):
130 *
131 * (1 - alpha) * esize * pow2 > 2 * alpha * pow2 + pow2
132 * (1 - alpha) * esize > 2 * alpha + 1
133 *
134 * esize > (1 + 2 * alpha) / (1 - alpha)
135 *
136 * This assumes both tables must keep keyHash, key, and value for each entry,
137 * where key and value point to separately allocated strings or structures.
138 * If key and value can be combined into one pointer, then the trade-off is:
139 *
140 * esize > (1 + 3 * alpha) / (1 - alpha)
141 *
142 * If the entry value can be a subtype of JSDHashEntryHdr, rather than a type
143 * that must be allocated separately and referenced by an entry.value pointer
144 * member, and provided key's allocation can be fused with its entry's, then
145 * k (the words wasted per entry with chaining) is 4.
146 *
147 * To see these curves, feed gnuplot input like so:
148 *
149 * gnuplot> f(x,k) = (1 + k * x) / (1 - x)
150 * gnuplot> plot [0:.75] f(x,2), f(x,3), f(x,4)
151 *
152 * For k of 2 and a well-loaded table (alpha > .5), esize must be more than 4
153 * words for chaining to be more space-efficient than double hashing.
154 *
155 * Solving for alpha helps us decide when to shrink an underloaded table:
156 *
157 * esize > (1 + k * alpha) / (1 - alpha)
158 * esize - alpha * esize > 1 + k * alpha
159 * esize - 1 > (k + esize) * alpha
160 * (esize - 1) / (k + esize) > alpha
161 *
162 * alpha < (esize - 1) / (esize + k)
163 *
164 * Therefore double hashing should keep alpha >= (esize - 1) / (esize + k),
165 * assuming esize is not too large (in which case, chaining should probably be
166 * used for any alpha). For esize=2 and k=3, we want alpha >= .2; for esize=3
167 * and k=2, we want alpha >= .4. For k=4, esize could be 6, and alpha >= .5
168 * would still obtain. See the JS_DHASH_MIN_ALPHA macro further below.
169 *
170 * The current implementation uses a configurable lower bound on alpha, which
171 * defaults to .25, when deciding to shrink the table (while still respecting
172 * JS_DHASH_MIN_SIZE).
173 *
174 * Note a qualitative difference between chaining and double hashing: under
175 * chaining, entry addresses are stable across table shrinks and grows. With
176 * double hashing, you can't safely hold an entry pointer and use it after an
177 * ADD or REMOVE operation, unless you sample table->generation before adding
178 * or removing, and compare the sample after, dereferencing the entry pointer
179 * only if table->generation has not changed.
180 *
181 * The moral of this story: there is no one-size-fits-all hash table scheme,
182 * but for small table entry size, and assuming entry address stability is not
183 * required, double hashing wins.
184 */
185 struct JSDHashTable {
186 const JSDHashTableOps *ops; /* virtual operations, see below */
187 void *data; /* ops- and instance-specific data */
188 int16 hashShift; /* multiplicative hash shift */
189 uint8 maxAlphaFrac; /* 8-bit fixed point max alpha */
190 uint8 minAlphaFrac; /* 8-bit fixed point min alpha */
191 uint32 entrySize; /* number of bytes in an entry */
192 uint32 entryCount; /* number of entries in table */
193 uint32 removedCount; /* removed entry sentinels in table */
194 uint32 generation; /* entry storage generation number */
195 char *entryStore; /* entry storage */
196 #ifdef JS_DHASHMETER
197 struct JSDHashStats {
198 uint32 searches; /* total number of table searches */
199 uint32 steps; /* hash chain links traversed */
200 uint32 hits; /* searches that found key */
201 uint32 misses; /* searches that didn't find key */
202 uint32 lookups; /* number of JS_DHASH_LOOKUPs */
203 uint32 addMisses; /* adds that miss, and do work */
204 uint32 addOverRemoved; /* adds that recycled a removed entry */
205 uint32 addHits; /* adds that hit an existing entry */
206 uint32 addFailures; /* out-of-memory during add growth */
207 uint32 removeHits; /* removes that hit, and do work */
208 uint32 removeMisses; /* useless removes that miss */
209 uint32 removeFrees; /* removes that freed entry directly */
210 uint32 removeEnums; /* removes done by Enumerate */
211 uint32 grows; /* table expansions */
212 uint32 shrinks; /* table contractions */
213 uint32 compresses; /* table compressions */
214 uint32 enumShrinks; /* contractions after Enumerate */
215 } stats;
216 #endif
217 };
219 /*
220 * Size in entries (gross, not net of free and removed sentinels) for table.
221 * We store hashShift rather than sizeLog2 to optimize the collision-free case
222 * in SearchTable.
223 */
224 #define JS_DHASH_TABLE_SIZE(table) JS_BIT(JS_DHASH_BITS - (table)->hashShift)
226 /*
227 * Table space at entryStore is allocated and freed using these callbacks.
228 * The allocator should return null on error only (not if called with nbytes
229 * equal to 0; but note that jsdhash.c code will never call with 0 nbytes).
230 */
231 typedef void *
232 (* JS_DLL_CALLBACK JSDHashAllocTable)(JSDHashTable *table, uint32 nbytes);
234 typedef void
235 (* JS_DLL_CALLBACK JSDHashFreeTable) (JSDHashTable *table, void *ptr);
237 /*
238 * When a table grows or shrinks, each entry is queried for its key using this
239 * callback. NB: in that event, entry is not in table any longer; it's in the
240 * old entryStore vector, which is due to be freed once all entries have been
241 * moved via moveEntry callbacks.
242 */
243 typedef const void *
244 (* JS_DLL_CALLBACK JSDHashGetKey) (JSDHashTable *table,
245 JSDHashEntryHdr *entry);
247 /*
248 * Compute the hash code for a given key to be looked up, added, or removed
249 * from table. A hash code may have any JSDHashNumber value.
250 */
251 typedef JSDHashNumber
252 (* JS_DLL_CALLBACK JSDHashHashKey) (JSDHashTable *table, const void *key);
254 /*
255 * Compare the key identifying entry in table with the provided key parameter.
256 * Return JS_TRUE if keys match, JS_FALSE otherwise.
257 */
258 typedef JSBool
259 (* JS_DLL_CALLBACK JSDHashMatchEntry)(JSDHashTable *table,
260 const JSDHashEntryHdr *entry,
261 const void *key);
263 /*
264 * Copy the data starting at from to the new entry storage at to. Do not add
265 * reference counts for any strong references in the entry, however, as this
266 * is a "move" operation: the old entry storage at from will be freed without
267 * any reference-decrementing callback shortly.
268 */
269 typedef void
270 (* JS_DLL_CALLBACK JSDHashMoveEntry)(JSDHashTable *table,
271 const JSDHashEntryHdr *from,
272 JSDHashEntryHdr *to);
274 /*
275 * Clear the entry and drop any strong references it holds. This callback is
276 * invoked during a JS_DHASH_REMOVE operation (see below for operation codes),
277 * but only if the given key is found in the table.
278 */
279 typedef void
280 (* JS_DLL_CALLBACK JSDHashClearEntry)(JSDHashTable *table,
281 JSDHashEntryHdr *entry);
283 /*
284 * Called when a table (whether allocated dynamically by itself, or nested in
285 * a larger structure, or allocated on the stack) is finished. This callback
286 * allows table->ops-specific code to finalize table->data.
287 */
288 typedef void
289 (* JS_DLL_CALLBACK JSDHashFinalize) (JSDHashTable *table);
291 /*
292 * Initialize a new entry, apart from keyHash. This function is called when
293 * JS_DHashTableOperate's JS_DHASH_ADD case finds no existing entry for the
294 * given key, and must add a new one. At that point, entry->keyHash is not
295 * set yet, to avoid claiming the last free entry in a severely overloaded
296 * table.
297 */
298 typedef JSBool
299 (* JS_DLL_CALLBACK JSDHashInitEntry)(JSDHashTable *table,
300 JSDHashEntryHdr *entry,
301 const void *key);
303 /*
304 * Finally, the "vtable" structure for JSDHashTable. The first eight hooks
305 * must be provided by implementations; they're called unconditionally by the
306 * generic jsdhash.c code. Hooks after these may be null.
307 *
308 * Summary of allocation-related hook usage with C++ placement new emphasis:
309 * allocTable Allocate raw bytes with malloc, no ctors run.
310 * freeTable Free raw bytes with free, no dtors run.
311 * initEntry Call placement new using default key-based ctor.
312 * Return JS_TRUE on success, JS_FALSE on error.
313 * moveEntry Call placement new using copy ctor, run dtor on old
314 * entry storage.
315 * clearEntry Run dtor on entry.
316 * finalize Stub unless table->data was initialized and needs to
317 * be finalized.
318 *
319 * Note the reason why initEntry is optional: the default hooks (stubs) clear
320 * entry storage: On successful JS_DHashTableOperate(tbl, key, JS_DHASH_ADD),
321 * the returned entry pointer addresses an entry struct whose keyHash member
322 * has been set non-zero, but all other entry members are still clear (null).
323 * JS_DHASH_ADD callers can test such members to see whether the entry was
324 * newly created by the JS_DHASH_ADD call that just succeeded. If placement
325 * new or similar initialization is required, define an initEntry hook. Of
326 * course, the clearEntry hook must zero or null appropriately.
327 *
328 * XXX assumes 0 is null for pointer types.
329 */
330 struct JSDHashTableOps {
331 /* Mandatory hooks. All implementations must provide these. */
332 JSDHashAllocTable allocTable;
333 JSDHashFreeTable freeTable;
334 JSDHashGetKey getKey;
335 JSDHashHashKey hashKey;
336 JSDHashMatchEntry matchEntry;
337 JSDHashMoveEntry moveEntry;
338 JSDHashClearEntry clearEntry;
339 JSDHashFinalize finalize;
341 /* Optional hooks start here. If null, these are not called. */
342 JSDHashInitEntry initEntry;
343 };
345 /*
346 * Default implementations for the above ops.
347 */
348 extern JS_PUBLIC_API(void *)
349 JS_DHashAllocTable(JSDHashTable *table, uint32 nbytes);
351 extern JS_PUBLIC_API(void)
352 JS_DHashFreeTable(JSDHashTable *table, void *ptr);
354 extern JS_PUBLIC_API(JSDHashNumber)
355 JS_DHashStringKey(JSDHashTable *table, const void *key);
357 /* A minimal entry contains a keyHash header and a void key pointer. */
358 struct JSDHashEntryStub {
359 JSDHashEntryHdr hdr;
360 const void *key;
361 };
363 extern JS_PUBLIC_API(const void *)
364 JS_DHashGetKeyStub(JSDHashTable *table, JSDHashEntryHdr *entry);
366 extern JS_PUBLIC_API(JSDHashNumber)
367 JS_DHashVoidPtrKeyStub(JSDHashTable *table, const void *key);
369 extern JS_PUBLIC_API(JSBool)
370 JS_DHashMatchEntryStub(JSDHashTable *table,
371 const JSDHashEntryHdr *entry,
372 const void *key);
374 extern JS_PUBLIC_API(JSBool)
375 JS_DHashMatchStringKey(JSDHashTable *table,
376 const JSDHashEntryHdr *entry,
377 const void *key);
379 extern JS_PUBLIC_API(void)
380 JS_DHashMoveEntryStub(JSDHashTable *table,
381 const JSDHashEntryHdr *from,
382 JSDHashEntryHdr *to);
384 extern JS_PUBLIC_API(void)
385 JS_DHashClearEntryStub(JSDHashTable *table, JSDHashEntryHdr *entry);
387 extern JS_PUBLIC_API(void)
388 JS_DHashFreeStringKey(JSDHashTable *table, JSDHashEntryHdr *entry);
390 extern JS_PUBLIC_API(void)
391 JS_DHashFinalizeStub(JSDHashTable *table);
393 /*
394 * If you use JSDHashEntryStub or a subclass of it as your entry struct, and
395 * if your entries move via memcpy and clear via memset(0), you can use these
396 * stub operations.
397 */
398 extern JS_PUBLIC_API(const JSDHashTableOps *)
399 JS_DHashGetStubOps(void);
401 /*
402 * Dynamically allocate a new JSDHashTable using malloc, initialize it using
403 * JS_DHashTableInit, and return its address. Return null on malloc failure.
404 * Note that the entry storage at table->entryStore will be allocated using
405 * the ops->allocTable callback.
406 */
407 extern JS_PUBLIC_API(JSDHashTable *)
408 JS_NewDHashTable(const JSDHashTableOps *ops, void *data, uint32 entrySize,
409 uint32 capacity);
411 /*
412 * Finalize table's data, free its entry storage (via table->ops->freeTable),
413 * and return the memory starting at table to the malloc heap.
414 */
415 extern JS_PUBLIC_API(void)
416 JS_DHashTableDestroy(JSDHashTable *table);
418 /*
419 * Initialize table with ops, data, entrySize, and capacity. Capacity is a
420 * guess for the smallest table size at which the table will usually be less
421 * than 75% loaded (the table will grow or shrink as needed; capacity serves
422 * only to avoid inevitable early growth from JS_DHASH_MIN_SIZE).
423 */
424 extern JS_PUBLIC_API(JSBool)
425 JS_DHashTableInit(JSDHashTable *table, const JSDHashTableOps *ops, void *data,
426 uint32 entrySize, uint32 capacity);
428 /*
429 * Set maximum and minimum alpha for table. The defaults are 0.75 and .25.
430 * maxAlpha must be in [0.5, 0.9375] for the default JS_DHASH_MIN_SIZE; or if
431 * MinSize=JS_DHASH_MIN_SIZE <= 256, in [0.5, (float)(MinSize-1)/MinSize]; or
432 * else in [0.5, 255.0/256]. minAlpha must be in [0, maxAlpha / 2), so that
433 * we don't shrink on the very next remove after growing a table upon adding
434 * an entry that brings entryCount past maxAlpha * tableSize.
435 */
436 JS_PUBLIC_API(void)
437 JS_DHashTableSetAlphaBounds(JSDHashTable *table,
438 float maxAlpha,
439 float minAlpha);
441 /*
442 * Call this macro with k, the number of pointer-sized words wasted per entry
443 * under chaining, to compute the minimum alpha at which double hashing still
444 * beats chaining.
445 */
446 #define JS_DHASH_MIN_ALPHA(table, k) \
447 ((float)((table)->entrySize / sizeof(void *) - 1) \
448 / ((table)->entrySize / sizeof(void *) + (k)))
450 /*
451 * Finalize table's data, free its entry storage using table->ops->freeTable,
452 * and leave its members unchanged from their last live values (which leaves
453 * pointers dangling). If you want to burn cycles clearing table, it's up to
454 * your code to call memset.
455 */
456 extern JS_PUBLIC_API(void)
457 JS_DHashTableFinish(JSDHashTable *table);
459 /*
460 * To consolidate keyHash computation and table grow/shrink code, we use a
461 * single entry point for lookup, add, and remove operations. The operation
462 * codes are declared here, along with codes returned by JSDHashEnumerator
463 * functions, which control JS_DHashTableEnumerate's behavior.
464 */
465 typedef enum JSDHashOperator {
466 JS_DHASH_LOOKUP = 0, /* lookup entry */
467 JS_DHASH_ADD = 1, /* add entry */
468 JS_DHASH_REMOVE = 2, /* remove entry, or enumerator says remove */
469 JS_DHASH_NEXT = 0, /* enumerator says continue */
470 JS_DHASH_STOP = 1 /* enumerator says stop */
471 } JSDHashOperator;
473 /*
474 * To lookup a key in table, call:
475 *
476 * entry = JS_DHashTableOperate(table, key, JS_DHASH_LOOKUP);
477 *
478 * If JS_DHASH_ENTRY_IS_BUSY(entry) is true, key was found and it identifies
479 * entry. If JS_DHASH_ENTRY_IS_FREE(entry) is true, key was not found.
480 *
481 * To add an entry identified by key to table, call:
482 *
483 * entry = JS_DHashTableOperate(table, key, JS_DHASH_ADD);
484 *
485 * If entry is null upon return, then either the table is severely overloaded,
486 * and memory can't be allocated for entry storage via table->ops->allocTable;
487 * Or if table->ops->initEntry is non-null, the table->ops->initEntry op may
488 * have returned false.
489 *
490 * Otherwise, entry->keyHash has been set so that JS_DHASH_ENTRY_IS_BUSY(entry)
491 * is true, and it is up to the caller to initialize the key and value parts
492 * of the entry sub-type, if they have not been set already (i.e. if entry was
493 * not already in the table, and if the optional initEntry hook was not used).
494 *
495 * To remove an entry identified by key from table, call:
496 *
497 * (void) JS_DHashTableOperate(table, key, JS_DHASH_REMOVE);
498 *
499 * If key's entry is found, it is cleared (via table->ops->clearEntry) and
500 * the entry is marked so that JS_DHASH_ENTRY_IS_FREE(entry). This operation
501 * returns null unconditionally; you should ignore its return value.
502 */
503 extern JS_PUBLIC_API(JSDHashEntryHdr *)
504 JS_DHashTableOperate(JSDHashTable *table, const void *key, JSDHashOperator op);
506 /*
507 * Remove an entry already accessed via LOOKUP or ADD.
508 *
509 * NB: this is a "raw" or low-level routine, intended to be used only where
510 * the inefficiency of a full JS_DHashTableOperate (which rehashes in order
511 * to find the entry given its key) is not tolerable. This function does not
512 * shrink the table if it is underloaded. It does not update stats #ifdef
513 * JS_DHASHMETER, either.
514 */
515 extern JS_PUBLIC_API(void)
516 JS_DHashTableRawRemove(JSDHashTable *table, JSDHashEntryHdr *entry);
518 /*
519 * Enumerate entries in table using etor:
520 *
521 * count = JS_DHashTableEnumerate(table, etor, arg);
522 *
523 * JS_DHashTableEnumerate calls etor like so:
524 *
525 * op = etor(table, entry, number, arg);
526 *
527 * where number is a zero-based ordinal assigned to live entries according to
528 * their order in table->entryStore.
529 *
530 * The return value, op, is treated as a set of flags. If op is JS_DHASH_NEXT,
531 * then continue enumerating. If op contains JS_DHASH_REMOVE, then clear (via
532 * table->ops->clearEntry) and free entry. Then we check whether op contains
533 * JS_DHASH_STOP; if so, stop enumerating and return the number of live entries
534 * that were enumerated so far. Return the total number of live entries when
535 * enumeration completes normally.
536 *
537 * If etor calls JS_DHashTableOperate on table with op != JS_DHASH_LOOKUP, it
538 * must return JS_DHASH_STOP; otherwise undefined behavior results.
539 *
540 * If any enumerator returns JS_DHASH_REMOVE, table->entryStore may be shrunk
541 * or compressed after enumeration, but before JS_DHashTableEnumerate returns.
542 * Such an enumerator therefore can't safely set aside entry pointers, but an
543 * enumerator that never returns JS_DHASH_REMOVE can set pointers to entries
544 * aside, e.g., to avoid copying live entries into an array of the entry type.
545 * Copying entry pointers is cheaper, and safe so long as the caller of such a
546 * "stable" Enumerate doesn't use the set-aside pointers after any call either
547 * to PL_DHashTableOperate, or to an "unstable" form of Enumerate, which might
548 * grow or shrink entryStore.
549 *
550 * If your enumerator wants to remove certain entries, but set aside pointers
551 * to other entries that it retains, it can use JS_DHashTableRawRemove on the
552 * entries to be removed, returning JS_DHASH_NEXT to skip them. Likewise, if
553 * you want to remove entries, but for some reason you do not want entryStore
554 * to be shrunk or compressed, you can call JS_DHashTableRawRemove safely on
555 * the entry being enumerated, rather than returning JS_DHASH_REMOVE.
556 */
557 typedef JSDHashOperator
558 (* JS_DLL_CALLBACK JSDHashEnumerator)(JSDHashTable *table, JSDHashEntryHdr *hdr,
559 uint32 number, void *arg);
561 extern JS_PUBLIC_API(uint32)
562 JS_DHashTableEnumerate(JSDHashTable *table, JSDHashEnumerator etor, void *arg);
564 #ifdef JS_DHASHMETER
565 #include <stdio.h>
567 extern JS_PUBLIC_API(void)
568 JS_DHashTableDumpMeter(JSDHashTable *table, JSDHashEnumerator dump, FILE *fp);
569 #endif
571 JS_END_EXTERN_C
573 #endif /* jsdhash_h___ */