2 * Copyright (C) 2005, 2006, 2008, 2010 Apple Inc. All rights reserved.
3 * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com>
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
15 * You should have received a copy of the GNU Library General Public License
16 * along with this library; see the file COPYING.LIB. If not, write to
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
21 #ifndef WTF_StringHasher_h
22 #define WTF_StringHasher_h
24 #include <wtf/unicode/Unicode.h>
28 // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
29 static const unsigned stringHashingStartValue = 0x9e3779b9U;
31 // Paul Hsieh's SuperFastHash
32 // http://www.azillionmonkeys.com/qed/hash.html
33 // char* data is interpreted as latin-encoded (zero extended to 16 bits).
35 // NOTE: This class must stay in sync with the create_hash_table script in
36 // JavaScriptCore and the CodeGeneratorJS.pm script in WebCore.
39 static const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
42 : m_hash(stringHashingStartValue)
43 , m_hasPendingCharacter(false)
44 , m_pendingCharacter(0)
48 inline void addCharacters(UChar a, UChar b)
50 ASSERT(!m_hasPendingCharacter);
51 addCharactersToHash(a, b);
54 inline void addCharacter(UChar ch)
56 if (m_hasPendingCharacter) {
57 addCharactersToHash(m_pendingCharacter, ch);
58 m_hasPendingCharacter = false;
62 m_pendingCharacter = ch;
63 m_hasPendingCharacter = true;
66 inline unsigned hash() const
68 unsigned result = m_hash;
71 if (m_hasPendingCharacter) {
72 result += m_pendingCharacter;
73 result ^= result << 11;
74 result += result >> 17;
77 // Force "avalanching" of final 31 bits.
78 result ^= result << 3;
79 result += result >> 5;
80 result ^= result << 2;
81 result += result >> 15;
82 result ^= result << 10;
84 // Reserving space from the high bits for flags preserves most of the hash's
85 // value, since hash lookup typically masks out the high bits anyway.
86 result &= (1u << (sizeof(result) * 8 - flagCount)) - 1;
88 // This avoids ever returning a hash code of 0, since that is used to
89 // signal "hash not computed yet". Setting the high bit maintains
90 // reasonable fidelity to a hash code of 0 because it is likely to yield
91 // exactly 0 when hash lookup masks out the high bits.
93 result = 0x80000000 >> flagCount;
98 template<typename T, UChar Converter(T)> static inline unsigned computeHash(const T* data, unsigned length)
101 bool rem = length & 1;
105 hasher.addCharacters(Converter(data[0]), Converter(data[1]));
110 hasher.addCharacter(Converter(*data));
112 return hasher.hash();
115 template<typename T, UChar Converter(T)> static inline unsigned computeHash(const T* data)
120 UChar b0 = Converter(*data++);
123 UChar b1 = Converter(*data++);
125 hasher.addCharacter(b0);
129 hasher.addCharacters(b0, b1);
132 return hasher.hash();
135 template<typename T> static inline unsigned computeHash(const T* data, unsigned length)
137 return computeHash<T, defaultConverter>(data, length);
140 template<typename T> static inline unsigned computeHash(const T* data)
142 return computeHash<T, defaultConverter>(data);
145 template<size_t length> static inline unsigned hashMemory(const void* data)
147 COMPILE_ASSERT(!(length % 4), length_must_be_a_multible_of_four);
148 return computeHash<UChar>(static_cast<const UChar*>(data), length / sizeof(UChar));
151 static inline unsigned hashMemory(const void* data, unsigned size)
154 return computeHash<UChar>(static_cast<const UChar*>(data), size / sizeof(UChar));
158 static inline UChar defaultConverter(UChar ch)
163 static inline UChar defaultConverter(LChar ch)
168 inline void addCharactersToHash(UChar a, UChar b)
171 unsigned tmp = (b << 11) ^ m_hash;
172 m_hash = (m_hash << 16) ^ tmp;
173 m_hash += m_hash >> 11;
177 bool m_hasPendingCharacter;
178 UChar m_pendingCharacter;
183 using WTF::StringHasher;
185 #endif // WTF_StringHasher_h