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 uint32_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 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: Checker()78 constexpr Checker() : mState(kIdle), mIsWritable(1) {} 79 80 Checker& operator=(Checker&& aOther) { 81 // Atomic<> doesn't have an |operator=(Atomic<>&&)|. 82 mState = uint32_t(aOther.mState); 83 mIsWritable = uint32_t(aOther.mIsWritable); 84 85 aOther.mState = kIdle; 86 87 return *this; 88 } 89 IsIdle(uint32_t aState)90 static bool IsIdle(uint32_t aState) { return aState == kIdle; } IsRead(uint32_t aState)91 static bool IsRead(uint32_t aState) { return kRead1 <= aState && 92 aState <= kReadMax; } IsRead1(uint32_t aState)93 static bool IsRead1(uint32_t aState) { return aState == kRead1; } IsWrite(uint32_t aState)94 static bool IsWrite(uint32_t aState) { return aState == kWrite; } 95 IsIdle()96 bool IsIdle() const { return mState == kIdle; } 97 IsWritable()98 bool IsWritable() const { return !!mIsWritable; } 99 SetNonWritable()100 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 StartReadOp()115 void StartReadOp() 116 { 117 uint32_t oldState = mState++; // this is an atomic increment 118 MOZ_ASSERT(IsIdle(oldState) || IsRead(oldState)); 119 MOZ_ASSERT(oldState < kReadMax); // check for overflow 120 } 121 EndReadOp()122 void EndReadOp() 123 { 124 uint32_t oldState = mState--; // this is an atomic decrement 125 MOZ_ASSERT(IsRead(oldState)); 126 } 127 StartWriteOp()128 void StartWriteOp() 129 { 130 MOZ_ASSERT(IsWritable()); 131 uint32_t oldState = mState.exchange(kWrite); 132 MOZ_ASSERT(IsIdle(oldState)); 133 } 134 EndWriteOp()135 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 MOZ_ASSERT(IsWritable()); 141 uint32_t oldState = mState.exchange(kIdle); 142 MOZ_ASSERT(IsWrite(oldState)); 143 } 144 StartIteratorRemovalOp()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 EndIteratorRemovalOp()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 StartDestructorOp()164 void StartDestructorOp() 165 { 166 // A destructor op is like a write, but the table doesn't need to be 167 // writable. 168 uint32_t oldState = mState.exchange(kWrite); 169 MOZ_ASSERT(IsIdle(oldState)); 170 } 171 EndDestructorOp()172 void EndDestructorOp() 173 { 174 uint32_t oldState = mState.exchange(kIdle); 175 MOZ_ASSERT(IsWrite(oldState)); 176 } 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: EntryStore()219 EntryStore() : mEntryStore(nullptr), mGeneration(0) {} 220 ~EntryStore()221 ~EntryStore() 222 { 223 free(mEntryStore); 224 mEntryStore = nullptr; 225 mGeneration++; // a little paranoid, but why not be extra safe? 226 } 227 Get()228 char* Get() { return mEntryStore; } Get()229 const char* Get() const { return mEntryStore; } 230 Set(char * aEntryStore)231 void Set(char* aEntryStore) 232 { 233 mEntryStore = aEntryStore; 234 mGeneration++; 235 } 236 Generation()237 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 PLDHashTable(PLDHashTable && aOther)280 PLDHashTable(PLDHashTable&& aOther) 281 // These two fields are |const|. Initialize them here because the 282 // move assignment operator cannot modify them. 283 : mOps(aOther.mOps) 284 , 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 , mChecker() 290 #endif 291 { 292 *this = mozilla::Move(aOther); 293 } 294 295 PLDHashTable& operator=(PLDHashTable&& aOther); 296 297 ~PLDHashTable(); 298 299 // This should be used rarely. Ops()300 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. Capacity()305 uint32_t Capacity() const 306 { 307 return mEntryStore.Get() ? CapacityFromHashShift() : 0; 308 } 309 EntrySize()310 uint32_t EntrySize() const { return mEntrySize; } EntryCount()311 uint32_t EntryCount() const { return mEntryCount; } Generation()312 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? Done()443 bool Done() const { return mNexts == mNextsLimit; } 444 445 // Get the current entry. Get()446 PLDHashEntryHdr* Get() const 447 { 448 MOZ_ASSERT(!Done()); 449 450 PLDHashEntryHdr* entry = reinterpret_cast<PLDHashEntryHdr*>(mCurrent); 451 MOZ_ASSERT(EntryIsLive(entry)); 452 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 Iter()483 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. ConstIter()487 Iterator ConstIter() const 488 { 489 return Iterator(const_cast<PLDHashTable*>(this)); 490 } 491 492 private: 493 // Multiplicative hash uses an unsigned 32 bit integer and the golden ratio, 494 // expressed as a fixed-point 32-bit fraction. 495 static const uint32_t kHashBits = 32; 496 static const uint32_t kGoldenRatio = 0x9E3779B9U; 497 498 static uint32_t HashShift(uint32_t aEntrySize, uint32_t aLength); 499 500 static const PLDHashNumber kCollisionFlag = 1; 501 EntryIsFree(PLDHashEntryHdr * aEntry)502 static bool EntryIsFree(PLDHashEntryHdr* aEntry) 503 { 504 return aEntry->mKeyHash == 0; 505 } EntryIsRemoved(PLDHashEntryHdr * aEntry)506 static bool EntryIsRemoved(PLDHashEntryHdr* aEntry) 507 { 508 return aEntry->mKeyHash == 1; 509 } EntryIsLive(PLDHashEntryHdr * aEntry)510 static bool EntryIsLive(PLDHashEntryHdr* aEntry) 511 { 512 return aEntry->mKeyHash >= 2; 513 } 514 MarkEntryFree(PLDHashEntryHdr * aEntry)515 static void MarkEntryFree(PLDHashEntryHdr* aEntry) 516 { 517 aEntry->mKeyHash = 0; 518 } MarkEntryRemoved(PLDHashEntryHdr * aEntry)519 static void MarkEntryRemoved(PLDHashEntryHdr* aEntry) 520 { 521 aEntry->mKeyHash = 1; 522 } 523 524 PLDHashNumber Hash1(PLDHashNumber aHash0); 525 void Hash2(PLDHashNumber aHash, uint32_t& aHash2Out, uint32_t& aSizeMaskOut); 526 527 static bool MatchEntryKeyhash(PLDHashEntryHdr* aEntry, PLDHashNumber aHash); 528 PLDHashEntryHdr* AddressEntry(uint32_t aIndex); 529 530 // We store mHashShift rather than sizeLog2 to optimize the collision-free 531 // case in SearchTable. CapacityFromHashShift()532 uint32_t CapacityFromHashShift() const 533 { 534 return ((uint32_t)1 << (kHashBits - mHashShift)); 535 } 536 537 PLDHashNumber ComputeKeyHash(const void* aKey); 538 539 enum SearchReason { ForSearchOrRemove, ForAdd }; 540 541 template <SearchReason Reason> 542 PLDHashEntryHdr* NS_FASTCALL 543 SearchTable(const void* aKey, PLDHashNumber aKeyHash); 544 545 PLDHashEntryHdr* FindFreeEntry(PLDHashNumber aKeyHash); 546 547 bool ChangeTable(int aDeltaLog2); 548 549 void ShrinkIfAppropriate(); 550 551 PLDHashTable(const PLDHashTable& aOther) = delete; 552 PLDHashTable& operator=(const PLDHashTable& aOther) = delete; 553 }; 554 555 // Compute the hash code for a given key to be looked up, added, or removed. 556 // A hash code may have any PLDHashNumber value. 557 typedef PLDHashNumber (*PLDHashHashKey)(const void* aKey); 558 559 // Compare the key identifying aEntry with the provided key parameter. Return 560 // true if keys match, false otherwise. 561 typedef bool (*PLDHashMatchEntry)(const PLDHashEntryHdr* aEntry, 562 const void* aKey); 563 564 // Copy the data starting at aFrom to the new entry storage at aTo. Do not add 565 // reference counts for any strong references in the entry, however, as this 566 // is a "move" operation: the old entry storage at from will be freed without 567 // any reference-decrementing callback shortly. 568 typedef void (*PLDHashMoveEntry)(PLDHashTable* aTable, 569 const PLDHashEntryHdr* aFrom, 570 PLDHashEntryHdr* aTo); 571 572 // Clear the entry and drop any strong references it holds. This callback is 573 // invoked by Remove(), but only if the given key is found in the table. 574 typedef void (*PLDHashClearEntry)(PLDHashTable* aTable, 575 PLDHashEntryHdr* aEntry); 576 577 // Initialize a new entry, apart from mKeyHash. This function is called when 578 // Add() finds no existing entry for the given key, and must add a new one. At 579 // that point, |aEntry->mKeyHash| is not set yet, to avoid claiming the last 580 // free entry in a severely overloaded table. 581 typedef void (*PLDHashInitEntry)(PLDHashEntryHdr* aEntry, const void* aKey); 582 583 // Finally, the "vtable" structure for PLDHashTable. The first four hooks 584 // must be provided by implementations; they're called unconditionally by the 585 // generic PLDHashTable.cpp code. Hooks after these may be null. 586 // 587 // Summary of allocation-related hook usage with C++ placement new emphasis: 588 // initEntry Call placement new using default key-based ctor. 589 // moveEntry Call placement new using copy ctor, run dtor on old 590 // entry storage. 591 // clearEntry Run dtor on entry. 592 // 593 // Note the reason why initEntry is optional: the default hooks (stubs) clear 594 // entry storage: On successful Add(tbl, key), the returned entry pointer 595 // addresses an entry struct whose mKeyHash member has been set non-zero, but 596 // all other entry members are still clear (null). Add() callers can test such 597 // members to see whether the entry was newly created by the Add() call that 598 // just succeeded. If placement new or similar initialization is required, 599 // define an |initEntry| hook. Of course, the |clearEntry| hook must zero or 600 // null appropriately. 601 // 602 // XXX assumes 0 is null for pointer types. 603 struct PLDHashTableOps 604 { 605 // Mandatory hooks. All implementations must provide these. 606 PLDHashHashKey hashKey; 607 PLDHashMatchEntry matchEntry; 608 PLDHashMoveEntry moveEntry; 609 PLDHashClearEntry clearEntry; 610 611 // Optional hooks start here. If null, these are not called. 612 PLDHashInitEntry initEntry; 613 }; 614 615 // A minimal entry is a subclass of PLDHashEntryHdr and has a void* key pointer. 616 struct PLDHashEntryStub : public PLDHashEntryHdr 617 { 618 const void* key; 619 }; 620 621 #endif /* PLDHashTable_h */ 622