diff options
Diffstat (limited to '')
| -rw-r--r-- | xpcom/ds/nsBaseHashtable.h | 1029 |
1 files changed, 1029 insertions, 0 deletions
diff --git a/xpcom/ds/nsBaseHashtable.h b/xpcom/ds/nsBaseHashtable.h new file mode 100644 index 0000000000..7b57ef4666 --- /dev/null +++ b/xpcom/ds/nsBaseHashtable.h @@ -0,0 +1,1029 @@ +/* -*- 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/. */ + +#ifndef nsBaseHashtable_h__ +#define nsBaseHashtable_h__ + +#include <functional> +#include <utility> + +#include "mozilla/dom/SafeRefPtr.h" +#include "mozilla/Maybe.h" +#include "mozilla/MemoryReporting.h" +#include "mozilla/RefPtr.h" +#include "mozilla/Result.h" +#include "mozilla/UniquePtr.h" +#include "nsCOMPtr.h" +#include "nsDebug.h" +#include "nsHashtablesFwd.h" +#include "nsTHashtable.h" + +namespace mozilla::detail { + +template <typename SmartPtr> +struct SmartPtrTraits { + static constexpr bool IsSmartPointer = false; + static constexpr bool IsRefCounted = false; +}; + +template <typename Pointee> +struct SmartPtrTraits<UniquePtr<Pointee>> { + static constexpr bool IsSmartPointer = true; + static constexpr bool IsRefCounted = false; + using SmartPointerType = UniquePtr<Pointee>; + using PointeeType = Pointee; + using RawPointerType = Pointee*; + template <typename U> + using OtherSmartPtrType = UniquePtr<U>; + + template <typename U, typename... Args> + static SmartPointerType NewObject(Args&&... aConstructionArgs) { + return mozilla::MakeUnique<U>(std::forward<Args>(aConstructionArgs)...); + } +}; + +template <typename Pointee> +struct SmartPtrTraits<RefPtr<Pointee>> { + static constexpr bool IsSmartPointer = true; + static constexpr bool IsRefCounted = true; + using SmartPointerType = RefPtr<Pointee>; + using PointeeType = Pointee; + using RawPointerType = Pointee*; + template <typename U> + using OtherSmartPtrType = RefPtr<U>; + + template <typename U, typename... Args> + static SmartPointerType NewObject(Args&&... aConstructionArgs) { + return MakeRefPtr<U>(std::forward<Args>(aConstructionArgs)...); + } +}; + +template <typename Pointee> +struct SmartPtrTraits<SafeRefPtr<Pointee>> { + static constexpr bool IsSmartPointer = true; + static constexpr bool IsRefCounted = true; + using SmartPointerType = SafeRefPtr<Pointee>; + using PointeeType = Pointee; + using RawPointerType = Pointee*; + template <typename U> + using OtherSmartPtrType = SafeRefPtr<U>; + + template <typename U, typename... Args> + static SmartPointerType NewObject(Args&&... aConstructionArgs) { + return MakeSafeRefPtr<U>(std::forward<Args>(aConstructionArgs)...); + } +}; + +template <typename Pointee> +struct SmartPtrTraits<nsCOMPtr<Pointee>> { + static constexpr bool IsSmartPointer = true; + static constexpr bool IsRefCounted = true; + using SmartPointerType = nsCOMPtr<Pointee>; + using PointeeType = Pointee; + using RawPointerType = Pointee*; + template <typename U> + using OtherSmartPtrType = nsCOMPtr<U>; + + template <typename U, typename... Args> + static SmartPointerType NewObject(Args&&... aConstructionArgs) { + return MakeRefPtr<U>(std::forward<Args>(aConstructionArgs)...); + } +}; + +template <class T> +T* PtrGetWeak(T* aPtr) { + return aPtr; +} + +template <class T> +T* PtrGetWeak(const RefPtr<T>& aPtr) { + return aPtr.get(); +} + +template <class T> +T* PtrGetWeak(const SafeRefPtr<T>& aPtr) { + return aPtr.unsafeGetRawPtr(); +} + +template <class T> +T* PtrGetWeak(const nsCOMPtr<T>& aPtr) { + return aPtr.get(); +} + +template <class T> +T* PtrGetWeak(const UniquePtr<T>& aPtr) { + return aPtr.get(); +} + +template <typename EntryType> +class nsBaseHashtableValueIterator : public ::detail::nsTHashtableIteratorBase { + // friend class nsTHashtable<EntryType>; + + public: + using iterator_category = std::forward_iterator_tag; + using value_type = const std::decay_t<typename EntryType::DataType>; + using difference_type = int32_t; + using pointer = value_type*; + using reference = value_type&; + + using iterator_type = nsBaseHashtableValueIterator; + using const_iterator_type = nsBaseHashtableValueIterator; + + using nsTHashtableIteratorBase::nsTHashtableIteratorBase; + + value_type* operator->() const { + return &static_cast<const EntryType*>(mIterator.Get())->GetData(); + } + decltype(auto) operator*() const { + return static_cast<const EntryType*>(mIterator.Get())->GetData(); + } + + iterator_type& operator++() { + mIterator.Next(); + return *this; + } + iterator_type operator++(int) { + iterator_type it = *this; + ++*this; + return it; + } +}; + +template <typename EntryType> +class nsBaseHashtableValueRange { + public: + using IteratorType = nsBaseHashtableValueIterator<EntryType>; + using iterator = IteratorType; + + explicit nsBaseHashtableValueRange(const PLDHashTable& aHashtable) + : mHashtable{aHashtable} {} + + auto begin() const { return IteratorType{mHashtable}; } + auto end() const { + return IteratorType{mHashtable, typename IteratorType::EndIteratorTag{}}; + } + auto cbegin() const { return begin(); } + auto cend() const { return end(); } + + uint32_t Count() const { return mHashtable.EntryCount(); } + + private: + const PLDHashTable& mHashtable; +}; + +template <typename EntryType> +auto RangeSize(const detail::nsBaseHashtableValueRange<EntryType>& aRange) { + return aRange.Count(); +} + +} // namespace mozilla::detail + +/** + * Data type conversion helper that is used to wrap and unwrap the specified + * DataType. + */ +template <class DataType, class UserDataType> +class nsDefaultConverter { + public: + /** + * Maps the storage DataType to the exposed UserDataType. + */ + static UserDataType Unwrap(DataType& src) { return UserDataType(src); } + + /** + * Const ref variant used for example with nsCOMPtr wrappers. + */ + static DataType Wrap(const UserDataType& src) { return DataType(src); } + + /** + * Generic conversion, this is useful for things like already_AddRefed. + */ + template <typename U> + static DataType Wrap(U&& src) { + return std::forward<U>(src); + } + + template <typename U> + static UserDataType Unwrap(U&& src) { + return std::forward<U>(src); + } +}; + +/** + * the private nsTHashtable::EntryType class used by nsBaseHashtable + * @see nsTHashtable for the specification of this class + * @see nsBaseHashtable for template parameters + */ +template <class KeyClass, class TDataType> +class nsBaseHashtableET : public KeyClass { + public: + using DataType = TDataType; + + const DataType& GetData() const { return mData; } + DataType* GetModifiableData() { return &mData; } + template <typename U> + void SetData(U&& aData) { + mData = std::forward<U>(aData); + } + + decltype(auto) GetWeak() const { + return mozilla::detail::PtrGetWeak(GetData()); + } + + private: + DataType mData; + friend class nsTHashtable<nsBaseHashtableET<KeyClass, DataType>>; + template <typename KeyClassX, typename DataTypeX, typename UserDataTypeX, + typename ConverterX> + friend class nsBaseHashtable; + friend class ::detail::nsTHashtableKeyIterator< + nsBaseHashtableET<KeyClass, DataType>>; + + typedef typename KeyClass::KeyType KeyType; + typedef typename KeyClass::KeyTypePointer KeyTypePointer; + + template <typename... Args> + explicit nsBaseHashtableET(KeyTypePointer aKey, Args&&... aArgs); + nsBaseHashtableET(nsBaseHashtableET<KeyClass, DataType>&& aToMove) = default; + ~nsBaseHashtableET() = default; +}; + +/** + * Templated hashtable. Usually, this isn't instantiated directly but through + * its sub-class templates nsInterfaceHashtable, nsClassHashtable, + * nsRefPtrHashtable and nsTHashMap. + * + * Originally, UserDataType used to be the only type exposed to the user in the + * public member function signatures (hence its name), but this has proven to + * inadequate over time. Now, UserDataType is only exposed in by-value + * getter member functions that are called *Get*. Member functions that provide + * access to the DataType are called Lookup rather than Get. Note that this rule + * does not apply to nsRefPtrHashtable and nsInterfaceHashtable, as they are + * provide a similar interface, but are no genuine sub-classes of + * nsBaseHashtable. + * + * @param KeyClass a wrapper-class for the hashtable key, see nsHashKeys.h + * for a complete specification. + * @param DataType the datatype stored in the hashtable, + * for example, uint32_t or nsCOMPtr. + * @param UserDataType the datatype returned from the by-value getter member + * functions (named *Get*), for example uint32_t or nsISupports* + * @param Converter that is used to map from DataType to UserDataType. A + * default converter is provided that assumes implicit conversion is an + * option. + */ +template <class KeyClass, class DataType, class UserDataType, class Converter> +class nsBaseHashtable + : protected nsTHashtable<nsBaseHashtableET<KeyClass, DataType>> { + using Base = nsTHashtable<nsBaseHashtableET<KeyClass, DataType>>; + typedef mozilla::fallible_t fallible_t; + + public: + typedef typename KeyClass::KeyType KeyType; + typedef nsBaseHashtableET<KeyClass, DataType> EntryType; + + using nsTHashtable<EntryType>::Contains; + using nsTHashtable<EntryType>::GetGeneration; + using nsTHashtable<EntryType>::SizeOfExcludingThis; + using nsTHashtable<EntryType>::SizeOfIncludingThis; + + nsBaseHashtable() = default; + explicit nsBaseHashtable(uint32_t aInitLength) + : nsTHashtable<EntryType>(aInitLength) {} + + /** + * Return the number of entries in the table. + * @return number of entries + */ + [[nodiscard]] uint32_t Count() const { + return nsTHashtable<EntryType>::Count(); + } + + /** + * Return whether the table is empty. + * @return whether empty + */ + [[nodiscard]] bool IsEmpty() const { + return nsTHashtable<EntryType>::IsEmpty(); + } + + /** + * Get the value, returning a flag indicating the presence of the entry in + * the table. + * + * @param aKey the key to retrieve + * @param aData data associated with this key will be placed at this pointer. + * If you only need to check if the key exists, aData may be null. + * @return true if the key exists. If key does not exist, aData is not + * modified. + * + * @attention As opposed to Remove, this does not assign a value to *aData if + * no entry is present! (And also as opposed to the member function Get with + * the same signature that nsClassHashtable defines and hides this one.) + */ + [[nodiscard]] bool Get(KeyType aKey, UserDataType* aData) const { + EntryType* ent = this->GetEntry(aKey); + if (!ent) { + return false; + } + + if (aData) { + *aData = Converter::Unwrap(ent->mData); + } + + return true; + } + + /** + * Get the value, returning a zero-initialized POD or a default-initialized + * object if the entry is not present in the table. + * + * This overload can only be used if UserDataType is default-constructible. + * Use the double-argument Get or MaybeGet with non-default-constructible + * UserDataType. + * + * @param aKey the key to retrieve + * @return The found value, or UserDataType{} if no entry was found with the + * given key. + * @note If zero/default-initialized values are stored in the table, it is + * not possible to distinguish between such a value and a missing entry. + */ + [[nodiscard]] UserDataType Get(KeyType aKey) const { + EntryType* ent = this->GetEntry(aKey); + if (!ent) { + return UserDataType{}; + } + + return Converter::Unwrap(ent->mData); + } + + /** + * Get the value, returning Nothing if the entry is not present in the table. + * + * @param aKey the key to retrieve + * @return The found value wrapped in a Maybe, or Nothing if no entry was + * found with the given key. + */ + [[nodiscard]] mozilla::Maybe<UserDataType> MaybeGet(KeyType aKey) const { + EntryType* ent = this->GetEntry(aKey); + if (!ent) { + return mozilla::Nothing(); + } + + return mozilla::Some(Converter::Unwrap(ent->mData)); + } + + using SmartPtrTraits = mozilla::detail::SmartPtrTraits<DataType>; + + /** + * Looks up aKey in the hash table. If it doesn't exist a new object of + * SmartPtrTraits::PointeeType will be created (using the arguments provided) + * and then returned. + * + * \note This can only be instantiated if DataType is a smart pointer. + */ + template <typename... Args> + auto GetOrInsertNew(KeyType aKey, Args&&... aConstructionArgs) { + static_assert( + SmartPtrTraits::IsSmartPointer, + "GetOrInsertNew can only be used with smart pointer data types"); + return mozilla::detail::PtrGetWeak(LookupOrInsertWith(std::move(aKey), [&] { + return SmartPtrTraits::template NewObject< + typename SmartPtrTraits::PointeeType>( + std::forward<Args>(aConstructionArgs)...); + })); + } + + /** + * Add aKey to the table if not already present, and return a reference to its + * value. If aKey is not already in the table then the a default-constructed + * or the provided value aData is used. + * + * If the arguments are non-trivial to provide, consider using + * LookupOrInsertWith instead. + */ + template <typename... Args> + DataType& LookupOrInsert(const KeyType& aKey, Args&&... aArgs) { + return WithEntryHandle(aKey, [&](auto entryHandle) -> DataType& { + return entryHandle.OrInsert(std::forward<Args>(aArgs)...); + }); + } + + /** + * Add aKey to the table if not already present, and return a reference to its + * value. If aKey is not already in the table then the value is + * constructed using the given factory. + */ + template <typename F> + DataType& LookupOrInsertWith(const KeyType& aKey, F&& aFunc) { + return WithEntryHandle(aKey, [&aFunc](auto entryHandle) -> DataType& { + return entryHandle.OrInsertWith(std::forward<F>(aFunc)); + }); + } + + /** + * Add aKey to the table if not already present, and return a reference to its + * value. If aKey is not already in the table then the value is + * constructed using the given factory. + */ + template <typename F> + [[nodiscard]] auto TryLookupOrInsertWith(const KeyType& aKey, F&& aFunc) { + return WithEntryHandle( + aKey, + [&aFunc](auto entryHandle) + -> mozilla::Result<std::reference_wrapper<DataType>, + typename std::invoke_result_t<F>::err_type> { + if (entryHandle) { + return std::ref(entryHandle.Data()); + } + + // XXX Use MOZ_TRY after generalizing QM_TRY to mfbt. + auto res = std::forward<F>(aFunc)(); + if (res.isErr()) { + return res.propagateErr(); + } + return std::ref(entryHandle.Insert(res.unwrap())); + }); + } + + /** + * If it does not yet, inserts a new entry with the handle's key and the + * value passed to this function. Otherwise, it updates the entry by the + * value passed to this function. + * + * \tparam U DataType must be implicitly convertible (and assignable) from U + * \post HasEntry() + * \param aKey the key to put + * \param aData the new data + */ + template <typename U> + DataType& InsertOrUpdate(KeyType aKey, U&& aData) { + return WithEntryHandle(aKey, [&aData](auto entryHandle) -> DataType& { + return entryHandle.InsertOrUpdate(std::forward<U>(aData)); + }); + } + + template <typename U> + [[nodiscard]] bool InsertOrUpdate(KeyType aKey, U&& aData, + const fallible_t& aFallible) { + return WithEntryHandle(aKey, aFallible, [&aData](auto maybeEntryHandle) { + if (!maybeEntryHandle) { + return false; + } + maybeEntryHandle->InsertOrUpdate(std::forward<U>(aData)); + return true; + }); + } + + /** + * Remove the entry associated with aKey (if any), _moving_ its current value + * into *aData. Return true if found. + * + * This overload can only be used if DataType is default-constructible. Use + * the single-argument Remove or Extract with non-default-constructible + * DataType. + * + * @param aKey the key to remove from the hashtable + * @param aData where to move the value. If an entry is not found, *aData + * will be assigned a default-constructed value (i.e. reset to + * zero or nullptr for primitive types). + * @return true if an entry for aKey was found (and removed) + */ + // XXX This should also better be marked nodiscard, but due to + // nsClassHashtable not guaranteeing non-nullness of entries, it is usually + // only checked if aData is nullptr in such cases. + // [[nodiscard]] + bool Remove(KeyType aKey, DataType* aData) { + if (auto* ent = this->GetEntry(aKey)) { + if (aData) { + *aData = std::move(ent->mData); + } + this->RemoveEntry(ent); + return true; + } + if (aData) { + *aData = std::move(DataType()); + } + return false; + } + + /** + * Remove the entry associated with aKey (if any). Return true if found. + * + * @param aKey the key to remove from the hashtable + * @return true if an entry for aKey was found (and removed) + */ + bool Remove(KeyType aKey) { + if (auto* ent = this->GetEntry(aKey)) { + this->RemoveEntry(ent); + return true; + } + + return false; + } + + /** + * Retrieve the value for a key and remove the corresponding entry at + * the same time. + * + * @param aKey the key to retrieve and remove + * @return the found value, or Nothing if no entry was found with the + * given key. + */ + [[nodiscard]] mozilla::Maybe<DataType> Extract(KeyType aKey) { + mozilla::Maybe<DataType> value; + if (EntryType* ent = this->GetEntry(aKey)) { + value.emplace(std::move(ent->mData)); + this->RemoveEntry(ent); + } + return value; + } + + template <typename HashtableRef> + struct LookupResult { + private: + EntryType* mEntry; + HashtableRef mTable; +#ifdef DEBUG + uint32_t mTableGeneration; +#endif + + public: + LookupResult(EntryType* aEntry, HashtableRef aTable) + : mEntry(aEntry), + mTable(aTable) +#ifdef DEBUG + , + mTableGeneration(aTable.GetGeneration()) +#endif + { + } + + // Is there something stored in the table? + explicit operator bool() const { + MOZ_ASSERT(mTableGeneration == mTable.GetGeneration()); + return mEntry; + } + + void Remove() { + if (!*this) { + return; + } + mTable.RemoveEntry(mEntry); + mEntry = nullptr; + } + + [[nodiscard]] DataType& Data() { + MOZ_ASSERT(!!*this, "must have an entry to access its value"); + return mEntry->mData; + } + + [[nodiscard]] const DataType& Data() const { + MOZ_ASSERT(!!*this, "must have an entry to access its value"); + return mEntry->mData; + } + + [[nodiscard]] DataType* DataPtrOrNull() { + return static_cast<bool>(*this) ? &mEntry->mData : nullptr; + } + + [[nodiscard]] const DataType* DataPtrOrNull() const { + return static_cast<bool>(*this) ? &mEntry->mData : nullptr; + } + + [[nodiscard]] DataType* operator->() { return &Data(); } + [[nodiscard]] const DataType* operator->() const { return &Data(); } + + [[nodiscard]] DataType& operator*() { return Data(); } + [[nodiscard]] const DataType& operator*() const { return Data(); } + }; + + /** + * Removes all entries matching a predicate. + * + * The predicate must be compatible with signature bool (const Iterator &). + */ + template <typename Pred> + void RemoveIf(Pred&& aPred) { + for (auto iter = Iter(); !iter.Done(); iter.Next()) { + if (aPred(const_cast<std::add_const_t<decltype(iter)>&>(iter))) { + iter.Remove(); + } + } + } + + /** + * Looks up aKey in the hashtable and returns an object that allows you to + * read/modify the value of the entry, or remove the entry (if found). + * + * A typical usage of this API looks like this: + * + * if (auto entry = hashtable.Lookup(key)) { + * DoSomething(entry.Data()); + * if (entry.Data() > 42) { + * entry.Remove(); + * } + * } // else - an entry with the given key doesn't exist + * + * This is useful for cases where you want to read/write the value of an entry + * and (optionally) remove the entry without having to do multiple hashtable + * lookups. If you want to insert a new entry if one does not exist, then use + * WithEntryHandle instead, see below. + */ + [[nodiscard]] auto Lookup(KeyType aKey) { + return LookupResult<nsBaseHashtable&>(this->GetEntry(aKey), *this); + } + + [[nodiscard]] auto Lookup(KeyType aKey) const { + return LookupResult<const nsBaseHashtable&>(this->GetEntry(aKey), *this); + } + + /** + * Used by WithEntryHandle as the argument type to its functor. It is + * associated with the Key passed to WithEntryHandle and manages only the + * potential entry with that key. Note that in case no modifying operations + * are called on the handle, the state of the hashtable remains unchanged, + * i.e. WithEntryHandle does not modify the hashtable itself. + * + * Provides query functions (Key, HasEntry/operator bool, Data) and + * modifying operations for inserting new entries (Insert), updating existing + * entries (Update) and removing existing entries (Remove). They have + * debug-only assertion that fail when the state of the entry doesn't match + * the expectation. There are variants prefixed with "Or" (OrInsert, OrUpdate, + * OrRemove) that are a no-op in case the entry does already exist resp. does + * not exist. There are also variants OrInsertWith and OrUpdateWith that don't + * accept a value, but a functor, which is only called if the operation takes + * place, which should be used if the provision of the value is not trivial + * (e.g. allocates a heap object). Finally, there's InsertOrUpdate that + * handles both existing and non-existing entries. + * + * Note that all functions of EntryHandle only deal with DataType, not with + * UserDataType. + */ + class EntryHandle : protected nsTHashtable<EntryType>::EntryHandle { + public: + using Base = typename nsTHashtable<EntryType>::EntryHandle; + + EntryHandle(EntryHandle&& aOther) = default; + ~EntryHandle() = default; + + EntryHandle(const EntryHandle&) = delete; + EntryHandle& operator=(const EntryHandle&) = delete; + EntryHandle& operator=(const EntryHandle&&) = delete; + + using Base::Key; + + using Base::HasEntry; + + using Base::operator bool; + + using Base::Entry; + + /** + * Inserts a new entry with the handle's key and the value passed to this + * function. + * + * \tparam Args DataType must be constructible from Args + * \pre !HasEntry() + * \post HasEntry() + */ + template <typename... Args> + DataType& Insert(Args&&... aArgs) { + Base::InsertInternal(std::forward<Args>(aArgs)...); + return Data(); + } + + /** + * If it doesn't yet exist, inserts a new entry with the handle's key and + * the value passed to this function. The value is not consumed if no insert + * takes place. + * + * \tparam Args DataType must be constructible from Args + * \post HasEntry() + */ + template <typename... Args> + DataType& OrInsert(Args&&... aArgs) { + if (!HasEntry()) { + return Insert(std::forward<Args>(aArgs)...); + } + return Data(); + } + + /** + * If it doesn't yet exist, inserts a new entry with the handle's key and + * the result of the functor passed to this function. The functor is not + * called if no insert takes place. + * + * \tparam F must return a value that is implicitly convertible to DataType + * \post HasEntry() + */ + template <typename F> + DataType& OrInsertWith(F&& aFunc) { + if (!HasEntry()) { + return Insert(std::forward<F>(aFunc)()); + } + return Data(); + } + + /** + * Updates the entry with the handle's key by the value passed to this + * function. + * + * \tparam U DataType must be assignable from U + * \pre HasEntry() + */ + template <typename U> + DataType& Update(U&& aData) { + MOZ_RELEASE_ASSERT(HasEntry()); + Data() = std::forward<U>(aData); + return Data(); + } + + /** + * If an entry with the handle's key already exists, updates its value by + * the value passed to this function. The value is not consumed if no update + * takes place. + * + * \tparam U DataType must be assignable from U + */ + template <typename U> + void OrUpdate(U&& aData) { + if (HasEntry()) { + Update(std::forward<U>(aData)); + } + } + + /** + * If an entry with the handle's key already exists, updates its value by + * the the result of the functor passed to this function. The functor is not + * called if no update takes place. + * + * \tparam F must return a value that DataType is assignable from + */ + template <typename F> + void OrUpdateWith(F&& aFunc) { + if (HasEntry()) { + Update(std::forward<F>(aFunc)()); + } + } + + /** + * If it does not yet, inserts a new entry with the handle's key and the + * value passed to this function. Otherwise, it updates the entry by the + * value passed to this function. + * + * \tparam U DataType must be implicitly convertible (and assignable) from U + * \post HasEntry() + */ + template <typename U> + DataType& InsertOrUpdate(U&& aData) { + if (!HasEntry()) { + Insert(std::forward<U>(aData)); + } else { + Update(std::forward<U>(aData)); + } + return Data(); + } + + using Base::Remove; + + using Base::OrRemove; + + /** + * Returns a reference to the value of the entry. + * + * \pre HasEntry() + */ + [[nodiscard]] DataType& Data() { return Entry()->mData; } + + [[nodiscard]] DataType* DataPtrOrNull() { + return static_cast<bool>(*this) ? &Data() : nullptr; + } + + [[nodiscard]] DataType* operator->() { return &Data(); } + + [[nodiscard]] DataType& operator*() { return Data(); } + + private: + friend class nsBaseHashtable; + + explicit EntryHandle(Base&& aBase) : Base(std::move(aBase)) {} + }; + + /** + * Performs a scoped operation on the entry for aKey, which may or may not + * exist when the function is called. It calls aFunc with an EntryHandle. The + * result of aFunc is returned as the result of this function. Its return type + * may be void. See the documentation of EntryHandle for the query and + * modifying operations it offers. + * + * A simple use of this function is, e.g., + * + * hashtable.WithEntryHandle(key, [](auto&& entry) { entry.OrInsert(42); }); + * + * \attention It is not safe to perform modifying operations on the hashtable + * other than through the EntryHandle within aFunc, and trying to do so will + * trigger debug assertions, and result in undefined behaviour otherwise. + */ + template <class F> + [[nodiscard]] auto WithEntryHandle(KeyType aKey, F&& aFunc) + -> std::invoke_result_t<F, EntryHandle&&> { + return Base::WithEntryHandle( + aKey, [&aFunc](auto entryHandle) -> decltype(auto) { + return std::forward<F>(aFunc)(EntryHandle{std::move(entryHandle)}); + }); + } + + /** + * Fallible variant of WithEntryHandle, with the following differences: + * - The functor aFunc must accept a Maybe<EntryHandle> (instead of an + * EntryHandle). + * - In case allocation of the slot for the entry fails, Nothing is passed to + * the functor. + * + * For more details, see the explanation on the non-fallible overload above. + */ + template <class F> + [[nodiscard]] auto WithEntryHandle(KeyType aKey, const fallible_t& aFallible, + F&& aFunc) + -> std::invoke_result_t<F, mozilla::Maybe<EntryHandle>&&> { + return Base::WithEntryHandle( + aKey, aFallible, [&aFunc](auto maybeEntryHandle) { + return std::forward<F>(aFunc)( + maybeEntryHandle + ? mozilla::Some(EntryHandle{maybeEntryHandle.extract()}) + : mozilla::Nothing()); + }); + } + + public: + class ConstIterator { + public: + explicit ConstIterator(nsBaseHashtable* aTable) + : mBaseIterator(&aTable->mTable) {} + ~ConstIterator() = default; + + KeyType Key() const { + return static_cast<EntryType*>(mBaseIterator.Get())->GetKey(); + } + UserDataType UserData() const { + return Converter::Unwrap( + static_cast<EntryType*>(mBaseIterator.Get())->mData); + } + const DataType& Data() const { + return static_cast<EntryType*>(mBaseIterator.Get())->mData; + } + + bool Done() const { return mBaseIterator.Done(); } + void Next() { mBaseIterator.Next(); } + + ConstIterator() = delete; + ConstIterator(const ConstIterator&) = delete; + ConstIterator(ConstIterator&& aOther) = delete; + ConstIterator& operator=(const ConstIterator&) = delete; + ConstIterator& operator=(ConstIterator&&) = delete; + + protected: + PLDHashTable::Iterator mBaseIterator; + }; + + // This is an iterator that also allows entry removal. Example usage: + // + // for (auto iter = table.Iter(); !iter.Done(); iter.Next()) { + // const KeyType key = iter.Key(); + // const UserDataType data = iter.UserData(); + // // or + // const DataType& data = iter.Data(); + // // ... do stuff with |key| and/or |data| ... + // // ... possibly call iter.Remove() once ... + // } + // + class Iterator final : public ConstIterator { + public: + using ConstIterator::ConstIterator; + + using ConstIterator::Data; + DataType& Data() { + return static_cast<EntryType*>(this->mBaseIterator.Get())->mData; + } + + void Remove() { this->mBaseIterator.Remove(); } + }; + + Iterator Iter() { return Iterator(this); } + + ConstIterator ConstIter() const { + return ConstIterator(const_cast<nsBaseHashtable*>(this)); + } + + using nsTHashtable<EntryType>::Remove; + + /** + * Remove the entry associated with aIter. + * + * @param aIter the iterator pointing to the entry + * @pre !aIter.Done() + */ + void Remove(ConstIterator& aIter) { aIter.mBaseIterator.Remove(); } + + using typename nsTHashtable<EntryType>::iterator; + using typename nsTHashtable<EntryType>::const_iterator; + + using nsTHashtable<EntryType>::begin; + using nsTHashtable<EntryType>::end; + using nsTHashtable<EntryType>::cbegin; + using nsTHashtable<EntryType>::cend; + + using nsTHashtable<EntryType>::Keys; + + /** + * Return a range of the values (of DataType). Note this range iterates over + * the values in place, so modifications to the nsTHashtable invalidate the + * range while it's iterated, except when calling Remove() with a value + * iterator derived from that range. + */ + auto Values() const { + return mozilla::detail::nsBaseHashtableValueRange<EntryType>{this->mTable}; + } + + /** + * Remove an entry from a value range, specified via a value iterator, e.g. + * + * for (auto it = hash.Values().begin(), end = hash.Values().end(); + * it != end; * ++it) { + * if (*it > 42) { hash.Remove(it); } + * } + * + * You might also consider using RemoveIf though. + */ + void Remove(mozilla::detail::nsBaseHashtableValueIterator<EntryType>& aIter) { + aIter.mIterator.Remove(); + } + + /** + * reset the hashtable, removing all entries + */ + void Clear() { nsTHashtable<EntryType>::Clear(); } + + /** + * Measure the size of the table's entry storage. The size of things pointed + * to by entries must be measured separately; hence the "Shallow" prefix. + * + * @param aMallocSizeOf the function used to measure heap-allocated blocks + * @return the summed size of the table's storage + */ + size_t ShallowSizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const { + return this->mTable.ShallowSizeOfExcludingThis(aMallocSizeOf); + } + + /** + * Like ShallowSizeOfExcludingThis, but includes sizeof(*this). + */ + size_t ShallowSizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const { + return aMallocSizeOf(this) + ShallowSizeOfExcludingThis(aMallocSizeOf); + } + + /** + * Swap the elements in this hashtable with the elements in aOther. + */ + void SwapElements(nsBaseHashtable& aOther) { + nsTHashtable<EntryType>::SwapElements(aOther); + } + + using nsTHashtable<EntryType>::MarkImmutable; + + /** + * Makes a clone of this hashtable by copying all entries. This requires + * KeyType and DataType to be copy-constructible. + */ + nsBaseHashtable Clone() const { return CloneAs<nsBaseHashtable>(); } + + protected: + template <typename T> + T CloneAs() const { + static_assert(std::is_base_of_v<nsBaseHashtable, T>); + // XXX This can probably be optimized, see Bug 1694368. + T result(Count()); + for (const auto& srcEntry : *this) { + result.WithEntryHandle(srcEntry.GetKey(), [&](auto&& dstEntry) { + dstEntry.Insert(srcEntry.GetData()); + }); + } + return result; + } +}; + +// +// nsBaseHashtableET definitions +// + +template <class KeyClass, class DataType> +template <typename... Args> +nsBaseHashtableET<KeyClass, DataType>::nsBaseHashtableET(KeyTypePointer aKey, + Args&&... aArgs) + : KeyClass(aKey), mData(std::forward<Args>(aArgs)...) {} + +#endif // nsBaseHashtable_h__ |