Home | History | Annotate | Download | only in wtf 
      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 
     27 namespace 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(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 
    179 using WTF::DefaultHash;
    180 using WTF::IntHash;
    181 using WTF::PtrHash;
    182 
    183 #endif // WTF_HashFunctions_h
    184