wtf/HashFunctions.h

   1 // -*- mode: c++; c-basic-offset: 4 -*-
   2 /*
   3  * This file is part of the KDE libraries
   4  * Copyright (C) 2005, 2006 Apple Computer, Inc.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Library General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Library General Public License
  17  * along with this library; see the file COPYING.LIB.  If not, write to
  18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  19  * Boston, MA 02110-1301, USA.
  20  *
  21  */
  22
  23 #ifndef WTF_HashFunctions_h
  24 #define WTF_HashFunctions_h
  25
  26 #include "RefPtr.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(uint32_t key)
  41     {
  42         key += ~(key << 15);
  43         key ^= (key >> 10);
  44         key += (key << 3);
  45         key ^= (key >> 6);
  46         key += ~(key << 11);
  47         key ^= (key >> 16);
  48         return key;
  49     }
  50
  51     // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
  52     inline unsigned intHash(uint64_t key)
  53     {
  54         key += ~(key << 32);
  55         key ^= (key >> 22);
  56         key += ~(key << 13);
  57         key ^= (key >> 8);
  58         key += (key << 3);
  59         key ^= (key >> 15);
  60         key += ~(key << 27);
  61         key ^= (key >> 31);
  62         return static_cast<unsigned>(key);
  63     }
  64
  65     template<typename T> struct IntHash {
  66         static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
  67         static bool equal(T a, T b) { return a == b; }
  68         static const bool safeToCompareToEmptyOrDeleted = true;
  69     };
  70
  71     template<typename T> struct FloatHash {
  72         static unsigned hash(T key) { return intHash(*reinterpret_cast<typename IntTypes<sizeof(T)>::UnsignedType*>(&key)); }
  73         static bool equal(T a, T b) { return a == b; }
  74         static const bool safeToCompareToEmptyOrDeleted = true;
  75     };
  76
  77     // pointer identity hash function
  78
  79     template<typename T> struct PtrHash {
  80         static unsigned hash(T key)
  81         {
  82 #if COMPILER(MSVC)
  83 #pragma warning(push)
  84 #pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's conversion warnings
  85 #endif
  86             return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key));
  87 #if COMPILER(MSVC)
  88 #pragma warning(pop)
  89 #endif
  90         }
  91         static bool equal(T a, T b) { return a == b; }
  92         static const bool safeToCompareToEmptyOrDeleted = true;
  93     };
  94     template<typename P> struct PtrHash<RefPtr<P> > {
  95         static unsigned hash(const RefPtr<P>& key) { return PtrHash<P*>::hash(key.get()); }
  96         static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
  97         static const bool safeToCompareToEmptyOrDeleted = true;
  98     };
  99
 100     // default hash function for each type
 101
 102     template<typename T> struct DefaultHash;
 103
 104     // make IntHash the default hash function for many integer types
 105
 106     template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
 107     template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
 108     template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
 109     template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
 110     template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
 111     template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
 112
 113     template<> struct DefaultHash<float> { typedef FloatHash<float> Hash; };
 114     template<> struct DefaultHash<double> { typedef FloatHash<double> Hash; };
 115
 116     // make PtrHash the default hash function for pointer types that don't specialize
 117
 118     template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
 119     template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
 120
 121 } // namespace WTF
 122
 123 using WTF::DefaultHash;
 124 using WTF::IntHash;
 125 using WTF::PtrHash;
 126
 127 #endif // WTF_HashFunctions_h