Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef PLDHashTable_h
8 : #define PLDHashTable_h
9 :
10 : #include "mozilla/Atomics.h"
11 : #include "mozilla/Attributes.h" // for MOZ_ALWAYS_INLINE
12 : #include "mozilla/fallible.h"
13 : #include "mozilla/MemoryReporting.h"
14 : #include "mozilla/Move.h"
15 : #include "mozilla/Types.h"
16 : #include "nscore.h"
17 :
18 : typedef size_t PLDHashNumber;
19 :
20 : class PLDHashTable;
21 : struct PLDHashTableOps;
22 :
23 : // Table entry header structure.
24 : //
25 : // In order to allow in-line allocation of key and value, we do not declare
26 : // either here. Instead, the API uses const void *key as a formal parameter.
27 : // The key need not be stored in the entry; it may be part of the value, but
28 : // need not be stored at all.
29 : //
30 : // Callback types are defined below and grouped into the PLDHashTableOps
31 : // structure, for single static initialization per hash table sub-type.
32 : //
33 : // Each hash table sub-type should make its entry type a subclass of
34 : // PLDHashEntryHdr. The mKeyHash member contains the result of multiplying the
35 : // hash code returned from the hashKey callback (see below) by kGoldenRatio,
36 : // then constraining the result to avoid the magic 0 and 1 values. The stored
37 : // mKeyHash value is table size invariant, and it is maintained automatically
38 : // -- users need never access it.
39 93123 : struct PLDHashEntryHdr
40 : {
41 : private:
42 : friend class PLDHashTable;
43 :
44 : PLDHashNumber mKeyHash;
45 : };
46 :
47 : #ifdef DEBUG
48 :
49 : // This class does three kinds of checking:
50 : //
51 : // - that calls to one of |mOps| or to an enumerator do not cause re-entry into
52 : // the table in an unsafe way;
53 : //
54 : // - that multiple threads do not access the table in an unsafe way;
55 : //
56 : // - that a table marked as immutable is not modified.
57 : //
58 : // "Safe" here means that multiple concurrent read operations are ok, but a
59 : // write operation (i.e. one that can cause the entry storage to be reallocated
60 : // or destroyed) cannot safely run concurrently with another read or write
61 : // operation. This meaning of "safe" is only partial; for example, it does not
62 : // cover whether a single entry in the table is modified by two separate
63 : // threads. (Doing such checking would be much harder.)
64 : //
65 : // It does this with two variables:
66 : //
67 : // - mState, which embodies a tri-stage tagged union with the following
68 : // variants:
69 : // - Idle
70 : // - Read(n), where 'n' is the number of concurrent read operations
71 : // - Write
72 : //
73 : // - mIsWritable, which indicates if the table is mutable.
74 : //
75 : class Checker
76 : {
77 : public:
78 13560 : constexpr Checker() : mState(kIdle), mIsWritable(1) {}
79 :
80 3 : Checker& operator=(Checker&& aOther) {
81 : // Atomic<> doesn't have an |operator=(Atomic<>&&)|.
82 3 : mState = uint32_t(aOther.mState);
83 3 : mIsWritable = uint32_t(aOther.mIsWritable);
84 :
85 3 : aOther.mState = kIdle;
86 :
87 3 : return *this;
88 : }
89 :
90 461101 : static bool IsIdle(uint32_t aState) { return aState == kIdle; }
91 244390 : static bool IsRead(uint32_t aState) { return kRead1 <= aState &&
92 244390 : aState <= kReadMax; }
93 : static bool IsRead1(uint32_t aState) { return aState == kRead1; }
94 216842 : static bool IsWrite(uint32_t aState) { return aState == kWrite; }
95 :
96 : bool IsIdle() const { return mState == kIdle; }
97 :
98 433697 : bool IsWritable() const { return !!mIsWritable; }
99 :
100 32 : void SetNonWritable() { mIsWritable = 0; }
101 :
102 : // NOTE: the obvious way to implement these functions is to (a) check
103 : // |mState| is reasonable, and then (b) update |mState|. But the lack of
104 : // atomicity in such an implementation can cause problems if we get unlucky
105 : // thread interleaving between (a) and (b).
106 : //
107 : // So instead for |mState| we are careful to (a) first get |mState|'s old
108 : // value and assign it a new value in single atomic operation, and only then
109 : // (b) check the old value was reasonable. This ensures we don't have
110 : // interleaving problems.
111 : //
112 : // For |mIsWritable| we don't need to be as careful because it can only in
113 : // transition in one direction (from writable to non-writable).
114 :
115 244249 : void StartReadOp()
116 : {
117 244249 : uint32_t oldState = mState++; // this is an atomic increment
118 244266 : MOZ_ASSERT(IsIdle(oldState) || IsRead(oldState));
119 244266 : MOZ_ASSERT(oldState < kReadMax); // check for overflow
120 244266 : }
121 :
122 244245 : void EndReadOp()
123 : {
124 244245 : uint32_t oldState = mState--; // this is an atomic decrement
125 244267 : MOZ_ASSERT(IsRead(oldState));
126 244267 : }
127 :
128 211259 : void StartWriteOp()
129 : {
130 211259 : MOZ_ASSERT(IsWritable());
131 211259 : uint32_t oldState = mState.exchange(kWrite);
132 211259 : MOZ_ASSERT(IsIdle(oldState));
133 211259 : }
134 :
135 211258 : void EndWriteOp()
136 : {
137 : // Check again that the table is writable, in case it was marked as
138 : // non-writable just after the IsWritable() assertion in StartWriteOp()
139 : // occurred.
140 211258 : MOZ_ASSERT(IsWritable());
141 211258 : uint32_t oldState = mState.exchange(kIdle);
142 211259 : MOZ_ASSERT(IsWrite(oldState));
143 211259 : }
144 :
145 : void StartIteratorRemovalOp()
146 : {
147 : // When doing removals at the end of iteration, we go from Read1 state to
148 : // Write and then back.
149 : MOZ_ASSERT(IsWritable());
150 : uint32_t oldState = mState.exchange(kWrite);
151 : MOZ_ASSERT(IsRead1(oldState));
152 : }
153 :
154 : void EndIteratorRemovalOp()
155 : {
156 : // Check again that the table is writable, in case it was marked as
157 : // non-writable just after the IsWritable() assertion in
158 : // StartIteratorRemovalOp() occurred.
159 : MOZ_ASSERT(IsWritable());
160 : uint32_t oldState = mState.exchange(kRead1);
161 : MOZ_ASSERT(IsWrite(oldState));
162 : }
163 :
164 5582 : void StartDestructorOp()
165 : {
166 : // A destructor op is like a write, but the table doesn't need to be
167 : // writable.
168 5582 : uint32_t oldState = mState.exchange(kWrite);
169 5583 : MOZ_ASSERT(IsIdle(oldState));
170 5583 : }
171 :
172 5583 : void EndDestructorOp()
173 : {
174 5583 : uint32_t oldState = mState.exchange(kIdle);
175 5583 : MOZ_ASSERT(IsWrite(oldState));
176 5583 : }
177 :
178 : private:
179 : // Things of note about the representation of |mState|.
180 : // - The values between kRead1..kReadMax represent valid Read(n) values.
181 : // - kIdle and kRead1 are deliberately chosen so that incrementing the -
182 : // former gives the latter.
183 : // - 9999 concurrent readers should be enough for anybody.
184 : static const uint32_t kIdle = 0;
185 : static const uint32_t kRead1 = 1;
186 : static const uint32_t kReadMax = 9999;
187 : static const uint32_t kWrite = 10000;
188 :
189 : mutable mozilla::Atomic<uint32_t> mState;
190 : mutable mozilla::Atomic<uint32_t> mIsWritable;
191 : };
192 : #endif
193 :
194 : // A PLDHashTable may be allocated on the stack or within another structure or
195 : // class. No entry storage is allocated until the first element is added. This
196 : // means that empty hash tables are cheap, which is good because they are
197 : // common.
198 : //
199 : // There used to be a long, math-heavy comment here about the merits of
200 : // double hashing vs. chaining; it was removed in bug 1058335. In short, double
201 : // hashing is more space-efficient unless the element size gets large (in which
202 : // case you should keep using double hashing but switch to using pointer
203 : // elements). Also, with double hashing, you can't safely hold an entry pointer
204 : // and use it after an add or remove operation, unless you sample Generation()
205 : // before adding or removing, and compare the sample after, dereferencing the
206 : // entry pointer only if Generation() has not changed.
207 : class PLDHashTable
208 : {
209 : private:
210 : // This class maintains the invariant that every time the entry store is
211 : // changed, the generation is updated.
212 : class EntryStore
213 : {
214 : private:
215 : char* mEntryStore;
216 : uint32_t mGeneration;
217 :
218 : public:
219 13560 : EntryStore() : mEntryStore(nullptr), mGeneration(0) {}
220 :
221 5580 : ~EntryStore()
222 5580 : {
223 5580 : free(mEntryStore);
224 5580 : mEntryStore = nullptr;
225 5580 : mGeneration++; // a little paranoid, but why not be extra safe?
226 5580 : }
227 :
228 2194204 : char* Get() { return mEntryStore; }
229 217261 : const char* Get() const { return mEntryStore; }
230 :
231 4838 : void Set(char* aEntryStore)
232 : {
233 4838 : mEntryStore = aEntryStore;
234 4838 : mGeneration++;
235 4838 : }
236 :
237 12028 : uint32_t Generation() const { return mGeneration; }
238 : };
239 :
240 : const PLDHashTableOps* const mOps; // Virtual operations; see below.
241 : int16_t mHashShift; // Multiplicative hash shift.
242 : const uint32_t mEntrySize; // Number of bytes in an entry.
243 : uint32_t mEntryCount; // Number of entries in table.
244 : uint32_t mRemovedCount; // Removed entry sentinels in table.
245 : EntryStore mEntryStore; // (Lazy) entry storage and generation.
246 :
247 : #ifdef DEBUG
248 : mutable Checker mChecker;
249 : #endif
250 :
251 : public:
252 : // Table capacity limit; do not exceed. The max capacity used to be 1<<23 but
253 : // that occasionally that wasn't enough. Making it much bigger than 1<<26
254 : // probably isn't worthwhile -- tables that big are kind of ridiculous.
255 : // Also, the growth operation will (deliberately) fail if |capacity *
256 : // mEntrySize| overflows a uint32_t, and mEntrySize is always at least 8
257 : // bytes.
258 : static const uint32_t kMaxCapacity = ((uint32_t)1 << 26);
259 :
260 : static const uint32_t kMinCapacity = 8;
261 :
262 : // Making this half of kMaxCapacity ensures it'll fit. Nobody should need an
263 : // initial length anywhere nearly this large, anyway.
264 : static const uint32_t kMaxInitialLength = kMaxCapacity / 2;
265 :
266 : // This gives a default initial capacity of 8.
267 : static const uint32_t kDefaultInitialLength = 4;
268 :
269 : // Initialize the table with |aOps| and |aEntrySize|. The table's initial
270 : // capacity is chosen such that |aLength| elements can be inserted without
271 : // rehashing; if |aLength| is a power-of-two, this capacity will be
272 : // |2*length|. However, because entry storage is allocated lazily, this
273 : // initial capacity won't be relevant until the first element is added; prior
274 : // to that the capacity will be zero.
275 : //
276 : // This will crash if |aEntrySize| and/or |aLength| are too large.
277 : PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
278 : uint32_t aLength = kDefaultInitialLength);
279 :
280 1 : PLDHashTable(PLDHashTable&& aOther)
281 : // These two fields are |const|. Initialize them here because the
282 : // move assignment operator cannot modify them.
283 1 : : mOps(aOther.mOps)
284 1 : , mEntrySize(aOther.mEntrySize)
285 : // Initialize this field because it is required for a safe call to the
286 : // destructor, which the move assignment operator does.
287 : , mEntryStore()
288 : #ifdef DEBUG
289 2 : , mChecker()
290 : #endif
291 : {
292 1 : *this = mozilla::Move(aOther);
293 1 : }
294 :
295 : PLDHashTable& operator=(PLDHashTable&& aOther);
296 :
297 : ~PLDHashTable();
298 :
299 : // This should be used rarely.
300 4 : const PLDHashTableOps* Ops() const { return mOps; }
301 :
302 : // Size in entries (gross, not net of free and removed sentinels) for table.
303 : // This can be zero if no elements have been added yet, in which case the
304 : // entry storage will not have yet been allocated.
305 217087 : uint32_t Capacity() const
306 : {
307 217087 : return mEntryStore.Get() ? CapacityFromHashShift() : 0;
308 : }
309 :
310 0 : uint32_t EntrySize() const { return mEntrySize; }
311 49804 : uint32_t EntryCount() const { return mEntryCount; }
312 12028 : uint32_t Generation() const { return mEntryStore.Generation(); }
313 :
314 : // To search for a |key| in |table|, call:
315 : //
316 : // entry = table.Search(key);
317 : //
318 : // If |entry| is non-null, |key| was found. If |entry| is null, key was not
319 : // found.
320 : PLDHashEntryHdr* Search(const void* aKey);
321 :
322 : // To add an entry identified by |key| to table, call:
323 : //
324 : // entry = table.Add(key, mozilla::fallible);
325 : //
326 : // If |entry| is null upon return, then the table is severely overloaded and
327 : // memory can't be allocated for entry storage.
328 : //
329 : // Otherwise, |aEntry->mKeyHash| has been set so that
330 : // PLDHashTable::EntryIsFree(entry) is false, and it is up to the caller to
331 : // initialize the key and value parts of the entry sub-type, if they have not
332 : // been set already (i.e. if entry was not already in the table, and if the
333 : // optional initEntry hook was not used).
334 : PLDHashEntryHdr* Add(const void* aKey, const mozilla::fallible_t&);
335 :
336 : // This is like the other Add() function, but infallible, and so never
337 : // returns null.
338 : PLDHashEntryHdr* Add(const void* aKey);
339 :
340 : // To remove an entry identified by |key| from table, call:
341 : //
342 : // table.Remove(key);
343 : //
344 : // If |key|'s entry is found, it is cleared (via table->mOps->clearEntry).
345 : // The table's capacity may be reduced afterwards.
346 : void Remove(const void* aKey);
347 :
348 : // To remove an entry found by a prior search, call:
349 : //
350 : // table.RemoveEntry(entry);
351 : //
352 : // The entry, which must be present and in use, is cleared (via
353 : // table->mOps->clearEntry). The table's capacity may be reduced afterwards.
354 : void RemoveEntry(PLDHashEntryHdr* aEntry);
355 :
356 : // Remove an entry already accessed via Search() or Add().
357 : //
358 : // NB: this is a "raw" or low-level method. It does not shrink the table if
359 : // it is underloaded. Don't use it unless necessary and you know what you are
360 : // doing, and if so, please explain in a comment why it is necessary instead
361 : // of RemoveEntry().
362 : void RawRemove(PLDHashEntryHdr* aEntry);
363 :
364 : // This function is equivalent to
365 : // ClearAndPrepareForLength(kDefaultInitialLength).
366 : void Clear();
367 :
368 : // This function clears the table's contents and frees its entry storage,
369 : // leaving it in a empty state ready to be used again. Afterwards, when the
370 : // first element is added the entry storage that gets allocated will have a
371 : // capacity large enough to fit |aLength| elements without rehashing.
372 : //
373 : // It's conceptually the same as calling the destructor and then re-calling
374 : // the constructor with the original |aOps| and |aEntrySize| arguments, and
375 : // a new |aLength| argument.
376 : void ClearAndPrepareForLength(uint32_t aLength);
377 :
378 : // Measure the size of the table's entry storage. If the entries contain
379 : // pointers to other heap blocks, you have to iterate over the table and
380 : // measure those separately; hence the "Shallow" prefix.
381 : size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
382 :
383 : // Like ShallowSizeOfExcludingThis(), but includes sizeof(*this).
384 : size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const;
385 :
386 : #ifdef DEBUG
387 : // Mark a table as immutable for the remainder of its lifetime. This
388 : // changes the implementation from asserting one set of invariants to
389 : // asserting a different set.
390 : void MarkImmutable();
391 : #endif
392 :
393 : // If you use PLDHashEntryStub or a subclass of it as your entry struct, and
394 : // if your entries move via memcpy and clear via memset(0), you can use these
395 : // stub operations.
396 : static const PLDHashTableOps* StubOps();
397 :
398 : // The individual stub operations in StubOps().
399 : static PLDHashNumber HashVoidPtrKeyStub(const void* aKey);
400 : static bool MatchEntryStub(const PLDHashEntryHdr* aEntry, const void* aKey);
401 : static void MoveEntryStub(PLDHashTable* aTable, const PLDHashEntryHdr* aFrom,
402 : PLDHashEntryHdr* aTo);
403 : static void ClearEntryStub(PLDHashTable* aTable, PLDHashEntryHdr* aEntry);
404 :
405 : // Hash/match operations for tables holding C strings.
406 : static PLDHashNumber HashStringKey(const void* aKey);
407 : static bool MatchStringKey(const PLDHashEntryHdr* aEntry, const void* aKey);
408 :
409 : // This is an iterator for PLDHashtable. Assertions will detect some, but not
410 : // all, mid-iteration table modifications that might invalidate (e.g.
411 : // reallocate) the entry storage.
412 : //
413 : // Any element can be removed during iteration using Remove(). If any
414 : // elements are removed, the table may be resized once iteration ends.
415 : //
416 : // Example usage:
417 : //
418 : // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) {
419 : // auto entry = static_cast<FooEntry*>(iter.Get());
420 : // // ... do stuff with |entry| ...
421 : // // ... possibly call iter.Remove() once ...
422 : // }
423 : //
424 : // or:
425 : //
426 : // for (PLDHashTable::Iterator iter(&table); !iter.Done(); iter.Next()) {
427 : // auto entry = static_cast<FooEntry*>(iter.Get());
428 : // // ... do stuff with |entry| ...
429 : // // ... possibly call iter.Remove() once ...
430 : // }
431 : //
432 : // The latter form is more verbose but is easier to work with when
433 : // making subclasses of Iterator.
434 : //
435 : class Iterator
436 : {
437 : public:
438 : explicit Iterator(PLDHashTable* aTable);
439 : Iterator(Iterator&& aOther);
440 : ~Iterator();
441 :
442 : // Have we finished?
443 702267 : bool Done() const { return mNexts == mNextsLimit; }
444 :
445 : // Get the current entry.
446 125303 : PLDHashEntryHdr* Get() const
447 : {
448 125303 : MOZ_ASSERT(!Done());
449 :
450 125303 : PLDHashEntryHdr* entry = reinterpret_cast<PLDHashEntryHdr*>(mCurrent);
451 125303 : MOZ_ASSERT(EntryIsLive(entry));
452 125303 : return entry;
453 : }
454 :
455 : // Advance to the next entry.
456 : void Next();
457 :
458 : // Remove the current entry. Must only be called once per entry, and Get()
459 : // must not be called on that entry afterwards.
460 : void Remove();
461 :
462 : protected:
463 : PLDHashTable* mTable; // Main table pointer.
464 :
465 : private:
466 : char* mStart; // The first entry.
467 : char* mLimit; // One past the last entry.
468 : char* mCurrent; // Pointer to the current entry.
469 : uint32_t mNexts; // Number of Next() calls.
470 : uint32_t mNextsLimit; // Next() call limit.
471 :
472 : bool mHaveRemoved; // Have any elements been removed?
473 :
474 : bool IsOnNonLiveEntry() const;
475 : void MoveToNextEntry();
476 :
477 : Iterator() = delete;
478 : Iterator(const Iterator&) = delete;
479 : Iterator& operator=(const Iterator&) = delete;
480 : Iterator& operator=(const Iterator&&) = delete;
481 : };
482 :
483 454 : Iterator Iter() { return Iterator(this); }
484 :
485 : // Use this if you need to initialize an Iterator in a const method. If you
486 : // use this case, you should not call Remove() on the iterator.
487 39 : Iterator ConstIter() const
488 : {
489 39 : return Iterator(const_cast<PLDHashTable*>(this));
490 : }
491 :
492 : private:
493 : // Multiplicative hash uses an unsigned pointer sized integer and the golden ratio,
494 : // expressed as a fixed-point pointer sized fraction.
495 : static const uint32_t kHashBits = sizeof(size_t) * 8;
496 : #ifdef HAVE_64BIT_BUILD
497 : // Golden ratio borrowed from http://burtleburtle.net/bob/hash/evahash.html.
498 : static const uint64_t kGoldenRatio = 0X9E3779B97F4A7C13ULL;
499 : #else
500 : static const uint32_t kGoldenRatio = 0x9E3779B9U;
501 : #endif
502 :
503 : static uint32_t HashShift(uint32_t aEntrySize, uint32_t aLength);
504 :
505 : static const PLDHashNumber kCollisionFlag = 1;
506 :
507 857893 : static bool EntryIsFree(PLDHashEntryHdr* aEntry)
508 : {
509 857893 : return aEntry->mKeyHash == 0;
510 : }
511 263216 : static bool EntryIsRemoved(PLDHashEntryHdr* aEntry)
512 : {
513 263216 : return aEntry->mKeyHash == 1;
514 : }
515 649317 : static bool EntryIsLive(PLDHashEntryHdr* aEntry)
516 : {
517 649317 : return aEntry->mKeyHash >= 2;
518 : }
519 :
520 8472 : static void MarkEntryFree(PLDHashEntryHdr* aEntry)
521 : {
522 8472 : aEntry->mKeyHash = 0;
523 8472 : }
524 2709 : static void MarkEntryRemoved(PLDHashEntryHdr* aEntry)
525 : {
526 2709 : aEntry->mKeyHash = 1;
527 2709 : }
528 :
529 : PLDHashNumber Hash1(PLDHashNumber aHash0);
530 : void Hash2(PLDHashNumber aHash, size_t& aHash2Out, size_t& aSizeMaskOut);
531 :
532 : static bool MatchEntryKeyhash(PLDHashEntryHdr* aEntry, PLDHashNumber aHash);
533 : PLDHashEntryHdr* AddressEntry(size_t aIndex);
534 :
535 : // We store mHashShift rather than sizeLog2 to optimize the collision-free
536 : // case in SearchTable.
537 218854 : uint32_t CapacityFromHashShift() const
538 : {
539 218854 : return ((uint32_t)1 << (kHashBits - mHashShift));
540 : }
541 :
542 : PLDHashNumber ComputeKeyHash(const void* aKey);
543 :
544 : enum SearchReason { ForSearchOrRemove, ForAdd };
545 :
546 : template <SearchReason Reason>
547 : PLDHashEntryHdr* NS_FASTCALL
548 : SearchTable(const void* aKey, PLDHashNumber aKeyHash);
549 :
550 : PLDHashEntryHdr* FindFreeEntry(PLDHashNumber aKeyHash);
551 :
552 : bool ChangeTable(int aDeltaLog2);
553 :
554 : void ShrinkIfAppropriate();
555 :
556 : PLDHashTable(const PLDHashTable& aOther) = delete;
557 : PLDHashTable& operator=(const PLDHashTable& aOther) = delete;
558 : };
559 :
560 : // Compute the hash code for a given key to be looked up, added, or removed.
561 : // A hash code may have any PLDHashNumber value.
562 : typedef PLDHashNumber (*PLDHashHashKey)(const void* aKey);
563 :
564 : // Compare the key identifying aEntry with the provided key parameter. Return
565 : // true if keys match, false otherwise.
566 : typedef bool (*PLDHashMatchEntry)(const PLDHashEntryHdr* aEntry,
567 : const void* aKey);
568 :
569 : // Copy the data starting at aFrom to the new entry storage at aTo. Do not add
570 : // reference counts for any strong references in the entry, however, as this
571 : // is a "move" operation: the old entry storage at from will be freed without
572 : // any reference-decrementing callback shortly.
573 : typedef void (*PLDHashMoveEntry)(PLDHashTable* aTable,
574 : const PLDHashEntryHdr* aFrom,
575 : PLDHashEntryHdr* aTo);
576 :
577 : // Clear the entry and drop any strong references it holds. This callback is
578 : // invoked by Remove(), but only if the given key is found in the table.
579 : typedef void (*PLDHashClearEntry)(PLDHashTable* aTable,
580 : PLDHashEntryHdr* aEntry);
581 :
582 : // Initialize a new entry, apart from mKeyHash. This function is called when
583 : // Add() finds no existing entry for the given key, and must add a new one. At
584 : // that point, |aEntry->mKeyHash| is not set yet, to avoid claiming the last
585 : // free entry in a severely overloaded table.
586 : typedef void (*PLDHashInitEntry)(PLDHashEntryHdr* aEntry, const void* aKey);
587 :
588 : // Finally, the "vtable" structure for PLDHashTable. The first four hooks
589 : // must be provided by implementations; they're called unconditionally by the
590 : // generic PLDHashTable.cpp code. Hooks after these may be null.
591 : //
592 : // Summary of allocation-related hook usage with C++ placement new emphasis:
593 : // initEntry Call placement new using default key-based ctor.
594 : // moveEntry Call placement new using copy ctor, run dtor on old
595 : // entry storage.
596 : // clearEntry Run dtor on entry.
597 : //
598 : // Note the reason why initEntry is optional: the default hooks (stubs) clear
599 : // entry storage: On successful Add(tbl, key), the returned entry pointer
600 : // addresses an entry struct whose mKeyHash member has been set non-zero, but
601 : // all other entry members are still clear (null). Add() callers can test such
602 : // members to see whether the entry was newly created by the Add() call that
603 : // just succeeded. If placement new or similar initialization is required,
604 : // define an |initEntry| hook. Of course, the |clearEntry| hook must zero or
605 : // null appropriately.
606 : //
607 : // XXX assumes 0 is null for pointer types.
608 : struct PLDHashTableOps
609 : {
610 : // Mandatory hooks. All implementations must provide these.
611 : PLDHashHashKey hashKey;
612 : PLDHashMatchEntry matchEntry;
613 : PLDHashMoveEntry moveEntry;
614 : PLDHashClearEntry clearEntry;
615 :
616 : // Optional hooks start here. If null, these are not called.
617 : PLDHashInitEntry initEntry;
618 : };
619 :
620 : // A minimal entry is a subclass of PLDHashEntryHdr and has a void* key pointer.
621 : struct PLDHashEntryStub : public PLDHashEntryHdr
622 : {
623 : const void* key;
624 : };
625 :
626 : #endif /* PLDHashTable_h */
|
