• Skip to content
  • Skip to link menu
KDE 4.3 API Reference
  • KDE API Reference
  • kdelibs
  • Sitemap
  • Contact Us
 

WTF

HashFunctions.h

Go to the documentation of this file.
00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  * Copyright (C) 2005, 2006, 2008 Apple Inc. All rights reserved.
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it under the terms of the GNU Library General Public
00007  * License as published by the Free Software Foundation; either
00008  * version 2 of the License, or (at your option) any later version.
00009  *
00010  * This library is distributed in the hope that it will be useful,
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  * Library General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU Library General Public License
00016  * along with this library; see the file COPYING.LIB.  If not, write to
00017  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00018  * Boston, MA 02110-1301, USA.
00019  *
00020  */
00021 
00022 #ifndef WTF_HashFunctions_h
00023 #define WTF_HashFunctions_h
00024 
00025 #include "RefPtr.h"
00026 #include <kjs/global.h>
00027 #ifdef HAVE_STDINT_H
00028 #include <stdint.h>
00029 #endif
00030 
00031 namespace WTF {
00032 
00033     template<size_t size> struct IntTypes;
00034     template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t UnsignedType; };
00035     template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t UnsignedType; };
00036     template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t UnsignedType; };
00037     template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
00038 
00039     // integer hash function
00040 
00041     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
00042     inline unsigned intHash(uint8_t key8)
00043     {
00044         unsigned key = key8;
00045         key += ~(key << 15);
00046         key ^= (key >> 10);
00047         key += (key << 3);
00048         key ^= (key >> 6);
00049         key += ~(key << 11);
00050         key ^= (key >> 16);
00051         return key;
00052     }
00053 
00054     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
00055     inline unsigned intHash(uint16_t key16)
00056     {
00057         unsigned key = key16;
00058         key += ~(key << 15);
00059         key ^= (key >> 10);
00060         key += (key << 3);
00061         key ^= (key >> 6);
00062         key += ~(key << 11);
00063         key ^= (key >> 16);
00064         return key;
00065     }
00066 
00067     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
00068     inline unsigned intHash(uint32_t key) 
00069     {
00070         key += ~(key << 15);
00071         key ^= (key >> 10);
00072         key += (key << 3);
00073         key ^= (key >> 6);
00074         key += ~(key << 11);
00075         key ^= (key >> 16);
00076         return key;
00077     }
00078     
00079     // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
00080     inline unsigned intHash(uint64_t key)
00081     {
00082         key += ~(key << 32);
00083         key ^= (key >> 22);
00084         key += ~(key << 13);
00085         key ^= (key >> 8);
00086         key += (key << 3);
00087         key ^= (key >> 15);
00088         key += ~(key << 27);
00089         key ^= (key >> 31);
00090         return static_cast<unsigned>(key);
00091     }
00092 
00093     template<typename T> struct IntHash {
00094         static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
00095         static bool equal(T a, T b) { return a == b; }
00096         static const bool safeToCompareToEmptyOrDeleted = true;
00097     };
00098 
00099     template<typename T> struct FloatHash {
00100         static unsigned hash(T key) { return intHash(*reinterpret_cast<typename IntTypes<sizeof(T)>::UnsignedType*>(&key)); }
00101         static bool equal(T a, T b) { return a == b; }
00102         static const bool safeToCompareToEmptyOrDeleted = true;
00103     };
00104 
00105     // pointer identity hash function
00106 
00107     template<typename T> struct PtrHash {
00108         static unsigned hash(T key)
00109         {
00110 #if COMPILER(MSVC)
00111 #pragma warning(push)
00112 #pragma warning(disable: 4244) // work around what seems to be a bug in MSVC's conversion warnings
00113 #endif
00114             return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key));
00115 #if COMPILER(MSVC)
00116 #pragma warning(pop)
00117 #endif
00118         }
00119         static bool equal(T a, T b) { return a == b; }
00120         static const bool safeToCompareToEmptyOrDeleted = true;
00121     };
00122     template<typename P> struct PtrHash<RefPtr<P> > : PtrHash<P*> {
00123         using PtrHash<P*>::hash;
00124         static unsigned hash(const RefPtr<P>& key) { return hash(key.get()); }
00125         using PtrHash<P*>::equal;
00126         static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
00127         static bool equal(P* a, const RefPtr<P>& b) { return a == b; }
00128         static bool equal(const RefPtr<P>& a, P* b) { return a == b; }
00129     };
00130 
00131     // default hash function for each type
00132 
00133     template<typename T> struct DefaultHash;
00134 
00135     template<typename T, typename U> struct PairHash {
00136         static unsigned hash(const std::pair<T, U>& p)
00137         {
00138             return intHash((static_cast<uint64_t>(DefaultHash<T>::Hash::hash(p.first)) << 32 | DefaultHash<U>::Hash::hash(p.second)));
00139         }
00140         static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b)
00141         {
00142             return DefaultHash<T>::Hash::equal(a.first, b.first) && DefaultHash<U>::Hash::equal(a.second, b.second);
00143         }
00144         static const bool safeToCompareToEmptyOrDeleted = DefaultHash<T>::Hash::safeToCompareToEmptyOrDeleted 
00145                                                             && DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted;
00146     };
00147 
00148     // make IntHash the default hash function for many integer types
00149 
00150     template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; };
00151     template<> struct DefaultHash<unsigned short> { typedef IntHash<unsigned> Hash; };
00152     template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
00153     template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
00154     template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
00155     template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
00156     template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
00157     template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
00158 
00159 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED)
00160     template<> struct DefaultHash<wchar_t> { typedef IntHash<wchar_t> Hash; };
00161 #endif
00162 
00163     template<> struct DefaultHash<float> { typedef FloatHash<float> Hash; };
00164     template<> struct DefaultHash<double> { typedef FloatHash<double> Hash; };
00165 
00166     // make PtrHash the default hash function for pointer types that don't specialize
00167 
00168     template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
00169     template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
00170 
00171     template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { typedef PairHash<T, U> Hash; };
00172 
00173 } // namespace WTF
00174 
00175 using WTF::DefaultHash;
00176 using WTF::IntHash;
00177 using WTF::PtrHash;
00178 
00179 #endif // WTF_HashFunctions_h

WTF

Skip menu "WTF"
  • Main Page
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members
  • Related Pages

kdelibs

Skip menu "kdelibs"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • Kate
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.6.1
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal