Bug 1477626 - Introduce mozilla::HashNumber and use it in various places. r=Waldo
Currently we have three ways of representing hash values.
- uint32_t: used in HashFunctions.h.
- PLDHashNumber: defined in PLDHashTable.{h,cpp}.
- js::HashNumber: defined in js/public/Utility.h.
Functions that create hash values with functions from HashFunctions.h use a mix
of these three types. It's a bit of a mess.
This patch introduces mozilla::HashNumber, and redefines PLDHashNumber and
js::HashNumber as synonyms. It also changes HashFunctions.h to use
mozilla::HashNumber throughout instead of uint32_t.
This leaves plenty of places that still use uint32_t that should use
mozilla::HashNumber or one of its synonyms, but I didn't want to tackle that
now.
The patch also:
- Does similar things for the constants defining the number of bits in each
hash number type.
- Moves js::HashNumber from Utility.h to HashTable.h, which is a better spot
for it. (This required changing the signature of ScrambleHashCode(); that's
ok, it'll get moved by the next patch anyway.)
MozReview-Commit-ID: EdoWlCm7OUC
--- a/js/public/HashTable.h
+++ b/js/public/HashTable.h
@@ -13,24 +13,26 @@
#include "mozilla/HashFunctions.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/MemoryChecking.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/Move.h"
#include "mozilla/Opaque.h"
#include "mozilla/PodOperations.h"
#include "mozilla/ReentrancyGuard.h"
-#include "mozilla/TemplateLib.h"
#include "mozilla/TypeTraits.h"
#include "mozilla/UniquePtr.h"
#include "js/Utility.h"
namespace js {
+using HashNumber = mozilla::HashNumber;
+static const uint32_t kHashNumberBits = mozilla::kHashNumberBits;
+
class TempAllocPolicy;
template <class> struct DefaultHasher;
template <class, class> class HashMapEntry;
namespace detail {
template <typename T> class HashTableEntry;
template <class T, class HashPolicy, class AllocPolicy> class HashTable;
} // namespace detail
@@ -1252,31 +1254,30 @@ class HashTable : private AllocPolicy
# define METER(x)
#endif
// The default initial capacity is 32 (enough to hold 16 elements), but it
// can be as low as 4.
static const uint32_t sMinCapacity = 4;
static const uint32_t sMaxInit = JS_BIT(CAP_BITS - 1);
static const uint32_t sMaxCapacity = JS_BIT(CAP_BITS);
- static const uint32_t sHashBits = mozilla::tl::BitSize<HashNumber>::value;
// Hash-table alpha is conceptually a fraction, but to avoid floating-point
// math we implement it as a ratio of integers.
static const uint8_t sAlphaDenominator = 4;
static const uint8_t sMinAlphaNumerator = 1; // min alpha: 1/4
static const uint8_t sMaxAlphaNumerator = 3; // max alpha: 3/4
static const HashNumber sFreeKey = Entry::sFreeKey;
static const HashNumber sRemovedKey = Entry::sRemovedKey;
static const HashNumber sCollisionBit = Entry::sCollisionBit;
void setTableSizeLog2(uint32_t sizeLog2)
{
- hashShift = sHashBits - sizeLog2;
+ hashShift = js::kHashNumberBits - sizeLog2;
}
static bool isLiveHash(HashNumber hash)
{
return Entry::isLiveHash(hash);
}
static HashNumber prepareHash(const Lookup& l)
@@ -1321,17 +1322,17 @@ class HashTable : private AllocPolicy
e->~Entry();
alloc.free_(oldTable, capacity);
}
public:
explicit HashTable(AllocPolicy ap)
: AllocPolicy(ap)
, gen(0)
- , hashShift(sHashBits)
+ , hashShift(js::kHashNumberBits)
, table(nullptr)
, entryCount(0)
, removedCount(0)
#ifdef JS_DEBUG
, mutationCount(0)
, mEntered(false)
#endif
{}
@@ -1397,17 +1398,17 @@ class HashTable : private AllocPolicy
struct DoubleHash
{
HashNumber h2;
HashNumber sizeMask;
};
DoubleHash hash2(HashNumber curKeyHash) const
{
- uint32_t sizeLog2 = sHashBits - hashShift;
+ uint32_t sizeLog2 = js::kHashNumberBits - hashShift;
DoubleHash dh = {
((curKeyHash << sizeLog2) >> hashShift) | 1,
(HashNumber(1) << sizeLog2) - 1
};
return dh;
}
static HashNumber applyDoubleHash(HashNumber h1, const DoubleHash& dh)
@@ -1547,17 +1548,17 @@ class HashTable : private AllocPolicy
enum RebuildStatus { NotOverloaded, Rehashed, RehashFailed };
RebuildStatus changeTableSize(int deltaLog2, FailureBehavior reportFailure = ReportFailure)
{
// Look, but don't touch, until we succeed in getting new entry store.
Entry* oldTable = table;
uint32_t oldCap = capacity();
- uint32_t newLog2 = sHashBits - hashShift + deltaLog2;
+ uint32_t newLog2 = js::kHashNumberBits - hashShift + deltaLog2;
uint32_t newCapacity = JS_BIT(newLog2);
if (MOZ_UNLIKELY(newCapacity > sMaxCapacity)) {
if (reportFailure)
this->reportAllocOverflow();
return RehashFailed;
}
Entry* newTable = createTable(*this, newCapacity, reportFailure);
@@ -1786,17 +1787,17 @@ class HashTable : private AllocPolicy
{
MOZ_ASSERT(table);
return entryCount;
}
uint32_t capacity() const
{
MOZ_ASSERT(table);
- return JS_BIT(sHashBits - hashShift);
+ return JS_BIT(js::kHashNumberBits - hashShift);
}
Generation generation() const
{
MOZ_ASSERT(table);
return Generation(gen);
}
--- a/js/public/Utility.h
+++ b/js/public/Utility.h
@@ -661,20 +661,16 @@ struct FreePolicy
typedef mozilla::UniquePtr<char[], JS::FreePolicy> UniqueChars;
typedef mozilla::UniquePtr<char16_t[], JS::FreePolicy> UniqueTwoByteChars;
} // namespace JS
namespace js {
-/* Integral types for all hash functions. */
-typedef uint32_t HashNumber;
-const unsigned HashNumberSizeBits = 32;
-
namespace detail {
/*
* Given a raw hash code, h, return a number that can be used to select a hash
* bucket.
*
* This function aims to produce as uniform an output distribution as possible,
* especially in the most significant (leftmost) bits, even though the input
@@ -682,35 +678,35 @@ namespace detail {
* be deterministic and quick to compute.
*
* Since the leftmost bits of the result are best, the hash bucket index is
* computed by doing ScrambleHashCode(h) / (2^32/N) or the equivalent
* right-shift, not ScrambleHashCode(h) % N or the equivalent bit-mask.
*
* FIXME: OrderedHashTable uses a bit-mask; see bug 775896.
*/
-inline HashNumber
-ScrambleHashCode(HashNumber h)
+inline uint32_t
+ScrambleHashCode(uint32_t h)
{
/*
* Simply returning h would not cause any hash tables to produce wrong
* answers. But it can produce pathologically bad performance: The caller
* right-shifts the result, keeping only the highest bits. The high bits of
* hash codes are very often completely entropy-free. (So are the lowest
* bits.)
*
* So we use Fibonacci hashing, as described in Knuth, The Art of Computer
* Programming, 6.4. This mixes all the bits of the input hash code h.
*
* The value of goldenRatio is taken from the hex
* expansion of the golden ratio, which starts 1.9E3779B9....
* This value is especially good if values with consecutive hash codes
* are stored in a hash table; see Knuth for details.
*/
- static const HashNumber goldenRatio = 0x9E3779B9U;
+ static const uint32_t goldenRatio = 0x9E3779B9U;
return mozilla::WrappingMultiply(h, goldenRatio);
}
} /* namespace detail */
} /* namespace js */
/* sixgill annotation defines */
--- a/js/src/ds/OrderedHashTable.h
+++ b/js/src/ds/OrderedHashTable.h
@@ -130,17 +130,17 @@ class OrderedHashTable
// clear() requires that members are assigned only after all allocation
// has succeeded, and that this->ranges is left untouched.
hashTable = tableAlloc;
data = dataAlloc;
dataLength = 0;
dataCapacity = capacity;
liveCount = 0;
- hashShift = HashNumberSizeBits - initialBucketsLog2();
+ hashShift = js::kHashNumberBits - initialBucketsLog2();
MOZ_ASSERT(hashBuckets() == buckets);
return true;
}
~OrderedHashTable() {
forEachRange<Range::onTableDestroyed>();
alloc.free_(hashTable, hashBuckets());
freeData(data, dataLength, dataCapacity);
@@ -619,17 +619,17 @@ class OrderedHashTable
public:
HashNumber prepareHash(const Lookup& l) const {
return ScrambleHashCode(Ops::hash(l, hcs));
}
private:
/* The size of hashTable, in elements. Always a power of two. */
uint32_t hashBuckets() const {
- return 1 << (HashNumberSizeBits - hashShift);
+ return 1 << (js::kHashNumberBits - hashShift);
}
static void destroyData(Data* data, uint32_t length) {
for (Data* p = data + length; p != data; )
(--p)->~Data();
}
void freeData(Data* data, uint32_t length, uint32_t capacity) {
@@ -691,17 +691,17 @@ class OrderedHashTable
// If the size of the table is not changing, rehash in place to avoid
// allocating memory.
if (newHashShift == hashShift) {
rehashInPlace();
return true;
}
size_t newHashBuckets =
- size_t(1) << (HashNumberSizeBits - newHashShift);
+ size_t(1) << (js::kHashNumberBits - newHashShift);
Data** newHashTable = alloc.template pod_malloc<Data*>(newHashBuckets);
if (!newHashTable)
return false;
for (uint32_t i = 0; i < newHashBuckets; i++)
newHashTable[i] = nullptr;
uint32_t newCapacity = uint32_t(newHashBuckets * fillFactor());
Data* newData = alloc.template pod_malloc<Data>(newCapacity);
--- a/mfbt/HashFunctions.h
+++ b/mfbt/HashFunctions.h
@@ -2,18 +2,18 @@
/* 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/. */
/* Utilities for hashing. */
/*
- * This file exports functions for hashing data down to a 32-bit value,
- * including:
+ * This file exports functions for hashing data down to a uint32_t (a.k.a.
+ * mozilla::HashNumber), including:
*
* - HashString Hash a char* or char16_t/wchar_t* of known or unknown
* length.
*
* - HashBytes Hash a byte array of known length.
*
* - HashGeneric Hash one or more values. Currently, we support uint32_t,
* types which can be implicitly cast to uint32_t, data
@@ -27,19 +27,19 @@
*
* class ComplexObject
* {
* char* mStr;
* uint32_t mUint1, mUint2;
* void (*mCallbackFn)();
*
* public:
- * uint32_t hash()
+ * HashNumber hash()
* {
- * uint32_t hash = HashString(mStr);
+ * HashNumber hash = HashString(mStr);
* hash = AddToHash(hash, mUint1, mUint2);
* return AddToHash(hash, mCallbackFn);
* }
* };
*
* If you want to hash an nsAString or nsACString, use the HashString functions
* in nsHashKeys.h.
*/
@@ -53,32 +53,35 @@
#include "mozilla/MathAlgorithms.h"
#include "mozilla/Types.h"
#include "mozilla/WrappingOperations.h"
#include <stdint.h>
namespace mozilla {
+typedef uint32_t HashNumber;
+static const uint32_t kHashNumberBits = 32;
+
/**
* The golden ratio as a 32-bit fixed-point value.
*/
-static const uint32_t kGoldenRatioU32 = 0x9E3779B9U;
+static const HashNumber kGoldenRatioU32 = 0x9E3779B9U;
namespace detail {
MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
-constexpr uint32_t
-RotateLeft5(uint32_t aValue)
+constexpr HashNumber
+RotateLeft5(HashNumber aValue)
{
return (aValue << 5) | (aValue >> 27);
}
-constexpr uint32_t
-AddU32ToHash(uint32_t aHash, uint32_t aValue)
+constexpr HashNumber
+AddU32ToHash(HashNumber aHash, uint32_t aValue)
{
/*
* This is the meat of all our hash routines. This hash function is not
* particularly sophisticated, but it seems to work well for our mostly
* plain-text inputs. Implementation notes follow.
*
* Our use of the golden ratio here is arbitrary; we could pick almost any
* number which:
@@ -119,25 +122,25 @@ AddU32ToHash(uint32_t aHash, uint32_t aV
return mozilla::WrappingMultiply(kGoldenRatioU32,
RotateLeft5(aHash) ^ aValue);
}
/**
* AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
*/
template<size_t PtrSize>
-constexpr uint32_t
-AddUintptrToHash(uint32_t aHash, uintptr_t aValue)
+constexpr HashNumber
+AddUintptrToHash(HashNumber aHash, uintptr_t aValue)
{
return AddU32ToHash(aHash, static_cast<uint32_t>(aValue));
}
template<>
-inline uint32_t
-AddUintptrToHash<8>(uint32_t aHash, uintptr_t aValue)
+inline HashNumber
+AddUintptrToHash<8>(HashNumber aHash, uintptr_t aValue)
{
uint32_t v1 = static_cast<uint32_t>(aValue);
uint32_t v2 = static_cast<uint32_t>(static_cast<uint64_t>(aValue) >> 32);
return AddU32ToHash(AddU32ToHash(aHash, v1), v2);
}
} /* namespace detail */
@@ -146,188 +149,188 @@ AddUintptrToHash<8>(uint32_t aHash, uint
* inputs.
*
* Currently, we support hashing uint32_t's, values which we can implicitly
* convert to uint32_t, data pointers, and function pointers.
*/
template<typename T,
bool TypeIsNotIntegral = !mozilla::IsIntegral<T>::value,
typename U = typename mozilla::EnableIf<TypeIsNotIntegral>::Type>
-MOZ_MUST_USE inline uint32_t
-AddToHash(uint32_t aHash, T aA)
+MOZ_MUST_USE inline HashNumber
+AddToHash(HashNumber aHash, T aA)
{
/*
* Try to convert |A| to uint32_t implicitly. If this works, great. If not,
* we'll error out.
*/
return detail::AddU32ToHash(aHash, aA);
}
template<typename A>
-MOZ_MUST_USE inline uint32_t
-AddToHash(uint32_t aHash, A* aA)
+MOZ_MUST_USE inline HashNumber
+AddToHash(HashNumber aHash, A* aA)
{
/*
* You might think this function should just take a void*. But then we'd only
* catch data pointers and couldn't handle function pointers.
*/
static_assert(sizeof(aA) == sizeof(uintptr_t), "Strange pointer!");
return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, uintptr_t(aA));
}
// We use AddUintptrToHash() for hashing all integral types. 8-byte integral types
// are treated the same as 64-bit pointers, and smaller integral types are first
// implicitly converted to 32 bits and then passed to AddUintptrToHash() to be hashed.
template<typename T,
typename U = typename mozilla::EnableIf<mozilla::IsIntegral<T>::value>::Type>
-MOZ_MUST_USE constexpr uint32_t
-AddToHash(uint32_t aHash, T aA)
+MOZ_MUST_USE constexpr HashNumber
+AddToHash(HashNumber aHash, T aA)
{
return detail::AddUintptrToHash<sizeof(T)>(aHash, aA);
}
template<typename A, typename... Args>
-MOZ_MUST_USE uint32_t
-AddToHash(uint32_t aHash, A aArg, Args... aArgs)
+MOZ_MUST_USE HashNumber
+AddToHash(HashNumber aHash, A aArg, Args... aArgs)
{
return AddToHash(AddToHash(aHash, aArg), aArgs...);
}
/**
* The HashGeneric class of functions let you hash one or more values.
*
* If you want to hash together two values x and y, calling HashGeneric(x, y) is
* much better than calling AddToHash(x, y), because AddToHash(x, y) assumes
* that x has already been hashed.
*/
template<typename... Args>
-MOZ_MUST_USE inline uint32_t
+MOZ_MUST_USE inline HashNumber
HashGeneric(Args... aArgs)
{
return AddToHash(0, aArgs...);
}
namespace detail {
template<typename T>
-uint32_t
+HashNumber
HashUntilZero(const T* aStr)
{
- uint32_t hash = 0;
+ HashNumber hash = 0;
for (T c; (c = *aStr); aStr++) {
hash = AddToHash(hash, c);
}
return hash;
}
// This is a `constexpr` alternative to HashUntilZero(const T*). It should
// only be used for compile-time computation because it uses recursion.
// XXX: once support for GCC 4.9 is dropped, this function should be removed
// and HashUntilZero(const T*) should be made `constexpr`.
template<typename T>
-constexpr uint32_t
-ConstExprHashUntilZero(const T* aStr, uint32_t aHash)
+constexpr HashNumber
+ConstExprHashUntilZero(const T* aStr, HashNumber aHash)
{
return !*aStr
? aHash
: ConstExprHashUntilZero(aStr + 1, AddToHash(aHash, *aStr));
}
template<typename T>
-uint32_t
+HashNumber
HashKnownLength(const T* aStr, size_t aLength)
{
- uint32_t hash = 0;
+ HashNumber hash = 0;
for (size_t i = 0; i < aLength; i++) {
hash = AddToHash(hash, aStr[i]);
}
return hash;
}
} /* namespace detail */
/**
* The HashString overloads below do just what you'd expect.
*
* If you have the string's length, you might as well call the overload which
* includes the length. It may be marginally faster.
*/
-MOZ_MUST_USE inline uint32_t
+MOZ_MUST_USE inline HashNumber
HashString(const char* aStr)
{
return detail::HashUntilZero(reinterpret_cast<const unsigned char*>(aStr));
}
-MOZ_MUST_USE inline uint32_t
+MOZ_MUST_USE inline HashNumber
HashString(const char* aStr, size_t aLength)
{
return detail::HashKnownLength(reinterpret_cast<const unsigned char*>(aStr), aLength);
}
MOZ_MUST_USE
-inline uint32_t
+inline HashNumber
HashString(const unsigned char* aStr, size_t aLength)
{
return detail::HashKnownLength(aStr, aLength);
}
-MOZ_MUST_USE inline uint32_t
+MOZ_MUST_USE inline HashNumber
HashString(const char16_t* aStr)
{
return detail::HashUntilZero(aStr);
}
// This is a `constexpr` alternative to HashString(const char16_t*). It should
// only be used for compile-time computation because it uses recursion.
//
// You may need to use the
// MOZ_{PUSH,POP}_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING macros if you use
// this function. See the comment on those macros' definitions for more detail.
//
// XXX: once support for GCC 4.9 is dropped, this function should be removed
// and HashString(const char16_t*) should be made `constexpr`.
-MOZ_MUST_USE constexpr uint32_t
+MOZ_MUST_USE constexpr HashNumber
ConstExprHashString(const char16_t* aStr)
{
return detail::ConstExprHashUntilZero(aStr, 0);
}
-MOZ_MUST_USE inline uint32_t
+MOZ_MUST_USE inline HashNumber
HashString(const char16_t* aStr, size_t aLength)
{
return detail::HashKnownLength(aStr, aLength);
}
/*
* On Windows, wchar_t is not the same as char16_t, even though it's
* the same width!
*/
#ifdef WIN32
-MOZ_MUST_USE inline uint32_t
+MOZ_MUST_USE inline HashNumber
HashString(const wchar_t* aStr)
{
return detail::HashUntilZero(aStr);
}
-MOZ_MUST_USE inline uint32_t
+MOZ_MUST_USE inline HashNumber
HashString(const wchar_t* aStr, size_t aLength)
{
return detail::HashKnownLength(aStr, aLength);
}
#endif
/**
* Hash some number of bytes.
*
* This hash walks word-by-word, rather than byte-by-byte, so you won't get the
* same result out of HashBytes as you would out of HashString.
*/
-MOZ_MUST_USE extern MFBT_API uint32_t
+MOZ_MUST_USE extern MFBT_API HashNumber
HashBytes(const void* bytes, size_t aLength);
/**
* A pseudorandom function mapping 32-bit integers to 32-bit integers.
*
* This is for when you're feeding private data (like pointer values or credit
* card numbers) to a non-crypto hash function (like HashBytes) and then using
* the hash code for something that untrusted parties could observe (like a JS
@@ -350,20 +353,20 @@ class HashCodeScrambler
public:
/** Creates a new scrambler with the given 128-bit key. */
constexpr HashCodeScrambler(uint64_t aK0, uint64_t aK1) : mK0(aK0), mK1(aK1) {}
/**
* Scramble a hash code. Always produces the same result for the same
* combination of key and hash code.
*/
- uint32_t scramble(uint32_t aHashCode) const
+ HashNumber scramble(HashNumber aHashCode) const
{
SipHasher hasher(mK0, mK1);
- return uint32_t(hasher.sipHash(aHashCode));
+ return HashNumber(hasher.sipHash(aHashCode));
}
private:
struct SipHasher
{
SipHasher(uint64_t aK0, uint64_t aK1)
{
// 1. Initialization.
--- a/xpcom/ds/PLDHashTable.cpp
+++ b/xpcom/ds/PLDHashTable.cpp
@@ -188,17 +188,17 @@ PLDHashTable::HashShift(uint32_t aEntryS
BestCapacity(aLength, &capacity, &log2);
uint32_t nbytes;
if (!SizeOfEntryStore(capacity, aEntrySize, &nbytes)) {
MOZ_CRASH("Initial entry store size is too large");
}
// Compute the hashShift value.
- return kHashBits - log2;
+ return kPLDHashNumberBits - log2;
}
PLDHashTable::PLDHashTable(const PLDHashTableOps* aOps, uint32_t aEntrySize,
uint32_t aLength)
: mOps(recordreplay::GeneratePLDHashTableCallbacks(aOps))
, mEntryStore()
, mGeneration(0)
, mHashShift(HashShift(aEntrySize, aLength))
@@ -267,17 +267,17 @@ PLDHashTable::Hash1(PLDHashNumber aHash0
{
return aHash0 >> mHashShift;
}
void
PLDHashTable::Hash2(PLDHashNumber aHash0,
uint32_t& aHash2Out, uint32_t& aSizeMaskOut) const
{
- uint32_t sizeLog2 = kHashBits - mHashShift;
+ uint32_t sizeLog2 = kPLDHashNumberBits - mHashShift;
uint32_t sizeMask = (PLDHashNumber(1) << sizeLog2) - 1;
aSizeMaskOut = sizeMask;
// The incoming aHash0 always has the low bit unset (since we leave it
// free for the collision flag), and should have reasonably random
// data in the other 31 bits. We used the high bits of aHash0 for
// Hash1, so we use the low bits here. If the table size is large,
// the bits we use may overlap, but that's still more random than
@@ -472,17 +472,17 @@ PLDHashTable::FindFreeEntry(PLDHashNumbe
}
bool
PLDHashTable::ChangeTable(int32_t aDeltaLog2)
{
MOZ_ASSERT(mEntryStore.Get());
// Look, but don't touch, until we succeed in getting new entry store.
- int32_t oldLog2 = kHashBits - mHashShift;
+ int32_t oldLog2 = kPLDHashNumberBits - mHashShift;
int32_t newLog2 = oldLog2 + aDeltaLog2;
uint32_t newCapacity = 1u << newLog2;
if (newCapacity > kMaxCapacity) {
return false;
}
uint32_t nbytes;
if (!SizeOfEntryStore(newCapacity, mEntrySize, &nbytes)) {
@@ -490,17 +490,17 @@ PLDHashTable::ChangeTable(int32_t aDelta
}
char* newEntryStore = (char*)calloc(1, nbytes);
if (!newEntryStore) {
return false;
}
// We can't fail from here on, so update table parameters.
- mHashShift = kHashBits - newLog2;
+ mHashShift = kPLDHashNumberBits - newLog2;
mRemovedCount = 0;
// Assign the new entry store to table.
char* oldEntryStore;
char* oldEntryAddr;
oldEntryAddr = oldEntryStore = mEntryStore.Get();
mEntryStore.Set(newEntryStore, &mGeneration);
PLDHashMoveEntry moveEntry = mOps->moveEntry;
@@ -694,17 +694,17 @@ void
PLDHashTable::ShrinkIfAppropriate()
{
uint32_t capacity = Capacity();
if (mRemovedCount >= capacity >> 2 ||
(capacity > kMinCapacity && mEntryCount <= MinLoad(capacity))) {
uint32_t log2;
BestCapacity(mEntryCount, &capacity, &log2);
- int32_t deltaLog2 = log2 - (kHashBits - mHashShift);
+ int32_t deltaLog2 = log2 - (kPLDHashNumberBits - mHashShift);
MOZ_ASSERT(deltaLog2 <= 0);
(void) ChangeTable(deltaLog2);
}
}
size_t
PLDHashTable::ShallowSizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const
--- a/xpcom/ds/PLDHashTable.h
+++ b/xpcom/ds/PLDHashTable.h
@@ -5,22 +5,24 @@
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifndef PLDHashTable_h
#define PLDHashTable_h
#include "mozilla/Atomics.h"
#include "mozilla/Attributes.h" // for MOZ_ALWAYS_INLINE
#include "mozilla/fallible.h"
+#include "mozilla/HashFunctions.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/Move.h"
#include "mozilla/Types.h"
#include "nscore.h"
-typedef uint32_t PLDHashNumber;
+using PLDHashNumber = mozilla::HashNumber;
+static const uint32_t kPLDHashNumberBits = mozilla::kHashNumberBits;
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.
@@ -498,17 +500,16 @@ public:
Iterator ConstIter() const
{
return Iterator(const_cast<PLDHashTable*>(this));
}
private:
// Multiplicative hash uses an unsigned 32 bit integer and the golden ratio,
// expressed as a fixed-point 32-bit fraction.
- static const uint32_t kHashBits = 32;
static const uint32_t kGoldenRatio = 0x9E3779B9U;
static uint32_t HashShift(uint32_t aEntrySize, uint32_t aLength);
static const PLDHashNumber kCollisionFlag = 1;
static bool EntryIsFree(const PLDHashEntryHdr* aEntry)
{
@@ -539,17 +540,17 @@ private:
static bool MatchEntryKeyhash(const PLDHashEntryHdr* aEntry,
const PLDHashNumber aHash);
PLDHashEntryHdr* AddressEntry(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 << (kHashBits - mHashShift));
+ return ((uint32_t)1 << (kPLDHashNumberBits - mHashShift));
}
PLDHashNumber ComputeKeyHash(const void* aKey) const;
enum SearchReason { ForSearchOrRemove, ForAdd };
template <SearchReason Reason>
PLDHashEntryHdr* NS_FASTCALL