| 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 |