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 19 matching lines...) Expand all Loading... |
30 | 30 |
31 template<size_t size> struct IntTypes; | 31 template<size_t size> struct IntTypes; |
32 template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t U
nsignedType; }; | 32 template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t U
nsignedType; }; |
33 template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t
UnsignedType; }; | 33 template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t
UnsignedType; }; |
34 template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t
UnsignedType; }; | 34 template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t
UnsignedType; }; |
35 template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t
UnsignedType; }; | 35 template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t
UnsignedType; }; |
36 | 36 |
37 // integer hash function | 37 // integer hash function |
38 | 38 |
39 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | 39 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm |
40 inline unsigned intHash(uint8_t key8) | 40 unsigned intHash(uint8_t key8); |
41 { | |
42 unsigned key = key8; | |
43 key += ~(key << 15); | |
44 key ^= (key >> 10); | |
45 key += (key << 3); | |
46 key ^= (key >> 6); | |
47 key += ~(key << 11); | |
48 key ^= (key >> 16); | |
49 return key; | |
50 } | |
51 | 41 |
52 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | 42 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm |
53 inline unsigned intHash(uint16_t key16) | 43 unsigned intHash(uint16_t key16); |
54 { | |
55 unsigned key = key16; | |
56 key += ~(key << 15); | |
57 key ^= (key >> 10); | |
58 key += (key << 3); | |
59 key ^= (key >> 6); | |
60 key += ~(key << 11); | |
61 key ^= (key >> 16); | |
62 return key; | |
63 } | |
64 | 44 |
65 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | 45 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm |
66 inline unsigned intHash(uint32_t key) | 46 unsigned intHash(uint32_t key); |
67 { | |
68 key += ~(key << 15); | |
69 key ^= (key >> 10); | |
70 key += (key << 3); | |
71 key ^= (key >> 6); | |
72 key += ~(key << 11); | |
73 key ^= (key >> 16); | |
74 return key; | |
75 } | |
76 | 47 |
77 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm | 48 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/intha
sh.htm |
78 inline unsigned intHash(uint64_t key) | 49 unsigned intHash(uint64_t key); |
79 { | |
80 key += ~(key << 32); | |
81 key ^= (key >> 22); | |
82 key += ~(key << 13); | |
83 key ^= (key >> 8); | |
84 key += (key << 3); | |
85 key ^= (key >> 15); | |
86 key += ~(key << 27); | |
87 key ^= (key >> 31); | |
88 return static_cast<unsigned>(key); | |
89 } | |
90 | 50 |
91 // Compound integer hash method: http://opendatastructures.org/versions/edit
ion-0.1d/ods-java/node33.html#SECTION00832000000000000000 | 51 // Compound integer hash method: http://opendatastructures.org/versions/edit
ion-0.1d/ods-java/node33.html#SECTION00832000000000000000 |
92 inline unsigned pairIntHash(unsigned key1, unsigned key2) | 52 unsigned pairIntHash(unsigned key1, unsigned key2); |
93 { | |
94 unsigned shortRandom1 = 277951225; // A random 32-bit value. | |
95 unsigned shortRandom2 = 95187966; // A random 32-bit value. | |
96 uint64_t longRandom = 19248658165952622LL; // A random 64-bit value. | |
97 | |
98 uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * ke
y2); | |
99 unsigned highBits = static_cast<unsigned>(product >> (sizeof(uint64_t) -
sizeof(unsigned))); | |
100 return highBits; | |
101 } | |
102 | 53 |
103 template<typename T> struct IntHash { | 54 template<typename T> struct IntHash { |
104 static unsigned hash(T key) { return intHash(static_cast<typename IntTyp
es<sizeof(T)>::UnsignedType>(key)); } | 55 static unsigned hash(T key) { return intHash(static_cast<typename IntTyp
es<sizeof(T)>::UnsignedType>(key)); } |
105 static bool equal(T a, T b) { return a == b; } | 56 static bool equal(T a, T b) { return a == b; } |
106 static const bool safeToCompareToEmptyOrDeleted = true; | 57 static const bool safeToCompareToEmptyOrDeleted = true; |
107 }; | 58 }; |
108 | 59 |
109 template<typename T> struct FloatHash { | 60 template<typename T> struct FloatHash { |
110 typedef typename IntTypes<sizeof(T)>::UnsignedType Bits; | 61 typedef typename IntTypes<sizeof(T)>::UnsignedType Bits; |
111 static unsigned hash(T key) | 62 static unsigned hash(T key) |
(...skipping 131 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
243 | 194 |
244 template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { type
def PairHash<T, U> Hash; }; | 195 template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { type
def PairHash<T, U> Hash; }; |
245 | 196 |
246 } // namespace WTF | 197 } // namespace WTF |
247 | 198 |
248 using WTF::DefaultHash; | 199 using WTF::DefaultHash; |
249 using WTF::IntHash; | 200 using WTF::IntHash; |
250 using WTF::PtrHash; | 201 using WTF::PtrHash; |
251 | 202 |
252 #endif // WTF_HashFunctions_h | 203 #endif // WTF_HashFunctions_h |
OLD | NEW |