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 |