OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
8 * | 8 * |
9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
54 key += ~(key << 15); | 54 key += ~(key << 15); |
55 key ^= (key >> 10); | 55 key ^= (key >> 10); |
56 key += (key << 3); | 56 key += (key << 3); |
57 key ^= (key >> 6); | 57 key ^= (key >> 6); |
58 key += ~(key << 11); | 58 key += ~(key << 11); |
59 key ^= (key >> 16); | 59 key ^= (key >> 16); |
60 return key; | 60 return key; |
61 } | 61 } |
62 | 62 |
63 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | 63 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm |
64 inline unsigned intHash(uint32_t key) | 64 inline unsigned intHash(uint32_t key) |
65 { | 65 { |
66 key += ~(key << 15); | 66 key += ~(key << 15); |
67 key ^= (key >> 10); | 67 key ^= (key >> 10); |
68 key += (key << 3); | 68 key += (key << 3); |
69 key ^= (key >> 6); | 69 key ^= (key >> 6); |
70 key += ~(key << 11); | 70 key += ~(key << 11); |
71 key ^= (key >> 16); | 71 key ^= (key >> 16); |
72 return key; | 72 return key; |
73 } | 73 } |
74 | 74 |
75 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | 75 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm |
76 inline unsigned intHash(uint64_t key) | 76 inline unsigned intHash(uint64_t key) |
77 { | 77 { |
78 key += ~(key << 32); | 78 key += ~(key << 32); |
79 key ^= (key >> 22); | 79 key ^= (key >> 22); |
80 key += ~(key << 13); | 80 key += ~(key << 13); |
81 key ^= (key >> 8); | 81 key ^= (key >> 8); |
82 key += (key << 3); | 82 key += (key << 3); |
83 key ^= (key >> 15); | 83 key ^= (key >> 15); |
84 key += ~(key << 27); | 84 key += ~(key << 27); |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
149 | 149 |
150 template<typename T, typename U> struct PairHash { | 150 template<typename T, typename U> struct PairHash { |
151 static unsigned hash(const std::pair<T, U>& p) | 151 static unsigned hash(const std::pair<T, U>& p) |
152 { | 152 { |
153 return pairIntHash(DefaultHash<T>::Hash::hash(p.first), DefaultHash<
U>::Hash::hash(p.second)); | 153 return pairIntHash(DefaultHash<T>::Hash::hash(p.first), DefaultHash<
U>::Hash::hash(p.second)); |
154 } | 154 } |
155 static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) | 155 static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) |
156 { | 156 { |
157 return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<
U>::Hash::equal(a.second, b.second); | 157 return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<
U>::Hash::equal(a.second, b.second); |
158 } | 158 } |
159 static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::
safeToCompareToEmptyOrDeleted | 159 static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::
safeToCompareToEmptyOrDeleted |
160 && DefaultHash<U>::H
ash::safeToCompareToEmptyOrDeleted; | 160 && DefaultHash<U>::H
ash::safeToCompareToEmptyOrDeleted; |
161 }; | 161 }; |
162 | 162 |
163 template<typename T, typename U> struct IntPairHash { | 163 template<typename T, typename U> struct IntPairHash { |
164 static unsigned hash(const std::pair<T, U>& p) { return pairIntHash(p.fi
rst, p.second); } | 164 static unsigned hash(const std::pair<T, U>& p) { return pairIntHash(p.fi
rst, p.second); } |
165 static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) {
return PairHash<T, T>::equal(a, b); } | 165 static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) {
return PairHash<T, T>::equal(a, b); } |
166 static const bool safeToCompareToEmptyOrDeleted = PairHash<T, U>::safeTo
CompareToEmptyOrDeleted; | 166 static const bool safeToCompareToEmptyOrDeleted = PairHash<T, U>::safeTo
CompareToEmptyOrDeleted; |
167 }; | 167 }; |
168 | 168 |
169 // make IntHash the default hash function for many integer types | 169 // make IntHash the default hash function for many integer types |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
212 | 212 |
213 template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { type
def PairHash<T, U> Hash; }; | 213 template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { type
def PairHash<T, U> Hash; }; |
214 | 214 |
215 } // namespace WTF | 215 } // namespace WTF |
216 | 216 |
217 using WTF::DefaultHash; | 217 using WTF::DefaultHash; |
218 using WTF::IntHash; | 218 using WTF::IntHash; |
219 using WTF::PtrHash; | 219 using WTF::PtrHash; |
220 | 220 |
221 #endif // WTF_HashFunctions_h | 221 #endif // WTF_HashFunctions_h |
OLD | NEW |