From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- xpcom/ds/PLDHashTable.h | 807 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 807 insertions(+) create mode 100644 xpcom/ds/PLDHashTable.h (limited to 'xpcom/ds/PLDHashTable.h') diff --git a/xpcom/ds/PLDHashTable.h b/xpcom/ds/PLDHashTable.h new file mode 100644 index 0000000000..f1d741791c --- /dev/null +++ b/xpcom/ds/PLDHashTable.h @@ -0,0 +1,807 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +// See the comment at the top of mfbt/HashTable.h for a comparison between +// PLDHashTable and mozilla::HashTable. + +#ifndef PLDHashTable_h +#define PLDHashTable_h + +#include + +#include "mozilla/Assertions.h" +#include "mozilla/Atomics.h" +#include "mozilla/HashFunctions.h" +#include "mozilla/Maybe.h" +#include "mozilla/MemoryReporting.h" +#include "mozilla/fallible.h" +#include "nscore.h" + +using PLDHashNumber = mozilla::HashNumber; +static const uint32_t kPLDHashNumberBits = mozilla::kHashNumberBits; + +#if defined(DEBUG) || defined(FUZZING) +# define MOZ_HASH_TABLE_CHECKS_ENABLED 1 +#endif + +class PLDHashTable; +struct PLDHashTableOps; + +// Table entry header structure. +// +// In order to allow in-line allocation of key and value, we do not declare +// either here. Instead, the API uses const void *key as a formal parameter. +// The key need not be stored in the entry; it may be part of the value, but +// need not be stored at all. +// +// Callback types are defined below and grouped into the PLDHashTableOps +// structure, for single static initialization per hash table sub-type. +// +// Each hash table sub-type should make its entry type a subclass of +// PLDHashEntryHdr. PLDHashEntryHdr is merely a common superclass to present a +// uniform interface to PLDHashTable clients. The zero-sized base class +// optimization, employed by all of our supported C++ compilers, will ensure +// that this abstraction does not make objects needlessly larger. +struct PLDHashEntryHdr { + PLDHashEntryHdr() = default; + PLDHashEntryHdr(const PLDHashEntryHdr&) = delete; + PLDHashEntryHdr& operator=(const PLDHashEntryHdr&) = delete; + PLDHashEntryHdr(PLDHashEntryHdr&&) = default; + PLDHashEntryHdr& operator=(PLDHashEntryHdr&&) = default; + + private: + friend class PLDHashTable; +}; + +#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED + +// This class does three kinds of checking: +// +// - that calls to one of |mOps| or to an enumerator do not cause re-entry into +// the table in an unsafe way; +// +// - that multiple threads do not access the table in an unsafe way; +// +// - that a table marked as immutable is not modified. +// +// "Safe" here means that multiple concurrent read operations are ok, but a +// write operation (i.e. one that can cause the entry storage to be reallocated +// or destroyed) cannot safely run concurrently with another read or write +// operation. This meaning of "safe" is only partial; for example, it does not +// cover whether a single entry in the table is modified by two separate +// threads. (Doing such checking would be much harder.) +// +// It does this with two variables: +// +// - mState, which embodies a tri-stage tagged union with the following +// variants: +// - Idle +// - Read(n), where 'n' is the number of concurrent read operations +// - Write +// +// - mIsWritable, which indicates if the table is mutable. +// +class Checker { + public: + constexpr Checker() : mState(kIdle), mIsWritable(true) {} + + Checker& operator=(Checker&& aOther) { + // Atomic<> doesn't have an |operator=(Atomic<>&&)|. + mState = uint32_t(aOther.mState); + mIsWritable = bool(aOther.mIsWritable); + + aOther.mState = kIdle; + // XXX Shouldn't we set mIsWritable to true here for consistency? + + return *this; + } + + static bool IsIdle(uint32_t aState) { return aState == kIdle; } + static bool IsRead(uint32_t aState) { + return kRead1 <= aState && aState <= kReadMax; + } + static bool IsRead1(uint32_t aState) { return aState == kRead1; } + static bool IsWrite(uint32_t aState) { return aState == kWrite; } + + bool IsIdle() const { return mState == kIdle; } + + bool IsWritable() const { return mIsWritable; } + + void SetNonWritable() { mIsWritable = false; } + + // NOTE: the obvious way to implement these functions is to (a) check + // |mState| is reasonable, and then (b) update |mState|. But the lack of + // atomicity in such an implementation can cause problems if we get unlucky + // thread interleaving between (a) and (b). + // + // So instead for |mState| we are careful to (a) first get |mState|'s old + // value and assign it a new value in single atomic operation, and only then + // (b) check the old value was reasonable. This ensures we don't have + // interleaving problems. + // + // For |mIsWritable| we don't need to be as careful because it can only in + // transition in one direction (from writable to non-writable). + + void StartReadOp() { + uint32_t oldState = mState++; // this is an atomic increment + MOZ_RELEASE_ASSERT(IsIdle(oldState) || IsRead(oldState)); + MOZ_RELEASE_ASSERT(oldState < kReadMax); // check for overflow + } + + void EndReadOp() { + uint32_t oldState = mState--; // this is an atomic decrement + MOZ_RELEASE_ASSERT(IsRead(oldState)); + } + + void StartWriteOp() { + MOZ_RELEASE_ASSERT(IsWritable()); + uint32_t oldState = mState.exchange(kWrite); + MOZ_RELEASE_ASSERT(IsIdle(oldState)); + } + + void EndWriteOp() { + // Check again that the table is writable, in case it was marked as + // non-writable just after the IsWritable() assertion in StartWriteOp() + // occurred. + MOZ_RELEASE_ASSERT(IsWritable()); + uint32_t oldState = mState.exchange(kIdle); + MOZ_RELEASE_ASSERT(IsWrite(oldState)); + } + + void StartIteratorRemovalOp() { + // When doing removals at the end of iteration, we go from Read1 state to + // Write and then back. + MOZ_RELEASE_ASSERT(IsWritable()); + uint32_t oldState = mState.exchange(kWrite); + MOZ_RELEASE_ASSERT(IsRead1(oldState)); + } + + void EndIteratorRemovalOp() { + // Check again that the table is writable, in case it was marked as + // non-writable just after the IsWritable() assertion in + // StartIteratorRemovalOp() occurred. + MOZ_RELEASE_ASSERT(IsWritable()); + uint32_t oldState = mState.exchange(kRead1); + MOZ_RELEASE_ASSERT(IsWrite(oldState)); + } + + void StartDestructorOp() { + // A destructor op is like a write, but the table doesn't need to be + // writable. + uint32_t oldState = mState.exchange(kWrite); + MOZ_RELEASE_ASSERT(IsIdle(oldState)); + } + + void EndDestructorOp() { + uint32_t oldState = mState.exchange(kIdle); + MOZ_RELEASE_ASSERT(IsWrite(oldState)); + } + + private: + // Things of note about the representation of |mState|. + // - The values between kRead1..kReadMax represent valid Read(n) values. + // - kIdle and kRead1 are deliberately chosen so that incrementing the - + // former gives the latter. + // - 9999 concurrent readers should be enough for anybody. + static const uint32_t kIdle = 0; + static const uint32_t kRead1 = 1; + static const uint32_t kReadMax = 9999; + static const uint32_t kWrite = 10000; + + mozilla::Atomic mState; + mozilla::Atomic mIsWritable; +}; +#endif + +// A PLDHashTable may be allocated on the stack or within another structure or +// class. No entry storage is allocated until the first element is added. This +// means that empty hash tables are cheap, which is good because they are +// common. +// +// There used to be a long, math-heavy comment here about the merits of +// double hashing vs. chaining; it was removed in bug 1058335. In short, double +// hashing is more space-efficient unless the element size gets large (in which +// case you should keep using double hashing but switch to using pointer +// elements). Also, with double hashing, you can't safely hold an entry pointer +// and use it after an add or remove operation, unless you sample Generation() +// before adding or removing, and compare the sample after, dereferencing the +// entry pointer only if Generation() has not changed. +class PLDHashTable { + private: + // A slot represents a cached hash value and its associated entry stored in + // the hash table. The hash value and the entry are not stored contiguously. + struct Slot { + Slot(PLDHashEntryHdr* aEntry, PLDHashNumber* aKeyHash) + : mEntry(aEntry), mKeyHash(aKeyHash) {} + + Slot(const Slot&) = default; + Slot(Slot&& aOther) = default; + + Slot& operator=(Slot&& aOther) = default; + + bool operator==(const Slot& aOther) const { + return mEntry == aOther.mEntry; + } + + PLDHashNumber KeyHash() const { return *HashPtr(); } + void SetKeyHash(PLDHashNumber aHash) { *HashPtr() = aHash; } + + PLDHashEntryHdr* ToEntry() const { return mEntry; } + + bool IsFree() const { return KeyHash() == 0; } + bool IsRemoved() const { return KeyHash() == 1; } + bool IsLive() const { return IsLiveHash(KeyHash()); } + static bool IsLiveHash(uint32_t aHash) { return aHash >= 2; } + + void MarkFree() { *HashPtr() = 0; } + void MarkRemoved() { *HashPtr() = 1; } + void MarkColliding() { *HashPtr() |= kCollisionFlag; } + + void Next(uint32_t aEntrySize) { + char* p = reinterpret_cast(mEntry); + p += aEntrySize; + mEntry = reinterpret_cast(p); + mKeyHash++; + } + PLDHashNumber* HashPtr() const { return mKeyHash; } + + private: + PLDHashEntryHdr* mEntry; + PLDHashNumber* mKeyHash; + }; + + // This class maintains the invariant that every time the entry store is + // changed, the generation is updated. + // + // The data layout separates the cached hashes of entries and the entries + // themselves to save space. We could store the entries thusly: + // + // +--------+--------+---------+ + // | entry0 | entry1 | ... | + // +--------+--------+---------+ + // + // where the entries themselves contain the cached hash stored as their + // first member. PLDHashTable did this for a long time, with entries looking + // like: + // + // class PLDHashEntryHdr + // { + // PLDHashNumber mKeyHash; + // }; + // + // class MyEntry : public PLDHashEntryHdr + // { + // ... + // }; + // + // The problem with this setup is that, depending on the layout of + // `MyEntry`, there may be platform ABI-mandated padding between `mKeyHash` + // and the first member of `MyEntry`. This ABI-mandated padding is wasted + // space, and was surprisingly common, e.g. when MyEntry contained a single + // pointer on 64-bit platforms. + // + // As previously alluded to, the current setup stores things thusly: + // + // +-------+-------+-------+-------+--------+--------+---------+ + // | hash0 | hash1 | ..... | hashN | entry0 | entry1 | ... | + // +-------+-------+-------+-------+--------+--------+---------+ + // + // which contains no wasted space between the hashes themselves, and no + // wasted space between the entries themselves. malloc is guaranteed to + // return blocks of memory with at least word alignment on all of our major + // platforms. PLDHashTable mandates that the size of the hash table is + // always a power of two, so the alignment of the memory containing the + // first entry is always at least the alignment of the entire entry store. + // That means the alignment of `entry0` should be its natural alignment. + // Entries may have problems if they contain over-aligned members such as + // SIMD vector types, but this has not been a problem in practice. + // + // Note: It would be natural to store the generation within this class, but + // we can't do that without bloating sizeof(PLDHashTable) on 64-bit machines. + // So instead we store it outside this class, and Set() takes a pointer to it + // and ensures it is updated as necessary. + class EntryStore { + private: + char* mEntryStore; + + static char* Entries(char* aStore, uint32_t aCapacity) { + return aStore + aCapacity * sizeof(PLDHashNumber); + } + + char* Entries(uint32_t aCapacity) const { + return Entries(Get(), aCapacity); + } + + public: + EntryStore() : mEntryStore(nullptr) {} + + ~EntryStore() { + free(mEntryStore); + mEntryStore = nullptr; + } + + char* Get() const { return mEntryStore; } + bool IsAllocated() const { return !!mEntryStore; } + + Slot SlotForIndex(uint32_t aIndex, uint32_t aEntrySize, + uint32_t aCapacity) const { + char* entries = Entries(aCapacity); + auto entry = + reinterpret_cast(entries + aIndex * aEntrySize); + auto hashes = reinterpret_cast(Get()); + return Slot(entry, &hashes[aIndex]); + } + + Slot SlotForPLDHashEntry(PLDHashEntryHdr* aEntry, uint32_t aCapacity, + uint32_t aEntrySize) { + char* entries = Entries(aCapacity); + char* entry = reinterpret_cast(aEntry); + uint32_t entryOffset = entry - entries; + uint32_t slotIndex = entryOffset / aEntrySize; + return SlotForIndex(slotIndex, aEntrySize, aCapacity); + } + + template + void ForEachSlot(uint32_t aCapacity, uint32_t aEntrySize, F&& aFunc) { + ForEachSlot(Get(), aCapacity, aEntrySize, std::move(aFunc)); + } + + template + static void ForEachSlot(char* aStore, uint32_t aCapacity, + uint32_t aEntrySize, F&& aFunc) { + char* entries = Entries(aStore, aCapacity); + Slot slot(reinterpret_cast(entries), + reinterpret_cast(aStore)); + for (size_t i = 0; i < aCapacity; ++i) { + aFunc(slot); + slot.Next(aEntrySize); + } + } + + void Set(char* aEntryStore, uint16_t* aGeneration) { + mEntryStore = aEntryStore; + *aGeneration += 1; + } + }; + + // These fields are packed carefully. On 32-bit platforms, + // sizeof(PLDHashTable) is 20. On 64-bit platforms, sizeof(PLDHashTable) is + // 32; 28 bytes of data followed by 4 bytes of padding for alignment. + const PLDHashTableOps* const mOps; // Virtual operations; see below. + EntryStore mEntryStore; // (Lazy) entry storage and generation. + uint16_t mGeneration; // The storage generation. + uint8_t mHashShift; // Multiplicative hash shift. + const uint8_t mEntrySize; // Number of bytes in an entry. + uint32_t mEntryCount; // Number of entries in table. + uint32_t mRemovedCount; // Removed entry sentinels in table. + +#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED + mutable Checker mChecker; +#endif + + public: + // Table capacity limit; do not exceed. The max capacity used to be 1<<23 but + // that occasionally that wasn't enough. Making it much bigger than 1<<26 + // probably isn't worthwhile -- tables that big are kind of ridiculous. + // Also, the growth operation will (deliberately) fail if |capacity * + // mEntrySize| overflows a uint32_t, and mEntrySize is always at least 8 + // bytes. + static const uint32_t kMaxCapacity = ((uint32_t)1 << 26); + + static const uint32_t kMinCapacity = 8; + + // Making this half of kMaxCapacity ensures it'll fit. Nobody should need an + // initial length anywhere nearly this large, anyway. + static const uint32_t kMaxInitialLength = kMaxCapacity / 2; + + // This gives a default initial capacity of 8. + static const uint32_t kDefaultInitialLength = 4; + + // Initialize the table with |aOps| and |aEntrySize|. The table's initial + // capacity is chosen such that |aLength| elements can be inserted without + // rehashing; if |aLength| is a power-of-two, this capacity will be + // |2*length|. However, because entry storage is allocated lazily, this + // initial capacity won't be relevant until the first element is added; prior + // to that the capacity will be zero. + // + // This will crash if |aEntrySize| and/or |aLength| are too large. + PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize, + uint32_t aLength = kDefaultInitialLength); + + PLDHashTable(PLDHashTable&& aOther) + // Initialize fields which are checked by the move assignment operator + // and the destructor (which the move assignment operator calls). + : mOps(nullptr), mGeneration(0), mEntrySize(0) { + *this = std::move(aOther); + } + + PLDHashTable& operator=(PLDHashTable&& aOther); + + ~PLDHashTable(); + + // This should be used rarely. + const PLDHashTableOps* Ops() const { return mOps; } + + // Size in entries (gross, not net of free and removed sentinels) for table. + // This can be zero if no elements have been added yet, in which case the + // entry storage will not have yet been allocated. + uint32_t Capacity() const { + return mEntryStore.IsAllocated() ? CapacityFromHashShift() : 0; + } + + uint32_t EntrySize() const { return mEntrySize; } + uint32_t EntryCount() const { return mEntryCount; } + uint32_t Generation() const { return mGeneration; } + + // To search for a |key| in |table|, call: + // + // entry = table.Search(key); + // + // If |entry| is non-null, |key| was found. If |entry| is null, key was not + // found. + PLDHashEntryHdr* Search(const void* aKey) const; + + // To add an entry identified by |key| to table, call: + // + // entry = table.Add(key, mozilla::fallible); + // + // If |entry| is null upon return, then the table is severely overloaded and + // memory can't be allocated for entry storage. + // + // Otherwise, if the initEntry hook was provided, |entry| will be + // initialized. If the initEntry hook was not provided, the caller + // should initialize |entry| as appropriate. + PLDHashEntryHdr* Add(const void* aKey, const mozilla::fallible_t&); + + // This is like the other Add() function, but infallible, and so never + // returns null. + PLDHashEntryHdr* Add(const void* aKey); + + // To remove an entry identified by |key| from table, call: + // + // table.Remove(key); + // + // If |key|'s entry is found, it is cleared (via table->mOps->clearEntry). + // The table's capacity may be reduced afterwards. + void Remove(const void* aKey); + + // To remove an entry found by a prior search, call: + // + // table.RemoveEntry(entry); + // + // The entry, which must be present and in use, is cleared (via + // table->mOps->clearEntry). The table's capacity may be reduced afterwards. + void RemoveEntry(PLDHashEntryHdr* aEntry); + + // Remove an entry already accessed via Search() or Add(). + // + // NB: this is a "raw" or low-level method. It does not shrink the table if + // it is underloaded. Don't use it unless necessary and you know what you are + // doing, and if so, please explain in a comment why it is necessary instead + // of RemoveEntry(). + void RawRemove(PLDHashEntryHdr* aEntry); + + // This function is equivalent to + // ClearAndPrepareForLength(kDefaultInitialLength). + void Clear(); + + // This function clears the table's contents and frees its entry storage, + // leaving it in a empty state ready to be used again. Afterwards, when the + // first element is added the entry storage that gets allocated will have a + // capacity large enough to fit |aLength| elements without rehashing. + // + // It's conceptually the same as calling the destructor and then re-calling + // the constructor with the original |aOps| and |aEntrySize| arguments, and + // a new |aLength| argument. + void ClearAndPrepareForLength(uint32_t aLength); + + // Measure the size of the table's entry storage. If the entries contain + // pointers to other heap blocks, you have to iterate over the table and + // measure those separately; hence the "Shallow" prefix. + size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const; + + // Like ShallowSizeOfExcludingThis(), but includes sizeof(*this). + size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const; + + // Mark a table as immutable for the remainder of its lifetime. This + // changes the implementation from asserting one set of invariants to + // asserting a different set. + void MarkImmutable() { +#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED + mChecker.SetNonWritable(); +#endif + } + + // If you use PLDHashEntryStub or a subclass of it as your entry struct, and + // if your entries move via memcpy and clear via memset(0), you can use these + // stub operations. + static const PLDHashTableOps* StubOps(); + + // The individual stub operations in StubOps(). + static PLDHashNumber HashVoidPtrKeyStub(const void* aKey); + static bool MatchEntryStub(const PLDHashEntryHdr* aEntry, const void* aKey); + static void MoveEntryStub(PLDHashTable* aTable, const PLDHashEntryHdr* aFrom, + PLDHashEntryHdr* aTo); + static void ClearEntryStub(PLDHashTable* aTable, PLDHashEntryHdr* aEntry); + + // Hash/match operations for tables holding C strings. + static PLDHashNumber HashStringKey(const void* aKey); + static bool MatchStringKey(const PLDHashEntryHdr* aEntry, const void* aKey); + + class EntryHandle { + public: + EntryHandle(EntryHandle&& aOther) noexcept; +#ifdef MOZ_HASH_TABLE_CHECKS_ENABLED + ~EntryHandle(); +#endif + + EntryHandle(const EntryHandle&) = delete; + EntryHandle& operator=(const EntryHandle&) = delete; + EntryHandle& operator=(EntryHandle&& aOther) = delete; + + // Is this slot currently occupied? + bool HasEntry() const { return mSlot.IsLive(); } + + explicit operator bool() const { return HasEntry(); } + + // Get the entry stored in this slot. May not be called unless the slot is + // currently occupied. + PLDHashEntryHdr* Entry() { + MOZ_ASSERT(HasEntry()); + return mSlot.ToEntry(); + } + + template + void Insert(F&& aInitEntry) { + MOZ_ASSERT(!HasEntry()); + OccupySlot(); + std::forward(aInitEntry)(Entry()); + } + + // If the slot is currently vacant, the slot is occupied and `initEntry` is + // invoked to initialize the entry. Returns the entry stored in now-occupied + // slot. + template + PLDHashEntryHdr* OrInsert(F&& aInitEntry) { + if (!HasEntry()) { + Insert(std::forward(aInitEntry)); + } + return Entry(); + } + + /** Removes the entry. Note that the table won't shrink on destruction of + * the EntryHandle. + * + * \pre HasEntry() + * \post !HasEntry() + */ + void Remove(); + + /** Removes the entry, if it exists. Note that the table won't shrink on + * destruction of the EntryHandle. + * + * \post !HasEntry() + */ + void OrRemove(); + + private: + friend class PLDHashTable; + + EntryHandle(PLDHashTable* aTable, PLDHashNumber aKeyHash, Slot aSlot); + + void OccupySlot(); + + PLDHashTable* mTable; + PLDHashNumber mKeyHash; + Slot mSlot; + }; + + template + auto WithEntryHandle(const void* aKey, F&& aFunc) + -> std::invoke_result_t { + return std::forward(aFunc)(MakeEntryHandle(aKey)); + } + + template + auto WithEntryHandle(const void* aKey, const mozilla::fallible_t& aFallible, + F&& aFunc) + -> std::invoke_result_t&&> { + return std::forward(aFunc)(MakeEntryHandle(aKey, aFallible)); + } + + // This is an iterator for PLDHashtable. Assertions will detect some, but not + // all, mid-iteration table modifications that might invalidate (e.g. + // reallocate) the entry storage. + // + // Any element can be removed during iteration using Remove(). If any + // elements are removed, the table may be resized once iteration ends. + // + // Example usage: + // + // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) { + // auto entry = static_cast(iter.Get()); + // // ... do stuff with |entry| ... + // // ... possibly call iter.Remove() once ... + // } + // + // or: + // + // for (PLDHashTable::Iterator iter(&table); !iter.Done(); iter.Next()) { + // auto entry = static_cast(iter.Get()); + // // ... do stuff with |entry| ... + // // ... possibly call iter.Remove() once ... + // } + // + // The latter form is more verbose but is easier to work with when + // making subclasses of Iterator. + // + class Iterator { + public: + explicit Iterator(PLDHashTable* aTable); + struct EndIteratorTag {}; + Iterator(PLDHashTable* aTable, EndIteratorTag aTag); + Iterator(Iterator&& aOther); + ~Iterator(); + + // Have we finished? + bool Done() const { return mNexts == mNextsLimit; } + + // Get the current entry. + PLDHashEntryHdr* Get() const { + MOZ_ASSERT(!Done()); + MOZ_ASSERT(mCurrent.IsLive()); + return mCurrent.ToEntry(); + } + + // Advance to the next entry. + void Next(); + + // Remove the current entry. Must only be called once per entry, and Get() + // must not be called on that entry afterwards. + void Remove(); + + bool operator==(const Iterator& aOther) const { + MOZ_ASSERT(mTable == aOther.mTable); + return mNexts == aOther.mNexts; + } + + Iterator Clone() const { return {*this}; } + + protected: + PLDHashTable* mTable; // Main table pointer. + + private: + Slot mCurrent; // Pointer to the current entry. + uint32_t mNexts; // Number of Next() calls. + uint32_t mNextsLimit; // Next() call limit. + + bool mHaveRemoved; // Have any elements been removed? + uint8_t mEntrySize; // Size of entries. + + bool IsOnNonLiveEntry() const; + + void MoveToNextLiveEntry(); + + Iterator() = delete; + Iterator(const Iterator&); + Iterator& operator=(const Iterator&) = delete; + Iterator& operator=(const Iterator&&) = delete; + }; + + Iterator Iter() { return Iterator(this); } + + // Use this if you need to initialize an Iterator in a const method. If you + // use this case, you should not call Remove() on the iterator. + Iterator ConstIter() const { + return Iterator(const_cast(this)); + } + + private: + static uint32_t HashShift(uint32_t aEntrySize, uint32_t aLength); + + static const PLDHashNumber kCollisionFlag = 1; + + PLDHashNumber Hash1(PLDHashNumber aHash0) const; + void Hash2(PLDHashNumber aHash, uint32_t& aHash2Out, + uint32_t& aSizeMaskOut) const; + + static bool MatchSlotKeyhash(Slot& aSlot, const PLDHashNumber aHash); + Slot SlotForIndex(uint32_t aIndex) const; + + // We store mHashShift rather than sizeLog2 to optimize the collision-free + // case in SearchTable. + uint32_t CapacityFromHashShift() const { + return ((uint32_t)1 << (kPLDHashNumberBits - mHashShift)); + } + + PLDHashNumber ComputeKeyHash(const void* aKey) const; + + enum SearchReason { ForSearchOrRemove, ForAdd }; + + // Avoid using bare `Success` and `Failure`, as those names are commonly + // defined as macros. + template + auto SearchTable(const void* aKey, PLDHashNumber aKeyHash, + PLDSuccess&& aSucess, PLDFailure&& aFailure) const; + + Slot FindFreeSlot(PLDHashNumber aKeyHash) const; + + bool ChangeTable(int aDeltaLog2); + + void RawRemove(Slot& aSlot); + void ShrinkIfAppropriate(); + + mozilla::Maybe MakeEntryHandle(const void* aKey, + const mozilla::fallible_t&); + + EntryHandle MakeEntryHandle(const void* aKey); + + PLDHashTable(const PLDHashTable& aOther) = delete; + PLDHashTable& operator=(const PLDHashTable& aOther) = delete; +}; + +// Compute the hash code for a given key to be looked up, added, or removed. +// A hash code may have any PLDHashNumber value. +typedef PLDHashNumber (*PLDHashHashKey)(const void* aKey); + +// Compare the key identifying aEntry with the provided key parameter. Return +// true if keys match, false otherwise. +typedef bool (*PLDHashMatchEntry)(const PLDHashEntryHdr* aEntry, + const void* aKey); + +// Copy the data starting at aFrom to the new entry storage at aTo. Do not add +// reference counts for any strong references in the entry, however, as this +// is a "move" operation: the old entry storage at from will be freed without +// any reference-decrementing callback shortly. +typedef void (*PLDHashMoveEntry)(PLDHashTable* aTable, + const PLDHashEntryHdr* aFrom, + PLDHashEntryHdr* aTo); + +// Clear the entry and drop any strong references it holds. This callback is +// invoked by Remove(), but only if the given key is found in the table. +typedef void (*PLDHashClearEntry)(PLDHashTable* aTable, + PLDHashEntryHdr* aEntry); + +// Initialize a new entry. This function is called when +// Add() finds no existing entry for the given key, and must add a new one. +typedef void (*PLDHashInitEntry)(PLDHashEntryHdr* aEntry, const void* aKey); + +// Finally, the "vtable" structure for PLDHashTable. The first four hooks +// must be provided by implementations; they're called unconditionally by the +// generic PLDHashTable.cpp code. Hooks after these may be null. +// +// Summary of allocation-related hook usage with C++ placement new emphasis: +// initEntry Call placement new using default key-based ctor. +// moveEntry Call placement new using copy ctor, run dtor on old +// entry storage. +// clearEntry Run dtor on entry. +// +// Note the reason why initEntry is optional: the default hooks (stubs) clear +// entry storage. On a successful Add(tbl, key), the returned entry pointer +// addresses an entry struct whose entry members are still clear (null). Add() +// callers can test such members to see whether the entry was newly created by +// the Add() call that just succeeded. If placement new or similar +// initialization is required, define an |initEntry| hook. Of course, the +// |clearEntry| hook must zero or null appropriately. +// +// XXX assumes 0 is null for pointer types. +struct PLDHashTableOps { + // Mandatory hooks. All implementations must provide these. + PLDHashHashKey hashKey; + PLDHashMatchEntry matchEntry; + PLDHashMoveEntry moveEntry; + + // Optional hooks start here. If null, these are not called. + PLDHashClearEntry clearEntry; + PLDHashInitEntry initEntry; +}; + +// A minimal entry is a subclass of PLDHashEntryHdr and has a void* key pointer. +struct PLDHashEntryStub : public PLDHashEntryHdr { + const void* key; +}; + +#endif /* PLDHashTable_h */ -- cgit v1.2.3