The Tor Browser / file comparison

comparison: xpcom/glue/pldhash.h

xpcom/glue/pldhash.h

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial