OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2008, 2010, 2013 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2008, 2010, 2013 Apple Inc. All rights reserved. |
3 * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com> | 3 * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com> |
4 * | 4 * |
5 * This library is free software; you can redistribute it and/or | 5 * This library is free software; you can redistribute it and/or |
6 * modify it under the terms of the GNU Library General Public | 6 * modify it under the terms of the GNU Library General Public |
7 * License as published by the Free Software Foundation; either | 7 * License as published by the Free Software Foundation; either |
8 * version 2 of the License, or (at your option) any later version. | 8 * version 2 of the License, or (at your option) any later version. |
9 * | 9 * |
10 * This library is distributed in the hope that it will be useful, | 10 * This library is distributed in the hope that it will be useful, |
(...skipping 17 matching lines...) Expand all Loading... |
28 namespace WTF { | 28 namespace WTF { |
29 | 29 |
30 // Paul Hsieh's SuperFastHash | 30 // Paul Hsieh's SuperFastHash |
31 // http://www.azillionmonkeys.com/qed/hash.html | 31 // http://www.azillionmonkeys.com/qed/hash.html |
32 | 32 |
33 // LChar data is interpreted as Latin-1-encoded (zero extended to 16 bits). | 33 // LChar data is interpreted as Latin-1-encoded (zero extended to 16 bits). |
34 | 34 |
35 // NOTE: The hash computation here must stay in sync with | 35 // NOTE: The hash computation here must stay in sync with |
36 // build/scripts/hasher.py. | 36 // build/scripts/hasher.py. |
37 | 37 |
38 // Golden ratio. Arbitrary start value to avoid mapping all zeros to a hash valu
e of zero. | 38 // Golden ratio. Arbitrary start value to avoid mapping all zeros to a hash |
| 39 // value of zero. |
39 static const unsigned stringHashingStartValue = 0x9E3779B9U; | 40 static const unsigned stringHashingStartValue = 0x9E3779B9U; |
40 | 41 |
41 class StringHasher { | 42 class StringHasher { |
42 DISALLOW_NEW(); | 43 DISALLOW_NEW(); |
43 | 44 |
44 public: | 45 public: |
45 static const unsigned flagCount = | 46 static const unsigned flagCount = |
46 8; // Save 8 bits for StringImpl to use as flags. | 47 8; // Save 8 bits for StringImpl to use as flags. |
47 | 48 |
48 StringHasher() | 49 StringHasher() |
49 : m_hash(stringHashingStartValue), | 50 : m_hash(stringHashingStartValue), |
50 m_hasPendingCharacter(false), | 51 m_hasPendingCharacter(false), |
51 m_pendingCharacter(0) {} | 52 m_pendingCharacter(0) {} |
52 | 53 |
53 // The hasher hashes two characters at a time, and thus an "aligned" hasher is
one | 54 // The hasher hashes two characters at a time, and thus an "aligned" hasher is |
54 // where an even number of characters have been added. Callers that always add | 55 // one where an even number of characters have been added. Callers that |
55 // characters two at a time can use the "assuming aligned" functions. | 56 // always add characters two at a time can use the "assuming aligned" |
| 57 // functions. |
56 void addCharactersAssumingAligned(UChar a, UChar b) { | 58 void addCharactersAssumingAligned(UChar a, UChar b) { |
57 ASSERT(!m_hasPendingCharacter); | 59 ASSERT(!m_hasPendingCharacter); |
58 m_hash += a; | 60 m_hash += a; |
59 m_hash = (m_hash << 16) ^ ((b << 11) ^ m_hash); | 61 m_hash = (m_hash << 16) ^ ((b << 11) ^ m_hash); |
60 m_hash += m_hash >> 11; | 62 m_hash += m_hash >> 11; |
61 } | 63 } |
62 | 64 |
63 void addCharacter(UChar character) { | 65 void addCharacter(UChar character) { |
64 if (m_hasPendingCharacter) { | 66 if (m_hasPendingCharacter) { |
65 m_hasPendingCharacter = false; | 67 m_hasPendingCharacter = false; |
(...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
171 hasher.addCharactersAssumingAligned<T, Converter>(data, length); | 173 hasher.addCharactersAssumingAligned<T, Converter>(data, length); |
172 return hasher.hash(); | 174 return hasher.hash(); |
173 } | 175 } |
174 | 176 |
175 template <typename T> | 177 template <typename T> |
176 static unsigned computeHash(const T* data, unsigned length) { | 178 static unsigned computeHash(const T* data, unsigned length) { |
177 return computeHash<T, defaultConverter>(data, length); | 179 return computeHash<T, defaultConverter>(data, length); |
178 } | 180 } |
179 | 181 |
180 static unsigned hashMemory(const void* data, unsigned length) { | 182 static unsigned hashMemory(const void* data, unsigned length) { |
181 // FIXME: Why does this function use the version of the hash that drops the
top 8 bits? | 183 // FIXME: Why does this function use the version of the hash that drops the |
182 // We want that for all string hashing so we can use those bits in StringImp
l and hash | 184 // top 8 bits? We want that for all string hashing so we can use those |
183 // strings consistently, but I don't see why we'd want that for general memo
ry hashing. | 185 // bits in StringImpl and hash strings consistently, but I don't see why |
| 186 // we'd want that for general memory hashing. |
184 ASSERT(!(length % 2)); | 187 ASSERT(!(length % 2)); |
185 return computeHashAndMaskTop8Bits<UChar>(static_cast<const UChar*>(data), | 188 return computeHashAndMaskTop8Bits<UChar>(static_cast<const UChar*>(data), |
186 length / sizeof(UChar)); | 189 length / sizeof(UChar)); |
187 } | 190 } |
188 | 191 |
189 template <size_t length> | 192 template <size_t length> |
190 static unsigned hashMemory(const void* data) { | 193 static unsigned hashMemory(const void* data) { |
191 static_assert(!(length % 2), "length must be a multiple of two"); | 194 static_assert(!(length % 2), "length must be a multiple of two"); |
192 return hashMemory(data, length); | 195 return hashMemory(data, length); |
193 } | 196 } |
(...skipping 26 matching lines...) Expand all Loading... |
220 unsigned m_hash; | 223 unsigned m_hash; |
221 bool m_hasPendingCharacter; | 224 bool m_hasPendingCharacter; |
222 UChar m_pendingCharacter; | 225 UChar m_pendingCharacter; |
223 }; | 226 }; |
224 | 227 |
225 } // namespace WTF | 228 } // namespace WTF |
226 | 229 |
227 using WTF::StringHasher; | 230 using WTF::StringHasher; |
228 | 231 |
229 #endif // WTF_StringHasher_h | 232 #endif // WTF_StringHasher_h |
OLD | NEW |