third_party/WebKit/Source/wtf/HashFunctions.h

   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 "wtf/OwnPtr.h"
  25 #include "wtf/RefPtr.h"
  26 #include "wtf/StdLibExtras.h"
  27 #include <stdint.h>
  28
  29 namespace WTF {
  30
  31     template<size_t size> struct IntTypes;
  32     template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_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; };
  35     template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
  36
  37     // integer hash function
  38
  39     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
  40     inline 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
  52     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
  53     inline 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
  65     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
  66     inline 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
  77     // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
  78     inline 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
  91     // Compound integer hash method: http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
  92     inline 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 * key2);
  99         unsigned highBits = static_cast<unsigned>(product >> (sizeof(uint64_t) - sizeof(unsigned)));
 100         return highBits;
 101     }
 102
 103     template<typename T> struct IntHash {
 104         static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
 105         static bool equal(T a, T b) { return a == b; }
 106         static const bool safeToCompareToEmptyOrDeleted = true;
 107     };
 108
 109     template<typename T> struct FloatHash {
 110         typedef typename IntTypes<sizeof(T)>::UnsignedType Bits;
 111         static unsigned hash(T key)
 112         {
 113             return intHash(bitwise_cast<Bits>(key));
 114         }
 115         static bool equal(T a, T b)
 116         {
 117             return bitwise_cast<Bits>(a) == bitwise_cast<Bits>(b);
 118         }
 119         static const bool safeToCompareToEmptyOrDeleted = true;
 120     };
 121
 122     // pointer identity hash function
 123
 124     template<typename T> struct PtrHash {
 125         static unsigned hash(T key)
 126         {
 127 #if COMPILER(MSVC)
 128 #pragma warning(push)
 129 #pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's conversion warnings
 130 #endif
 131             return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key));
 132 #if COMPILER(MSVC)
 133 #pragma warning(pop)
 134 #endif
 135         }
 136         static bool equal(T a, T b) { return a == b; }
 137         static bool equal(std::nullptr_t, T b) { return b == 0; }
 138         static bool equal(T a, std::nullptr_t) { return a == 0; }
 139         static const bool safeToCompareToEmptyOrDeleted = true;
 140     };
 141     template<typename P> struct PtrHash<RefPtr<P>> : PtrHash<P*> {
 142         using PtrHash<P*>::hash;
 143         static unsigned hash(const RefPtr<P>& key) { return hash(key.get()); }
 144         static unsigned hash(const PassRefPtr<P>& key) { return hash(key.get()); }
 145         using PtrHash<P*>::equal;
 146         static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
 147         static bool equal(P* a, const RefPtr<P>& b) { return a == b; }
 148         static bool equal(const RefPtr<P>& a, P* b) { return a == b; }
 149         static bool equal(const RefPtr<P>& a, const PassRefPtr<P>& b) { return a == b; }
 150     };
 151     template<typename P> struct PtrHash<RawPtr<P>> : PtrHash<P*> {
 152         using PtrHash<P*>::hash;
 153         static unsigned hash(const RawPtr<P>& key) { return hash(key.get()); }
 154         using PtrHash<P*>::equal;
 155         static bool equal(const RawPtr<P>& a, const RawPtr<P>& b) { return a == b; }
 156         static bool equal(P* a, const RawPtr<P>& b) { return a == b; }
 157         static bool equal(const RawPtr<P>& a, P* b) { return a == b; }
 158     };
 159     template<typename P> struct PtrHash<OwnPtr<P>> : PtrHash<P*> {
 160         using PtrHash<P*>::hash;
 161         static unsigned hash(const OwnPtr<P>& key) { return hash(key.get()); }
 162         static unsigned hash(const PassOwnPtr<P>& key) { return hash(key.get()); }
 163
 164         static bool equal(const OwnPtr<P>& a, const OwnPtr<P>& b)
 165         {
 166             return a.get() == b.get();
 167         }
 168         static bool equal(const OwnPtr<P>& a, P* b) { return a == b; }
 169         static bool equal(const OwnPtr<P>& a, const PassOwnPtr<P>& b)
 170         {
 171             return a.get() == b.get();
 172         }
 173     };
 174
 175     // default hash function for each type
 176
 177     template<typename T> struct DefaultHash;
 178
 179     template<typename T, typename U> struct PairHash {
 180         static unsigned hash(const std::pair<T, U>& p)
 181         {
 182             return pairIntHash(DefaultHash<T>::Hash::hash(p.first), DefaultHash<U>::Hash::hash(p.second));
 183         }
 184         static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b)
 185         {
 186             return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<U>::Hash::equal(a.second, b.second);
 187         }
 188         static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::safeToCompareToEmptyOrDeleted
 189                                                             && DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted;
 190     };
 191
 192     template<typename T, typename U> struct IntPairHash {
 193         static unsigned hash(const std::pair<T, U>& p) { return pairIntHash(p.first, p.second); }
 194         static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) { return PairHash<T, T>::equal(a, b); }
 195         static const bool safeToCompareToEmptyOrDeleted = PairHash<T, U>::safeToCompareToEmptyOrDeleted;
 196     };
 197
 198     // make IntHash the default hash function for many integer types
 199
 200     template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; };
 201     template<> struct DefaultHash<unsigned short> { typedef IntHash<unsigned> Hash; };
 202     template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
 203     template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
 204     template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
 205     template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
 206     template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
 207     template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
 208
 209 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED)
 210     template<> struct DefaultHash<wchar_t> { typedef IntHash<wchar_t> Hash; };
 211 #endif
 212
 213     template<> struct DefaultHash<float> { typedef FloatHash<float> Hash; };
 214     template<> struct DefaultHash<double> { typedef FloatHash<double> Hash; };
 215
 216     // make PtrHash the default hash function for pointer types that don't specialize
 217
 218     template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
 219     template<typename P> struct DefaultHash<RefPtr<P>> { typedef PtrHash<RefPtr<P>> Hash; };
 220     template<typename P> struct DefaultHash<RawPtr<P>> { typedef PtrHash<RawPtr<P>> Hash; };
 221     template<typename P> struct DefaultHash<OwnPtr<P>> { typedef PtrHash<OwnPtr<P>> Hash; };
 222
 223     // make IntPairHash the default hash function for pairs of (at most) 32-bit integers.
 224
 225     template<> struct DefaultHash<std::pair<short, short>> { typedef IntPairHash<short, short> Hash; };
 226     template<> struct DefaultHash<std::pair<short, unsigned short>> { typedef IntPairHash<short, unsigned short> Hash; };
 227     template<> struct DefaultHash<std::pair<short, int>> { typedef IntPairHash<short, int> Hash; };
 228     template<> struct DefaultHash<std::pair<short, unsigned>> { typedef IntPairHash<short, unsigned> Hash; };
 229     template<> struct DefaultHash<std::pair<unsigned short, short>> { typedef IntPairHash<unsigned short, short> Hash; };
 230     template<> struct DefaultHash<std::pair<unsigned short, unsigned short>> { typedef IntPairHash<unsigned short, unsigned short> Hash; };
 231     template<> struct DefaultHash<std::pair<unsigned short, int>> { typedef IntPairHash<unsigned short, int> Hash; };
 232     template<> struct DefaultHash<std::pair<unsigned short, unsigned>> { typedef IntPairHash<unsigned short, unsigned> Hash; };
 233     template<> struct DefaultHash<std::pair<int, short>> { typedef IntPairHash<int, short> Hash; };
 234     template<> struct DefaultHash<std::pair<int, unsigned short>> { typedef IntPairHash<int, unsigned short> Hash; };
 235     template<> struct DefaultHash<std::pair<int, int>> { typedef IntPairHash<int, int> Hash; };
 236     template<> struct DefaultHash<std::pair<int, unsigned>> { typedef IntPairHash<unsigned, unsigned> Hash; };
 237     template<> struct DefaultHash<std::pair<unsigned, short>> { typedef IntPairHash<unsigned, short> Hash; };
 238     template<> struct DefaultHash<std::pair<unsigned, unsigned short>> { typedef IntPairHash<unsigned, unsigned short> Hash; };
 239     template<> struct DefaultHash<std::pair<unsigned, int>> { typedef IntPairHash<unsigned, int> Hash; };
 240     template<> struct DefaultHash<std::pair<unsigned, unsigned>> { typedef IntPairHash<unsigned, unsigned> Hash; };
 241
 242     // make PairHash the default hash function for pairs of arbitrary values.
 243
 244     template<typename T, typename U> struct DefaultHash<std::pair<T, U>> { typedef PairHash<T, U> Hash; };
 245
 246 } // namespace WTF
 247
 248 using WTF::DefaultHash;
 249 using WTF::IntHash;
 250 using WTF::PtrHash;
 251
 252 #endif // WTF_HashFunctions_h