#ifndef WTF_StringHasher_h
#define WTF_StringHasher_h
#include "wtf/unicode/Unicode.h"
namespace WTF {
static const unsigned stringHashingStartValue = 0x9E3779B9U;
class StringHasher {
public:
static const unsigned flagCount = 8;
StringHasher()
: m_hash(stringHashingStartValue)
, m_hasPendingCharacter(false)
, m_pendingCharacter(0)
{
}
void addCharactersAssumingAligned(UChar a, UChar b)
{
ASSERT(!m_hasPendingCharacter);
m_hash += a;
m_hash = (m_hash << 16) ^ ((b << 11) ^ m_hash);
m_hash += m_hash >> 11;
}
void addCharacter(UChar character)
{
if (m_hasPendingCharacter) {
m_hasPendingCharacter = false;
addCharactersAssumingAligned(m_pendingCharacter, character);
return;
}
m_pendingCharacter = character;
m_hasPendingCharacter = true;
}
void addCharacters(UChar a, UChar b)
{
if (m_hasPendingCharacter) {
#if ASSERT_ENABLED
m_hasPendingCharacter = false;
#endif
addCharactersAssumingAligned(m_pendingCharacter, a);
m_pendingCharacter = b;
#if ASSERT_ENABLED
m_hasPendingCharacter = true;
#endif
return;
}
addCharactersAssumingAligned(a, b);
}
template<typename T, UChar Converter(T)> void addCharactersAssumingAligned(const T* data, unsigned length)
{
ASSERT(!m_hasPendingCharacter);
bool remainder = length & 1;
length >>= 1;
while (length--) {
addCharactersAssumingAligned(Converter(data[0]), Converter(data[1]));
data += 2;
}
if (remainder)
addCharacter(Converter(*data));
}
template<typename T> void addCharactersAssumingAligned(const T* data, unsigned length)
{
addCharactersAssumingAligned<T, defaultConverter>(data, length);
}
template<typename T, UChar Converter(T)> void addCharactersAssumingAligned(const T* data)
{
ASSERT(!m_hasPendingCharacter);
while (T a = *data++) {
T b = *data++;
if (!b) {
addCharacter(Converter(a));
break;
}
addCharactersAssumingAligned(Converter(a), Converter(b));
}
}
template<typename T> void addCharactersAssumingAligned(const T* data)
{
addCharactersAssumingAligned<T, defaultConverter>(data);
}
template<typename T, UChar Converter(T)> void addCharacters(const T* data, unsigned length)
{
if (m_hasPendingCharacter && length) {
m_hasPendingCharacter = false;
addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++));
--length;
}
addCharactersAssumingAligned<T, Converter>(data, length);
}
template<typename T> void addCharacters(const T* data, unsigned length)
{
addCharacters<T, defaultConverter>(data, length);
}
template<typename T, UChar Converter(T)> void addCharacters(const T* data)
{
if (m_hasPendingCharacter && *data) {
m_hasPendingCharacter = false;
addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++));
}
addCharactersAssumingAligned<T, Converter>(data);
}
template<typename T> void addCharacters(const T* data)
{
addCharacters<T, defaultConverter>(data);
}
unsigned hashWithTop8BitsMasked() const
{
unsigned result = avalancheBits();
result &= (1U << (sizeof(result) * 8 - flagCount)) - 1;
if (!result)
result = 0x80000000 >> flagCount;
return result;
}
unsigned hash() const
{
unsigned result = avalancheBits();
if (!result)
result = 0x80000000;
return result;
}
template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
{
StringHasher hasher;
hasher.addCharactersAssumingAligned<T, Converter>(data, length);
return hasher.hashWithTop8BitsMasked();
}
template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data)
{
StringHasher hasher;
hasher.addCharactersAssumingAligned<T, Converter>(data);
return hasher.hashWithTop8BitsMasked();
}
template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
{
return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length);
}
template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data)
{
return computeHashAndMaskTop8Bits<T, defaultConverter>(data);
}
template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data, unsigned length)
{
StringHasher hasher;
hasher.addCharactersAssumingAligned<T, Converter>(data, length);
return hasher.hash();
}
template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data)
{
StringHasher hasher;
hasher.addCharactersAssumingAligned<T, Converter>(data);
return hasher.hash();
}
template<typename T> static unsigned computeHash(const T* data, unsigned length)
{
return computeHash<T, defaultConverter>(data, length);
}
template<typename T> static unsigned computeHash(const T* data)
{
return computeHash<T, defaultConverter>(data);
}
static unsigned hashMemory(const void* data, unsigned length)
{
ASSERT(!(length % 2));
return computeHashAndMaskTop8Bits<UChar>(static_cast<const UChar*>(data), length / sizeof(UChar));
}
template<size_t length> static unsigned hashMemory(const void* data)
{
COMPILE_ASSERT(!(length % 2), length_must_be_a_multiple_of_two);
return hashMemory(data, length);
}
private:
static UChar defaultConverter(UChar character)
{
return character;
}
static UChar defaultConverter(LChar character)
{
return character;
}
unsigned avalancheBits() const
{
unsigned result = m_hash;
if (m_hasPendingCharacter) {
result += m_pendingCharacter;
result ^= result << 11;
result += result >> 17;
}
result ^= result << 3;
result += result >> 5;
result ^= result << 2;
result += result >> 15;
result ^= result << 10;
return result;
}
unsigned m_hash;
bool m_hasPendingCharacter;
UChar m_pendingCharacter;
};
}
using WTF::StringHasher;
#endif