Imported WebKit commit c7503cef7ecb236730d1309676ab9fc723fd061d (http://svn.webkit.org/repository/webkit/trunk@128886)

New snapshot with various build fixes

1 files changed, 40 insertions, 1 deletions

diff --git a/Source/WTF/wtf/HashFunctions.h b/Source/WTF/wtf/HashFunctions.h
index 808b2b1e5..eb1b2f0cc 100644
--- a/Source/WTF/wtf/HashFunctions.h
+++ b/Source/WTF/wtf/HashFunctions.h
@@ -86,6 +86,18 @@ namespace WTF {
         return static_cast<unsigned>(key);
     }
 
+    // Compound integer hash method: http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
+    inline unsigned pairIntHash(unsigned key1, unsigned key2)
+    {
+        unsigned shortRandom1 = 277951225; // A random 32-bit value.
+        unsigned shortRandom2 = 95187966; // A random 32-bit value.
+        uint64_t longRandom = 19248658165952622LL; // A random 64-bit value.
+
+        uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * key2);
+        unsigned highBits = static_cast<unsigned>(product >> (sizeof(uint64_t) - sizeof(unsigned)));
+        return highBits;
+    }
+
     template<typename T> struct IntHash {
         static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
         static bool equal(T a, T b) { return a == b; }
@@ -139,7 +151,7 @@ namespace WTF {
     template<typename T, typename U> struct PairHash {
         static unsigned hash(const std::pair<T, U>& p)
         {
-            return intHash((static_cast<uint64_t>(DefaultHash<T>::Hash::hash(p.first)) << 32 | DefaultHash<U>::Hash::hash(p.second)));
+            return pairIntHash(DefaultHash<T>::Hash::hash(p.first), DefaultHash<U>::Hash::hash(p.second));
         }
         static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b)
         {
@@ -149,6 +161,12 @@ namespace WTF {
                                                             && DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted;
     };
 
+    template<typename T, typename U> struct IntPairHash {
+        static unsigned hash(const std::pair<T, U>& p) { return pairIntHash(p.first, p.second); }
+        static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) { return PairHash<T, T>::equal(a, b); }
+        static const bool safeToCompareToEmptyOrDeleted = PairHash<T, U>::safeToCompareToEmptyOrDeleted;
+    };
+
     // make IntHash the default hash function for many integer types
 
     template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; };
@@ -172,6 +190,27 @@ namespace WTF {
     template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
     template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
 
+    // make IntPairHash the default hash function for pairs of (at most) 32-bit integers.
+
+    template<> struct DefaultHash<std::pair<short, short> > { typedef IntPairHash<short, short> Hash; };
+    template<> struct DefaultHash<std::pair<short, unsigned short> > { typedef IntPairHash<short, unsigned short> Hash; };
+    template<> struct DefaultHash<std::pair<short, int> > { typedef IntPairHash<short, int> Hash; };
+    template<> struct DefaultHash<std::pair<short, unsigned> > { typedef IntPairHash<short, unsigned> Hash; };
+    template<> struct DefaultHash<std::pair<unsigned short, short> > { typedef IntPairHash<unsigned short, short> Hash; };
+    template<> struct DefaultHash<std::pair<unsigned short, unsigned short> > { typedef IntPairHash<unsigned short, unsigned short> Hash; };
+    template<> struct DefaultHash<std::pair<unsigned short, int> > { typedef IntPairHash<unsigned short, int> Hash; };
+    template<> struct DefaultHash<std::pair<unsigned short, unsigned> > { typedef IntPairHash<unsigned short, unsigned> Hash; };
+    template<> struct DefaultHash<std::pair<int, short> > { typedef IntPairHash<int, short> Hash; };
+    template<> struct DefaultHash<std::pair<int, unsigned short> > { typedef IntPairHash<int, unsigned short> Hash; };
+    template<> struct DefaultHash<std::pair<int, int> > { typedef IntPairHash<int, int> Hash; };
+    template<> struct DefaultHash<std::pair<int, unsigned> > { typedef IntPairHash<unsigned, unsigned> Hash; };
+    template<> struct DefaultHash<std::pair<unsigned, short> > { typedef IntPairHash<unsigned, short> Hash; };
+    template<> struct DefaultHash<std::pair<unsigned, unsigned short> > { typedef IntPairHash<unsigned, unsigned short> Hash; };
+    template<> struct DefaultHash<std::pair<unsigned, int> > { typedef IntPairHash<unsigned, int> Hash; };
+    template<> struct DefaultHash<std::pair<unsigned, unsigned> > { typedef IntPairHash<unsigned, unsigned> Hash; };
+
+    // make PairHash the default hash function for pairs of arbitrary values.
+
     template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { typedef PairHash<T, U> Hash; };
 
 } // namespace WTF