15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 2926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * Copyright (C) 2005, 2006, 2008, 2010, 2013 Apple Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com> 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is free software; you can redistribute it and/or 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modify it under the terms of the GNU Library General Public 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * License as published by the Free Software Foundation; either 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * version 2 of the License, or (at your option) any later version. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is distributed in the hope that it will be useful, 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * but WITHOUT ANY WARRANTY; without even the implied warranty of 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Library General Public License for more details. 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * You should have received a copy of the GNU Library General Public License 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * along with this library; see the file COPYING.LIB. If not, write to 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Boston, MA 02110-1301, USA. 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 21926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef WTF_StringHasher_h 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define WTF_StringHasher_h 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 25591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/unicode/Unicode.h" 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Paul Hsieh's SuperFastHash 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// http://www.azillionmonkeys.com/qed/hash.html 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 32926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)// LChar data is interpreted as Latin-1-encoded (zero extended to 16 bits). 33926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 34926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)// NOTE: The hash computation here must stay in sync with the create_hash_table script in 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// JavaScriptCore and the CodeGeneratorJS.pm script in WebCore. 36926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 37926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)// Golden ratio. Arbitrary start value to avoid mapping all zeros to a hash value of zero. 38926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)static const unsigned stringHashingStartValue = 0x9E3779B9U; 39926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)class StringHasher { 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)public: 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags. 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 44926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) StringHasher() 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : m_hash(stringHashingStartValue) 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_hasPendingCharacter(false) 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) , m_pendingCharacter(0) 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 51926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // The hasher hashes two characters at a time, and thus an "aligned" hasher is one 52926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // where an even number of characters have been added. Callers that always add 53926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // characters two at a time can use the "assuming aligned" functions. 54926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void addCharactersAssumingAligned(UChar a, UChar b) 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(!m_hasPendingCharacter); 57926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_hash += a; 58926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_hash = (m_hash << 16) ^ ((b << 11) ^ m_hash); 59926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_hash += m_hash >> 11; 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 62926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void addCharacter(UChar character) 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_hasPendingCharacter) { 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_hasPendingCharacter = false; 66926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharactersAssumingAligned(m_pendingCharacter, character); 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 70926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_pendingCharacter = character; 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) m_hasPendingCharacter = true; 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 74926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) void addCharacters(UChar a, UChar b) 75926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 76926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (m_hasPendingCharacter) { 77197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 78926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_hasPendingCharacter = false; 79926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)#endif 80926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharactersAssumingAligned(m_pendingCharacter, a); 81926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_pendingCharacter = b; 82197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) 83926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_hasPendingCharacter = true; 84926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles)#endif 85926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return; 86926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 87926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 88926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharactersAssumingAligned(a, b); 89926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 90926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 91926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, UChar Converter(T)> void addCharactersAssumingAligned(const T* data, unsigned length) 92926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 93926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT(!m_hasPendingCharacter); 94926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 95926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) bool remainder = length & 1; 96926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) length >>= 1; 97926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 98926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) while (length--) { 99926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharactersAssumingAligned(Converter(data[0]), Converter(data[1])); 100926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) data += 2; 101926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 102926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 103926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (remainder) 104926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharacter(Converter(*data)); 105926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 106926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 107926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T> void addCharactersAssumingAligned(const T* data, unsigned length) 108926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 109926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharactersAssumingAligned<T, defaultConverter>(data, length); 110926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 111926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 112926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, UChar Converter(T)> void addCharacters(const T* data, unsigned length) 113926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 114926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) if (m_hasPendingCharacter && length) { 115926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) m_hasPendingCharacter = false; 116926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++)); 117926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) --length; 118926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 119926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharactersAssumingAligned<T, Converter>(data, length); 120926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 121926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 122926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T> void addCharacters(const T* data, unsigned length) 123926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) { 124926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) addCharacters<T, defaultConverter>(data, length); 125926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) } 126926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) 127926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned hashWithTop8BitsMasked() const 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned result = avalancheBits(); 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Reserving space from the high bits for flags preserves most of the hash's 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // value, since hash lookup typically masks out the high bits anyway. 133926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) result &= (1U << (sizeof(result) * 8 - flagCount)) - 1; 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This avoids ever returning a hash code of 0, since that is used to 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // signal "hash not computed yet". Setting the high bit maintains 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // reasonable fidelity to a hash code of 0 because it is likely to yield 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // exactly 0 when hash lookup masks out the high bits. 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!result) 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result = 0x80000000 >> flagCount; 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 145926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned hash() const 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned result = avalancheBits(); 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This avoids ever returning a hash code of 0, since that is used to 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // signal "hash not computed yet". Setting the high bit maintains 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // reasonable fidelity to a hash code of 0 because it is likely to yield 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // exactly 0 when hash lookup masks out the high bits. 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!result) 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result = 0x80000000; 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 159926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length) 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) StringHasher hasher; 162926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) hasher.addCharactersAssumingAligned<T, Converter>(data, length); 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return hasher.hashWithTop8BitsMasked(); 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 166926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length) 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length); 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 171926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T, UChar Converter(T)> static unsigned computeHash(const T* data, unsigned length) 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) StringHasher hasher; 174926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) hasher.addCharactersAssumingAligned<T, Converter>(data, length); 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return hasher.hash(); 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 178926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<typename T> static unsigned computeHash(const T* data, unsigned length) 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return computeHash<T, defaultConverter>(data, length); 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 183926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) static unsigned hashMemory(const void* data, unsigned length) 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 185926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // FIXME: Why does this function use the version of the hash that drops the top 8 bits? 186926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // We want that for all string hashing so we can use those bits in StringImpl and hash 187926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) // strings consistently, but I don't see why we'd want that for general memory hashing. 188926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) ASSERT(!(length % 2)); 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return computeHashAndMaskTop8Bits<UChar>(static_cast<const UChar*>(data), length / sizeof(UChar)); 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 192926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) template<size_t length> static unsigned hashMemory(const void* data) 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 194926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) COMPILE_ASSERT(!(length % 2), length_must_be_a_multiple_of_two); 195926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return hashMemory(data, length); 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)private: 199926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) static UChar defaultConverter(UChar character) 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 201926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return character; 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 204926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) static UChar defaultConverter(LChar character) 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 206926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return character; 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 209926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) unsigned avalancheBits() const 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned result = m_hash; 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Handle end case. 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (m_hasPendingCharacter) { 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result += m_pendingCharacter; 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result ^= result << 11; 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result += result >> 17; 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Force "avalanching" of final 31 bits. 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result ^= result << 3; 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result += result >> 5; 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result ^= result << 2; 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result += result >> 15; 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result ^= result << 10; 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned m_hash; 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool m_hasPendingCharacter; 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UChar m_pendingCharacter; 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::StringHasher; 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // WTF_StringHasher_h 240