| 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 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 102 | 102 |
| 103 if (remainder) | 103 if (remainder) |
| 104 addCharacter(Converter(*data)); | 104 addCharacter(Converter(*data)); |
| 105 } | 105 } |
| 106 | 106 |
| 107 template<typename T> void addCharactersAssumingAligned(const T* data, unsign
ed length) | 107 template<typename T> void addCharactersAssumingAligned(const T* data, unsign
ed length) |
| 108 { | 108 { |
| 109 addCharactersAssumingAligned<T, defaultConverter>(data, length); | 109 addCharactersAssumingAligned<T, defaultConverter>(data, length); |
| 110 } | 110 } |
| 111 | 111 |
| 112 template<typename T, UChar Converter(T)> void addCharactersAssumingAligned(c
onst T* data) | |
| 113 { | |
| 114 ASSERT(!m_hasPendingCharacter); | |
| 115 | |
| 116 while (T a = *data++) { | |
| 117 T b = *data++; | |
| 118 if (!b) { | |
| 119 addCharacter(Converter(a)); | |
| 120 break; | |
| 121 } | |
| 122 addCharactersAssumingAligned(Converter(a), Converter(b)); | |
| 123 } | |
| 124 } | |
| 125 | |
| 126 template<typename T> void addCharactersAssumingAligned(const T* data) | |
| 127 { | |
| 128 addCharactersAssumingAligned<T, defaultConverter>(data); | |
| 129 } | |
| 130 | |
| 131 template<typename T, UChar Converter(T)> void addCharacters(const T* data, u
nsigned length) | 112 template<typename T, UChar Converter(T)> void addCharacters(const T* data, u
nsigned length) |
| 132 { | 113 { |
| 133 if (m_hasPendingCharacter && length) { | 114 if (m_hasPendingCharacter && length) { |
| 134 m_hasPendingCharacter = false; | 115 m_hasPendingCharacter = false; |
| 135 addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++))
; | 116 addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++))
; |
| 136 --length; | 117 --length; |
| 137 } | 118 } |
| 138 addCharactersAssumingAligned<T, Converter>(data, length); | 119 addCharactersAssumingAligned<T, Converter>(data, length); |
| 139 } | 120 } |
| 140 | 121 |
| 141 template<typename T> void addCharacters(const T* data, unsigned length) | 122 template<typename T> void addCharacters(const T* data, unsigned length) |
| 142 { | 123 { |
| 143 addCharacters<T, defaultConverter>(data, length); | 124 addCharacters<T, defaultConverter>(data, length); |
| 144 } | 125 } |
| 145 | 126 |
| 146 template<typename T, UChar Converter(T)> void addCharacters(const T* data) | |
| 147 { | |
| 148 if (m_hasPendingCharacter && *data) { | |
| 149 m_hasPendingCharacter = false; | |
| 150 addCharactersAssumingAligned(m_pendingCharacter, Converter(*data++))
; | |
| 151 } | |
| 152 addCharactersAssumingAligned<T, Converter>(data); | |
| 153 } | |
| 154 | |
| 155 template<typename T> void addCharacters(const T* data) | |
| 156 { | |
| 157 addCharacters<T, defaultConverter>(data); | |
| 158 } | |
| 159 | |
| 160 unsigned hashWithTop8BitsMasked() const | 127 unsigned hashWithTop8BitsMasked() const |
| 161 { | 128 { |
| 162 unsigned result = avalancheBits(); | 129 unsigned result = avalancheBits(); |
| 163 | 130 |
| 164 // Reserving space from the high bits for flags preserves most of the ha
sh's | 131 // Reserving space from the high bits for flags preserves most of the ha
sh's |
| 165 // value, since hash lookup typically masks out the high bits anyway. | 132 // value, since hash lookup typically masks out the high bits anyway. |
| 166 result &= (1U << (sizeof(result) * 8 - flagCount)) - 1; | 133 result &= (1U << (sizeof(result) * 8 - flagCount)) - 1; |
| 167 | 134 |
| 168 // This avoids ever returning a hash code of 0, since that is used to | 135 // This avoids ever returning a hash code of 0, since that is used to |
| 169 // signal "hash not computed yet". Setting the high bit maintains | 136 // signal "hash not computed yet". Setting the high bit maintains |
| (...skipping 19 matching lines...) Expand all Loading... |
| 189 return result; | 156 return result; |
| 190 } | 157 } |
| 191 | 158 |
| 192 template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskT
op8Bits(const T* data, unsigned length) | 159 template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskT
op8Bits(const T* data, unsigned length) |
| 193 { | 160 { |
| 194 StringHasher hasher; | 161 StringHasher hasher; |
| 195 hasher.addCharactersAssumingAligned<T, Converter>(data, length); | 162 hasher.addCharactersAssumingAligned<T, Converter>(data, length); |
| 196 return hasher.hashWithTop8BitsMasked(); | 163 return hasher.hashWithTop8BitsMasked(); |
| 197 } | 164 } |
| 198 | 165 |
| 199 template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskT
op8Bits(const T* data) | |
| 200 { | |
| 201 StringHasher hasher; | |
| 202 hasher.addCharactersAssumingAligned<T, Converter>(data); | |
| 203 return hasher.hashWithTop8BitsMasked(); | |
| 204 } | |
| 205 | |
| 206 template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* dat
a, unsigned length) | 166 template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* dat
a, unsigned length) |
| 207 { | 167 { |
| 208 return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length); | 168 return computeHashAndMaskTop8Bits<T, defaultConverter>(data, length); |
| 209 } | 169 } |
| 210 | 170 |
| 211 template<typename T> static unsigned computeHashAndMaskTop8Bits(const T* dat
a) | |
| 212 { | |
| 213 return computeHashAndMaskTop8Bits<T, defaultConverter>(data); | |
| 214 } | |
| 215 | |
| 216 template<typename T, UChar Converter(T)> static unsigned computeHash(const T
* data, unsigned length) | 171 template<typename T, UChar Converter(T)> static unsigned computeHash(const T
* data, unsigned length) |
| 217 { | 172 { |
| 218 StringHasher hasher; | 173 StringHasher hasher; |
| 219 hasher.addCharactersAssumingAligned<T, Converter>(data, length); | 174 hasher.addCharactersAssumingAligned<T, Converter>(data, length); |
| 220 return hasher.hash(); | 175 return hasher.hash(); |
| 221 } | 176 } |
| 222 | 177 |
| 223 template<typename T, UChar Converter(T)> static unsigned computeHash(const T
* data) | |
| 224 { | |
| 225 StringHasher hasher; | |
| 226 hasher.addCharactersAssumingAligned<T, Converter>(data); | |
| 227 return hasher.hash(); | |
| 228 } | |
| 229 | |
| 230 template<typename T> static unsigned computeHash(const T* data, unsigned len
gth) | 178 template<typename T> static unsigned computeHash(const T* data, unsigned len
gth) |
| 231 { | 179 { |
| 232 return computeHash<T, defaultConverter>(data, length); | 180 return computeHash<T, defaultConverter>(data, length); |
| 233 } | 181 } |
| 234 | 182 |
| 235 template<typename T> static unsigned computeHash(const T* data) | |
| 236 { | |
| 237 return computeHash<T, defaultConverter>(data); | |
| 238 } | |
| 239 | |
| 240 static unsigned hashMemory(const void* data, unsigned length) | 183 static unsigned hashMemory(const void* data, unsigned length) |
| 241 { | 184 { |
| 242 // FIXME: Why does this function use the version of the hash that drops
the top 8 bits? | 185 // FIXME: Why does this function use the version of the hash that drops
the top 8 bits? |
| 243 // We want that for all string hashing so we can use those bits in Strin
gImpl and hash | 186 // We want that for all string hashing so we can use those bits in Strin
gImpl and hash |
| 244 // strings consistently, but I don't see why we'd want that for general
memory hashing. | 187 // strings consistently, but I don't see why we'd want that for general
memory hashing. |
| 245 ASSERT(!(length % 2)); | 188 ASSERT(!(length % 2)); |
| 246 return computeHashAndMaskTop8Bits<UChar>(static_cast<const UChar*>(data)
, length / sizeof(UChar)); | 189 return computeHashAndMaskTop8Bits<UChar>(static_cast<const UChar*>(data)
, length / sizeof(UChar)); |
| 247 } | 190 } |
| 248 | 191 |
| 249 template<size_t length> static unsigned hashMemory(const void* data) | 192 template<size_t length> static unsigned hashMemory(const void* data) |
| (...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 287 unsigned m_hash; | 230 unsigned m_hash; |
| 288 bool m_hasPendingCharacter; | 231 bool m_hasPendingCharacter; |
| 289 UChar m_pendingCharacter; | 232 UChar m_pendingCharacter; |
| 290 }; | 233 }; |
| 291 | 234 |
| 292 } // namespace WTF | 235 } // namespace WTF |
| 293 | 236 |
| 294 using WTF::StringHasher; | 237 using WTF::StringHasher; |
| 295 | 238 |
| 296 #endif // WTF_StringHasher_h | 239 #endif // WTF_StringHasher_h |
| OLD | NEW |