1/*
2 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public License
15 * along with this library; see the file COPYING.LIB. If not, write to
16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 *
19 */
20
21#ifndef WTF_HashFunctions_h
22#define WTF_HashFunctions_h
23
24#include "RefPtr.h"
25#include <stdint.h>
26
27namespace WTF {
28
29 template<size_t size> struct IntTypes;
30 template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t UnsignedType; };
31 template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t UnsignedType; };
32 template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t UnsignedType; };
33 template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
34
35 // integer hash function
36
37 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
38 inline unsigned intHash(uint8_t key8)
39 {
40 unsigned key = key8;
41 key += ~(key << 15);
42 key ^= (key >> 10);
43 key += (key << 3);
44 key ^= (key >> 6);
45 key += ~(key << 11);
46 key ^= (key >> 16);
47 return key;
48 }
49
50 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
51 inline unsigned intHash(uint16_t key16)
52 {
53 unsigned key = key16;
54 key += ~(key << 15);
55 key ^= (key >> 10);
56 key += (key << 3);
57 key ^= (key >> 6);
58 key += ~(key << 11);
59 key ^= (key >> 16);
60 return key;
61 }
62
63 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
64 inline unsigned intHash(uint32_t key)
65 {
66 key += ~(key << 15);
67 key ^= (key >> 10);
68 key += (key << 3);
69 key ^= (key >> 6);
70 key += ~(key << 11);
71 key ^= (key >> 16);
72 return key;
73 }
74
75 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
76 inline unsigned intHash(uint64_t key)
77 {
78 key += ~(key << 32);
79 key ^= (key >> 22);
80 key += ~(key << 13);
81 key ^= (key >> 8);
82 key += (key << 3);
83 key ^= (key >> 15);
84 key += ~(key << 27);
85 key ^= (key >> 31);
86 return static_cast<unsigned>(key);
87 }
88
89 template<typename T> struct IntHash {
90 static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
91 static bool equal(T a, T b) { return a == b; }
92 static const bool safeToCompareToEmptyOrDeleted = true;
93 };
94
95 template<typename T> struct FloatHash {
96 static unsigned hash(T key)
97 {
98 union {
99 T key;
100 typename IntTypes<sizeof(T)>::UnsignedType bits;
101 } u;
102 u.key = key;
103 return intHash(u.bits);
104 }
105 static bool equal(T a, T b) { return a == b; }
106 static const bool safeToCompareToEmptyOrDeleted = true;
107 };
108
109 // pointer identity hash function
110
111 template<typename T> struct PtrHash {
112 static unsigned hash(T key)
113 {
114#if COMPILER(MSVC)
115#pragma warning(push)
116#pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's conversion warnings
117#endif
118 return IntHash<uintptr_t>::hash(key: reinterpret_cast<uintptr_t>(key));
119#if COMPILER(MSVC)
120#pragma warning(pop)
121#endif
122 }
123 static bool equal(T a, T b) { return a == b; }
124 static const bool safeToCompareToEmptyOrDeleted = true;
125 };
126 template<typename P> struct PtrHash<RefPtr<P> > : PtrHash<P*> {
127 using PtrHash<P*>::hash;
128 static unsigned hash(const RefPtr<P>& key) { return hash(key.get()); }
129 using PtrHash<P*>::equal;
130 static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
131 static bool equal(P* a, const RefPtr<P>& b) { return a == b; }
132 static bool equal(const RefPtr<P>& a, P* b) { return a == b; }
133 };
134
135 // default hash function for each type
136
137 template<typename T> struct DefaultHash;
138
139 template<typename T, typename U> struct PairHash {
140 static unsigned hash(const std::pair<T, U>& p)
141 {
142 return intHash((static_cast<uint64_t>(DefaultHash<T>::Hash::hash(p.first)) << 32 | DefaultHash<U>::Hash::hash(p.second)));
143 }
144 static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b)
145 {
146 return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<U>::Hash::equal(a.second, b.second);
147 }
148 static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::safeToCompareToEmptyOrDeleted
149 && DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted;
150 };
151
152 // make IntHash the default hash function for many integer types
153
154 template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; };
155 template<> struct DefaultHash<unsigned short> { typedef IntHash<unsigned> Hash; };
156 template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
157 template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
158 template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
159 template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
160 template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
161 template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
162
163#if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED)
164 template<> struct DefaultHash<wchar_t> { typedef IntHash<wchar_t> Hash; };
165#endif
166
167 template<> struct DefaultHash<float> { typedef FloatHash<float> Hash; };
168 template<> struct DefaultHash<double> { typedef FloatHash<double> Hash; };
169
170 // make PtrHash the default hash function for pointer types that don't specialize
171
172 template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
173 template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
174
175 template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { typedef PairHash<T, U> Hash; };
176
177} // namespace WTF
178
179using WTF::DefaultHash;
180using WTF::IntHash;
181using WTF::PtrHash;
182
183#endif // WTF_HashFunctions_h
184

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/wtf/HashFunctions.h