diff options
Diffstat (limited to 'xpcom/ds/nsHashKeys.h')
| -rw-r--r-- | xpcom/ds/nsHashKeys.h | 636 |
1 files changed, 636 insertions, 0 deletions
diff --git a/xpcom/ds/nsHashKeys.h b/xpcom/ds/nsHashKeys.h new file mode 100644 index 0000000000..fb0a8244c4 --- /dev/null +++ b/xpcom/ds/nsHashKeys.h @@ -0,0 +1,636 @@ +/* -*- 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 nsTHashKeys_h__ +#define nsTHashKeys_h__ + +#include "nsID.h" +#include "nsISupports.h" +#include "nsCOMPtr.h" +#include "PLDHashTable.h" +#include <new> + +#include "nsString.h" +#include "nsCRTGlue.h" +#include "nsUnicharUtils.h" +#include "nsPointerHashKeys.h" + +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +#include <type_traits> +#include <utility> + +#include "mozilla/HashFunctions.h" + +namespace mozilla { + +// These are defined analogously to the HashString overloads in mfbt. + +inline uint32_t HashString(const nsAString& aStr) { + return HashString(aStr.BeginReading(), aStr.Length()); +} + +inline uint32_t HashString(const nsACString& aStr) { + return HashString(aStr.BeginReading(), aStr.Length()); +} + +} // namespace mozilla + +/** @file nsHashKeys.h + * standard HashKey classes for nsBaseHashtable and relatives. Each of these + * classes follows the nsTHashtable::EntryType specification + * + * Lightweight keytypes provided here: + * nsStringHashKey + * nsCStringHashKey + * nsUint32HashKey + * nsUint64HashKey + * nsFloatHashKey + * IntPtrHashKey + * nsPtrHashKey + * nsClearingPtrHashKey + * nsVoidPtrHashKey + * nsClearingVoidPtrHashKey + * nsISupportsHashKey + * nsIDHashKey + * nsDepCharHashKey + * nsCharPtrHashKey + * nsUnicharPtrHashKey + * nsGenericHashKey + */ + +/** + * hashkey wrapper using nsAString KeyType + * + * @see nsTHashtable::EntryType for specification + */ +class nsStringHashKey : public PLDHashEntryHdr { + public: + typedef const nsAString& KeyType; + typedef const nsAString* KeyTypePointer; + + explicit nsStringHashKey(KeyTypePointer aStr) : mStr(*aStr) {} + nsStringHashKey(const nsStringHashKey&) = delete; + nsStringHashKey(nsStringHashKey&& aToMove) + : PLDHashEntryHdr(std::move(aToMove)), mStr(std::move(aToMove.mStr)) {} + ~nsStringHashKey() = default; + + KeyType GetKey() const { return mStr; } + bool KeyEquals(const KeyTypePointer aKey) const { return mStr.Equals(*aKey); } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; } + static PLDHashNumber HashKey(const KeyTypePointer aKey) { + return mozilla::HashString(*aKey); + } + +#ifdef MOZILLA_INTERNAL_API + // To avoid double-counting, only measure the string if it is unshared. + size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const { + return GetKey().SizeOfExcludingThisIfUnshared(aMallocSizeOf); + } +#endif + + enum { ALLOW_MEMMOVE = true }; + + private: + nsString mStr; +}; + +#ifdef MOZILLA_INTERNAL_API + +namespace mozilla::detail { + +template <class CharT, bool Unicode = true> +struct comparatorTraits {}; + +template <> +struct comparatorTraits<char, false> { + static int caseInsensitiveCompare(const char* aLhs, const char* aRhs, + size_t aLhsLength, size_t aRhsLength) { + return nsCaseInsensitiveCStringComparator(aLhs, aRhs, aLhsLength, + aRhsLength); + }; +}; + +template <> +struct comparatorTraits<char, true> { + static int caseInsensitiveCompare(const char* aLhs, const char* aRhs, + size_t aLhsLength, size_t aRhsLength) { + return nsCaseInsensitiveUTF8StringComparator(aLhs, aRhs, aLhsLength, + aRhsLength); + }; +}; + +template <> +struct comparatorTraits<char16_t, true> { + static int caseInsensitiveCompare(const char16_t* aLhs, const char16_t* aRhs, + size_t aLhsLength, size_t aRhsLength) { + return nsCaseInsensitiveStringComparator(aLhs, aRhs, aLhsLength, + aRhsLength); + }; +}; + +} // namespace mozilla::detail + +/** + * This is internal-API only because nsCaseInsensitive{C}StringComparator is + * internal-only. + * + * @see nsTHashtable::EntryType for specification + */ + +template <typename T, bool Unicode> +class nsTStringCaseInsensitiveHashKey : public PLDHashEntryHdr { + public: + typedef const nsTSubstring<T>& KeyType; + typedef const nsTSubstring<T>* KeyTypePointer; + + explicit nsTStringCaseInsensitiveHashKey(KeyTypePointer aStr) : mStr(*aStr) { + // take it easy just deal HashKey + } + + nsTStringCaseInsensitiveHashKey(const nsTStringCaseInsensitiveHashKey&) = + delete; + nsTStringCaseInsensitiveHashKey(nsTStringCaseInsensitiveHashKey&& aToMove) + : PLDHashEntryHdr(std::move(aToMove)), mStr(std::move(aToMove.mStr)) {} + ~nsTStringCaseInsensitiveHashKey() = default; + + KeyType GetKey() const { return mStr; } + bool KeyEquals(const KeyTypePointer aKey) const { + using comparator = typename mozilla::detail::comparatorTraits<T, Unicode>; + return mStr.Equals(*aKey, comparator::caseInsensitiveCompare); + } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; } + static PLDHashNumber HashKey(const KeyTypePointer aKey) { + nsTAutoString<T> tmKey(*aKey); + ToLowerCase(tmKey); + return mozilla::HashString(tmKey); + } + enum { ALLOW_MEMMOVE = true }; + + // To avoid double-counting, only measure the string if it is unshared. + size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const { + return GetKey().SizeOfExcludingThisIfUnshared(aMallocSizeOf); + } + + private: + const nsTString<T> mStr; +}; + +using nsStringCaseInsensitiveHashKey = + nsTStringCaseInsensitiveHashKey<char16_t, true>; +using nsCStringASCIICaseInsensitiveHashKey = + nsTStringCaseInsensitiveHashKey<char, false>; +using nsCStringUTF8CaseInsensitiveHashKey = + nsTStringCaseInsensitiveHashKey<char, true>; + +#endif // MOZILLA_INTERNAL_API + +/** + * hashkey wrapper using nsACString KeyType + * + * @see nsTHashtable::EntryType for specification + */ +class nsCStringHashKey : public PLDHashEntryHdr { + public: + typedef const nsACString& KeyType; + typedef const nsACString* KeyTypePointer; + + explicit nsCStringHashKey(const nsACString* aStr) : mStr(*aStr) {} + nsCStringHashKey(nsCStringHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mStr(std::move(aOther.mStr)) {} + ~nsCStringHashKey() = default; + + KeyType GetKey() const { return mStr; } + bool KeyEquals(KeyTypePointer aKey) const { return mStr.Equals(*aKey); } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return mozilla::HashString(*aKey); + } + +#ifdef MOZILLA_INTERNAL_API + // To avoid double-counting, only measure the string if it is unshared. + size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const { + return GetKey().SizeOfExcludingThisIfUnshared(aMallocSizeOf); + } +#endif + + enum { ALLOW_MEMMOVE = true }; + + private: + const nsCString mStr; +}; + +/** + * hashkey wrapper using integral or enum KeyTypes + * + * @see nsTHashtable::EntryType for specification + */ +template <typename T, + std::enable_if_t<std::is_integral_v<T> || std::is_enum_v<T>, int> = 0> +class nsIntegralHashKey : public PLDHashEntryHdr { + public: + using KeyType = const T&; + using KeyTypePointer = const T*; + + explicit nsIntegralHashKey(KeyTypePointer aKey) : mValue(*aKey) {} + nsIntegralHashKey(nsIntegralHashKey&& aOther) noexcept + : PLDHashEntryHdr(std::move(aOther)), mValue(aOther.mValue) {} + ~nsIntegralHashKey() = default; + + KeyType GetKey() const { return mValue; } + bool KeyEquals(KeyTypePointer aKey) const { return *aKey == mValue; } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return mozilla::HashGeneric(*aKey); + } + enum { ALLOW_MEMMOVE = true }; + + private: + const T mValue; +}; + +/** + * hashkey wrapper using uint32_t KeyType + * + * @see nsTHashtable::EntryType for specification + */ +using nsUint32HashKey = nsIntegralHashKey<uint32_t>; + +/** + * hashkey wrapper using uint64_t KeyType + * + * @see nsTHashtable::EntryType for specification + */ +using nsUint64HashKey = nsIntegralHashKey<uint64_t>; + +/** + * hashkey wrapper using float KeyType + * + * @see nsTHashtable::EntryType for specification + */ +class nsFloatHashKey : public PLDHashEntryHdr { + public: + typedef const float& KeyType; + typedef const float* KeyTypePointer; + + explicit nsFloatHashKey(KeyTypePointer aKey) : mValue(*aKey) {} + nsFloatHashKey(nsFloatHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mValue(std::move(aOther.mValue)) {} + ~nsFloatHashKey() = default; + + KeyType GetKey() const { return mValue; } + bool KeyEquals(KeyTypePointer aKey) const { return *aKey == mValue; } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return *reinterpret_cast<const uint32_t*>(aKey); + } + enum { ALLOW_MEMMOVE = true }; + + private: + const float mValue; +}; + +/** + * hashkey wrapper using intptr_t KeyType + * + * @see nsTHashtable::EntryType for specification + */ +using IntPtrHashKey = nsIntegralHashKey<intptr_t>; + +/** + * hashkey wrapper using nsISupports* KeyType + * + * @see nsTHashtable::EntryType for specification + */ +class nsISupportsHashKey : public PLDHashEntryHdr { + public: + typedef nsISupports* KeyType; + typedef const nsISupports* KeyTypePointer; + + explicit nsISupportsHashKey(const nsISupports* aKey) + : mSupports(const_cast<nsISupports*>(aKey)) {} + nsISupportsHashKey(nsISupportsHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), + mSupports(std::move(aOther.mSupports)) {} + ~nsISupportsHashKey() = default; + + KeyType GetKey() const { return mSupports; } + bool KeyEquals(KeyTypePointer aKey) const { return aKey == mSupports; } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return NS_PTR_TO_UINT32(aKey) >> 2; + } + enum { ALLOW_MEMMOVE = true }; + + private: + nsCOMPtr<nsISupports> mSupports; +}; + +/** + * hashkey wrapper using refcounted * KeyType + * + * @see nsTHashtable::EntryType for specification + */ +template <class T> +class nsRefPtrHashKey : public PLDHashEntryHdr { + public: + typedef T* KeyType; + typedef const T* KeyTypePointer; + + explicit nsRefPtrHashKey(const T* aKey) : mKey(const_cast<T*>(aKey)) {} + nsRefPtrHashKey(nsRefPtrHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mKey(std::move(aOther.mKey)) {} + ~nsRefPtrHashKey() = default; + + KeyType GetKey() const { return mKey; } + bool KeyEquals(KeyTypePointer aKey) const { return aKey == mKey; } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return NS_PTR_TO_UINT32(aKey) >> 2; + } + enum { ALLOW_MEMMOVE = true }; + + private: + RefPtr<T> mKey; +}; + +template <class T> +inline void ImplCycleCollectionTraverse( + nsCycleCollectionTraversalCallback& aCallback, nsRefPtrHashKey<T>& aField, + const char* aName, uint32_t aFlags = 0) { + CycleCollectionNoteChild(aCallback, aField.GetKey(), aName, aFlags); +} + +/** + * hashkey wrapper using T* KeyType that sets key to nullptr upon + * destruction. Relevant only in cases where a memory pointer-scanner + * like valgrind might get confused about stale references. + * + * @see nsTHashtable::EntryType for specification + */ + +template <class T> +class nsClearingPtrHashKey : public nsPtrHashKey<T> { + public: + explicit nsClearingPtrHashKey(const T* aKey) : nsPtrHashKey<T>(aKey) {} + nsClearingPtrHashKey(nsClearingPtrHashKey&& aToMove) + : nsPtrHashKey<T>(std::move(aToMove)) {} + ~nsClearingPtrHashKey() { nsPtrHashKey<T>::mKey = nullptr; } +}; + +typedef nsClearingPtrHashKey<const void> nsClearingVoidPtrHashKey; + +/** + * hashkey wrapper using a function pointer KeyType + * + * @see nsTHashtable::EntryType for specification + */ +template <class T> +class nsFuncPtrHashKey : public PLDHashEntryHdr { + public: + typedef T& KeyType; + typedef const T* KeyTypePointer; + + explicit nsFuncPtrHashKey(const T* aKey) : mKey(*const_cast<T*>(aKey)) {} + nsFuncPtrHashKey(const nsFuncPtrHashKey<T>& aToCopy) : mKey(aToCopy.mKey) {} + ~nsFuncPtrHashKey() = default; + + KeyType GetKey() const { return const_cast<T&>(mKey); } + bool KeyEquals(KeyTypePointer aKey) const { return *aKey == mKey; } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return NS_PTR_TO_UINT32(*aKey) >> 2; + } + enum { ALLOW_MEMMOVE = true }; + + protected: + T mKey; +}; + +/** + * hashkey wrapper using nsID KeyType + * + * @see nsTHashtable::EntryType for specification + */ +class nsIDHashKey : public PLDHashEntryHdr { + public: + typedef const nsID& KeyType; + typedef const nsID* KeyTypePointer; + + explicit nsIDHashKey(const nsID* aInID) : mID(*aInID) {} + nsIDHashKey(nsIDHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mID(std::move(aOther.mID)) {} + ~nsIDHashKey() = default; + + KeyType GetKey() const { return mID; } + bool KeyEquals(KeyTypePointer aKey) const { return aKey->Equals(mID); } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + // Hash the nsID object's raw bytes. + return mozilla::HashBytes(aKey, sizeof(KeyType)); + } + + enum { ALLOW_MEMMOVE = true }; + + private: + nsID mID; +}; + +/** + * hashkey wrapper using nsID* KeyType + * + * @see nsTHashtable::EntryType for specification + */ +class nsIDPointerHashKey : public PLDHashEntryHdr { + public: + typedef const nsID* KeyType; + typedef const nsID* KeyTypePointer; + + explicit nsIDPointerHashKey(const nsID* aInID) : mID(aInID) {} + nsIDPointerHashKey(nsIDPointerHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mID(aOther.mID) {} + ~nsIDPointerHashKey() = default; + + KeyType GetKey() const { return mID; } + bool KeyEquals(KeyTypePointer aKey) const { return aKey->Equals(*mID); } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + // Hash the nsID object's raw bytes. + return mozilla::HashBytes(aKey, sizeof(*aKey)); + } + + enum { ALLOW_MEMMOVE = true }; + + private: + const nsID* mID; +}; + +/** + * hashkey wrapper for "dependent" const char*; this class does not "own" + * its string pointer. + * + * This class must only be used if the strings have a lifetime longer than + * the hashtable they occupy. This normally occurs only for static + * strings or strings that have been arena-allocated. + * + * @see nsTHashtable::EntryType for specification + */ +class nsDepCharHashKey : public PLDHashEntryHdr { + public: + typedef const char* KeyType; + typedef const char* KeyTypePointer; + + explicit nsDepCharHashKey(const char* aKey) : mKey(aKey) {} + nsDepCharHashKey(nsDepCharHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mKey(std::move(aOther.mKey)) {} + ~nsDepCharHashKey() = default; + + const char* GetKey() const { return mKey; } + bool KeyEquals(const char* aKey) const { return !strcmp(mKey, aKey); } + + static const char* KeyToPointer(const char* aKey) { return aKey; } + static PLDHashNumber HashKey(const char* aKey) { + return mozilla::HashString(aKey); + } + enum { ALLOW_MEMMOVE = true }; + + private: + const char* mKey; +}; + +/** + * hashkey wrapper for const char*; at construction, this class duplicates + * a string pointed to by the pointer so that it doesn't matter whether or not + * the string lives longer than the hash table. + */ +class nsCharPtrHashKey : public PLDHashEntryHdr { + public: + typedef const char* KeyType; + typedef const char* KeyTypePointer; + + explicit nsCharPtrHashKey(const char* aKey) : mKey(strdup(aKey)) {} + + nsCharPtrHashKey(const nsCharPtrHashKey&) = delete; + nsCharPtrHashKey(nsCharPtrHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mKey(aOther.mKey) { + aOther.mKey = nullptr; + } + + ~nsCharPtrHashKey() { + if (mKey) { + free(const_cast<char*>(mKey)); + } + } + + const char* GetKey() const { return mKey; } + bool KeyEquals(KeyTypePointer aKey) const { return !strcmp(mKey, aKey); } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return mozilla::HashString(aKey); + } + + size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const { + return aMallocSizeOf(mKey); + } + + enum { ALLOW_MEMMOVE = true }; + + private: + const char* mKey; +}; + +/** + * hashkey wrapper for const char16_t*; at construction, this class duplicates + * a string pointed to by the pointer so that it doesn't matter whether or not + * the string lives longer than the hash table. + */ +class nsUnicharPtrHashKey : public PLDHashEntryHdr { + public: + typedef const char16_t* KeyType; + typedef const char16_t* KeyTypePointer; + + explicit nsUnicharPtrHashKey(const char16_t* aKey) : mKey(NS_xstrdup(aKey)) {} + nsUnicharPtrHashKey(const nsUnicharPtrHashKey& aToCopy) = delete; + nsUnicharPtrHashKey(nsUnicharPtrHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mKey(aOther.mKey) { + aOther.mKey = nullptr; + } + + ~nsUnicharPtrHashKey() { + if (mKey) { + free(const_cast<char16_t*>(mKey)); + } + } + + const char16_t* GetKey() const { return mKey; } + bool KeyEquals(KeyTypePointer aKey) const { return !NS_strcmp(mKey, aKey); } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return mozilla::HashString(aKey); + } + + size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const { + return aMallocSizeOf(mKey); + } + + enum { ALLOW_MEMMOVE = true }; + + private: + const char16_t* mKey; +}; + +namespace mozilla { + +template <typename T> +PLDHashNumber Hash(const T& aValue) { + return aValue.Hash(); +} + +} // namespace mozilla + +/** + * Hashtable key class to use with objects for which Hash() and operator==() + * are defined. + */ +template <typename T> +class nsGenericHashKey : public PLDHashEntryHdr { + public: + typedef const T& KeyType; + typedef const T* KeyTypePointer; + + explicit nsGenericHashKey(KeyTypePointer aKey) : mKey(*aKey) {} + nsGenericHashKey(const nsGenericHashKey&) = delete; + nsGenericHashKey(nsGenericHashKey&& aOther) + : PLDHashEntryHdr(std::move(aOther)), mKey(std::move(aOther.mKey)) {} + + KeyType GetKey() const { return mKey; } + bool KeyEquals(KeyTypePointer aKey) const { return *aKey == mKey; } + + static KeyTypePointer KeyToPointer(KeyType aKey) { return &aKey; } + static PLDHashNumber HashKey(KeyTypePointer aKey) { + return ::mozilla::Hash(*aKey); + } + enum { ALLOW_MEMMOVE = true }; + + private: + T mKey; +}; + +#endif // nsTHashKeys_h__ |