WTF

HashFunctions.h

00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  * This file is part of the KDE libraries
00004  * Copyright (C) 2005, 2006 Apple Computer, Inc.
00005  *
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Library General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2 of the License, or (at your option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Library General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU Library General Public License
00017  * along with this library; see the file COPYING.LIB.  If not, write to
00018  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00019  * Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #ifndef WTF_HashFunctions_h
00024 #define WTF_HashFunctions_h
00025 
00026 #include <kjs/global.h>
00027 #ifdef HAVE_STDINT_H
00028 #include <stdint.h>
00029 #endif
00030 #include "RefPtr.h"
00031 
00032 namespace WTF {
00033 
00034     template<size_t size> struct IntTypes;
00035     template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t UnsignedType; };
00036     template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t UnsignedType; };
00037     template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t UnsignedType; };
00038     template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
00039 
00040     // integer hash function
00041 
00042     // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
00043     inline unsigned intHash(uint32_t key) 
00044     {
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 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
00055     inline unsigned intHash(uint64_t key)
00056     {
00057         key += ~(key << 32);
00058         key ^= (key >> 22);
00059         key += ~(key << 13);
00060         key ^= (key >> 8);
00061         key += (key << 3);
00062         key ^= (key >> 15);
00063         key += ~(key << 27);
00064         key ^= (key >> 31);
00065         return static_cast<unsigned>(key);
00066     }
00067 
00068     template<typename T> struct IntHash {
00069         static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
00070         static bool equal(T a, T b) { return a == b; }
00071     };
00072 
00073     // pointer identity hash function
00074 
00075     template<typename T> struct PtrHash {
00076         static unsigned hash(T key) { return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); }
00077         static bool equal(T a, T b) { return a == b; }
00078     };
00079     template<typename P> struct PtrHash<RefPtr<P> > {
00080         static unsigned hash(const RefPtr<P>& key) { return PtrHash<P*>::hash(key.get()); }
00081         static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
00082     };
00083 
00084     // default hash function for each type
00085 
00086     template<typename T> struct DefaultHash;
00087 
00088     // make IntHash the default hash function for many integer types
00089 
00090     template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
00091     template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
00092     template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
00093     template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
00094     template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
00095     template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
00096 
00097     // make PtrHash the default hash function for pointer types that don't specialize
00098 
00099     template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
00100     template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
00101 
00102 } // namespace WTF
00103 
00104 using WTF::DefaultHash;
00105 using WTF::IntHash;
00106 using WTF::PtrHash;
00107 
00108 #endif // KXLMCORE_HashFunctions_h
WTF

HashFunctions.h

WTF

kdelibs
