WTF
HashFunctions.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef WTF_HashFunctions_h
00023 #define WTF_HashFunctions_h
00024
00025 #include "RefPtr.h"
00026 #include <kjs/global.h>
00027 #ifdef HAVE_STDINT_H
00028 #include <stdint.h>
00029 #endif
00030
00031 namespace WTF {
00032
00033 template<size_t size> struct IntTypes;
00034 template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t UnsignedType; };
00035 template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t UnsignedType; };
00036 template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t UnsignedType; };
00037 template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
00038
00039
00040
00041
00042 inline unsigned intHash(uint8_t key8)
00043 {
00044 unsigned key = key8;
00045 key += ~(key << 15);
00046 key ^= (key >> 10);
00047 key += (key << 3);
00048 key ^= (key >> 6);
00049 key += ~(key << 11);
00050 key ^= (key >> 16);
00051 return key;
00052 }
00053
00054
00055 inline unsigned intHash(uint16_t key16)
00056 {
00057 unsigned key = key16;
00058 key += ~(key << 15);
00059 key ^= (key >> 10);
00060 key += (key << 3);
00061 key ^= (key >> 6);
00062 key += ~(key << 11);
00063 key ^= (key >> 16);
00064 return key;
00065 }
00066
00067
00068 inline unsigned intHash(uint32_t key)
00069 {
00070 key += ~(key << 15);
00071 key ^= (key >> 10);
00072 key += (key << 3);
00073 key ^= (key >> 6);
00074 key += ~(key << 11);
00075 key ^= (key >> 16);
00076 return key;
00077 }
00078
00079
00080 inline unsigned intHash(uint64_t key)
00081 {
00082 key += ~(key << 32);
00083 key ^= (key >> 22);
00084 key += ~(key << 13);
00085 key ^= (key >> 8);
00086 key += (key << 3);
00087 key ^= (key >> 15);
00088 key += ~(key << 27);
00089 key ^= (key >> 31);
00090 return static_cast<unsigned>(key);
00091 }
00092
00093 template<typename T> struct IntHash {
00094 static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
00095 static bool equal(T a, T b) { return a == b; }
00096 static const bool safeToCompareToEmptyOrDeleted = true;
00097 };
00098
00099 template<typename T> struct FloatHash {
00100 static unsigned hash(T key) { return intHash(*reinterpret_cast<typename IntTypes<sizeof(T)>::UnsignedType*>(&key)); }
00101 static bool equal(T a, T b) { return a == b; }
00102 static const bool safeToCompareToEmptyOrDeleted = true;
00103 };
00104
00105
00106
00107 template<typename T> struct PtrHash {
00108 static unsigned hash(T key)
00109 {
00110 #if COMPILER(MSVC)
00111 #pragma warning(push)
00112 #pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's conversion warnings
00113 #endif
00114 return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key));
00115 #if COMPILER(MSVC)
00116 #pragma warning(pop)
00117 #endif
00118 }
00119 static bool equal(T a, T b) { return a == b; }
00120 static const bool safeToCompareToEmptyOrDeleted = true;
00121 };
00122 template<typename P> struct PtrHash<RefPtr<P> > : PtrHash<P*> {
00123 using PtrHash<P*>::hash;
00124 static unsigned hash(const RefPtr<P>& key) { return hash(key.get()); }
00125 using PtrHash<P*>::equal;
00126 static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
00127 static bool equal(P* a, const RefPtr<P>& b) { return a == b; }
00128 static bool equal(const RefPtr<P>& a, P* b) { return a == b; }
00129 };
00130
00131
00132
00133 template<typename T> struct DefaultHash;
00134
00135 template<typename T, typename U> struct PairHash {
00136 static unsigned hash(const std::pair<T, U>& p)
00137 {
00138 return intHash((static_cast<uint64_t>(DefaultHash<T>::Hash::hash(p.first)) << 32 | DefaultHash<U>::Hash::hash(p.second)));
00139 }
00140 static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b)
00141 {
00142 return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<U>::Hash::equal(a.second, b.second);
00143 }
00144 static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::safeToCompareToEmptyOrDeleted
00145 && DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted;
00146 };
00147
00148
00149
00150 template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; };
00151 template<> struct DefaultHash<unsigned short> { typedef IntHash<unsigned> Hash; };
00152 template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
00153 template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
00154 template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
00155 template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
00156 template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
00157 template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
00158
00159 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED)
00160 template<> struct DefaultHash<wchar_t> { typedef IntHash<wchar_t> Hash; };
00161 #endif
00162
00163 template<> struct DefaultHash<float> { typedef FloatHash<float> Hash; };
00164 template<> struct DefaultHash<double> { typedef FloatHash<double> Hash; };
00165
00166
00167
00168 template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
00169 template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
00170
00171 template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { typedef PairHash<T, U> Hash; };
00172
00173 }
00174
00175 using WTF::DefaultHash;
00176 using WTF::IntHash;
00177 using WTF::PtrHash;
00178
00179 #endif // WTF_HashFunctions_h