| 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 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 47 typedef uint32_t UnsignedType; | 47 typedef uint32_t UnsignedType; |
| 48 }; | 48 }; |
| 49 template <> | 49 template <> |
| 50 struct IntTypes<8> { | 50 struct IntTypes<8> { |
| 51 typedef int64_t SignedType; | 51 typedef int64_t SignedType; |
| 52 typedef uint64_t UnsignedType; | 52 typedef uint64_t UnsignedType; |
| 53 }; | 53 }; |
| 54 | 54 |
| 55 // integer hash function | 55 // integer hash function |
| 56 | 56 |
| 57 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm | 57 // Thomas Wang's 32 Bit Mix Function: |
| 58 // http://www.cris.com/~Ttwang/tech/inthash.htm |
| 58 inline unsigned hashInt(uint8_t key8) { | 59 inline unsigned hashInt(uint8_t key8) { |
| 59 unsigned key = key8; | 60 unsigned key = key8; |
| 60 key += ~(key << 15); | 61 key += ~(key << 15); |
| 61 key ^= (key >> 10); | 62 key ^= (key >> 10); |
| 62 key += (key << 3); | 63 key += (key << 3); |
| 63 key ^= (key >> 6); | 64 key ^= (key >> 6); |
| 64 key += ~(key << 11); | 65 key += ~(key << 11); |
| 65 key ^= (key >> 16); | 66 key ^= (key >> 16); |
| 66 return key; | 67 return key; |
| 67 } | 68 } |
| 68 | 69 |
| 69 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm | 70 // Thomas Wang's 32 Bit Mix Function: |
| 71 // http://www.cris.com/~Ttwang/tech/inthash.htm |
| 70 inline unsigned hashInt(uint16_t key16) { | 72 inline unsigned hashInt(uint16_t key16) { |
| 71 unsigned key = key16; | 73 unsigned key = key16; |
| 72 key += ~(key << 15); | 74 key += ~(key << 15); |
| 73 key ^= (key >> 10); | 75 key ^= (key >> 10); |
| 74 key += (key << 3); | 76 key += (key << 3); |
| 75 key ^= (key >> 6); | 77 key ^= (key >> 6); |
| 76 key += ~(key << 11); | 78 key += ~(key << 11); |
| 77 key ^= (key >> 16); | 79 key ^= (key >> 16); |
| 78 return key; | 80 return key; |
| 79 } | 81 } |
| 80 | 82 |
| 81 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm | 83 // Thomas Wang's 32 Bit Mix Function: |
| 84 // http://www.cris.com/~Ttwang/tech/inthash.htm |
| 82 inline unsigned hashInt(uint32_t key) { | 85 inline unsigned hashInt(uint32_t key) { |
| 83 key += ~(key << 15); | 86 key += ~(key << 15); |
| 84 key ^= (key >> 10); | 87 key ^= (key >> 10); |
| 85 key += (key << 3); | 88 key += (key << 3); |
| 86 key ^= (key >> 6); | 89 key ^= (key >> 6); |
| 87 key += ~(key << 11); | 90 key += ~(key << 11); |
| 88 key ^= (key >> 16); | 91 key ^= (key >> 16); |
| 89 return key; | 92 return key; |
| 90 } | 93 } |
| 91 | 94 |
| 92 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm | 95 // Thomas Wang's 64 bit Mix Function: |
| 96 // http://www.cris.com/~Ttwang/tech/inthash.htm |
| 93 inline unsigned hashInt(uint64_t key) { | 97 inline unsigned hashInt(uint64_t key) { |
| 94 key += ~(key << 32); | 98 key += ~(key << 32); |
| 95 key ^= (key >> 22); | 99 key ^= (key >> 22); |
| 96 key += ~(key << 13); | 100 key += ~(key << 13); |
| 97 key ^= (key >> 8); | 101 key ^= (key >> 8); |
| 98 key += (key << 3); | 102 key += (key << 3); |
| 99 key ^= (key >> 15); | 103 key ^= (key >> 15); |
| 100 key += ~(key << 27); | 104 key += ~(key << 27); |
| 101 key ^= (key >> 31); | 105 key ^= (key >> 31); |
| 102 return static_cast<unsigned>(key); | 106 return static_cast<unsigned>(key); |
| 103 } | 107 } |
| 104 | 108 |
| 105 // Compound integer hash method: http://opendatastructures.org/versions/edition-
0.1d/ods-java/node33.html#SECTION00832000000000000000 | 109 // Compound integer hash method: |
| 110 // http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECT
ION00832000000000000000 |
| 106 inline unsigned hashInts(unsigned key1, unsigned key2) { | 111 inline unsigned hashInts(unsigned key1, unsigned key2) { |
| 107 unsigned shortRandom1 = 277951225; // A random 32-bit value. | 112 unsigned shortRandom1 = 277951225; // A random 32-bit value. |
| 108 unsigned shortRandom2 = 95187966; // A random 32-bit value. | 113 unsigned shortRandom2 = 95187966; // A random 32-bit value. |
| 109 uint64_t longRandom = 19248658165952622LL; // A random 64-bit value. | 114 uint64_t longRandom = 19248658165952622LL; // A random 64-bit value. |
| 110 | 115 |
| 111 uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * key2); | 116 uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * key2); |
| 112 unsigned highBits = | 117 unsigned highBits = |
| 113 static_cast<unsigned>(product >> (sizeof(uint64_t) - sizeof(unsigned))); | 118 static_cast<unsigned>(product >> (sizeof(uint64_t) - sizeof(unsigned))); |
| 114 return highBits; | 119 return highBits; |
| 115 } | 120 } |
| (...skipping 18 matching lines...) Expand all Loading... |
| 134 static const bool safeToCompareToEmptyOrDeleted = true; | 139 static const bool safeToCompareToEmptyOrDeleted = true; |
| 135 }; | 140 }; |
| 136 | 141 |
| 137 // pointer identity hash function | 142 // pointer identity hash function |
| 138 | 143 |
| 139 template <typename T> | 144 template <typename T> |
| 140 struct PtrHash { | 145 struct PtrHash { |
| 141 static unsigned hash(T* key) { | 146 static unsigned hash(T* key) { |
| 142 #if COMPILER(MSVC) | 147 #if COMPILER(MSVC) |
| 143 #pragma warning(push) | 148 #pragma warning(push) |
| 144 #pragma warning( \ | 149 // work around what seems to be a bug in MSVC's conversion warnings |
| 145 disable : 4244) // work around what seems to be a bug in MSVC's conversion
warnings | 150 #pragma warning(disable : 4244) |
| 146 #endif | 151 #endif |
| 147 return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); | 152 return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); |
| 148 #if COMPILER(MSVC) | 153 #if COMPILER(MSVC) |
| 149 #pragma warning(pop) | 154 #pragma warning(pop) |
| 150 #endif | 155 #endif |
| 151 } | 156 } |
| 152 static bool equal(T* a, T* b) { return a == b; } | 157 static bool equal(T* a, T* b) { return a == b; } |
| 153 static bool equal(std::nullptr_t, T* b) { return !b; } | 158 static bool equal(std::nullptr_t, T* b) { return !b; } |
| 154 static bool equal(T* a, std::nullptr_t) { return !a; } | 159 static bool equal(T* a, std::nullptr_t) { return !a; } |
| 155 static const bool safeToCompareToEmptyOrDeleted = true; | 160 static const bool safeToCompareToEmptyOrDeleted = true; |
| (...skipping 29 matching lines...) Expand all Loading... |
| 185 return a == b.get(); | 190 return a == b.get(); |
| 186 } | 191 } |
| 187 }; | 192 }; |
| 188 | 193 |
| 189 // Default hash function for each type. | 194 // Default hash function for each type. |
| 190 template <typename T> | 195 template <typename T> |
| 191 struct DefaultHash; | 196 struct DefaultHash; |
| 192 | 197 |
| 193 // Actual implementation of DefaultHash. | 198 // Actual implementation of DefaultHash. |
| 194 // | 199 // |
| 195 // The case of |isIntegral| == false is not implemented. If you see a compile er
ror saying DefaultHashImpl<T, false> | 200 // The case of |isIntegral| == false is not implemented. If you see a compile |
| 196 // is not defined, that's because the default hash functions for T are not defin
ed. You need to implement them yourself. | 201 // error saying DefaultHashImpl<T, false> is not defined, that's because the |
| 202 // default hash functions for T are not defined. You need to implement them |
| 203 // yourself. |
| 197 template <typename T, bool isIntegral> | 204 template <typename T, bool isIntegral> |
| 198 struct DefaultHashImpl; | 205 struct DefaultHashImpl; |
| 199 | 206 |
| 200 template <typename T> | 207 template <typename T> |
| 201 struct DefaultHashImpl<T, true> { | 208 struct DefaultHashImpl<T, true> { |
| 202 using Hash = IntHash<typename std::make_unsigned<T>::type>; | 209 using Hash = IntHash<typename std::make_unsigned<T>::type>; |
| 203 }; | 210 }; |
| 204 | 211 |
| 205 // Canonical implementation of DefaultHash. | 212 // Canonical implementation of DefaultHash. |
| 206 template <typename T> | 213 template <typename T> |
| (...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 274 using Hash = PairHash<T, U>; | 281 using Hash = PairHash<T, U>; |
| 275 }; | 282 }; |
| 276 | 283 |
| 277 } // namespace WTF | 284 } // namespace WTF |
| 278 | 285 |
| 279 using WTF::DefaultHash; | 286 using WTF::DefaultHash; |
| 280 using WTF::IntHash; | 287 using WTF::IntHash; |
| 281 using WTF::PtrHash; | 288 using WTF::PtrHash; |
| 282 | 289 |
| 283 #endif // WTF_HashFunctions_h | 290 #endif // WTF_HashFunctions_h |
| OLD | NEW |