File indexing completed on 2024-05-12 15:43:37
0001 /* 0002 * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved. 0003 * 0004 * This library is free software; you can redistribute it and/or 0005 * modify it under the terms of the GNU Library General Public 0006 * License as published by the Free Software Foundation; either 0007 * version 2 of the License, or (at your option) any later version. 0008 * 0009 * This library is distributed in the hope that it will be useful, 0010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 0011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0012 * Library General Public License for more details. 0013 * 0014 * You should have received a copy of the GNU Library General Public License 0015 * along with this library; see the file COPYING.LIB. If not, write to 0016 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0017 * Boston, MA 02110-1301, USA. 0018 * 0019 */ 0020 0021 #ifndef WTF_HashFunctions_h 0022 #define WTF_HashFunctions_h 0023 0024 #include <wtf/RefPtr.h> 0025 #include <kjs/global.h> 0026 #if HAVE_STDINT_H 0027 #include <stdint.h> 0028 #endif 0029 0030 namespace WTF 0031 { 0032 0033 template<size_t size> struct IntTypes; 0034 template<> struct IntTypes<1> { 0035 typedef int8_t SignedType; 0036 typedef uint8_t UnsignedType; 0037 }; 0038 template<> struct IntTypes<2> { 0039 typedef int16_t SignedType; 0040 typedef uint16_t UnsignedType; 0041 }; 0042 template<> struct IntTypes<4> { 0043 typedef int32_t SignedType; 0044 typedef uint32_t UnsignedType; 0045 }; 0046 template<> struct IntTypes<8> { 0047 typedef int64_t SignedType; 0048 typedef uint64_t UnsignedType; 0049 }; 0050 0051 // integer hash function 0052 0053 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm 0054 inline unsigned intHash(uint8_t key8) 0055 { 0056 unsigned key = key8; 0057 key += ~(key << 15); 0058 key ^= (key >> 10); 0059 key += (key << 3); 0060 key ^= (key >> 6); 0061 key += ~(key << 11); 0062 key ^= (key >> 16); 0063 return key; 0064 } 0065 0066 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm 0067 inline unsigned intHash(uint16_t key16) 0068 { 0069 unsigned key = key16; 0070 key += ~(key << 15); 0071 key ^= (key >> 10); 0072 key += (key << 3); 0073 key ^= (key >> 6); 0074 key += ~(key << 11); 0075 key ^= (key >> 16); 0076 return key; 0077 } 0078 0079 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm 0080 inline unsigned intHash(uint32_t key) 0081 { 0082 key += ~(key << 15); 0083 key ^= (key >> 10); 0084 key += (key << 3); 0085 key ^= (key >> 6); 0086 key += ~(key << 11); 0087 key ^= (key >> 16); 0088 return key; 0089 } 0090 0091 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm 0092 inline unsigned intHash(uint64_t key) 0093 { 0094 key += ~(key << 32); 0095 key ^= (key >> 22); 0096 key += ~(key << 13); 0097 key ^= (key >> 8); 0098 key += (key << 3); 0099 key ^= (key >> 15); 0100 key += ~(key << 27); 0101 key ^= (key >> 31); 0102 return static_cast<unsigned>(key); 0103 } 0104 0105 template<typename T> struct IntHash { 0106 static unsigned hash(T key) 0107 { 0108 return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); 0109 } 0110 static bool equal(T a, T b) 0111 { 0112 return a == b; 0113 } 0114 static const bool safeToCompareToEmptyOrDeleted = true; 0115 }; 0116 0117 template<typename T> struct FloatHash { 0118 static unsigned hash(T key) 0119 { 0120 return intHash(*reinterpret_cast<typename IntTypes<sizeof(T)>::UnsignedType *>(&key)); 0121 } 0122 static bool equal(T a, T b) 0123 { 0124 return a == b; 0125 } 0126 static const bool safeToCompareToEmptyOrDeleted = true; 0127 }; 0128 0129 // pointer identity hash function 0130 0131 template<typename T> struct PtrHash { 0132 static unsigned hash(T key) 0133 { 0134 #if defined(WTF_COMPILER_MSVC) 0135 #pragma warning(push) 0136 #pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's conversion warnings 0137 #endif 0138 return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); 0139 #if defined(WTF_COMPILER_MSVC) 0140 #pragma warning(pop) 0141 #endif 0142 } 0143 static bool equal(T a, T b) 0144 { 0145 return a == b; 0146 } 0147 static const bool safeToCompareToEmptyOrDeleted = true; 0148 }; 0149 template<typename P> struct PtrHash<RefPtr<P> > : PtrHash<P *> { 0150 using PtrHash<P *>::hash; 0151 static unsigned hash(const RefPtr<P> &key) 0152 { 0153 return hash(key.get()); 0154 } 0155 using PtrHash<P *>::equal; 0156 static bool equal(const RefPtr<P> &a, const RefPtr<P> &b) 0157 { 0158 return a == b; 0159 } 0160 static bool equal(P *a, const RefPtr<P> &b) 0161 { 0162 return a == b; 0163 } 0164 static bool equal(const RefPtr<P> &a, P *b) 0165 { 0166 return a == b; 0167 } 0168 }; 0169 0170 // default hash function for each type 0171 0172 template<typename T> struct DefaultHash; 0173 0174 template<typename T, typename U> struct PairHash { 0175 static unsigned hash(const std::pair<T, U> &p) 0176 { 0177 return intHash((static_cast<uint64_t>(DefaultHash<T>::Hash::hash(p.first)) << 32 | DefaultHash<U>::Hash::hash(p.second))); 0178 } 0179 static bool equal(const std::pair<T, U> &a, const std::pair<T, U> &b) 0180 { 0181 return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<U>::Hash::equal(a.second, b.second); 0182 } 0183 static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::safeToCompareToEmptyOrDeleted 0184 && DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted; 0185 }; 0186 0187 // make IntHash the default hash function for many integer types 0188 0189 template<> struct DefaultHash<short> { 0190 typedef IntHash<unsigned> Hash; 0191 }; 0192 template<> struct DefaultHash<unsigned short> { 0193 typedef IntHash<unsigned> Hash; 0194 }; 0195 template<> struct DefaultHash<int> { 0196 typedef IntHash<unsigned> Hash; 0197 }; 0198 template<> struct DefaultHash<unsigned> { 0199 typedef IntHash<unsigned> Hash; 0200 }; 0201 template<> struct DefaultHash<long> { 0202 typedef IntHash<unsigned long> Hash; 0203 }; 0204 template<> struct DefaultHash<unsigned long> { 0205 typedef IntHash<unsigned long> Hash; 0206 }; 0207 template<> struct DefaultHash<long long> { 0208 typedef IntHash<unsigned long long> Hash; 0209 }; 0210 template<> struct DefaultHash<unsigned long long> { 0211 typedef IntHash<unsigned long long> Hash; 0212 }; 0213 0214 #if !defined(WTF_COMPILER_MSVC) || defined(_NATIVE_WCHAR_T_DEFINED) 0215 template<> struct DefaultHash<wchar_t> { 0216 typedef IntHash<wchar_t> Hash; 0217 }; 0218 #endif 0219 0220 template<> struct DefaultHash<float> { 0221 typedef FloatHash<float> Hash; 0222 }; 0223 template<> struct DefaultHash<double> { 0224 typedef FloatHash<double> Hash; 0225 }; 0226 0227 // make PtrHash the default hash function for pointer types that don't specialize 0228 0229 template<typename P> struct DefaultHash<P *> { 0230 typedef PtrHash<P *> Hash; 0231 }; 0232 template<typename P> struct DefaultHash<RefPtr<P> > { 0233 typedef PtrHash<RefPtr<P> > Hash; 0234 }; 0235 0236 template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { 0237 typedef PairHash<T, U> Hash; 0238 }; 0239 0240 } // namespace WTF 0241 0242 using WTF::DefaultHash; 0243 using WTF::IntHash; 0244 using WTF::PtrHash; 0245 0246 #endif // WTF_HashFunctions_h