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